Triangle subdivision

                        

Subdivide(Patch p) {
  if ((p->Level) - (p->Neighbor0->Level) == 1) {
    // p is deeper than its 0th neighbor; subdivide that

    Subdivide(p->Neighbor0);
  }
  if ((p->Level) - (p->Neighbor1->Level) == 1) {
    Subdivide(p->Neighbor1);
  }
  if ((p->Level) - (p->Neighbor2->Level) == 1) {
    Subdivide(p->Neighbor2);
  }
  // Create P's three children;

  // Set up the neighbor links for P's children;

}

[/source]

Note that if this is done right there shouldn't be any
data-integrity issues; that is, if p (in the process of being
subdivided) causes q to be subdivided (via one of the recursive
calls) then it's impossible for that chain to get back around to
try and subdivide p again, because each node will only cause the
subdivision of neighbors at a lower level so you'll have a
descending chain.  This also means that it's impossible for the
recursion to loop in any way; the subdivision of a node at level
5, say, will only recurse to try and subdivide neighbor nodes of
level 4, which will then only try to recursively subdivide
neighbors of level 3, etc.  Also, assuming that this procedure is
started from the base mesh and that that mesh has no T-vertices
(and that all the tris of the base mesh are considered to be at
level 0), then you'll never have two nodes more than one level
apart, so the tests in the code above don't have to be for >= but
just for ==.

Once you've completed your subdivision (and your radiosity
calculations) you may need to split a few triangles up for
rendering, but this is a lot easier: go through the leaves of
your tree looking for leaves that have neighbors at a higher
level.  If a leaf has one neighbor at a higher level, split it
along the bisector between that side and its opposite vertex:

[source]
      +
     /|\
    / | \
   /  |  \
  /   |   \
 +----+----+
[/source] 

If it has all of its neighbors at higher levels, then you can
split it into four triangles in the same way you do to subdivide.
The hardest case is if two of its neighbors are at higher levels;
in this case your best choice may be to introduce a new vertex
and split it into five triangles by drawing the line between the
two center points (of the edges it shares with higher-level
neighbors) and the lines from each of those points to the vertex
opposite, introducing a vertex where those two lines intersect.
Hopefully this will make sense out of it, * being the new vertex:

[source]
            +
           / \
          /   \
         /     \
        +-------+
       / \__ __/ \
      /    _*_    \
     /  __/   \__  \
    / _/         \_ \
   /_/             \_\
  +-------------------+