# 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. 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.

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. left, left) AND
follow+ both trees in the second direction (e.g right, right)
if both new nodes are leaf nodes, connect them

* all O(n) inner tree nodes.
+ When you arrive at a leaf node, store it and continue traversing the other subtree as before.

This way you stick to the splitting plane and traverse it always in the same directions for both subtrees, without taking the actual coordinates into account to find boxes to connect. These edges result in the quads and triangles in the example above.

Even the second from left quad at the bottom can be split into two triangles, with regard to adjacency, its edge intersection is just very short and thus harder to see than the other intersections.

(Finding these triangles is only one application, on the other hand it could be quite useful to identify what connections could create a quad and still produce a useful mesh. The mesh in the example may be good for some applications and bad for others)

## Are there techniques for more efficient and more general queries?

The combinatoric approach does not guarantee that the neighbors actually share a non-zero edge intersection and as you see in the example, the edges connecting their centers (or other points inside the cells) may cross other boxes in the tree, what cannot be detected by this algorithm.

In addition, the algorithm starts at $$n$$ splitting planes and traverses the full subtrees in time $$n log n$$, what seems rather inefficient.

I am now looking for techniques for faster queries to find neighbors of cells, edges, and vertices. I would for example like to start at an edge of a box in the tree and find all neighbor faces (and thus neighbor boxes). This would not only involve faces that are adjacent to the edge, but also neighbors of the parent cell and more complex neighborhoods that may occur in a kd-tree.

## Papers I found so far

Rope trees, that construct additional links inside the tree for more efficient ray intersections:

Havran, V., Bittner, J., & Zára, J. (1998, April). Ray tracing with rope trees. In 14th Spring Conference on Computer Graphics (pp. 130-140). (PDF)

Using nested kd-trees allows for some of the queries:

Greß, A., & Klein, R. (2004). Efficient representation and extraction of 2-manifold isosurfaces using kd-trees. Graphical Models, 66(6), 370-397. (Website)

• Out of curiosity, what dimensions are you most interested in having this data structure represent? Lower dimensional ones like $k \leq 3$? I can think of a way to construct this, though I have never seen this variation of a kd-tree before. Aug 27 '19 at 4:10
• I only need 3D and possibly additional 2D trees on the faces of the 3D cells. 2D looks a bit easier, but maybe it is only easier to think about it. I suppose, that $k\ge 4$ will generalize the same scheme like an algorithm in 3 dimensions, once you know how to handle, e.g., the face overlaps in multiple dimensions. I think the 2D case may allow for some shortcuts, that do not generalize to higher dimensions.
– allo
Aug 27 '19 at 8:25
• Are you able to share the application? Though the question is interesting as is, it may be that there are other approaches to the underlying problem. Aug 29 '19 at 17:22
• I am working on a triangulation code based on the paper from Greß and Klein 2004. They describe a interesting technique based on nested kd-trees, but the description of the actual traversal (sec. 3.3) is rather short. While working on it, I looked for some more general literature, because I am interested in the ideas how to do the neccessary neighborhood queries in a more general setting.
– allo
Aug 30 '19 at 18:29
• Just want to say, that I am following your progress and very interested in this problem myself. Unfortunately, nothing to contribute from my side, as of right now. Aug 30 '19 at 18:39