Chapter 8
Three-Dimensional Object
Representations
This chapter examines the methods that have been devised to describe and visualize various
kinds of objects and data sets. In addition, programming projects explore the application of
OpenGL functions for different representations, as well as the implementation details involved
in the algorithms for generating displays of splines, fractals, and other objects.
Exercises
8-1. Input for this algorithm is the sphere radius, assuming that the sphere is centered at the
coordinate origin. A polygon-mesh representation can be constructed using longitude and
latitude lines to obtain vertex positions. Thus, two additional input parameters could
be provided to specify the number of latitude and longitude lines that are to be used in
subdividing the sphere surface.
The parametric equations for either a longitude line or a latitude line can be obtained
from Eqs. 8-2. Along each longitude line, angle θ has a constant value. Similarly, angle
φ is constant along any latitude line. For example, the coordinates along the longitude
line in the xz plane (θ = 0) are calculated with the equations
x = r cos φ,
y = 0,
z = r sin φ
and the equations for computing coordinate positions along the latitude line in the xy
plane (φ = 0) are
x = r cos θ,
y = r sin θ,
z = 0
If we denote the required number of latitude lines as nlat and the required number of
longitude lines as nlong, the algorithm can obtain vertex coordinates by calculating nlong
positions along nlat latitude lines (or vice versa). Thus, angle θ is assigned nlong values
over the range from −π to +π, and angle φ is assigned nlat values over the range from
−π/2 to +π/2.
47
48
CHAPTER 8. THREE-DIMENSIONAL OBJECT REPRESENTATIONS
The algorithm should take sphere symmetries into account to reduce the number of
trigonometric calculations. Coordinate positions need to be computed from the paramet-
ric sphere equations only for the latitude lines in the northern (or southern) hemisphere.
Positions in the other hemisphere are obtained using a reflection about the xy plane.
Also, the algorithm need only calculate positions within one octant of each circular lat-
itude (or longitude) line. The remaining positions in the other octants for each circle
are obtained by symmetry (Fig. 3-18). Furthermore, the latitude “lines” at the top and
bottom of the sphere (the poles) are points.
At the top of the sphere, polygon edges are defined from the pole position radially down
to the coordinate positions on the first latitude line below the pole, and a polygon edge
is defined between each pair of adjacent positions along that latitude line. A similar set
of polygons is constructed at the bottom of the sphere. Thus, the top and bottom of the
spherical surface are each represented with a triangular mesh.
For all other latitude lines, adjacent pairs of coordinate positions are used to define a
horizontal edge of a quadrilateral, and adjacent positions along a longitude line joining
two latitude lines are used to define a vertical edge of a quadrilateral. To facilitate
processing and to ensure that the vertex positions for each surface facet are coplanar,
additional calculations can be performed to split each quadrilateral into two triangles.
The final step in the algorithm is to store the information for vertex coordinates, polygon
edges, and surface facets in polygon tables (Section 3-15).
8-2. A polygon-mesh representation for an ellipsoid can be constructed using Eqs. 8-4 and
the sphere algorithm from the preceding exercise. The primary differences between the
two algorithms are that the parametric equations involve a radius value for each axis and
input values are needed for rx, ry, and rz, with the ellipsoid centered at the coordinate
origin. Also, coordinate positions along an ellipse are symmetric between quadrants, but
not between octants.
8-3. Assuming that the cylinder parameters are specified relative to the coordinate origin,
input for this algorithm can be the cylinder radius r and the height h above the xy plane.
Thus, the cylinder axis is along the z axis, the center position for the bottom of the
cylinder is (0, 0, 0), and the center position for the top of the cylinder is (0, 0, h). If some
other position is to be given for the cylinder, calculations for the polygon-mesh vertex
coordinates can be carried out relative to the given cylinder reference position. Or, the
cylinder can be translated and rotated to place its base in the xy plane and its axis along
the z axis.
First, compute a set of equally spaced points around the perimeter of the cylinder top.
This can be accomplished using the midpoint circle algorithm (Section 3-9) or the para-
metric circle equations 3-28. In either case, we need only calculate coordinates for the
points in the first quadrant, and the remaining points are determined by symmetry (Fig.
3-18). These points provide the vertices for a convex polygon representation of the top of
the cylinder, and form the basis for obtaining the polygon representation for the cylinder
base. For every position (x, y, h) along the top of the cylinder, there is a corresponding
point (x, y, 0) at the base of the cylinder, which are the remaining vertex positions
49
needed for the polygon at the base and for the rectangles along the side of the cylinder.
The final step in the algorithm is to store the information for vertex coordinates, polygon
edges, and surface facets in polygon tables (Section 3-15).
The number of circle subdivisions can be an additional input parameter. Or a fixed
number of subdivisions, such as 8 or 10, can be used for all input cylinders.
To facilitate processing and to ensure that the vertex positions for each surface facet are
coplanar, additional calculations can be performed to convert the polygon representation
into a triangular mesh. This is accomplished for the top and bottom of the cylinder by
adding radial lines from the circle center to the vertex positions on the circle perimeter.
For each rectangular strip along the side of the cylinder, add a diagonal line. Also, the
size of the polygons along the side of the cylinder can be reduced by first dividing each
rectangle into a number of smaller rectangles, then splitting the reduced rectangles into
triangles. Thus, another option for this algorithm is the specification of the number of
horizontal slices to be used in creating the rectangles along the side of the cylinder.
8-4. A polygon-mesh representation for a superellipsoid can be constructed using Eqs. 8-12
and the ellipsoid algorithm (Exercise 8-2), along with the additional parameters s1 and
s2.
8-5. An algorithm for generating a polygon-mesh representation for the surface of a meta-
ball object can be set up using techniques similar to those for the sphere and ellipsoid
algorithms (Exercises 8-1 and 8-2). Given values for parameters b, d, and the surface
constant for f(r), convert the object description to a parametric form involving surface
parameters u and v. Then, subdivide the surface into a number of subintervals in the
two orthogonal directions to obtain a set of polygon facets.
8-6. Input for this routine can be a data file that includes a value for the tension parameter
t, as well as a set of four control-point positions. An additional input can be either the
number of coordinate positions to plot along the curve or a step size ∆u for the parametric
parameter u.
The parametric representation 8-35 can be rewritten in standard polynomial form for
each of the x and y coordinates, and positions along the curve between the middle two
control points are calculated for parameter values uj+1 = uj + ∆u, where u0 = 0, un = 1,
and j = 0, 1, 2, . . . , n. These coordinate positions could be connected with straight line
segments, or forward differences can be used to determine points along the cardinal-spline
path.
To display the curve section, the example program in Section 8-10 can be modified so
that the cardinal-spline routine replaces procedure bezier. As an option, a closed curve
as in Fig. 8-29 can be displayed using a cyclic permutation of the four control points.
Another option is to specify more that four control points so that multiple connected
cardinal-spline sections can be generated between all control points except the first point
and the last point.
8-7. The parametric equations for a Kochanek-Bartels spline can be derived from boundary
conditions 8-36 using the same procedures discussed for cardinal splines. And the curve
50
CHAPTER 8. THREE-DIMENSIONAL OBJECT REPRESENTATIONS
can be displayed using the cardinal-spline procedures in Exercise 8-6. For this program, an
input file can include values for the tension, bias, and continuity parameters, in addition
to the control-point positions and a value for the parametric step size ∆u.
8-8. As noted in Section 8-10, a B´ezier curve generated with three distinct, noncollinear control
points is a parabola. The three blending functions are
BEZ0,2 = (1 − u)2,
BEZ1,2 = 2u(1 − u),
BEZ2,2 = u2
Function BEZ0,2 has a minimum value of 0 at u = 1.0 and a maximum value of 1.0 at
u = 0. Function BEZ1,2 has its minimum value of 0 at both u = 0 and u = 1.0, and
BEZ1,2 has a maximum value of 0.5 at u = 0.5. Function BEZ2,2 has a minimum value
of 0 at u = 0 and a maximum value of 1.0 at u = 1.0.
8-9. The five B´ezier blending functions for n = 4 are
BEZ0,4 = (1 − u)4,
BEZ1,4 = 4u(1 − u)3,
BEZ2,4 = 6u2(1 − u)2,
BEZ3,4 = 4u3(1 − u),
BEZ4,4 = u4,
max = 1 at u = 0
min = 0 at u = 1;
min = 0 at u = 0, 1; max = 27/64 at u = 1/4
min = 0 at u = 0, 1; max = 3/8 at u = 1/2
min = 0 at u = 0, 1; max = 27/64 at u = 3/4
min = 0 at u = 0;
max = 1 at u = 1
8-10. For this exercise, replace the set of four control-point coordinates given in procedure
displayFcn with input from a data file. Other input values could also be included in
the data file, such as the curve width, the curve color, and details for displaying the
control points and control graph. For example, the control points could be displayed in
a specified size and color, with connecting dashed lines.
8-11. For this exercise, replace the fixed values for variable nCtrlPts and the control-point
coordinates given in procedure displayFcn with input from a data file that contains the
control-point positions and the number of positions. Various other data can be included
in the input, such as the number of points to be plotted along the curve path, the width
and color of the curve, and details for displaying the control points and control graph.
For example, the control points could be displayed in a specified size and color, with
connecting dashed lines. Other options include displaying the curve as set of straight-line
segments, or a set of points obtained with forward-difference calculations.
8-12. This programming exercise is a variation of the program for Exercise 8-10. Modify the
programming example in Section 8-10 so that the OpenGL routines from the example
in Section 8-18 are used to generate and display the B´ezier curve, instead of the explicit
calculations for the blending functions and curve coordinates.
8-13. Expand the program from the preceding exercise so that the control points are specified
in three-dimensional Cartesian coordinates and a three-dimensional B´ezier curve is gener-
ated. Viewing routines for displaying the curve can be taken from previous programming
51
examples. Various projection planes could be used to view the curve from different po-
sitions. For example, a curve defined in the xz plane projects to a straight line if the
projection plane is parallel to the xy plane. Also, the four input control points might not
be coplanar.
8-14. Input for each curve section can be limited to three or four control points. Any number
of connected curve sections could be displayed, or the routine could be limited to the
display of just two connecting curve sections. An input file can be used to specify the
coordinates for each set of control points, the number of control points in each set, and
the number of curve sections to be displayed.
For the second curve section, the positions for the first two control points could be
calculated from the continuity conditions, or all control-point positions could be specified
as input.
If all control-point positions are included in the input file, tests should be
performed to be sure that the first-order continuity conditions are satisfied. Thus, the
coordinates for the first control point of the second curve section should be the same as
the coordinates for the last control point of the first curve section. And the coordinates for
the second control point should satisfy Eq. 8-47. Either the program from Exercise 8-10
or the program from Exercise 8-12 could be modified to display the two curve sections.
8-15. This is an extension of the preceding exercise, with an added calculation for the coor-
dinates of p2. For this routine, the third control point of the second curve section is
positioned so that the first and second derivatives of the first and second curve sections
match at the boundary. Thus, the position for the first control point of the second curve
section is the same as the position for the last control point of the first curve section, the
position for the second control point of the second curve section is calculated from Eq.
8-47, and the position for the third control point of the second curve section is calculated
from Eqs. 8-45 as
p2 = pn +
n (pn − pn−1) +
2n
n(n − 1)
n(n − 1)
[pn−2 − 2pn−1 + pn]
8-16. The subdivisions methods given in Section 8-17 are to be used to calculate curve positions
in the program for Exercise 8-10.
8-17. The forward-difference methods given in Section 8-17 are to be used to calculate curve
positions in the program for Exercise 8-10.
8-18. For a given value of n, a uniform knot vector with integer values from 0 to n+d+1 = n+6
can be constructed. Then the knot vector values are used in relations 8-53 to obtain the
first blending function. The remaining blending functions can then be obtained from Eqs.
8-55. Also, the blending functions Bk,3(u) from Example 8-1 in Section 8-12 can be used
in the determination of blending functions Bk,5(u).
As an example, if n = d = 5, the knot vector is
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
52
CHAPTER 8. THREE-DIMENSIONAL OBJECT REPRESENTATIONS
And blending function B0,5(u) is evaluated from blending functions B0,3(u) in Example
8-1.
8-19. For a given value of n, a uniform knot vector with integer values from 0 to n+d+1 = n+7
can be constructed. Then the knot vector values are used in relations 8-53 to obtain the
first blending function. The remaining blending functions can then be obtained from Eqs.
8-55. Also, the blending functions Bk,3(u) from Example 8-1 in Section 8-12 can be used
in the determination of blending functions Bk,6(u).
As an example, if n = d = 6, the knot vector is
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
And blending function B0,6(u) is evaluated from blending functions B0,3(u) in Example
8-1.
8-20. In general, the set of blending functions could be determined for specified values of
the knot vector and parameters d and n. These blending functions would then replace
the B´ezier blending functions in the programming example of Section 8-10. A simpler
assignment for this problem is to implement the blending functions in Exercise 8-1 of
Section 8-12 to display the quadratic B-spline curve. And the forward-difference methods
from Section 8-17 are used to calculate coordinate positions along the B-spline curve,
using the procedures discussed for Exercise 8-17.
8-21. As in Exercise 8-12, programming examples from Section 8-10 and 8-18 can be combined
to display the curve. In this case, the GLU routines are to be used to generate a B-spline.
8-22. For this exercise, input can be specified in a data file that contains the coordinates for
three control points and the values for the weight factors ωk. These input values are then
used in Eq. 8-69, along with the B´ezier blending functions, to generate a conic section,
using the methods given in Section 8-15.
8-23. The routine from the preceding exercise is modified to implement Eq. 8-71, using the
methods described in the Section 8-15 example.
8-24. Coordinates for a position on a B´ezier surface are calculated from Eq. 8-51, given a set
of control points and the values for the blending functions. At any point P(u, v) on the
surface, we can calculate two surface vectors that are tangent to the surface along the
directions of the surface parameters:
ru =
∂P
∂u
,
rv =
∂P
∂v
The unit normal vector at point P is then calculated as
n =
ru × rv
|ru × rv|
8-25. For quadratic equations of the form
with 0 ≤ u ≤ 1 and increments uk+1 = uk + δ, the forward-difference calculations are
x(u) = a0 + a1u + a2u2
53
with initial values
xk+1 = xk + ∆xk
∆xk+1 = ∆xk + ∆2xk
x0 = a0
∆x0 = a1δ + a2δ2
∆2x0 = 2a2δ2
and the second forward difference ∆2xk is a constant for all values of k. The above
equations are then applied repeatedly to obtain the (x, y) coordinate positions along the
curve from u = 0 to u = 1. This algorithm can be implemented to display a quadratic
curve, specified by input parameters.
8-26. Forward-difference calculations for a cubic curve are given in Section 8-17. These calcula-
tions are then applied repeatedly to obtain the (x, y) coordinate positions along the curve
from u = 0 to u = 1. As in the preceding exercise, this algorithm could be implemented
to display a cubic curve, specified by input parameters.
8-27. An input file for this problem can include the components of the translation vector,
specifying the sweep direction relative to the coordinate origin, a translation distance,
and a shape that is defined in the xy plane. The translation distance (Section 8-19) can
be assumed to specify the third dimension for the object relative to its definition in the
xy plane. (Otherwise, starting and ending positions along the sweep direction can be
specified.) For example, a translation distance in the +z direction for a circle specifies
the height of a circular cylinder above the xy plane.
The surface for the three-dimensional object is to be defined with a polygon mesh. This is
accomplished by dividing both the perimeter of the two-dimensional object and the trans-
lation distance into a number of intervals, which are connected to form the boundaries
of the surface facets, as illustrated in Fig. 8-55. The size of the intervals (or the number
of intervals) in each direction can be specified in the input file. A complete description
of the surface is then given in a set of polygon tables that specify the vertex and edge
information for each surface facet.
8-28. Methods for this exercise are similar to those in the preceding exercise. The difference
is that rotational sweep parameters are specified in the input file instead of translational
sweep parameters. A rotation axis can be specified in various ways. It could be defined
with an axis vector or with two three-dimensional coordinate positions (Section 5-11).
Or the rotation axis could be assumed to be in the xy plane at a specified distance from
the center of the object, as in Fig. 8-56. Also, a rotation angle can be given in the input
54
CHAPTER 8. THREE-DIMENSIONAL OBJECT REPRESENTATIONS
file, which specifies the amount of rotation about the axis from the defined position of
the object in the xy plane. Or, a 360◦ sweep could be assumed.
The perimeter of the two-dimensional object is divided in subintervals, which are rotated
incrementally through the sweep angle to form a set of points on the three-dimensional
surface. Surface facet information is then stored in tables as in Exercise 8-27.
8-29. The ray-casting method discussed in Section 8-20 can be used to generate the CSG
description of an object formed from two overlapping three-dimensional shapes using a
specified Boolean operation. For this algorithm, two simple shapes, such as a cube and
a sphere or a cube and a tetrahedron, can be defined relative to the coordinate origin.
For instance, each object can be defined with its center at the coordinate origin. The
parameters for the two objects, such as the sphere radius and the cube vertex coordinates,
could be specified in an input file, along with the new center position and orientation for
each object, the surface color for each object, and the type of Boolean operation to be
applied.
Geometric transformations are applied to place the two objects in some region of space,
given the input positioning and orientation information. Then ray intersection calcu-
lations are performed, as indicated in Figs. 8-60 and 8-61, for each pixel within the
firing-plane projection of the coordinate extents of the scene.
To compute the intersection position for a ray and a sphere, substitute the equation for
the line along the path of the orthogonal ray into the sphere equation and solve for the
distance from the firing plane. For example, if a pixel is at position Ppix on the firing
plane and the center of a sphere with radius r is at position Pc, then the intersection
position is calculated from the sphere equation as
|(Ppix + s u) − Pc|2 − r2 = 0
where s is the distance along the ray from the firing plane and u is the unit direction
vector for the ray. If the firing plane is the xy plane, as in Fig. 8-61, then all rays are
parallel to the z axis and u = uz. If the discriminant in the solution for s is negative,
the ray does not intersect the sphere. Otherwise, the intersection point nearest the firing
plane is the visible surface intersection position.
Methods for computing the intersection position for a ray and a polygon surface of a
polyhedron are similar to those for computing the intersection of a polygon edge with a
clipping plane (Exercise 3-17). First determine whether the ray intersects the bounding
sphere for the polyhedron. If it does, then test the surface normal vector for each polygon
to identify those polygons that are visible to the firing plane. The normal vector N for a
visible polygon satisfies the inequality
N·u < 0
For each visible polygon, substitute the equation for the pixel ray into the plane equation
to obtain
N·(Ppix + s u) + D = 0