Are there well-known methods for navigating on kd-trees?
When you have a mesh, there are many well-known methods to navigate it, as for example using a half-edge data structure, that allows easy circulation around faces and vertices. Are there similar structures/algorithms for kd-trees, that allow you to easily find adjacent and overlapping (half)faces?
I am mostly interested in circulating around an edge to find all adajacent (half)faces and cells, what seems to get rather complicated especially on imbalanced kd-trees. In addition, identifying overlapping halffaces which neighbor faces are overlapping the same opposite halfface would be useful.
I wonder if there are some standard algorithms. It is hard to search for them, because every book and every internet search result is full of standard algorithms for searching nearest neighbors in euclidean space using a kd-tree, without mentioning how to navigate in the kd-tree mesh or graph for queries with respect to the tree itself.
Something that works analogous to a halfedge structure would be really nice, but I suppose most algorithms will rather traverse the tree.
If there are no specific algorithms, I would really like suggestions how to work with a collection of cuboids, i.e. the geometric representation of the kd-tree bounding boxes, for querying adjacency, overlaps and similar geometric properties.
Halfedges
For reference short introduction to halfedge structures on meshes. A halfedge structure looks like this:
(Image taken from the CGAL manual)
It makes all important queries really easy:
* Circulate around a face: Follow the next pointer until you're back at the start edge.
* Find a neighbor face: Follow the opposite pointer to the halfedge of the other face.
* Find the edges around a vertex: Follow the next pointer, then the opposite pointer to find the next incident edge.
The structure has many more useful properties, like allowing to follow the boundary of a mesh using the next points of boundary edges and circulating around holes, in the same way as circulating inside a face.
KD-Trees
These operations are only well defined on polygonal meshes. A kd-tree looks like this:
(Picture taken from the Wikipedia article on kd-trees)
The tree is build by subdividing an initial box. You start in one dimension and when you subdivide a box, you always use the next dimension (e.g. 180
x, y, x, y for 2D or x, y, z, x, y, z for 3D). There are several ways to choose the splitting plane, depending on your actual application.
Such a tree is no mesh, as it has T-junctions by design. If you try to build a halfedge structure in this example tree, you have edges, that have multiple opposite edges, as you see in the rightmost column of the tree.
In addition, such a tree has overlapping (half)edges like the blue edge on the left side of the example tree. When you try to split it into half edges, you get four halfedges, each adjacent to two opposite edges.
Adjacency in a KD-Tree
If you want to use such a tree for example to create a mesh of the points contained in the tree, you need adjacency information between the boxes.
Here is an example in which I used a kd-tree to create a mixed quad/triangle mesh using a kd-tree that separates the vertices:
(Note that not all boxes with overlapping edges are connected, see below for more on how this graph is created)
Neighbors sharing an edge are neighbors in the corresponding graph as well (and the construction guarantees that it is the same edge). But boxes that do not share the same parent node, may be adjacent to each other. In the upper left you see a triangle, that corresponds to the subtree:
|\ A |\ B C
in which the neighboring leaf nodes are connected with the neighbor cell of their parent cell. This is still a rather easy query and the intersections are uncomplicated as well. There are no overlapping edges and an edge has either one or two non-overlapping opposite edges.
But you also see many triangle and quads, that connected boxes that are far apart from each other in the tree with no obvious way to find the needed adjacency information.
Finding neighbors in the tree
I created this graph using the following algorithm:
``` start at all* splits: traverse the two subtrees in parallel as follows: if the dimension is the same as the split: follow+ the subtrees in the split direction in both trees (e.g. right, left) else: follow+ both trees in the first direction (e.g. 953