Polite shrub

April 22nd, 2009

Back 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 »

Leave a Reply