Efficient antialiased rendering of 3-D linear fractals

ABSTRACT

Object instancing is the efficient method of representing an hierarchical object with a directed graph instead of a tree. If this graph contains a cycle then the object it represents is a linear fractal. Linear fractals are difficult to render for three specific reasons: (1) ray-fractal intersection is not trivial, (2) surface normals are undefined and (3) the object aliases at all sampling resolutions.Ray-fractal intersections are efficiently approximated to sub-pixel accuracy using procedural bounding volumes and a careful determination of the size of a pixel, giving the perception that the surface is infinitely detailed. Furthermore, a surface normal for these non-differentiable surfaces is defined and analyzed. Finally, the concept of antialiasing "covers" is adapted and used to solve the problem of sampling fractal surfaces.An initial bounding volume estimation method is also described, allowing a linear fractal to be rendered given only its iterated, function system. A parallel implementation of these methods is described and applications of these results to the rendering of other fractal models are given.

REFERENCES

• 1: BARNSLEY, M. F., ERVIN, V., HARDIN, D., AND LANCASTER, j. Solution of an inverse problem for fractals and other sets. Proceedings of the National Academy of Science 83 (April 1986), 1975-1977.
• 2: Michael F. Barnsley , Arnaud Jacquin , Francois Malassenet , Laurie Reuter , Alan D. Sloan, Harnessing chaos for image synthesis, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.131-140, Aug. 1988
• 3: Alan H. Barr, Ray tracing deformed surfaces, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.287-296, Aug. 1986
• 4: Christian Bouville, Bounding ellipsoids for ray-fractal intersection, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.45-52, Jul. 1985
• 5: Stephen Demko , Laurie Hodges , Bruce Naylor, Construction of fractal objects with iterated function systems, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.271-278, Jul. 1985
• 6: J. C. Hart , D. J. Sandin , L. H. Kauffman, Ray tracing deterministic 3-D fractals, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.289-296, July 1989
• 7: HEPTING, D., PRUSINKIEWICZ, P., AND SAUPE, D. Rendering methods for iterated function systems. In Proceedings of Fractals '90 (1990), IFIP.
• 8: HUTCHINSON, J. Fractals and self-similarity. Indiana University Mathematics Journal 30, 5 (1981), 713-747.
• 9: J AQUIN, A. E. Image coding based on a fractal theory of iterated contractive image transformations. Preprint, 1990.
• 10: James T. Kajiya, New Techniques for Ray Tracing Procedurally Defined Objects, ACM Transactions on Graphics (TOG), v.2 n.3, p.161-181, July 1983 [doi>10.1145/357323.357324]
• 11: Timothy L. Kay , James T. Kajiya, Ray tracing complex scenes, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.269-278, Aug. 1986
• 12: MANDELBROT, B. B. The Fractai Geometry of Nature, 2nd ed. Freeman, San Francisco, 1982.
• 13: MITCHELL, D. P., Summer 1990. personal communication.
• 14: MITCHELL, D. P., AND AMANATIDES, J. Megacycles. SIGGRAPH Video Review 51 (1989), #14.
• 15: Alan Norton, Generation and display of geometric fractals in 3-D, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.61-67, July 1982
• 16: Thomas Porter , Tom Duff, Compositing digital images, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.253-259, July 1984
• 17: PRESS, W. H., FLANNERY, B. P., TEUKOL- SKY, S. A., AND VETTERLING, W. T. Numerical Recipes in C. Cambridge University Press, 1988.
• 18: IEEE Computer Graphics and Applications Staff, Exploring the Beauty of Plants, IEEE Computer Graphics and Applications, v.10 n.2, p.3-6, March 1990
• 19: P. Prusinkiewicz , Aristid Lindenmayer, The algorithmic beauty of plants, Springer-Verlag New York, Inc., New York, NY, 1990
• 20: Steven M. Rubin , Turner Whitted, A 3-dimensional representation for fast rendering of complex scenes, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.110-116, July 1980
• 21: SHANNON, C. E. Communication in the presence of noise. Proceedings of the Institute of Radio Engineers 37, 1 (January 1949), 10-21.
• 22: Mikio Shinya , T. Takahashi , Seiichiro Naito, Principles and applications of pencil tracing, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.45-54, July 1987
• 23: John M. Snyder , Alan H. Barr, Ray tracing complex models containing surface tessellations, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.119-128, July 1987
• 24: STRANG, G. Linear Algebra and its Applications, 3rd ed. Harcourt Brace Jovanovich, 1988.
• 25: Ivan E. Sutherland, Sketch pad a man-machine graphical communication system, Proceedings of the SHARE design automation workshop, p.6.329-6.346, January 1964 [doi>10.1145/800265.810742]
• 26: D. Thomas , A. N. Netravali , D. S. Fox, Anti-aliased ray tracing with covers, Computer Graphics Forum, v.8 n.4, p.325-336, Dec. 1989 [doi>10.1111/j.1467-8659.1989.tb00514.x]
• 27: E. R. Vrscay , C. J. Roehrig, Iterated function systems and the inverse problem of fractal construction, Proceedings of the third conference on Computers and mathematics, p.250-259, May 1989, Boston, Massachusetts, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Fractals

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Hierarchy and geometric transformations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture; Visible line/surface algorithms

General Terms:
Algorithms, Theory

Keywords:
covers, fractal, object instancing, procedural modeling, ray tracing