“Efficient antialiased rendering of 3-D linear fractals” by Hart and DeFanti

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.

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. BARNSLEY, M. F., JACQUIN, A., }~{AL- LASSENET, F., RUETER, L., AND SLOAN, A. D. Ilarnessing chaos for image synthesis. Computer Graphics 22, 4 (1988), 131-140.
3. BARR, A. H. Ray tracing deformed surfaces. Computer Graphics 20, 4 (1986), 287-296.
4. BOUVILLE, C. Bounding ellipsoids for rayfractal intersection. Computer Graphics 19, 3 (1985), 4 5-51.
5. DEMKO, S., tIot)6ES, L., AND NAYLOR, B. Construction of fractal objects with iterated function systems. Computer Graphics 19, 3 (1985), 271-278.
6. HART, J. C., SANDIN, D. J., AND KAUFFMAN, L. It. Ray tracing deterministic 3-D fractals. Computer Graphics 23, 3 (1989), 289-296.
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. KAJIYA, J. T. New techniques for ray tracing procedurally defined objects. A CM Transactions on Graphics 2, 3 (1983), 161-181. Also appeared in Computer Graphics 17, 3 (1983), 91-102.
11. KAY, T. L., AND KAJIYA, J. T. Ray tracing complex scenes. Computer Graphics 20, 4 (1986), 269-278.
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. NORTON, A. Generation and rendering of geometric fractals in 3-D. Computer Graphics 16, 3 (1982), 61-67.
16. PORTER, T., AND DUFF, T. Compositing digital images. Computer Graphics 18, 3 (1984), 253-259.
17. PRESS, W. H., FLANNERY, B. P., TEUKOL- SKY, S. A., AND VETTERLING, W. T. Numerical Recipes in C. Cambridge University Press, 1988.
18. PRUSINKIEWlCZ, P. About the cover: Exploring the beauty of plants. 1EEE Computer Graphics and Applications 10, 2 (March 1990), 3-6.
19. PRUSINKI~.WlCZ, P., AND LINDENMAYER, A. The Algorithmic Beauty of Plants. Springer- Verlag, New York, 1990.
20. ROBIN, S. M., AND IVHITTED, T. A 3- dimensional representation for fast rendering of complex scenes. Compuler Graphics 14, 3 (1980), 110-116.
21. SHANNON, C. E. Communication in the presence of noise. Proceedings of the Institute of Radio Engineers 37, 1 (January 1949), 10-21.
22. SHINYA, M., TAKAIIAStlI, T., AND NAITO, S. Principles and applications of pencil tracing. Computer Graphics 21, 4 (1987), 45-54.
23. SNYDER, J. M., AND BARR, A. H. Ray tracing complex models containing surface tessellations. Computer Graphics 21, 4 (1987), 119-128.
24. STRANG, G. Linear Algebra and its Applications, 3rd ed. Harcourt Brace Jovanovich, 1988.
25. SOTHERLAND, I. E. Sketchpad: A man-machine graphical communication system. Proceedings of the Spring Joint Computer Conference (1963).
26. THOMAS, D., NETRAVALI, A. N., AND FOX, D. S. Antialiased ray tracing with covers. Computer Graphics Forum 8, 4 (December 1989), 325-336.
27. VRSCAY, E. R., AND ROEHRIG, C. J. Iterated function systems and the inverse problem of fractal construction using moments. In Computers and Mathematics (New York, 1989), E. Kaltofen and S. M. Watt, Eds., Springer-Verlag, pp. 250- 259.