Alternating Digital Tree

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

Alternating Digital Tree

In need a data structure which is capable of performing intersection detection of geometries with different topologies. For example, consider a hybrid mesh composed of non-overlapping mesh elements (quadrilaterals and triangles). Algorithm should find which quad or triangle a query point resides in. In general geometries compared against are (point, segment) vs (triangle, quad) and segment vs segment. Note that mesh topology is static so it is good to store mesh elements in the tree. Actually the name of the data structure is Alternating Digital Tree ( ADT is similar to kd-tree but also assigns a mesh element to each node and also stores element's AABB at the same node. This makes it capable of point containment query.

Intersecting Sequences of dD Iso-oriented Boxes performs intersection detection of boxes which store handles to actual geometries. In this case, I would need to create a box for each geometry (even for points). Also, in my case the mesh topology is static so desired data structure should store mesh elements. I am not sure if box_intersection_d stores static data structure or constructs hierarchy at each call.

kd-tree and range tree are very similar to ADT but they offer only neighbor and range search but not intersection detection.

Segment tree and Interval skip list offer point containment search only for segments/intervals.

AABB tree (3D Fast Intersection and Distance Computation) support intersection queries include line objects (rays, lines, segments) against sets of triangles, or plane objects (planes, triangles) against sets of segments. So no triangle vs triangle or point vs triangle.

Is there a data structure suitable for ADT in CGAL?