CODEWITHSUNDEEP
geometrycomplexity-theoryintersect
fish
fish

Reputation: 11

How to find the cubes passed through by a triangle

Given a triangle with vertice A, B and C in 3D world and a axis-aligned bounding cuboid with length*width*height=nd*md*ld(n, m, l are integers and d is float) containing it, partition the cuboid into n*m*l cubes and how to find the cubes passed through by the triangle?

There are many algorithm to detect whether a triangle and a cube intersect. Loop over all cubes the problem can be solved. However, the complexity of this approach is O(n*m*l) or O(n^3). Is there an approach with complexity O(n^2) or even O(nlogn)?

Upvotes: 1

Views: 78

Answers (1)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

You cannot improve upon O(n m l) for the following reason: select m=1 and l=1. Then one has a planar arrangement of n cubes, and your triangle could intersect every one. If you need to report each cube intersected, you would have to report all n cubes.

But clearly this is just a flaw in your problem statement. What you should ask is the situation where n=m=l. So now you have an n x n x n set of cubes, and one triangle can only intersect O(n^2) of them.

In this case, certainly a triangle might intersect Ω(n^2) cubes, so one cannot improve upon quadratic complexity. This rules out O(n log n).

So the question becomes: Is there a subcubic algorithm for identifying the O(n^2) cubes intersected by a triangle? (And one may replace "triangle" with "plane.")

I believe the answer is Yes. One method is to construct an octree representing the cubes. Searches for "voxels" and "octree intersection" may lead you to explicit algorithms.

Upvotes: 1

Related Questions