Sign in to follow this  

Techniques to avoid skinny triangles with constrained delaunay triangulation

Recommended Posts

Gumgo    968

I am creating procedurally generated levels by stitching together "tilesets" created in a 3D modeling program such as 3DS max. Each tile consists of a 2x2x2 "section" of geometry, such as a wall, floor, corner, etc. These tiles are placed next to each other to form rooms and hallways.


After all the tiles are placed, I run a mesh simplification algorithm over the resulting geometry to reduce polygon counts for rendering and physics (and eventually NavMesh generation). The algorithm goes something like this:

1) Form groups of adjacent coplanar triangles that all have the same UV barycentric parameterizations (e.g. removing vertices wouldn't cause "warping").

2) Combine each group into a single polygon, possibly with holes.

3) Remove excess collinear vertices from the boundaries.

4) Triangulate the polygons using constrained delaunay triangulation.


The issue is that step 4) is prone to producing long skinny triangles, which is causing problems everywhere (e.g. breaking my thresholds used to detect collinearity). Can anyone provide some advice on how to approach this problem, or point me to some resources or algorithms that deal with avoiding this?

Share this post

Link to post
Share on other sites
apatriarca    2365
How big is your world? How big are the players and NPC? Do you really need this kind of optimization?

Are you implementing the constrained Delaunay triangulation yourself? If you do not want skinny triangles you have to introduce additional points and construct a conforming Delaunay triangulation. This means you also have to increase the triangle count relative to your constrained triangulation.

Share this post

Link to post
Share on other sites
plainoldcj    1068

Listen to apatriarca!

Just as a footnote:
If you are having problems with floating point precision, eg. for deciding colinearity,
you can consider using exact arithmetic.
In this specific case, where you use simple geometry to represent tiles, it might be even
possible to use integer math only - assuming you use integer coordinates for vertices.

Here you can see how colinearity can be decided using +, * only.

Share this post

Link to post
Share on other sites
Maze Master    510

Jonathan Shewchuk (author of the code triangle) has an excellent paper about constrained Delaunay mesh refinement here:

A lot of his papers deal with this type of thing and are very readable, see here:


The basic idea is to find triangles whose circumcircle contains the vertex of another triangle, then "pop" the triangle by placing a new vertex in the center of the circumcircle and recalculate the mesh locally. After repeating this process enough (and dealing with constraints and boundaries in a way detailed in the paper), the process will eventually end with a (refined) mesh that has no thin triangles.

Edited by Nick Alger

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this