0% found this document useful (0 votes)
23 views49 pagesCG Mod 4 & 5
Computer graphics
Uploaded by
afnanazir2004Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
23 views49 pagesCG Mod 4 & 5
Computer graphics
Uploaded by
afnanazir2004Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 49
B
UNIT -1Z
i Concepts
7 ciples BD hee the pehiup
a h 7m pejunce Spe da Foe
Cameras
yA
babcheh.\ A}
Sta ec oGniltna hes. — abi ak the
_ position ancl aelet Fon. plan
Ge ean
ued Ato <= View & +.
/
hddisdiicbiiiaelt
|
7
i i
tg tee oot We can abe's
q a Juitace ieee 2 techies
paees~ en Mi oo a
call se na tl OD duping plone
Bien ney ed
TD Puntpective pro Projection
Th hi nettrod » we Arcwe — to ject _points a
f Ce eae eat oneal
thi causes objects further frond ee
ees ofthe scene Alte that ame _niciner.
the: Viewing. pasttion:
ae acteusticz : SS
| ds Ad appear more 26 die :
wat the Ina : ove
approach (to ee Spare ee
Lines but Pow ving,
evel Information alooud Abe shape 4-
thE back Surfaces Hy an. an
ee Objecte are Z 7A ith.
ae. aby ae apa eee hye! 3
wn dein
th auc oa
Vite Ades #0.
20 That the alto —
obkewred ~ (not ls covered)
pricing h Goxchis i Ne ;
ice oe es
tng pe —— Wal Wotlea bu meng. te eae ada rhe iy
be deecribed a ete 9» Buel “ak
Tppline Burfacer , that one oT tae coonvertecl te
elygonal oprecntations fo7 processing *
Uya6r proprstendation « pelyhidpen
ines the wodarce akwees § the Object.
objects. Surgaee one tossclated
fe ae) ay oduce pepe rah
ap oxtraastion eee
race % eytinda & seproren ted 4
c ol indication ni
&
fact a - cae ae eee
Aurface- wrt a aaa
Lt
Nortex coordinates Tand ato ciated atu but E
mation for cach rege
we ee Leto -
[polygon dati apis can be organtzed. ro two +
pore ieee steiblice ead. athsubute hui
GCreometoute sila tables ar wear Coo3din
ard panianaetens tb a tha pakicd ohiewtix
tas polygon. A Meaaie
Hleibade lepraadon a stale;
sarge tras piv)
aamctors
tho object
! eee Bs Fanfece as ped
(on. sie pe A pope
“ Pa omy
and sore eg
aaplicaes “ comridinate Wonok@n Hee
plicit coordinate vabus art Dited for each
ux in £2th polygon ~ Mio edge Infor make n
wild awe ko be ‘HEonetoncted m rhe weet
Werrten AAs tings tn he poligon ebe coe
We can vod extra information p the Lala tabs js
mee information extsiaction: Fon initence uecould |
mand the edge table 40 Include forucatd pointer into -
polygon +alpee 40 Phat common edger betueen
Wygons could be Identified more napidly > Trivarly —
vertex toble could be Cnparrded. (30 Had vortices
Le cross - roprenced ty | Coreecponding edges
iHional georneteete Information thot iS usually Stor
dale tables include tre slope 1 Lach tdge and _
poicinate Atends “04 Lach polygon - Aa vexkitos
i We tan < SS eat ad can
can dinate vi te ee Wied mad
eee os and 2 value fo4 individual ;
gon . :
1 ‘and. comple
Leonsithimay. a
hen verter
Therfore ers check
: j deta tables (verter,
[since Hus scheme provides”
Had would be performed E Sti € ay Ei, Ea
$2: €>, Ey, Es
2 Ee
Ns Vi, $2
One —+
| powoduce a Hiploy 9, thse (yo =y1239)— Zz
W2 Bi
J
ydation § a plane surface in Space can be bee
bed with sjoudss FO ks, water, bricks, wood paneling, rubber, paper, marble, steel,
atic, and cloth, just to mention a few. So it is probably not too surprising
a fe is no one method that we can use to describe objects that will include
oristics of these different materials. And to produce realistic displays of
. need to use representations that accurately model object characteris-
E; sphics enes can contain many different kinds of objects: trees, flowers
" i, i:
y the’
ggataenet
wee i
ae polygon and quadric surfaces provide precise descriptions for simple Eu-
jean objects such as polyhedrons and ellipsoids; spline surfaces and construc-
we techniques are useful for designing aircraft wings, gears, and other engineer-
r aructures with curved surfaces; procedural methods, such as fractal
qastructions and particle systems, allow us to give accurate representations for
gods, clamps of grass, and other natural objects; physically based modeling
methods Using systems of interacting forces can be used to describe the nonrigid
ihavior of a piece of cloth or a glob of jello; octree encodings are used to repre-
«mt internal features of objects, such as those obtained from medical CT images;
anf isosurface displays, volume renderings, and other visualization techniques
av applied to three-dimensional discrete data sets to obtain visual representa-
tons of the data.
Representation schemes for solid objects are often divided into two broad
categories, although not all representations fall neatly into one or the other of
these two categories. Boundary representations (B-reps) describe a three-dimen-
sional object as a set of surfaces that separate the object interior from the environ-
ment. Typical examples of boundary representations are polygon facets and
spline patches. Space-partitioning representations are used to describe interior
Properties, by partitioning the spatial region containing an object into a set of
small, nonoverlapping, contiguous solids (usually cubes). A common space-par-
tioning description for a three-dimensional object is an octree representation. In
this chapter, we consider the features of the various representation schemes and
W they are used in applications.
10-1
POLYGON SURFACES
e most i three-dimensional
commonly used boundary representation for a three-dimensi
Baphics object is a ie of surface potrsont that enclose the object interior. Many
Sraphics Systems store all object descriptions as sets of surface polygons. This
‘Slag es and speeds up the surface rendering and display of objects, since all
are described with linear equations. For this reason, polygon descrip-
. Wireframe representation of a
cylinder with back (hidden)
lines removed.
tions are often referred to as “standard graphics objects. nay Sm oS Polyp.
onal representation is the only one available, but many age - - jects ty
be described with other schemes, such as spline surfaces, tha Converted
to polygonal representations oe
ntation for a e : :
tures a ee eh Het stat ae surface are fesse a ree Produce
the polygon-mesh approximation. In Fig. 10-1, the surface of a > inder is Tepre.
sented as a polygon mesh. Such representations are common in esign and solid.
modeling applications, since the wireframe outline can be displayed quickly to
give a general indication of the surface structure. Realistic renderings are pro-
duced by interpolating shading patterns across the polygon surfaces to eliminate
or reduce the presence of polygon edge boundaries. And the polygon-mesh ap.
proximation to a curved surface can be improved by dividing the surface into
smaller polygon facets.
i
dron precisely defines the surface fe._
Polygon Tables
We specify a polygon surface with a set of vertex coordinates and associated at-
tribute parameters. As information for each polygon is input, the data are placed
into tables that are to be used in the subsequent processing, display, and manipu-
n data tables can be organized into tw
lation of the objects in a scene{_Po
groups: geometric tables and attribute tables. Geometric aot Se contain ve
tex coordinates and parameters to identify the spatial orientation of the polygo
surfaces. Attribute information for an object includes parameters ifying #
degree of transparency of the object and its surface reflectivity and texture chi
acteristics. ) —_ = ee
hy,
proximation to a curves wow
smaller polygon" facets.
x coordinates and ass,
h a set of vertex COOr’ na ia se)
r each polygon is input, the data cae : %
uent processing, display, and ace
t
Polygon Tables
on surface wit
i ely
les can be organized int Pu. |
le specify a polyg' .
ak parenciers As earner paees
into tables that are to be used (Polygon data tab
satire: Se oO title and atiribe te tables. Geometric data tables contain ,°
Soup Sead arameters to identify the spatial orientation of the leo,
i ae i: itformation for an object includes parameters Specifying on |
surfaces. Attribute | f the object and its surface reflectivity and texture Fi
degree of transparency ©
acteristics. w= ' ‘ is t
4 ient organization for storing geometric data is to create three Hite
f veni
a vesbertable, an edge table, and a polygon eee ee for each -
tex in the object are stored in the vertex table: The edge table contains Pointe,
tify the vertices for each polygon edge. Ang ie
ck into the edge table to identify the edges fo,
back into the vertex table to -
ble contains pointers ba 1
table co! le strated in Fig. 10-2 for two adjacent polygons «,
polygon ise
each polygon. This scheme is illu rat .
an object surface. In addition, individual objects and their component Polygon
faces can be assigned object and facet identifiers for easy reference, :
Listing the geometric data in three tables, as in Fig. 10-2, provides a conve.
nient reference to the individual components (vertices, edges, and Polygons) of
displayed efficiently by using data from the
each object. Also, the object can be é
edge table to draw the component linesf An alternative arrangement is to use}
two tables: a vertex table and a polygon ~But this scheme is less convenient,
and some edges could get drawn twice. Another possibility is to use only a poly.
gon table, but this duplicates coordinate information, since explicit coordinate
values are listed for each vertex in each polygon. Also edge information would
have to be reconstructed from the vertex listings in the polygon table.
We can add extra information to the data tables of Fig. 10-2 for faster infor-
mation extraction. For instance, we could expand the edge table to include for-
ward pointers into the polygon table so that common edges between polygons
could be identified more rapidly (Fig. 10-3). This is particularly useful for the ren-
ding smoothly across the edges
dering procedures that must vary surface sha
from one polygon to the next. Similarly, the vertex table could be expanded ©
that vertices are cross-referenced to corresponding edges.
____ Additional geometric information that is usually stored in the data table
includes the slope for each edge and the coordinate extents for each poh
vertices are input, we can calculate edge slopes, and we can scan the coof
— Section 10-1
Polygon Surfaces
2 My Yar 24
2 Xp Vor 22
Vy: Xgr Yar 23
Viz Xap Var a
1 Kee Ver 25 Figure 10-2
Geometric data table re
Presentation
surfaces, formed with s for ty
WO adjace
ix edges and fiy e Jacent polygon
vertices
yalues to identify the minimum and maximum x. ; d
solygons- Edge slopes and bounding-box hteaenisc ;
needed in subsequent Processing, for example, Pee : the polygons are
tents are also used in some visible-surface dotensidealion at Ae en
Since the geometric data tables may contain mitentive lstin 35 of
and edges for complex objects, it is important that the data be checked fi ae
tency and completeness. When vertex, edge, and polygon definitions naSiek.
fied, it is possible, particularly in interactive applications, that certain in as
rors could be made that would distort the display of the object. The more
information included in the data tables, the easier it is to check for errors. There-
fore, error checking is easier when three data tables (vertex, edge, and polygon)
are used, since this scheme provides the most information. 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
and (5) that if the edge table contains pointers to polygons, every edge ref-
back to the polygon.
values for individual
edge,
erenced by a polygon pointer has a reciprocal pointer
Plane Equations
i i j j the inpu
To produce a display of a three-dimensional object, we must process
ie ae for the object through several see eae
steps include transformation of the modeling and a0 ee . wari aa
to viewing coordinates, then to device coordinates; i ae ae
faces; and the application of surface-rendering proce sevion of the individual
processes, we need information about the spatial orien
Ey: Vie Vee Sh
Ex: Va Wy. Sy
| Est Vy VSS |
| Eat VaVeS, |
Ex Vp |
Ey: Vg. Vy. S2
a
Figure 10-3
Edge table for the surfaces of
Fig. 10-2 expanded to include
pointers to the polygon table. a —— ‘ane that describe the polygon planes ™ Vette,
Three-Dimensional Object rdinate values and :
Representations 7 The equation for a plane surface can be expressed in the form
Ax + By+Cz+D=0
F
where (x, y, z) is any point on the plane, and the coefficients A, B, C, ang
constants deacxtots cine spatial properties of the plane. We can obtain en
of A, B, C, and D by solving a set of three plane equations using the
values for three noncollinear points in the plane. For this purpose, we can ile
three successive polygon vertices, (x;, Yj, 21), (tz, Yor 22), and (x5, ys, 24), ar
the following set of simultaneous linear plane equations for the ratios A /D,B/p.
and C/D: h
(A/D), + (B/D), + (C/Diy = -1, k=1,2,3 oy
The solution for this set of equations can be obtained in determinant form, using
Cramer’s rule, as
1 "i 2;
A=|1 yw %
1 vs %
sy yy 1
C= Xy Vy 1
% yy 1
Expanding the :
Cients in the form rminants, we can write N=iA BO
Expanding the determinants, we can write the calculations for the Plane —
Gents in the form
A= yy(Zq ~ 25) + Yal2a — %) + ysl — 2)
B = z,(x, — X5) + Z4(xy — &) + Zg(X) — Xp)
(ig
C = x4(y2 — ys) + x9(y3 — ys) + XY) — yp)
D = ~x\(Y223 — Ys%2) — XalYo%1 — Yr2a) — X3(Y,Z2 — y,2,)
As vertex values and other information are entered into the polygon data strc.
ture, values for A, B, C, and D are computed for each polygon and stored with
the other polygon data. ’
Orientation of a plane surface in space can be described with the normal
vector to the plane, as shown in Fig. 10-4. This surface normal vector has Carte
sian components (A, B, C), where parameters A, B, and C are the plane coeff-
Gients calculated in Eqs. 10-4,
Since we are usually dealing with polygon surfaces that enclose object Jo determine the components of the normal vector for the shaded surface
; Fig. 10-5, we select three of the four vertices along the boundary of the
a” These points are selected in a counterclockwise direction as we view
poye™ ade the cube toward the origin. Coordinates for these vertices, in the
a selected, can be used in Eqs. 10-4 to obtain the plane coefficients: A = 1,
or ¢ =0,D = —1. Thus, the normal vector for this plane is in the direction of
e. nsitive x axis.
The elements of the plane normal can also be obtained using a vector cross-
product calculation. We again select three vertex positions, V, Vz, and V3, taken
s counterclockwise order when viewing the surface from outside to inside in a
right-handed Cartesian system. Forming two vectors, one from V, to V2 and the
other from V, to V3, we calculate N as the vector cross product:
Figure 10-5
= = = yo-5) The shaded polygon surface
N= (Vp Vi 0¥, = Wy) GOS) ithe ult cite eedeians
This generates values for the plane parameters A, B, and C. We can then obtain wee " i. nk 0).
the value for parameter D by substituting these values and the coordinates for
one of the polygon vertices in plane equation 10-1 and solving for D. The plane
equation can be expressed in vector form using the normal N and the position P
of any point in the plane as
NicF =< =f) (10-6)
Plane equations are used also to identify the position of spatial points rela-
tive to the plane surfaces of an object. For any point (x, y, z) not on a plane with
Parameters A, B,C, D, we have a
Ax + By+Cz+D#0
Ye can identify the point as either inside or outside the plane surface according
the sign (negative or positive) of Ax + By + Cz + D:
i yee i — i inn N=(V; Vi) X08; = V,) a The shaded polygon surface
of the unit cube has plane
equation x — 1 = Oand
normal vector N = (1, 0, 0)
enerates values for the plane parameters A, B, and C. We can then obtain
pee for parameter D by substituting these values and the coordinates for
the “f the polygon vertices in plane equation 10-1 and solving for D. The plane
one tion can be expressed in vector form using the normal N and the position P
eo point in the plane as
o
Ni P= =2) (10-4)
Plane equations are used also to identify the position of spatial points rela-
ive to the plane surfaces of an object. For any point (x, y, z) not 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
to the sign (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 parameters A, B, C, and D were calculated using vertices selected in a
counterclockwise order when viewing the surface in an outside-to-inside direc-
tion. For example, in Fig. 10-5, any point outside the shaded plane satisfies the in-
equality x — 1 > 0, while any point inside the plane has an x-coordinate value
less than 1.
Polygon Meshes
Some graphics packages (for example, PHIGS) provide several polygon functions
for modeling objects yee 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. This function produces n ~ 2 connected triangles, as shoven in:
10-6, given the coordinates for m vertices. Another |
lateral mesh, which generates a mesh of (n ~ 1) by Figure 10-7
A quadrilateral mesh
containing 12 quadrilaterals
constructed from a 5 by 4
input vertex array.
the coordinates for an m by ™m array of vertices. Figure 10-7 shows 99 a
forming a mesh of 12 quadrilaterals. etticg
When polygons are specified with more than three vertices, jt
i is
that the vertices may not all lie in one plane. This can be due to numericty te
or errors in selecting coordinate positions for the vertices. One way to han dle
situation is simply to divide the polygons into triangles. Another approach tha f
the plane parameters A, B, and C. We aon
sometimes taken is to approximate :
this with averaging methods or we can project the polygon onto the coora;
planes. Using the projection method, we take A proportional to the area of
polygon projection on the yz plane, B proportional to the projection area on _-
plane, and C proportional to the projection area on the xy plane. ma
High-quality graphics systems typically model objects with pol
meshes and set up a database of geometric and attribute information to faction
processing of the polygon facets. Fast hardware-implemented polygon renderer,
are incorporated into such systems with the capability for displaying hundreds
of thousands to one million or more shaded polygons per second (usually trian.
gles), including the application of surface texture and special lighting effects set eepRESENTATIONS
S
_ modeling packages often provide a number o i ;
sol =a resentations are useful for constructing subcteeeuneen caries
5 8 translational, rotational, or other symmetries. We can represent such ob-
Pas by specifying @ two-dimensional shape and a sweep that moves the shape
shrough @ region of space. A set of two-dimensional primitives, such as circles
per rectangles, can be provided for sweep representations as menu options.
other methods for obtaining two-dimensional figures include closed spline-
curve constructions and cross-sectional slices of solid objects.
Figure 10-53 illustrates a translational sweep. The periodic spline curve in
Fig. 10-53(@) defines the object cross section. We then perform a translational
@Pz 4
3
5
£
K
a
j
.
SPC has. sweep by moving the control points Po through p, a set distance along a straj
line path perpendicular to the plane of the cross section. At intervals along Bh,
path, we replicate the cross-sectional shape and draw a set of connecting |; this
the direction of the sweep to obtain the wireframe representation shown in Be
10-53(b).
In general, we can Specify sweep constructions using any path. For rota-
tional sweeps, we can move along a circular path through any angular distance
from 0 to 360°. For noncircular paths, we can specify the curve function 10-15
CONSTRUCTIVE SOLID-GEOMETRY METHODS ; 55 and 10-56 show examples f i ‘
ge 0-55(a), a block and pyrene gmin® ew shapes using the Section 10-15
: inte aes Pyramid are placed adjacent to each Consimuciive Solicd-Geanetry
j sation
Pe ecifyiNg z
.55(0). Figure 10-£ 6(a) shows a block and a cylinder with overlapping vol-
__ Using the intersection operation, we obtain the resulting solid in Fig. 10-
# with a difference operation, we can get the solid shown in Fig. 10-56(c).
/*", cSG application starts with an initial set of three-dimensional objects
_aaitives), such as blocks, pyramids, cylinders, cones, spheres, and closed
‘une surfaces. The primitives can be provided by the CSG package as menu se-
_or the primitives themselves could be formed using sweep methods,
" oline constructions, or other modeling procedures. To create a new three-dimen-
anal shape using CSG methods, we first select two primitives and drag them
fo position in some region of space. Then we select an operation (union, inter-
«tion, or difference) for combining the volumes of the two primitives. Now we
' lwea new object, in addition to the primitives, that we can use to form other ob-
_ ss We continue to construct new shapes, using combinations of primitives and
teobjects created at each step, until we have the final shape. An object designed
| wih this procedure is represented with a binary tree. An example tree represen-
| ton for a CSG object is given in Fig. 10-57. ’ ’
Ray-casting methods are commonly used to implement constructive solid-
or operations when objects are described with bo’ ~ are
* apply ray casting by constructing composite objects in world coordina
“th the xy plane corresponding to the pixel plane of a video monitor. This plane
Sthen referred to as the “firing plane” since we fire a ray from each pe heal
‘ through the objects that are to be combined (Fig. 10-58). We then determine
a ot c eg a tmtoreaction points accord-
the union operation, we obtain the combined object shown in Methods
BD
Figure 10-55
Combining two objects
(a) with a union operation
produces a single, composite
solid object (b).
a s for a CSG object is gi i
i i . given in }
which shows yz cross sections of two primitives and th i _
pendicular to the firing plane. For th € path of a pixel ray per
ae ee ; : e union Operation, the new volume is the
combined interior regions occupied by either or both primitives. For the intersec-
tion operation, the new volume is the interior region common to both primitives.
(b) (c) ‘ csG
| Object
pe a A Ki
ry )
oper, (2p ow
\ =
Sh
(oti, ) (abe ) (oe ) APY
Nd So — ss w
a oy ‘ ‘\ Figure 10-57 e
[ obs } | 9s) ACSG tree rep; ¥
\ Tesentati
aes object. Nation fy,
xy
obj, obj;
Pixel Ray '
Union
Intersection
Firing — tly
eee i— 5 (obj, — obj,)
2
ta)
Figure 10-38 Figure 10-59
Determining surface limits along a pixel ray.
operations using ray casting.
And a difference operation subtracts the volume of one primitive from the athe
Each primitive can be defined in its own local (modeling) Ve=> V,
2 u (10-96)
density function, p(x, y, 2), for the object, we can a
cive® “ ray from position (i, jas ype ae
Joné
uss?
my ~ Aj | PX, Yip ZZ (10-97)
he one-dimensional integral can often be approximated without actually
where gout the integration, depending on the form of the density function. The
c a ass of the CSG object is then approximated as
{fo
m~ > Mj (10-98)
mij
Other physical properties, such as center of mass and moment of inertia, can be
sbtained with similar calculations. We can improve the approximate calculations
for the values of the physical properties by taking finer subdivisions in the firing
lane. ;
If object shapes are represented with octrees, we can implement the set op-
erations in CSG procedures by scanning the tree structure describing the contents
of spatial octants. This procedure, described in the following section, searches the
xtants and suboctants of a unit cube to locate the regions occupied by the two
objects that are to be combined.
1016
Section 1
Octrees PRFAIOME NE Hay Fry MO, py in
sition (i 5 4?
my
Ea A
where the one-dimensi, :
ata inte (10-97;
carrying out the integration, 8" can
Hon, dey Often, be
total mass OF the CSC object io uPeMding on the fo PPPOxImate
then a Fern of th Without actual
ated ay © ME density funcyn The
ns >
Other physical properties, sich (10.99)
obtained with similar cajeytsct °° Center of
; mass
for the values of the physica] Pope ie improve tnemement ae Bene
y taki . 3 :
PY king fr subareas ations
fe firing,
i Fe pats BY: Scanning the mov WE SAN implement the ax
ofspatial octants. This procedans iS the tree stray describing the et P
octants and suboctants of 4 unit Gy in the following section, See est)
objects that are to be combined, *0 locate the regions ‘Occupied by the res
y the two
“onvenient representation for storing information about object interiors.
__ The octree encoding procedure for a three-dimensional space is an exten-
#ion of an encoding scheme for two-dimensional space, called quadtree encod-
‘ng: Quadtrees are generated by successively dividing a two-dimensional region
(usually a square) into quadrants, Each node in the quadtree has four data ele.
; ents, one for each of the quadrants in the region (Fig. 10-61). If all pixels within
* quadrant have the same color (a homogeneous quadrant), the corresponding
data element in the node stores that color. In addition, a flag is set in the data ele
‘Ment to indicate that the quadrant is homogeneous. Suppose all pixels in quad-
found lor code for red is then placed in
dae ote: BUS] ere ere aeteee dee
Section 10.56,
— —— Quadrant Ousarant
* 1
Guadtres Node
Region of a
Two-Dimensional
Space
Figure 10-61
Region of a two-dimensional space divided into numbered
quadrants and the associated quadtree node with four
data elements
single color specification, the quadtree has only one node. For a hetero,
region of space, the successive subdivisions into quadrants continuc.
quadrants are homogeneous. Figure 10-63 shows a quadtree representa...
region containing one area with a solid color that is different from the un
color specified for all other areas in the region. :
‘Quadtree encodings provide considerable savings in storage w'
color areas exist in a region of space, since each single-color area can -
sented with one node. For an area containing 2" by 2" pixels, a quadtree
sentation contains at most 7 levels. Each node in the quadtree has at mo:
immediate descendants.
An octree encoding scheme divides regions of three-dimensional spo«
(usually cubes) into octants and stores eight data elements in each node of the
tree (Fig. 10-64). Individual elements of a three-dimensional space are called val
ume elements, or voxels. When all voxels in an octant are of the same type, ths
Pe Representation Section 10-46
10-63
tree representation for a region
piselona solid background “aes
sone foreground.color
value is stored in the correspondin,
: 1% data eler
‘of space are ay by voxel type “void. pe ses bre Wesees
into octants, an the corresponding data element ie the node potnts
node in the octree. Procedures for generating octrees are si lr to
fo the i econ
hose fOr .quadtrees: Voxels in each octant are tested, and octant subdivisi
oF "i ant subdi -
until the region of space contains only nee oceans kash ee bh
can now have from zero to eight immediate descendants.
seers or ae ee ‘can be structured to accept definitions of
lygon mesh, curved surface patches, or solid
Using the minimum and maximum coordinate values of
;ped) around the object. This region of
is then tested, octant by octant, to
tation.
representation has been established for a solid object vari
routines can be applied to the solid, An algorithm for perforsy:
scan be applied to two octree representations for the sa
» For a union operation, a new octree is constructed with the
ns for each of the input objects. Similarly, intersection or differ- Chainer 10
ree: Dimenaloral Object
Reywesertations
ence operations are performed by looking, for regions of overlap in the tie
trees. The new octree ts then formed by either storing the ostants where the ay
Objects overlap or the region occu other
Three-dimenson pplving the try
formations to the occup! :
searching the octants from front to bac
that information can be translerred to a quadtree representation for display
10-17
BSP TREES
This representation scheme is similar to octree encoding, except we now divide
‘space into two partitions instead of eight at each step. With a binary spa
tioning (BSP) tree, we subdivide a scene into two sections at each step with
plane that can be at any position and orientation, In an octree encoding, the seine
is subdivided at each step with three mutually perpendicular planes aligned with
the Cartesian coordinate planes.
For adaptive subdivision of space, BSP trees can provide a more efficient,
partitioning since we can position and orient the cutting planes to suit the spatial
distribution of the objects. This can reduce the depth of the tree representation for
a scene, compared to an octree, and thus reduce the time to search the tree. fn.
dition, BSP trees are useful for identifying visible surfaces and for space parti.
tioning in ray-tracing algorithms.
4
The first abject detected is wale
10-18
FRACTAL-GEOMETRY METHODS
|All the object representations we have considered in the previous sections used.
Fuclidean-geometry methods; that is, object shapes were described with equa-
tions, These methods are adequate for describing manufactured objects:
that have smooth surfaces and regular shapes. But natural objects, such as moun
tains and clouds, have irregular or fragmented features, and Euclidean. nels
do not realistically model these objects. Natural objects can be realistically de
scribed with fractal-geometry methods, where procedures rather than equations
are used to model objects. As we might expect, procedurally defined objects have
characteristics quite different from objects described with equations. Fi
geometry representations for objects are commonly applied in many fields te
scribe and explain the features of natural phenomena. In computer graph
use fractal methods to generate displays of natural objects and visualizations
various mathematical and physical systems.
A fractal object has two basic characteristics: infinite detail at every
and a certain self-similarity between the object parts and the overall features
object. The self-similarity properties of an object can take different form
ject subparts. Natural objects are represented with procedures that
repeat an infinite number of times, Graphics displays of natural objects :
course, generated with a finite number of steps.
— eee. continuous Euclidean shape, no matter how 0
in view to smooth out. But if qhis standard approac
h for
Jications animated cartoon:
well, alth .
hough then is applied to othe
fiw this sequence. Real-tim there seal meepEeGL Cnet a mation ap- Sc
Pawas) display mouce eet an tons that do not &
ences in response to settings ont
as applications are generated by th
generated and sored Laey th imation, each fame of the scene is sey
consecat oy displayed in “real-tima rote nN aoe ie
(The storyboard is \ e playback” mode.
set of basic Gran fat are toni the action. It defines the motion sequence a
peproduced, the storyboard could const fe sot of ugh skaches ori cou t
ee ae ose oars oor CON cone ofa bet roxigh satches or an
he motion. “ roe
ols. And visualization app
al models. For frome-by. fran the nme
4 lutions of the numer
or they can be
‘An object definitio
Ses et definition i given foreach participant i the action. bjs can be
ME conection for each obce oe polygons or splines. In addition, the as
(A key frame Sees are specified sign withthe shape. pie
Bee grence. Within ead led drawing of the scene at a certain time in the anima-
ane for that £ ithin each key frame, each object is positioned ac n
cons oth at frame, Some key frames are chosen at extreme post
fion; others are spaced so that the time interval between ke
ccording to the
positions in the ac-
frames is not too
fat. More key frames a
y es are specified for intricate motions than f ple
ee ssjotions F 4 for intricate motions than for simple, slowly
In-t
: tweens are the intermediate frames between the key frames. The num-
per of in-betweens needed is determined by the media to be used to display the
animation. Film requires 24 frames per second, and graphics terminals are re-
freshed at the rate ‘of 30 to 60 frames per second Typically, time intervals for the
motion are set up so that there are from three to five jin-betweens for each pair of
key frames. Depending on the speed specified for the mont some key frames
can be duplicated. For a 1-minute film sequence with ne duplication, we would
need 1440 frames. With five in-betweens for each patt of key frames, we would
need 288 key frames. If the motion is not too complicated, we could space the key
frames a little farther apart
‘There are several other tasks that may be required, depending on the appli:
cation. They include motion verification, ‘editing, and production and synchro-
ization of a soundtrack. Many of the functions needed to produce general ani
ony computer-generated. Figures 16-1 ‘and 16-2 show examples of
mations are :
«s for animation sequences.
computer-generated frame
Figure 16-1
‘One frame from the award-winning
computer-animated short film Luxo
Jr. The film was designed using 2
iey-frame animation system and
cartoon animation techniques to
provide lifelike actions of the
lamps. Final images were rendered
with multiple light sources and
procedural texturing techniques:
(Courtesy of Pixar. © 1986 Pixar.) Figure 16-2
One frame from the short file Ti
‘Toy, the first computer-animated
film to win an Oscar. Designed
using a key-frame animation
system, the film also required
extensive facial expression
modeling, Final images were
rendered using procedural shading,
self-shadowing techniques, motion
blur, and texture mapping: (Courtesy
of Pixar. © 1988 Pizar)
Some steps in the development of an animation sequence are well-suited to come
puter solution. These include object manipulations and rendering, camera mo-
tions, and the generation of in-betweens. Animation packages, such as Wave.
front, for example, provide special functions for designing the animation and
processing individual objects.
One function available in animation packages is provided to store and mane
age the object database. Object shapes and associated parameters are stored and
updated in the database. Other object functions include those for motion genera
fion and those for object rendering. Motions can be generated according to speci-
fied constraints using two-dimensional or three-dimensional transformations,
Standard functions can then be applied to identify visible surfaces and apply the:
rendering algorithms.
Another typical function simulates camera movements, Standard motions
are zooming, panning, and tilting. Finally, given the specification for the ke
frames, the in-betweens can be automatically generated. 4
16-3
Sf RASTER ANIMATIONS
angles using antiali 18 Procedures, To rotate a block of pixels, we need to de.
block of raster
s Operations can be executed to I-tis -
ete