Generalized stochastic subdivision

ABSTRACT

Stochastic techniques have assumed a prominent role in computer graphics because of their success in modeling a variety of complex and natural phenomena. This paper describes the basis for techniques such as stochastic subdivision in the theory of random processes and estimation theory. The popular stochastic subdivision construction is then generalized to provide control of the autocorrelation and spectral properties of the synthesized random functions. The generalized construction is suitable for generating a variety of perceptually distinct high-quality random functions, including those with non-fractal spectra and directional or oscillatory characteristics. It is argued that a spectral modeling approach provides a more powerful and somewhat more intuitive perceptual characterization of random processes than does the fractal model. Synthetic textures and terrains are presented as a means of visually evaluating the generalized subdivision technique.

REFERENCES

• 1: Box, G., AND JENKINS, G. Time Series Analysis. Holden-Day, San Francisco, Calif., 1976.
• 2: BRACEWELL, R. The Fourier Transform and Its Applications. McGraw-Hill, New York, 1965.
• 3: BURROUGH, P. Fractal dimensions of landscapes and other environmental data. Nature 294 (Nov. 1981), 240-243.
• 4: Loren C. Carpenter, Computer rendering of fractal curves and surfaces, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.109, July 14-18, 1980, Seattle, Washington, United States
• 5: CHELLAPPA, R., AND KASHYAP, R. Texture synthesis using 2-D noncausal autoregressive models. IEEE Acoust. Speech Signal Process. 33, 1 (Feb. 1985), 194-203.
• 6: DEUTSCH, R. Estimation Theory. Prentice-Hall, Englewood Cliffs, N.J., 1965.
• 7: ELASSAL, A., AND CARUSO, V. Digital Elevation Models. National Cartographic Information Center, Reston, Va., 1984.
• 8: FELLOUS, A., GRANARA, J., AND HOURCADE, J. Fractional Brownian relief: An exact local method. In Proceedings of Eurographics 85 (Geneva, Switzerland, Sept.). North Holland, New York, 1985, pp. 353-363.
• 9: A Fournier , T Milligan, Frame buffer algorithms for stochastic models, Proceedings of Graphics Interface '85 on Computer-generated images: the state of the art, p.35-44, January 1986, Montreal, Quebec, Canada
• 10: Alain Fournier , Don Fussell , Loren Carpenter, Computer rendering of stochastic models, Communications of the ACM, v.25 n.6, p.371-384, June 1982 [doi>10.1145/358523.358553]
• 11: GAGALOWICZ, A., AND SONG, D.M. Sequential synthesis of natural textures. Comput. Vision Graph. Image Process. 30, 9 (Sept. 1985), 289-315.
• 12: GAGALOWICZ, A., AND SONG, D.M. Model driven synthesis of natural textures for 3-D scenes. In Proceedings of Eurographics 85 (Geneva, Switzerland, Sept.). North Holland, New York, 1985, pp. 91-108.
• 13: HARUYAMA, S., AND BARSKY, B. Using stochastic models for texture generation. IEEE Comput. Graph. Appl. 4, 3 (Mar. 1984), 7-21.
• 14: JULESZ, B. Visual pattern discrimination. IEEE Trans. Inf. Theory 8, 2 (Feb. 1962), 84-92.
• 15: LEVINSON, N. The Wiener RMS (root mean square) error criterion in filter design and prediction. J. Math. Phys. 25 (1947), 261-278.
• 16: J P Lewis, Methods for stochastic spectral synthesis, Proceedings on Graphics Interface '86/Vision Interface '86, p.173-179, August 1986, Vancouver, British Columbia, Canada
• 17: LEWIS, J.P. Algorithms for solid noise synthesis. Unpublished paper, Nov. 1986.
• 18: MAKHOUL, J. Spectral analysis of speech by linear prediction. IEEE Trans. Audio Electroacoust. AU-21 (June 1973), 140-148.
• 19: MANDELBROT, B. Comptes Rendus Acad. Paris 260 (1965), 3274-3277.
• 20: MANDELBROT, B. Stochastic models for the Earth's relief, the shape and dimension of the coastlines, and the number-area rule for islands. Proc. Natl. Acad. Sci. USA 72, 10 (Oct. 1975), 3825-3828.
• 21: MARK, D., AND ARONSON, P. Scale-dependent fractal dimensions of topographic surfaces. Dept. of Geography, State Univ. of New York, Buffalo.
• 22: John E. Markel , A. H. Gray, Linear Prediction of Speech, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 23: MATHERON, G. The intrinsic random functions and their applications. Adv. Appl. Probab. 5 (1973), 439-468.
• 24: MCLEOD, A., AND HIPEL, K. Preservation of the rescaled adjusted range (2: Simulation studies using Box-Jenkins models). Water Resour. Res. 14 (1978), 491-508.
• 25: Gavin S P Miller, The definition and rendering of terrain maps, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.39-48, August 1986
• 26: NELKIN, M., AND TREMBLAY, A-M. Deviation of 1If voltage fluctuations from scale-similar Gaussian behavior. J. Stat. Phys. 25, 2 (Feb. 1981), 253-268.
• 27: PANCHEV, S. Random Functions and Turbulence. Pergamon, Elmsford, N.Y., 1971.
• 28: PAPOULIS, A. Signal Analysis. McGraw-Hill, New York, 1977.
• 29: PELEG, S., NAOR, J., HARTLEY, R., AND AVNIR, D. Multiple-resolution texture analysis and classification. Tech. Rep. TR-1306, Computer Science Dept., Univ. of Maryland, College Park, July 1983.
• 30: Ken Perlin, An image synthesizer, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.287-296, July 1985
• 31: Ken Perlin, An image synthesizer, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.287-296, July 1985
• 32: PRATT, W., FAUGERAS, O., AND GAGALOWICZ, A. Visual discrimination of stochastic texture fields. IEEE Trans. Syst. Man Cybern. 8, 11 (Nov. 1978), 796-804.
• 33: PRATT, W., FAUGERAS, O., AND GAGALOWICZ, A. Applications of stochastic texture field models to image processing. Proc. IEEE 69, 5 (May 1981), 542-551.
• 34: RAmNER, L., AND SCHAFER, R. Digital Processing of Speech Signals. Prentice-Hall, Englewood Cliffs, N.J., 1979.
• 35: W. T. Reeves, Particle Systems—a Technique for Modeling a Class of Fuzzy Objects, ACM Transactions on Graphics (TOG), v.2 n.2, p.91-108, April 1983 [doi>10.1145/357318.357320]
• 36: William T. Reeves , Ricki Blau, Approximate and probabilistic algorithms for shading and rendering structured particle systems, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.313-322, July 1985
• 37: RICHARDSON, L. Gen. Syst. Yearb. 6 (1961), 139-187.
• 38: SCHAFER, R., AND RABINER, L. A digital signal processing approach to interpolation. Proc. IEEE 61, 6 (June 1973), 692-702.
• 39: SCHEIDEG6ER, A. Theoretical Geomorphology. Springer-Verlag, New York, 1970.
• 40: Alvy Ray Smith, Plants, fractals, and formal languages, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.1-10, July 1984
• 41: VANMARCKE, E. Random Fields. MIT Press, Cambridge, Mass., 1983.
• 42: Voss, R. Fractal Lunar Mist. SIGGRAPH proceedings cover image, (Detroit, Mich., July). ACM, New York, 1983.
• 43: Voss, R. Random fractal forgeries. In SIGGRAPH Conference Tutorial Notes (July). ACM, New York, 1985.
• 44: Norbert Wiener, Extrapolation, Interpolation, and Smoothing of Stationary Time Series, The MIT Press, 1964
• 45: YAGLOM, A. An Introduction to the Theory of Stationary Random Functions. Dover, New York, 1973.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms