Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`Pyramidal Parametrics
`
`Lance Williams
`
`Computer Graphics Laboratory
`New York Institute of Technology
`Old Westbury, New York
`
`Abstract
`
`The mapping of images onto surfaces
`may substantially increase the realism and
`information content of computer-generated
`imagery.
`The projection of a flat source
`image onto a curved surface may
`involve
`sampling difficulties, however, which are
`compounded as
`the view of
`the surface
`changes.
`As
`the projected scale of the
`surface increases,
`interpolation between
`the original samples of the source image
`is necessary~ as
`the scale
`is
`reduced,
`approximation of multiple samples in the
`source is required.
`Thus
`a constantly
`changing sampling window of view-dependent
`shape must traverse the source image .
`
`To reduce the computation implied by
`thes·e
`requirements,
`a set of prefiltered
`source
`images may be
`created .
`This
`approach can be applied
`to particular
`advantage
`in animation, where
`a
`large
`number of
`frames using
`the same source
`image must be generated.
`This
`paper
`advances
`a
`"pyramidal parametric" pre(cid:173)
`filtering and
`sampling geometry which
`minimizes aliasing effects and assures
`continuity with i n and
`between
`target
`images.
`
`Although the mapping of texture onto
`surfaces
`is an excellent example of the
`process and provided the original motiva(cid:173)
`tion
`for
`its
`development, pyramidal
`parametric data structures admit of wider
`application.
`The aliasing of not only
`surface texture, but also highlights and
`even
`the surface representations
`them(cid:173)
`selves, may be minimized by pyramidal
`parametric means.
`
`General Terms: Algorithms.
`
`Antialiasing,
`Phrases:
`and
`Keywords
`Illumination Models, Modeling, Pyramidal
`Data Structures, Reflectance Mapping, Tex(cid:173)
`ture Mapping, Visible Surface Algorithms.
`
`CR CateJories: I.3.3 [Computer Graphics]:
`Picture Image Generation--display algo(cid:173)
`rithms~ I . 3 . 5 [Computer Graphics]: Compu(cid:173)
`tational Geometry and Object Modeling-(cid:173)
`curve, surface, solid and object represen(cid:173)
`tations, geometric algorithms, languages
`and systems:
`I.3.7
`[Computer Graphics]:
`Three-Dimensional Graphics and Realism-(cid:173)
`color, shading, shadowing, and texture.
`
`1. Pyramidal Data Structures
`
`be
`Pyramidal data structures may
`based on various subdivisions:
`binary
`trees, quad
`trees, oct
`trees, or
`n(cid:173)
`dimensional hierarchies [17]. The common
`feature of these structures is a
`succes(cid:173)
`sion of
`levels which vary the resolution
`at which the data is represented .
`
`image by
`The decomposition of an
`two-dimensional binary subdivision was a
`pioneering strategy in computer graphics
`for visible surface determination [15].
`The approach was essentially a
`synthesis(cid:173)
`by-analysis:
`the
`image plane was subdi(cid:173)
`vided
`into quadrants
`recursively until
`analysis of a subsection showed that sur(cid:173)
`face ordering was sufficiently simple
`to
`permit
`rendering.
`Such
`subd i vision and
`analysis has been subsequently adopted
`to
`generate
`spatial data structures [5],
`which have beep used to represent
`images
`[9] both for pattern recognition [13] and
`for transmission [10], [14].
`In the field
`of computer graphics, such data structures
`have been adopted for texture mapping [4],
`[16], and generalized to represent objects
`in space [ 11 J.
`
`to
`The application of pyramidal data
`image storage and transmission may permit
`significant compression of the data to be
`stored or transmitted. This is so because
`highly detailed features may be
`localized
`within an otherwise low-frequency image,
`permitting the sampling rate to be reduced
`for
`large sections of the image. Besides
`permitting bandwidth
`compression,
`the
`representation orders data in such a way
`that the general character of
`images may
`be
`recalled or
`transmitted before
`the
`specific details .
`
`Pattern recognition and classifica(cid:173)
`tion often require
`the comparison of a
`candidate image against a set of canonical
`patterns.
`This
`is an operation
`the
`expense of which increases as
`the square
`of
`the
`resolution at which it is per(cid:173)
`formed . The use of pyramidal data struc(cid:173)
`tures in pattern recognition and classifi(cid:173)
`cation permits the comparison of the gross
`features
`of
`two-dimensional
`functions
`preliminary to the minute particulars~ a
`good general reference on this application
`is [12] .
`
`Permission to copy without fee all or part of this material is granted
`provided that the copies are not made or distributed for direct
`commercial advantage, the ACM copyright notice and the title of the
`
`publication and its date appear, and notice is given that copying is by
`permission of the Association for Computing Machinery. To copy
`otherwise, or to republish, requires a fee and / or specific permission.
`
`© AC M 0-89791 - 109- 1/8 3100710001 $00.75
`
`0001
`
`Volkswagen 1013
`
`

`
`Computer Graphics
`
`Volume 17. Number 3
`
`July 1983
`
`tex(cid:173)
`In computer graphics, pyramidal
`ture maps may be used to perform arbitrary
`mappings of a function with minimal alias(cid:173)
`ing artifacts and
`reduced computation.
`Once again, images may be
`represented at
`different spatial bandwidths. The concern
`is
`that
`inappropriate
`resolution
`misrepresents
`the data: that is, sampling
`high-resolution data at
`larger
`sample
`intervals invites aliasing.
`
`2. Parametric Interpolation
`
`By a pyramidal parametric data struc(cid:173)
`ture, we will mean
`simply a pyramidal
`structure with both intra- and inter-level
`interpolation .
`Consider
`the case of an
`image
`represented as
`a
`two-dimensional
`array of samples .
`Interpolation is neces(cid:173)
`sary to produce a continuous
`function of
`two parameters, U and v.
`If, in addition,
`a third parameter (call it D) moves us up
`and down
`a hierarchy of corresponding
`two-dimensional functions, with interpola(cid:173)
`tion between (or among) the levels of the
`pyramid providing continuity,
`the struc(cid:173)
`ture is pyramidal parametric.
`
`between
`~e practical distinction
`such a structure and an ordinary interpo(cid:173)
`lant over an n-dimensional array of sam(cid:173)
`ples
`is
`that
`the number of samples
`representing each level of the pyramid may
`be different.
`
`3 . Mip Mapping
`
`format
`"Mip" mapping is a particular
`two-dimensional parametric functions,
`for
`which, along with its associated address(cid:173)
`ing
`scheme, has been used successfully to
`bandlimit
`texture mapping at New York
`Institute of Technology since 1979 . The
`acronym "mip" is
`from
`the Latin phrase
`"multum in parvo," meaning "many things in
`a small place." Mip mapping
`supplements
`bilinear
`interpolation of pixel values in
`the texture map
`(which may be used
`to
`smoothly
`translate and magnify the tex(cid:173)
`ture) with interpolation between prefil(cid:173)
`tered versions of
`the map (which may be
`used to compress many pixels into a
`small
`place) .
`In
`this
`latter capacity, mip
`offers much greater speed
`than
`texturing
`algorithms which perform explicit convolu(cid:173)
`tion over an area in the texture map
`for
`each pixel rendered [1], [6] .
`
`in compressing
`its speed
`Mip owes
`First, a fair
`texture
`to
`two
`factors.
`amount of filtering of the original
`tex(cid:173)
`ture takes place when the mip map is first
`created. Second, subsequent filtering
`is
`approximated by blending different levels
`of the mip map.
`This means
`that all
`filters
`are
`approximated by
`linearly
`interpolating a set of square box filters,
`the sides of which are powers-of-two pix(cid:173)
`els in length. Thus, mapping entails a
`fixed overhead, which
`is independent of
`the area filtered to compute a sample.
`
`2
`
`0002
`
`Q
`
`Figure (1)
`Structure of a Color Mip Map
`into
`Smaller and smaller images diminish
`the upper left corner of the map. Each of
`the
`images
`is averaged down
`from
`its
`larger predecessor.
`
`(Below:)
`Mip maps are indexed by three coordinates:
`U, V, and D. U and V are spatial coordi(cid:173)
`nates of the map: D is the variable used
`to
`index,
`and
`interpolate between, th~
`different levels of the pyramid.
`
`v
`
`v
`
`,~
`
`v
`
`v
`
`D
`
`the memory
`illustrates
`1)
`Figure
`organization of a color mip map. The
`image is separated into its red, green,
`and blue components
`(R, G, and B in the
`diagram). Successively filtered and down(cid:173)
`sampled versions of each component are
`instanced above and to
`the
`left of
`the
`originals,
`in a
`series of smaller and
`smaller
`images, each half
`the
`linear
`dimension
`(and
`a quarter
`the number of
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`samples) of its parent. Successive divi(cid:173)
`sions by
`four partition the frame buffer
`equally among the three components, with a
`single unused pixel remaining in the upper
`left-hand corner.
`
`The concept behind this memory organ(cid:173)
`ization is that corresponding points in
`different
`prefiltered maps
`can
`be
`addressed
`simply by a binary shift of an
`input U, V coordinate pair.
`Since
`the
`filtering and
`sampling are performed at
`scales which are powers of
`two,
`indexing
`the maps
`is possible with
`inexpensive
`binary scaling.
`In a hardware implementa(cid:173)
`tion, the addresses in all the correspond(cid:173)
`ing maps (now separate memories) would be
`instantly
`and
`simultaneously available
`from the U, V input.
`
`The routines for creating and access(cid:173)
`ing mip maps at NYIT are based on simple
`box (Fourier) window prefiltering, bil(cid:173)
`inear
`interpolation of pixels within each
`map
`instance, and
`linear
`interpolation
`between
`two maps for each value of D (the
`pyramid's vertical coordinate). For each
`of
`the
`three components of a color mip
`map, this requires 8 pixel
`reads and 7
`multiplications .
`This choice of filters
`is strictly for the sake of speed.
`Note
`that
`the bilinear interpolation of pixel
`values at the extreme edges of each map
`instance must be performed with pixels
`from the opposite edge(s) of that map, for
`texture which
`is periodic.
`For non(cid:173)
`periodic texture, scaling or clipping of
`the U, V coordinates prevents the intru(cid:173)
`sion of an inappropriate map or color com(cid:173)
`ponent into the interpolation.
`
`to
`(Fourier) window used
`The box
`create
`the mip maps illustrated here, and
`the tent (Bartlett) window used to
`inter(cid:173)
`polate them, are far from ideal; yet prob(cid:173)
`ably the most severe compromise made by
`mip
`filtering
`is that it is symmetrical.
`Each of the prefiltered levels of the map
`is filtered equally in X and Y. Choosing
`a value of D trades off aliasing against
`blurring, which becomes a tricky proposi(cid:173)
`tion as a pixel's projection in
`the
`tex(cid:173)
`ture map deviates from symmetry. Heckbert
`[8] suggests:
`
`d =max (v{~)2+{fx)2 •J{g~)2+{~)'
`
`where D is proportional to the "diameter"
`of the area in the texture to be filtered,
`and the partials of U and V (the
`texture(cid:173)
`map coordinates) with respect to X and Y
`(the screen coordinates) can be calculated
`from the surface projection .
`
`Illustrations of mapping performed by
`the mip technique are the subject of Fig(cid:173)
`ures {2) through {10). The NYIT Test Frog
`in Figure (2) is magnified by simple point
`sampling in (3), and by
`interpolation
`in
`(4).
`The hapless amphibian is similarly
`
`Figure (2)
`Mip map of the flexible NYIT Test Frog.
`
`compressed by point sampling in (5) and by
`mipping in ( 6) .
`
`The more general and interesting case
`continuously variable upsampling and
`downsampling of the original texture -- is
`(7) on a variety of sur(cid:173)
`illustrated
`in
`faces. Since the symmetry of mip filter(cid:173)
`ing would be expected
`to show up badly
`when texture is compressed
`in only one
`dimension, figures (B) through (10) are of
`especial
`interest .
`These
`pictures,
`created by Ed Emshwiller at NYIT for his
`videotape, "Sunstone," were mapped using
`Alvy Ray Smith's TEXAS animation program,
`which in turn used MIP to antialias
`tex(cid:173)
`ture.
`As
`the panels rotate edge-on, the
`collapses to a line smoothly and
`
`...... rent artifacts .
`
`,
`
`,
`
`.........
`
`,
`
`...
`
`~,·
`
`p
`
`,
`
`...
`
`i ...
`
`.,
`
`.,
`
`........
`
`~-
`
`....... ,• -
`
`.,
`
`,
`
`I
`
`AI
`t(/
`.,
`
`,~~ ;
`,
`
`,.
`
`,
`
`.,
`
`,
`
`,
`
`,.
`
`,
`
`p
`
`p
`
`,
`
`,.
`
`interpolation and
`General mapping:
`pyramidal compression.
`
`-.
`0 ..... --
`
`,
`
`,.
`
`"'
`
`,
`
`,.
`
`3
`
`0003
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`Figure (3)
`Upsampling the frog: magnification by
`
`Figure (4)
`Upsampling the frog: magnification by
`
`Fiqure l6}
`Downsampling: compression by pyramidal interpolation (detail, right).
`
`4
`
`0004
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`Figures (8)-(9)
`"Sunstone" by Ed Emshwiller, segment animated by Alvy Ray Smith
`Pyramidal parametric texture mapping on polygons .
`
`5
`
`0005
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`july 1983
`
`Figures (10)-(ll)
`"Sunstone" by Ed Emshwiller, segment animated by Alvy Ray Smith
`Pyramidal parametric texture mapping on polygons.
`
`6
`
`0006
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`4 . Highlight Antialiasing
`
`As small or highly curved objects
`move across
`a raster, their surface nor(cid:173)
`mals may beat erratically with
`the
`sam(cid:173)
`pling
`grid .
`This causes
`the shading
`values
`to
`flash annoyingly
`in motion
`sequences,
`a
`symptom of
`illumination
`aliasing. The surface normals essentially
`point-sample the illumination function.
`
`illustrates samples of
`Figure (12)
`the surface normals of a set of parallel
`cylinders. The cylinders in
`the diagram
`are depicted as if from the edge of the
`image plane: the regularly-spaced verti7a1
`line segments are the samples along a s~n­
`gle axis. The arrows at the sample points
`indicate
`the directions of
`the surface
`normals . Depending on the shading formula
`invoked,
`there may be very high contrast
`between samples where the normal is nearly
`parallel
`to
`the sample axis, and samples
`where the normal points directly at
`the
`observer's eye.
`
`Figure (12)
`
`The shading function depends not only
`on the shape of the surface, but its light
`reflection properties
`(characterized by
`the
`shading formula), the position of the
`light source,
`and
`the position of
`the
`observer's eye . Hanrahan [7] expresses it
`in honest Greek:
`
`i i !p(E,N,L) ~ dxdy
`
`X y
`
`{f[X""";Y)
`
`where the normal, N, the light sources, L,
`and the eye, E, are vectors which may each
`be functions of U and V, and the limits of
`integration are the X, Y boundaries of the
`pixel .
`
`highlight
`illustrates
`(13)
`Figure
`aliasing on a perfectly flat surface . The
`viewing conventions of the diagram are the
`same as in Figure (12).
`"L" is the direc(cid:173)
`tion vector of the light source: the sur(cid:173)
`face is a polygon at an angle to the image
`plane: the dotted bump is a graph of
`the
`reflected
`light,
`characteristic of a
`
`Figure (14)
`
`1
`
`( !\,./
`
`:
`:
`·•
`
`I : t
`t I
`1;
`.
`
`I
`... ............. _"-o./ __ ..__,.;-_""'"'--v-.....J'-
`
`I
`
`~'"
`l
`. I
`
`t
`\
`I
`
`----
`
`specular surface reflection function. The
`highlight
`indicated by
`the bump falls
`entirely between the samples.
`(Note
`that
`this is only possible on a flat surface if
`either the eye or the light
`is
`local,
`a
`point in space rather than simply a direc(cid:173)
`tion vector. Some boring shading formulae
`exclude
`the
`possibility of highlight
`aliasing on polygons by requiring all flat
`surfaces to be flat in shading.)
`
`A first attempt to overcome the limi(cid:173)
`tations of point-sampling the illumination
`function is to integrate the function over
`the projected area
`represented by each
`sample point.
`This approach
`is
`illus(cid:173)
`trated
`in Figure
`(14). The brackets at
`each sample represent the area of the sur(cid:173)
`face over which the illumination function
`is integrated. This procedure
`is analo(cid:173)
`gous to area-averaging of sampled edges or
`texture [3].
`
`In order to ge.neral ize this approach
`to curved surfaces, the "sample interval"
`over whi ch illumination is integrated must
`be modified according to the local curva(cid:173)
`ture of the surface at a sample .
`In Fig(cid:173)
`ure
`(15),
`the
`area
`of
`a
`surface
`represented by a pixel has been projected
`onto a
`curved surface. The solid angle
`over which illumination must be integrated
`is approximated by the volume enclosed by
`the normals at
`the pixel corners.
`The
`distribution of
`light within this volume
`will sum to an estimate of the diffuse
`reflection over the pixel.
`If the surface
`exhibits undulations at the pixel
`level,
`however, aliasing will result.
`
`Figure (15)
`
`7
`
`0007
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`into
`We might divide the surface up
`regions of relatively low curvature (as is
`done in some patch rendering algorithms),
`and
`rely
`on
`"edge antialiasing"
`to
`integrate the different surfaces within a
`pixel. Alternatively, we may develop some
`mechanism for limiting the local curvature
`of surfaces before rendering. This possi(cid:173)
`bility is explored in the next section.
`
`If we represent the illumination of a
`scene as a two-dimensional map, highlights
`can be effectively antialiased in much the
`same way as
`textures. Blinn and Newell
`[1] demonstrated specular reflection using
`an illumination map. The map was an image
`of the environment (a spherical projection
`of
`the scene, indexed by the X and Y com(cid:173)
`ponents of
`the surface normals) which
`could be used
`to cast reflections onto
`specular surfaces. The impression of mir(cid:173)
`rored
`facets and chrome objects which can
`be achieved with this method is striking~
`(16) provides an
`Figure
`illustration.
`Reflectance mapping is not, however, accu(cid:173)
`rate
`for
`local reflections. To achieve
`similar results with
`three dimensional
`accuracy requires ray-tracing.
`
`illumination
`A pyramidal parametric
`map permits convenient antialiasing of
`highlights as long as a
`good measure of
`local surface curvature is available. The
`value of "D'' used to index the map is pro(cid:173)
`portional
`to the solid angle subtended by
`the surface over the pixel being computed;
`this may be estimated by the same formula
`used to compute D
`for ordinary
`texture
`mapping.
`Nine
`light sources of varying
`brightness glint raggedly
`from
`the
`test
`object in Figure (18)~ the reflectance map
`in Figure (17) providen the
`illumination.
`In
`Figure
`(19), convincing highL1ght
`antialiasing results from the full pyrami(cid:173)
`dal parametric treatment.
`
`Figure 16
`Michael Chou (right) poses with
`ginary companion .
`Reflectance
`enhance the realism of synthetic
`
`ima(cid:173)
`an
`maps can
`shading .
`
`A pyramidal
`containing
`outside the
`
`Figure ( 17)
`parametric reflectance map,
`9
`light sources. The region
`i c:.
`11 snh~rP 11
`'lH"'nc:oA
`
`Figure (18) Before
`
`Figure (19) After
`
`8
`
`0008
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`32 X 32
`
`16 X 16
`
`8 X 8
`
`64 X 64
`
`Figures (20-23) Different resolution meshes.
`
`5. Levels of Detail in Surface Represen(cid:173)
`tation
`
`texture
`In addition to bandlimiting
`illumination
`functions
`for mapping
`and
`onto a surface, pyramidal parametrics may
`be used to limit the level of detail with
`which the surface itself is represented.
`The goal
`is
`to represent an object for
`graphic display as economically as
`its
`projection on
`the
`image plane permits,
`without boiling and sparkling aliasing
`artifacts as the projection changes .
`
`shading
`The expense of computing and
`each pixel dominates
`the cost of many
`algorithms for renderinq higher- order sur(cid:173)
`faces .
`For meshes of polygons or patch
`control points which project onto a
`small
`portion of the image, however, the vertex
`(or control-point) expense dominates.
`In
`these situations it is desirable to reduce
`the number of points used to represent the
`object .
`
`A pyramidal parametric data structure
`the components of which are spatial coor(cid:173)
`dinates (the X-Y-Z of the vertices of a
`rectangular mesh, for example, as opposed
`to the R-G-B of a texture or
`illumination
`map) provides a continuously-variable fil(cid:173)
`tered instance of the surface for sampling
`at any desired degree of resolution.
`
`illustrate
`Figures (20) through (23)
`simple surface based on a human face
`a
`model developed by Fred Parke at the
`University of Utah. As the sampling den(cid:173)
`sity varies, so does the filtering of
`the
`surface.
`These
`faces are
`filtered and
`sampled by
`the
`same methods previously
`discussed
`for
`texture and
`reflectance
`maps.
`Pyramidal parametric
`representa(cid:173)
`tions
`such as these appear promising for
`reducing aliasing effects as well as sys(cid:173)
`tematic~lly sampling very large data bases
`over a wide ranqe of scales and viewing
`angles.
`
`9
`
`0009
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`6. Conclusions
`
`Pyramidal data structures are of pro(cid:173)
`ven value
`in
`image analysis and have
`interesting application to image bandwidth
`compression and transmission .
`"Pyramidal
`parametrics," pyramidal data structures
`with intra- and inter-level interpolation,
`are here proposed for use
`in
`image syn(cid:173)
`thesis.
`By
`continuously varying
`the
`detail with which data are
`resolved,
`pyramidal parametrics provide economical
`approximate solutions to filtering prob(cid:173)
`lems
`in mapping texture and illumination
`onto surfaces, and preliminary experiments
`suggest
`they may provide flexible surface
`representations as well.
`
`7. Acknowledgments
`
`I would like to acknowledge Ed Cat(cid:173)
`mull, the first (to my knowledge) to apply
`multiple prefiltered
`images
`to
`texture
`mapping:
`the method was applied to the
`bicubic patches in his thesis, although it
`was not described. Credit is also due Tom
`Duff, who wrote both recursive and
`scan(cid:173)
`order ~outines for creating mip maps which
`preserved numerical precision over all map
`instances; Dick Lundin, who wrote
`the
`first assembly-coded mip map accessing
`routines; Ephraim Cohen, who wrote the
`second; Rick Ace, who translated Ephraim's
`PDP-11 versions
`for
`the VAX a ssembler:
`Paul Heckbert, for refining and
`speeding
`up both creation and accessing routines,
`and
`investigating various estimates of
`"D"; Michael
`Chou,
`for
`implementing
`highlight antialiasing and high-resolution
`reflectance mapping on quadric surfaces.
`
`Jules
`to
`thanks
`special
`owe
`I
`Bloomenthal, Michael Chou, Pat Hanrahan,
`and Paul Heckbert for critical reading and
`numerous helpful suggestions in the course
`of preparing this text. Photographic sup(cid:173)
`port was provided by Michael Lehman.
`
`10
`
`0010
`
`

`
`Computer Graphics
`
`Volume 17, Number 3
`
`July 1983
`
`8. References
`
`"Texture
`(1) Blinn, J., and Newell, M.,
`and Reflection on Computer Generated
`Images," CACM, Vol. 19,
`tlO, Oct.
`1976, pp. 542-547.
`
`Electrical and Systems Engineering
`Dept., Rensselaer Polytechnic
`I nsti(cid:173)
`tute , October 1980.
`
`and Klinger, A.,
`[12] Tanimoto, S.L . ,
`Structured Computer Vision, Academic
`Press, New Yor k , 1980.
`
`"A
`[13] Tanimoto, S.L., and Pavlidis, T.,
`Hierarchical Data Structure for Pic(cid:173)
`ture Processing," Computer Graphics
`and
`Image Processing, Vol .
`4 , 12,
`June 1975 .
`
`Processing
`"Image
`(14] Tanimoto, S.L.,
`with Gross
`Information First , " Com(cid:173)
`puter Graphics and
`Image Processing
`9, 1979.
`
`[15] Warnock, J.E . , "A Hidden-Line Algo(cid:173)
`rithm
`for Halftone Picture Represen(cid:173)
`tation," Department of Computer Sci(cid:173)
`ence, University of Utah, TR 4-15 ,
`1969.
`
`(16] Williams,
`L.,
`Parametrics,"
`SIGGRAPH
`notes,
`"Advanced
`Image
`1981.
`
`"Pyramidal
`tutorial
`Synthesis,"
`
`[17] Yau, M.M., and Srihari, S.N., "Recur(cid:173)
`sive Generation of Hierarchical Data
`Structures for Multidimensional Digi(cid:173)
`tal
`Images," Proceedings of the IEEE
`Computer Society Conference on Pat(cid:173)
`tern Recognition and Image Process(cid:173)
`ing, August 1981.
`
`for
`"Illumination
`[2] Bui-Tuong Phong,
`Computer Generated Pictures," PhD.
`dissertation, Department of Computer
`Science, University of Utah, December
`1978.
`
`in
`[3] Crow, F.C., "The Aliasing Problem
`Computer Synthesized Shaded Images,"
`PhD. dissertation, Department of Com(cid:173)
`puter Science, Un iversity of Utah,
`Tech. Report UTEC-CSc-76-015, March
`1976.
`
`[4] Dungan, w., Stenger, A. ,
`and Sutty,
`G. ,
`"Texture Tile Considerations for
`Raster Graphics,"
`SIGGRAPH
`1978
`Proceedings, Vol. 12, 13, August
`1978.
`
`[5] Eastman, Charles M. , "Representations
`for Space Planning," CACM, Vol. 13,
`14, April 1970 .
`
`and Cook,
`[6] Feibush, E.A., Levoy, M.,
`R. L. ,
`"Synthetic Texturing Using
`Digital Filters," Computer Graphics,
`Vol. 14, July, 1980.
`
`(7] Hanrahan, Pat, private communication,
`1983 .
`
`"Texture Mapping
`[8] Heckbert, Paul,
`Polygons
`in Perspective," NYIT Com(cid:173)
`puter Graphics Lab Tech. Memo #13,
`April. 1983.
`
`(9] Klinger, A., and Dyer, c. R., "Experi(cid:173)
`ments on Picture Representation Using
`Regular Decomposition,"
`Computer
`Graphics and
`Image Processing , 15,
`March, 1976.
`
`[10] Knowlton, K. , "Progressive Transmis(cid:173)
`sion of Gray-Scale and Binary Pic(cid:173)
`tures by Simple, Efficient, and Loss(cid:173)
`less Encoding Schemes," Proceedings
`of the IEEE, Vol . 68, 17, July 1980,
`PP· 885-896 .
`
`[11] Meagher, D., "Octree Encoding: A New
`Technique
`for
`the Representation,
`Manipulation, and Display of Arbi(cid:173)
`trary 3D Objects by Computer," IPL(cid:173)
`TR-80- 111,
`Image
`Processing
`Lab,
`
`11
`
`0011