Find whether a triangle and polyhedron (represented by planes) intersect

2
votes

I am given a polyhedron which is represented by a list of planes. The volume delimited by these planes is the actual polyhedron.

I have a list of triangles, and I need to remove all the triangles that intersect or is contained in this polyhedron. My idea is to check each plane for an intersection with the triangle. If it does intersect the triangle, then check if the line segment representing the intersection contains a point that lies on the same side of all other planes.

To catch the case where the triangle is fully contained, we can just check if any of the triangle's corners is contained in the polyhedron (by checking that the point lies on the same side of all planes).

I'm not sure if this solution even works for all cases however, or if there is a more elegant solution. I'm also not sure how I can figure out if the line segment of an intersection contains a point on the same side of all the other planes.

I have thought about the separating axis theorem too, but that would require me to convert the polyhedron into some different representation (since the planes are infinite), and I'm not sure how to do that.

Any help would be appreciated!

1
mathgraphicsgeometrygame-physicsintersection
You could sucessively clip the triangle at each plane. If the triangle vanishes completely, there is no intersection. – Nico Schertler
Your solution is close to the one I cam up with, so I think it is a go. – Michael Dorgan
@NicoSchertler What do you mean with clip? Trying to cut off all portions of the triangles that are on one side of each of polyhedron's planes? – jakobbotsch
Yes, exactly. Clipping is a basic process in graphics (triangles are usually clipped at the screen's edges). You can do that either in 3D or intersect the planes with the triangle plane and clip in 2D. – Nico Schertler
Thanks @NicoSchertler, I ended up using your approach. Clipping the triangles to planes is very easy (we can simply treat each triangle edge as a line segment, and that makes the clipping really straightforward). It seems to work, thanks! – jakobbotsch

1 Answers

0
votes

As @NicoSchertler suggested in a comment, a solution is to take each triangle and clip it on all the planes. If there are no points left (or under 3 points, so it is not a triangle), the triangle intersects the polyhedron. This seems to work well.