Exploring the Infinite-Time Behavior of the Chaos Game : Approximation and Interactive Visualization of 3D IFSP and RIFS Invariant Measures Using PC Graphics Accelerators

• Autorzy: Martyn T.
• Języki publikacji: EN

Abstrakty

EN

In this paper we tackle the problem of approximation and visualization of invariant measures arising from Iterated Function Systems with Probabilities (IFSP) and Recurrent Iterated Function Systems (RIFS) on R³. The measures are generated during the evolution of a stochastic dynamical system, which is a random process commonly known as the chaos game. From the dynamical system viewpoint, an invariant measure gives a temporal information on the long-term behavior of the chaos game related to a given IFSP or RIFS. The non-negative number that the measure takes on for a given subset of space says how often the dynamical system visits that subset during the temporal evolution of the system as time tends to infinity. In order to approximate the measures, we propose a method of measure instancing that can be considered an analogue of object instancing for IFS attractors. Although the IFSP and RIFS invariant measures are generated by the long-term behavior of stochastic dynamical systems, measure instancing makes it possible to compute the value that the measure takes on for a given subset of space in a deterministic way at any accuracy required. To visualize the data obtained with the algorithm, we use direct volume rendering. To incorporate the global structure of invariant measures along with their local properties in an image, a modification of a shading model based on varying density emitters is used. We adapt the model to match the fractal measure context. Then we show how to implement the model on commodity graphics hardware using an approach that combines GPU-based direct volume raycasting and 3D texture slicing used in the object-aligned manner. By means of the presented techniques, visual exploration of 3D IFSP and RIFS measures can be carried out efficiently at interactive frame rates.

Słowa kluczowe

EN

fractals; recurrent iterated function system; invariant measure; volume rendering; GPU programming

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2009
• Tom: Vol. 18, No. 4
• Strony: 453--476
• Opis fizyczny: Bibliogr. 37 poz., il.

Twórcy

autor

Martyn T.

• Institute of Computer Science Warsaw University of Technology, ul. Nowowiejska 15/17, 00-665 Warsaw, Poland,

Bibliografia

• [1] Rudin W.: Real and Complex Analysis, 2nd ed. McGraw-Hill. 1974.
• [2] Mandelbrot B.B.: The Fractal Geometry of Nature. San Francisco: W. H. Freeman and Co. 1982.
• [3] Preparata F.P., Shamos M.I.: Computational Geometry. An Introduction. New York: Springer-Verlag. 1985.
• [4] Barnsley M.F., Jaquin A., Reuter L., Sloan A.D.: A Cloud Study. The Computergraphical Mathematics Laboratory at Georgia Institute of Technology (Animation). 1987.
• [5] Elton J.: An ergodic theorem for iterated maps. J. Ergodic Theory Dynamical Sys, 7(4), 481-8.1987.
• [6] Barnsley M.F., Jacquin A., Malassenet F., Reuter L., Sloan A.D.: Harnessing chaos for image synthesis. SIGGRAPH '88, 22, 131-140. 1988.
• [7] Sabella P.: A rendering algorithm for visualizing 3D scalar fields. SIGGRAPH '88, 22(4), 51-61. 1988.
• [8] Peitgen H.-O., Saupe D. (editors): The Science of Fractal Images. New York: Springer-Verlag. 1988.
• [9] Barnsley M.F., Elton J.H., Hardin D.P.: Recurrent iterated function systems. Constructive Approximation, 5, 3-31. 1989.
• [10] Hepting D., Prusinkiewicz P., Saupe D.: Rendering methods for iterated function systems. In: Peitgen H.-O., Henriques J.M., Penedo L.F. (editors): Fractals in the Fundamental and Applied Sciences. Amsterdam: North-Holland, 1991.
• [11] Hart J.C., DeFanti T.A.: Efficient antialiased rendering of 3-D linear fractals. SIGGRAPH '91, 25, 91-100. 1991.
• [12] Laur D., Hanrahan P.: Hierarchical splatting: A progresive refinement algorithm for volume rendering. SIGGRAPH '91, 25, 285-288. 1991.
• [13] Press W.H., Flannery B.P., Teukolsky S.A., Vetterling W.T.: Numerical Recipes in C, 2nd ed. Cambridge: Cambridge University Press. 1992.
• [14] Barnsley M.F.: Fractals Everywhere, 2nd ed. Boston: Academic Press. 1993.
• [15] Cullip T.J., Neumann U.: Accelerating volume reconstruction with 3D texture hardware. Tech. Rep. TR93-027, University of North Caroline at Chapel Hill. 1993.
• [16] Cabral B., Cam N., Foran J.: Accelerated volume rendering and tomographic reconstruction using texture mapping hardware. ACM Symp. on Volume Visualization, 91-98. 1994.
• [17] Fisher Y. (editor): Fractal Image Compression. New York: Springer-Verlag. 1995.
• [18] Cochran W.O., Hart J.C., Flynn P.J.: Fractal volume compression. IEEE Transactions on Visualization and Computer Graphics, 2(4), 313-322. 1996.
• [19] Gutierrez J.M., Iglesias A., Rodriguez M.A.: A multifractal analysis of IFSP invariant measures with application to fractal image generation. Fractals, 4(1), 17-27. 1996.
• [20] Dellnitz M., Hohmann A., Junge O., Rumpf M.: Exploring invariant sets and invariant measures. CHAOS, 7(2), 221-228. 1997.
• [21] Wegenkittel R., Lofellmann H., Groller E.: Visualizing the behavior of higher dimensional dynamical systems. Proceedings of IEEE Visualization '97, 119-125. 1997.
• [22] Dellnitz M., Junge O.: An adaptive subdivision technique for the approximation of attractors and invariant measures. Computation and Visualization in Science, 1, 63-68. 1998.
• [23] Edgar G.A.: Integral, Probability, and Fractal Measures. New York: Springer-Verlag. 1998.
• [24] Elber G.: Line art illustrations of parametric and implicit forms. IEEE Transactions on Visualization and Computer Graphics, 4(1), 71-81. 1998.
• [25] Burkle D., Dellnitz M., Junge O., Rumpf M., Spielberg M.: Visualizing Complicated Dynamics. Proceedings of IEEE Visualization '99, 33-36. 1999.
• [26] Alligood K.T., Sauer T.D., Yorke J.A.: Chaos. An Introduction to Dynamical Systems, 3nd ed. New York: Springer-Verlag. 2000.
• [27] Rezk-Salama C, Engel K., Bauer M., Greiner G., Ertl T.: Interactive volume rendering on standard PC graphics hardware using multi-textures and multi-stage rasterization. Graphics Hardware 2000, 109-118. 2000.
• [28] Harte D.: Multifractals: Theory and Applications. Boca Raton: Chapman&Hall/CRC. 2001.
• [29] Morato L.M., Siri P.: A stochastic algorithm to compute optimal probabilities in the chaos game. Adv. Appl. Prob., 33(2), 423-436. 2001.
• [30] Krüger J., Westermann R.: Acceleration techniques for GPU-based volume rendering. Proceedings of IEEE Visualization '03, 287-292. 2003.
• [31] Martyn T.: Tight bounding ball for affine IFS attractor. Computers & Graphics, 27(4), 535-552. 2003.
• [32] Martyn T.: A method for numerical estimation of generalized Rényi dimensions of affine recurrent IFS invariant measures, In: M.M. Novak (ed.): Thinking in Patterns. Singapore: World Scientific. 2004.
• [33] Morato, L.M., Siri, P.: Addendum to stochastic algorithm to compute optimal probabilities in the chaos game: a new convergence criterion. Adv. Appl. Prob., 36(1), 318-323. 2004.
• [34] Harris M., Buck I.: GPU flow-control idioms. In: M. Pharr (ed.): GPU Gems 2. Upper Saddle River, NJ: Addison-Wesley, 547-555. 2005.
• [35] Stegmaier S., Strengert M., Klein T., Ertl T.: A simple and flexible volume rendering framework for graphics-hardware-based raycasting. Proceedings of the International Workshop on Volume Graphics '05, 187-195. 2005.
• [36] Barnsley M.F.: Super fractals. Cambridge: Cambridge University Press. 2006.
• [37] Strengert M., Klein T., Botchen R., Stegmaier S., Chen M., Ertl T.: Spectral volume rendering using GPU-based raycasting. Visual Computer, 22, 550-561. 2006.