Behold a 5000-pyramid smoothly-growing shrub! That’s it! Keep beholding!

I’ve been working with a lot of largish loops lately, iterating a series of nested processes over lists of ever-increasing size, and bumping into some soft walls.

However! Whether through inspired genius or cargo-cult pigeon-pecking, I have arrived at a superior method.

First, I will bore you with the setup, followed by code and cake.

Setup

Somewhere between 500 and 700 iterations of the old shrub-growing code, MEL began to choke on something. Certain sub-processes stopped functioning, and it started gradually neglecting its collision detection. If I set the target size beyond the top boundary of this amorphous no-man’s-land, the code skipped collision detection completely from the get-go, and put all the pyramids in the same place.

Why not insert some kind of error-catching? Perhaps a handy print() or two? That would be handy, yes, but MEL refuses to give me any print()s until the whole thing is done, so I’d get a barrage of errors once the whole thing had finished, and by then I’d forgotten who I was.

After throwing quite a few typewriter-wielding monkeys at the problem, I found that adding a flushUndo in the loop cut down on the ram-hoarding, at the cost of speed, but it seemed to work more consistently. Turning undo off entirely before running the code helped even more.

However — the biggest speed boost came when I disabled the key-setting code. The boost stayed when I split the placement and animation code entirely, not setting any keys until after the placement had finished.

So now the code can place 1000 pyramids, complete with collision detection, in 4 minutes, and can set the keys afterward in no time at all. The time required for more pyramids still goes up exponentially: 5000 pyramids took an hour and a quarter. But by gum, it works!

N.B.: the code does not produce the scene above: Once the scene was built, I rendered a non-linear frame sequence with Science. Here’s the code for the Science:

Science

// render 5000 frames in 500 frames, exponentially
float $increase = 1.0;
int $totalFrames = 5000;
int $renderFrames = 500;
float $increaseVal = pow($totalFrames-$renderFrames, 1.0/$renderFrames);
for ($frame = 0.0; $frame < $renderFrames; $frame++) {
  $increase *= $increaseVal;
  currentTime ($frame + $increase);
  render -b;
}

Yes, that's how it was.

The idea here is that the rendered frame number should equal the animation frame number times a steadily-increasing amount. Put another way, since I knew I wanted 500 frames, advancing at a rate of at least one image per frame, I wanted image# to equal frame# + some constant times itself 500 times (aka x^500), such that image 1 = frame 1 and image 500 = frame 5000. Put another way: 500+(x^500) = 5000. Solving for x we get 4500^(1/500) which in this case = 1.016965980175, aka that $increaseVal number.

So. Good-bye to all that. Here is the pyramid-building code, set to 500 pyramids. It takes about a minute-fifteen here, and works best with undos off. I lied about the cake.

Pyramid-Building Code

// start smooth 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 -sp 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[];
  global string $growList[];
  $coneList[0] = $old[0];
  $growList = $coneList;

  int $totalCones = 500;

  string $new;

  // main creation loop
  for ($i=1; $i<$totalCones; ++$i) {
    while (1 == 1) {
      // pick a random cone in growlist
      int $growInt = floor(rand(size($growList)));
      $growCone = $growList[$growInt];
      // 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;
        break;
      }
    }
  }

  // delete all bottom faces to lighten the load
  for ($i=1;$i<size($coneList);$i++) {
    $which = $coneList[$i];
    delete ($which + ".f[0]");
    // set visibility and scale keys
    setKeyframe -attribute "visibility" -v 0 -t 0 $which;
    setKeyframe -attribute "visibility" -v 1 -t ($i) $which;
    setKeyframe -attribute "scaleY" -v 0 -t ($i) $which;
    setKeyframe -attribute "scaleY" -v 1 -t ($i+5) $which;
    keyTangent  -edit -time ($i+5) -itt "flat" $which;
  }

  clear $coneList;
  clear $growList;
}
doit();
print("done!");
$totalTime = `timerX -startTime $startTime`;
print ("Total Time: "+$totalTime/60+" minutes\n");

// end smooth shrub

« previously: “Yoga” Scrabble ad by Wizz | Home | next: Mondo shrub »

This entry was posted on Tuesday, April 28th, 2009 at 7:08 pm and is filed under Code, MEL. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.