Intersection test with kd-tree

Question

My current understanding of a kd-tree is; that on every node we split our points into two equally big groups for one axis.

We iterate through the individual axis until the tree is saturated.

This kind of data-structure is, of course, is interesting for raytracing applications because we don't have to search through every triangle face to test our intersection with the ray, we simply know where it would be likely that a triangle would intersect with our ray.

---

I have some question on how this is done.

How do we handle weird triangles where we cannot make easy splits(triangles intersecting other triangles or triangles which span the entire?

Do we even split on the triangles or do we split on the vertices?

How exactly do we test for an intersection of a ray that we send out from the camera ?

I see a couple of methods. First, we could build bounding boxes from our scene and the splitting planes and test for intersection with those boxes or we could test for intersection with the splitting planes and see where the intersection is relative to the camera

Answer 1

The short answer is: This all depends on your application. There are several variations of kd-trees.

How do we handle weird triangles where we cannot make easy splits?

I believe you are referring to the choice of the splitting plane for a given set of triangles. This is a pretty hard optimization problem, which is usually solved with a heuristic. E.g., you could sort the centroids of triangles along one axis and choose the median as the splitting plane. Nothing is stopping you from implementing some more intelligent criterion.

If you find that your splitting plane passes through a primitive, you have two options. Either split the primitive or add it to both subtrees. What you should do depends on your application.

Do we even split on the triangles or do we split on the vertices?

That depends on the primitives you want to add to your tree. If you want to use the tree for raycasting, then it makes sense to have the triangles in the tree. kd-trees are a very general concept that works with any kind of primitives, though. E.g., they are also widely used for point clouds.

How exactly do we test for an intersection of a ray that we send out from the camera?

You do this by traversing the tree. So, you start at the root node and check if the ray intersects with the associated bounding box (which is the entire space). Then you check which of the two subtrees are first intersected by the ray and continue to this one. And then you repeat: You test for intersection with the node's AABB (which you build incrementally from the splitting planes). If the ray does not intersect the AABB, then immediately return back to the parent node. If it does, continue to the first child. When you come back from the first child, go to the second child (unless you already found an intersection).

For some more details, I would advice to take a look at application-specific instances of kd-trees.