Orthtree generalization

[JacksonCampolattaro]

Summary of Changes

Orthtree is no longer restricted to only subdividing a Point_set_3, the contents of the tree are now a customization point of its Traits type.

Orthtree nodes are now represented as IDs. All node data is now stored using a new property system which allows users to add custom data to nodes. The new property system is included in Property_map. It initially also replaced the property system used by Surface_mesh and Point_set_3, but as this introduced problems we postpone that.

Release Management

• Affected package(s): Orthtree
• Issue(s) solved (if any): N/A
• Feature/Small Feature (if any): link
• Link to compiled documentation link
• License and copyright ownership: INRIA

TODO

• [ ] Polish the Property system
  • [x] Give Properties.h a more descriptive name
  • [ ] Fix issue with emplace_group on MSVC.
  • [ ] Fix iteration over deleted elements.
  • [x] Delete old property system from Surface_mesh
  • ~~Expand documentation of Property_array, Property_container, etc.~~ These will be left undocumented for now, as we expect the API to change in the future.
  • ~~Consider preferring the use of Property_array_handle and eliminating direct access to Property_array; mixing the two is a potential source of confusion.~~ This doesn't need to be handled until the new property system is documented, but I'd like to come back to this if there's time.
• [ ] Polish the generalized Orthtree
  • [x] Merge Orthtree_traits_point_* classes; only the typedefs are different, so the functionality should be de-duplicated.
    • [x] Use template machinery to choose the appropriate base class based on the dimension tag.
  • [x] Ensure shared corners of adjacent nodes have identical coordinates (Sven's solution should resolve this)
    • [x] This should have a unit test
    • Seems to be working after switching to Iso_cubioid. I might just need to find the right numerical edge case though.
  • [x] Remove enlarge_ratio feature
    • ~~Call bbox.dilate(1) instead; this behavior is more appropriate in almost all cases.~~ This does not seem to be necessary now that Iso_cuboid is used.
    • [ ] Add an example that extends a Traits class to provide the enlargement feature using a modified root_node_bbox functor.
  • [x] Replace Array type in Traits.
    • ~~Remove integer offsets. Simple_cartesian_d<int>::Point may work as an alternative, but I'll need generic kernel conversion to integrate it.~~ An array type is still used internally, but never exposed to the user.
  • [x] Replace Bbox with Iso_cuboid
  • [x] Change the new Traits methods to use the functor object pattern. (Is there a page I can link to in my documentation that explains why this pattern is necessary?)
    • [x] Document functor objects ~~(may require some template magic, along with the macros for unspecified_type)~~ Functor objects only need to be documented in the concept itself, because the explanation will appear in model documentation too.
  • [x] Nearest neighbors functionality only makes sense for some traits, and only has examples which work with point sets. It should become an external function. This may also let us remove element access from the traits class.
  • [x] Comb through documentation to make sure everything matches the new interface.
    • [x] Update user manual text
    • [x] Some features have been moved to Traits, their explanations should be moved.
    • [x] Orthtree documentation should not specifically mention points or point sets, now that it has been generalized.
  • [x] Update list of models for orthtree traits
  • [x] Expand and clarify root_node_contents_object() documentation.
  • [x] Replace all remaining instances of typedef with using for consistency.
    • [x] Does using Dimension = unspecified_type; break doxygen? If not, Concepts should also use using.
  • [ ] Run benchmarks to measure performance change vs original Orthtree implementation.
    • [ ] Benchmark results should be mentioned in the history section.
    • [ ] Benchmark plots must be re-created for the manual.
  • [ ] Implement unsplit(n). This features isn't actually used anywhere now, but it could be useful in the future.
  • [x] The new orthtree requires boost::span; the boost requirement will either need to be bumped to 1.78, or a span can be added to Stl_extension.
• [x] Adapt Efficient_RANSAC package to account for the new interface
• [x] Adapt Polyhedron package to account for non-nullable property handles
• [x] Double check license headers in all newly added files. Dates may need to be updated in some other files.
• [x] Fix bbox computation (doc box overlaps?)
• [ ] Update changes.md
• [ ] Check branch size(todo for @sloriot)

[sloriot]

/build:v0

[github-actions[bot]]

There was an error while building the doc:

<unknown>:1: warning: unable to resolve reference to 'CGAL::Orthtree::Node' for \ref command
/home/runner/work/cgal/cgal/Orthtree/doc/Orthtree/Concepts/CollectionPartitioningOrthtreeTraits.h:15: warning: Found unknown command '\cgalHasModel'
/home/runner/work/cgal/cgal/Orthtree/doc/Orthtree/Concepts/OrthtreeTraits.h:9: warning: Found unknown command '\cgalHasModel'
/home/runner/work/cgal/cgal/Orthtree/doc/Orthtree/Concepts/OrthtreeTraits.h:10: warning: Found unknown command '\cgalHasModel'
<unknown>:1: warning: unable to resolve reference to 'CGAL::Orthtree::Node' for \ref command
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:85: warning: Member Node_data (typedef) of class CGAL::Orthtree is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:114: warning: Member Node_property_container (typedef) of class CGAL::Orthtree is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:145: warning: Member Node_index_range (typedef) of class CGAL::Orthtree is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:182: warning: argument 'point_range' of command @param is not found in the argument list of CGAL::Orthtree< Traits_ >::Orthtree(Traits traits)
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:182: warning: argument 'point_map' of command @param is not found in the argument list of CGAL::Orthtree< Traits_ >::Orthtree(Traits traits)
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:182: warning: argument 'enlarge_ratio' of command @param is not found in the argument list of CGAL::Orthtree< Traits_ >::Orthtree(Traits traits)
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:949: warning: The following parameter of CGAL::Orthtree::adjacent_node(Node_index n, Local_coordinates direction) const is not documented:
  parameter 'n'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:31: warning: Found unknown command '\cgalModels'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:42: warning: Member Dimension (typedef) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:43: warning: Member FT (typedef) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:44: warning: Member Point_d (typedef) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:45: warning: Member Bbox_d (typedef) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:46: warning: Member Sphere_d (typedef) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:47: warning: Member Cartesian_const_iterator_d (typedef) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_2_base.h:91: warning: Member construct_point_d_object() const (function) of struct CGAL::Orthtree_traits_2_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:31: warning: Found unknown command '\cgalModels'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:42: warning: Member GeomTraits (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:43: warning: Member Dimension (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:44: warning: Member FT (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:45: warning: Member Point_d (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:46: warning: Member Bbox_d (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:47: warning: Member Sphere_d (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:48: warning: Member Cartesian_const_iterator_d (typedef) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_3_base.h:110: warning: Member construct_point_d_object() const (function) of struct CGAL::Orthtree_traits_3_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:31: warning: Found unknown command '\cgalModels'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:42: warning: Member Dimension (typedef) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:43: warning: Member FT (typedef) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:44: warning: Member Point_d (typedef) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:45: warning: Member Bbox_d (typedef) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:46: warning: Member Sphere_d (typedef) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:47: warning: Member Cartesian_const_iterator_d (typedef) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_d_base.h:67: warning: Member construct_point_d_object() const (function) of struct CGAL::Orthtree_traits_d_base is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:70: warning: Found unknown command '\cgalModels'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:91: warning: Member Self (typedef) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:92: warning: Member Tree (typedef) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:94: warning: Member Node_data (typedef) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:95: warning: Member Node_data_element (typedef) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:107: warning: Member construct_root_node_bbox_object() const (function) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:139: warning: Member construct_root_node_contents_object() const (function) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:145: warning: Member distribute_node_contents_object() const (function) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h:152: warning: Member get_geometric_object_for_element_object() const (function) of struct CGAL::Orthtree_traits_point is not documented.
/home/runner/work/cgal/cgal/Orthtree/doc/Orthtree/Orthtree.txt:125: warning: unable to resolve reference to 'CGAL::Orthtree::Node' for \ref command
/home/runner/work/cgal/cgal/Orthtree/doc/Orthtree/Orthtree.txt:140: warning: unable to resolve reference to 'CGAL::Orthtree::Node::parent' for \ref command

https://github.com/CGAL/cgal/actions/runs/6182099644

[JacksonCampolattaro]

/build:v1

[github-actions[bot]]

There was an error while building the doc:

<unknown>:1: warning: unable to resolve reference to 'CGAL::Orthtree::Node' for \ref command
<unknown>:1: warning: unable to resolve reference to 'CGAL::Orthtree::Node' for \ref command
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:938: warning: The following parameter of CGAL::Orthtree::adjacent_node(Node_index n, Local_coordinates direction) const is not documented:
  parameter 'n'

https://github.com/CGAL/cgal/actions/runs/6290924322

[JacksonCampolattaro]

/build:v2

[github-actions[bot]]

There was an error while building the doc:

/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:938: warning: The following parameter of CGAL::Orthtree::adjacent_node(Node_index n, Local_coordinates direction) const is not documented:
  parameter 'n'

https://github.com/CGAL/cgal/actions/runs/6295872474

[JacksonCampolattaro]

/build:v3

[github-actions[bot]]

There was an error while building the doc:

/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:1113: warning: argument 'direction' of command @param is not found in the argument list of CGAL::Orthtree< Traits_ >::adjacent_node(Node_index n, Adjacency adjacency) const
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:1113: warning: The following parameter of CGAL::Orthtree::adjacent_node(Node_index n, Adjacency adjacency) const is not documented:
  parameter 'adjacency'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:757: warning: The following parameter of CGAL::Orthtree::child(Node_index n, std::size_t i) const is not documented:
  parameter 'i'
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:1007: warning: argument 'lhsTree' of command @param is not found in the argument list of CGAL::Orthtree< Traits_ >::is_topology_equal(const Self &lhs, const Self &rhs)
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:1007: warning: argument 'rhsTree' of command @param is not found in the argument list of CGAL::Orthtree< Traits_ >::is_topology_equal(const Self &lhs, const Self &rhs)
/home/runner/work/cgal/cgal/Orthtree/include/CGAL/Orthtree.h:1007: warning: The following parameters of CGAL::Orthtree::is_topology_equal(const Self &lhs, const Self &rhs) are not documented:
  parameter 'lhs'
  parameter 'rhs'

https://github.com/CGAL/cgal/actions/runs/6331060358

[soesau]

There seems to be a bug in Surface Mesh due to the new properties. When I delete an edge, the halfedges of that edge are not marked as deleted.

And it seems that deleted elements still appear in the iterators, i.e., halfedges_begin()/faces_begin()/...

[JacksonCampolattaro]

There seems to be a bug in Surface Mesh due to the new properties. When I delete an edge, the halfedges of that edge are not marked as deleted.

And it seems that deleted elements still appear in the iterators, i.e., halfedges_begin()/faces_begin()/...

Hmm, I can take a look in the next couple of days, is there an existing unit test which catches this?

The halfedges should only require some special handling code in the surface mesh class, but the iteration issue is with the property system as a whole. I can fix that by adding a special iterator type which skips elements marked as empty in the bit vector.

[afabri]

This should be an example. Only one point should be written as output.

[JacksonCampolattaro]

The old version had a baroque system of memory management which ensured edges & faces were placed contiguously. This came at the cost of additional indirection when accessing the neighbors of an edge, because it needed to maintain a table of indices which was re-mapped when they were moved around in memory. The new property system provides its own memory management which keeps indices stable for theoretically better performance, at the cost of allowing gaps after deletion. The best short term solution for retaining the same behavior might be to revert the Surface_mesh package to do memory management the old way, but still use the new property system. The built-in memory management of the new property system adds minimal overhead, and when that feature is ignored the interface is similar to the old property system.

In the long term, I don't think this is a good solution. Eventually I think it would be worth doing one of the following:

• Add an iterator which skips empty indices in the property array. This loses random-access iterator semantics, but maintains performance for most important tasks.
• Keep the existing behavior, including deleted points in the iterator. This preserves random-access semantics (begin() + edge_index behaves as expected ), but makes forward iteration confusing if points have been deleted. I don't think this is a good solution.
• Condense the property arrays after each deletion, updating indices to account for the offsets. This could be the responsibility of the garbage collection function. This may be an expensive operation, but it's a cost that can be moved around.
  • For example, we could condense the arrays before returning iterators, or we could add a precondition that has_garbage() == false before the user iterates over properties.
• Different users of the property container system don't have the exact same needs. We could add property containers which perform memory management in different ways while providing the same interface. Property_container would then be a concept, implemented by versions which do no memory management, gap-list memory management, contiguous memory management, etc. This was my original hope for the property container system, but for the purposes of this PR I only created the simplest version.

In any case, these probably belong in their own PR. Re-working the entire property system as part of the orthtree update was definitely ambitious. By reverting to the old behavior, we can keep the new underlying property system as an implementation detail, and defer these choices until later.

[afabri]

Currently elements get deleted they are marked as deleted only. The deleted elements are "linked" to form a free-list, so that when adding elements instead of adding them at the end of the storage we first reuse slots from the free-list. Is that what you call "baroque" (I do not feel offended, only want o understand what you try to replace).

[JacksonCampolattaro]

Currently elements get deleted they are marked as deleted only. The deleted elements are "linked" to form a free-list, so that when adding elements instead of adding them at the end of the storage we first reuse slots from the free-list. Is that what you call "baroque" (I do not feel offended, only want o understand what you try to replace).

Sorry, I didn't mean baroque in a negative way. I must have misunderstood the old system or gotten it mixed up with another package, because it looks like Index_iterator already does what I suggest in my first bullet point. In that case the change in behavior is actually a bug (I'm still using Index_iterator, but something isn't working as expected). The only functional difference between the two is then replacing the linked free-list with an std::vector<bool> active-list provided by the property container. I suspect the vector system performs similarly, because while std::find_first_of is technically O(n), it should be extremely fast on the packed bit representation of vector<bool>, and it has nicer access patterns than traversing a linked list. The old system is almost certainly faster in situations where N is extremely large and you only need to allocate 1 element at a time instead of searching for a large-enough block.

[JacksonCampolattaro]

Switching back to the old implementation is probably the best course of action for now. The main purpose of the changes to Surface_mesh was to figure out the interface the new property container system should provide. Eventually there should be a property container implementation which does swap-with-last deletion for packages which don't require stable indices (like Point_set_3) and another which manages a free-list like Surface_mesh. That way more packages can have user-added properties in the future without the need to implement custom iterators and memory management.

When I came to the conference we decided to create the new property system in part because of licensing issues with the existing one. We started with vector<bool> garbage management because it's simple to implement.

[afabri]

Will the new orthtree work with the old property mechanism? I would expect that.

[JacksonCampolattaro]

I think it would work fine, aside from the licensing issues, which I think @sloriot knows more about.

The new property system also adds some features useful for an efficient implementation of the Orthtree (like an emplace_group method) and some quality-of-life changes like returning boost::optionals where appropriate instead of property maps in an invalid "null" state. These differences could all be worked around if necessary, it would just take some time.

[afabri]

@JacksonCampolattaro can you check that your new employer agrees that what you contribute to this PR from now on is under the copyright of Inria (@palliez).

[JacksonCampolattaro]

I was a little bit concerned about TU Delft's ancillary activities requirements initially, so I've already spoken with my advisor. Because this work isn't paid and I'm doing it on my own time, I don't need to report it officially and there shouldn't be any licensing issues.

[afabri]

I would be glad to discuss the changes made in Surface_mesh, but it is annoying that there are also distracting changes of indentation.

[JacksonCampolattaro]

Sorry about that, I'm testing out a roll back to the previous memory management scheme, but I'm running into the same issue.

[afabri]

Sorry about that, I'm testing out a roll back to the previous memory management scheme, but I'm running into the same issue.

Hello, I would be glad to join the today's orthtree meeting to understand things better and work on Surface_mesh myself.

[JacksonCampolattaro]

That sounds like a good idea. We typically meet at 13:15, perhaps you can join the call in Element.

[soesau]

/build:v0

[soesau]

/build:v0

[github-actions[bot]]

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/7672/v0/Manual/index.html

[soesau]

/build:v0

[github-actions[bot]]

There was an error while building the doc:

This round already exists. Overwrite it with /force-build.

https://github.com/CGAL/cgal/actions/runs/7505752662

[afabri]

/forcebuild:v0

[afabri]

/force-build:v0