Voxel space automata: modeling with stochastic growth processes in voxel space

ABSTRACT

A novel stochastic modeling technique is described which operates on a voxel data base in which objects are represented as collections of voxel records. Models are "grown" from predefined geometric elements according to rules based on simple relationships like intersection, proximity, and occlusion which can be evaluated more quickly and easily in voxel space than with analytic geometry. Growth is probabilistic: multiple trials are attempted in which an element's position and orientation are randomly perturbed, and the trial which best fits a set of rules is selected. The term voxel space automata is introduced to describe growth processes that sense and react to a voxel environment.Applications include simulation of plant growth, for which voxel representation facilitates sensing the environment. Illumination can be efficiently estimated at each plant "node" at each growth iteration by casting rays into the voxel environment, allowing accurate simulation of reaction to light including heliotropism.

REFERENCES

• 1: Arvo, James, David Kirk, Modeling Plants with Environment- Sensitive Automata, Proceedings of Ausgraph '88, 27-33.
• 2: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1]
• 3: Michael F. Cohen , Shenchang Eric Chen , John R. Wallace , Donald P. Greenberg, A progressive refinement approach to fast radiosity image generation, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.75-84, Aug. 1988
• 4: Robert L. Cook, Stochastic sampling in computer graphics, ACM Transactions on Graphics (TOG), v.5 n.1, p.51-72, Jan. 1986 [doi>10.1145/7529.8927]
• 5: Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 1988
• 6: Akira Fujimoto , Takayuki Tanaka , Kansei Iwata, ARTSccelerated ray-tracing system, IEEE Computer Graphics and Applications, v.6 n.4, p.16-26, April 1986 [doi>10.1109/MCG.1986.276715]
• 7: Cindy M. Goral , Kenneth E. Torrance , Donald P. Greenberg , Bennett Battaile, Modeling the interaction of light between diffuse surfaces, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.213-222, July 1984
• 8: Ned Greene, Environment mapping and other applications of world projections, IEEE Computer Graphics and Applications, v.6 n.11, p.21-29, November 1986 [doi>10.1109/MCG.1986.276658]
• 9: Greene, Ned, Organic Architecture {videotape}, Siggraph Video Review 38, (Aug. 1988), ACM Siggraph, New York, segment 16.
• 10: Halton, J. H., A Retrospective and Prospective Survey of the Monte Carlo Method, SlAM Rev., 12, 1 (Jan. 1970), 1-63.
• 11: Arie Kaufman , Eyal Shimony, 3D scan-conversion algorithms for voxel-based graphics, Proceedings of the 1986 workshop on Interactive 3D graphics, p.45-75, January 1987, Chapel Hill, North Carolina, United States [doi>10.1145/319120.319126]
• 12: Miller, Gene S., and C. Robert Hoffman, Illumination and Reflection Maps: Simulated Objects in Simulated and Real Environments, SIGGRAPH 84: Advanced Computer Animation Seminar Notes, (July 1984).
• 13: Alan Norton, Generation and display of geometric fractals in 3-D, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.61-67, July 1982
• 14: Peter E. Oppenheimer, Real time design and animation of fractal plants and trees, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.55-64, Aug. 1986
• 15: Preston, Kendall, and J. B. Duff, Modern cellular automata: theory and applications, Plenum, New York, 1984.
• 16: Przemyslaw Prusinkiewicz , Aristid Lindenmayer , James Hanan, Development models of herbaceous plants for computer imagery purposes, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.141-150, Aug. 1988
• 17: William T. Reeves, Particle systems—a technique for modeling a class of fuzzy objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.359-375, July 1983
• 18: Phillippe de Reffye , Claude Edelin , Jean Françon , Marc Jaeger , Claude Puech, Plant models faithful to botanical structure and developmentr, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.151-158, Aug. 1988
• 19: Paolo Sabella, A rendering algorithm for visualizing 3D scalar fields, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.51-58, Aug. 1988
• 20: Alvy Ray Smith, Plants, fractals, and formal languages, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.1-10, July 1984
• 21: Craig Upson , Michael Keeler, V-buffer: visible volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.59-64, Aug. 1988
• 22: Wyvill, Brian, Craig McPheeters, Geoff Wyvill, Data Structure for Soft Objects, The Visual Computer, 2, 4 (1986), 227-234.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms