CODEWITHSUNDEEP
algorithmmath3dlanguage-agnosticraytracing
MaiaVictor
MaiaVictor

Reputation: 52957

Is there any fast ray→surface intersection algorithm?

Triangles are surfaces with a very simple ray→triangle intersection algorithm which can be done with a few operations. They are often used as primitives for ray-tracing applications for this reason - a mesh is, for example, approximated by a collection of triangles. The problem is, the more detailed the approximation, the more triangles you need, which means more tests. If your object is a perfect sphere, then using triangles might not be a good idea, since there is an O(1) algorithm that can test directly for ray→sphere intersections with few operations.

My question is: what other surfaces have that property of "having a faster ray→surface" intersection than the triangularization approach? Is there any mathematical structure/object that allows us to approximate the surface of an arbitrary 3D object and check for its intersection in O(1)?

Upvotes: 2

Views: 1181

Answers (1)

Fabrice NEYRET
Fabrice NEYRET

Reputation: 734

What knowledge do you have on your shape ? - pure close form : some have close solutions. - if it's just a triangle soup, you need some data structure for accelerate: e.g. grids, octrees, bounding box hierarchy, BSP... - if you can express a potential or distance function - even approximate - such as implicit surface, you can use dichotomy to get the intersection (iterations are quite fast).

( Or you can join the SparseVoxels community, but this is another story ;-) ).

Upvotes: 2

Related Questions