`

`1002
`
`Advanced Geometric and Raster Algorithms
`
`in the examples. A slash (/) preceding a name pushes that name onto the stack as a Literal
`object.
`In Fig. 19. 72, we build a rectangle and its Label, and draw both with a dotted line, as
`shown in Fig. 19.73. To do this, we build up the "current path" using path-construction
`operators. The first of these is the lineto operator, which adds a line from the current point
`to the specified point. The second is the charpath operator, which takes two arguments, a
`text string and a Boolean; if the Boolean is false, the outline of the text string in the current
`font is added to the current path. When the Boolean is true, the outline of the text string is
`converted to a special type of path suitable for use in dipping. (We shall see this outline text
`in the third example.) The stroke operator is used to render the current path and to begin a
`new current path. (The current path can also be rendered using the fill or eofiU operator.
`Both of these require that the path be closed. The first fills according to the nonzero
`winding rule; the second fills by the even-<XId fill rule.)
`Figure 19.74 shows how text is used for clipping; the result is shown in Fig. 19.75.
`Clipping to text requires the use of the clip path, which is another part of the POSTSCRIPT
`graphics state. Initially, the clip path encloses everything. We can create clipped objects by
`defining a smaller clip path. Here we define a procedure for drawing three horizontal strips,
`and then display them through two different clipping regions: a cubic curve, which is closed
`off using the closepath operator, and later a large piece of text. Since the clip operator
`always reduces the clipping region to the intersection of the cu.rrent clipping region and the
`current path, it i.s important to save the original clipping region so that we can restore it. Th
`do this, we use the gsave and grestore operators, which save and restore the entire graphics
`state.
`The procedure definition is somewhat arcane. The def operator expectS two argumentS
`on the stack: a name and a definition. Wh.en used to define a procedure, the name is pushed
`
`/Helvetica findfon t
`
`120 scaleront
`
`set font
`
`OO moveto
`new path
`I 00 300 moveto
`500 300 Iindo
`500 800 tineto
`I 00 800 lineto
`I 00 300 lineto
`I 00 50 moveto
`(Reclangle) raise charpa th
`
`[9 3] 0 setdasb
`stroke
`
`% Look for an object named "Helvetica"
`% previously defined.
`% Make it 120 times as big~efault font size is
`%one point
`% Make this the current font (stored as pan of
`% the "graphics s tate").
`% Move to a point on the page.
`% Begin the construction of a path.
`% Stan at location ( 100, 300).
`% Add a line to location (500, 300).
`% Continue adding line segments.
`
`% We have constructed a rectangle.
`% Move below the rectangle.
`
`% Add the text "Rectangle" to the
`% current path.
`% Set the dash-pattern to 9-on, 3-off, repeating
`% Draw the current path in this dash-pattern.
`
`Fig. 19.72 A more complex PosTSCRIPT program.
`
`TEXAS INSTRUMENTS EX. 1009 - 1064/1253
`
`

`

`

`

`1004
`
`Advanced Geometric and Rast er Algorithms
`
`/rect (
`
`/hexcb clef
`
`/w exch def
`
`w 0 rlineto
`0 h rlinelo
`w neg 0 rlineto
`
`0 h neg rlineto
`gsave
`fdl
`
`grestore
`newpath
`) clef
`
`/stripes (
`
`newpath
`I 00 300 moveto
`80050rect
`100 200 moveto
`800 50 rect
`100 I 00 moveto
`800 50rect
`) clef
`
`OO moveto
`. 95setgray
`stripes
`. 4 setgray
`gsave
`
`newpath
`50 150 moveto
`100 250 300 275 250 175
`curveto
`
`closepath
`clip
`
`stripes
`
`greslore
`
`% Define a new operator to
`% draw a rectangle whose width and height
`%are on the stack. It is invoked by "w h rect".
`% Define h as the height, the second argument
`% which is on the stack.
`% Define w as the fltSt argument from the
`%stack.
`%Draw a line by moving the pen by {w, 0).
`% Then draw a venical line. moving by (0, b).
`% Push w on the stack, negate it, push zero
`%on the stack and draw a line, moving by
`%{-w,O).
`% Same for h, closing the box.
`% Save graphics state, including clip path
`% Fill the current path, reducing the clip region
`% to a rectangle.
`% Restore the original clip path
`% Throw away the current path and stan anew.
`% This concludes the definition of rect.
`
`% Define the "stripes" operator, which
`% draws three stripes on the page. It
`% takes no arguments.
`% Go to a point on the screen.
`% Draw a rectangle.
`% Move down a little and do it again.
`
`% Do it yet again.
`% This concludes the definition of stripes.
`
`% Stan the current point at the origin .
`% Set the gray level to very pale.
`% Show the full stripes.
`%Set the gray shade a linle darker .
`% Save the current graphics state
`% (including the clip path).
`% Stan a new path at 50,150.
`
`% Draw a Bezier curve with control points
`% at (50, 150), (100, 250), (300, 275),
`% and {250, 175).
`% Close off the curve with a straight line.
`% The new clip region is the intersection
`%of the old clip region (everything) with
`% the path just constructed.
`% Draw stripes through the new clipping
`% region, slightly darker than last time.
`% Restore the original clipping path. Fig. 19.74 (Com.)
`
`TEXAS INSTRUMENTS EX. 1009 - 1066/1253
`
`

`

`19.9
`
`Page-Description Languages
`
`1005
`
`. 2 setgray
`gsave
`{Helvetica findfont
`l 00 scalefo nt setfont
`newpatb
`200 80 moveto
`{ABC) true cbarpath
`
`dosepath
`eoclip
`
`stripes
`g restor e
`
`% Darken the color further .
`
`% Create a huge Helvetica font.
`% Start a new path to clip by.
`% Get ready to write a few characters.
`% Create a path from the outline of
`% the text.
`% Close the path,
`% and make this the new clip path, using
`% the even-odd rule.
`% Draw the stripes through this.
`
`Fig. 19.74 A complex POSTSCRIPT program.
`
`draws (with the current gray-level) only where there are Is in the image; in places where
`there are Os, the raster memory is untouched. Thus, it effectively transfers the image as a
`pattern in transparent mode, except that this image can be transformed before the
`opera.tion is performed. ln fact, an image can be scaled and rotated, and any other operation
`(including clipping by the current clip path) can be applied to it.
`This last remark brings us to an important question: How are PoSTSCRIPT interpreters
`implemented? How >M>uld we draw thickened cubic splines, for example, or rotated
`images? The exact interpretation is not specified in the POSTSCRIPT lAnguage Reference
`Manual [ADOB85b], because the implementation must necessarily be different for different
`classes of printers (and for displays). Still, certain aspects of the imaging model are given
`explicitly. Curves are drawn by being divided into very short line segments. These segments
`are then thickened to the appropriate width and are drawn, producing a thick curve. Thus,
`thick lines have small notches in their sides if they are very wide, and the polygonizatioo of
`
`I
`
`r -
`
`,.
`
`. • "!''"
`
`ABC -
`
`Fig. 19 .75 PosTSCRIPT allows general clipping, even using text outlines as a clip path,
`as shown by this output from the third PosTSCRIPT program.
`
`TEXAS INSTRUMENTS EX. 1009 - 1067/1253
`
`

`

`1006
`
`Advanced Geometric and Raster Algorithms
`
`the curves is coarse (this, too, is user definable). Note that, in PoSTSCRIPT, the line width is
`a geometric rather than cosmetic attribute, in the sense that it is defined in some coordinate
`system and can later be transformed. If we set the line width and then scale the current
`transformation by 2, all subsequent lines are drawn twice as thick.
`POSTSCRIPT images apparently are transformed by affine maps using a technique
`similar to the two-pass transform. An image is defined, in the imaging model, as a grid of
`tiny squares, so a transformed image is drawn by rendering many small qudrilaterals. The
`method used for clipping by an arbitrary path is not stated so explicitly, but it appears that
`simple span arithmetic is performed in some implementations: The clipping region is
`represented by a collection of horizontal spans, each primitive is scan-converted row by
`row, and then only those pixels lying within the spans are actually painted. Much of the
`remaining implementation of the language amounts to a massive bookkeeping task; the
`current clip region, the current path, and the various fiU styles must all be maintained, as
`well as the raster memory and the current transformation matrix.
`
`19.10 SUMMARY
`
`We have discussed some of the geometric and raster algorithms and data structures in use
`today, as well as their use in implementing v.rrious raster packages, including page(cid:173)
`description languages. ~-pite the considerable sophistication of many of these algorithms,
`work continues to be done on these topics. Geometric clipping (and its extension to 30,
`which is used in polyhedral constructive solid geometry) is a subject of active research, and
`new scan-conversion algorithms, especially with antialiasing, are still appearing frequently
`in the literature.
`One lesson to be drawn from the algorithms is that simplicity may be more important
`than sophistication in many cases. Scissoring is a widely used clipping technique, the shape
`data structure makes many operations trivial, and the implementation of bitBit we described
`has, as its core, the idea of making short and simple code that can be executed in a cache.
`
`EXERCISES
`19.1 Improve the implementation of the Nichoii-Lee-Nicholl line-clipping algorithm by making as
`much repeated use of intermediate results as possible. Implement all the cases.
`19.2 The Liang- Barsky polygon-clipping algorithm described in the text may produce degenerate
`edges (so may the Sutherland-Hodgman algorithm described in Chapter 3). Develop an algorithm
`that takes the list of edges genemted by the algorithm and ''cancels" any tv.u successive edges that
`have opposite directions, and is then applied recursively. The algorithm is made simple by the
`observation that such edge pairs must be either vertical or horizontal. Explain why this is true. Note
`that )QUr algorithm should require no arithmetic except comparisons.
`Also develop an algorithm to split the polygon into multiple output polygons if necessary, so that
`no tv.u output polygons intersect. This may be done by applying the first algorithm to the output
`polygon, and then scanning the result for closed components. To test whether your algorithm works,
`apply it to several polygons that repeatedly go from one comer region to the adjacent or opposite one.
`19.3 Reimplement the Liang-Barsky polygon-clipping algorithm without the use of infinity, by
`making special cases of horizontal and vertical lines.
`
`TEXAS INSTRUMENTS EX. 1009 - 1068/1253
`
`

`

`Exercises
`
`1007
`
`19.4 Write an algorithm to convert a polygon in the plane, specified by a list of vertices, into the data
`structure for a contour described in the Weiler pol &)On-clipping algorithm. Extend your algorithm to
`-.wrlc for polygons with boles, specified by multiple paths.
`19.5 Suppose that you are given a set and a partial ordering (called conrained in) on the set: For any
`11M:> elements, A and 8 , A is contained in 8 , 8 is contained in A, or neither A nor 8 is contained in the
`other. (This partial order has nothing to do with the elemenr-ofrelation in set theory.)
`Design an algorithm that constructs a binary tree whose nodes are labeled by the elements of the
`set, and that has the following 11M:> properties: The left child of a node is always contained in the node,
`whereas the right child of a node (which may be NULL) neither is contained in nor contains the
`parent. A good algorithm for constructing this tree can be used to improve the postprocessing step in
`the Weiler polygon algorithm, where the containedlc<lCJlists structure of the contours must be
`determined.
`19.6 Show by example that finding an integer starting point for a line with actual endpoint (x,, y0) as
`done in the text can give a different choice from (Round(x,), Round(y0)). Which choice is better, and
`why?
`19.7 Suppose we have chosen to allow quarter-pixel resolution for endpoints of line segments, and
`that we consider the line from (0, 0) to (40, 1). Consider the portion of the line between x = 15 and
`x = 40. Show that, if we clip first and then compute the line equation from the clipped endpoints
`(after rounding to quarter-integers) and scan convert, the result will be different from that obtained by
`clipping, then using the rounded value of one clipped end as a start point, and scan converting using
`the equation of the original line.
`19.8 Complete the ellipse specification given in Section 19.2.6 as follows. Let
`
`C) = cos(r) (~) + sin(/) (~:).
`
`Solve this equation for cos(r) and for sin(r) in terms of x, y, P., P,, Q,, and Q,. Now use the identity
`cos•t + sin7 = I to create a single equation in x. y, P.. P,. Q. and Q,. Express this equation in the form
`Ax• + Bxy + Cy• + Dx + Ey + F = 0, and thus derive formulae for the coefficients A, B, C, D, E,
`and F in terms of P. .• P,. Q., and Q,. Your answers for D and E should be zero.
`19.9 Describe methods for specifying hyperbolas and parabolas, and for computing the coefficients
`of the conic from the spec.ification. One way to specify a hyperbola is to describe a parallelogram. The
`long diagonal of the parallelogram is the axis of the hyperbQia, the two vertices of the hyperbola lie at
`the endpoints of this diagonal (the vertices are the points on the two branches of the hyperbola that are
`closest to each other), and the asymptotes are parallel to the sides of the parallelogram. A parabola
`can be specified by giving a focus (a point), a directrix (a line), and one point on the parabola, but this
`is not very intuitive. Can you come up with something better?
`19.10 Compute the table of increments for the Van Aleen conic algorithm. These are the increments
`in the decision variables for square and diagonal moves in each drawing octant. Show that the code
`that handles the fust and second drawing octants actually will work for every odd or even octant.
`19.11 Show that the three different error measures for circles give the same pixel selections when the
`radius and coonlinates of the center of the circle are integers. This is simplest if you assume that tbe
`pixel under consideration satisfies x ~ 0, andy~ x. (All other cases can be derived from this one by
`symmetry.) The radial error measure selects bet,_n (x, y) and (x. y- I) by evaluating F(x, y) =
`x• + yl - r • at each of the 11M:> points and choosing the one where the absolute value ofF is smaller.
`The axial error measure uses y' = vr•- x 2; both y- y' and (y -
`I) - y' are computed. The one
`with smaller absolute value is selected. The midpoint error measure selects (,t, y) or (x, y - 1),
`depending on whether the value of F(x. y - 0.5) is negative or positive. What choice do you have to
`make to ensure that the three ambiguous cases agree (i.e., the cases where F(x, y) = F(x, y- 1),
`
`TEXAS INSTRUMENTS EX. 1009 - 1069/1253
`
`

`

`1008
`
`Advanced Geometric and Raster Algorithms
`
`where y - y - 0.5, and where F(x, y - 0 .5) = 0)? Or is there no consistent cboice? At least show
`lhat. in the ambiguous cases, lhere is some pixel !bat minimizes all three measures of error.
`19.12 Study the circle of radius v'7 centered at the origin by scan convening it with any algorithm
`you choose. Is the result aesthetically pleasing? What happens if you move the center to <t. 0)? Are
`the sharp comers in the scan-convened ven;ion irritating? Should circle algorithms try to make
`curvature constant rather than minimizing distances? This circle, along with a few othen; whose
`squared radii are integers, is panicuiJirly troublesome. Mcilroy (MCIL83) shows that the next case
`with such sharp comers is r 1
`• 7141 .
`
`19 .13 Complete the VanAken conic algorithm by adding the portion lhat finishes the conic in the
`last dnrwing octant.
`19.14 Improve the VanAken conic algorithm by adding ached: for octant jumps. DaSilva rDASI88)
`recommends using the decision variable to decide which pixel to draw next, but then checking to see
`whether that pixel has jumped over an octant. If it has, the alternate pixel is chosen instead.
`
`19.15 Write a general line-drawing algorithm. Your algorithm should handle the ease where the
`coordinates of the endpoints are rational numbers with a fixed denominator, p. Be certain that if you
`draw two lines !bat share an endpoint, the rasterized lines have the identical endpoints as well.
`Initializing the decision variable may be the most difficult pan of the algorithm.
`19. 16 By considering the line from (0, 0) to (4, 2) and the line from (4, 2) to (0, 0), show th8l the
`midpoint algorithm described in Chapter 3 can draw different pixels, depending on the direction in
`which the line is specified. Find a way to examine the coordinates of the endpoints of a line and to
`adjust the comparison (from less than to less than or equal to) in the midpoint algorithm so that the
`same piJleiS are always drawn, regardless of the order in which the endpoints of a segment are
`specified.
`
`19.17 Create a line-drawing algorithm to draw the ponion of a line (specified by M> endpoints) that
`lies between two vertical lines. That is , your procedure should look like TrimmedLine (point start,
`point tnd, lnt xmin , bat xma.r); and should draw tbe ponion oftbe line segment between start and ~nd
`tb8l lies between xmin and xmax. Implement this algorithm with scissoring, and then with analytic
`clipping. When doing analytic clipping, be sure to derive tbe decision variable and iDCTements from
`the original line, not from the rounded clipped endpoints.
`
`19.18 Explain why a tightly bent curve is difficult to draw with forward-differencing techniques .
`Explain the problem as a form of aliasing .
`
`19.19 Trace the recun;ive fill algorithm through a complete example to be sure you understand it.
`What are the subtle cases in the algorithm?
`19.20 Implement tbe recwsive fill algorithm. You can implement it and then execute it on a
`conventional video terminal, as long as it is cursoc-addressable, by using characters to represent
`different pixel values. Implement both bound8J)' fill and flood fill .
`19.21 Show how to construct a mitered joint between two lines using the shape algebra; that is,
`describe a union, intersection, or difference of shapes that will produce a mitered joint. Do the same
`for a trimmed mitered joint.
`19.22 Develop algorithms for determining the difference between two shapes and the union of two
`shapes by describing the high-level algorithm io terms of an " 'Overlap" function, and then
`describing the values returned by the overlllp function.
`19.23 Implement tbe improvements to the filling algorithms described in the text. What happens if
`stack processing is done on a firsl· in· first-out basis, instead of on a last-in-first-out one? Can you
`think of frame-buffer architectures in whicll tbe firs~ approach is better or worse?
`
`TEXAS INSTRUMENTS EX. 1009 - 1070/1253
`
`

`

`Exercises
`
`1009
`
`19.24 Consider the two filled circles defined by the equations (x- tOOf + y• = 10000.9801 and
`(x + tOO)'+ y' = 10000.9801. Show that , if we scan convert these circles, each generates a pixel at
`(0, 2); hence, the pixel (0, 2) is contained in the shape data structure for each. Show, on the other
`hand, that the intersection of these two circles contains only points between y = - 1 andy= I, and
`hence should not contain the pixel (0, 2). Is the shape algebra a good way to implement intersections
`despite this apparent contradiction? Explain the circumstances in which you would accept the shape
`intersection as a reasonable approximation of the true intersection of geometric primitives.
`19.25 In Section 19. 1, we talked about determining the side of a ray on which a given point lies.
`Suppose we have a ray from P to Q, and a point, R.
`a. Show that a ray 90" clockwise from the r'dy from P to Q is given by (-Q, + P,. Q, - PJ.
`b. Explain why R is to the left of the ray from P to Q only if the vector from P to R lies in the
`same halfplane as does the vector computed in part a.
`c. Two vectors lie in the same halfplane only if their dot product is positive. Use this fact to
`show that R lies to the left of the ray from P to Q if and only if
`(R, - P,)(-Q, + P,) + (R,- P,)(Q,- P.l
`
`is positive.
`19.26 Implement the simpler antialiasing algorithm for the circle described in Section 19.3.2. You
`wiU need some preliminary computations.
`a. Show that, for large enough Rand small Y'oilues of s. a point (x. y) at a distances outside a
`circle of radius R has a residual value, F(x. y) = x' + y'- R', which is approximately 2Rs.
`(Hint: To say that the point is distances outside the circle is tile same as saying its distance
`to the origin is R + s.)
`b. Compute a table of weighted overlap values for a disk of rad.ius I and a halfplane; make the
`table have 32 entries, corresponding to distances between - I and I pixel (a distance of- I
`means the pixel center is one unit inside the halfplane).
`c. Now write a scan-conversion algorithm as follows. For each pixel near the circle of radius
`R (determine these pixels using a midpoint-style algorithm), compute the residual and
`divide by 2R to get the distance. Use this to index into the table of overlap values; use the
`distance minus I to index into the table as well, and subtract to get a coverage value.
`d. Try your algorithm on both large and smaU circles, and criticize the performance for small
`circles.
`19.27 Suppose you are given a circle in the plane, with an equation of the form (x- h'/ + (y- k)'(cid:173)
`R' = 0. Describe how to detect whether a point (x. y) lies within the circle. Describe how to determine
`if a point lies within a distance or one from the circle. Now do the same two problems for an eUipse
`given by Ax2 + 2Bxy + cy• + Ox + Ey + F = 0. The second problem is much harder in this case,
`because of the difficult formula for the distance. Suppose that instead you estimate the distance from a
`IJZ) I F 2• and
`point (x, y) to the ellipse as follows: multiply the residual at the point (x, y) by (AC -
`check whether this value is between 0.99 and 1.01. Explain why this might make a reasonable
`measure of closeness to the ellipse.
`19.28 a. Consider the set of points on the x-axis bet~n -tandt. together with the set of points
`on the y axis between -tandt. We include only one of the two endpoints in each of these
`intervals. Since this has the shape of a "+" sign, we will call the shape P. Show that the
`midpoint algorithms we have discussed wiU dr11W the pixel at (0, 0) precisely if the
`primitive intersects P. (Note that P contains only tv.'O of its four possible endpoints. The
`decision or which two to include amounts to the decision to count an exact midpoint
`crossing of a horizontal line as contributing the left or the right pixel, and similarly for
`
`TEXAS INSTRUMENTS EX. 1009 - 1071/1253
`
`

`

`1010
`
`Advanced Geometric and Raster Algorithms
`
`YCrticaJ midpoint crossings. Be sure that )'OUt choice of endpoiniS for P corresponds to the
`algorithm you are studying.)
`b. Analogously, a pixel Q is drawn by a midpoint algorittun precisely if the primitive
`interseciS a copy of P that has been translated to have itS center at Q. Show that a circle of
`radius 0.49, centered at (0.5. 0.5), therefore causes no pixel to be drawn.
`c. Alternative shapes have been proposed instead of P, including the convex hull of P, and a
`square box around o pixel. Criticize each of these choices.
`19.29 The Posch-Fellner style algorithm for drawing thick curves can be improved somewhat.
`lnstead of considering a circle swcpc along a curve, consider a~~~ pt>lygon [HOBB89]. A pen polygon
`is characterized by two properties: opposite sides are parallel. and if the polygon is translated so that
`one •utcx of an edge lies at the origin, then the line containing the opposite edge must pass through a
`point with imeger coordinates. For example. an octagOn with vertices :!:(I, t >. :!:(t. 1), :!:(-t, 1),
`and :!:(- I , t> is a pen polygon. Compute the points on a curve through the origin with slope 0.935
`using the Posch-Fellner algorithm (with a width of 2) and the pen-polygon algorithm, using the
`octagonal pen. In general, thick lines drawn with pen polygons have a more uniform appearunce.
`
`TEXAS INSTRUMENTS EX. 1009 - 1072/1253
`
`

`

`20
`Advanced
`Modeling
`Techniques
`
`Earlier chapters have concentrated on geometric models, including transforming and
`rendering them. In a world made entirely of simple geometric objects, these models would
`suffice. But many natural phenomena are not efficiently represented by geometric models,
`at least not on a large scale. Fog, for example, is made up of tiny drops of water, but using a
`model in which each drop must be individuaUy placed is out of the question. Furthermore,
`this water-drop model does not accurately represent our perception of fog: We see fog as a
`blur in the air in front of us, not as millions of drops. Our visual perception of fog is based
`on how fog alters the light reaching our eyes, not on the shape or placement of the
`individual drops. Thus, to model the perceptual effect of fog efficiently, we need a different
`model. In the same way, the shape of a leaf of a tree may be modeled with polygons and its
`stem may be modeled with a spline tube, but to place explicitly every limb, branch, twig,
`and leaf of a tree would be impossibly time consuming and cumbersome.
`It is not only natural phenomena that resist geometric modeling. Giving an explicit
`description of the Brooklyn Bridge is also challenging. Much of the detail in the bridge is in
`rivets, nuts, and bolts. These are not placed in the same location on every strut or cable, so
`primitive instancing cannot be used; rather, they are placed in ways that can be determined
`from the locations of the struts or cables (for example, two cables whose ends abut need a
`coupler between them).
`The advanced modeling techniques in this chapter attempt to go beyond geometric
`modeling, to allow simple modeling of complex phenomena. Typically, this means
`representing a large class of objects by a single model with easily adjusted and intuitive
`parameters. Thus, the list of parameters becomes the data from which the model is
`generated. This technique has been called database amplification [SMIT84), a term
`
`101 1
`
`TEXAS INSTRUMENTS EX. 1009 - 1073/1253
`
`

`

`101 2
`
`Advanced Modeling Techniques
`
`,
`
`accurately describing our desire to model elaborate entities that are quite uniform at high
`levels of detail (e.g., fog, bridges, fire, plants).
`Some of the techniques lie somewhere between the extremes of explicit modeling and
`database amplification, such as the hierarchical splines of [FORS88], and the blobby
`objects of [BLJN82b] and soft objects of [WYVI86]. Hierarchical splines are surface
`patches having varying densities in their control-point meshes. In regions where the object
`to be modeled has few features, a coarse mesh is used. In regions with lots of detail, finer
`meshes subdivide a single rectangle in the coarser mesh. Thus, a modest amount of
`information (the control points and subdivision hierarchy) describes the shape of the full
`surface. The blobby and soft objects are again controlled by locating a few objects and then
`"blending" them together to form a complex object. The few objects (spheres or blobs of
`soft material) still required must be placed, but their intersections are smoothed out
`automatically, freeing the user from having to define fillets explicitly at each object
`intersection.
`Some of the techniques presented here are widely applicable; procedural models,
`fractals, grammar-based models, and particle systems have all been used to model a wide
`variety of things. Some of them are special purpose; for example, the ocean-wave models.
`Nonetheless, many of the models presented here give good pictures without being faithful to
`the underlying science. The clouds modeled as textured quadrics by Gardner [GARD84]
`are based not on atmospheric science, but rather on appearances; the water modeled by
`blobby objects has no basis in the physics of surface tension and the dynamics of water
`molecules. It is important to recognize the difference between these approaches to mod.eling
`and modeling based on the underlying science.
`For each modeling technique, new methods of rendering may be required. In
`discussing a new modeling technique, we therefore introduce any new rendering techniques
`developed for its use. In one case, volume rendering, the modeling (which consists of the
`assignment of a value to each point in a 30 region) is not new at all. Scalar fields have been
`used in physics and mathematics for hundred of years, but only recently have attempts been
`made to render these fields on 20 images.
`Finally, many of the methods presented here have been developed for dynamic models
`rather than for static ones, and for modeling growth and change as well as form. The
`individual images produced from these models are of interest, but the fuU power of the
`modeling technique comes out when several still images are combined in an animated
`sequence. Some of the topics covered in this chapter thus concern both object modeling and
`animation.
`
`20.1 EXTENSIONS OF PREVIOUS TECHNIQUES
`
`Before starting our survey of new techniques for modeling natural and artificial objects, we
`discuss two extensions to our previous modeling techniques: hierarchical splines and
`noise-based pattern mapping. Neither of these handles any shapes or characteristics that we
`could not model before, but each makes the modeling a great deal simpler. Hierarchical
`splines make it unnecessary to place many control points in regions with little detail (as
`would have to be done if a uniformly fine control mesh were used), and noise-based patterns
`are simply particularly interesting patterns to map onto conventional objects.
`
`TEXAS INSTRUMENTS EX. 1009 - 1074/1253
`
`

`

`20.1
`
`Extensions of Previous Techniques
`/
`
`1013
`
`20.1 . 1 Advanced Modeling with Splines
`
`With the tensor-product spline-patch surfaces defined in Chapter II , more control vertices
`must be added to gain a higher level of detail. The Oslo algorithm and its descendents
`[COHE80; BART87] can be applied to the control mesh of such splines to produce new
`control meshes with more vertices but identical resulting surfaces. This refinement of the
`cont.rol mesh is shown for a line spline in Fig. 20.1. The circled black dots control the shape
`of the thickened segment in the figure; if one of these i.s moved, the shape of the thickened
`segment changes. But bow many control vertices do we need to redraw tbe arc in its changed
`form? For tbe portions outside the thickened segment, we can use the (comparatively few)
`white vertices; for tbe portion inside the thickened segment, we can use the circled black
`vertices. This localization of detail is the fundamental notion of hierarchical B-spline
`modeling developed by Forsey and Bartels [FORS88].
`Two problems arise: maintaining a data structure for the hierarchical spline, and
`altering the large-scale spline without damaging the small-scale one. These two problems
`can be solved together. We wish to alter the large-scale spline so that the small-scale spline
`follows the alteration. We do this alteration by describing the locations of tbe (adjustable)
`control vertices for the small-scale spline in a coordinate system based on the larger spline.
`This prescribes the data structure for the splines as well- a tree in which the control
`vertices of each spline are specified in coordinates based on its parent node in the tree. The
`initial position of each control vertex defines the origin of its coordinate system, and the
`displacements along the normal to the large spline and in the directions tangent to the
`coordinate curves of the large spline determine a basis for this coordinate system. Thus,
`when the large spline is altered, the origin and basis vectors for the displacement coordinate
`system are moved as well.
`Figure 20.2 shows how this procedure works for a line spline. Color Plate IV.4(a) is an
`example of the impressive results this technique can yield. Notice that the final object is just
`a union of portions of various spline patches, so the conventional rendering techniques that
`can handle splines (including polygonal and ray-tracing renderers) can be adapted to render
`these objects. About 500 control nodes. each of which contains a parametric position, a
`level of overlay (i.e., depth in the heirarchy) and an offset, were used to define the dragon's
`head. By def