View Full Version : Some dumb questions about triangulation for OpenGL

09-19-2016, 01:46 AM

I'm making an exporter. The situation is that I have the verts as polygons with the verts in render order for each polygon. I am just doing this test cube for the time being.

First off, does it really matter how I triangulate it, assuming I don't try to make a triangle fan or anything? If not then obviously it's quite easy to cut off ears of polygons (should always be quads probably) in the right direction.

Doing it that way the first face's triangles would be yellow-red-black then black-blue-yellow.

Many of the polygons are all contiguous so I could go red-black-yellow then yellow-black-blue. This way I end on the starting vert of the next polygon in many cases. Or is that just coincidence.

Sorry, I know these are sort of dumb questions but I don't want to get too far ahead of myself on this exporter if I am making a mistake at the most basic level.

09-19-2016, 01:53 AM
If I understood you correctly, polygon ordering does not matter that much in an exporter. But it might, depending on the purpose of the tool which created this geometry (ie, if the tool directly use the mesh for the rendering, ordering might have been calculated in a manner that cache is well used).

What would import more is the polygon winding (so vertex ordering in a polygon). Changing this, might result in a mesh drawn in the reverse (you'll see hidden faces whereas the front-faces would not be drawn).

Finally, I would suggest you to generate triangles, not quads.

PS: for the rest, I'm not really sure of what you are asking for.

09-19-2016, 02:00 AM
Hmm, well I am importing it to OpenGL for rendering. In maya things are not triangulated. The reason being that this makes changing things an incredible mess. In the export I want to triangulate each polygon in code. It's not in ccw order by default but I made code to get the verts into the right order already. If it does not matter how the triangles are done so long as they are all there (which seems to be what you are saying) then that makes the job easier. Thanks.

And yeah I will make sure to keep triangles counterclockwise, I don't want triangles to disappear.

09-19-2016, 02:52 AM
Commonly, data go under a treatment once read. For example, one will generally do some ordering in the face lists so that it can reuse cache. Also, if the file does not contain any indexes, the final application might use indexing so that vertices are not repeated, to save up some memory requirement in the GPU. We actually don't know if you are doing such post-process.

As a general-purpose format, face ordering should not be very important. However, it might if someones exports to your new format, then reimports it, that person would expect to have exactly the same file as the original one. It depends on the purposes of what you are doing.

Strictly for import/export, face ordering is not important. Face winding might. Polygon type (quads or triangles) also might (mainly because some applications might understand only triangles not quads).

Since you target only OpenGL rendering, then face ordering might be relevant for the reasons mentioned above (mainly cache reuse) if you don't plan to do some post-process on them. Face winding will, but you already are ensuring this. And for the polygon types, it is strongly advised to use triangles, triangle strips or triangle fan only (or lines).

09-19-2016, 03:10 AM
Commonly, data go under a treatment once read. For example, one will generally do some ordering in the face lists so that it can reuse cache.

Do you have any resource or name of this so I can look up what this entails? And thanks again for your input.

09-19-2016, 04:22 AM
You can read this wiki page (https://www.opengl.org/wiki/Post_Transform_Cache) for example.

And I could found a discussion about it on this forum (https://www.opengl.org/discussion_boards/showthread.php/167481-Vertex-cache-optimization).

09-19-2016, 07:15 AM
I've wondered about this a bit myself. My solution was to have modeling program do the triangulation. Blender has that option. I'm sure Maya would have at least as much capability as Blender. The modeling program has more info about the situation than you do unless it exposes that information. It could be storing it all as triangles and then presenting it as faces and therefore would have no need to do any actual triangulation when called for. Since the vertex buffer doesn't accept polys, it must be doing this on some level.

But that doesn't really answer the question of how to do it yourself.

With anything beyond a triangle you are just asking for trouble. Even with a simple quad there are two different diagonals you can choose. With n-gons the problem increases exponentially. And with no triangle normals, it's basically impossible to solve the problem as far as I can see. You just have to assign random edges and hope for the best.

However, if you can make the assumption that a "face" has co-planar vertices, this problem drops to being trivial. Since all triangles on the face are co-planar, it doesn't really matter how you divide them. Even random works. The vertices still have to be wound in the proper direction, obviously. But how the edges are defined isn't important. I'm not even sure if it would matter for UV wrapping.

I haven't tried this. Like I said, I just let Blender take care of it for me before exporting the model. But it seems to me that you have to assume faces are co-planar and then the problem isn't a big deal, I would assume. Of course, until I actually try it, I'm just guessing.

09-19-2016, 08:38 AM
However, if you can make the assumption that a "face" has co-planar vertices

This isn't sufficient. It's necessary for all vertex attributes (colour, texture coordinates, etc) to have an affine mapping. I.e. the vertices have to be co-planar in (x,y,z,w,r,g,b,a,s,t,r,q,...) space, not just in terms of their spatial coordinates.

But if that isn't the case, then you're in trouble whatever you do. Any tessellation into triangles is probably "wrong".

Bilinear interpolation can be implemented in a shader, but it's complicated by the fact that each triangle needs the attributes for all four vertices of the original quad, or at least parameters derived from them.

09-19-2016, 01:28 PM
Well, it is maya so it stores things in a kind of weird manner. I don't want to triangulate the meshes first because it makes them unmanageable. I can triangulate and then undo it but that is messy and probably slow. I might also eventually expand the exporter to other platforms, too, so I want to keep full control so that I hopefully get the same results regardless of the tool used and not get bad results on some and good on others.

Sounds like postprocessing stuff is a good idea for performance, but so long as it works for now is the main concern. I just wanted to make sure I was not messing up before I spent a bunch of time pulling stuff together.

09-19-2016, 11:48 PM
Nothing prevents you to do this "postprocessing" before saving your file, so that you end up with triangles and indexes. Loading the file for the rendering will then be very fast.

I really suggest to use triangles (and strips and fan). Quads will lead you to some issues later as GClements explained it. Once you have quads, it's nothing more than doing a little loop for each of these quads. And if you use indexing, you just add some indexes without having to add any vertices, normals or texture coordinates or so.

Also, there is now collada (https://www.khronos.org/collada/), which should normally be a standard exchange format. I say normally, because from my concern, I never saw it that much used (but maybe it is).

09-21-2016, 12:26 AM
In maya itself there has to be quads, that is all there is to it. That doesn't say anything about the end result, though.

Collada is truly horrible and it really isn't meant as something for game engines per se. It is one of the main reasons I am writing an exporter, and this will basically go directly into the engine with a couple clicks. I will probably fix up the triangles into triangle fans or whatever some day but for now getting exporting to work at all is the goal (though all my normals UVs etc. all seem to be correct I also want to export textures and so on and save the export options into the object itself).