John C. Hart
Thomas A. DeFanti
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.
- 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.Google Scholar
Cross Ref
- 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. Google ScholarDigital Library
- 3 BARR, A. H. Ray tracing deformed surfaces. Computer Graphics 20, 4 (1986), 287-296. Google ScholarDigital Library
- 4 BOUVILLE, C. Bounding ellipsoids for rayfractal intersection. Computer Graphics 19, 3 (1985), 4 5-51. Google ScholarDigital Library
- 5 DEMKO, S., tIot)6ES, L., AND NAYLOR, B. Construction of fractal objects with iterated function systems. Computer Graphics 19, 3 (1985), 271-278. Google ScholarDigital Library
- 6 HART, J. C., SANDIN, D. J., AND KAUFFMAN, L. It. Ray tracing deterministic 3-D fractals. Computer Graphics 23, 3 (1989), 289-296. Google ScholarDigital Library
- 7 HEPTING, D., PRUSINKIEWICZ, P., AND SAUPE, D. Rendering methods for iterated function systems. In Proceedings of Fractals '90 (1990), IFIP.Google Scholar
- 8 HUTCHINSON, J. Fractals and self-similarity. Indiana University Mathematics Journal 30, 5 (1981), 713-747.Google ScholarCross Ref
- 9 J AQUIN, A. E. Image coding based on a fractal theory of iterated contractive image transformations. Preprint, 1990.Google Scholar
- 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. Google ScholarDigital Library
- 11 KAY, T. L., AND KAJIYA, J. T. Ray tracing complex scenes. Computer Graphics 20, 4 (1986), 269-278. Google ScholarDigital Library
- 12 MANDELBROT, B. B. The Fractai Geometry of Nature, 2nd ed. Freeman, San Francisco, 1982.Google Scholar
- 13 MITCHELL, D. P., Summer 1990. personal communication.Google Scholar
- 14 MITCHELL, D. P., AND AMANATIDES, J. Megacycles. SIGGRAPH Video Review 51 (1989), #14.Google Scholar
- 15 NORTON, A. Generation and rendering of geometric fractals in 3-D. Computer Graphics 16, 3 (1982), 61-67. Google ScholarDigital Library
- 16 PORTER, T., AND DUFF, T. Compositing digital images. Computer Graphics 18, 3 (1984), 253-259. Google ScholarDigital Library
- 17 PRESS, W. H., FLANNERY, B. P., TEUKOL- SKY, S. A., AND VETTERLING, W. T. Numerical Recipes in C. Cambridge University Press, 1988.Google ScholarDigital Library
- 18 PRUSINKIEWlCZ, P. About the cover: Exploring the beauty of plants. 1EEE Computer Graphics and Applications 10, 2 (March 1990), 3-6. Google ScholarDigital Library
- 19 PRUSINKI~.WlCZ, P., AND LINDENMAYER, A. The Algorithmic Beauty of Plants. Springer- Verlag, New York, 1990. Google ScholarDigital Library
- 20 ROBIN, S. M., AND IVHITTED, T. A 3- dimensional representation for fast rendering of complex scenes. Compuler Graphics 14, 3 (1980), 110-116. Google ScholarDigital Library
- 21 SHANNON, C. E. Communication in the presence of noise. Proceedings of the Institute of Radio Engineers 37, 1 (January 1949), 10-21.Google Scholar
- 22 SHINYA, M., TAKAIIAStlI, T., AND NAITO, S. Principles and applications of pencil tracing. Computer Graphics 21, 4 (1987), 45-54. Google ScholarDigital Library
- 23 SNYDER, J. M., AND BARR, A. H. Ray tracing complex models containing surface tessellations. Computer Graphics 21, 4 (1987), 119-128. Google ScholarDigital Library
- 24 STRANG, G. Linear Algebra and its Applications, 3rd ed. Harcourt Brace Jovanovich, 1988.Google Scholar
- 25 SOTHERLAND, I. E. Sketchpad: A man-machine graphical communication system. Proceedings of the Spring Joint Computer Conference (1963). Google ScholarDigital Library
- 26 THOMAS, D., NETRAVALI, A. N., AND FOX, D. S. Antialiased ray tracing with covers. Computer Graphics Forum 8, 4 (December 1989), 325-336. Google ScholarDigital Library
- 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. Google Scholar
Index Terms
- Efficient antialiased rendering of 3-D linear fractals
Recommendations
Efficient antialiased rendering of 3-D linear fractals
SIGGRAPH '91: Proceedings of the 18th annual conference on Computer graphics and interactive techniquesObject 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 ...
Real-time multiply recursive reflections and refractions using hybrid rendering
We present a new method for real-time rendering of multiple recursions of reflections and refractions. The method uses the strengths of real-time ray tracing for objects close to the camera, by storing them in a per-frame constructed bounding volume ...
Comments