# Triangulation of non-planar faces

This topic is 4229 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Okay, so I'm getting pretty close to being done with my triangulation class. It can now take an object and triangulate all of its faces if they are simple faces (either concave or convex). It can also triangulate faces with holes and faces that self-intersect (bascially it runs through a pre-processing step to turn those complex faces into simple faces before running through the triangulation routine). Triangulation of simple faces is done through ear clipping (ala Dr. Eberly's paper on the subject). I have one final preprocessing step I'd like to run the object's faces through before I call this one done. And that is dealing with faces that are not planar. As you can imagine, creating a line segment during triangulation can cause an ugly seam across a face if it runs across a non-planar area of the face. Having already run through the first two preprocessing steps (so we know there are no holes or self-intersections left), the idea is to cut up the face along any seams (if any) such that the result is two (or more) planar polygons that can be triangulated. I've come up with an algorithm for this, but it seems pretty naive. 1) Take three adjacent vertex points and determine their plane (if they are colinear, add more points until you get a unique plane). This is the test plane. 2) Add more vertex points to this list, going both clockwise and counter-clockwise, until you reach a point that is no longer on the test plane (within a tolerance). Back up to your last valid vertex that lies on the test plane. Note that if your counterclockwise direction test vertex equals your clockwise direction test vertex, you have gone all the way around the face, and it was planer to begin with, end the routine here. 3) Once you have all the adjacent vertex points that are coplanar, draw a line connecting the endpoints and split the object into two new objects. The first is planar and can be triangulated. The second needs further testing for planarity. I think that might work, although there is a slight added wrinkle that the end points have to be mutually visible to each other (at this point I haven't quite figured out what to do if they are not). That's what I've come up with. Are there any better suggestions? Anything else I ought to be thinking about?

##### Share on other sites
On further reflection, my algorithm isn't going to work at all. For example, if you take a planar octagon, then push one vertex backward out of the plane of the rest of the vertices. The result of my algorithm would draw a line segment right across the non-planar part, which is certainly not the desired result.

So now I'm at a bit of a loss. What's the solution here?

##### Share on other sites
Quick and simple way: Create a new vertex at the center of the face, by taking the average position of the vertices. Then create a fan of triangles that gos out from this center point to each edge. Will only work with convex faces, of course. If you want a better approximation, you'll have to subdivide it a lot and create many new vertices.

Another thing I should mention. No matter what you do, you can't try to split it into coplanor parts, because none of it should be coplanor if even one vertex is moved.

Edit: Just thought of something. In the case that only one vertex deviates from the plane of the rest, you could do a nice triangulation just by doing a fan originating from that vertex.

[Edited by - StealthNinja on May 14, 2007 6:56:44 PM]

##### Share on other sites
The real question is "What should a non-planar face look like when rendered?"

Take the simplest example - a square with one vertex above or below the plane described by the other 3 corners. How should that be rendered? It should (I think) obviously result in two triangles, but there are two ways to place the triangles with respect to the out-of-plane vertex that each results in a different shape.

Since the information about which triangulation is correct doesn't exist, you just have to pick one. Your algorithm works fine for segmenting a face into planar segments, but it sounds like that isn't the way you feel they should be triangulated..?

##### Share on other sites
Aye, you have a point, Extrarius, and in the course of considering this issue this afternoon, it had crossed my mind that this might be a problem with no solution, since the intent of the designer is in play here, and we just don't have enough information to know what that intent was.

However, having said that, I think StealthNinja may be on to something there. Dropping a new vertex at the average point of the vertices, then connecting it with line segments to N-1, N, and N+1 (where N is the vertex out of plane) might give the best result (where I define "best" as "the most likely triangulation desired by the designer"). I could be wrong, but in my head it seems better than my original proposed algorithm.

And yes, I'm aware it would only work for convex faces. However, as part of my ear clipping algorithm implementation, I've already got routines that classify the angles between vertices as convex or reflex, so I think from there subdividing the face into a convex portion containing the out-of-plane vertex is fairly trivial (and would also solve the issue of mutual visibility between points, since all points in a convex polygon are so).

So I have three choices:

1) Ignore the issue and just let the triangulator go at it. This may produce unsightly seams, but to some extent that's inevitable anyway. It's the easiest approach, and since we don't know what the designer intended in the first place, may be the best. We leave it to the designer to clean up any bad seams (serves him right for sending non-planar faces to the triangulator in the first place!)

2) Go with a simple algorithm like the one I initially proposed. It's simple, but not without significant problems (the biggest being it leaves unresolved the issue of mutual visibility and what to do if the vertices you want to connect are not). Probably will still require attention by the developer to seams, may not be any better than the first option.

3) Go with the more complex one suggested by SN. Solves the mutual visibility problem. Loses a point for adding a new vertex (one of my goals was to keep that to a minimum, and other than adding them to resolve certain types of self-intersections, I've met that goal so far). This will, of course, still create seams in the face, but they will be less intense than the first two choices (at least I *think* so, could be wrong). My reservation here is does this *really* have a better chance of nailing the intent of the designer, or am I kidding myself? Will the resulting seams really be less intrusive than just letting the triangulator handle it? I'm just not sure.

I'm very open to advice. I've pretty much talked myself out of number 2, but am split between 1 and 3 now.

: Ah rats, I just realized option 3 doesn't necessarily solve the mutual visibility problem any more than option 2 does. Don't know why I didn't realize that, brain must be tired. I'm now even more inclined to simply go with option 1.

[Edited by - RonHiler on May 14, 2007 8:56:09 PM]

##### Share on other sites
Somehow I recall a thread some time ago about this topic. It is not clear what a "nonplanar polygon" is. If you have a manifold on which the vertices live, you can make sense of this concept. Without the underlying surface, the concept is ambiguous.

Someone already pointed out the problems with a nonplanar quadrilateral. It gets worse. Consider the closed polyline with ordered vertices (0,0,0), (1,0,0), (1,0,1), (0,0,1), (0,1,1), (1,1,1), (1,1,0), (0,1,0), (0,0,0). One interpretation leads to a triangulation that produces three faces of a cube. Another interpreations leads to a triangulation that produces three different faces of a cube.

If your concern is that the vertices are theoretically in a plane but numerical round-off errors cause the vertices to be "slightly" nonplanar, then (1) fit the vertices with a least-squares plane, (2) project the vertices onto that plane, and (3) triangulate the results as a polygon in 2D.

##### Share on other sites
I think you misunderstand, David. No one said anything about a "nonplanar polygon". You'll notice I used the term face rather than polygon. A polygon implies planarity. A face has no such restriction. Maybe if you knew what these were and where they come from it would help.

These faces are created by modelers, I have no control over the objects they are going to build. Although all objects start out with polygon faces (in the form of primitives like cuboids), they can move the vertices of an object around the build area independently of each other (this is a pretty standard feature of any half decent modelling program), and there is no guarantee the faces of the objects they are going to send to the triangulator are going to be planar. In fact, a great deal of the time I expect they won't be. I have to prepare the routines for the worst the desginers can throw at it!

It would be nice if I could just error out of the routine and tell the designer, "no, you cannot triangulate that object, it contains faces that are non-planar", but that's just not going to fly. When a designer hits the triangulate button, they expect a triangulated object, and as the programmer, I'm expected to give it to them :)

I get what you and Extrarius are saying, there is ambiguity here with regards to how you interpret a non-planar face. I do have a face normal (or the best approximation of it we can get if the face is not planar, using Newell's Method), and of course the vertex winding tells me which way the normal is facing, so there's a little more information there than just the vertices and adjacency information, but not a lot. The best I can do is to try to produce the best chance of giving the triangulation the modeler expects. Could it still be the wrong interpretation? Of course it could. I get that. I just have to do the best I can.

The question is how to get there? Is it best to write a complicated preprocessing routine to examine some portion of the face that is convex and take an average vertex value and add the seam there, or do I just throw my hands into the air and send the whole thing to the triangulator as is? I don't know, that's what I'm asking y'alls expert opinion about.

I have triangulation. I have triangulation with holes. I even have triangulation with faces that self-intersect. I feel like I'm pretty close to having done everything I can to take whatever messy object the designers throw at my program and give back a decent result (well, I have one last post-triangulation step to code, but it's pretty trivial). If I could get past this one last hurdle, I'm done, and can move on to other systems. And I'm going to be glad. I knew going into it this system was going to be a nightmare, and its lived up to its expectations in that regard :)

So, if you have any advice on which way would be better (or something completely different) to get past this, I'd be glad for it.

##### Share on other sites
In my fading experience, OpenGL deals with non-planar 'polygons' by transforming and projecting the vertices as normal, then rasterising from there. This always 'works' because the projection maps them all to a plane. Everything looks fine from a static viewpoint, but as the camera moves, the object changes shape.

I think this is really the only way to proceed. Your renderer can only give well-defined results for well-defined objects (I guess that's the contrapositive of GIGO), so its contract should be 'give me a planar face and I'll render it right'. If the client code breaks the contract, anything goes, and its the user's fault.

##### Share on other sites
Aye. I was just trying to give the users as much slack in that contract as I could :)

I'm increasingly of the opinion that I'm just going to say to hell with it and feed the face to the ear-clipping routine regardless of its planarity. I don't really see the point of sending the face through another complicated preprocessing step which may or may not produce better results. The ear-clipper itself doesn't care if the faces are planar or not.

That's pretty awesome for me, since my triangulator class suddenly (and quite unexpectedly) just became virtually finished. I was expecting to spend another two or three weeks working on it. Now I'm thinking I'll be done by the end of the day. Sweet.

Just as a final check, I'm going to see what happens with a couple of professional modeling packages when they're fed such cases. But unless they suddenly give me a major insight, I think I'm done.

##### Share on other sites
Quote:
 Original post by RonHilerI think you misunderstand, David. No one said anything about a "nonplanar polygon". You'll notice I used the term face rather than polygon. A polygon implies planarity. A face has no such restriction. Maybe if you knew what these were and where they come from it would help.

I very well understand what you are asking. I, for one, have no objections to using the term "nonplanar polygon" (for example, a spherical polygon), and my post was not intended to be an objection. Call it a "face" if you will, but you want to apply triangulation--an inherently planar concept--to something that is not planar. The name "polygon" or "face" will not change the technical difficulties. The more information you have about the problem domain, the more you can formulate an algorithm that will solve problems in that domain.

Your later suggestion of just feeding what you have to an ear-clipping algorithm might work--but then again it might not, because such algorithms rely on planarity. Despite my mathematical background, I work as an engineer who has to solve problems, knowing that "you cannot solve this" does not sit well with your clients. But attempting to solve the problem by crossing your fingers when you try something not designed to solve the problem is not really a good engineering solution.

If the modeler starts off with a planar triangle mesh, and then he starts moving vertices around, the question is: By how much? If the final modification of the planar triangle mesh is a complicated terrain, you have your work cut out for you. If the vertices are just slightly moved, then you have a lot more hope to accomplish your goals. In this case, create a surface on which the vertices live and use a 2D parameterization so that you are back in Planar Land.

For example, fit the vertices with a plane using least squares, project the vertices onto that plane, and triangulate the result. If the vertices were moved enough so that the mesh has nearly flat regions, yet has some sharp creases, then decompose the mesh into the nearly flat regions. Apply the least-squares fit of a plane to each region.

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013556
×