View Full Version : delaunay tesselation

01 January 2008, 11:35 PM
hey !

i am searching for a MEL script that creates the delaunay triangulation for a cloud of locators. since i'm working in a landscape architecture office, the locators will define a landscape.
now i will need a terrain built from nurbs planes (2 + 1 + 1 cvs in 3 corners), but the code for polys would help me a step further...

i tried now several times in MEL but i was not successful with my approaches... :hmm:

the algorithm doesn't have to be fast, so connecting 50 to 100 points can easily take a minute if needed.

any help accepted... :)

* * *

by the way... i am also searching the algorithm / a MEL script to create the cathenary curve between two locators for a defined length L of the curve. also between two locators.

*help* :)

01 January 2008, 09:57 AM
this might not help alot, but i have seen scripts based on qhull that do what you want.
i have not done this myself though, sry that i cant be of more help. if you have time maybe google qhull to find out more.

01 January 2008, 12:40 PM
on wikipedia (german) i've found a method which sound pretty easy but isn't that fast. but it should really be fast enough to calculate the surface of 100 points.

you'd first need to calculate a 2d array of all points. since there's no point with the same x & y value you can simply cancel the z value of every point. this z value will then be calculated with z=x^2+y^2 where z is the new z value and x, y are the x and y values of your point.

then you need to calculate the convex hull of all those points. take all triangles facing down (z negative for the normal vector) and project them back to 2d. this will result in a 2D-Delaunay-Triangulation which can be set to your points.

you can use the 2d triangulation if there are no points with the same x and y value. since you're playing around with landscapes you often have points with the same x & y. but it doesn't matter which projection you use. just take the one which is appropriate to your case.

there's another method. you first create a simple network of triangles. it mustn't have cutting edges!
then you go on checking if the perimeter of every triangle doesn't contain another point. this is done by taking two triangles sharing one edge (4 different points, 1-2-3 = first triangle, 1-3-4 = second triangle). then check if the point 4 is in the perimeter of the first triangle. if it is you need to flip the shared edge. this will change the triangles as following:

1-2-3 (first triangle) ---> 1-2-4
1-3-4 (second triangle) --> 2-3-4

It messes up my ascii picture :D
take a look at this ( one
(Source: Wikipedia, German one)

the flipping won't change the connection of the whole network so no need to start checking from the beginning. if all you triangles fullfill the condition with the perimeter you have your delaunay triangulation.

hope this helps. i don't have time at the moment to write such a script. but it should be a lot of work. just a few lines in some loops.

PS: to calculate the perimeter of a triangle you add the position vectors of your vertices togheter and divide them by 3 (middle point of perimeter). then calculate the distance from the middle point to one of the vertices which gives you the radius. to check if a point is inside the perimeter you simply calculate the distance between middle point and the point which you want to check and if it is smaller or equal the radius of the perimeter then it's inside. else it's outside.

01 January 2008, 09:33 PM
i have tried an approach, but the way to check if a point is inside a triangle does not make sense like this.

imagine a long, thin triangle. if there's a point just outside the midpart of the triangle, this point indeed is in the range of the circle you mentioned, but nevertheless is outside the triangle. or did i miss something ?

and the other question is:
how do i check all possible triangles for the best tesselation that just creates those triangles that have the largest possible area and do not tesselate across all the model.

the rules seem very complex... :(

i'll try some more... :)

01 January 2008, 07:42 AM
If you create a cloth plane and the locators as rigid objects. it should work.

If u use quads you can convert to nurbs later

01 January 2008, 08:20 AM
wow, that's a totally new approach... !


but i need it all very precise and i guess this approach is a little funky... :)

but thanks for the input !

01 January 2008, 05:16 PM
yess it is funky......

export to ascii xyz and use freeware software to mesh......i.e. pointshop3d or terrain software.

01 January 2008, 11:42 PM
You could sort the locators into groups on Y. Then sort the groups individually based on X.

For each subgroup create a linear curve between the locator points, then loft your curves into a surface, and use NURBS->poly conversion to get a triangle mesh.

CGTalk Moderation
01 January 2008, 11:42 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.