![[Figure 1]](bez.png)
![[UW shield]](http://www.uwaterloo.ca/images/UWlogo.GIF)
Triangular Bezier Patches are the 3-D analogue to Bezier curves, with the domain now representing a triangle. The de Casteljau algorithm is generalizable to the Bezier Patches, allowing for simple and stable evaluation. It is only natural then to look for a triangular equivalent to B-Splines. The current state of the art is DMS splines which provide the automatic continuity and local control properties that made their 2-D counterparts so attractive to use. However, no known coefficient-based evaluation scheme exists, and their evaluation requires the direct calculation of complex basis functions. The discovery of a coefficient-based Triangular B-Spline scheme could have very profound effects. The lure of solving this open problem and possibly devising the "Ingram Algorithm" was just too great to pass up.
With the tool, it is now possible to see how the control points must be placed to allow neighbouring Bezier patches to have G1 continuity (Figure 1). To see the entire control polygon, it is being viewed in wireframe mode. Click on the thumbnail to view the image at a larger size.
![[Figure 2]](bpatch.png)
This patch scheme represents the first step towards triangular B-Splines. At
each corner of the domain triangle, knots are shaken out of a Bezier patch into
a little knot cloud, very similar to what happens in the 2-D case.
For a degree n patch, there are n-1
additional knots at each corner. A de Boor style algorithm exists for
this scheme. If all the points in each knot cloud are coincident, then the
B-Patch reduces to a Bezier patch.
The next portion of the project was to convert the Bezier Patch visualizer to that of a B-Patch visualizer. In addition to the functionality from before, the user is given the domain knots in the bottom corner of the screen which can be moved freely. The user is also free to move the base knots, thus allowing neighbouring patches to have different sized domains. The knot clouds are shared between patches where applicable, much like the control points are shared.
So far, everything said about B-Patches is good, so what's the catch? In order to get neighbouring patches to meet with just C0 continuity, the knot clouds along the shared edge must be collinear (Figure 2). If we wanted to add a third patch to the mix, there is no where it could be placed without knot clouds collapsing to a single vertex. Thus, we need something more flexible to join our patches.
![[Figure 3]](simplex.png)
For this portion of my project I implemented a visualizer for simplex splines where the user is capable of adding knots to the domain and moving them around at will. The tessellation code simply samples the domain at uniform spacing and evaluates the spline for position and partial derivatives. An example of a cubic simplex spline over 6 knots is given (Figure 3). Anybody notice a similarity to the last homework problem!!!
Since the domain is uniformly sampled, discontinuities in the surface show up as artifacts with the tessellator attempting to connect them. I originally planned to triangulate the domain based on knot locations, but it turned out to be a much harder problem than I first anticipated. The underlying evaluator works fine, and that is what is needed for the next section, so it never got implemented.
![[Figure 4]](dms1.png)
However, the cost is worth the reward in the end. No matter where you move the control points, if the knot clouds are set up such that none of the underlying simplex splines have collinear points, then the patches will meet with Cn-1 continuity automatically. As with B-Patches, if all the points in the knot cloud are coincident, the patch reduces to a Bezier patch.
For this last portion of the project I converted the B-Patch visualizer to a DMS spline visualizer. The interface is virtually the same as before except that there is an additional knot in each knot cloud. The capability to only have one of the domain patches evaluated was added. The main reason for this was to more readily show the contribution that a second patch has on the other. An example of a single DMS spline patch is given (Figure 4). In Figure 5, the only difference is that the other patch is added (i.e. no camera, control point or knot movement) and you can see how the two patches now meet with the desired continuity along the shared edge. Due to the high cost of rendering a DMS spline, a high resolution option was added. Ideally, one would edit in the lower resolution, and then switch to the high resolution solely for viewing.
![[Figure 5]](dms2.png)
It is worth noting that numeric stability plagues the explicit evaluation of
DMS splines and simplex splines. In particular, when a point is on the
edge between two other points, numerical precision usually has the point fall
on one side of the edge or the other. This leads to a whole host of problems,
ranging from slight precision errors on the surface, to entirely missed
control point weighting. Fra95 covers this issue in great detail, but his
techniques make the evaluation vastly more complex. In my visualizer I only
implemented a couple of sleazy hacks that do a nice job to avoid the problem
instead of directly solving it.
With this being said, I don't believe that DMS splines in their current form will turn out to be the final story for triangular B-Splines. The main problem is that it is very tough to control each of the individual knot clouds to shape your overall surface. If one looks at uniform B-splines in the 2-D case, the knot vector essentially disappears. With DMS splines, there does not seem to be any way of accomplishing the same feat. Perhaps devising a uniform triangular B-Spline will hold the key to a more elegant solution (and that elusive Ingram Algorithm!!!).