Graphics accelerators are just beginning to include support for curved surfaces as basic primitives. A problem with these early implementations is a lack of generality. For example, the shadow volume method needs to use the silhouette edge of a model in order to generate projected quadrilaterals. Computing such silhouette edges from the curved surfaces currently has to be done on the software side. Even with such limitations, the potential quality and speed improvements offered by curved surface descriptions makes them useful today, and future graphics hardware promises to be more powerful and flexible.
The advantage of using curved surfaces is at least fourfold: (1) they have a more compact representation than a set of polygons, (2) they provide scalable geometric primitives, (3) they provide smoother and more continuous primitives than planar polygons, and (4) animation and collision detection may become simpler and faster.
There are a number of advantages of a compact curve representation for real-time rendering. First, there is a savings in memory for model storage (and so some gain in memory cache efficiency). This is especially useful for game consoles, which typically have little memory compared to a PC. Transforming curved surfaces generally involves fewer matrix multiplications than transforming a mesh representing the surface. If the graphics hardware can accept such curved surface descriptions directly, the amount of data the host CPU has to send to the graphics hardware is usually much less than sending a polygon mesh.
An N-patch is a triangular Bézier surface, which can replace each triangle in a triangle mesh. N-patches have the interesting property that a model with few polygons can be made more convincing and realistic. The individual polygons are treated as curved surfaces, so creating more vertices on the surface. The result of a higher vertex density is better lighting of the surface and more realistic silhouette edges.
This article starts with a brief description of Bézier triangles. Bézier triangles form the basis for N-patches, which are discussed in more detail in the rest of the article.
Bézier Triangles
Even though the triangle often is considered a simpler geometric primitive than the rectangle, this is not the case when it comes to Bézier surfaces: Bézier triangles are not as straightforward as Bézier patches. However, because Bézier triangles are used in forming N-patches, we first discuss these.
The control points are located in a triangular grid, as shown in Figure 1.
Figure 1. The control points of a Bézier triangle with degree three (cubic). |
The degree of the Bézier triangle is n, and this implies that there are n+1 control points per side. These control points are denoted p^{0}_{i,j,k} and sometimes abbreviated to p_{i,j,k}. Note that i+j+k=n, and i,j,k >= 0 for all control points. Thus, the total number of control points is
It should come as no surprise that Bézier triangles also are based on repeated interpolation. However, due to the triangular shape of the domain, barycentric coordinates must be used for the interpolation. Recall that a point within a triangle Δp_{0}p_{1}p_{2}, can be described as
p(u,v) = p_{0} + u(p_{1}-p_{0}) + v(p_{2}-p_{0}) = (1-u-v)p_{0 }+ up_{1} + vp_{2},
where (u,v) are the barycentric coordinates. For points inside the triangle the following must hold: u>=0, v>=0, and 1-u+v>=0 (alternately, u+v<=1). Based on this, the de Casteljau algorithm for Bézier triangles is:
de Casteljau [triangles]:
The final point on the Bézier triangle at (u,v) is p^{n}_{000}(u,v). The Bézier triangle in Bernstein form is:
Bernstein [triangles]:
The Bernstein polynomials now depend on both u and v, and are therefore computed differently, as shown below:
When any of the following is true: i,j,k<0 and i,j,k>n, the Bernstein polynomial is set to zero; B^{n}_{ijk}(u,v)=0. The partial derivatives are [1]:
Derivatives [triangles]:
Some unsurprising properties of Bézier triangles are that they interpolate (pass through) the three corner control points, and that each boundary is a Bézier curve described by the control points on that boundary. Also, the surfaces lies in the convex hull of the control points. Finally, rotating the control points and then generating points on the Bézier triangle is the same as generating points on the Bézier triangle and then rotating these. A Bézier triangle is shown in Figure 2.
Figure 2. Top: wireframe of a Bézier triangle. Bottom: Shaded surface together with control points. |
Next, we will discuss a direct application of Bézier triangles.