Optimizing the triangulation

Graphics and GPU Programming Programming OpenGL

Started by MrSparkle27 July 28, 2008 03:06 AM

11 comments, last by Bakura 15 years, 8 months ago

142

Author

July 28, 2008 03:06 AM

Hi! I implemented the Cutting-Ear-Algorithm to triangulate any convex or concave polygon. The result is pretty good but sometimes there are some very thin triangles due to how the algorithm works. Is it recommended to optimize the triangulation or doesn't it really matters when rendering with DirectX or OpenGL? Which would be the best way to optimize the triangulation? Currently I try to compare the bounding circles of all adjoining triangles. If a triangule is completely in a bounding circle of another triangle I swap the segment between both triangles. This works pretty good but is much slower than the triangulation itself, and I'm still not sure if it's really worth it. Christian

dave

2,188

July 28, 2008 03:20 AM

Are you talking about optimising the algorithm, or optimising the resultant triangles for Direct3D/OpenGL?

MrSparkle27

142

Author

July 28, 2008 03:43 AM

I want to optimize the triangles by maximizing their internal angles, similiar to the Delaunay constraint.

MrSparkle27

142

Author

July 28, 2008 11:20 AM

This is the result so far, it creates a nice triangulation but it's still very slow at the moment. As you can see the long, thin triangles are replaced. I'm not sure if this is really appropriate.

Before optimization:

After optimization:

[Edited by - MrSparkle27 on July 28, 2008 2:20:53 PM]

Spodi

642

July 28, 2008 11:55 AM

Do you want to do this real-time? If not, there will of course be no harm in trying to reduce the amount of triangles while preserving the shape. But if you are doing it real-time, it will be hard to cut out a few extra triangles and render it faster than it will be to just render it all.

NetGore - Open source multiplayer RPG engine

MrSparkle27

142

Author

July 28, 2008 12:11 PM

Nope, I don't want to reduce the number of triangles. I just want to optimize the shape of the triangles.

The Cutting Ear algorithm can produce very thin triangles but I'm not sure if this could affect the output when rendering the mesh with DirectX or OpenGL.

In a 3d modelling program like 3ds max, it's always best to optimize the triangulation of the meshes to avoid ugly artefacts during rendering.

My question is wether it is recommended to optimize the triangulation or just waste of time.

Thanks,
Christian

PS: How can I include images to my postings?

Wyrframe

2,489

July 28, 2008 01:30 PM

Include images with good ol' <img src="" />.

RIP GameDev.net: launched 2 unusably-broken forum engines in as many years, and now has ceased operating as a forum at all, happy to remain naught but an advertising platform with an attached social media presense, headed by a staff who by their own admission have no idea what their userbase wants or expects.Here's to the good times; shame they exist in the past.

stalef

607

July 28, 2008 04:22 PM

As long as you do flat-shading, it is probably no gain in optimizing it. But as soon as you do any pr. vertex normal stuff, I believe long narrow triangles will give you artifacts.

MrSparkle27

142

Author

July 28, 2008 05:47 PM

Yes, you may be right. I also thought about texture coordinates. I guess the interpolation of the uv coordinates along the long edges can result in really ugly distortion of the textures. Maybe it's really worth to implement a mesh optimizer though.