i
i
i
i
i
i
i
i
600 13. Curves and Curved Surfaces
Figure 13.21. The columns show different levels of detail of the same model. The original
triangle data, consisting of 414 triangles, is shown on the left. The middle model has
3,726 triangles, while the right has 20,286 triangles, all generated with the presented
algorithm. Note how the silhouette and the shading improve. The bottom rows show
the models in wireframe, which reveals that each original triangle generates the same
amount of subtriangles. (Model courtesy of id Software. Images from ATI Technologies
Inc. demo.)
to create a cubic B´ezier triangle for each original triangle, and generate as
many triangles as we wish from the B´ezier triangle.
To shorten notation, w =1−u−v will be used. A cubic B´ezier triangle
(see Figure 13.19) is given by
p(u, v)=
i+j+k=3
B
3
ijk
(u, v)p
ijk
= u
3
p
300
+ v
3
p
030
+ w
3
p
003
+3u
2
vp
210
+3u
2
wp
201
+3uv
2
p
120
+3v
2
wp
021
+3vw
2
p
012
+3uw
2
p
102
+6uvwp
111
.
(13.37)
To ensure C
0
continuity at the borders between two N-patch triangles,
the control points on the edge can be determined from the corner con-
trol points and the normals at the respective control point (assuming that
i
i
i
i
i
i
i
i
13.2. Parametric Curved Surfaces 601
Figure 13.22. How the B´ezier point p
210
is computed using the normal n
200
at p
300
,
and the two corner points p
300
and p
030
.
normals are shared between adjacent triangles). Also, to get reasonable
behavior of the surface at the control points, the normals there should be
normals of the surface in Equation 13.37. Therefore, the following strategy
is adopted to compute the six different control points for the borders.
Say that we want to compute p
210
using the control points p
300
, p
030
and the normal n
200
at p
300
, as illustrated in Figure 13.22. Simply take
the point
2
3
p
300
+
1
3
p
030
and project it in the direction of the normal, p
200
,
onto the tangent plane defined by p
300
and n
200
[331, 332, 1304]. Assuming
normalized normals, the point p
210
is computed as
p
210
=
1
3
(2p
300
+ p
030
− (n
200
· (p
030
− p
300
))n
200
) . (13.38)
The other border control points can be computed similarly, so it only
remains to compute the interior control point, p
111
. Thisisdoneasshown
in Equation 13.39, and this choice follows a quadratic polynomial [331, 332]:
p
111
=
1
4
(p
210
+p
120
+p
102
+p
201
+p
021
+p
012
)−
1
6
(p
300
+p
030
+p
003
). (13.39)
Instead of using Equation 13.36 to compute the two tangents on the
surface, and subsequently the normal, Vlachos et al. [1304] choose to inter-
polate the normal using a quadratic scheme, as shown below:
n(u, v)=
i+j+k=2
B
2
ijk
(u, v)n
ijk
= u
2
n
200
+ v
2
n
020
+ w
2
n
002
+ uvn
110
+ uwn
101
+ vwn
011
.
(13.40)
This can be thought of as a B´ezier triangle of degree two, where the
control points are six different normals. In Equation 13.40, the choice
of the degree, i.e., quadratic, is quite natural, since the derivatives are
i
i
i
i
i
i
i
i
602 13. Curves and Curved Surfaces
Figure 13.23. This figure illustrates why quadratic interpolation of normals is needed,
and why linear interpolation is not sufficient. The left column shows what happens
when linear interpolation of normals is used. This works fine when the normals describe
a convex surface (top), but breaks down when the surface has an inflection (bottom).
The right column illustrates quadratic interpolation. (Illustration after van Overveld
and Wyvill [1297].)
of one degree lower than the actual B´ezier triangle, and because linear
interpolation of the normals cannot describe an inflection. See Figure 13.23.
To be able to use Equation 13.40, the normal control points n
110
, n
101
,
and n
011
need to be computed. One intuitive, but flawed, solution is to
use the average of n
200
and n
020
(normals at the vertices of the original
triangle) to compute n
110
. However, when n
200
= n
020
, then the problem
shown at the lower left in Figure 13.23 will once again be encountered.
Instead, n
110
is constructed by taking the average of n
200
and n
020
.Then
this normal is reflected in the plane π, which is shown in Figure 13.24.
This plane has a normal parallel to the difference between the endpoints
p
300
and p
030
. The plane π is passing through the origin, since direction
vectors are reflected, and these are independent of the position on the
plane. Also, note that each normal should be normalized. Mathematically,
Figure 13.24. Construction of n
110
for N-patches. The dashed normal is the average
of n
200
and n
020
,andn
110
is this normal reflected in the plane π. The plane π has a
normal that is parallel to p
030
− p
300
.
i
i
i
i
i
i
i
i
13.2. Parametric Curved Surfaces 603
the unnormalized version of n
110
is expressed as [1304]
n
110
= n
200
+ n
020
−2
(p
030
− p
300
) · (n
200
+ n
020
)
(p
030
− p
300
) · (p
030
− p
300
)
(p
030
−p
300
). (13.41)
Originally, van Overveld and Wyvill used a factor of 3/2 instead of the 2 in
this equation. Which value is best is hard to judge from looking at images,
but using 2 gives the nice interpretation of a true reflection in the plane.
At this point, all B´ezier points of the cubic B´ezier triangle and all the
normal vectors for quadratic interpolation have been computed. It only
remains to create triangles on the B´ezier triangle so these can be rendered.
Advantages of this approach are that the surface gets a better silhouette
and shape relatively cheaply, and that only minor modifications must be
made to existing code to make it work. All that is needed is that tessellation
should be done (instead of rendering as usual), down to some level of detail
(LOD). A hardware implementation is pretty straightforward.
One way to specify LODs is the following. The original triangle data
is LOD 0. The LOD number then increases with the number of newly
introduced vertices on a triangle edge. So LOD 1 introduces one new ver-
tex per edge, and so creates four subtriangles on the B´ezier triangle, and
LOD 2 introduces two new vertices per edge, generating nine triangles. In
general, LOD n generates (n +1)
2
triangles. To prevent cracking between
B´ezier triangles, each triangle in the mesh must be tessellated with the
same LOD. This is a big disadvantage, since a tiny triangle will be tessel-
lated as much as a large triangle. Techniques such as adaptive tessellation
(Section 13.6.4) and fractional tessellation (Section 13.6.2) can be used to
avoid these problems, and these are getting more and more widespread
support.
One problem with N-patches is that creases are hard to control, and
often one needs to insert extra triangles near the desired crease. The con-
tinuity between B´ezier triangles is only C
0
, but they still look acceptable
in many cases. This is mainly because the normals are continuous across
triangles, so that a set of N-patches mimics a G
1
surface. A better solution
is suggested by Boubekeur et al. [131], where a vertex can have two nor-
mals, and two such connected vertices generate a crease. Note that to get
good-looking texturing, C
1
continuity is required across borders between
triangles (or patches). Also worth knowing is that cracks will appear if
two adjacent triangles do not share the same normals. A technique to fur-
ther improve the quality of the continuity across N-patches is described by
Gr¨un [462]. Dyken and Reimers [289] present a technique inspired by N-
patches, where only the silhouettes as seen from the viewer are tessellated,
and hence, the silhouettes become more curved. These silhouette curves are
derived in similar ways as the N-patches curves. To get smooth transitions,
they blend between coarse silhouettes and tessellated silhouettes.
i
i
i
i
i
i
i
i
604 13. Curves and Curved Surfaces
13.2.4 Continuity
When constructing an interesting object from B´ezier surfaces, one often
wants to stitch together several different B´ezier surfaces to form one com-
posite surface. To get a good-looking result, care must be taken to ensure
that reasonable continuity is obtained across the surfaces. This is in the
same spirit as for curves, in Section 13.1.3.
Assume two bicubic B´ezier patches should be pieced together. These
have 4 × 4 control points each. This is illustrated in Figure 13.25, where
the left patch has control points, a
ij
, and the right has control points, b
ij
,
for 0 ≤ i, j ≤ 3. To ensure C
0
continuity, the patches must share the same
control points at the border, that is, a
3j
= b
0j
.
However, this is not sufficient to get a nice looking composite surface.
Instead, a simple technique will be presented that gives C
1
continuity [332].
To achieve this we must constrain the position of the two rows of control
points closest to the shared control points. These rows are a
2j
and b
1j
.
For each j,thepointsa
2j
, b
0j
,andb
1j
must be collinear, that is, they
must lie on a line. Moreover, they must have the same ratio, which means
that ||a
2j
−b
0j
|| = k||b
0j
−b
1j
||. Here, k is a constant, and it must be the
same for all j. Examples are shown in Figure 13.25 and 13.26.
This sort of construction uses up many degrees of freedom of setting the
control points. This can be seen even more clearly when stitching together
four patches, sharing one common corner. The construction is visualized
in Figure 13.27. The result is shown to the right in this figure, where the
locations of the eight control points around the shared control point are
shown. These nine points must all lie in the same plane, and they must
form a bilinear patch, as shown in Figure 13.14. If one is satisfied with
Figure 13.25. How to stitch together two B´ezier patches with C
1
continuity. All control
points on bold lines must be collinear, and they must have the same ratio between the
two segment lengths. Note that a
3j
= b
0j
to get a shared boundary between patches.
This can also be seen to the right in Figure 13.26.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.