“Approximate and probabilistic algorithms for shading and rendering structured particle systems” by Blau and Reeves

Detail enhances the visual richness and realism of computer-generated images. Our stochastic modelling approach, called particle systems, builds complex pictures from sets of simple, volume-filling primitives. For example, structured particle systems have been used to generate trees and a grass-covered forest floor. Particle systems can produce so much irregular, three-dimensional detail that exact shading and visible surface calculations become infeasible. We describe approximate and probabilistic algorithms for shading and the visible surface problem. Because particle systems algorithms generate richly-detailed images, it is hard to detect any deviation from an exact rendering. Recent work in stochastic modelling also enables us to model complex motions with random variation, such as a field of grass blowing in the breeze. We analyze the performance of our current algorithms to understand the costs of our stochastic modelling approach.

1. Aono, M. and T. L. Kunii, Botanical tree image generation, IEEE Computer Graphics and Applications 4, 5 (May 1984), 10-34.]]
2. Bloomenthal, J., Modeling n~tural trees with space curves, SIGGRAPH 85j Computer Graphics 19, 3 (July 1985),]]
3. Brooks, J., R. Murarka, D. Onuoha, F. Rahn and H. Steingurg, An extension of the combinatorial geometry technique for modeling vegetation and terrain features, Contract report 159 for USA Ballistic Research Labortorles, Mathematical Applications Group, Inc., June 1974.]]
4. Crow, F. C., A more flexible image generation environment, SIGGRAPH 8~, Computer Graphics 16, 3 (July 1982), 9..18.]]
5. Fournier, A., D. Fusaell and L. Carpenter, Computer rendering of stochastic models, Comm. ACM ~5, 0 (June 1982), 371-384.]]
6. Gardner, G. Y., Simulation of natural scenes using textured quadric surfaces, SIGGIL4PH 8~, Computer Graphics 18, 3 (July 1984), 11-20.]]
7. Lucasfilm Ltd, The Adventures o/Andr~ and Wally B., (film), Aug. 1984.]]
8. Ludwig, C., Mazfleld Parrish, Watson-GuptUl, New York, 1973.]]
9. Mandelbrot, B. B., Fractals: Form, chance and dimension, Freeman, San Francisco, 1977.]]
10. Marshall, R., R. Wilson and W. Carlson, Procedure models for generating three-dimensional terrain, SIGGRAPH 80, Computer Graphics 14, 3 (July 1980), 154-162.]]
11. Paramount, Genesis Demo from Star Trek II: The Wrath of Khan, in SIGGRAPH Video Review Number 11, June 1982.]]
12. Reeves, W. T., Particle systems–A technique for modelling a class of fuzzy objects, S}GGRAPH 83, Computer Graphics 17, 3 (July 1983), 359-376.]]
13. Smith, A. R., Plants, fractals, and formal languages, SIG- GRAPH 84, Computer Graphics 18, 3 (July 1984), 1-10.]]
14. Whitted, T. and D. M. ~Teimer, A software testbed for the development of 3d raster graphics system~, Transaction8 on Graphics 1, 1 (Jan. 1982), 43-58.]]
15. Williams, L., Casting curved shadows on curved surfaces, SIGGRAPH 78, Computer Graphics 1~, 3 (Aug. 1978), 27O-274.]]