Generating the RRT Image

How was it created?

The tree was generated iteratively by sampling a cube in 3 dimensions, and using a seed point located at the base (the "root" of the tree).  A total of 1000 nodes were generated by iterating an "Extend" macro.  Here is a snippet of the POVRay code I used to generate the whole tree:

////////////////////////////////////////////////////////////////
// "rrt.mcr"
// RRT generation and display macros
// James Kuffner, Jr.
// September 2001

// initialize tree data structures
#declare rrtMaxNodes   = 1000;
#declare rrtNodes      = array[rrtMaxNodes]
#declare rrtNodeParent = array[rrtMaxNodes]
#declare rrtNodeDepth  = array[rrtMaxNodes]

#declare rrtNodeParent[0] = -1;    // parentIndex
#declare rrtNodeDepth[0]  = 0;     // tree depth

////////////////////////////////////////////////////////////////
//
// grow a branch on the RRT
#macro Extend(rrtTarget, rrtStepSize, rrtNumNodes)
  #local nearestIndex = FindNearestNeighbor(rrtTarget, rrtNumNodes);
  #local rrtBase = rrtNodes[nearestIndex];
  #local dist = DistanceMetric(rrtBase, rrtTarget);
  #local fract = 1.0;
  #if (dist > rrtStepSize)
     #local fract = (rrtStepSize / dist);
  #end
  #local rrtEnd = fract * (rrtTarget - rrtBase);
  #declare rrtNodes[rrtNumNodes] = rrtBase + rrtEnd;
  #declare rrtNodeParent[rrtNumNodes] = nearestIndex;
  #declare rrtNodeDepth[rrtNumNodes] = rrtNodeDepth[nearestIndex] + 1;
#end

////////////////////////////////////////////////////////////////
//
// incrementally generate rrt

#macro BuildRRT(rrtDimension, rrtMin, rrtMax, rootNode, rrtStepSize)
  #declare rrtNodes[0] = rootNode;  // root 
  #declare rrtNodeParent[0] = -1;   // parentIndex
  #declare rrtNodeDepth[0] = 0;     // tree depth
  #local rrtNumNodes = 1;
  // incrementally build RRT
  #while (rrtNumNodes < rrtMaxNodes)
    #local rrtTarget = RandomSample(rrtDimension, rrtMin, rrtMax);
    Extend(rrtTarget, rrtStepSize, rrtNumNodes)
    #local rrtNumNodes = rrtNumNodes + 1;
  #end
#end

Rendering the RRT

After the tree was generated, I used another set of macros to generate the tree geometry from the RRT node data.  Each branch of the tree is modeled as an open cylinder, with branch connections (RRT nodes) modeled as spheres.  The radii of the spheres and cylinders is proportional to the maximum "distance" of all descendant nodes of a given RRT node.  This has the effect of making larger all branches that support distant child branches in the tree.

Each of the leaf nodes of the RRT were made to appear "glowing" by adding a hollow, emissive sphere using the POVRay media effect construct:

sphere { < 0, 0, 0 >, 1
  pigment { rgbt < 1, 1, 1, 1 > }   // color of glow
  interior {
    media {
	emission rgb < 1.0, 0.6, 0.7 > * 0.08  // control brightness
	intervals 1
	samples 5
	method 3
	density { spherical }
    }
  }
  translate rrtNodes[i]   // position sphere and leaf node i
  hollow
}

This increases the rendering time a lot, but it adds more depth to the image.  In addition to the media effect, I added some simple fog and adjusted the lighting to create a more surrealistic feel.

Some Intermediate Test Images

Here are a few intermediate images I created along the way to debug and test different effects:

More Art and CG Images...