PDA

View Full Version : loading .obj file: how to triangularize polygons ?



john_connor
07-29-2016, 08:52 AM
hi, i'm trying to load obj model files and was wondering how to triangularize faces that have more that 4 points per face (polygons)
quads can just be split into 2 triangles, but whats with n points ?

i would try it like this:
point 0 = ...
for (int i = 2; i < n; i++)
{
point i = ...
build triangle from (point 0) x (point i - 1) x (point i)
}

is that correct ?

mhagain
07-29-2016, 10:15 AM
Yes, that's correct. This is the same order as is used if converting GL_POLYGON or GL_TRIANGLE_FAN to GL_TRIANGLES.

jonhnack
08-02-2016, 03:57 AM
I wrote a little loader for obj files, and I do have a document from wotsit, and It will also have the methods required to load an OBJ file, write a VTK file, and to triangularize itself

BBeck1
08-02-2016, 08:03 PM
It's just a standard rule in 3D modeling to never create models with n-gons (polygons with more than 4 sides). 4 sides is the standard (quads). Triangles are fine, and as you know, you need triangles in order to feed your vertex shader. But after 4 sides it just gets worse and worse. Expect bad things to happen if you have n-gons. Any professional 3D modeler will tell you never have any n-gons in your model.

The most correct solution would probably be to import it into Blender (or whatever 3D modeling software you have) and fix the n-gons (remove them and replace them with triangles and/or quads). Of course doing so will probably mess up any textures or anything of that sort you have. It can also mess up animations. So, really you want to get the n-gons out pretty much the moment they appear so that you don't have to later try and fix an ugly problem.

Blender has a function that will triangulate the model and then you'll have nothing but pure triangles in the model. Then presumably you can re-export as an .OBJ.

But it's just a standard rule in 3D game modeling to never let n-gons into your model and fix them if they should appear (some operations you perform will create n-gons and you just have to rebuild those faces so that the are either quads or triangles.

Silence
08-05-2016, 02:56 AM
I don't know about if there are any real standards about this in the modeling crew. But I would say, don't use quads, use triangles. Just simply because triangles are plans by nature. Quads might not be plans, and therefore could provoke some issues for some calculations. Or then, each quad will have to be divided into triangles again in order to ensure they are plans.
Moreover (and I believe it's due to the reason mentioned above), graphic cards generally perform better with triangles than quads.
Finally, quads have been deprecated in GL 3.

BBeck1
08-05-2016, 07:09 AM
I had not even thought about previous versions of OGL doing polygons. I started in OGL 4.5 (coming from DX11).

You make a good point about the planes. Two sides of a triangle can be two vectors and their cross product will give the normal to indicate what direction the triangle faces for things like lighting and back face culling. Obviously, you have to have a triangle in order to do that rather than a polygon since more than 3 vertices could live on more than 1 plane.

I did a quick YouTube search on N-gons. This guy, who has a lot more modeling experience than me, explains why it's pretty much a standard rule not to ever use n-gons.

https://www.youtube.com/watch?v=0_1w6DqNio4

john_connor
08-05-2016, 05:02 PM
standard rule of not, there are some guys who make good models, but (unfortunately) dont care about that rule
(of course, this rule makes sense, a triangle is the most basic face type)
until now, i used (as you described previously) blender to triangularize those models
i tried to write a more flexible loader to be able to draw more / different primitives

the main difficulty:
drawing more than 1 primitive type requires more than 1 draw call :doh:
if i have to draw for example 3 faces, 1 7gon, 1 20gon and 1 55gon, i would have to call glDrawArrays(GL_POLYGON, ...) 3 times, once for each face (which is not "very efficient")
using triangles, i can draw each model type multiple times with just 1 drawcall (instanced)

in my current loader, i std::map<...> all N-gons (together in a std::vector<>) to their N
in a second step (not part of the loader) i then want to be able to translate each primitive types to triangles
my question was just mainly to get around blender ;) ...

i found that "tinyobjloader" on the internet, but unfortunately i dont know how to "translate" it to a vertexbuffer

BBeck1
08-07-2016, 07:07 AM
Ah I see.

I'm not even sure where to start with that other than to pick a vertex and make the closest two vertices into a triangle and continue in clockwise or counter-clockwise order.

There are two problems I see, one of which should not be an issue.

The first is that you could divide them in an un-natural way and change the direction they are intended to face. There are two ways to divide a quad for example with the dividing line going in opposite diagonals. However, I would take the definition of face to be that they are all on the same plane. So, that shouldn't really be an issue here.

The second is more problematic. If the polygon is concave instead of convex (for lack of a better word), you could have edges in your triangles that go outside of the polygon. Maybe there is a way to test for this and start over from a different vertex when this happens. One possible test would be to make line segments to form a ring in the shape of the polygon. Then you could test whether the proposed triangle edge crosses any of these line segments.

Oh. There's also the issue with "winding". Generally back-face culling determines which side is the inside and which is the outside by the order you define the vertices in. Clockwise is one direction and counter-clockwise is the other. So, you'll have to take that into account.

GClements
08-07-2016, 09:39 AM
The first is that you could divide them in an un-natural way and change the direction they are intended to face. There are two ways to divide a quad for example with the dividing line going in opposite diagonals. However, I would take the definition of face to be that they are all on the same plane. So, that shouldn't really be an issue here.

It's not just the geometry that this affects, but also texture mapping. If the mapping between spatial coordinates and texture coordinates is non-affine, splitting a quad (or polygon) into triangles will result in a different, affine mapping for each triangle (for a triangle, the mapping cannot be other than affine).

But that's also the case if you just pass a quad or polygon to OpenGL and allow OpenGL to split it into triangles. But if you split it yourself, you can at least ensure that the result is consistent between implementations; if you let OpenGL handle it, different implementations may split it differently. This is a large part of the reason that quads and polygons were deprecated in modern OpenGL.



The second is more problematic. If the polygon is concave instead of convex (for lack of a better word), you could have edges in your triangles that go outside of the polygon. Maybe there is a way to test for this and start over from a different vertex when this happens.

First, you need to determine the (approximate) plane of the polygon. Then, if you calculate the cross product of each pair of adjacent edges, the dot product between that and the plane's normal should always be positive (or always negative, depending upon the order used for calculating the plane normal and the cross products).

If a polygon only has a single "concave" vertex, choosing that as the starting vertex will allow you to use the "triangle fan" approach. If it has two or more, that won't work. Adding an edge between each concave vertex will "chop off" a convex section which can then be tessellated as a triangle fan, and removing all such sections will result in the remainder being convex (assuming that the polygon doesn't have holes and doesn't self-intersect).

dagreen
08-23-2016, 11:34 AM
[QUOTE=First, you need to determine the (approximate) plane of the polygon. Then, if you calculate the cross product of each pair of adjacent edges, the dot product between that and the plane's normal should always be positive (or always negative, depending upon the order used for calculating the plane normal and the cross products).

If a polygon only has a single "concave" vertex, choosing that as the starting vertex will allow you to use the "triangle fan" approach. If it has two or more, that won't work. Adding an edge between each concave vertex will "chop off" a convex section which can then be tessellated as a triangle fan, and removing all such sections will result in the remainder being convex (assuming that the polygon doesn't have holes and doesn't self-intersect).[/QUOTE]

That also helped me a lot man thanks!