[Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)

[Charles B. <cb...@cb...>]

Well, ATI's posted this on their website, so I guess we
can talk about it freely now.

http://www.ati.com/na/pages/resource_centre/dev_rel/devrel.html

I don't give a hoot about the DX8 implementation of this, I
want to talk about the algorithm of making a curved triangle
only using its vertices and normals.  I worked on this for
a while, and decided it wasn't such a hot thing to do, because
you can't even guarantee G1 continuity, so I abandonded
it and moved on to butterfly subdivision, where continuity 
can be gauranteed.

So, first of all, I remember hearing that this heuristic was
invented by the wise Charles Loop.  Is that correct?  Are there
any papers on this?  I imagine there aren't, because it's a 
little trick that's not exactly up to Pixar quality standards.

BTW you can see easily the problems with this scheme.  Each
triangle is made into a cubic Bezier Triangle.  There are two
new control points associated with each original vertex, and
one in the middle.  The two control points at each vertex
are made to lie on the plane defined by the vertex and its
normal.  This gaurantees that the final Bezier surface is
tangent to that same plane at that vertex, thereby giving
you G1 (but actually not C1, if you want to be nit-picky)
at that vertex.  However, at every other point on the triangle,
G1 is in trouble.  Let me try to draw a little picture :

    a
   /|\
  / | \
 /  |  \
b---c---d

So we have two neighboring triangles,  abc and acd.
At the points a and c, they smoothly meet after Bezier
tesselation.  However, everywhere else along the edge ac
they are not G1 in general, because the slope coming
into the edge ac from triangle acd depends on the point
d, and the slope coming in from triangle abc depends on
the point b, so that you can't have G1 unless b and d
are related in some very restrictive way.  

To get G1, you need to go to Quartic Bezier Triangles,
and you need to find the control points of each triangle
by looking at its neighbors.  See, for example, Charles
Loop's papers on finding the Quartic Bezier Triangles
that are equivalent to Catmull-Clark subdivision (in
Siggraph).

I can see why hardware manufacturers like this scheme,
because it is totally per-triangle (eg. you don't need
any connectivity information).  However, we are much
smarter, and we know how are triangles are connected,
so we can use the fast subdivision tesselation scheme
of Kari Pulli (for example), or we can use Tom's
subdivision + displacement + VIPM technique.  (I'm
imagining for the moment that I don't have a GPU that
can do these Patches in hardware, so I would have to
implement them in software, obviously they are cool/free
when the hardware does them for you).

--------------------------------------
Charles Bloom           www.cbloom.com