Three Dimensional Object Representations

Representation schemes for solid objects are divided into two categories as
follows: 1. Boundary Representation ( B-reps)

It describes a three dimensional object as a set of surfaces that separate the object
interior from the environment. Examples are polygon facets and spline patches.

2. Space Partitioning representation

It describes the interior properties, by partitioning the spatial region containing an

object into a set of small, nonoverlapping, contiguous solids(usually cubes). Eg:
Octree Representation.

Polygon Surfaces

Polygon surfaces are boundary representations for a 3D graphics object is a set of

polygons that enclose the object interior.

Polygon Tables

The polygon surface is specified with a set of vertex coordinates and associated
attribute parameters.

For each polygon input, the data are placed into tables that are to be used in the
subsequent processing.

Polygon data tables can be organized into two groups: Geometric tables and
attribute tables.
Geometric Tables Contain vertex coordinates and parameters to identify the
spatial orientation of the polygon surfaces.

Attribute tables Contain attribute information for an object such as parameters

specifying the degree of transparency of the object and its surface reflectivity and
texture characteristics. A convenient organization for storing geometric data is to
create three lists:

1. The Vertex Table

Coordinate values for each vertex in the object are stored in this table. 2. The Edge
Table

It contains pointers back into the vertex table to identify the vertices for each
polygon edge. 3. The Polygon Table

It contains pointers back into the edge table to identify the edges for each polygon.
This is shown in fig
Listing the geometric data in three tables provides a convenient reference to the
individual components (vertices, edges and polygons) of each object.

The object can be displayed efficiently by using data from the edge table to draw
the component lines.

Extra information can be added to the data tables for faster information extraction.
For instance, edge table can be expanded to include forward points into the
polygon table so that common edges between polygons can be identified more
rapidly.

E1 : V1, V2, S1

E2 : V2, V3, S1

E3 : V3, V1, S1, S2

E4 : V3, V4, S2

E5 : V4, V5, S2

E6 : V5, V1, S2

is useful for the rendering procedure that must vary surface shading smoothly
across the edges from one polygon to the next. Similarly, the vertex table can be
expanded so that vertices are cross-referenced to corresponding edges.
Additional geometric information that is stored in the data tables includes the slope
for each edge and the coordinate extends for each polygon. As vertices are input,
we can calculate edge slopes and we can scan the coordinate values to identify the
minimum and maximum x, y and z values for individual polygons.

The more information included in the data tables will be easier to check for errors.
Some of the tests that could be performed by a graphics package are:

1. That every vertex is listed as an endpoint for at least two edges.

2. That every edge is part of at least one polygon.

3. That every polygon is closed.

4. That each polygon has at least one shared edge.

5. That if the edge table contains pointers to polygons, every edge referenced by a
polygon pointer has a reciprocal pointer back to the polygon.

Plane Equations:

To produce a display of a 3D object, we must process the input data representation

for the object through several procedures such as,

- Transformation of the modeling and world coordinate descriptions to viewing

coordinates.

- Then to device coordinates:

- Identification of visible surfaces

- The application of surface-rendering procedures.

For these processes, we need information about the spatial orientation of the
individual surface components of the object. This information is obtained from the
vertex coordinate value and the equations that describe the polygon planes.

The equation for a plane surface is Ax + By+ Cz + D = 0 ----(1)

Where (x, y, z) is any point on the plane, and the coefficients A,B,C and D are
constants describing the spatial properties of the plane.

We can obtain the values of A, B,C and D by solving a set of three plane equations
using the coordinate values for three non collinear points in the plane.

For that, we can select three successive polygon vertices (x1, y1, z1), (x2, y2, z2)
and (x3, y3, z3) and solve the following set of simultaneous linear plane equations
for the ratios A/D, B/D and C/D.

(A/D)xk + (B/D)yk + (c/D)zk = -1, k=1,2,3 -----(2)

The solution for this set of equations can be obtained in determinant form, using
Cramer’s rule as

Expanding the determinants , we can write the calculations for the plane
coefficients in the form:
A = y1 (z2 –z3 ) + y2(z3 –z1 ) + y3 (z1 –z2 )

B = z1 (x2 -x3 ) + z2 (x3 -x1 ) + z3 (x1 -x2 )

C = x1 (y2 –y3 ) + x2 (y3 –y1 ) + x3 (y1 -y2 )

D = -x1 (y2 z3 -y3 z2 ) - x2 (y3 z1 -y1 z3 ) - x3 (y1 z2 -y2 z1) ------(4)

As vertex values and other information are entered into the polygon data structure,
values for A, B, C and D are computed for each polygon and stored with the other
polygon data.

Plane equations are used also to identify the position of spatial points relative to
the plane surfaces of an object. For any point (x, y, z) hot on a plane with
parameters A,B,C,D, we have

Ax + By + Cz + D ≠ 0

We can identify the point as either inside or outside the plane surface according o
the sigh (negative or positive) of Ax + By + Cz + D:

If Ax + By + Cz + D < 0, the point (x, y, z) is inside the surface. If Ax + By + Cz +

D > 0, the point (x, y, z) is outside the surface.

These inequality tests are valid in a right handed Cartesian system, provided the
plane parmeters A,B,C and D were calculated using vertices selected in a counter
clockwise order when viewing the surface in an outside-to-inside direction.
Polygon Meshes

A single plane surface can be specified with a function such as fillArea. But when
object surfaces are to be tiled, it is more convenient to specify the surface facets
with a mesh function. One type of polygon mesh is the triangle strip.A triangle
strip formed with 11 triangles connecting 13 vertices.

This function produces n-2 connected triangles given the coordinates for n vertices.

Another similar function in the quadrilateral mesh, which generates a mesh of (n-
1) by (m-1) quadrilaterals, given the coordinates for an n by m array of vertices.
Figure shows 20 vertices forming a mesh of 12 quadrilaterals.
Curved Lines and Surfaces Displays of three dimensional curved lines and
surface can be generated from an input set of mathematical functions defining
the objects or from a set of user specified data points. When functions are
specified, a package can project the defining equations for a curve to the display
plane and plot pixel positions along the path of the projected function. For
surfaces, a functional description in decorated to produce a polygon-mesh
approximation to the surface.

Spline Representations A Spline is a flexible strip used to produce a smooth

curve through a designated set of points. Several small weights are distributed
along the length of the strip to hold it in position on the drafting table as the curve
is drawn.
The Spline curve refers to any sections curve formed with polynomial sections
satisfying specified continuity conditions at the boundary of the pieces.

A Spline surface can be described with two sets of orthogonal spline curves.
Splines are used in graphics applications to design curve and surface shapes, to
digitize drawings for computer storage, and to specify animation paths for the
objects or the camera in the scene. CAD applications for splines include the design
of automobiles bodies, aircraft and spacecraft surfaces, and ship hulls.

Interpolation and Approximation Splines Spline curve can be specified by a set

of coordinate positions called control points which indicates the general shape of
the curve. These control points are fitted with piecewise continuous parametric
polynomial functions in one of the two ways. 1. When polynomial sections are
fitted so that the curve passes through each control point the resulting curve is said
to interpolate the set of control points.

A set of six control points interpolated with piecewise continuous polynomial

sections

1. When the polynomials are fitted to the general control point path without
necessarily passing through any control points, the resulting curve is said
to approximate the set of control points.

A set of six control points approximated with piecewise continuous polynomial

sections
 Interpolation curves are used to digitize drawings or to specify animation
paths. Approximation curves are used as design tools to structure object surfaces.
A spline curve is designed , modified and manipulated with operations on the
control points.The curve can be translated, rotated or scaled with transformation
applied to the control points. The convex polygon boundary that encloses a set of
control points is called the convex hull. The shape of the convex hull is to imagine
a rubber band stretched around the position of the control points so that each
control point is either on the perimeter of the hull or inside it.
Convex hull shapes (dashedlines) for two sets of control points

Parametric Continuity Conditions

For a smooth transition from one section of a piecewise parametric curve to the
next various continuity conditions are needed at the connection points.

If each section of a spline in described with a set of parametric coordinate

functions or the form x = x(u), y = y(u), z = z(u), u1<= u <= u2 -----(a)

We set parametric continuity by matching the parametric derivatives of adjoining

curve sections at their common boundary.

Zero order parametric continuity referred to as C0 continuity, means that the

curves meet. (i.e) the values of x,y, and z evaluated at u2 for the first curve section
are equal. Respectively, to the value of x,y, and z evaluated at u1 for the next curve
section.

First order parametric continuity referred to as C1 continuity means that the

first parametric derivatives of the coordinate functions in equation (a) for two
successive curve sections are equal at their joining point.
Second order parametric continuity, or C2 continuity means that both the first
and second parametric derivatives of the two curve sections are equal at their
intersection.

Higher order parametric continuity conditions are defined similarly.

Piecewise construction of a curve by joining two curve segments using

different orders of continuity

a) Zero order continuity only

b) First order continuity only

c) Second order continuity only

Geometric Continuity Conditions

To specify conditions for geometric continuity is an alternate method for joining
two successive curve sections.

The parametric derivatives of the two sections should be proportional to each other
at their common boundary instead of equal to each other.

Zero order Geometric continuity referred as G0 continuity means that the two
curves sections must have the same coordinate position at the boundary point.

First order Geometric Continuity referred as G1 continuity means that the

parametric first derivatives are proportional at the interaction of two successive
sections.

Second order Geometric continuity referred as G2 continuity means that both the
first and second parametric derivatives of the two curve sections are proportional at
their boundary. Here the curvatures of two sections will match at the joining
position.

Three control points fitted with two curve sections joined with a) parametric
continuity
b) Geometric continuity where the tangent vector of curve C3 at point p1 has
a greater magnitude than the tangent vector of curve C1 at p1.

Spline specifications There are three methods to specify a spline representation:

1. We can state the set of boundary conditions that are imposed on the spline; (or)

2. We can state the matrix that characterizes the spline; (or)

3. We can state the set of blending functions that determine how specified
geometric constraints on the curve are combined to calculate positions along the
curve path.

To illustrate these three equivalent specifications, suppose we have the following

parametric cubic polynomial representation for the x coordinate along the path of a
spline section.

x(u)=axu3 + axu2 + cxu + dx 0<= u <=1 ----------(1) Boundary conditions for this
curve might be set on the endpoint coordinates x(0) and x(1) and on the parametric
first derivatives at the endpoints x’(0) and x’(1). These boundary conditions are
sufficient to determine the values of the four coordinates ax, bx, cx and dx. From
the boundary conditions we can obtain the matrix that characterizes this spline
curve by first rewriting eq(1) as the matrix product
where U is the row matrix of power of parameter u and C is the coefficient column
matrix. Using equation (2) we can write the boundary conditions in matrix form
and solve for the coefficient matrix C as

C = Mspline . Mgeom -----(3) Where Mgeom in a four element column matrix

containing the geometric constraint values on the spline and Mspline in the 4 * 4
matrix that transforms the geometric constraint values to the polynomial
coefficients and provides a characterization for the spline curve.

Matrix Mgeom contains control point coordinate values and other geometric
constraints. We can substitute the matrix representation for C into equation (2) to
obtain.

x (u) = U . Mspline . Mgeom ------(4)

The matrix Mspline, characterizing a spline representation, called the basis

matriz is useful for transforming from one spline representation to another.

Finally we can expand equation (4) to obtain a polynomial representation for

coordinate x in terms of the geometric constraint parameters.

x(u) = Σ gk. BFk(u) where gk are the constraint parameters, such as the control
point coordinates and slope of the curve at the control points and BFk(u) are the
polynomial blending functions.