# OpenGL How to split polygon into triangles?

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

## Recommended Posts

I'm using anim8or as my 3D modeller and am writing the code to import the models into my OpenGL project. I've run into a problem, as I had intended to use vertex arrays to store the mesh data. However anim8or store objects as the highest n-gons available, and the number of points may vary thruought the mesh. The data stored looks like this:
      5 4 0 -1 ( (2 0) (7 1) (4 2) (1 3) (0 4) )
5 4 0 -1 ( (3 5) (9 6) (6 7) (2 0) (0 4) )
5 4 0 -1 ( (1 3) (5 8) (8 9) (3 5) (0 4) )
5 4 0 -1 ( (4 2) (10 10) (11 11) (5 8) (1 3) )
5 4 0 -1 ( (6 7) (12 12) (13 13) (7 1) (2 0) )
5 4 0 -1 ( (8 9) (14 14) (15 15) (9 6) (3 5) )
5 4 0 -1 ( (7 1) (13 13) (16 16) (10 10) (4 2) )
5 4 0 -1 ( (11 11) (17 17) (14 14) (8 9) (5 8) )
5 4 0 -1 ( (9 6) (15 15) (18 18) (12 12) (6 7) )
5 4 0 -1 ( (16 16) (19 19) (17 17) (11 11) (10 10) )
5 4 0 -1 ( (18 18) (19 19) (16 16) (13 13) (12 12) )
5 4 0 -1 ( (17 17) (19 19) (18 18) (15 15) (14 14) )


That first number (a 5 in all of the cases in this example) is the number of sides the polygon will have. The next 3 numbers don't matter for this discussion. The following list is made up of n groupings, where the first one is the index into an array of vertices. So the first polygon in the mesh is a pentagon made up of the vertices 2, 7, 4, 1, and 0. Simple enough, right? Well, certainly not for using vertex arrays. I originally thought I could just split the mesh up into all triangles, but that appears to be complicated for anything more complex than a square. Does anyone know a simple algorithm to do this? Thanks in advance!

##### Share on other sites
Quote:
 Original post by CyberSlag5kWell, certainly not for using vertex arrays. I originally thought I could just split the mesh up into all triangles, but that appears to be complicated for anything more complex than a square. Does anyone know a simple algorithm to do this?

That's called a tesselator, or a triangulator. Check out this site.

Alternatively, you can also use the OpenGL glu library tesselation functions (GLUtesselator, and gluTess*() calls). From my experience, the glu tesselators are usually extremely robust, stable, and easy to use. Even if you don't use OpenGL, you can compile the tesselator separately, and use it with DirectX or whatever else (the source is available through Mesa).

##### Share on other sites
Well, if you need to split up the polygons into triangles (and perhaps I haven't understood your problem correctly, because this solution is very simple), you could create a linear index array for triangles. The index array would begin (2, 7, 4, 2, 4, 1, 2, 1, 0). You take the first index (2), then the second (7) and the third (4). Then you take the first vertex again, then the fourth (1), then the fifth (0) and so on. You cut the pentagon up into three triangles. The new index array is constructed from the indices you already have. You don't need to change your vertex/normal/texcoord arrays at all, just your index array...

##### Share on other sites
Quote:
 Original post by iNsAn1tYWell, if you need to split up the polygons into triangles (and perhaps I haven't understood your problem correctly, because this solution is very simple), you could create a linear index array for triangles. The index array would begin (2, 7, 4, 2, 1, 0). You take the first index (2), then the second (7) and the third (4). Then you take the first vertex again, then the fourth (1), then the fifth (0). You cut the pentagon up into two triangles. The new index array is constructed from the indices you already have. You don't need to change your vertex/normal/texcoord arrays at all, just your index array...

That doesn't work with concave polygons.

##### Share on other sites
Quote:
Original post by Yann L
Quote:
 Original post by iNsAn1tYWell, if you need to split up the polygons into triangles (and perhaps I haven't understood your problem correctly, because this solution is very simple), you could create a linear index array for triangles. The index array would begin (2, 7, 4, 2, 1, 0). You take the first index (2), then the second (7) and the third (4). Then you take the first vertex again, then the fourth (1), then the fifth (0). You cut the pentagon up into two triangles. The new index array is constructed from the indices you already have. You don't need to change your vertex/normal/texcoord arrays at all, just your index array...

That doesn't work with concave polygons.

Yes. The algorithm's based on the assumption that they're all convex. I should have mentioned that. Like I said, it's very simple [grin]

##### Share on other sites
Quote:
 Original post by iNsAn1tYYes. The algorithm's based on the assumption that they're all convex. I should have mentioned that. Like I said, it's very simple [grin]

Well, if CyberSlag's 3D modeller polygon output is guaranteed to be convex, then the whole thing becomes just as easy as the example you outlined (which is basically a tri fan, you could also use tri-stripping based approaches). I don't know if that guarantee of convexity applies in this case, though.

##### Share on other sites
I used an algorithm based on this :

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/twoears.html

IFIRC it handles covex & concave. You walk along the polygon in order, make a triangle out of three vertices, and make sure itdoesn't cross an existing edge. Eventually you have a list of tris from the polygon.

##### Share on other sites
Thanks guys. Most appreciated :)

##### Share on other sites
Can't the modeller you use output triangles instead. Is there not a setting? I ask because I have never used it, not to be rude as it may sound. I would think there would be such a setting.

##### Share on other sites
Quote:
 Original post by kburkhart84Can't the modeller you use output triangles instead. Is there not a setting? I ask because I have never used it, not to be rude as it may sound. I would think there would be such a setting.

Nope. I even asked the program's creator. And you didn't sound rude at all.

• ### Similar Content

• By khawk
We've just released all of the source code for the NeHe OpenGL lessons on our Github page at https://github.com/gamedev-net/nehe-opengl. code - 43 total platforms, configurations, and languages are included.
Now operated by GameDev.net, NeHe is located at http://nehe.gamedev.net where it has been a valuable resource for developers wanting to learn OpenGL and graphics programming.

View full story
• By TheChubu
The Khronos™ Group, an open consortium of leading hardware and software companies, announces from the SIGGRAPH 2017 Conference the immediate public availability of the OpenGL® 4.6 specification. OpenGL 4.6 integrates the functionality of numerous ARB and EXT extensions created by Khronos members AMD, Intel, and NVIDIA into core, including the capability to ingest SPIR-V™ shaders.
SPIR-V is a Khronos-defined standard intermediate language for parallel compute and graphics, which enables content creators to simplify their shader authoring and management pipelines while providing significant source shading language flexibility. OpenGL 4.6 adds support for ingesting SPIR-V shaders to the core specification, guaranteeing that SPIR-V shaders will be widely supported by OpenGL implementations.
OpenGL 4.6 adds the functionality of these ARB extensions to OpenGL’s core specification:
GL_ARB_gl_spirv and GL_ARB_spirv_extensions to standardize SPIR-V support for OpenGL GL_ARB_indirect_parameters and GL_ARB_shader_draw_parameters for reducing the CPU overhead associated with rendering batches of geometry GL_ARB_pipeline_statistics_query and GL_ARB_transform_feedback_overflow_querystandardize OpenGL support for features available in Direct3D GL_ARB_texture_filter_anisotropic (based on GL_EXT_texture_filter_anisotropic) brings previously IP encumbered functionality into OpenGL to improve the visual quality of textured scenes GL_ARB_polygon_offset_clamp (based on GL_EXT_polygon_offset_clamp) suppresses a common visual artifact known as a “light leak” associated with rendering shadows GL_ARB_shader_atomic_counter_ops and GL_ARB_shader_group_vote add shader intrinsics supported by all desktop vendors to improve functionality and performance GL_KHR_no_error reduces driver overhead by allowing the application to indicate that it expects error-free operation so errors need not be generated In addition to the above features being added to OpenGL 4.6, the following are being released as extensions:
GL_KHR_parallel_shader_compile allows applications to launch multiple shader compile threads to improve shader compile throughput WGL_ARB_create_context_no_error and GXL_ARB_create_context_no_error allow no error contexts to be created with WGL or GLX that support the GL_KHR_no_error extension “I’m proud to announce OpenGL 4.6 as the most feature-rich version of OpenGL yet. We've brought together the most popular, widely-supported extensions into a new core specification to give OpenGL developers and end users an improved baseline feature set. This includes resolving previous intellectual property roadblocks to bringing anisotropic texture filtering and polygon offset clamping into the core specification to enable widespread implementation and usage,” said Piers Daniell, chair of the OpenGL Working Group at Khronos. “The OpenGL working group will continue to respond to market needs and work with GPU vendors to ensure OpenGL remains a viable and evolving graphics API for all its customers and users across many vital industries.“
The OpenGL 4.6 specification can be found at https://khronos.org/registry/OpenGL/index_gl.php. The GLSL to SPIR-V compiler glslang has been updated with GLSL 4.60 support, and can be found at https://github.com/KhronosGroup/glslang.
Sophisticated graphics applications will also benefit from a set of newly released extensions for both OpenGL and OpenGL ES to enable interoperability with Vulkan and Direct3D. These extensions are named:
GL_EXT_memory_object GL_EXT_memory_object_fd GL_EXT_memory_object_win32 GL_EXT_semaphore GL_EXT_semaphore_fd GL_EXT_semaphore_win32 GL_EXT_win32_keyed_mutex They can be found at: https://khronos.org/registry/OpenGL/index_gl.php
Industry Support for OpenGL 4.6
“With OpenGL 4.6 our customers have an improved set of core features available on our full range of OpenGL 4.x capable GPUs. These features provide improved rendering quality, performance and functionality. As the graphics industry’s most popular API, we fully support OpenGL and will continue to work closely with the Khronos Group on the development of new OpenGL specifications and extensions for our customers. NVIDIA has released beta OpenGL 4.6 drivers today at https://developer.nvidia.com/opengl-driver so developers can use these new features right away,” said Bob Pette, vice president, Professional Graphics at NVIDIA.
"OpenGL 4.6 will be the first OpenGL release where conformant open source implementations based on the Mesa project will be deliverable in a reasonable timeframe after release. The open sourcing of the OpenGL conformance test suite and ongoing work between Khronos and X.org will also allow for non-vendor led open source implementations to achieve conformance in the near future," said David Airlie, senior principal engineer at Red Hat, and developer on Mesa/X.org projects.

View full story
• By _OskaR
Hi,
I have an OpenGL application but without possibility to wite own shaders.
I need to perform small VS modification - is possible to do it in an alternative way? Do we have apps or driver modifictions which will catch the shader sent to GPU and override it?
• By xhcao
Does sync be needed to read texture content after access texture image in compute shader?
My simple code is as below,
glUseProgram(program.get());
glBindImageTexture(0, texture[0], 0, GL_FALSE, 3, GL_READ_ONLY, GL_R32UI);
glBindImageTexture(1, texture[1], 0, GL_FALSE, 4, GL_WRITE_ONLY, GL_R32UI);
glDispatchCompute(1, 1, 1);
// Does sync be needed here?
glUseProgram(0);
GL_TEXTURE_CUBE_MAP_POSITIVE_X + face, texture[1], 0);
glReadPixels(0, 0, kWidth, kHeight, GL_RED_INTEGER, GL_UNSIGNED_INT, outputValues);

Compute shader is very simple, imageLoad content from texture[0], and imageStore content to texture[1]. Does need to sync after dispatchCompute?

• My question: is it possible to transform multiple angular velocities so that they can be reinserted as one? My research is below: