BUNGIE - EXHIBIT 1018 - PART 3 OF 4
`
`

`
` _
`
`SIGGRAPH 93'_A”5.‘.I_‘°,"“.3Q§'!9[l‘i?;lT§,5H9E§ll9?9 ._
`
`..-
`
`of a cylinder in these spaces? Also, neither space allows
`similarity transformations: changing the size of an object
`changes its shape! Other questions arise. What sort of har-
`monic analysis is available to synthesize fractal terrains and
`textures in these spaces? If we hope to do physically-based
`modeling in these spaces, we need to expand our understand-
`ing of the laws of physics beyond the behavior of light de-
`scribed above in relation to shading. Finally, the theory of
`splines in non-Euclidean spaces was explored in [GK85].
`In the area of topological content, one obvious goal is
`to implement the five non-isotropic three dimensional model
`geometries. Also, there are many sorts of discrete groups,
`particularly those that create fractal patterns, which do not
`fit neatly into the current framework.
`In the direction of mathematical research and user inter-
`
`face, the efforts described here suggest various techniques for
`exploring 3-manifolds. Connecting this software with virtual
`reality technology would allow the researcher to perform a
`variety of explorations of the space. The use of sound also
`promises to yield useful evidence.
`Looking at the wider world of Riemannian geometry,
`this work is one step in the direction of visualizing arbi-
`trary curved spaces, the Riemannian manifolds that figure
`centrally in relativity and cosmology. For related work see
`[HD89].
`Finally, this work opens a new domain for artistic cre-
`ativity, three dimensional analogues of M. C. Escher’s dra-
`matic interlocking planar tessellations.
`
`9 Conclusions
`
`Approaching metric geometries via their common ancestry
`in projective geometry yields simple models which can be
`directly implemented in existing rendering systems. The re-
`sulting systems allow interactive navigation of curved spaces
`for the first time. Custom shaders provide realistic render-
`ing of the insider's view. Methods for manipulating and
`displaying discrete groups allow interactive exploration of a
`wide class of topological manifolds modeled on these spaces,
`that have never been visualized before. The resulting sys-
`tem provides a unique tool for mathematicians, educators,
`and scientists and artists whose work is related to spatial
`symmetry.
`
`Acknowledgements
`
`I would like to acknowledge valuable ideas, comments, sug-
`gestions, and assistance from Bill Thurston, Jeff Weeks, Sil-
`vio Levy, Stuart Levy, Mark Phillips, John Sullivan, David
`Banks, and the reviewers.
`
`References
`
`[Bea83]
`
`The Geometry of Discrete
`Alan F. Beardon.
`Groups. Springer-Verlag, 1983.
`
`[Car76] Manfredo P. Do Carmo. Difierential Geometry
`of Curves and Surfaces. Prentice—Hall, 1976.
`
`[Cay59]
`
`A. Cayley. A sixth memoir upon quantics. Philo-
`sophical Transactions of the Royal Society of
`London, 149:61—90, 1859.
`
`[Cox65]
`
`H.M.S. Coxeter. Non-Euclidean Geometry. Uni-
`versity of Toronto Press, 1965.
`
`262
`
`[Cox73]
`
`[Cox87]
`
`[ECH+91]
`
`[FRC92]
`
`[GK85]
`
`[GM91]
`
`[Gun83]
`
`[Gun92]
`
`[HD89]
`
`[Lev92]
`
`[LM78]
`
`[MLP+]
`
`H.M.S. Coxeter. Regular Polytopes. Dover, 1973.
`
`H.M.S. Coxeter. Projective Geometry. Springer
`Verlag, 1987.
`
`D. B. A. Epstein, Jim Cannon, Derek Holt, Sil-
`vio Levy, Mike Patterson, and William Thurston.
`Word Processing in Groups. Jones and Bartlett,
`1991.
`
`Helaman Ferguson, Alyn Rockwood, and Jordan
`Cox. Topological design of sculptural surfaces.
`Computer Graphics, 26:149—156, July, 1992. Pro-
`ceedings of SIGGRAPH 1992.
`
`S. Gabriel and J. Kajiya. Spline interpolation in
`curved space. In State of the Art Image Synthesis,
`1985. Course notes for SIGGRAPH 1985.
`
`Charlie Gunn and Delle Maxwell. Not Knot.
`
`Jones and Bartlett, 1991.
`
`Charlie Gunn. A computer implementation of
`the two-dimensional euclidean crystallographic
`groups. Master’s thesis, UNC, Chapel Hill, 1983.
`
`Charlie Gunn. Visualizing hyperbolic geometry.
`In Computer Graphics and Mathematics, pages
`299-313. Eurographics, Springer Verlag, 1992.
`
`Ping-Kang Hsiung and Robert H.P. Dunn. Visu-
`alizing relativistic effects in spacetime. In Super-
`computing 89. IEEE/ACM, Nov, 1989.
`
`Silvio Levy. Automatic generation of hyperbolic
`tilings. Leonardo, 35:349—354, 1992.
`E. H. Lockwood and R. H. Macmillan. Geometric
`
`symmetry. Cambridge University Press, 1978.
`
`Tamara Munzner, Stuart Levy, Mark Phillips,
`Nathaniel Thurston, and Celeste Fowler.
`.Ge-
`omview —— an interactive viewing program for sgi
`workstations. ftp@geom.umn.edu.
`
`[Mun75]
`
`James Munkres. Topology: A First Course, chap-
`ter 8. Prentice-Hall, 1975.
`
`[PG92]
`
`[Sch80]
`
`[Thu82]
`
`[Thuar]
`
`[Ups89]
`
`[Wee]
`
`Mark Phillips and Charlie Gunn. Visualizing hy-
`perbolic space: Unusual uses of 4x4 matrices.
`In 1992 Symposium an Interactive 3D Graphics,
`pages 209-214. ACM SIGGRAPH, ACM, 1992.
`
`R.L.E. Schwarzenberger. N-Dimensional Crys-
`tallography. Pitman Publishing, 1980. chapters
`13-16.
`
`William Thurston. Three dimensional manifolds,
`kleinian groups and hyperbolic geometry. BAMS,
`19:417——431, 1982.
`
`William Thurston. The Geometry and Topology
`of Three-Manifolds, volume 1. to appear.
`
`The Renderman Companion.
`Steve Upstill.
`Addison-Wesley, 1989. chapters 13-16.
`
`Jeff Weeks. snappea —— a macintosh application
`for computing 3-manifolds. ftp@geom.umn.edu.
`
`[Wee85]
`
`Jeff Weeks. The Shape of Space. Marcel Dekker,
`1985.
`
`[Woo22]
`
`Frederick Woods. Higher Geometry. Dover, 1961
`(1922).
`
`

`
`
`
`
`
`35I
`3
`
`
`
`COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993
`
`Imaging Vector Fields Using Line Integral Convolution
`
`Brian Cabral
`
`Leith (Casey) Leedom*
`
`Lawrence Livermore National Laboratory
`
`ABSTRACT
`
`Imaging vector fields has applications in science, art, image pro-
`cessing and special effects. An effective new approach is to use
`linear and curvilinear filtering techniques to locally blur textures
`along a vector field. This approach builds on several previous tex-
`ture generation and filtering techniques[8, 9, 11, 14, 15, 17, 23]. It
`is, however, unique because it is local, one-dimensional and inde-
`pendent of any predefined geometry or texture. The technique is
`general and capable of imaging arbitrary two- and three-dimen-
`sional vector fields. The local one-dimensional nature of the algo-
`rithm lends itself to highly parallel and efficient implementations.
`Furthermore, the curvilinear filter is capable of rendering detail on
`very intricate vector fields. Combining this technique with other
`rendering and image processing techniques — like periodic motion
`filtering — results in richly infomrative and striking images. The
`technique can also produce novel special effects.
`CR categories and subject descriptors: 1.3.3 [Computer
`Graphics]: Picture/Image generation; 1.3.7 [Computer Graphics]:
`T'hree-Dimensional Graphics and Realism; 1.4.3 [Image Process-
`ing]: Enhancement.
`Keywords: convolution, filtering, rendering, visualization, tex-
`ture synthesis, flow fields, special effects, periodic motion filtering.
`
`1. INTRODUCTION
`Upon first inspection, imaging vector fields appears to have lim-
`ited application — confined primarily to scientific visualization.
`However, much of the form and shape in our environment is a
`function of not only image intensity and color, but also of direc-
`tional information such as edges. Painters, sculptors, photogra-
`phers, image processors[16] and computer graphics researchers[9]
`have recognized the importance of direction in the process of
`image creation and form. Hence, algorithms that can image such
`directional information have wide application across both scien-
`tific and artistic domains.
`
`Such algorithms should possess a number of desirable and
`sometimes conflicting properties including: accuracy, locality of
`calculation, simplicity, controllability and generality. Line Integral
`Convolution OJC) is a new technique that possesses many of these
`properties. Its generality allows for the introduction of a com-
`
`* Authors’ current e-mail addresses are: cabral@llnl.gov and
`casey@gauss. llnl.gov.
`
`pletely new family of periodic motion filters which have wide
`application (see section 4.1). It represents a confluence of signal
`and image processing and a variety of previous work done in com-
`puter graphics and scientific visualization.
`
`2. BACKGROUND
`
`There are currently few techniques which image vector fields in
`a general manner. These techniques can be quite effective for visu-
`alizing vector data. However, they break down when operating on
`very dense fields and do not generalize to other applications. In
`particular, large vector fields (512x5l2 or greater) strain existing
`algorithms.
`Most vector visualization algorithms use spatial resolution to
`represent the vector field. These include sampling the field, such as
`with stream lines[l2] or particle traces, and using icons[19] at
`every vector field coordinate. Stream lines and particle tracing
`techniques depend critically on the placement of the “streamers” or
`the particle sources. Depending on their placement, eddies or cur-
`rents in the data field can be missed. Icons, on the other hand, do
`not miss data, but use up a considerable amount of spatial resolu-
`tion limiting their usefulness to small vector fields.
`Another general approach is to generate textures via a vector
`field. Van Wijk’s spot noise algorithm[23] uses a vector field to
`control the generation of bandlimited noise. The time complexity
`of the two types of implementation techniques presented by Van
`Wijk are relatively high. Furthermore the technique, by definition,
`depends heavily on the form of the texture (spot noise) itself. Spe-
`cifically, it does not easily generalize to other forms of textures that
`might be better suited to a particular class of vector data (such as
`fluid flow versus electromagnetic).
`Reaction diffusion techniques[20, 24] also provide an avenue
`for visualizing vector fields since the controlling differential equa-
`tions are inherently vector in nature. It is possible to map vector
`data onto these differential equations to come up with a vector
`visualization technique. Here too however, the time complexity of
`these algorithms limit their general usefulness.
`Three-dimensional vector fields can be visualized by three-
`dimensional
`texture generation techniques such as texels and
`hypertextures described in [11, 15]. Both techniques take a texture
`on a geometrically defined surface and project the texture out some
`distance from the surface. By definition these techniques are bound
`to the surface and do not compute an image for the entire field as is
`done by Van W"1jk[23]. This is limiting in that it requires a priori
`knowledge to place the surface. Like particle streams and vector
`streamers these visualization techniques are critically dependent
`on the placement of the sampling surface.
`The technique presented by Haeberli[9] for algorithmicly gener-
`ating “paintings” via vector-like brush strokes can also be thought
`of as a vector visualization technique. Crawfis and Max[5]
`
`1993
`
`ACM-0-89791-601-8/93/008/0263
`
`
`
`263
`
`
`
`

`
`
`
`Sl_Gr(_EiFlAPH 93, Anaheim. California, 1-6 August 1993
`
`describe a three—dimensional variation on this in which blurred cyl-
`inders represent three-dimensional brush strokes whose directions
`and colors are controlled by a three-dimensional vector field. Both
`techniques represent a conceptual extension of traditional
`icon
`placement, where the icons are more sophisticated shapes. How-
`ever,
`these techniques break down as the density of the field
`increases since they require spatial resolution to work.
`What is needed is a technique that can image dense vector fields,
`is independent of both predefined sampling placement constraints
`and texture generation techniques and can work in two and three
`dimensions. Such a technique would be very general and have
`wide application.
`
`3. DDA CONVOLUTION
`
`.
`
`'-t.--
`
`'
`
`—"
`
`‘ '
`
`Figure 2: Circular and turbuleri
`imaged using DDA convolution over white noise.
`
`One approach is a generalization of traditional DDA line draw-
`ing techniques[ 1] and the spatial convolution algorithms described
`by Van Wrjk[23] and Perlin[l4]. Each vector in a field is used to
`define a long, narrow, DDA generated filter kernel tangential to the
`vector and going in the positive and negative vector direction some
`fixed distance. L. A texture is then mapped one-to-one onto the
`vector field. The input texture pixels under the filter kernel are
`summed, normalized by the length of the filter kernel, 2L, and
`placed in an output pixel image for the vector position. Figure 1,
`illustrates this operation for a single vector in a field.
`Tliis effectively filters the underlying texture as a function of the
`vector field. The images in figure 2 are rendered using the DDA
`convolution algorithm. On the left is a simple circular vector field;
`to its right is the result of a computational fluid dynamics code. The
`input texture image in these examples is white noise. Although tl1e
`description above implies a box filter. any arbitrary filter shape can
`be used for the filter convolution kernel. It is important to note that
`this algorithm is very sensitive to symmetry of the DDA algorithm
`and filter. If the algorithm weights the forward direction more than
`the backward direction, the circular field in figure 2 appears to spi-
`ral inward implying a vortical behavior that is not present in the
`vector field.
`
`3.1 LOCAL FIELD BEHAVIOR
`
`The DDA approach, while efficient, is inherently inaccurate. It
`assumes that the local vector field can be approximated by a
`
`straight line. For points in vector fields where the local radius of
`curvature is large, this assumption is valid. However, where there
`are complex structures smaller than the length of the DDA line, the
`local radius of curvature is small and is not well approximated by a
`straight line. In a sense, DDA convolution renders the vector field
`unevenly, treating linear portions of the vector field more accu-
`rately than small scale vortices. While this graceful degradation
`may be fine or even desirable for special effects applications. it is
`problematic for visualizing vector fields such as the ones in figure
`2, since detail in the small scale structures is lost.
`Van Wijk’s spot noise algorithm[23] also suffers from this prob-
`lem since the spots are elliptically stretched along a line in the
`direction of the local field. If the ellipse major axis exceeds the
`local length scale of the vector field, the spot noise will inaccu-
`rately represent the vector field. An accurate measure of local field
`behavior would require a global analysis of the field. Such tech-
`niques currently do not exist for arbitrary vector fields, would most
`likely be expensive to ca[culate[l3] and are an area of active
`research['i].
`
`4. LINE INTEGRAL CONVOLUTION
`The local behavior of the vector field can be approximated by
`computing a local stream line that stans at the center of pixel (X, y)
`and moves out in the positive and negative directions. The for-
`ward coordinate advection is given by equation (1).
`
`vector tlelo
`
`P0 = (x+0.5,y+0.5}
`
`[2-DA line
`
`Input texture
`
`Output image
`
`
`
`Figure l: The mopping of o vector onto or DDA line and Input
`pixel field generating a single output pixel.
`
`P
`
`v(rP,,,p
`.=P. as (1)
`"‘+||"(LP.--rll1I
`*
`
`V ( L P_] ] - the vector from the input vector
`field at lattice point (LPJJ, LPIJ)
`
`00 if VII 9
`
`S, =
`
`P
`
`_.P
`
`0 if$ < 0
`c
`l_Pci —PC
`T 0lil'lcl.'“|"l.5'e
`C
`
`for (e,c) E
`
`(rap!
`
`(borrom, y)
`(left X)
`.
`3
`{’1ghr!x)
`
`2
`
`)
`
`(
`
`A 5: ' mi“ (Sroflsbartom’SIefr‘Srighr)
`
`1' Vector field lattice and image coordinates are usually specified in a left-
`handed coordinate system while vector components are usually specified in
`a right-handed coordinate system. In this case. the y-component of the lat-
`tice coordinate in equation (1) must be reflected about the vertical center of
`the lattice to operate in a consistent coordinate system. This reflection has
`been omitted to preserve simplicity of presentation.
`
`

`
`
`
`m___COl\_/lF’_UTE_l=l GFlAPH|_CS Proceedings, Annual Conference Series, 1993
`
`7. m-:”\W~\T_\ K‘ \
`
`~.
`
`ax
`
`K.
`
`K.
`
`\
`
`\
`K.
`fix” 7:
`
`- - *\
`
`R.
`
`\.
`
`\
`
`\
`
`'\
`
`\
`ix
`
`\
`
`K - I-\
`-\
`\
`\
`'2 Z If Km 9:
`1
`x
`l \
`x
`"Krill-‘lg?’
`
`\
`\
`\ +"\
`r
`r
`
`TIM? x.‘ \ ‘QC-V
`/'
`\
`>
`\
`gs 9% ~ ~'
`
`Ix ix
`
`\
`
`\
`
`L
`
`x"
`
`\ j
`xi
`
`\
`
`L
`
`t
`7- _
`
`‘r
`
`\
`
`\
`
`\
`\
`tjit
`1
`g 1“
`
`/if r-
`f
`
`\
`
`\
`
`\.
`
`\. N —-
`
`——>
`
`/'
`
`/'
`
`/'
`
`/'
`
`showing the Io-c-ol
`Ffijure 3: A two-dirhiensiondlvector
`stream line starting in cell (x, y). The vector field is the upper
`left corner of the fluid dynamics field In figures 2 and 4.
`
`Only the directional component of the vector field is used in this
`advection. The magnitude of tire vector field can be used later in
`post processing steps as explained in section 4.3.1. As,- is the posi-
`tive parametric distance along a line parallel to the vector field
`from P,- to the nearest cell edge.
`As with the DDA algorithm, it is important to maintain symme-
`try about a cell. Hence, the local stream line is also advected back-
`wards by the negative of the vector field as shown in equation (3).
`
`P5 =13
`
`l
`P"=P'1—1
`
`_ V(LPU_1l) As,
`llV(LPV—1l)H
`"1
`
`6)
`
`Primed variables represent the negative direction counterparts to
`the positive direction variables and are not repeated in subsequent
`definitions. As above As’,-, is always positive.
`The calculation of As; in the stream line advection is sensitive to
`round off errors. As, must produce advected coordinates that lie
`within the i+1‘h cell, taking the stream line segment out of the cur-
`rent cell. In the implementation of the algorithm a small round off
`term is added to each Asi to insure that entry into the adjacent cell
`occurs. This local stream line calculation is illustrated in figure 3.
`Each cell is assumed to be a unit square. All spatial quantities (e.g.,
`A5,») are relative to this measurement. However, the cells need not
`be square or even rectangular (see section 6) for this approxima-
`tion to work. So, without loss of generality, descriptions are given
`relative to a cubic lattice with unit spacing.
`Continuous sections of the local stream line — i.e. the straight
`line segments in figure 3 — can be thought of as parameterized
`space curves in s and the input texture pixel mapped to a cell can
`be treated as a continuous scalar function of x and y.2 It is then
`possible to integrate over this scalar field along each pararneterized
`space curve. Such integrals can be summed in a piecewise C1 fash-
`ion and are known as line integrals of the first kind (L[FK)[2]. The
`convolution concept used in the DDA algorithm can now be com-
`
`2' Bilinear, cubic or Bezier splines are viable alternatives to straight line
`segments. However, these higher order curves are more expensive to com-
`pute.
`
`
`
`bined with LIFK to form a Line Integral Convolution (LIC). This
`results in a variation of the DDA approach that locally follows the
`vector field and captures small radius of curvature features. For
`each continuous segment, i, an exact integral of a convolution ker-
`nel k(w) is computed and used as a weight in the LIC as shown in
`equation (4).
`
`s‘.+A.r,.
`
`hi =
`where
`so = 0
`
`1' k(w)dw
`x’
`
`s’. = si__1+Asi_1
`
`(4)
`
`The entire LIC for output pixel F ’(x, y) is given by equation (5).
`I
`1'
`
`2F(l_Pil)hi+ 2F(l_P'tl)h'i
`'
`:=o
`F'(x,y) = ‘=0
`I
`I,
`2m+Ew,
`I = 0
`1 = 0
`where
`F ( L PJ ) is the input pixel corresponding to
`the vector at position (LPXJ , |_PyJ)
`l=isuchthatsisL<si+1
`
`(5)
`
`(6)
`
`The numerator of equation (5) represents the line integral of the fil-
`ter kernel times the input pixel field, F. The denominator is the line
`integral of the convolution kernel and is used to normalize the out-
`put pixel weight (see section 4.2).
`The length of the local stream line, 2L, is given in unit pixels.
`Depending on the input pixel field, F, if L is too large, all the
`resulting LICs will return values very close together for all coordi-
`nates (x, y). On the other hand, if L is too small then an insufficient
`amount of filtering occurs. Since the value of L dramatically
`affects the performance of the algorithm, the smallest effective
`value is desired. For most of the figures, a value of 10 was used.
`Singularities in the vector field occur when vectors in two adja-
`cent local stream line cells geometrically “point” at a shared cell
`edge. This results in As, values equal to zero leaving I in equation
`(6) undefined. This situation can easily be detected and the advec-
`tion algorithm terminated. If the vector field goes to zero at any
`point, the LIC algorithm is terminated as in the case of a field sin-
`gularity. Both of these cases generate truncated strearn lines. If a
`zero field vector lies in the starting cell of the LIC, the input pixel
`value for that cell, a constant or any other arbitrary value can be
`returned as the value of the LIC depending on the visual effect
`desired for null vectors.
`
`Using adjacent strearn line vectors to detect singularities can
`however result in false singularities. False singularities occur when
`the vector field is nearly parallel to an edge, but causes the LIC to
`cross over that edge. Similarly, the cell just entered also has a near
`parallel vector which points to this same shared edge. This artifact
`can be remedied by adjusting the parallel vector/edge test found in
`equation (2), to test the angle formed between the vector and the
`edge against some small angle theta, instead of zero. Any vector
`which forms an angle less than theta with some edge is deemed to
`be “parallel” to that edge. Using a value of 3° for theta removes
`these artifacts.
`
`The images in figure 4 were rendered using LIC and correspond
`to the same two vector fields rendered in figire 2. Note the
`increased amount of detail present in these images versus their
`DDA counterparts. In particular the image of the fluid dynamics
`vector field in figure 4 shows detail incorrectly rendered or absent
`in figure 2.
`
`265
`
`

`
` ".'."\\\-
`
`"“.:---
`
`-3-2‘. -'
`
`
`Figure 4: Circular and turbulent fluid dynamics vector fields
`imaged using LIC over white noise.
`
`2
`
`-r" —-
`
`-
`
`The images in figure 5 show the effect of varying L. The input
`texture is a photograph of flowers. The input vector field was cre-
`ated by taking the gradient of a bandlimited noise image and rotat-
`ing each of the gradient vectors by 90°, producing vectors which
`follow the contours of the soft hills and valleys of the bandlimited
`noise. With L equal
`to 0,
`the input
`image is passed through
`unchanged. As the value of L increases, the input image is blurred
`to a greater extent, giving an impressionistic result. Here, a biased
`ramp filter[ 10] is used to roughly simulate a brush stroke.
`
`Figures 2, 4, 8, 9 and 11 were generated using white noise input
`images. Aliasing can be a serious problem when using LIC with a
`high frequency source image such as white noise. The aliasing is
`caused by the one-dimensional point sampling of the infinitely thin
`LIC filter. This aliasing can be removed by either creating a thick
`LIC filter with a low-pass filter cross section or by low-pass filter-
`ing the input image. This second alternative is preferable since it
`comes at no additional cost to the LIC algorithm. The images in
`figure 6 show the effect of ninning LIC over 256x256 white noise
`which has been low-pass filtered using a fourdi order Butterworth
`filter with cutoff frequencies of I28, 84, 64, and 32.
`It is worth noting that Van Wijk's spot noise algorithm[23] can
`be adapted to use the local stream line approximation to more
`accurately represent the behavior of a vector field. Instead of
`
`Ir. ‘C
`
`..
`
`Figure 5: Photograph of flowers processed using LIC with L
`equal to D, 5. 10 and 20 (left to right. top to bottom).
`
`straight line ellipticai stretching, each spot could be warped so that
`the major axis follows the local stream line. Furthermore, the
`minor axis could either be perpendicular to the warped major axis
`or itself could he warped along transverse field lines. However, an
`algorithm to perform this task for an arbitrary local stream line
`would be inherently more expensive and complex than the LIC
`algorithm.
`Sims[18] describes an alternative technique which produces
`results similar to LIC. This alternative approach warps or advects
`texture coordinates as a function of a vector field. The similarity
`between the two techniques is predictable even though the tech-
`niques are quite different. The dilation and contraction of the tex-
`ture coordinate system warping has the visual effect of blurring
`and sharpening the warped image. This is due to the resampling
`and reconstruction process necessary when warping from one
`coordinate system to another. Thus, for regions where the source
`image is stretched along the vector field an apparent bluning will
`occur similar to those seen with LIC. However, the techniques are
`completely different in two fundamental ways. First, LIC is a local
`operator, meaning no information outside of a fixed area of interest
`is needed. Warping even when done locally requires maintaining
`global consistency to avoid tearing holes in the warped image.
`This increases the complexity of the warping operation when com-
`pared to LIC. Second, LIC is a spatially varying filtering operation
`and does not warp or transform any texture coordinates.
`
`4.1 PERIODIC MOTION FILTERS
`
`The LIC algorithm visualizes local vector field tangents, but not
`their direction. Freeman, et al[8] describe a technique which simu-
`lates motion by use of special convolutions. A similar technique is
`used by Van Gelder and Wilhelms[22] to show vector field flow.
`This technique can be extended and used to represent the local vec-
`tor field direction via animation of successive LIC imaged vector
`fields using varying phase shifted periodic filter kernels.
`The success of this technique depends on the shape of the filter.
`In the previous examples (figures 2 and 4), a constant or box filter
`is used. If the filter is periodic like the filters used in [8], by chang-
`ing the phase of such filters as a function of time, apparent motion
`
`
`
`I
`n
`I
`5
`1'
`-
`'
`-
`Flute 6: The upper left hand quarter of the circular vector
`field is convolved using LIC over Butterworih low-pass filtered
`white noise with cutoff trequencies of 128. 86. 64. and 32 09”
`to right. top to bottom).
`
`

`
`COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993
`
`
`
`lnhhn
`
`lhnln
`
`Figure 7: Phase shifted Hanning ripple functions(top), 0 Hon-
`ning windowing funclion(midd|e). and Hanning ripple func-
`tions multiplied by the Hcinning window functIon(boh‘om).
`
`apparent motion[3]. A low frequency ripple function results in a
`windowed filter whose frequency response noticeably changes as a
`function of phase. This appears as a periodic blurring and sharpen-
`ing of the image as the phase changes. Higher frequency ripple
`functions produce windowed filters with a nearly constant fre-
`quency response since the general shape of the filter doesn't radi-
`cally change. However, the feature size picked up by me ripple
`filter is smaller and the result is less apparent motion. If the ripple
`frequency exceeds the Nyquist limit of the pixel spacing the appar-
`ent motion disappears. Experimentation shows that a ripple func-
`tion frequency between 2 and 4 cycles per window period is
`reasonable. One can always achieve both good frequency response
`and good feature motion by increasing the spatial resolution. This
`comes, of course, at a cost of increased computation[16].
`
`(3)
`
`4.2 NORMALIZATION
`
`sin (bc) — sin (ac)
`b - a + -——:—7—-———
`
`1
`7 Z
`
`+ sin (bd+ B) - sin (ad+|3)
`d
`+ sin(b(c—d) -5) —sin(a(c—d) -5)
`2(c-d)
`
`sin(b(c+d) +[3) —sin(a(c+d) +6)
`2(c+d)
`
`+
`
`As mentioned above, both the Hanning window and the Han-
`ning ripple filter function can be independently dilated by adjust-
`ing c and d to have specific local support and periodicity. The
`window function has a fixed period of 21:.
`Choosing the periodicity of the ripple function represents mak-
`ing a design trade-off between maintaining a nearly constant fre-
`quency response as a function of phase shift and the quality of the
`
`3‘ D. Gabor in 1946 created a localized form of the Fourier transform
`known as the Gabor transform. This transform is the Fourier transform of
`an input signal multiplied by a Gaussian window translated along the sig-
`nal as a frmction of time. The net result is a signal which is spatially and
`frequency localized. Wavelet theory is based on a generalization of this
`type of spatial and frequency localization.
`
`
`
`A normalization to the convolution integral is perfonned in
`equation (5) to insure that the apparent brightness and contrast of
`the resultant image is well behaved as a function of kernel shape,
`phase and length. The numerator in equation (5) is divided by the
`integral of the convolution kernel. This insures that the normalized
`area under the convolution kernel is always unity resulting in a
`constant overall brightness for the image independent of the filter
`shape and LIC length.
`
`Because the actual length of the LIC may vary from pixel to
`pixel, the denominator can not be precomputed. However, an inter-
`esting effect is observed if a fixed nonnalization is used. Truncated
`stream lines are attenuated which highlights singularities. The
`images in figure 8 a show another section of the fluid dynamics
`vector field imaged with variable and constant kernel nonnaliza-
`tion. The implementation of the LIC algorithm uses precomputed
`sum tables for the integral to avoid costly arithmetic in the inner-
`most loop.
`
`A second normalization may be done to insure the output image
`retains the input image’s contrast properties. The LIC algorithm
`reduces the overall image contrast as a function of L. In fact, in the
`case of the box filter, as L goes to infinity the entire output image
`goes to the average of the input image. This can be ameliorated by
`amplifying the input or contrast stretching the output image as a
`function of L. Clearly as L goes to infinity the amplification or con-
`
`267
`
`il i E
`
`
`
`in the direction of the vector field is created. However, the filters
`used in [8] were, by design, high-pass Laplacian edge enhancing
`filters. Using this filter over a bandlimited noise texture produces
`very incoherent images since the high frequency components of
`the noise are accentuated. Instead, it is possible, and desirable, to
`create periodic low-pass filters to blur the underlying texture in the
`direction of the vector field. A Hanning filter l/2(l + cos(w+[3)),
`has this property. It has low band-pass filter characteristics, it is
`periodic by definition and has a simple analytic fonn. This func-
`tion will be referred to as the ripple filter function.
`Since the LIC algorithm is by definition a local operation, any
`filter used must be windowed. That is, it must be made local even
`if it has infinite extent. In the previous section we used a constant
`filter implicitly windowed by a box of height one. Using this same
`box window on a phase shifted Hanning filter we get a filter with
`abrupt cutoffs, as illustrated in the top row of figure 7.
`This abrupt cutoff is noticeable as spatio-temporal artifacts in
`animations that vary the phase as a function of time. One solution
`to this problem is to use a Gaussian window as suggested by
`Gabor[4].3 By multiplying, or windowing, the Hanning function
`by a Gaussian, these cutoffs are smoothly attenuated to zero. How-
`ever, a Gaussian windowed Hanning fimction does not have a sim-
`ple closed form integral. An alternative is to find a windowing
`function with windowing properties similar to a Gaussian and
`which has a simple closed form integral. Interestingly, the Hanning
`function itself meets these two criteria. In the bottom row of figure
`7, the five phase shifted Hanning filter frmctions in the top row are
`multiplied by the Hanning window function in the middle row. The
`general form of this function is shown in equation (7). In this equa-
`
`1+cos(cw)
`k(w) raj?-——x
`
`l+cos(dw+[3)
`2
`
`(7)
`
`l
`=Z(1+ cos (cw) + cos (dw+fi) +cos (cw) cos (dw+|3))
`tion c and d represent the dilation constants of the Hanning win-
`dow and ripple functions respectively. B is the ripple function
`phase shift given in radians. The integral of k(w) from a to b used
`in equation (4) is shown in equation (8).
`
`b f
`
`k(w) dw
`
`

`
`

`
`Colt-lPUTEF_t_GFtfi_lPil_I§_S Proceedings, Annual Conference Series. 1_99§
`
`4.4 THREE-DIMENSIONAL LIC
`
`The LIC algorithm easily generalizes to higher dimensions.
`Equations (1), (3) and (5) trivially extend to three dimensions. In
`the three-dimensional case. cell edges are replaced with cell faces.
`Both the input vector field and input texture must be three-dimen-
`sional. The output of the three—dimensional LIC algorithm is a
`three—dimensional
`image or scalar field. This field is rendered
`using volume rendering techniques such as those found in [21] and
`[6].
`
`Figure 14 is a three-dimensional rendering of an electrostat