0
\$\begingroup\$

I wrote a simple Wavefront parser in C++ that loads v, vn, vt and f into std::vectors.

The most f lines in my .obj file contain four triples like this:

    f 601/10518/265 10522/10517/265 10521/10516/265 602/10515/265

obviously, if I have four triples I create two triangles.

But I do not understand well enough what to do with the last f line in my .obj file that contains about 700 triples:

    f 3229/3228/1 3456/3227/1 3455/3280/1 3508/3279/1 3507/3332/1 3560/3331/1 3559/3384/1 3612/3383/1 3611/3436/1 3664/3435/1 3663/3488/1 3716/3487/1 3715/3540/1 3768/3539/1 3767/3592/1 3820/3591/1 3819/3644/1 3872/3643/1 3871/3696/1 3924/3695/1 ....

From wikipedia: OBJ files also support free-form geometry which use curves and surfaces to define objects, such as NURBS surfaces.

Is this line a some kind of this NURBS surfaces? If yes what lib can I use for them?

How to convert it to triangles? (For drawing with OpenGLES).

Can I use GL_TRIANGLE_STRIP or GL_TRIANGLE_FAN?

Below I provided a trivial plane example that I load successfully:

    # Blender 3.6.5
    # www.blender.org
    mtllib plane.mtl
    o Plane
    v -1.000000 0.000000 1.000000
    v 1.000000 0.000000 1.000000
    v -1.000000 0.000000 -1.000000
    v 1.000000 0.000000 -1.000000
    vn -0.0000 1.0000 -0.0000
    vt 0.000000 0.000000
    vt 1.000000 0.000000
    vt 1.000000 1.000000
    vt 0.000000 1.000000
    s 0
    f 1/1/1 2/2/1 4/3/1 3/4/1

but my real-life mesh is too long to add there, I exported it in Blender from this:

enter image description here

\$\endgroup\$
3
  • \$\begingroup\$ In your screenshot, I see a large face at the top left that seems to have a great many vertices along its perimeter. Could this be the source of the very long line you found? \$\endgroup\$
    – DMGregory
    Commented Nov 4, 2023 at 11:04
  • \$\begingroup\$ @DMGregory theoretically it can, it is a result of Dissolve faces in Blender, see details here: developernote.com/2023/10/… \$\endgroup\$ Commented Nov 4, 2023 at 11:07
  • \$\begingroup\$ So now that you know it's just one big planar polygon of n vertices, you can triangulate it into n-2 triangles along the diagonals. How have you tried doing that, and where did you get stuck? \$\endgroup\$
    – DMGregory
    Commented Nov 4, 2023 at 11:12

1 Answer 1

1
\$\begingroup\$

As we hashed out in the comments, that 700-entry line seems to be the middle face of your tile: a square with something like 174 T-junctions on each side would give you the 700-entry line you're seeing.

All those T-junctions are vertices in one big polygon (an n-gon, or specifically a 700-gon), so we need to break it into triangles for rendering just like we do for quads.

If you have a list of vertices in order around the perimeter of a convex polygon, you can triangulate it into a strip by alternating two steps:

  • Take two vertices from the end of the list and one from the start to make a triangle. Remove one vertex from the end of the list.

    MakeTriangle(startIndex, endIndex - 1, endIndex);
    endIndex--;
    
  • Take two vertices from the start of the list and one from the end to make a triangle. Remove one vertex from the start of the list.

    MakeTriangle(startIndex, startIndex + 1, endIndex);
    startIndex++;
    

(Note that this reduces to the same thing you're already doing if the input has 3 or 4 vertices. I've expressed the code examples above as shifting indices for the start and end instead of removing a vertex and shifting the rest of the list down, for efficiency.)

To avoid degenerate triangles, you may need to cycle the list (move vertices from the end to the start) so that the first triangle you pick has non-zero area. In the case of the big square face in the image, that means starting in one of the corners, so that the alternating steps above give you zig-zag cuts diagonally across it.

You can also build a fan by using just one of these steps repeatedly, but this will tend to give you more long and skinny triangles, including many with zero area in the example from the image. The strip strategy helps balance out the sizes.

In general though, you want to do most of the hard work of triangulating the mesh in the DCC (Digital Content Creation) software like Blender before importing the content into your game/engine. These tools are designed for this work, and have the structure/adjacency information available to do higher-order operations, handle non-convex polygons, etc. Digesting your meshes into quads and triangles before import lets you keep your game or engine's import code simpler (and faster!) and can give you higher quality results, as artists can control exactly how those complex n-gons get triangulated, rather than leaving it up to one fixed algorithm.

In this case, an artist working in Blender could notice that most of the edges along the straight sides of the tile are unnecessary and remove them, so the top face becomes just a single big quad without T-junctions all along its length. This reduces your polygon and vertex counts for better rendering performance.

The resulting topology would look like this, all quads, no n-gons:

▦▤▦
▥□▥
▦▤▦
\$\endgroup\$
3
  • \$\begingroup\$ What if it is not a convex polygon? see en.wikipedia.org/wiki/Convex_polygon and en.wikipedia.org/wiki/Convex_set \$\endgroup\$ Commented Nov 5, 2023 at 13:31
  • 1
    \$\begingroup\$ Then you can search polygon triangulation for algorithms that work on non-convex polygons. But as stated in my answer, I do not recommend implementing this in your game/engine — let tools like Blender, which already handle these cases, do the heavy lifting for you before you export. Then your import code stays as simple and fast (free of bugs / artifacts / nasty edge cases) as possible. \$\endgroup\$
    – DMGregory
    Commented Nov 5, 2023 at 15:38
  • \$\begingroup\$ Yes, at least in my mesh this dissolved face is a convex polygon. \$\endgroup\$ Commented Nov 5, 2023 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .