A 100-pyramid Pythonized polite shrub — 500 took too long, and crashed Maya.

Gory details (including code) follow:

Right, so I made a Python version of the polite shrub by tweaking the Pymel polite worm, and tested it against the MEL version. It’s slow, as I suspected. Real slow.

I’m learning things, also slowly. In Pymel, variable1 = variable2 doesn’t just set values; it turns variable1 into an auto-updating pointer to variable2. Why you’d want this, when you could just use variable2, I’m not sure, but knowing this has eliminated at least one embarrassing structural flaw in the code.

On the other hand, the MEL eats memory, and I smell a leak somewhere — Maya’s usage climbs steadily through the running, far more than I would have guessed necessary to store 500 strings, and if you set the number of iterations too high, it runs out of ram and bails. The Python is better-behaved, though my fears of long running times were well-founded: for 500 pyramids, the MEL took a minute 10 seconds; the Pymel took 36 minutes, finished, and crashed.

It’s not so bad for shorter runs, but the time increases exponentially: it can do 50 in 1 minute, 100 in 3, 200 in 9… etc. Toward the end of a 500-run, it can take upwards of 15 seconds to place a new cone, if it’s in a dense area.

So, yeah. It might just be the Pymel, but I suspect something’s still not quite on. Suspiciously, the Pymel also makes a more tightly-packed structure, resulting in more lithop-type near-intersections, as though the MEL’s collision detection is comparatively over-sensitive. This may be related to the longer running time of the Python: for higher iteration values, if everything’s more tightly-packed there are more pyramids to check for every growth.

Anyway. Possibly-broken code follows, set at 100 iterations, which takes about 3 minutes on my machine.

# start: semi-polite python worm

from pymel import *
import pymel.core.datatypes as dt
import random

startTime=timerX()

# find the center of a face - aka the "centroid"
def centerOfFace(face):
  # get locations of all the face's vertices
  pos = face.getPoints(space="world")
  returnVec = [0, 0, 0]
  # add them all together
  for vec in pos:
    returnVec += vec
  # divide by # of vectors for average
  returnVec /= len(pos)
  return returnVec

# distange between two vectors
def distanceBetween(a, b):
  a = dt.Vector(a)
  b = dt.Vector(b)
  return length(a-b)
#  return length([a[0]-b[0], a[1]-b[1], a[2]-b[2]])

def getNormal(someFace):
  fc = centerOfFace(someFace)
  # returns normal relative to face at origin
  norm = someFace.getNormal(space='world')
  returnVec = [fc[0]+norm[0], fc[1]+norm[1], fc[2]+norm[2]]
  return returnVec

# detect sidedness of a point relative to a face
def isInFront(point, face):
  faceNorm = getNormal(face)
  facePos = centerOfFace(face)
  if (getVectorAngle(point, faceNorm, facePos) <= 90):
    return 1
  else:
    return 0

# get angle between two vectors
def getVectorAngle(aLoc, bLoc, orig):
  aLoc = dt.Vector(aLoc)
  bLoc = dt.Vector(bLoc)
  orig = dt.Vector(orig)
  cLoc = aLoc-bLoc
  cLocFloor = round(cLoc, 4)
  if (cLocFloor[0]==0 and cLocFloor[1]==0 and cLocFloor[2]==0):
    return 0
  else:
    # normalize locations to the face center
    aNorm = aLoc-orig
    bNorm = bLoc-orig
    returnAngle = degrees(angle(aNorm, bNorm))
    # round answer down to two decimal places
    returnAngle = round(returnAngle, 2)
    return returnAngle

# get angle between two vertices with respect to a third point
def getVertexAngle(aVert, bVert, orig):
  aVec = dt.Vector(pointPosition(aVert))
  bVec = dt.Vector(pointPosition(bVert))
  return getVectorAngle(aVec, bVec, orig)

# find the centroid of a cone
# 1/4 of the way from the base to the peak
def centerOfCone(cone):
  coneLoc = cone.t.get()
  coneLoc = datatypes.Vector(coneLoc)
  topLoc = pointPosition(cone.vtx[3]) # 3 = peak
  topLoc = datatypes.Vector(topLoc)
  center = ((topLoc-coneLoc)/4)+coneLoc
  return center

# find nearby cones
def checkProximity(conePos):
  ids = []
  global coneList
  for i in coneList:
    iPos = centerOfCone(i)
    iDist = distanceBetween(iPos, conePos)
    # detection radius: 2r = 2
    if (iDist < 0.70710678118654752440084436210485):
      # 1/2*sqrt(2) : definite intersection
      return "fail"
    elif (iDist < 2.1213203435596425732025330863145): # 2/3*sqrt(2)
      # possible intersection, add index to list of suspects
      ids.append(i)
  return ids

def alignPyramids(pyrA, pyrB, 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(pyrA, r=1, os=1, ro=[0, angle, 0])
    # check the result
    angle2 = getVertexAngle(newVertex, oldVertex, fc)
    # if still not aligned, go the other way twice
    if (angle2 > 0):
      angle3 = angle * -2
      xform(pyrA, r=1, os=1, ro=[0, angle3, 0])

# do pyramids intersect?
def pyramidsIntersect(pyrA, pyrB):
  # get all vertexes in pyrA
  pos = pyrA.getPoints(space="world")
  for i in pos:
    # for each point in pyrA
    if isInPyramid(i, pyrB):
      return 1

  # not yet? try the other way around
  pos = pyrB.getPoints(space="world")
  for i in pos:
    if isInPyramid(i, pyrA):
      return 1
  # made it this far? then fail
  return 0

def isInPyramid(point, pyramid):
  for face in pyramid.faces:
    if (isInFront(point, face)):
      return 0 # it's outside
  # if it's behind all four faces, it's inside
  return 1

def copyCone(old):
  # make a list of faces on old that aren't the base
  faces = [1, 2, 3]
  new = ''
  while (len(faces) > 0):
    # pick a random face
    r = random.choice(faces)
    # strike face off the list
    faces.remove(r)
    selectedFace = old.f[r]
    fc = centerOfFace(selectedFace)
    # copy cone and move to selected face
    dupe = duplicate(old)
    new = dupe[0]
    xform(new, a=1, t=[fc[0], fc[1], fc[2]])
    # aim new at face with a temporary normal constraint
    tmpConst = normalConstraint(selectedFace, new, aim=(0, 1, 0))
    delete(tmpConst)
    alignPyramids(new, old, fc)

    # collision detection - is area in new occupied?
    # reference coneList
    global coneList
    # check for other cones in search radius
    conePos = centerOfCone(new)
    if (len(coneList) > 1):
      suspects = checkProximity(conePos)

      if (suspects == "fail"):
        delete(new) # start over
        new = "fail"
      else:
        for i in suspects:
          if (pyramidsIntersect(new, i) == 1):
            # intersection found, try another face
            delete(new)
            new = "fail"
            break
        # no intersections? copy is good, clear facelist
        if (new == 'fail'):
          continue
        else: faces = []
    else: faces = []
  # facelist empty?
  return new

coneList = []

def doit():
  # make a tetrahedron
  new = polyCone(r=1, h=1.414214, sx=3)[0]
  # move its pivot point to the bottom face
  xform(rp=(0, -0.707107, 0))
  # move to origin and freeze xforms
  xform(t=(0, 0.707107, 0))
  makeIdentity(apply=True, t=1)

  # initialize cone list
  global coneList
  coneList = [new]
  growList = [new]

  totalCones = 100

  # main creation loop
  for i in range(totalCones-1):
    while (1 == 1):
      # pick a random cone in growList
      growCone = random.choice(growList)
      # attempt to grow a new cone
      new = copyCone(growCone)
      # if no growth spaces open on that cone
      if (new == "fail"):
        # remove it from the coneList
        growList.remove(str(growCone))
      else:
        # success! add new cone to list
        coneList.append(new)
        growList.append(new)
        setKeyframe(new, attribute = "visibility", v = 0, t = 1)
        setKeyframe(new, attribute = "visibility", v = 1, t = i+2)
        break

  # delete all bottom faces to lighten the load
  for i in coneList:
    delete(i.f[0])

  del coneList
  del growList

doit()
select(None)
totalTime = timerX(startTime=startTime)
print("Total Time: "+str(totalTime))

# end

« previously: Anchored | Home | next: Subprime »

This entry was posted on Friday, April 24th, 2009 at 6:44 pm and is filed under Code, Python. 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.