Features

Dynamic Level of Detail Terrain Rendering with Bézier Patches

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 level-of-detail 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 Bi-cubic Bézier surfaces.

Each Bi-cubic 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 vertex-normal 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 vertex-normal 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 light-maps. 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 off-line 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 three-space. 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 co-ordinates 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⁰, p¹, p², and p³) and the basis polynomial are (1, u, u² and u³).

A bi-cubic 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. Bi-cubic parametric patches are defined over a rectangular domain in uv-space and the boundary curves of the patch are themselves cubic polynomial curves. A point Q with the co-ordinates (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₀₀ p₀₁ p₀₂ p₀₃
p₁₀ p₁₁ p₁₂ p₁₃
p₂₀ p₂₁ p₂₂ p₂₃
p₃₀ p₃₁ p₃₂ p₃₃

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₀ will have the most influence and when u=1, p₃ will have the most influence. The control points p₁ and p₂ 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 pre-multiply these to get:

	Figure 1: Control polyhedron (left) and resulting bi-cubic Bézier patch (right)

______________________________________________________

Level of Detail System

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service