PDA

View Full Version : delaunay triangulation & voronoi


hilti
11-21-2006, 12:07 PM
hey there...

i'm searching for a script concerning the generation of voronoi structures (in 3D) based on the delaunay triangulation. does anybody wrote/knows such a script?
would be so nice, if somebody could help me.

best regards/c.

Starrider
11-29-2006, 06:48 AM
hi!
i read this here... http://forums.cgsociety.org/showthread.php?t=434923 and i wondered if you two are developing a script for triangulation now. i'd be very interested in the results and i could offer to convert it to a maya node (api) for you.
what do you think?
D

grantimus
11-29-2006, 08:11 AM
That is a very generous offer Starrider. I don't know what hilti is up to. My first guess would be that he is trying to recover a polygonal surface from some kind of point cloud. You know, the kind of thing a laser scan or photogrametric survey would output. Or maybe he just needs to put together some kind of scientific visualization.

At any rate, calculating these kinds of things with MEL alone would be SSSSLLLLLLLOOOOOOWWWWW. Hilti should seriously consider your offer.

Besides, it would be cool to see some useful tools come out of CGTalk collaborations.

Starrider
11-30-2006, 08:26 AM
hi!
yeah i was wondering if it's possible to do that in mel without having the time to drink too much coffee. but if you have working mel code, it's quite easy to convert it to a maya node.
so how far are you? do you have some code yet?
D

tbaypaul
12-01-2006, 04:30 PM
Well, I'm bummed, I hate it when something stumps me......I was hoping that I could be of more help....but the Delaunay tri answer seems to elude me.
I have duplicated a bit of code from J.O'Rourke's Computational Geometry in C book, but the true answer seems to be buried in either the text or in it's problems.

I get....almost the right answer......but it is not correct in that it contains too many redundancies in the solution...

The idea is to take your sample set to the next higher dimension via a parabolic...ie xyz creates xyzv where v = sum of the squares of the other three coordinates. Get the normal in 4d space and sort thru the faces based on pointing down the neg v axis. Then that set is sorted based on neg v and a neg dot product with a sample point m. Allowing only the bottom convex hull along v...and that is the solution set in xyz....supposedly...

maybe someone can clarify it all...it is such a simple concept geometrically.....attached is a 2d version.....


////////////////////////////////////////////////////////////
// delaunayTriangulation3d.mel script maya 8
// nov26, 2006
// script to hopefuly calculate the delaunay triangulation
// of 3d points.
// Based on the O(n^4) algorithm dt4.c in Joseph O'Rourke's
// Computational Geometry in C 2ed p187
// and gratimus 4d cross product script.
////////////////////////////////////////////////////////////
{
float $x[], $y[], $z[], $v[]; // input coordinates of points (x, y, z, v=x^2 + y^2 + z^2)
int $numberOfPnts = 0; // number of points in sample
int $i, $j, $k, $m; // indices of points
float $xN, $yN, $zN, $vN; // outward normal to ($i, $j, $k)
int $flag; // true if test point m is above point ($i, $j, $k)

string $triangle[];
string $stringArray[];
// alt test point set
//$x = {31, -13, -63, -5, 87, 40, 23, 64, 0, -14};
//$y = {10, 55, 75, 55, 35, 15, 25, 10, 85, 65};
//$z = {-76, 21, -83, -66, -94, 71, -46, -80, -57, 2};
$x = {-5, 5, 5, -5, -5, 5, 5, -5};
$y = {5, 5, 5, 5, -5, -5, -5, -5};
$z = {5, 5, -5, -5, 5, 5, -5, -5};
$numberOfPnts = `size($x)`;
int $q;
for($q = 0; $q < $numberOfPnts; $q++)
{
spaceLocator -p ($x[$q]) ($y[$q]) ($z[$q]);
}
//print ($numberOfPnts + "\n");
// input points and calculate v.
for($i = 0; $i < $numberOfPnts; $i++)
{
$v[$i] = $x[$i]*$x[$i] + $y[$i]*$y[$i] + $z[$i]*$z[$i];
//print($v[$i] + "\n");
}
// loop for each triple set of points (i, j, k)
for($i = 0; $i < $numberOfPnts - 2; $i++)
for($j = $i + 1; $j < $numberOfPnts; $j++)
for($k = $i + 1; $k < $numberOfPnts; $k++)
if($j != $k)
{
// compute normal to triangle (i, j, k) in 4d coordinate space
float $u[], $v[];
$u = {($x[$j] - $x[$i]), ($y[$j] - $y[$i]), ($z[$j] - $z[$i]), ($v[$j] - $v[$i])};
$v = {($x[$k] - $x[$i]), ($y[$k] - $y[$i]), ($z[$k] - $z[$i]), ($v[$k] - $v[$i])};
float $cross[] = {($u[1]*$v[2]-$v[1]*$u[2]) + ($u[1]*$v[2]-$v[1]*$u[3]) + ($u[2]*$v[3]-$v[2]*$u[3]),
($v[2]*$u[3]-$u[2]*$v[3]) + ($u[2]*$v[0]-$v[2]*$u[0]) + ($u[3]*$v[0]-$v[2]*$u[0]),
($u[1]*$v[3]-$v[1]*$u[3]) + ($v[1]*$u[0]-$u[1]*$v[0]) + ($u[3]*$v[0]-$v[3]*$u[0]),
($v[1]*$u[2]-$u[1]*$v[2]) + ($v[1]*$u[0]-$u[1]*$v[0]) + ($v[2]*$u[0]-$u[2]*$v[0])};
$xN = $cross[0];
$yN = $cross[1];
$zN = $cross[2];
$vN = $cross[3];
$flag = $vN < 0;
//print($flag + " :flag set after vNormal evauation\n");
if($flag)
for($m = 0; $m < $numberOfPnts; $m++)
{
float $dot = ($x[$m] - $x[$i]) * $xN + ($y[$m] - $y[$i]) * $yN + ($z[$m] - $z[$i]) * $zN + ($v[$m] - $v[$i]) * $vN;
//print($dot + "\n");

$flag = $flag && $dot <= 0;
//print($flag + " :flag set at $flag && $dot evaluation\n");

if($flag)
{
// convert int to strings for indices so we can use stringArrayRemoveDuplicates on it.
string $test1, $test2, $test3;
$test1 = string ($i);
$test2 = string ($j);
$test3 = string ($k);
$triangle[0] = ($test1 + " " + $test2 + " " + $test3);
//print ($triangle[0] + "\n");

$stringArray = stringArrayCatenate($stringArray, $triangle );
}
}
}
// removed redundent triangle entries
//print ($stringArray);
$stringArray = stringArrayRemoveDuplicates($stringArray);
print "Final string array\n";
print ($stringArray);
int $arraySize = `size($stringArray)`;
// convert to int indices for polyFacet creation and set to single sided poly's
int $counter;
string $arrayOut[];
for($counter = 0; $counter < $arraySize; $counter++)
{
int $arrayOutSize = `tokenize $stringArray[$counter] $arrayOut`;
//print $arrayOut;
int $ii = float($arrayOut[0]);
int $jj = float($arrayOut[1]);
int $kk = float($arrayOut[2]);
string $facet[] = `polyCreateFacet -ch 0 -p ($x[$ii]) ($y[$ii]) ($z[$ii]) -p ($x[$jj]) ($y[$jj]) ($z[$jj]) -p ($x[$kk]) ($y[$kk]) ($z[$kk])` ;
string $facetShape[] =`listRelatives -s $facet[0]`;
setAttr ($facetShape[0] + ".doubleSided") 0;
}
}

ThirdRail
10-17-2007, 03:00 AM
Apologies for resurrecting on old thread...

Was any progress made as a plug-in?

CGTalk Moderation
10-17-2007, 03:00 AM
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.