We present a variational framework for rapid shape prototyping. The modeled shape is represented as a Catmull-Clark multiresolution subdivision surface which is interactively deformed by direct user input. Free-form design goals are formulated as constraints on the shape and the modeling problem is cast into a constrained optimization one. The focus of this paper is on handling multiresolution constraints of different kinds and on preserving surface details throughout the deformation process. Our approach eliminates the need for an explicit decomposition of the input model into frequency bands and the overhead associated with saving and restoring high-frequency detail after global shape fairing. Instead, we define a deformation vector field over the model and we optimize its energy. Surface details are considered as part of the rest shape and are preserved during free-form model editing. We explore approximating the solution of the optimization problem to various degrees to balance trade-offs between interactivity and accuracy of the results.

Three‐dimensional (3D) image acquisition systems are rapidly becoming more affordable, especially systems based on commodity electronic cameras. At the same time, personal computers with graphics hardware capable of displaying complex 3D models are also becoming inexpensive enough to be available to a large population. As a result, there is potentially an opportunity to consider new virtual reality applications as diverse as cultural heritage and retail sales that will allow people to view realistic 3D objects on home computers. Although there are many physical techniques for acquiring 3D data—including laser scanners, structured light and time‐of‐flight—there is a basic pipeline of operations for taking the acquired data and producing a usable numerical model. We look at the fundamental problems of range image registration, line‐of‐sight errors, mesh integration, surface detail and color, and texture mapping. In the area of registration we consider both the problems of finding an initial global alignment using manual and automatic means, and refining this alignment with variations of the Iterative Closest Point methods. To account for scanner line‐of‐sight errors we compare several averaging approaches. In the area of mesh integration, that is finding a single mesh joining the data from all scans, we compare various methods for computing interpolating and approximating surfaces. We then look at various ways in which surface properties such as color (more properly, spectral reflectance) can be extracted from acquired imagery. Finally, we examine techniques for producing a final model representation that can be efficiently rendered using graphics hardware.

Cutting and pasting to combine different elements into a common structure are widely used operations that have been successfully adapted to many media types. Surface design could also benefit from the availability of a general, robust, and efficient cut-and-paste tool, especially during the initial stages of design when a large space of alternatives needs to be explored. Techniques to support cut-and-paste operations for surfaces have been proposed in the past, but have been of limited usefulness due to constraints on the type of shapes supported and the lack of real-time interaction. In this paper, we describe a set of algorithms based on multiresolution subdivision surfaces that perform at interactive rates and enable intuitive cut-and-paste operations.

In this paper we describe a method for creating sharp features and trim regions on multiresolution subdivision surfaces along a set of user-defined curves. Operations such as engraving, embossing, and trimming are important in many surface modeling applications. Their implementation, however, is non-trivial due to computational, topological, and smoothness constraints that the underlying surface has to satisfy. The novelty of our work lies in the ability to create sharp features anywhere on a surface and in the fact that the resulting representation remains within the multiresolution subdivision framework. Preserving the original representation has the advantage that other operations applicable to multiresolution subdivision surfaces can subsequently be applied to the edited model. We also introduce an extended set of subdivision rules for Catmull-Clark surfaces that allows the creation of creases along diagonals of control mesh faces.

We present a method for computing horizon maps from captured images of a bumpy surface. 1Horizon maps encode surface self-shadowing effects, and can be used with bump or normals maps to realistically render surfaces with small height perturbations. The method does not rely on complete surface reconstruction, and requires only eight captured images as input. In this paper we discuss how shadow information is extrapolated from the eight captured images to compute the horizon map. Our implementation accounts for the noise and uncertainties in physically acquired data.

The creation of three-dimensional digital content by scanning real objects has become common practice in graphics applications for which visual quality is paramount, such as animation, e-commerce, and virtual museums. While a lot of attention has been devoted recently to the problem of accurately capturing the geometry of scanned objects, the acquisition of high-quality textures is equally important, but not as widely studied. In this paper, we focus on methods to construct accurate digital models of scanned objects by integrating high-quality texture and normal maps with geometric data. These methods are designed for use with inexpensive, electronic camera-based systems in which low-resolution range images and high-resolution intensity images are acquired. The resulting models are well-suited for interactive rendering on the latest-generation graphics hardware with support for bump mapping. Our contributions include new techniques for processing range, reflectance, and surface normal data, for image-based registration of scans, and for reconstructing high-quality textures for the output digital object.

We present a technique for accelerating the rendering of high depth‐complexity scenes. In a preprocessing stage, we approximate the input model with a hierarchical data structure and compute simple view‐dependent polygonal occluders to replace the complex input geometry in subsequent visibility queries. When the user is inspecting and visualizing the input model, the computed occluders are used to avoid rendering geometry which cannot be seen. Our method has several advantages which allow it to perform conservative visibility queries efficiently and it does not require any special graphics hardware. The preprocessing step of our approach can also be used within the framework of other visibility culling methods which need to pre‐select or pre‐render occluders. In this paper, we describe our technique and its implementation in detail, and provide experimental evidence of its performance. In addition, we briefly discuss possible extensions of our algorithm.

The Ball-Pivoting Algorithm (BPA) computes a triangle mesh interpolating a given point cloud. Typically, the points are surface samples acquired with multiple range scans of an object. The principle of the BPA is very simple: Three points form a triangle if a ball of a user-specified radius p touches them without containing any other point. Starting with a seed triangle, the ball pivots around an edge (i.e., it revolves around the edge while keeping in contact with the edge's endpoints) until it touches another point, forming another triangle. The process continues until all reachable edges have been tried, and then starts from another seed triangle, until all points have been considered. The process can then be repeated with a ball of larger radius to handle uneven sampling densities. We applied the BPA to datasets of millions of points representing actual scans of complex 3D objects. The relatively small amount of memory required by the BPA, its time efficiency, and the quality of the results obtained compare favorably with existing techniques.

Reconstructing the shape of a 3D object from a digital scan of its surface has a range of applications, such asreverse engineering, authoring 3D synthetic worlds, shape analysis, 3D faxing and tailor-fit modeling. Input data

We present an efficient and uniform approach for the automatic reconstruction of surfaces of CAD (computer aided design) models and scalar fields defined on them, from an unorganized collection of scanned point data.A possible application is the rapid computer model reconstruction of an existing part or prototype from a three dimensional (3D) points scan of its surface.Color, texture or some scalar material property of the physical part, define natural scalar fields over the surface of the CAD model.Our reconstruction algorithm does not impose any convexity or differentiability restrictions on the surface of the original physical part or the scalar field function, except that it assumes that there is a sufficient sampling of the input point data to unambiguously reconstruct the CAD model.Compared to earlier methods our algorithm has the advantages of simplicity, efficiency and uniformity (both CAD model and scalar field reconstruction).The simplicity and efficiency of our approach is based on several novel uses of appropriate sub-structures (alpha shapes) of a three-dimensional Delaunay Triangulation, its dual the three-dimensional Voronoi diagram, and dual uses of trivariate Bernstein-Bézier forms.The boundary of the CAD model is modeled using implicit cubic Bernstein-Bézier patches, while the scalar field is reconstructed with functional cubic Bernstein-Bézier patches.

Dealing with simplicial decompositions which are dimension independent allows for the convergence of disparate viewpoints from computer graphics, solid and geometric modeling.In this framework it is possible to treat in a unified manner several geometric problems, such as solid modeling of articulated objects, simplicial approximation of curved manifolds, motion encoding and interference detection, free configuration space computation, and graphical representation of multidimensional data.In the paper the authora describe the winged scheme, a simple representation based on simplicial decompositions, which can be used for linear polyhedra of any dimension and which allows for "solid" approximation of curved manifolds when combined with curved maps (e.g., NURBS).Various operators and algorithms are discussed, including boundary evaluation, linear and screw extrusion, grid generation, simplicial maps, and set operations.A simple manipulation language is also introduced, and some nontrivial examples are discussed.