MCIS 625: Computer Graphics
Winter 2004
WEEK 7
Instructor: Dr. Michael Laszlo
Assignment
Surface Modeling
Three-dimensional modeling techniques can be broadly classified into surface
modeling and solid modeling. To represent a geometric solid using
surface modeling, we represent only the solid's surface. The solid's interior
is represented only implicitly, as the region bounded by its surface. If the
solid is well-behaved, then its boundary is a surface in the mathematical sense:
around every point on the surface there exists a small disk-shaped neighborhood.
For example, the boundary of a ball is a sphere, and the boundary of a donut
is a torus. If the solid is less well-behaved, then so is its boundary. For
example, the boundary of two cones that intersect only at the apex of each—at
a single point—is not a mathematical surface, although it can be
represented within the computer. Solid modeling can also be used to represent
"free-floating" surfaces that are not the boundary of any solid, such as flags
or fabrics. Such surfaces are known as sheets or lamina.
Perhaps the most common technique for surface modeling uses the polygon mesh, a collection of polygons such that each polygon edge is shared by at most two polygons. Polygon meshes are easy to represent and manipulate. In a common representation, each vertex is assigned a position in space and a unique index. The index is used to refer to the vertex. Each polygon in the mesh is specified by an ordered sequence of vertex indexes. This is the approach taken, in fact, by VRML's IndexedFaceSet node type.
Polygon meshes are very general in that they can be used to approximate any surface as closely as desired by making the mesh resolution increasingly fine—that is, decreasing the size of the polygons. The polygons are usually triangles because triangles admit a uniform representation, and because triangles are necessarily coplanar (a triangle lies in the unique plane determined by its vertices). Nonetheless, some modeling systems also allow quadrilaterals (4-sided polygons) and polygons with even more sides. Note that the IndexedFaceSet node type in VRML enables the construction of meshes whose polygons have any number of sides, and the ElevationGrid node builds meshes of quadrilaterals.
Polygon meshes use a considerable amount of memory, since each of the polygons that comprise a mesh is represented explicitly. Models of commonplace objects such as cars, toothbrushes, planes, and human bodies, can be composed of hundreds of thousands and even millions of polygons. Nonetheless, there are two ways in which the memory consumed by mesh representations can be decreased. First, the mesh's resolution can be responsive to the local curvature of the target surface. This means that the mesh may be fine in regions of high curvature, yet coarse in regions of low curvature. Where the target surface is relatively flat (of low curvature), the mesh polygons are large and relatively little memory is used. Second, for computer graphics, only a rough approximation to the target surface is generally sufficient (a close approximation is usually overkill). A rough approximation suffices because shading methods can be applied which "smooth" the appearance of the mesh, making it appear to exactly match the target surface. Afterall, computer graphics is concerned more with appearance than with reality!
Polygon meshes are a special case of parametric patches, which are mathematically-described surfaces. Each patch maps two real parameters u and v into space. As u and v range over [0,1], the mapping describes a (generally curved) surface in space. A set of parametric patches can be connected by the same rules by which polygons are combined to form a polygon mesh. A set of parametric patches generally uses much less memory than a similar polygon mesh, since a single patch may approximate a region as accurately as a polygon mesh comprised of tens or even hundreds of polygons. On the other hand, polygon meshes can be rendered more efficiently than parametric patches. One technique for rendering a parametric patch constructs an approximating polygon mesh, which it then directly renders.
Solid Modeling
In contrast to surface modeling, solid modeling represents the entire
volume contained by a target solid, this volume being the union of the solid's
interior and boundary. Constructive solid geometry (CSG) is a
particularly powerful and widely-used solid modeling technique. A CSG model
consists of a tree (known as a CSG tree) whose leaf nodes correspond
to primitive solids such as spheres, pyramids, cylinders, ruled cylinders, and
wedges, and whose internal nodes correspond to Boolean set operations such as
union, intersection, and difference. The solid represented by an internal node
is formed by applying the node's Boolean set operation to the solid represented
by its children. For example, the solid represented by a union node is
the union of the solids represented by the node's two children.
Another solid modeling method is extrusion, whereby a planar source surface (or source curve) is swept along a sweep path in space. The solid defined thus is the set of points in space through which the source surface passes. Sweeping a disk along a straightline path produces a cylinder; sweeping a circle along a second perpendicular circle produces a torus. In VRML, extrusions are built using Extrusion nodes. Extrusion can be made very general by defining a transformation that is parameterized by the sweep path's parameter—as the source surface is swept, it is transformed by the current transformation. A simple example is sweeping a disk along a straight line while varying the circle's radius, the result of which is a cylinder of varying radius, a "worm" of sorts.
The octree is a solid modeling method whereby a cube of space is recursively subdivided into octant subcubes. The subdivision process continues until every subcube is homogeneous—the subcube is either entirely contained by the target solid, or it is entirely external to the target solid. Octrees have many uses besides solid modeling; later in this course, we will see how they are used to accelerate ray tracing.
Chapters 9 and 10 of our text, as well as this week's slide set, cover these and other modeling techniques in greater detail.