Polite shrub
April 22nd, 2009Back to MEL, because this would have taken for-freakin-ever to run in Pymel. This is 500 pyramids.
Figured out the strategic flaw in my collision-detection. I need two lists: one of objects available for growing from, the other with everything in it, for collision-checking.
…that didn’t have anything to do with the code, it was a personal revelation. Although now I think about it, it applies to the code too. There’s still the occasional sneaky intersection, but they’re much rarer now.
Code follows:
// start polite shrub
$startTime = `timerX`;
global string $coneList[];
global string $growList[];
// find the center of a face - aka the "centroid"
proc vector centerOfFace(string $face) {
// get locations of all the face's vertices
float $pos[] = `xform -q -ws -t ($face)`;
// get length of the array: # vertices * 3
int $posSize = size($pos);
// put the average of all vectors into 1st vector
for ($i = 0; $i < 3; $i++){
for ($j = $i+3; $j<$posSize; $j+=3){
$pos[$i] += $pos[$j];
}
$pos[$i] /= ($posSize / 3);
}
return <<$pos[0], $pos[1], $pos[2]>>;
}
proc float distanceBetween(vector $aLoc, vector $bLoc) {
return `mag <<$aLoc.x-$bLoc.x, $aLoc.y-$bLoc.y, $aLoc.z-$bLoc.z>>`;
}
proc vector getNormal(string $face) {
string $pin[] = `polyInfo -fn $face`;
string $tokens[];
int $numTokens = `tokenize $pin[0] " " $tokens`;
// make sure we're looking at polyInfo data:
if ( ( $numTokens > 3 ) && ( $tokens[0] == "FACE_NORMAL" ) ) {
// returns normal relative to face at origin with no rotations
float $x = ($tokens[$numTokens-3]);
float $y = ($tokens[$numTokens-2]);
float $z = ($tokens[$numTokens-1]);
vector $fc = centerOfFace($face);
// rotate normal to match mesh xform
string $tokensB[];
int $numTokensB = `tokenize $face "." $tokensB`;
string $faceParent = $tokensB[0];
float $pRot[] = `xform -q -ro $faceParent`;
spaceLocator -p ($x) ($y) ($z) -n "norm";
xform -ro ($pRot[0]) ($pRot[1]) ($pRot[2]);
// move normal to match face center and freeze xforms
xform -t ($fc.x) ($fc.y) ($fc.z);
makeIdentity -apply true -r 1 -t 1 -s 1;
// return worldspace position of locator
float $normX = `getAttr norm.localPositionX`;
float $normY = `getAttr norm.localPositionY`;
float $normZ = `getAttr norm.localPositionZ`;
vector $returnVec = <<$normX, $normY, $normZ>>;
delete "norm";
return $returnVec;
} else print("bad getNormal input");
}
// detect sidedness of a point relative to a face
proc int isInFront(vector $point, string $face) {
vector $faceNorm = getNormal($face);
vector $facePos = centerOfFace($face);
if (getVectorAngle($point, $faceNorm, $facePos) <= 90) return 1;
else return 0;
}
// get angle between two vectors with respect to a third point
proc float getVectorAngle(vector $aLoc, vector $bLoc, vector $orig) {
if ($aLoc == $bLoc) return 0;
else {
// normalize locations to the face center
float $aOrig[] = {$aLoc.x-$orig.x, $aLoc.y-$orig.y, $aLoc.z-$orig.z};
float $bOrig[] = {$bLoc.x-$orig.x, $bLoc.y-$orig.y, $bLoc.z-$orig.z};
// use law of cosines via dot product
float $dotP = dotProduct( $aOrig, $bOrig, 1 );
float $angle = rad_to_deg(acos($dotP));
// round answer down to two decimal places
return (floor(($angle+.005)*100))/100;
}
}
// get angle between two vertices with respect to a third point
proc float getVertexAngle(string $aVert, string $bVert, vector $orig) {
float $aLoc[] = `xform -q -ws -t $aVert`;
float $bLoc[] = `xform -q -ws -t $bVert`;
vector $aVec = <<$aLoc[0], $aLoc[1], $aLoc[2]>>;
vector $bVec = <<$bLoc[0], $bLoc[1], $bLoc[2]>>;
return getVectorAngle($aVec, $bVec, $orig);
}
// find the centroid of a cone - 1/4 of the way from the base to the peak
proc vector centerOfCone(string $cone) {
vector $coneLoc = getAttr($cone+".translate");
vector $topLoc = `pointPosition -w ($cone+".vtx[3]")`;
vector $center = <<($topLoc.x - $coneLoc.x)/4+$topLoc.x,
($topLoc.y - $coneLoc.y)/4+$topLoc.y,
($topLoc.z - $coneLoc.z)/4+$topLoc.z>>;
return $center;
}
proc alignPyramids(string $pyrA, string $pyrB, vector $fc) {
// pick a vertex on each pyramid
$newVertex = $pyrA+".vtx[0]"; // 0 is on the base
$oldVertex = $pyrB+".vtx[3]"; // 3 is the tip
// get angle between two vertices
$angle = getVertexAngle($newVertex, $oldVertex, $fc);
// if not already aligned
if ($angle > 0) {
// rotate $new to align the corners
xform -r -os -ro 0 $angle 0 $pyrA;
// check the result
$angle2 = getVertexAngle($newVertex, $oldVertex, $fc);
// if still not aligned, go the other way twice
if ($angle2 > 0) {
$angle3 = $angle * -2;
xform -r -os -ro 0 $angle3 0 $pyrA;
}
}
}
// do pyramids intersect?
proc int pyramidsIntersect(string $pyrA, string $pyrB) {
// get all vertexes in pyrA
vector $pos[] = `getVertices($pyrA)`;
for ($i=0; $i<size($pos); $i++) {
// for each point in pyrA
$test = isInPyramid($pos[$i], $pyrB);
if ($test == 1) return 1;
}
// not yet? try the other way around
vector $pos[] = `getVertices($pyrB)`;
for ($i=0; $i<size($pos); $i++) {
$test = isInPyramid ($pos[$i], $pyrA);
if ($test == 1) return 1;
}
// made it this far? then fail
return 0;
}
proc int isInPyramid(vector $point, string $pyramid) {
int $numFaces[] = `polyEvaluate -f $pyramid`;
for ($i=0;$i<$numFaces[0];$i++) {
if (isInFront($point, $pyramid+".f["+$i+"]") == 1) {
return 0; // it's outside
}
}
// if it's behind all four faces, it's inside
return 1;
}
proc vector[] getVertices(string $mesh) {
// get the number of vertices used in the mesh
int $vertexCount[] = `polyEvaluate -v $mesh`;
vector $vectors[];
// process each vertex
for($i=0; $i<$vertexCount[0]; $i++) {
// get vertex positions
float $vert[] = `pointPosition ($mesh+".vtx["+$i+"]")`;
$vectors[$i] = <<$vert[0], $vert[1], $vert[2]>>;
}
return $vectors;
}
// find nearby cones
proc int[] checkProximity(vector $conePos) {
int $ids[];
global string $coneList[];
for ($i=0; $i<size($coneList); ++$i) {
$iPos = centerOfCone($coneList[$i]);
$iDist = distanceBetween($iPos, $conePos);
// detection radius: 2r = 2
if ($iDist < 0.70710678118654752440084436210485) {
$ids[0] = -1;
return $ids;
} else if ($iDist < 2.1213203435596425732025330863145) {
// possible intersection, add index to list of suspects
$ids[size($ids)] = $i;
}
}
return $ids;
}
proc string copyCone(string $old) {
// make a list of faces on $old that aren't the base
string $faces[] = {"1", "2", "3"}; // method only works for strings
int $checkingFaces = 1; // current cone is still grow target
string $new;
while (size($faces) > 0) {
// pick a random face
int $randIndex = rand(size($faces));
string $r = $faces[$randIndex];
// strike face off the list
stringArrayRemoveAtIndex($randIndex, $faces);
$selectedFace = ($old + ".f[" + $r + "]");
vector $fc = centerOfFace($selectedFace);
// copy cone and move to selected face
$dupe = `duplicate $old`;
$new = $dupe[0];
xform -a -t ($fc.x) ($fc.y) ($fc.z) $new;
// aim $new at face with a temporary normal constraint
string $tmpConst[] = `normalConstraint -aim 0 1 0 $selectedFace $new`;
delete $tmpConst[0];
alignPyramids($new, $old, $fc);
// collision detection - is area in $new occupied?
// reference coneList
global string $coneList[];
// check for other cones in search radius
vector $conePos = centerOfCone($new);
if (size($coneList) > 1) {
int $suspects[] = checkProximity($conePos);
if ($suspects[0] == -1) {
// quick intersection found
delete $new;
$new = "fail";
} else {
// possible intersections found
for ($i = 0; $i < size($suspects); ++$i) {
$suspect = $suspects[$i];
if (pyramidsIntersect($new, $coneList[$suspect]) == 1) {
// intersection found, try another face
delete $new;
$new = "fail";
break;
}
}
// no intersections? copy is good, clear facelist
if ($new != "fail") {
$faces = {};
}
}
// no suspects? no need to check faces
} else { $faces = {}; }
}
return $new;
}
proc doit() {
// make a regular tetrahedron
select `polyCone -r 1 -h 1.414214 -sx 3`;
string $old[] = `ls -sl`;
// move its pivot point to the bottom face
xform -rp 0 -0.707107 0;
// move to orig and freeze xforms
xform -t 0 0.707107 0;
makeIdentity -apply true -t 1;
// initialize cone list
global string $coneList[];
$coneList[0] = $old[0];
$growList = $coneList;
int $totalCones = 500;
string $growCone = $coneList[0]; // cone to grow from
string $new;
// main creation loop
for ($i=1; $i<$totalCones; ++$i) {
while (1 == 1) {
// attempt to grow a new cone
$new = copyCone($growCone);
// if no growth spaces open on that cone
if ($new == "fail") {
// remove it from the growList
$growList = stringArrayRemove({$growCone}, $growList);
} else { // success!
// add new cone to lists
$coneList[size($coneList)] = $new;
$growList[size($growList)] = $new;
setKeyframe -attribute "visibility" -v 0 -t 0 $new;
setKeyframe -attribute "visibility" -v 1 -t ($i) $new;
break;
}
// pick another random cone in growlist and try again
int $growInt = floor(rand(size($growList)));
$growCone = $growList[$growInt];
}
}
// delete all bottom faces to lighten the load
for ($i=1;$i<size($coneList);$i++) {
delete ($coneList[$i] + ".f[0]");
}
clear $coneList;
clear $growList;
}
doit();
print("done!");
$totalTime = `timerX -startTime $startTime`;
print ("Total Time: "+$totalTime+"\n");
// end polite shrub
« previously: Semi-polite Python worm | Home | next: Anchored »