Abstract We introduce a new extrinsic discretization of tangent vector fields on triangle meshes that is continuous, with bounded derivatives that are continuous almost everywhere, supporting pointwise evaluation and integration of differential operators. We achieve this by building a continuous normal field over the mesh via Phong interpolation and using minimal Rodrigues rotations to transport vertex‐based tangent vectors into triangle interiors. Unlike most existing discretizations, which typically sacrifice either continuity or the ability to evaluate derivatives pointwise, our approach supports both. Because it is pointwise evaluatable, and using the fact that the covariant derivative can be decomposed into its symmetric, antisymmetric, and scalar components, our discretization supports the construction of standard vector‐field processing operators including the connection and Hodge Laplacians, Killing energy, divergence, curl, and the Lie bracket. This framework provides a simple and practical finite‐element formulation for vector‐field processing on meshes, supporting both integration‐based operators and pointwise queries. To our knowledge, ours is the first discretization that jointly enables extrinsic continuous vector fields, bounded derivatives, and pointwise evaluation of this collection of operators.

Abstract Many common approaches for reconstructing surfaces from point clouds leverage normal information to fit an implicit function to the points. Normals typically play two roles: the direction provides a planar approximation to the surface and the sign distinguishes inside from outside. When the sign is missing, reconstructing a surface with globally consistent sidedness is challenging. In this work, we investigate the idea of squaring the Poisson Surface Reconstruction, replacing the normals with their outer products, making the approach agnostic to the signs of the input/estimated normals. Squaring results in a quartic optimization problem, for which we develop an iterative and hierarchical solver, based on setting the cubic partial derivatives to zero. We show that this technique significantly outperforms standard L‐BFGS solver and demonstrate reconstruction of surfaces from unoriented noisy input in linear time.

Total Body Photography (TBP) is becoming a useful screening tool for patients at high risk for skin cancer. While much progress has been made, existing TBP systems can be further improved for automatic detection and analysis of suspicious skin lesions, which is in part related to the resolution and sharpness of acquired images. This paper proposes a novel shape-aware TBP system automatically capturing full-body images while optimizing image quality in terms of resolution and sharpness over the body surface. The system uses depth and RGB cameras mounted on a 360-degree rotary beam, along with 3D body shape estimation and an in-focus surface optimization method to select the optimal focus distance for each camera pose. This allows for optimizing the focused coverage over the complex 3D geometry of the human body given the calibrated camera poses. We evaluate the effectiveness of the system in capturing high-fidelity body images. The proposed system achieves an average resolution of 0.068 mm/pixel and 0.0566 mm/pixel with approximately 85% and 95% of surface area in-focus, evaluated on simulation data of diverse body shapes and poses as well as a real scan of a mannequin respectively. Furthermore, the proposed shape-aware focus method outperforms existing focus protocols (e.g. auto-focus). We believe the high-fidelity imaging enabled by the proposed system will improve automated skin lesion analysis for skin cancer screening.

Abstract Screened Poisson surface reconstruction robustly creates meshes from oriented point sets. For large datasets, the technique requires hours of computation and significant memory. We present a method to parallelize and distribute this computation over multiple commodity client nodes. The method partitions space on one axis into adaptively sized slabs containing balanced subsets of points. Because the Poisson formulation involves a global system, the challenge is to maintain seamless consistency at the slab boundaries and obtain a reconstruction that is indistinguishable from the serial result. To this end, we express the reconstructed indicator function as a sum of a low‐resolution term computed on a server and high‐resolution terms computed on distributed clients. Using a client–server architecture, we map the computation onto a sequence of serial server tasks and parallel client tasks, separated by synchronization barriers. This architecture also enables low‐memory evaluation on a single computer, albeit without speedup. We demonstrate a 700 million vertex reconstruction of the billion point David statue scan in less than 20 min on a 65‐node cluster with a maximum memory usage of 45 GB/node, or in 14 h on a single node.

Abstract Screened Poisson Surface Reconstruction creates 2D surfaces from sets of oriented points in 3D (and can be extended to co‐dimension one surfaces in arbitrary dimensions). In this work we generalize the technique to manifolds of co‐dimension larger than one. The reconstruction problem consists of finding a vector‐valued function whose zero set approximates the input points. We argue that the right extension of screened Poisson Surface Reconstruction is based on exterior products: the orientation of the point samples is encoded as the exterior product of the local normal frame. The goal is to find a set of scalar functions such that the exterior product of their gradients matches the exterior products prescribed by the input points. We show that this setup reduces to the standard formulation for co‐dimension 1, and leads to more challenging multi‐quadratic optimization problems in higher co‐dimension. We explicitly treat the case of co‐dimension 2, i.e., curves in 3D and 2D surfaces in 4D. We show that the resulting bi‐quadratic problem can be relaxed to a set of quadratic problems in two variables and that the solution can be made effective and efficient by leveraging a hierarchical approach.

Solving partial differential equations (PDEs) on geometric domains is an important component of computer graphics, geometry processing, and many other fields. Typically, the given discrete mesh is the geometric representation and should not be altered for simulation purposes. Hence, accurately solving PDEs on general meshes is a central goal and has been considered for various differential operators over the last years. While it is known that using higher-order basis functions on simplicial meshes can substantially improve accuracy and convergence, extending these benefits to general surface or volume tessellations in an efficient fashion remains an open problem. Our work proposes variationally optimized piecewise quadratic shape functions for polygons and polyhedra, which generalize quadratic P 2 elements, exactly reproduce them on simplices, and inherit their beneficial numerical properties. To mitigate the associated cost of increased computation time, particularly for volumetric meshes, we introduce a custom two-level multigrid solver which significantly improves computational performance.

We present a novel surface convolution operator acting on vector fields that is based on a simple observation: instead of combining neighboring features with respect to a single coordinate parameterization defined at a given point, we have every neighbor describe the position of the point within its own coordinate frame. This formulation combines intrinsic spatial convolution with parallel transport in a scattering operation while placing no constraints on the filters themselves, providing a definition of convolution that commutes with the action of isometries, has increased descriptive potential, and is robust to noise and other nuisance factors. The result is a rich notion of convolution which we call field convolution, well-suited for CNNs on surfaces. Field convolutions are flexible, straight-forward to incorporate into surface learning frameworks, and their highly discriminating nature has cascading effects throughout the learning pipeline. Using simple networks constructed from residual field convolution blocks, we achieve state-of-the-art results on standard benchmarks in fundamental geometry processing tasks, such as shape classification, segmentation, correspondence, and sparse matching.

Abstract This paper presents a novel, highly distinctive and robust local surface feature descriptor. Our descriptor is predicated on a simple observation: instead of describing the points in the vicinity of a feature point relative to a reference frame at the feature point, all points in the region describe the feature point relative to their own frames. Isometry invariance is a byproduct of this construction. Our descriptor is derived relative to the extended convolution – a generalization of the standard convolution that allows the filter to adaptively transform as it passes over the domain. As such, we name our descriptor the Extended Convolution Histogram of Orientations (ECHO). It exhibits superior performance compared to popular surface descriptors in both feature matching and shape correspondence experiments. In particular, the ECHO descriptor is highly stable under near‐isometric deformations and remains distinctive under significant levels of noise, tessellation, complex deformations and the kinds of interference commonly found in real data.

Abstract The discrete Laplace‐Beltrami operator for surface meshes is a fundamental building block for many (if not most) geometry processing algorithms. While Laplacians on triangle meshes have been researched intensively, yielding the cotangent discretization as the de‐facto standard, the case of general polygon meshes has received much less attention. We present a discretization of the Laplace operator which is consistent with its expression as the composition of divergence and gradient operators, and is applicable to general polygon meshes, including meshes with non‐convex, and even non‐planar, faces. Byvirtuallyinserting a carefully placed point we implicitly refine each polygon into a triangle fan, but then hide the refinement within the matrix assembly. The resulting operator generalizes the cotangent Laplacian, inherits its advantages, and is empirically shown to be on par or even better than the recent polygon Laplacian of Alexa and Wardetzky [AW11] — while being simpler to compute.

Abstract Reconstructing surfaces from scanned 3D points has been an important research area for several decades. One common approach that has proven efficient and robust to noise is implicit surface reconstruction, i.e. fitting to the points a 3D scalar function (such as an indicator function or signed‐distance field) and then extracting an isosurface. Though many techniques fall within this category, existing methods either impose no boundary constraints or impose Dirichlet/Neumann conditions on the surface of a bounding box containing the scanned data. In this work, we demonstrate the benefit of supporting Dirichlet constraints on a general boundary. To this end, we adapt the Screened Poisson Reconstruction algorithm to input a constraint envelope in addition to the oriented point cloud. We impose Dirichlet boundary conditions, forcing the reconstructed implicit function to be zero outside this constraint surface. Using a visual hull and/or depth hull derived from RGB‐D scans to define the constraint envelope, we obtain substantially improved surface reconstructions in regions of missing data.

Abstract A key processing step in numerous computer graphics applications is the solution of a linear system discretized over a spatial domain. Often, the linear system can be represented using an adaptive domain tessellation, either because the solution will only be sampled sparsely, or because the solution is known to be ‘interesting’ (e.g. high frequency) only in localized regions. In this work, we propose an adaptive, finite elements, multi‐grid solver capable of efficiently solving such linear systems. Our solver is designed to be general‐purpose, supporting finite elements of different degrees, across different dimensions and supporting both integrated and pointwise constraints. We demonstrate the efficacy of our solver in applications including surface reconstruction, image stitching and Euclidean Distance Transform calculation.

Abstract We describe a novel approach that addresses the problem of establishing correspondences between non‐rigidly deformed shapes by performing the registration over the unit sphere. In a pre‐processing step, each shape is conformally parametrized over the sphere, centered to remove Möbius inversion ambiguity, and authalically evolved to expand regions that are excessively compressed by the conformal parametrization. Then, for each pair of shapes, we perform fast SO(3) correlation to find the optimal rotational alignment and refine the registration using optical flow. We evaluate our approach on the TOSCA dataset, demonstrating that our approach compares favorably to state‐of‐the‐art methods.

Abstract Conformal parameterizations over the sphere provide high‐quality maps between genus zero surfaces, and are essential for applications such as data transfer and comparative shape analysis. However, such maps are not unique: to define correspondence between two surfaces, one must find the Möbius transformation that best aligns two parameterizations—akin to picking a translation and rotation in rigid registration problems. We describe a simple procedure that canonically centers and rotationally aligns two spherical maps. Centering is implemented via elementary operations on triangle meshes in ℝ3, and minimizes area distortion. Alignment is achieved using the FFT over the group of rotations. We examine this procedure in the context of spherical conformal parameterization, orbifold maps, non‐rigid symmetry detection, and dense point‐to‐point surface correspondence.

Processing signals on surfaces often involves resampling the signal over the vertices of a dense mesh and applying mesh-based filtering operators. We present a framework to process a signal directly in a texture atlas domain. The benefits are twofold: avoiding resampling degradation and exploiting the regularity of the texture image grid. The main challenges are to preserve continuity across atlas chart boundaries and to adapt differential operators to the non-uniform parameterization. We introduce a novel function space and multigrid solver that jointly enable robust, interactive, and geometry-aware signal processing. We demonstrate our approach using several applications including smoothing and sharpening, multiview stitching, geodesic distance computation, and line integral convolution.

We convert a sequence of unstructured textured meshes into a mesh with incrementally changing connectivity and atlas parameterization. Like prior work on surface tracking, we seek temporally coherent mesh connectivity to enable efficient representation of surface geometry and texture. Like recent work on evolving meshes, we pursue local remeshing to permit tracking over long sequences containing significant deformations or topological changes. Our main contribution is to show that both goals are realizable within a common framework that simultaneously evolves both the set of mesh triangles and the parametric map. Sparsifying the remeshing operations allows the formation of large spatiotemporal texture charts. These charts are packed as prisms into a 3D atlas for a texture video. Reducing tracking drift using mesh-based optical flow helps improve compression of the resulting video stream.

Today's 3D scanning pipelines can be classified into two overarching categories: offline, high accuracy methods that rely on global optimization to reconstruct complex scenes with hundreds of millions of samples, and online methods that produce real-time but low-quality output, usually from structure-from-motion or depth sensors. The method proposed in this paper is the first to combine the benefits of both approaches, supporting online reconstruction of scenes with hundreds of millions of samples from high-resolution sensing modalities such as structured light or laser scanners. The key property of our algorithm is that it sidesteps the signed-distance computation of classical reconstruction techniques in favor of direct filtering, parametrization, and mesh and texture extraction. All of these steps can be realized using only weak notions of spatial neighborhoods, which allows for an implementation that scales approximately linearly with the size of each dataset that is integrated into a partial reconstruction. Combined, these algorithmic differences enable a drastically more efficient output-driven interactive scanning and reconstruction workflow, where the user is able to see the final quality field-aligned textured mesh during the entirety of the scanning procedure. Holes or parts with registration problems are displayed in real-time to the user and can be easily resolved by adding further localized scans, or by adjusting the input point cloud using our interactive editing tools with immediate visual feedback on the output mesh. We demonstrate the effectiveness of our algorithm in conjunction with a state-of-the-art structured light scanner and optical tracking system and test it on a large variety of challenging models.

Scanned performances are commonly represented in virtual environments as sequences of textured triangle meshes. Detailed shapes deforming over time benefit from meshes with dynamically evolving connectivity. We analyze these unstructured mesh sequences to automatically synthesize motion graphs with new smooth transitions between compatible poses and actions. Such motion graphs enable natural periodic motions, stochastic playback, and user-directed animations. The main challenge of unstructured sequences is that the meshes differ not only in connectivity but also in alignment, shape, and texture. We introduce new geometry processing techniques to address these problems and demonstrate visually seamless transitions on high-quality captures.

In this work we study the interpolation problem in contouring methods such as Marching Cubes. Traditionally, linear interpolation is used to define the position of an is vertex along a zero-crossing edge, which is a suitable approach if the underlying implicit function is (approximately) piecewise linear along each edge. Non-linear implicit functions, however, are frequently encountered and linear interpolation leads to inaccurate is surfaces with visible reconstruction artifacts. We instead utilize the gradient of the implicit function to generate more accurate is surfaces by means of Hermite interpolation techniques. We propose and compare several interpolation methods and demonstrate clear quality improvements by using higher order interpolants. We further show the effectiveness of the approach even when Hermite data is not available and gradients are approximated using finite differences.

Abstract In computer graphics, numerous geometry processing applications reduce to the solution of a Poisson equation. When considering geometries with symmetry, a natural question to consider is whether and how the symmetry can be leveraged to derive an efficient solver for the underlying system of linear equations. In this work we provide a simple representation‐theoretic analysis that demonstrates how symmetries of the geometry translate into block diagonalization of the linear operators and we show how this results in efficient linear solvers for surfaces of revolution with and without angular boundaries.

Abstract This work revisits the Shock Filters of Osher and Rudin [ OR90 ] and shows how the proposed filtering process can be interpreted as the advection of image values along flow‐lines. Using this interpretation, we obtain an efficient implementation that only requires tracing flow‐lines and re‐sampling the image. We show that the approach is stable, allowing the use of arbitrarily large time steps without requiring a linear solve. Furthermore, we demonstrate the robustness of the approach by extending it to the processing of signals on meshes in 3D.

We propose a new spectral analysis of the variance in Monte Carlo integration, expressed in terms of the power spectra of the sampling pattern and the integrand involved. We build our framework in the Euclidean space using Fourier tools and on the sphere using spherical harmonics. We further provide a theoretical background that explains how our spherical framework can be extended to the hemispherical domain. We use our framework to estimate the variance convergence rate of different state-of-the-art sampling patterns in both the Euclidean and spherical domains, as the number of samples increases. Furthermore, we formulate design principles for constructing sampling methods that can be tailored according to available resources. We validate our theoretical framework by performing numerical integration over several integrands sampled using different sampling patterns.

- neural connectivity maps of the brain-using the parallel execution of computer vision algorithms on high-performance compute clusters. These services and open-science data sets are publicly available at openconnecto.me. The system design inherits much from NoSQL scale-out and data-intensive computing architectures. We distribute data to cluster nodes by partitioning a spatial index. We direct I/O to different systems-reads to parallel disk arrays and writes to solid-state storage-to avoid I/O interference and maximize throughput. All programming interfaces are RESTful Web services, which are simple and stateless, improving scalability and usability. We include a performance evaluation of the production system, highlighting the effec-tiveness of spatial data organization.

Poisson surface reconstruction creates watertight surfaces from oriented point sets. In this work we extend the technique to explicitly incorporate the points as interpolation constraints. The extension can be interpreted as a generalization of the underlying mathematical framework to a screened Poisson equation. In contrast to other image and geometry processing techniques, the screening term is defined over a sparse set of points rather than over the full domain. We show that these sparse constraints can nonetheless be integrated efficiently. Because the modified linear system retains the same finite-element discretization, the sparsity structure is unchanged, and the system can still be solved using a multigrid approach. Moreover we present several algorithmic improvements that together reduce the time complexity of the solver to linear in the number of points, thereby enabling faster, higher-quality surface reconstructions.

A new type of deformable model is presented that merges meshes and level sets into one representation to provide interoperability between methods designed for either. This includes the ability to circumvent the CFL time step restriction for methods that require large step sizes. The key idea is to couple a constellation of disconnected triangular surface elements (springls) with a level set that tracks the moving constellation. The target application for Spring Level Sets (SpringLS) is to implement comprehensive imaging pipelines that require a mixture of deformable model representations to achieve the best performance. We demonstrate how to implement key components of a comprehensive imaging pipeline with SpringLS, including image segmentation, registration, tracking, and atlasing.

A new data structure is presented for geometrically modeling multi-objects. The model can exhibit elastic and fluid-like behavior to enable interpretability between tasks that require both deformable registration and active contour segmentation. The data structure consists of a label mask, distance field, and springls (a constellation of disconnected triangles). The representation has sub-voxel precision, is parametric, re-meshes, tracks point correspondences, and guarantees no self-intersections, air-gaps, or overlaps between adjacent structures. In this work, we show how to apply existing registration algorithms and active contour segmentation to the data structure; and as a demonstration, the data structure is used to segment cortical and subcortical structures (74 total) in the human brain.

An emerging topic is to build image segmentation systems that can segment hundreds to thousands of objects (i.e. cell segmentation\tracking, full brain parcellation, full body segmentation, etc.). Multi-object Level Set Methods (MLSM) perform this task with the benefit of sub-pixel precision. However, current implementations of MLSM are not as computationally or memory efficient as their region growing and graph cut counterparts which lack sub-pixel precision. To address this performance gap, we present a novel parallel implementation of MLSM that leverages the sparse properties of the algorithm to minimize its memory footprint for multiple objects. The new method, Multi-Object Geodesic Active Contours (MOGAC), can represent N objects with just two functions: a label mask image and unsigned distance field. The time complexity of the algorithm is shown to be O((M (power)d)/P) for M (power)d pixels and P processing units in dimension d = {2,3}, independent of the number of objects. Results are presented for 2D and 3D image segmentation problems.

Abstract This work considers the question of whether mean‐curvature flow can be modified to avoid the formation of singularities. We analyze the finite‐elements discretization and demonstrate why the original flow can result in numerical instability due to division by zero. We propose a variation on the flow that removes the numerical instability in the discretization and show that this modification results in a simpler expression for both the discretized and continuous formulations. We discuss the properties of the modified flow and present empirical evidence that not only does it define a stable surface evolution for genus‐zero surfaces, but that the evolution converges to a conformal parameterization of the surface onto the sphere.

Abstract In this paper, we present a novel approach for efficiently evolving meshes using mean‐curvature flow. We use a finite‐elements hierarchy that supports an efficient multigrid solver for performing the semi‐implicit time‐stepping. Although expensive to compute, we show that it is possible to track this hierarchy through the process of surface evolution. As a result, we provide a way to efficiently flow the surface through the evolution, without requiring a costly initialization at the beginning of each time‐step. Using our approach, we demonstrate a factor of nearly seven‐fold improvement over the non‐tracking implementation, supporting the evolution of surfaces consisting of 1M triangles at a rate of just a few seconds per update.

We present a general framework for performing geometry filtering through the solution of a screened Poisson equation. We show that this framework can be efficiently adapted to a changing Riemannian metric to support curvature-aware filtering and describe a parallel and streaming multigrid implementation for solving the system. We demonstrate the practicality of our approach by developing an interactive system for mesh editing that allows for exploration of a large family of curvature-guided, anisotropic filters.

We present a new technique for fusing together an arbitrary number of aligned images into a single color or intensity image. We approach this fusion problem from the context of Multidimensional Scaling (MDS) and describe an algorithm that preserves the relative distances between pairs of pixel values in the input (vectors of measurements) as perceived differences in a color image. The two main advantages of our approach over existing techniques are that it can incorporate user constraints into the mapping process and allows adaptively compressing or exaggerating features in the input in order to make better use of the output's limited dynamic range. We demonstrate these benefits by showing applications in various scientific domains and comparing our algorithm to previously proposed techniques.

We describe a real-time system for editing large 3D meshes. The system supports both global and local modulation of surface detail, expressing the position of vertices on the edited geometry as the solution to a linear system of equations defined over the surface. The interactivity of our system is enabled by the design of an efficient sparse linear solver, providing an interface with which users can explore a broad landscape of possible surface modifications.

Abstract We present a closed‐form solution for the symmetrization problem, solving for the optimal deformation that reconciles a set of local bilateral symmetries. Given as input a set of point‐pairs which should be symmetric, we first compute for each local neighborhood a transformation which would produce an approximate bilateral symmetry. We then solve for a single global symmetry which includes all of these local symmetries, while minimizing the deformation within each local neighborhood. Our main motivation is the symmetrization of digitized fossils, which are often deformed by a combination of compression and bending. In addition, we use the technique to symmetrize articulated models.

Processing spherical images is challenging. Because no spherical parameterization is globally uniform, an accurate solver must account for the spatially varying metric. We present the first efficient metric-aware solver for Laplacian processing of spherical data. Our approach builds on the commonly used equirectangular parameterization, which provides differentiability, axial symmetry, and grid sampling. Crucially, axial symmetry lets us discretize the Laplacian operator just once per grid row. One difficulty is that anisotropy near the poles leads to a poorly conditioned system. Our solution is to construct an adapted hierarchy of finite elements, adjusted at the poles to maintain derivative continuity, and selectively coarsened to bound element anisotropy. The resulting elements are nested both within and across resolution levels. A streaming multigrid solver over this hierarchy achieves excellent convergence rate and scales to huge images. We demonstrate applications in reaction-diffusion texture synthesis and panorama stitching and sharpening.

Gradient-domain processing is widely used to edit and combine images. In this article we extend the framework in two directions. First, we adapt the gradient-domain approach to operate on a spherical domain, to enable operations such as seamless stitching, dynamic-range compression, and gradient-based sharpening over spherical imagery. An efficient streaming computation is obtained using a new spherical parameterization with bounded distortion and localized boundary constraints. Second, we design a distributed solver to efficiently process large planar or spherical images. The solver partitions images into bands, streams through these bands in parallel within a networked cluster, and schedules computation to hide the necessary synchronization latency. We demonstrate our contributions on several datasets including the Digitized Sky Survey, a terapixel spherical scan of the night sky.

Abstract We present a novel approach for computing and solving the Poisson equation over the surface of a mesh. As in previous approaches, we define the Laplace‐Beltrami operator by considering the derivatives of functions defined on the mesh. However, in this work, we explore a choice of functions that is decoupled from the tessellation. Specifically, we use basis functions (second‐order tensor‐product B‐splines) defined over 3D space, and then restrict them to the surface. We show that in addition to being invariant to mesh topology, this definition of the Laplace‐Beltrami operator allows a natural multiresolution structure on the function space that is independent of the mesh structure, enabling the use of a simple multigrid implementation for solving the Poisson equation.

We demonstrate data indexing and query processing techniques that improve the efficiency of comparing, correlating, and joining data contained in non-convex regions. We use computational geometry techniques to automatically characterize the region of space from which data are drawn, partition the region based on that characterization, and create an index from the partitions. Our motivating application performs distributed data analysis queries among federated database sites that store scientific data sets from the Chesapeake Bay. Our preliminary findings indicate that these techniques often reduce the number of I/Os needed to serve a query by a factor of five---depending on the geometry of the query region.

We introduce a new tool to solve the large linear systems arising from gradient-domain image processing. Specifically, we develop a streaming multigrid solver, which needs just two sequential passes over out-of-core data. This fast solution is enabled by a combination of three techniques: (1) use of second-order finite elements (rather than traditional finite differences) to reach sufficient accuracy in a single V-cycle, (2) temporally blocked relaxation, and (3) multi-level streaming to pipeline the restriction and prolongation phases into single streaming passes. A key contribution is the extension of the B-spline finite-element method to be compatible with the forward-difference gradient representation commonly used with images. Our streaming solver is also efficient for in-memory images, due to its fast convergence and excellent cache behavior. Remarkably, it can outperform spatially adaptive solvers that exploit application-specific knowledge. We demonstrate seamless stitching and tone-mapping of gigapixel images in about an hour on a notebook PC.

In many shape analysis applications, the ability to find the best rotation that aligns two models is an essential first step in the analysis process. In the past, methods for model alignment have either used normalization techniques, such as PCA alignment, or have performed an exhaustive search over the space of rotation to find the best optimal alignment. While normalization techniques have the advantage of efficiency, providing a quick method for registering two shapes, they are often imprecise and can give rise to poor alignments. Conversely, exhaustive search is guaranteed to provide the correct answer, but, even using efficient signal processing techniques, this type of approach can be prohibitively slow. In this paper, we present a new method for aligning two 3D shapes. We show that the method is markedly faster than existing approaches based on efficient signal processing and we provide registration results demonstrating that the alignments obtained using our method have a high degree of precision and are markedly better than those obtained using normalization.

In recent years, many shape representations and geometric algorithms have been proposed for matching 3D shapes. Usually, each algorithm is tested on a different (small) database of 3D models, and thus no direct comparison is available for competing methods. We describe the Princeton Shape Benchmark (PSB), a publicly available database of polygonal models collected from the World Wide Web and a suite of tools for comparing shape matching and classification algorithms. One feature of the benchmark is that it provides multiple semantic labels for each 3D model. For instance, it includes one classification of the 3D models based on function, another that considers function and form, and others based on how the object was constructed (e.g., man-made versus natural objects). We find that experiments with these classifications can expose different properties of shape-based retrieval algorithms. For example, out of 12 shape descriptors tested, extended Gaussian images by B. Horn (1984) performed best for distinguishing man-made from natural objects, while they performed among the worst for distinguishing specific object types. Based on experiments with several different shape descriptors, we conclude that no single descriptor is best for all classifications, and thus the main contribution of this paper is to provide a framework to determine the conditions under which each descriptor performs best.

In this paper, we investigate a data-driven synthesis approach to constructing 3D geometric surface models. We provide methods with which a user can search a large database of 3D meshes to find parts of interest, cut the desired parts out of the meshes with intelligent scissoring, and composite them together in different ways to form new objects. The main benefit of this approach is that it is both easy to learn and able to produce highly detailed geometric models -- the conceptual design for new models comes from the user, while the geometric details come from examples in the database. The focus of the paper is on the main research issues motivated by the proposed approach: (1) interactive segmentation of 3D surfaces, (2) shape-based search to find 3D models with parts matching a query, and (3) composition of parts to form new models. We provide new research contributions on all three topics and incorporate them into a prototype modeling system. Experience with our prototype system indicates that it allows untrained users to create interesting and detailed 3D models.

With recent improvements in methods for the acquisition and rendering of 3D models, the need for retrieval of models has gained prominence in the graphics and vision communities. A variety of methods have been proposed that enable the efficient querying of model repositories for a desired 3D shape. Many of these methods use a 3D model as a query and attempt to retrieve models from the database that have a similar shape.In this paper we consider the implications of anisotropy on the shape matching paradigm. In particular, we propose a novel method for matching 3D models that factors the shape matching equation as the disjoint outer product of anisotropy and geometric comparisons. We provide a general method for computing the factored similarity metric and show how this approach can be applied to improve the matching performance of many existing shape matching methods.

As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).

We describe a system for non-photorealistic rendering (NPR) of virtual environments. In real time, it synthesizes imagery of architectural interiors using stroke-based textures. We address the four main challenges of such a system — interactivity, visual detail, controlled stroke size, and frame-to-frame coherence — through image based rendering (IBR) methods. In a preprocessing stage, we capture photos of a real or synthetic environment, map the photos to a coarse model of the environment, and run a series of NPR filters to generate textures. At runtime, the system re-renders the NPR textures over the geometry of the coarse model, and it adds dark lines that emphasize creases and silhouettes. We provide a method for constructing non-photorealistic textures from photographs that largely avoids seams in the resulting imagery. We also offer a new construction, art-maps, to control stroke size across the images. Finally, we show a working system that provides an immersive experience rendered in a variety of NPR styles.