Converting quadriladerals in an OBJ file into triangles?

Question

At first, it seemed obvious... Make 2 triangles per face wherever 4 indices were found, right?
Meaning, the following:

v 1.000000 1.000000 0.000000
v -1.000000 1.000000 -0.000000
v 1.000000 -1.000000 0.000000
v -1.000000 -1.000000 -0.000000
f -4 -3 -2 -1

... would, in turn, need to be converted into something like:

v 1.000000 1.000000 0.000000
v -1.000000 1.000000 -0.000000
v 1.000000 -1.000000 0.000000
v -1.000000 -1.000000 -0.000000
f -4 -3 -2
f -2 -3 -1

This particular example, of course, would render correctly.
However, not all cases are as simple as splitting the face into two faces (where the first face contains the first three vertices of the original face, and the second face contains the last 3 vertices, as per the above example). Take the following cube, for example:

v 0.000000 1.000000 1.000000
v 0.000000 0.000000 1.000000
v 1.000000 0.000000 1.000000
v 1.000000 1.000000 1.000000
v 0.000000 1.000000 0.000000
v 0.000000 0.000000 0.000000
v 1.000000 0.000000 0.000000
v 1.000000 1.000000 0.000000
f 1 2 3 4
f 8 7 6 5
f 4 3 7 8
f 5 1 4 8
f 5 6 2 1
f 2 6 7 3

These faces cannot be split the same way in the previous example... So, I would need some way of knowing how to split a quadrilateral face into two triangle faces, whilst using the correct indices for the second face...

How can this be achieved? Please note that I am NOT using the fixed-function pipeline, and therefore, using GL_QUADS is NOT an option. My rendering engine is pretty much stuck on using GL_TRIANGLES only.

Cadmann

I understand the confusion here, I spend the last two days trying to figure this out. These are not QUADs but triangle strips, the documentation is very poor on this. – Saimon

Answer 1

If you have 4 indices, e.g.:

0 1 2 3

The division into two triangles would be one with the first 3 indices, and one with the first, third, and fourth. In this example:

0 1 2
0 2 3

Let's try some ASCII art to illustrate this:

3-------2
|      /|
|    /  |
|  /    |
|/      |
0-------1

Here you see 0 1 2 3 as the quad, 0 1 2 as the first triangle (bottom-right), and 0 2 3 as the second triangle (top left).

More generally, for faces with n vertices, you generate triangles:

0 (i) (i + 1)  [for i in 1..(n - 2)]

If you don't insist on separate triangles, you can also use GL_TRIANGLE_FAN primitives, which are still in core OpenGL. That way, you can draw any convex polygon with a triangle fan, using the original sequence of indices. So a triangle fan with vertex sequence 0 1 2 3 describes the quad in this case, and it very easily generalizes to faces with more than 4 vertices.

Edit: Since you still appear to have problems, let's see how this applies to the example in your post. I'll list the original index sequence of the quad for each face, and the index sequence for the two triangles after splitting the quad.

f 1 2 3 4 --> (1 2 3) (1 3 4)
f 8 7 6 5 --> (8 7 6) (8 6 5)
f 4 3 7 8 --> (4 3 7) (4 7 8)
f 5 1 4 8 --> (5 1 4) (5 4 8)
f 5 6 2 1 --> (5 6 2) (5 2 1)
f 2 6 7 3 --> (2 6 7) (2 7 3)

That looks correct to me when I draw the cube. Remember to subtract 1 from the indices for your use, since these are 1-based indices, and you will almost certainly need 0-based indices.

Thermotensile

Are you sure this is correct for all cases? In my final "cube" example above, this would render one of the faces incorrectly, resulting in a "cut corner" on one side of the cube (even with GL_TRIANGLE_FAN). So either something else is wrong with my code, or the object itself, or your answer does not handle all cases. – Cadmann

Which face do you have a problem with? I sketched it, and it all looks fine when using 0-based indices. But the example file you posted is indeed broken because indices in OBJ files are supposed to be 1-based. Here's a cube example: people.sc.fsu.edu/~jburkardt/data/obj/cube.obj. File format definition: fileformat.info/format/wavefrontobj/egff.htm. – Thermotensile

Thanks, I'll take a look at that and I'll get back to you – Cadmann

Okay, so that cube renders properly. But the ones listed HERE and HERE (Both of which are taken from THIS specification) appear to have missing/malformed triangles... and after closer examination from our previous topic found HERE, I figured perhaps the issue could've been spawned from OBJ files where faces contain quads (as they weren't being handled properly). So to fix this, I have taken it upon myself to split quads into two triangles, which lead me to the issue in my question above... – Cadmann

I have also tried meshes exported in OBJ format from 3DS Max, as well as THIS one found off a random website... and it seems as long as the faces are straight-up triangles instead of quadrilaterals (a plane mesh, for example), then it renders fine. But for whatever reason, quads always seem to mess up, and I've rewritten my code about a dozen times now trying to figure out why, and the only thing I can think of doing is to change all quads into triangles. – Cadmann

Part of the problem might still be that some of these files use 0-based indices (which I think is wrong). Other than that, it's hard to tell why this isn't working for you. – Thermotensile

Yeah those were actually typos from when I was debugging them. I've tried each file as 0-based and 1-based, and the only major difference it makes is turning planes (for 0-based) into a single triangle (for 1-based)... The majority of cubes still render improperly, irregardless of index base, and I'm pretty sure it has something to do with faces containing more than 3 indices per line. I'm still banging my head over this... – Cadmann

For the example you gave, I added the result of applying the proposed sub-division to the answer. – Thermotensile

Okay so I think I'm starting to get to the bottom of this, and I just have one final question... For faces containing negative indices (aka "interspersed referencing"), i.e: f -3 -2 -1... Which direction are they referencing vertices? Would -3 mean "Go back three vertices from the most recent", or "Go to the third vertex since the last face statement", or something else entirely? None of the OBJ specifications seem to go into great detail about these, and I'm seeing them in about half of these mesh files, leading me to believe that I'm also doing something wrong with those. – Cadmann

I believe -1 refers to the latest vertex you read before the face, -2 to the one before that, etc. That's what the Wikipedia page says as well: "-1 represents the latest defined vertex". – Thermotensile

This has now been (mostly) solved, and I'm able to render most meshes without an issue. Turns out, the actual problem was that I was forcing a zero-based index on all face indices, without firstly checking if they were actually "reference" (negative) indices... The end result was that non-reference indices were zero-based, and referenced indices were if fact -1 based... There were a few other bugs as well. But, for the most part, it appears to be working now, and I feel that even though your answers weren't addressing the actual issues, you deserve the points for staying & helping. Thanks! – Cadmann

This answer helped me immensely; it was the tiny piece of pointing out that the faces are 1-based, not 0-based that fixed my draw problems completely. THANK YOU! – Bandage

Worked perfectly. – Aptitude

Answer 2

Writing my own obj loader and reading the spec very carefully, the details on the 'f' parameter are very vague, especially seeing some files contain 'f' lines with > 4 arguments on them.

Turns out that these are actually a triangle strip in an odd order. Correct conversion to triangles is as follows (psuedo code):

n = 0;
triangles[n++] = [values[0], values[1], values[2]];
for(i = 3; i < count(values); ++i)
  triangles[n++] = [
    values[i - 3],
    values[i - 1],
    values[i]
  ];

Example:

f: A B C D E F G

Would be the following 5 triangles:

A B C
A C D
B D E
C E F
D F G

Saimon

The information in this answer is wrong, the resulting triangles would be ABC, ACD, ADE, AEF, AFG – Zoroastrian

Are you saying the vertices are wrong or the pseudo-code is wrong? – Saimon

I didnt look at the pseudo-code, but the vertices are wrong. They are not forming a triangle strip. They are forming triangle fan. – Zoroastrian

Assuming that the vertices A..G are counterclockwise (which they are according to the specification for the f format), your triangles ABC and BDE overlap. I agree with @Á.Márton on what the vertices should be. The ith triangle should consist of v[0], v[i], v[i+1] (if i starts at 1) – Sorilda