“From splines to fractals” by Kolb and Terzopoulos

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.

1. J. H. Ahlberg, E. N. Nilson, and J. L. Walsh. The Theory of Sptines and their Applications. Academic Press, New York, 1967.
2. R. H. Baxtets, J. C. Beatty, and B. A. Barsky. An Introductior, to Splines for use in Computer Graphics and Geometric Modeling. Morgan Kau~mann, Los Altos~ CA, 1987.
3. T. A. Foley. Weighted bicubic spline interpolation to rapidly varying data. A CM Transactions on Graphics, 6(1):1-18, January 1987.
4. A. Fournier, D. Fussel, and L. Caxpenter. Computer rendering of stochastic models. Communications of the A CM, 25(6):371-384, 1982.
5. H. Fuchs, Z. M. Kedem, and S. P. Uselton. Optimal surface reconstruction from planar contours. Communications of the A CM, 20(10):693-702, October 1977.
6. D. Geman and Hwang C.-K. Diffusions for global optimization. SIAM Journal o/ Control and Optimization, 24(5):1031-1043, September 1986.
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. B. K. P. Horn. Robot Vision. MIT Press, Cambridge, Massachusetts, 1986.
9. 3. P. Lewis. Generalized stochastic subdivision. A CM Transactions on Graphics, 6(3):167-190, July 1987.
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. R. Szeliski. Bayesian Modeling of Uncertainty in Low- Level Vision. PhD thesis, Carnegie Mellon University, August 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. D. Terzopoulos. ltegularization of inverse visual problems involving discontinuities. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAML8(4):413-424, July 1986.
17. D. Terzopoulos and K. Fleischer. Deformable models. The Visual Computer, 4(6):306-331, December, 1988.
18. D. Terzopoulos, J. Platt, A. Burr, and K. Fleischer. Elastically deformable models. Computer Graphics (SIG- GRAPH’87), 21(4):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.