Octree node splitting from a prescribed list of nodes.

[tdinar]

Hi,
I am trying to split leaf nodes that are stored by means of pointers in a list . When iterating over the list, while splitting each node, I get a violation of is_leaf() precondition, which should not occur in my list. It seems as if the tree is changing within the loop making some of the pointers not valid. Please have a look at the code below and advice if you may.

while (iter != tree_nodes.end() ){
   Quadtree::Node node = *iter;
   if (node.is_leaf()){
     list_nodes.push_back(&node); 
   }
   iter++;
 }
 std::vector<Quadtree::Node*>::iterator index = list_nodes.begin();
 while (index != list_nodes.end() ){
   Quadtree::Node* p = *index;
   Quadtree::Node node = *p;
   CGAL::Orthtrees::Node_access::split(node);
   index++;
 }

[JacksonCampolattaro]

Hi @tdinar,

The current Orthtree API has some flaws, one of which is that Node_access::split(node) doesn't actually distribute the points between child nodes. This functionality was made public for unit testing. It shouldn't be causing precondition violations, but it can produce incorrect results.

Another issue which might be causing your problem is that nodes contain a manually allocated pointer to their data, so the "Node" type is actually only a thin handle. It might be worth trying node.is_null() before you add each node to list_nodes, to see at which point they become invalid.

I'm working to make the Orthtree API a little more ergonomic in a new branch, but it may be some time before the fixes appear in packaged versions of CGAL. As a temporary solution, a workaround could be to implement a custom Split_predicate. In your case, it looks like the goal is to split every leaf node of a previously refined tree, so your split predicate could build on the functionality of another. The condition might look something like this:

n.is_root() || Other_split_predicate(n.parent())

[tdinar]

@JacksonCampolattaro
hi Jackson,

Thank you for your thorough explanation and suggestion of a workaround.

I have been working on splitting leaves that satisfy a geometric constraint based on their bounding box.

I confirm that Node_access::split(node) produces children that have erroneous bounding boxes when constructed. Not feasible to bounding boxes are used further.

When using a refinement predicate with the condition:

   ` n.depth() < max_depth && geomtric_constraint(bbox)`

I am faced with these two issues:

 1. The refinement stops as soon as the geometric constraint is violated, even if at the root node. 
     The refinement does not proceed into children of nodes violating the predicate.

 2. I had to pass the nodes' bbox data to the predicate with the aid of std::vector. 
      Not a deal breaker but it would be very helpful if a node constructs its bounding box.

I wish you luck with your work on the new branch,

I can lend a hand if deemed beneficial.

[JacksonCampolattaro]

I'm glad I could help! As for the two issues:

1. I might need some clarification to answer this properly. The refinement process only splits a node when the split predicate returns true, so in your example a node for which geometric_constraint() returns false won't have children at all. Maybe n.depth() < max_depth || geometric_constraint(bbox) will produce the behavior you're looking for?
2. This is a request we've also gotten from other users; the challenge is that storing an entire bounding box for each node is wasteful: the bbox will always be cubic for an Octree, and the side length and center position can be determined based on its coordinates within the tree. For your case, it might make sense to include the orthtree itself as context in your split predicate. That would allow you to call orthtree.bbox(*node) inside the predicate and produce the bounding box on the spot. Finding the bbox is cheap, and this should save some memory (and bookkeeping effort!) vs the std::vector.

[tdinar]

Thank you for you help.

1-Think of it as in a game, when you touch an area, a circular domain is chosen. Any node within the domain satisfies the geometric constraint "and" if any of these nodes satisfy the depth criteria then it will be refined. I want to repeat on ancestors of said node(s) until the maximum depth is reached. All other nodes outside the domain would not change. So I think I need the && to satisfy both the geometric constraint and the maximum depth.

2-This makes sense, so I will try it this way.

[JacksonCampolattaro]

If I'm understanding correctly, any node which is fully contained by a circular region should be subdivided, and so should any children of that node which are contained by the circle, repeating until max depth? In that case, you might also want to use a minimum depth, since your root node is probably not fully contained by the circular domain (this might be the source of your first issue). That condition would look something like this:

n.depth() < min_depth || (n.depth() < max_depth && geometric_constraint(bbox))

This should split the Quadtree into $4^{\textrm{min-depth}}$ equal squares, and then those will be further subdivided if they're within the circle.

[tdinar]

Hi @JacksonCampolattaro

Thank you for your help.

The conditional you have provided works correctly.

I am pushing through to verify my code and results.

Best.

[JacksonCampolattaro]

I'm glad it worked! Don't hesitate to message if you run into other issues with the Orthtree; real user input is helpful for the refactor.

Kind regards.

[tdinar]

Hi, @JacksonCampolattaro
keeping the min_depth at some number, and with increasing max_depth,
the predicate fails at some point with the error shown below.

CGAL error: precondition violation!

Expression : comp_f(object, nodeP->object) != LARGER

File       : /usr/local/include/CGAL/Multiset.h

Line       : 2183

Explanation: 

Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html

unknown file: Failure

C++ exception with description "CGAL ERROR: precondition violation!

Expr: comp_f(object, nodeP->object) != LARGER

File: /usr/local/include/CGAL/Multiset.h

Line: 2183" thrown in the test body.

Do you have an idea what could be the cause and how to resolve the issue? I tried to find out with no success.

Thanks.

[JacksonCampolattaro]

Hmm, that is odd. I'm not familiar with CGAL's Multiset implementation, and as far as I know it isn't used by the Orthtree. Are you able to use a debugger to find out under what conditions this occurs? A stack trace might also be useful, to confirm the precondition violation is happening inside refine().

[sloriot]

CGAL's Multiset is a red-black tree. It might be that the ordering that you are not consistent. That would explain the assertions.

[tdinar]

The screenshot below shows a case with a min_depth of 2 and a max_depth of 6. Note that all nodes satisfying the geometric constraint are not plotted.

At max_depth of 7 the algorithm produces the error shown above.

[tdinar]

Hi, I am suspecting the ordering is the reason for the error. I keep on checking. Thanks.

…

On Fri, Apr 7, 2023 at 10:09 AM Sebastien Loriot ***@***.***> wrote: CGAL's Multiset is a red-black tree. It might be that the ordering that you are not consistent. That would explain the assertions. — Reply to this email directly, view it on GitHub <#7350 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADIED6KYUSB2ABBTVLJA3W3W77DTVANCNFSM6AAAAAAWHG27HU> . You are receiving this because you were mentioned.Message ID: ***@***.***>