[Algorithms] Raycasting - how fast does it get?

[Alen L. <ale...@cr...>]

Hi all,

To ask it straight off... What would be the fastest way to check a ray
against a polygon soup? The mesh is static, so any kind of
precalculation could be ok (as long as the memory requirement is not
ridiculous). The only required result is distance of nearest hit (or
+inf if it's a miss) - don't even need to know which polygon was hit.

I am under the impression that a plain bsp structure (without storing
polygons neither in the leafs nor in the splits) and just checking if
the ray ever got into a solid node, would be the fastest. Though it
requires that the object be a 2-manifold, thus it is not useable for
the general case of a polygon soup. (*)

Other contenders that come to mind:
1) loose octree
2) plain octree (every polygon in up to 8 nodes)
3) a kd-tree
4) a bsp, but having polygons in leaf nodes and testing the polygons
individually, instead of just searching for a solid node (this one
should work even with a general polygon soup).

Does anything else come to mind? Any pointers on which of those would
be the fastest?

Thanks,
Alen

(*) Extra note on bsp trees... I was thinking since the data we have
generally does resemble somewhat closed meshes in most parts, we might
come up with a way to close them up and tidy into a 2-manifold, either
automatically or by hand. But we still need to support thin flat
objects (represented by two opposite-facing polygons, or by a
double-sided one, depending on what's suitable for the
representation). It might be possible to use bsp for the regular part
of the mesh and them keep another rep for the special cases in
parallel, but perhaps a good general method might be better.