CODEWITHSUNDEEP
algorithmmath3dspace-partitioning
ET 0.618
ET 0.618

Reputation: 3583

Thousands of rays intersections with Triangles in 3D space

There are thousands of rays and triangles. We need get all the intersection points. If we use the normal two level loops,we need O(mn) time complexity.Is there any way to low the time complexity fronm O(mn) to O(m* logn) or O(logm*n)?

Best Regards,

Upvotes: 3

Views: 504

Answers (6)

PeterN
PeterN

Reputation: 29

Obviously, if you must iterate and compute intersection between a ray and each triangle then the complexity is O(mn). However, if you are interested in only those triangles that may potentially intersect with particular ray, you can try a variant of a space partitioning grid, for example a Hierarchical Quadtree Grid (http://graphics.stanford.edu/courses/cs468-06-fall/Slides/steve.pdf).

Upvotes: 0

comingstorm
comingstorm

Reputation: 26107

The classic solution to this problem is to build a KD tree based on the triangles, and query it for each ray. You can optimize the tree for the kind of queries you expect; if your rays are randomly distributed, the probability of a hit is proportional to the surface area in question.

Even if you aren't actually doing ray tracing, this problem is currently the main performance bottleneck for ray tracing, so you should probably check out the literature on it.

Upvotes: 2

Adam Luchjenbroers
Adam Luchjenbroers

Reputation: 5019

What you probably want to look at is some kind of space partitioning technique. This allows you to quickly rule out collections of triangles.

I'd probably consider some approach using spherical Bounding Volume Hierarchies. But other techniques you may also want to look into are BSP (Binary Space Partitioning) Trees/ KD Trees or using an Octree

Upvotes: 8

Fortega
Fortega

Reputation: 19682

You could group the triangles close to each other in cubes. Then for each ray: if it does not hit the cube, you are sure it does not hit one of the triangles inside the cube, so you can skip all the intersection calculations with those triangles for this specific ray.

Upvotes: 0

Ofri Raviv
Ofri Raviv

Reputation: 24823

No. The reason is simple: there may actually be O(m * n) intersection points. just creating a list of them is O(n * m).

Upvotes: 2

Drakosha
Drakosha

Reputation: 12165

In 2D there's SweepLine algorithm. It looks to me like it can be generalized for 3D.

Upvotes: 0

Related Questions