This
paper discusses the terrain system used in SSX. An algorithm for
the tessellation of polynomial surfaces is presented. The system allows
for adaptive tessellation with continuous levelofdetail while avoiding
the introduction of cracks and seams between adjacent surfaces with different
geometric resolution. The Surface lighting on the terrain is discussed.
Introduction
A high order parametric surface representation is chosen for representing
the terrain in the SSX snowboarding game. The reasoning behind
this decision is to represent the snow surface with an elegant and concise
mathematical representation for physics calculations, and to allow for
an arbitrary polygonal resolution for rendering the terrain while insuring
a small memory footprint for the surface information.
Bézier
patches are chosen for their fast run time evaluation, affine invariance,
and convex hull property (for quick occlusion and intersection tests).
The terrain is represented as a grid of Bicubic Bézier surfaces.
Each Bicubic Bézier surface or patch is defined by a set of control
points. From these control points we can generate any point on the surface.
We tessellate the patch by connecting a grid of evaluated surface points
into triangles or triangle strips. The polygon primitives can then be
rendered by conventional 3D hardware. We can tessellate the patch to an
arbitrary resolution at run time. In order to achieve a high quality image
with reasonable performance it is desirable to evaluate the patches at
different resolutions. A heuristic is required for determining what resolution
a patch should be evaluated at. For this implementation a simple distance
based Level of Detail heuristic is used. Evaluating neighbouring patches
at different LOD will introduce ugly gaps in the rendered surface. Special
transition patches are generated to solve this problem.
Traditional polygonal lighting models require a vertexnormal pair in order to generate a colour for each vertex. The graphics hardware interpolates the vertex colours over the polygon surface. With dynamic evaluation of a parametric surface the number of vertices and their position will be changing. As a result a dynamically tessellated vertexnormal lighting system will tend to pop and move which will detract from the quality of the moving image. In order to avoid this one must decouple the geometric resolution from the light sample resolution. We use lightmaps. Light maps encode lighting as 2D textures. At run time the light map texture is modulated with a surface texture of each polygon to create the final image. With this method the surface lighting does not pop when the geometric resolution changes. We also have the added benefit of calculating the lighting offline using whatever lighting model we like. The trade off is we lose the ability to dynamically change the surface lighting without recalculating light maps at run time.
Background
A parametric curve defined in three dimensions is given by three univariate functions:
As u varies from 0 to 1 the functions sweep out the curve. Similarly
a parametric surface is defined by three bivariate functions:
As we vary u from 0 to 1 and we hold v constant we sweep out a curve in threespace. An infinity of such curves exists as we vary v from 0 to 1 and this defines the surface in three dimensions.
A Parametric curve is usually a polynomial:
Computer graphics generally stick to a degree of 3 that is cubic. For degrees greater then 3 there is a trade off between curve flexibility and descriptions that are more cumbersome to work with. The cubic form looks like this:
The relationship between the shape of the curve and the coefficients p_{i}
are not very intuitive. Instead of having to manipulate the coefficients
directly, the polynomial form can be rearranged into control points and
basis functions, which provide a more intuitive connection to the shape
of the curve:
The coordinates p_{i} are called control points and the
power basis is b_{i}(u). The cubic basis is a collection
of linearly independent polynomial b_{i}(u) given by:
For equation 2 the control points are (p^{0}, p^{1}, p^{2}, and p^{3}) and the basis polynomial are (1, u, u^{2} and u^{3}).
A bicubic parametric surface has the form of equation 3 and is traced out as the parameters (u,v) take all possible values between 0 and 1. This is known as a patch. Free form surfaces are modelled using nets of patches. Bicubic parametric patches are defined over a rectangular domain in uvspace and the boundary curves of the patch are themselves cubic polynomial curves. A point Q with the coordinates (x,y,z) in Cartesian space is represented by the parameters (u,v) in parametric space. Using the same control point and basis function representation we define the patch as:
Where p_{ij} is a set of 16 control points:
p_{00} p_{01} p_{02} p_{03}
p_{10} p_{11} p_{12} p_{13}
p_{20} p_{21} p_{22} p_{23}
p_{30} p_{31} p_{32} p_{33}
The net
of control points forms a polyhedron in Cartesian space and the position
of the points in this space controls the shape of the surface.
The basis used for rendering the patches in SSX is the Bézier
basis. The Bézier basis polynomial are called Bernstein polynomials
and are defined by:
where:
For a cubic Bézier curve the basis functions are:
These curves show the influence that each control point has on the final
curve form.
When u=0 the basis function B_{0,3} = 1 while the
others are 0. When u=1 the basis function B_{3,3}
= 1 while the others are 0. From this we know that when u=0,
p_{0} will have the most influence and when u=1, p_{3}
will have the most influence. The control points p_{1}
and p_{2} have the most effect when u=1/3 and u=2/3
respectively. The manner in which the basis functions affect the shape
of the curve is the reason they are called blending functions. An alternate
convention for specifying a Bézier curve is the matrix convention:
The Bézier patch is defined in matrix notation by:
This matrix form is what is used in SSX. Figure 1 shows the control
net P_{c} of 16 control points that is needed to describe
a single patch. The transpose of Bézier matrix M_{B}^{T}
has the same form as M_{B}. If we assume that the control
matrix P_{C} does not change then we can premultiply these
to get:



Figure 1: Control polyhedron (left) and resulting bicubic Bézier patch (right) 
Level of Detail System
To create an image that most accurately represents the terrain surface as described by the artist we want to evaluate the curved surfaces to a high level of detail. If all patches are tessellated to the same degree then we will generate just as much polygonal detail for far away patches as we do for close up patches. The total number of polygons that the hardware is required to render in most cases will limit us to a lower geometric resolution than we would like. With an LOD system we render polygon detail only where it is required. The results are near identical quality with fewer polygons to render. Unfortunately if all patches are not evaluated to the same degree, seams and "tearing" will be seen between the patches. The result is quite unacceptable for the quality expected of modern video games. The goal is to tessellate patches to different degrees without generating seems.
The algorithm presented here ensures that no tears or seams are created between neighbouring patches with different tessellation levels. The only constraint is that patches must have at least C^{0} continuity with their neighbours. C^{0} continuity requires that neighbouring patches share control points along the boundary connecting them. Note that C^{1} continuity is required for smooth lighting and physics calculations between patches but is not required for the LOD algorithm to work.
With these constraints in place the run time evaluation of the terrain will not need to be aware of neighbouring information to produce a seamless tessellation of the entire terrain with changing LOD. Most other algorithms that fix the "cracking" problem require neighbour information and usually a second pass in order to correct errors. The evaluation of the Bézier polynomial can be performed using various methods depending on the implementer's preference. There are many methods of evaluating equation 4 such as direct evaluation, forward differencing, and recursive subdivision. The evaluation method chosen to implement this system is not important.
A run time heuristic is used to determine the tessellation level of each of the four boundary curves of the Bézier patch. If each boundary curve requires the same level, then the entire patch is uniformly tessellated to the same degree. If the 4 boundary levels differ, then a nonuniform patch is generated. The number of edge vertices generated is directly a function of the boundary edge heuristic. As such the number of vertices on the boundary of two patches is always the same so long as C^{0} edge continuity exists. The "cracking" problem is reduced to ensuring that a nonuniform patch does not create any inner cracks or seems while retaining the number of edge vertices as determined by the boundary heuristic.
A nonuniform patch is treated as a uniform inner patch connected to the edge vertices with 4 triangle strips. Let the number of points per edge be specified clockwise as E0, E1, E2, and E3 respectively. The resolution of the inner patch is then defined as NxM where N = max(E0,E2)2 and M = max(E1,E3)2. This choice for NxM conservatively rounds up the degree of the inner patch to highest boundary degree both vertically and horizontally. The 4 strips generated are created from boundary edge vertices and the perimeter inner mesh vertices. S0=strip(E0,Nl), S1=strip(E1,Mt), S2=strip(E2,Nr), S3=strip(E3,Mb). See Figure 2.



Figure 2: Nonuniform mesh evaluation 
The LOD
heuristic is chosen as a function of distance from the camera position
C_{pos}. A minimum LOD_{min} and maximum
LOD_{max} boundary evaluation is chosen. A distance from
the camera for minimum Dist_{near} and maximum Dist_{far}
level of detail is chosen. Only the end control points of each edge p_{0}
and p_{1} are used to determine the degree evaluation.
For speed the dist function is actually chosen as the squared distance
as apposed to the square root. For a visible distance of 500 meters the
near distance would be something like 25 meters and the far lets say 250
meters. All boundary edges at 25 meters or closer will have maximum detail.
All boundary edges at 250 meters or farther will be minimum level of detail.
If we choose a good distance range relative to average patch edge length
and only a few different LOD levels then most patches will be uniformly
tessellated with nonuniform patches existing as a row of patches connecting
different uniform levels of detail at a fixed radius to the camera.
More exotic heuristics can be chosen that take into account things like edge or patch curvature, however one must be careful to ensure that the heuristic exhibits good hysteresis so that patches do not fluctuate between different LODs giving away the effect.
Conclusions and Future work
The terrain system discussed in this paper has been implemented in SSX, and SSX Tricky. The system stores only patch control information requiring a much smaller memory footprint over vertex geometry. Through dynamic level of detail the number of polygons rendered by the graphics hardware is reduced without noticeable quality loss. The system does not introduce seams between patches of different tessellation levels by ensuring identical edge tessellation on boundaries between patches that maintain C0 continuity. Neighbouring information is not required at run time in order to avoid LOD seems.
For terrain
systems that have limited memory storage (especially video game consoles)
but still require large environments and high geometric detail, Bézier
patches provide very good compression. The cost of rendering terrain geometry
at constant resolution is more expensive than necessary and does not scale
well to lower powered graphics hardware. The system presented here attempts
to decrease the memory and polygon costs of rendering a complex terrain.
With the addition of a patch caching system the performance of this terrain
architecture would scale nicely across lower powered machines.













For Further Information
Michael E. Mortenson, Geometric Modelling Second edition. Wiley Computer Publishing, 1997
Watt & Watt, Advanced Animation and Rendering Techniques Theory and Practice. AddisonWesley, ACM Press. 1992
Foley, vanDam, Feiner, and Hughes, Computer Graphics: Principles and Practice. Second Edition. AddisonWesley Publishing, 1990