## 3D photography

### Background

The goal of 3D photography is the inverse of computer aided manufacturing: given a physical object, such as a clay model of a car, a statue, a turbine blade, or a house, create a computer model of the object, capturing its shape, color, reflectance, and other visual properties.

3D scanning is similar in principle to a number of other important technologies (like digital audio, photography, and video) that convert aspects of physical reality into digital form. These technologies have a large impact because digital representations can be stored in data bases, transmitted over the Internet, viewed on CRTs, used in computer simulations, manipulated and edited in software, and used as templates for making electronic or physical copies.

3D scanning requires sensors to collect data on the appearance of the target object, and algorithms to convert these data into computer models. Sensors (``laser scanners'', ``range cameras'') typically produce samples of colored 3D points on the surface of the target object.

In statistics terminology, converting range data into a colored surface model means (1) estimating a 2D manifold in 3D space from a sample of points scattered around the manifold, and (2) estimating functions (color, reflectance) on manifolds of arbitrary topological type. While estimation of functions over euclidean space has been extensively studied, there has been little previous work on estimating functions on more general manifolds. Estimation of manifolds is a much more difficult problem than function estimation. Indeed, an approach to manifold estimation is to construct a simple domain, such as a simplicial surface, of the same topological type as the unknown manifold, and then estimate the coordinate functions.

Principal collaborators

The 3D Photography project was initiated by faculty members Tony DeRose (CSE), Tom Duchamp (Mathematics), John McDonald (Statistics) and Werner Stuetzle (Statistics). Many others - faculty members, graduate students, and staff members from Microsoft Research - made significant contributions.

### Contributions

Invented the first algorithm capable of estimating manifolds of arbitrary topological type from unorganized point data. The algorithm estimates the topological type as well as the geometric shape of the manifold. The output of the algorithm is a triangular mesh (surface consisting of planar triangles pasted together along their edges).

Figure 5a: Laser scan of an oil pump

Figure 5b: Piecewise smooth subdivision surface

Invented a new surface representation (``piecewise smooth subdivision surfaces'') and an algorithm to fit such surfaces to point data. Figure 5 shows a sample of points obtained by scanning an oil pump, and a piecewise smooth subdivision surface fit to the data. The fitting algorithm determines the number of vertices and the connectivity of the control mesh, the positions of the control points, as well as the presence and location of sharp features.

Figure 6a: High resolution bunny mesh;

Figure 6b:  Medium resolution wavelet approximation

Figure 6c: Low resolution wavelet approximation

Invented a method for multiresolution analysis of arbitrary meshes. The basic problem is that multiresolution (wavelet) analysis is a concept defined for functions, whereas meshes are manifolds. The key component of the method is an algorithm that converts a mesh, given in the form of vertices, edges, and faces, into parametric form. The algorithm represents the mesh as a piecewise linear embedding of a simple base complex. The coordinate functions of the embedding can then be expanded into wavelets. Figure 6 shows the model of a bunny and wavelet approximations at two different levels of detail.

## Publications

 Spline smoothing on surfaces. T. Duchamp and W. Stuetzle. Journal of Computational and Graphical Statistics, Vol. 12, No. 3, 2003, pp. 354-381. Surface light fields for 3D photography. D. Wood, D. Azuma, K. Aldinger, B. Curless, T. Duchamp, D. Salesin, and W. Stuetzle. Computer Graphics, Vol. 34, 2000 (SIGGRAPH '00 Proceedings). Acquisition and visualization of colored 3D objects. K. Pulli, H. Abi-Rached, T. Duchamp, L. Shapiro, and W. Stuetzle.   Proceedings of The 14th International Conference on Pattern Recognition, Brisbane, Australia, August, 1998. PDF View-based rendering: visualizing real objects from scanned range and color data. K. Pulli, M. Cohen, T. Duchamp, H. Hoppe, L. Shapiro, and W. Stuetzle. Proceedings of 8th Eurographics Workshop on Rendering, June 1997. Robust meshes from multiple range maps. K. Pulli, T. Duchamp, H. Hoppe, J. McDonald, L. Shapiro, and W. Stuetzle. Proceedings of International Conference on Recent Advances in 3-D Digital Imaging and Modeling, pages 205-211, May 1997.PDF Interactive multiresolution surface viewing. Andrew Certain, Jovan Popovic, Tony DeRose, Tom Duchamp, and W. Stuetzle.  Computer Graphics, Vol. 30, 1996 (SIGGRAPH '96 Proceedings), pp. 91--98. Vertex-based Delaunay triangulation of meshes of arbitrary topological type. A. Klein, A. Certain, A. DeRose, T. Duchamp, and W. Stuetzle. Technical Report, July 1997. PDF Multiresolution analysis of arbitrary meshes. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle.   Computer Graphics, Vol. 29, 1995 (SIGGRAPH '95 Proceedings), pp. 173--182. Piecewise smooth surface reconstruction. H. H.Hoppe, T. DeRose, T. Duchamp, M. Halstead, H.Jin, J.A. McDonald, J. Schweitzer, and W. Stuetzle. Computer Graphics, Vol. 28, 1994, (SIGGRAPH '94Proceedings), pp. 295--302. Mesh optimization. H. H.Hoppe, T. DeRose, T. Duchamp, J.A. McDonald, and W. Stuetzle.  Computer Graphics, Vol. 27, 1993, (SIGGRAPH '93Proceedings), pp. 19--26. Surface reconstruction from unorganized points. H. H.Hoppe, T. DeRose, T. Duchamp, J.A. McDonald, and W. Stuetzle.   Computer Graphics, Vol. 26,1992, (SIGGRAPH '92 Proceedings), pp. 71--78.