From splines to fractals

ABSTRACT

Deterministic splines and stochastic fractals are complementary techniques for generating free-form shapes. Splines are easily constrained and well suited to modeling smooth, man-made objects. Fractals, while difficult to constrain, are suitable for generating various irregular shapes found in nature. This paper develops constrained fractals, a hybrid of splines and fractals which intimately combines their complementary features. This novel shape synthesis technique stems from a formal connection between fractals and generalized energy-minimizing splines which may be derived through Fourier analysis. A physical interpretation of constrained fractal generation is to drive a spline subject to constraints with modulated white noise, letting the spline diffuse the noise into the desired fractal spectrum as it settles into equilibrium. We use constrained fractals to synthesize realistic terrain models from sparse elevation data.

REFERENCES

• 1: J. H. Ahlberg, E. N. Nilson, and J. L. Walsh. The Theory of Sptines and their Applications. Academic Press, New York, 1967.
• 2: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 3: Thomas A. Foley, Weighted bicubic spline interpolation to rapidly varying data, ACM Transactions on Graphics (TOG), v.6 n.1, p.1-18, Jan. 1987 [doi>10.1145/27625.27626]
• 4: 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]
• 5: H. Fuchs , Z. M. Kedem , S. P. Uselton, Optimal surface reconstruction from planar contours, Communications of the ACM, v.20 n.10, p.693-702, Oct. 1977 [doi>10.1145/359842.359846]
• 6: Stuart Geman , Chii-Ruey Hwang, Diffusions for global optimizations, SIAM Journal on Control and Optimization, v.24 n.5, p.1031-1043, Sept. 1986 [doi>10.1137/0324060]
• 7: S. Geman and D. Geman. Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):7'21-'/41, November 1984.
• 8: Berthold Klaus Paul Horn, Robot vision, MIT Press, Cambridge, MA, 1986
• 9: J. P. Lewis, Generalized stochastic subdivision, ACM Transactions on Graphics (TOG), v.6 n.3, p.167-190, July 1987 [doi>10.1145/35068.35069]
• 10: B. B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman, San Fzancisco, 1982.
• 11: D. G. Schweikezt. An interpolation curve using spline in tension. J. Math. and Physics, 45:312-317, 1966.
• 12: Richard Stephen Szeliski, Bayesian modeling of uncertainty in low-level vision, 1988
• 13: R. Szellski. Regutarization uses fractal priors. ~'.u AAAI- 87: Sixth National Conference on Artificial 2~telligence, pages 749-154, Morgan Kaufmann Publishers, Seattle, Washington, July 198"/.
• 14: R. Szeliski and D. Terzopoulos. Constrained fractals using stochastic relaxation. Submitted to A CM Transactions on Graphics, 1989.
• 15: D. Terzopoulos. Multilevel computational processes for visual surface reconstruction. Computer Visiont Graphics, and Image Processing, 24:52-96, 1983.
• 16: Demetri Terzopoulos, Regularization of inverse visual problems involving discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.4, p.413-242, July 1986 [doi>10.1109/TPAMI.1986.4767807]
• 17: D. Terzopoulos and K. Fleischer. Deformable models. The Visual Computer, 4(6):306-331, December, 1988.
• 18: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.205-214, July 1987
• 19: It. F. Voss. Random fractal forgeries, in R. A. Earnshaw, editor, Fundamental Algorithms for Computer Graphics, Springer-Verlag, Berlin, 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

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

General Terms:
Algorithms