1. Field of the Invention
The present invention generally relates to geometric processing in graphics systems and more specifically to a method for watertight evaluation of an approximate Catmull-Clark surface.
2. Description of the Related Art
Modern three-dimensional (3D) graphics systems are typically configured to generate one or more graphics images from one or more graphics scenes, with each graphics scene comprising one or more scene objects. The one or more graphics images are typically displayed or stored for display later. Each scene object is represented by a corresponding geometric model. Each geometric model may comprise a collection of abstract geometric objects such as triangles, patches, or meshes.
A subdivision surface is a type of geometric object described concisely by a coarse control mesh and a set of subdivision rules that specify how the control mesh may be refined into a more highly tessellated representation of a desired scene object. The control mesh may be recursively processed according to the subdivision rules to generate a limit surface that closely approximates a scene object or a portion of the scene object. The limit surface is typically represented as a set of abutting patches. In many applications, the limit surface needs to be constructed to enable a watertight tessellation, meaning a mesh of triangles that is tessellated from the limit surface to include no cracks, holes, or overlapping geometry. In a conventional graphics processing unit, each patch in the limit surface is tessellated into two or more triangles that represent a portion of the corresponding mesh of triangles. The mesh of triangles should be watertight because the mesh of triangles is typically used to render a corresponding scene object within an associated graphics image.
Catmull-Clark subdivision is a popular technique for achieving smooth-looking surfaces on scene objects comprising one or more subdivision surfaces. According to the Catmull-Clark subdivision technique, a well-known set of subdivision rules are applied recursively to a coarse control mesh to produce a progressively more detailed and smooth subdivision mesh. After an infinite number of subdivision steps, an initial surface specified by the control mesh converges to a “limit surface.” A limited number of subdivision steps (i.e., non-infinite), however, produces a reasonable approximation of the limit surface. For the purpose of discussion herein, a “limit surface” refers to an approximate limit surface generated using a finite number of subdivision steps, and in particular an approximate Catmull-Clark surface.
A portion of the limit surface corresponding to a given patch is specified by control points for the patch. In order to form a watertight boundary between two abutting patches, the boundary must be parametrically continuous in position (C0). Since control points are specified and evaluated with finite precision (normally using 32-bit floating point values) independently for each patch, a boundary between two abutting patches may be computed slightly differently for each of the two abutting patches, resulting in visible holes in an associated scene object. Scenarios where logically identical vertices and control points are actually not bit-wise identical may result in non-C0 boundaries with holes between two patches. Such scenarios are common and may materially degrade image quality in rendered graphics images.
Accordingly, what is needed in the art is a technique for watertight approximation of limit surfaces for adjacent patches.