Not sure what key words to use for searching this on Google, so I have to just describe it.

I have an array of planes (described by 3 points each which are always going to be points that lie on the intersections of 3 planes that form the object) that describe a convex polyhedron.

My goal is to make a triangle mesh to graphically display the polyhedron described by the planes.
Here are some things I already know how to do (don’t worry, what I am asking is not as complex as it sounds, as I can do 90% (I estimate) already).
#1: I already have robust routines for intersecting 3 planes to find a point, if one exists.
#2: I already have a polygon class which will end up describing the faces of the polyhedron, and this class has ear-clipping already functional so that I can break it down into a triangle mesh. All I need is to get the faces of the the polyhedron into this polygon format, and this is my only question.
#3: The points are counter-clockwise and I already have a plane class that accepts 3 points and transforms them into a more suitable plane representation (distance + normal) which I use in all the rest of my plane math.
#4: I mentioned intersecting 3 planes for a point, but I can also intersect 2 planes for a line.


So I have all the tools I need to handle this process. All I need is a concept on a robust way to break all these planes down into polygons that represent each face of the original object.
For all the ideas I have been make on my own, I keep finding pathological cases that break my idea. I need something robust, tried, and true, because this is a very important feature of my tool chain for my engine.

I also would not mind some tips on things to avoid in the name of robustness. I plan on working with doubles (or possibly 2,048-bit fixed-point integer form) for most of the math and have proper (if somewhat expensive) epsilon checks in place, etc., but I want to be sure I am taking every precaution possible because I have seen professional toolchains that have tried to load and convert the very same files I am now trying to do and fail to properly realize that some very narrow slab-type polynomials are in fact valid and other cases where it converts the level but then you see slab-type triangles missing and in some cases you can fall through the level there.
So I am really hoping not to fall into those kinds of traps, so robustness is extremely important.


Thank you,
L. Spiro

So here is the most robust way I imagined on my own.

I am guaranteed that all 3 points describing the face of the polyhedron are points on that face’s outer rim. I am not, however, guaranteed that they are contiguous points on the outer rim.


So I can only start with one point.

Starting with that point I check for a second plane that intersects that point, creating a line through it.
Then I continue searching for a 3rd plane that intersects along that line.
I search for 2 points that can result in the chopping of that line into a line-segment, and my goal is the shortest line segment possible.
I know on which side of the line segment to place each point by the normals of the 3rd plane. If they point in the same direction as the line (segment) they go to the end, otherwise to the start.

For each side, the point closest to the opposite side is kept.

If I did not already have a guarantee that the starting point I was using was on the outer rim, I could discard the line segment if it becomes negative in size and move on to the next 2nd plane. This would make the algorithm entirely generalized (no assumptions that you are starting on a point guaranteed to be one of the points that make up the face).

In either case I still have to move on to each 2nd plane that intersects the current face and simply repeat the process from there.

When the line segments of a face are gathered I can eliminate 0-sized segments and combining them with the proper winding is trivial (they will already be in the proper winding order), and I have my polygon for that face.
Move on until finished, clip some ears, and I have my triangulated mesh representing the polyhedron.


How does that sound?
I really couldn’t find any reading material on how to do this so I would expect more robust algorithms are out there. I know my idea will work but…


L. Spiro

There is a lot of information in those links. Quite a complicated algorithm.

That seems to be the keyword I need, but the second link provides little information as to the advantages of the algorithm.
Is it faster? More robust? I can’t tell if I should switch.


L. Spiro