Rendering Nested Triangles via Recursion | Fundamentals of SVG Programming: Concepts to Source Code (Graphics Series)

Rendering Sierpinski Curves

Informally, a Sierpinski triangle involves the creation of half-sized sub-triangles of an equilateral ('all sides equal') triangle. The following example shows you how to use recursion in order to successively sub-divide a set of triangles that are 'derived' from an initial triangle. Consider the image displayed in Figure 16.2.

click to expand
Figure 16.2: A Sierpinski curve.

The SVG document in Listing 16.3 demonstrates how to define an SVG document that generates a Sierpinski curve.

Listing 16.3 Sierpinski2.svg

<?xml version="1.0" standalone="no"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN"  "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dt d"> <svg width="100%" height="100%" onload="init(evt)"   xmlns="http://www.w3.org/2000/svg">  <script type="text/ecmascript">   <![CDATA[   var width          = 800.;   var height         = 500.;   var basePointX     = 350.;   var basePointY     = 50.;   var currentX       = 0.;   var currentY       = 0.;   var offsetX        = 0.0;   var offsetY        = 0.0;   var level          = 5.;   var triangleWidth  = 600.;   var triangleHeight = 300.;   var vertexCount    = 3.;   var xPts           = Array(vertexCount);   var yPts           = Array(vertexCount);   var pointPath      = "";   var ellipseColors  = ['red','green',                         'blue','yellow'];   var colorCount     = 4.;   var triangleNode   = null;   var svgDocument    = null;   var target         = null;   var gcNode         = null;   function init(event)   {      target = event.getTarget();      svgDocument = target.getOwnerDocument();      gcNode = svgDocument.getElementById("gc");      initializeTriangle();      drawPattern(level, xPts, yPts);   }   function initializeTriangle()   {      // clockwise from top vertex...      xPts[0] = basePointX;      yPts[0] = basePointY;      xPts[1] = basePointX+triangleWidth/2;      yPts[1] = basePointY+triangleHeight;      xPts[2] = basePointX-triangleWidth/2;      yPts[2] = basePointY+triangleHeight;   } // initializeTriangle   function drawPattern(level, oldXPts, oldYPts)   {      var innerXPts = Array(vertexCount);      var innerYPts = Array(vertexCount);      var upperXPts = Array(vertexCount);      var upperYPts = Array(vertexCount);      var leftXPts  = Array(vertexCount);      var leftYPts  = Array(vertexCount);      var rightXPts = Array(vertexCount);      var rightYPts = Array(vertexCount);      if( level >= 0 )      {         for(var v=0; v<vertexCount; v++)         {            // clockwise from upper-left vertex...            innerXPts[v] =             (oldXPts[v]+oldXPts[(v+1)%vertexCount])/2;            innerYPts[v] =             (oldYPts[v]+oldYPts[(v+1)%vertexCount])/2;         }         pointPath = "";         for(var v=0; v<vertexCount; v++)         {            pointPath += innerXPts[v]+","+                         innerYPts[v]+" ";         }         fillColor  = "fill:";         fillColor += ellipseColors[level%colorCount];         triangleNode = svgDocument.createElement(                                            "polygon");         triangleNode.setAttribute("points",pointPath);         triangleNode.setAttribute("style", fillColor);         gcNode.appendChild(triangleNode);         drawPattern(level-1, innerXPts, innerYPts);         // clockwise from top vertex (upper triangle)         upperXPts[0] = oldXPts[0];         upperYPts[0] = oldYPts[0];         upperXPts[1] = innerXPts[0];         upperYPts[1] = innerYPts[0];         upperXPts[2] = innerXPts[2];         upperYPts[2] = innerYPts[2];         drawPattern(level-1, upperXPts, upperYPts);         // clockwise from top vertex (left triangle)         leftXPts[0] = innerXPts[2];         leftYPts[0] = innerYPts[2];         leftXPts[1] = innerXPts[1];         leftYPts[1] = innerYPts[1];         leftXPts[2] = oldXPts[2];         leftYPts[2] = oldYPts[2];         drawPattern(level-1, leftXPts, leftYPts);         // clockwise from top vertex (right triangle)         rightXPts[0] = innerXPts[0];         rightYPts[0] = innerYPts[0];         rightXPts[1] = oldXPts[1];         rightYPts[1] = oldYPts[1];         rightXPts[2] = innerXPts[1];         rightYPts[2] = innerYPts[1];         drawPattern(level-1, rightXPts, rightYPts);      }   } // drawPattern ]]> </script> <!-- ============================ --> <g  transform="translate(10,10)">     <rect x="0" y="0"           width="800" height="500"           fill="none" stroke="none"/> </g> </svg>

Remarks

Listing 16.3 extends the technique presented in Listing 16.2. Instead of recursively computing the coordinates of a triangle whose coordinates are the midpoints of the sides of the current triangle, this example sub-divides the current triangle into four triangles, and then recursively invokes the function drawPattern() with each of those four triangles. This seemingly minor detail produces a much richer visual effect because of the recursion that is performed.

You can enhance this example by introducing a 'shift' term for the rendered triangles, thereby creating a more abstract effect. For example, you could do something like this:

 var factor = 0.9;  .....  shiftX = (oldXPts[0]+oldXPts[2])/factor;  shiftY = (oldYPts[0]+oldYPts[2])/factor;  for(var v=0; v<vertexCount; v++)  {     // clockwise from upper-left vertex...     innerXPts[v] = shiftX+             (oldXPts[v]+oldXPts[(v+1)%vertexCount])/2;     innerYPts[v] = shiftY+             (oldYPts[v]+oldYPts[(v+1)%vertexCount])/2; }

As you experiment with different colors and various 'shifting' techniques (such as randomly generated values), you will see that some combinations are much more interesting than others are. This is actually very common and will even happen to people who have a well-developed ability to visualize or anticipate the combined effect of recursion and code variations. The best way to learn is through experimentation and by reading other examples of recursion-based code.