“Adaptively sampled distance fields: a general representation of shape for computer graphics” by Frisken, Perry, Rockwood and Jones

Adaptively Sampled Distance Fields (ADFs) are a unifying representation of shape that integrate numerous concepts in computer graphics including the representation of geometry and volume data and a broad range of processing operations such as rendering, sculpting, level-of-detail management, surface offsetting, collision detection, and color gamut correction. Its structure is uncomplicated and direct, but is especially effective for quality reconstruction of complex shapes, e.g., artistic and organic forms, precision parts, volumes, high order functions, and fractals. We characterize one implementation of ADFs, illustrating its utility on two diverse applications: 1) artistic carving of fine detail, and 2) representing and rendering volume data and volumetric effects. Other applications are briefly presented.

1. R. Avila and L. Sobierajski, “A haptic interaction method for volume visualization”, Proc. IEEE Visualization’96, pp. 197-204, 1996.
2. J. Baerentzen, “Octree-based volume sculpting”, Proc. Late Breaking Hot Topics, IEEE Visualization’98, pp. 9-12, 1998.
3. J. Bloomenthal, Introduction to Implicit Surfaces, Morgan Kaufman Publishers, 1997.
4. D. Breen, S. Mauch and R. Whitaker, “3D scan conversion of CSG models into distance volumes”, Proc. 1998 IEEE Symposium on Volume Visualization, pp. 7-14, 1998.
5. M. Chow and M. Teichmann, “A Wavelet-Based Multiresolution Polyhedral Object Representation”, Visual Proc. SIGGRAPH ’97, p. 175, 1997.
6. P. Cignoni, L. De Floriani, C. Montani, E. Puppo, R. Scopigno, “Multiresolution Modeling and Rendering of Volume Data based on Simplicial Complexes”, 1994 ACM Volume Visualization Conference Proceedings, 1994, pp. 19-26.
7. D. Cohen-Or, D. Levin, and A. Solomovici, “Three-dimensional distance field metamorphosis”, ACM Transactions on Graphics, 1997.
8. T. DeRose, M. Kass, T. Truong, “Subdivision surfaces in character animation”, Proc. SIGGRAPH ’98, pp. 85-94, 1998.
9. D. Ebert, F.K. Musgrave, D. Peachy, K. Perlin, S. Worley, Texturing and Modeling a Procedural Approach, Academic Press, 1998.
10. J. Foley, A. van Darn, S. Feiner, and J. Hughes, Computer Graphics: Principles and Practice, Addison-Wesley, 1992.
11. S. Gibson, “Using DistanceMaps for smooth surface representation in sampled volumes”, Proc. 1998 IEEE Volume Visualization Symposium, pp. 23-30, 1998.
12. R. Kimmel, N. Kiryati and A. Bruckstein, “Multi-valued distance maps for motion planning on surfaces with moving obstacles”, IEEE Trans. on Robotics & Automation, 14, pp. 427- 436, 1998.
13. J. Lengyel, M. Reichert, B. Donald and D. Greenberg, “Real-time robot motion planning using rasterizing computer graphics hardware”, Proc. SIGGRAPH ’90, pp. 327-335, 1990.
14. T. Nishita, T.W. Sederberg and M. Kakimoto, “Ray tracing trimmed rational surface patches”, Proc. SIGGRAPH ’90, pp. 337-345, 1990.
15. S. Osher and J. Sethian, “Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulation”, J. Computational Physics, 79, pp. 12-49, 1988.
16. S. Parker, M. Parker, Y. Livnat, P. Sloan, C. Hansen, and P. Shirley, “Interactive ray tracing for volume visualization” IEEE Transactions On Visualization and Computer Graphics, Vol. 5 (3), pp. 238-250, 1999.
17. B. Payne and A. Toga, “Distance field manipulation of surface models”, IEEE Computer Graphics and Applications, pp. 65-71, 1992.
18. A. Ricci, “A constructive geometry for computer graphics”, Computer Journal, Vol. 16, No. 2, pp. 157-160, 1973.
19. H. Samet, The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.
20. W. Schroeder, W. Lorensen, and S. Linthicum, “Implicit modeling of swept surfaces and volumes,” Proc. Visualization ’94, pp. 40-45, 1994.
21. Sensable Devices’ FreeForm modeling software, http://www.sensable.com/freeform.
22. J. Sethian, Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics. Computer Vision, and Material Science. Cambridge University Press, 1996.
23. M. Stone, W. Cowan, J. Beatty, “Color gamut mappings and the printing of digital color images”, ACM Transaction on Graphics, Vol. 7, pp. 249-292, 1988.
24. R. Westermann, O. Sommer, T. Ertl, “Decoupling polygon rendering from geometry using rasterization hardware”, in Proc. Eurographics Rendering Workshop ’99, pp. 45-56, 1999.
25. R. Yagel, S. Lu, A. Rubello, R. Miller, “Volume-based reasoning and visualization of dicastability” In Proc. IEEE Visualization ’95, pp. 359-362, 1995.
26. K. Zuiderveld, A. Koning, and M. Viergever, “Acceleration of ray-casting using 3D distance transforms”, in Proc. Visualization in Biomedical Computing ’92, pp. 324-335, 1992.