This is a first stab at a worm which doesn’t self-intersect. This has led me into the valley of collision detection, which turns out to be deep, dark, and cluttered with the bones of many programmers wiser than I.

So far the code prevents any pyramid’s points from landing in the volume of any other pyramids, and starts another branch if the main branch runs into a blind alley (which happens at about 12 secs in the above video).

The resulting worm is semi-polite — it exhibits fewer blatant intersections and more coiling knots, but the loopholes in the code allow very sneaky intersections, including pyramids sharing an edge and overlapping edges. Tackling that will be the next step; hopefully it won’t triple the length of the code again.

MEL code follows:

//--start--

proc vector[] getVertices(string $mesh) {
  // get the number of vertices in the mesh
  int $vertexCount[] = `polyEvaluate -v $mesh`;
  vector $vectors[];
  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;
}

proc float distanceBetween(vector $aLoc, vector $bLoc) {
  return `mag <<$aLoc.x-$bLoc.x, $aLoc.y-$bLoc.y, $aLoc.z-$bLoc.z>>`;
}

// 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]>>;
}

// 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 center of a cone - midway between pivot and peak
proc vector centerOfCone(string $cone) {
  vector $coneLoc = getAttr($cone+".translate");
  vector $topLoc = `pointPosition -w ($cone+".vtx[3]")`;
  vector $center =  <<($coneLoc.x + $topLoc.x)/2,
                      ($coneLoc.y + $topLoc.y)/2,
                      ($coneLoc.z + $topLoc.z)/2>>;
  return $center;
}

// 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 < 2 && $iDist != 0) {
      // possible intersection, add index to list of suspects
      $ids[size($ids)] = $i;
    }
  }
  return $ids;
}

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;
    }
  }
}

// get a normal relative to the face
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;
}

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 the faces, it's inside; works with any convex solid
  return 1;
}

// 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 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 ($checkingFaces == 1) {
    // 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);
    int $suspects[] = checkProximity($conePos);
    $i = 0;
    $checkingSuspects = 1; // current face is still checking suspects
    $intFound = 0;
    while ($i<size($suspects) && $checkingSuspects == 1) {
      int $suspect = $suspects[$i];
      // if there's already a pyramid there
      if (centerOfCone($new) == centerOfCone($coneList[$suspect])) {
        print(" "+$coneList[$suspect]+" THERE ");
        $intFound = 1;
        $checkingSuspects = 0; // give up on this face
        delete $new;
      }
      // if intersection found
      else if (pyramidsIntersect($new, $coneList[$suspect]) == 1) {
        $intFound = 1;
        $checkingSuspects = 0; // give up on this face
        delete $new;
      }
      $i++;
    }
    if ($intFound == 1 && size($faces)==0){
      // intersection found, try another face
      $new = "fail";
      $checkingFaces = 0;
    }
    if ($intFound == 0 && $i>=size($suspects)) {
      // all suspects cleared!
      $checkingFaces = 0;
    }
  }
  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];

  int $totalCones = 500;
  int $growCone = 0; // index of cone to grow from
  string $new;

  // main creation loop
  for ($i=0; $i<$totalCones-1; ++$i) {
    while (1 == 1) {
      // attempt to grow a new cone
      $new = copyCone($coneList[$growCone]);
      // if no growth spaces open on that cone
      if ($new == "fail") {
        // remove it from the coneList
        stringArrayRemoveAtIndex($growCone, $coneList);
        // pick another random cone in the list and try again
        $growCone = rand(size($coneList));
      } else { // success!
        setKeyframe -attribute "visibility" -v 0 -t 0 $new;
        setKeyframe -attribute "visibility" -v 1 -t ($i+2) $new;
        break;
      }
    }
    // if success, add new cone to list
    $coneList[size($coneList)] = $new;
    $growCone = size($coneList)-1;
  }

  // delete all bottom faces to lighten the load
  for ($i=1;$i<size($coneList);$i++) {
    delete ($coneList[$i] + ".f[0]");
  }
  clear $coneList;
}
doit();
print("done!");

//--end---

« previously: Sloppy worm knot | Home | next: Torakku Yaro »

This entry was posted on Sunday, February 15th, 2009 at 9:00 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.