6

I have a collection of non-self-overlapping simple polygons P. In actuality, they are 2D triangles in 3D-space.

I'm looking for a data structure which, given a line L, has a relatively fast lookup for all polygons p in P which L intersects with. If it can give me the intersection point, that is a bonus, but I can calculate this myself if I just get the polygons, in any case.

I've used kd-trees and red-black-trees before, but as those deal with points, I am hoping that there is a data structure better suited to my problem. I'm expecting it to be some sort of BSP-tree, but am open to other suggestions.

elsurudo
  • 161
  • 4

2 Answers2

2

You could try to utilize an octree for this. This won't give you exactly the polygon set you are looking for, but a superset which may be significantly smaller than the whole set of polygons (of course, how well this works depends on the polygons and how they are distributed in space).

Pick a certain "maximum depth" for the tree which is appropriate for your problem scale. Associate with each "leaf" cube the polygons whose bounding box touches that cube. When looking for the polygons, determine the leaf cubes which are touched by the line and take only the associated polygons into account.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
1

If your scene is static (i.e., your triangles don't move, so you can amortize building your acceleration datastructure across all your lines), then I believe that a highly optimized kd-tree is still state of the art for this purpose. Because they have finite extent, your triangles may overlap more than one branch of the kd-tree tree; however, that will be true of any BSP-type acceleration structure.

An alternative class of acceleration structure is exemplified by the R-tree. Like the kd-tree, R-tree nodes have axis-aligned bounding boxes; however, in an R-tree, sibling nodes' bounding boxes may overlap.

In a generalized sense, most known acceleration structures are either R-tree-like or BSP-like.

comingstorm
  • 2,727
  • 1
  • 13
  • 14