Constrained delaunay triangulation

L

Lotias

Guest
Are there any scripts anyone has laying around for generating a constrained delaunay triangulation? I'm having a lot of trouble trying to work out the different methods for creating one. The resources I find online aren't very helpful - the explanations are rather confusing and I'm never quite sure how it works.

If nobody has a script laying around, can someone point me in the right direction? I've been stuck on this problem for quite a while. There's a helpful, simple explanation I know of for regular delaunay triangulation, but no constrained delaunay triangulation.
 
S

Shadowrend

Guest
I don't have my code at hand, but it is fairly easy to do (at least:
). I remember using two ds_lists for X / Y coords respectively, and then just drawing a polygon between those vertexes from the list. You can also just do it easier in a grid maybe. I also used some scripts from here for checking stuff, so you might find something useful there.

So the best way to start would be in pseudo code (from the top of my head):
Code:
list_x = ds_list_create();
list_y = ds_list_create();

px = mouse_x;
py = mouse_y;

if mouse_left { ds_list_add(list_x, px); ds_list_add(list_y, py); }

//draw
loop ds_list_size(list_x) { //just one list is needed cause they're both the same size
draw_vertex( ds_value(list_x, i));
draw_vertex( ds_value(list_y, i));
}
//draw the first vertexes at the and as well to close the shape correctly
And if you wanted to make holes in the shape, just subtract surface A from surface B using surfaces.
 
L

Lotias

Guest
I don't need holes in the shape, and that's not generating a Delaunay triangle mesh. That's just drawing a mesh. I need the actual data on each triangle & vertex inside the given polygon, not drawing a shape.
 
L

Lotias

Guest
I've already checked there. The closest is polygon_to_triangles, which doesn't factor in vertexes that lie inside the polygon. It only generates a mesh from a polygon outline, which is what I don't want.
 
L

Lotias

Guest
Doesn't look like there's much help available on this topic, especially for Game Maker. Oh well.
 
L

Lotias

Guest
Just a bump to see if anyone has anything on this. I keep looking at solutions on Github, but I can't even begin to translate or port any of it to Game Maker.
 
L

Lotias

Guest
Delaunay triangulation, if you look it up, is a triangulation of a set of points, not a polygon, wherein no vertex lies inside of the circumcircle of any other triangle.. Constrained Delaunay triangulation would let me generate a triangle mesh of an n-gon containing a set of points, as it lets me define edges that must appear in the triangulation.

Results of Delaunay triangulation looks like this, if that helps:
 
L

Lotias

Guest
The points are the vertexes. If it's relevant, the shape of delaunay triangulations directly corrolate with voronoi diagrams - voronoi in gray, delaunay in red, where the center of each circumcircle of the triangles forms a vertex of the voronoi diagram.

However, I don't think that information's very useful in the case of constrained delaunay triangulations.
 
L

Lotias

Guest
No idea how you get this



From this



So I'm not much got to you on this one, I'm afraid.
I never said that was the original set of points. I answered by saying that the vertexes on the black outline of a triangulation are the original points. The second image was to demonstrate the relation that delaunay triangulations have with voronoi diagrams.
 
M

Majatek

Guest
Is this something like what you're trying to achieve?



It's currently very messy using for loops to draw all the edges, but the source used for building the polygon is a path resource that is then converted into a list, which is then sorted with scripts found on the GMLscripts website. The list of values on the left represents the polygon's exterior shape, while the list of values on the right represents the triangles calculated from the polygon. Both lists are ds_list data structures.

I have yet to add an auto-detect function that corrects the source path after it's converted into a polygon to account for clockwise and counter-clockwise polygons. Once that's sorted and cleaned up into a more readable, commented example, I'll be happy with sharing the source. The only caveat is that it doesn't yet support adding points in the middle of the polygon, and that due to what I have planned I'm not considering going to the lengths of adding such a feature as it'd be wasted time on my part.
 
L

Lotias

Guest
That looks very close, but unfortunately the applications in mind require creating a triangulation of a polygon with points inside of the polygon. That aside, what's the difference between what you have here and the polygon triangulation that's also available on GMLscripts? I'm interested in using it (it'd just be far more limited than what I had in mind), I'm just not sure what's new in your implementation.

I'm surprised delaunay triangulation is so rare of a topic for video game development... triangulations are so, so useful and I can see more applications outside of skeletal animation.
 
M

Majatek

Guest
One possible way you could do it is by taking what GMLscripts outputs and then finding a way to subdivide them. Unfortunately as far as triangulation calculation goes, it's still using the ear clipping method provided by GMLscripts.

What's new is the way that the resources are being handled afaik, but ultimately yeah, I've looked around and delaunay triangulation seems to be that one topic that isn't really discussed.
 

Juju

Member
Yeah, I found that too. The pseudo-code is a direct copy-paste from the wikipedia article on Bowyer-Watson. I've made a start on the algo but I've gotten stuck. Have a gander if you'd like. I'm changing tack for now, gonna approach it from the Voronoi direction.
 

GMWolf

aka fel666
Unfortunately, for things like shader applications and mesh deformation, cels aren't the solution. :(
You can generate voronoi in shaders. In fact, I think voronoi is better suited for parallel computing than triangulation.

As for mesh deformation, I fail to see how Delaunay triangulation would help. Isn't that mesh generation?
 
L

Lotias

Guest
You can generate voronoi in shaders. In fact, I think voronoi is better suited for parallel computing than triangulation.

As for mesh deformation, I fail to see how Delaunay triangulation would help. Isn't that mesh generation?
Because it is mesh generation, it is extremely useful for generating an ideal mesh of triangles for subsequent deformation. I'm not sure how a voronoi diagram is better suited, since vertexes work in triangles...
Solved. It's a bit rough right now but it works.

Voronoi generation has already been solved graphically elsewhere. Might represent a superior method for a very large number of nodes.
I took a look, I can't tell if it's constrained but it's a huge step. I think it's possible to get closer to constrained triangulations (basically, forcing certain edges to appear in the triangulation, I think it works by ignoring points inside the circumcircle if a constraint is inbetween the center of the circumcircle and the furthest point on the new triangle, or something like that, not really sure) from here, if it's not constrained. I won't mark this solved yet because of that, but this is a big step. :)
I wish it was written for implementation in other projects though (it doesn't return the list of triangles), but that should be pretty easy to change.
 
Last edited by a moderator:

Joe Ellis

Member
Does it work by cycling through each point finding the 2 nearest points to that point and making a triangle from them? then delete any duplicate triangles after its cycled through every point
Thats easy to do, with a few do loops

like:

p=point index list
v=vertex list
t=triangle list

cp=current point
cpp=current point pos in vertex list
cpx=current point x
cpx=current point x
cpx=current point x

cd=current closest distance
cd1=1st closest distance
cd2=2nd closest distance

cn=current n

ccp=current cycle point
ccpp=current cycle point position in vertex list
ccpx=current cycle point x
ccpy=current cycle point y
ccpz=current cycle point z

cpd1=1st closest point position in vertex list
cpd2=2nd closest point position in vertex list

tv2xyz=triangle vertex 2
tv3xyz=triangle vertex 3
Code:
n=0
do
{
cp=ds_list_find_value(p,n)
cpp=ds_list_find_index(v,cp)
cpx=ds_list_find_value(v,cpp)
cpy=ds_list_find_value(v,cpp+1)
cpz=ds_list_find_value(v,cpp+2)
cd=10000
cd1=0
cd2=0

cn=n
n=0
do
{
ccp=ds_list_find_value(p,n)
if ccp=cp
{
n+=1
continue
}
ccpp=ds_list_find_index(v,ccp)
ccpx=ds_list_find_value(v,ccpp)
ccpy=ds_list_find_value(v,ccpp+1)
ccpz=ds_list_find_value(v,ccpp+2)

if point_distance_3d(cpx,cpy,cpz,ccpx,ccpy,ccpz)<cd
{
cd=point_distance_3d(cpx,cpy,cpz,ccpx,ccpy,ccpz)
cpd1=ccpp
}

n+=1
}
until ds_list_find_value(p,n)=undefined

cd1=cd
cd=10000

n=0
do
{
ccp=ds_list_find_value(p,n)
if ccp=cp
{
n+=1
continue
}
ccpp=ds_list_find_index(v,ccp)
ccpx=ds_list_find_value(v,ccpp)
ccpy=ds_list_find_value(v,ccpp+1)
ccpz=ds_list_find_value(v,ccpp+2)

if point_distance_3d(cpx,cpy,cpz,ccpx,ccpy,ccpz)<cd
{
if point_distance_3d(cpx,cpy,cpz,ccpx,ccpy,ccpz)>cd1
{
cd=point_distance_3d(cpx,cpy,cpz,ccpx,ccpy,ccpz)
cpd2=ccpp
}
}

n+=1
}
until ds_list_find_value(p,n)=undefined

tv2x=ds_list_find_value(v,cpd1)
tv2y=ds_list_find_value(v,cpd1+1)
tv2z=ds_list_find_value(v,cpd1+2)

tv3x=ds_list_find_value(v,cpd2)
tv3y=ds_list_find_value(v,cpd2+1)
tv3z=ds_list_find_value(v,cpd2+2)

ds_list_add(t,cpx,cpy,cpz,tv2x,tv2y,tv2z.tv3x,tv3y,tv3z) ///Create Triangle from the 3 vertices

n=cn
n+=1
}
until ds_list_find_value(p,n)=undefined
I'm not sure about how to do the constrained thing cus I dont really know what it means, but this code should work, and its gml so it'll probably be easy to add the constrained bit in

I might have missed the point slightly with what your after, if it needs some kind of angle comparing aswell as distance you can add that into the bits with point_distance_3d
 
L

Lotias

Guest
Does it work by cycling through each point finding the 2 nearest points to that point and making a triangle from them? then delete any duplicate triangles after its cycled through every point
Not even close - I suggest looking up what delaunay triangulation is in the first place before posting in a thread about it. What you're talking about is a general triangulation, which may be subject to flaws like tending towards 'skinny' triangles, with the method you describe having the possibility, I imagine, of overlapping triangles. Constrained means that there are certain things that must be in the triangulation - for example, triangles must lie within the outline of a polygon, or certain edges must be part of the triangulation, even if they are not delaunay triangles.
 

GMWolf

aka fel666
Yeah, I found that too. The pseudo-code is a direct copy-paste from the wikipedia article on Bowyer-Watson. I've made a start on the algo but I've gotten stuck. Have a gander if you'd like. I'm changing tack for now, gonna approach it from the Voronoi direction.
You do realize this has full cpp source right?
https://github.com/Bl4ckb0ne/delaunay-triangulation/blob/master/delaunay.cpp

If i ever get the time and drive, Ill convert it to GML. Its pretty short anyways.
 

Juju

Member
You do realize this has full cpp source right?
Yes, of course I do. I wasn't suggesting that the repo was limited to exclusively a psuedo-code snippet (because that'd be stupid).

I have implemented the Bowyer-Watson algorithm now, though the matter of applying constraints is not yet fully solved.
 

Joe Ellis

Member
Not even close - I suggest looking up what delaunay triangulation is in the first place before posting in a thread about it. What you're talking about is a general triangulation, which may be subject to flaws like tending towards 'skinny' triangles, with the method you describe having the possibility, I imagine, of overlapping triangles. Constrained means that there are certain things that must be in the triangulation - for example, triangles must lie within the outline of a polygon, or certain edges must be part of the triangulation, even if they are not delaunay triangles.
Sorry I was just trying to help out with what I know, I have read about it before, I wouldnt have posted if I didnt know what it is, I just thought that code would be a good place to start from, adding angle limits would stop slither triangles and checking for overlapping/intersecting triangles would be pretty easy and you can add other conditions you want into it aswell, it doesnt neccisarrily need to be exact delaunay in alot of cases so I thought my method could've ended up being sufficient if nothing else works/if no one gave you the exact delaunay method

Cant you flag the edges you want to be forced/constrained into the triangulation if they satisfy the certain conditions you need?
 
L

Lotias

Guest
Sorry I was just trying to help out with what I know, I have read about it before, I wouldnt have posted if I didnt know what it is, I just thought that code would be a good place to start from, adding angle limits would stop slither triangles and checking for overlapping/intersecting triangles would be pretty easy and you can add other conditions you want into it aswell, it doesnt neccisarrily need to be exact delaunay in alot of cases so I thought my method could've ended up being sufficient if nothing else works/if no one gave you the exact delaunay method

Cant you flag the edges you want to be forced/constrained into the triangulation if they satisfy the certain conditions you need?
The problem is how ensuring a large majority of triangles are delaunay, while ensuring triangles that share an edge with the constraint are "locally" delaunay works. It's a bit of a headscratcher, and requires more thought than just plugging it in.

Angle limits are not the solution; delaunay triangulation works by ensuring that none of the points given lie inside of any of the circumcircles of the generated triangles. This maximizes the minimum angle of each triangle. Angle limits would make complete triangulations impossible.
 
L

Lotias

Guest
@Lotias - Asked earlier, does it need to be Delaunay? I.e. are you searching for a solution to a 'problem that doesn't exist'?
Delaunay is the ideal solution to what I want. Regular, general triangulations would require manual refinement a good 95% of the time. I'm a little tired of explaining what delaunay triangulation is to everybody and whether or not it's really what I want. :bash:
 

Juju

Member
After having a think whilst you two had your lovers' tiff, I can't see an immediately obvious way of achieving constraints within the current framework. Seems like the accepted solutions (Chew's Second and Ruppert's) are somewhat available so that's my job for another day.
 
L

Lotias

Guest
After having a think whilst you two had your lovers' tiff, I can't see an immediately obvious way of achieving constraints within the current framework. Seems like the accepted solutions (Chew's Second and Ruppert's) are somewhat available so that's my job for another day.
I think one way would be going through triangles that intersect (sharing an edge with a constraint is fine) each constraint and removing them, and filling in the resulting holes using the constraint as an edge. I'll try playing with it but I'm not very good at messing with algorithms most of the time. Of course, other accepted solutions probably work better.
 

Juju

Member
Yeah, I thought about a subtractive method but that opens up a whole new set of problems, ones that (imo) have never been satisfactorily solved in GM. Ruppert's algo looks like the best bet to me.
 
L

Lotias

Guest
Yeah, I thought about a subtractive method but that opens up a whole new set of problems, ones that (imo) have never been satisfactorily solved in GM. Ruppert's algo looks like the best bet to me.
I'm reading about it, and it seems to insert vertices at the center of a circumcircle when triangles don't suit the triangulation, which is horrible for what I want (being able to draw a polygon and insert vertices and constraints and end up with an idealized mesh), so I don't know about Ruppert being the best bet.

I wonder if it's possible to translate this into GML -
https://github.com/mikolalysenko/cdt2d

I remember trying that once, but navigating the logic flow of it got me very lost, partially because I don't really understand javascript.
 

Juju

Member
As soon as you apply constraints to Delaunay, you're going to get imperfect, iffy meshes. There's no magic bullet here - it's a property of the maths. Chew's Second also has similar outcomes.
 
L

Lotias

Guest
As soon as you apply constraints to Delaunay, you're going to get imperfect, iffy meshes. There's no magic bullet here - it's a property of the maths. Chew's Second also has similar outcomes.
I know; I don't care that the constraints force non-ideal triangles into the mesh. I just don't want new vertices to be inserted when running the algorithm, which will often ruin the intended shape of the resulting mesh. My intent is sort of like Spine's mesh editor, which I assume uses some form of Delaunay. If you run the demo of the javascript, it doesn't seem to insert new vertices that I don't want.
 

Joe Ellis

Member
Yeah sorry about that thing I posted, I just tested it and it just results in a bunch of floating triangles haha
 
Top