PN Patches

Gerald Farin

March 11, 2003

A recent use of triangular Bézier patches is in computer graphics, where they are used for rendering triangle meshes, see [3], [2], [1]. Suppose you have a relatively coarse triangle mesh, such that even with Gouraud or Phong shading you will not get a nice looking object. Suppose further that you have a normal defined at every vertex.

The goal is to build a cubic Bézier patch over each triangle, such that the resulting collection of Bézier triangles forms a continuous surfaces. This surface will not be G^{1}, however. This defect will be overcome by a display trick, explained below.

Let us concentrate on one triangular facet. It has three vertices, which we denote by b_{300}, b_{030}, b_{003}. At each of these vertices, we also have a normal, and we denote them by n_{200}, n_{020}, n_{002} – this notation will be explained shortly. Our desired Bézier patch needs three boundary curves; let’s concentrate on the one from b_{300} to b_{030}. We need Bézier points b_{210} and b_{120} in order to have a boundary control polygon. They are found by using a point/normal interpolation algorithm. In order to find b_{210}, we define b′_{210} = (2b_{300} +b_{030})/3. Then we project b′_{210} into the plane defined by point b_{300} and normal n_{200} and obtain

b_{210} = b′_{210} − \frac{1}{3}(n_{200}[b_{030} − b_{300}])n_{200}.

This process is illustrated in Figure 1 and repeated for b_{120}.

We repeat for the remaining two boundaries. One control point is still undetermined, namely b_{111}. We determine it from

b_{111} = \frac{1}{4} ∑_{0jk,i0k,0jk} b_{ijk} − \frac{1}{6}[b_{300} + b_{030} + b_{003}].

At this point, we have built a cubic patch over each triangular facet. The resulting overall surface will not be smooth, for the reasons outlined in Section 18.4. The trick now is to modify the display algorithm such that it looks smooth.

Figure 1: PN patches: left, input data. Right: boundary control polygons.

When we render a surface, we need to break it down into an appropriate number of triangular facets, compute the normals at the vertices, and feed all to the shader. For a Bézier triangle, this is done by 1. running the de Casteljau algorithm for each vertex and 2. extracting the surface normal from it. For PN patches, these two processes are separated. The point evaluation is as usual, but the normal is computed differently. In fact, it is not the true surface normal but rather one that “looks better”.

A display normal d(u) will be computed from

d(u) = ∑_{|i|=n=2} B_{i}^{2}(u)d_{i}.  (1)

The six display control normals d_{i} are found as follows:

d_{200} = n_{200}, d_{020} = n_{020}, d_{002} = n_{002}.

The three remaining ones are not that simple. Concentrating on the edge u_{3} = 0, and the display normal d_{1/2} at (\frac{1}{2}, \frac{1}{2}, 0), we might set

d_{1/2} = \frac{1}{2}d_{200} + \frac{1}{2}d_{020}

and normalize to get a unit normal. This choice, however, would give an undesirable normal if d_{200} and d_{020} were close to being equal, meaning that the corresponding boundary curve has an inflection point. See Figure 2

A better choice was found to be constructing a plane perpendicular to \overline{b_{300}, b_{030}} and reflecting the above d_{1/2} across this plane for the final display normal value of d_{1/2}. This gives

d_{1/2} = d_{200} + d_{020} − 2\frac{(b_{030} − b_{300})(d_{200} + d_{020})}{∥b_{030} − b_{300}∥^{2}}(b_{030} − b_{300}).  (2)

Figure 2: PN normals: left, simple averaging. Right, averaging followed by reflection.

The display normal d_{110} is then defined to equal d_{1/2}.

With this arrangements of display control normals, we are guaranteed continuous normals along common boundary curves between patches. While the resulting display is not accurate, it is smooth – which is what matters if good looks for rendering is important!

An improvement over (2) is as follows. The assignment

d_{110} = d_{1/2}

does not guarantee that d(\frac{1}{2}, \frac{1}{2}, 0) = d_{1/2}. In order to achieve this, we need to set

d_{110} = \frac{3}{2}d_{1/2} − \frac{1}{4}d_{200} − \frac{1}{4}d_{020}.  (3)

References

[1] Y-C Lee and C-W Jen. Improved quadratic normal vector interpolation for realistic shading. The Visual Computer, 17(6):337–352, 2001.

[2] C. van Overveld and B. Wyvill. An algorithm for polygon subdivision based on vertex normals. In Computer Graphics International ’97, pages 3–12, 1997.

[3] A. Vlachos, J. Peters, C. Boyd, and J. Mitchell. Curved PN triangles. In ACM Symposium on Interactive 3D Graphics 2001, pages 159–166, 2001.