33-Issue 5
Permanent URI for this collection
Browse
Browsing 33-Issue 5 by Issue Date
Now showing 1 - 20 of 29
Results Per Page
Sort Options
Item Clever Support: Efficient Support Structure Generation for Digital Fabrication(The Eurographics Association and John Wiley and Sons Ltd., 2014) Vanek, Juraj; Galicia, Jorge A. G.; Benes, Bedrich; Thomas Funkhouser and Shi-Min HuWe introduce an optimization framework for the reduction of support structures required by 3D printers based on Fused Deposition Modeling (FDM) technology. The printers need to connect overhangs with the lower parts of the object or the ground in order to print them. Since the support material needs to be printed first and discarded later, optimizing its volume can lead to material and printing time savings.We present a novel, geometry-based approach that minimizes the support material while providing sufficient support. Using our approach, the input 3D model is first oriented into a position with minimal area that requires support. Then the points in this area that require support are detected. For these points the supporting structure is progressively built while attempting to minimize the overall length of the support structure. The resulting structure has a tree-like shape that effectively supports the overhangs. We have tested our algorithm on the MakerBot R ReplicatorTM 2 printer and we compared our solution to the embedded software solution in this printer and to Autodesk R MeshmixerTMsoftware. Our solution reduced printing time by an average of 29.4% (ranging from 13.9% to 49.5%) and the amount of material by 40.5% (ranging from 24.5% to 68.1%).Item Freeform Honeycomb Structures(The Eurographics Association and John Wiley and Sons Ltd., 2014) Jiang, Caigui; Wang, Jun; Wallner, Johannes; Pottmann, Helmut; Thomas Funkhouser and Shi-Min HuMotivated by requirements of freeform architecture, and inspired by the geometry of hexagonal combs in beehives, this paper addresses torsion-free structures aligned with hexagonal meshes. Since repetitive geometry is a very important contribution to the reduction of production costs, we study in detail ''honeycomb structures'', which are defined as torsion-free structures where the walls of cells meet at 120 degrees. Interestingly, the Gauss-Bonnet theorem is useful in deriving information on the global distribution of node axes in such honeycombs. This paper discusses the computation and modeling of honeycomb structures as well as applications, e.g. for shading systems, or for quad meshing. We consider this paper as a contribution to the wider topic of freeform patterns, polyhedral or otherwise. Such patterns require new approaches on the technical level, e.g. in the treatment of smoothness, but they also extend our view of what constitutes aesthetic freeform geometry.Item Designing N-PolyVector Fields with Complex Polynomials(The Eurographics Association and John Wiley and Sons Ltd., 2014) Diamanti, Olga; Vaxman, Amir; Panozzo, Daniele; Sorkine-Hornung, Olga; Thomas Funkhouser and Shi-Min HuWe introduce N-PolyVector fields, a generalization of N-RoSy fields for which the vectors are neither necessarily orthogonal nor rotationally symmetric. We formally define a novel representation for N-PolyVectors as the root sets of complex polynomials and analyze their topological and geometric properties. A smooth N-PolyVector field can be efficiently generated by solving a sparse linear system without integer variables. We exploit the flexibility of N-PolyVector fields to design conjugate vector fields, offering an intuitive tool to generate planar quadrilateral meshes.Item 3D Motion Completion in Crowded Scenes(The Eurographics Association and John Wiley and Sons Ltd., 2014) Gafni, Niv; Sharf, Andrei; Thomas Funkhouser and Shi-Min HuCrowded motions refer to multiple objects moving around and interacting such as crowds, pedestrians and etc. We capture crowded scenes using a depth scanner at video frame rates. Thus, our input is a set of depth frames which sample the scene over time. Processing such data is challenging as it is highly unorganized, with large spatiotemporal holes due to many occlusions. As no correspondence is given, locally tracking 3D points across frames is hard due to noise and missing regions. Furthermore global segmentation and motion completion in presence of large occlusions is ambiguous and hard to predict. Our algorithm utilizes Gestalt principles of common fate and good continuity to compute motion tracking and completion respectively. Our technique does not assume any pregiven markers or motion template priors. Our key-idea is to reduce the motion completion problem to a 1D curve fitting and matching problem which can be solved efficiently using a global optimization scheme. We demonstrate our segmentation and completion method on a variety of synthetic and real world crowded scanned scenes.Item Functional Fluids on Surfaces(The Eurographics Association and John Wiley and Sons Ltd., 2014) Azencot, Omri; Weißmann, Steffen; Ovsjanikov, Maks; Wardetzky, Max; Ben-Chen, Mirela; Thomas Funkhouser and Shi-Min HuFluid simulation plays a key role in various domains of science including computer graphics. While most existing work addresses fluids on bounded Euclidean domains, we consider the problem of simulating the behavior of an incompressible fluid on a curved surface represented as an unstructured triangle mesh. Unlike the commonly used Eulerian description of the fluid using its time-varying velocity field, we propose to model fluids using their vorticity, i.e., by a (time varying) scalar function on the surface. During each time step, we advance scalar vorticity along two consecutive, stationary velocity fields. This approach leads to a variational integrator in the space continuous setting. In addition, using this approach, the update rule amounts to manipulating functions on the surface using linear operators, which can be discretized efficiently using the recently introduced functional approach to vector fields. Combining these time and space discretizations leads to a conceptually and algorithmically simple approach, which is efficient, time-reversible and conserves vorticity by construction. We further demonstrate that our method exhibits no numerical dissipation and is able to reproduce intricate phenomena such as vortex shedding from boundaries.Item Efficient Encoding of Texture Coordinates Guided by Mesh Geometry(The Eurographics Association and John Wiley and Sons Ltd., 2014) Vása, Libor; Brunnett, Guido; Thomas Funkhouser and Shi-Min HuIn this paper, we investigate the possibilities of efficient encoding of UV coordinates associated with vertices of a triangle mesh. Since most parametrization schemes attempt to achieve at least some level of conformality, we exploit the similarity of the shapes of triangles in the mesh and in the parametrization. We propose two approaches building on this idea: first, applying a recently proposed generalization of the parallelogram predictor, using the inner angles of mesh triangles corresponding to the UV-space triangles. Second, we propose an encoding method based on discrete Laplace operator, which also allows exploiting the information contained in the mesh geometry to efficiently encode the parametrization. Our experiments show that the proposed approach leads to savings of up to 3 bits per UV vertex, without loss of precision.Item Blue-Noise Remeshing with Farthest Point Optimization(The Eurographics Association and John Wiley and Sons Ltd., 2014) Yan, Dong-Ming; Guo, Jianwei; Jia, Xiaohong; Zhang, Xiaopeng; Wonka, Peter; Thomas Funkhouser and Shi-Min HuIn this paper, we present a novel method for surface sampling and remeshing with good blue-noise properties. Our approach is based on the farthest point optimization (FPO), a relaxation technique that generates high quality blue-noise point sets in 2D. We propose two important generalizations of the original FPO framework: adaptive sampling and sampling on surfaces. A simple and efficient algorithm for accelerating the FPO framework is also proposed. Experimental results show that the generalized FPO generates point sets with excellent blue-noise properties for adaptive and surface sampling. Furthermore, we demonstrate that our remeshing quality is superior to the current state-of-the-art approaches.Item An Efficient Approach to Correspondences between Multiple Non-Rigid Parts(The Eurographics Association and John Wiley and Sons Ltd., 2014) Tam, Gary K. L.; Martin, Ralph R.; Rosin, Paul L.; Lai, Yu-Kun; Thomas Funkhouser and Shi-Min HuIdentifying multiple deformable parts on meshes and establishing dense correspondences between them are tasks of fundamental importance to computer graphics, with applications to e.g. geometric edit propagation and texture transfer. Much research has considered establishing correspondences between non-rigid surfaces, but little work can both identify similar multiple deformable parts and handle partial shape correspondences. This paper addresses two related problems, treating them as a whole: (i) identifying similar deformable parts on a mesh, related by a non-rigid transformation to a given query part, and (ii) establishing dense point correspondences automatically between such parts. We show that simple and efficient techniques can be developed if we make the assumption that these parts locally undergo isometric deformation. Our insight is that similar deformable parts are suggested by large clusters of point correspondences that are isometrically consistent. Once such parts are identified, dense point correspondences can be obtained by an iterative propagation process. Our techniques are applicable to models with arbitrary topology. Various examples demonstrate the effectiveness of our techniques.Item Remeshing-assisted Optimization for Locally Injective Mappings(The Eurographics Association and John Wiley and Sons Ltd., 2014) Jin, Yao; Huang, Jin; Tong, Ruofeng; Thomas Funkhouser and Shi-Min HuConstructing locally injective mappings for 2D triangular meshes is vital in applications such as deformations. In such a highly constrained optimization, the prescribed tessellation may impose strong restriction on the solution. As a consequence, the feasible region may be too small to contain an ideal solution, which leads to problems of slow convergence, poor solution, or even that no solution can be found. We propose to integrate adaptive remeshing into interior point method to solve this issue. We update the vertex positions via a parameter-free relaxation enhanced geometry optimization, and then use edge-flip operations to reduce the residual and keep a reasonable condition number for better convergence. For more robustness, when the iteration of interior point method terminates but leaves the positional constraints unsatisfied, we estimate the edges in the current tessellation that block vertices moving based on the convergence information of the optimization, and then split neighboring edges to break the restriction. The results show that our method has better performance than the solely geometric optimization approaches, especially for extreme deformations.Item SUPER 4PCS: Fast Global Pointcloud Registration via Smart Indexing(The Eurographics Association and John Wiley and Sons Ltd., 2014) Mellado, Nicolas; Aiger, Dror; Mitra, Niloy J.; Thomas Funkhouser and Shi-Min HuData acquisition in large-scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state-of-the-art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present SUPER 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an 'instance problem' and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory-efficient, and fast. We demonstrate that SUPER 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/.Item As-Conformal-As-Possible Surface Registration(The Eurographics Association and John Wiley and Sons Ltd., 2014) Yoshiyasu, Yusuke; Ma, Wan-Chun; Yoshida, Eiichi; Kanehiro, Fumio; Thomas Funkhouser and Shi-Min HuWe present a non-rigid surface registration technique that can align surfaces with sizes and shapes that are different from each other, while avoiding mesh distortions during deformation. The registration is constrained locally as conformal as possible such that the angles of triangle meshes are preserved, yet local scales are allowed to change. Based on our conformal registration technique, we devise an automatic registration and interactive registration technique, which can reduce user interventions during template fitting. We demonstrate the versatility of our technique on a wide range of surfaces.Item Exploring the Geometry of the Space of Shells(The Eurographics Association and John Wiley and Sons Ltd., 2014) Heeren, Behrend; Rumpf, Martin; Schröder, Peter; Wardetzky, Max; Wirth, Benedikt; Thomas Funkhouser and Shi-Min HuWe prove both in the smooth and discrete setting that the Hessian of an elastic deformation energy results in a proper Riemannian metric on the space of shells (modulo rigid body motions). Based on this foundation we develop a time- and space-discrete geodesic calculus. In particular we show how to shoot geodesics with prescribed initial data, and we give a construction for parallel transport in shell space. This enables, for example, natural extrapolation of paths in shell space and transfer of large nonlinear deformations from one shell to another with applications in animation, geometric, and physical modeling. Finally, we examine some aspects of curvature on shell space.Item Discrete 2-Tensor Fields on Triangulations(The Eurographics Association and John Wiley and Sons Ltd., 2014) Goes, Fernando de; Liu, Beibei; Budninskiy, Max; Tong, Yiying; Desbrun, Mathieu; Thomas Funkhouser and Shi-Min HuGeometry processing has made ample use of discrete representations of tangent vector fields and antisymmetric tensors (i.e., forms) on triangulations. Symmetric 2-tensors, while crucial in the definition of inner products and elliptic operators, have received only limited attention. They are often discretized by first defining a coordinate system per vertex, edge or face, then storing their components in this frame field. In this paper, we introduce a representation of arbitrary 2-tensor fields on triangle meshes. We leverage a coordinate-free decomposition of continuous 2-tensors in the plane to construct a finite-dimensional encoding of tensor fields through scalar values on oriented simplices of a manifold triangulation. We also provide closed-form expressions of pairing, inner product, and trace for this discrete representation of tensor fields, and formulate a discrete covariant derivative and a discrete Lie bracket. Our approach extends discrete/finite-element exterior calculus, recovers familiar operators such as the weighted Laplacian operator, and defines discrete notions of divergence-free, curl-free, and traceless tensors-thus offering a numerical framework for discrete tensor calculus on triangulations. We finally demonstrate the robustness and accuracy of our operators on analytical examples, before applying them to the computation of anisotropic geodesic distances on discrete surfacesItem Real-time Bas-Relief Generation from Depth-and-Normal Maps on GPU(The Eurographics Association and John Wiley and Sons Ltd., 2014) Ji, Zhongping; Sun, Xianfang; Li, Shi; Wang, Yigang; Thomas Funkhouser and Shi-Min HuTo design a bas-relief from a 3D scene is an inherently interactive task in many scenarios. The user normally needs to get instant feedback to select a proper viewpoint. However, current methods are too slow to facilitate this interaction. This paper proposes a two-scale bas-relief modeling method, which is computationally efficient and easy to produce different styles of bas-reliefs. The input 3D scene is first rendered into two textures, one recording the depth information and the other recording the normal information. The depth map is then compressed to produce a base surface with level-of-depth, and the normal map is used to extract local details with two different schemes. One scheme provides certain freedom to design bas-reliefs with different visual appearances, and the other provides a control over the level of detail. Finally, the local feature details are added into the base surface to produce the final result. Our approach allows for real-time computation due to its implementation on graphics hardware. Experiments with a wide range of 3D models and scenes show that our approach can effectively generate digital bas-reliefs in real time.Item Piecewise-Planar 3D Reconstruction with Edge and Corner Regularization(The Eurographics Association and John Wiley and Sons Ltd., 2014) Boulch, Alexandre; Gorce, Martin de La; Marlet, Renaud; Thomas Funkhouser and Shi-Min HuThis paper presents a method for the 3D reconstruction of a piecewise-planar surface from range images, typically laser scans with millions of points. The reconstructed surface is a watertight polygonal mesh that conforms to observations at a given scale in the visible planar parts of the scene, and that is plausible in hidden parts. We formulate surface reconstruction as a discrete optimization problem based on detected and hypothesized planes. One of our major contributions, besides a treatment of data anisotropy and novel surface hypotheses, is a regularization of the reconstructed surface w.r.t. the length of edges and the number of corners. Compared to classical area-based regularization, it better captures surface complexity and is therefore better suited for man-made environments, such as buildings. To handle the underlying higher-order potentials, that are problematic for MRF optimizers, we formulate minimization as a sparse mixed-integer linear programming problem and obtain an approximate solution using a simple relaxation. Experiments show that it is fast and reaches near-optimal solutions.Item A Variational Taxonomy for Surface Reconstruction from Oriented Points(The Eurographics Association and John Wiley and Sons Ltd., 2014) Schroers, Christopher; Setzer, Simon; Weickert, Joachim; Thomas Funkhouser and Shi-Min HuThe problem of reconstructing a watertight surface from a finite set of oriented points has received much attention over the last decades. In this paper, we propose a general higher order framework for surface reconstruction. It is based on the idea that position and normal defined by each oriented point can be used to construct an implicit local description of the unknown surface. On the one hand, this allows us to systematically explain and relate several popular methods, for example implicit moving least squares, smooth signed distance surface reconstruction as well as (screened) Poisson surface reconstruction. On the other hand, it allows to derive and discuss a number of new approaches for reconstructing either the signed distance or the indicator function of the sought object. All of these approaches are able to achieve competitive results but one of them turns out to be especially promising. To improve reconstructions in difficult real world scenarios where point clouds have been estimated from colour images, we introduce a hull constraint that encourages the surface to stay within a given region. Our framework is implemented on the GPU using a recent cyclic scheme called Fast Jacobi, which combines low implementational effort with high efficiency.Item Preface and Table of Contents(The Eurographics Association and Blackwell Publishing Ltd., 2014) Thomas Funkhouser and Shi-Min HuItem 3D Shape Segmentation and Labeling via Extreme Learning Machine(The Eurographics Association and John Wiley and Sons Ltd., 2014) Xie, Zhige; Xu, Kai; Liu, Ligang; Xiong, Yueshan; Thomas Funkhouser and Shi-Min HuWe propose a fast method for 3D shape segmentation and labeling via Extreme Learning Machine (ELM). Given a set of example shapes with labeled segmentation, we train an ELM classifier and use it to produce initial segmentation for test shapes. Based on the initial segmentation, we compute the final smooth segmentation through a graph-cut optimization constrained by the super-face boundaries obtained by over-segmentation and the active contours computed from ELM segmentation. Experimental results show that our method achieves comparable results against the state-of-the-arts, but reduces the training time by approximately two orders of magnitude, both for face-level and super-face-level, making it scale well for large datasets. Based on such notable improvement, we demonstrate the application of our method for fast online sequential learning for 3D shape segmentation at face level, as well as realtime sequential learning at super-face level.Item Cross-Collection Map Inference by Intrinsic Alignment of Shape Spaces(The Eurographics Association and John Wiley and Sons Ltd., 2014) Shapira, Nitzan; Ben-Chen, Mirela; Thomas Funkhouser and Shi-Min HuInferring maps between shapes is a long standing problem in geometry processing. The less similar the shapes are, the harder it is to compute a map, or even define criteria to evaluate it. In many cases, shapes appear as part of a collection, e.g. an animation or a series of faces or poses of the same character, where the shapes are similar enough, such that maps within the collection are easy to obtain. Our main observation is that given two collections of shapes whose ''shape space'' structure is similar, it is possible to find a correspondence between the collections, and then compute a cross-collection map. The cross-map is given as a functional correspondence, and thus it is more appropriate in cases where a bijective point-to-point map is not well defined. Our core idea is to treat each collection as a point-sampling from a low-dimensional shape-space manifold, and use dimensionality reduction techniques to find a low-dimensional Euclidean embedding of this sampling. To measure distances on the shape-space manifold, we use the recently introduced shape differences, which lead to a similar low-dimensional structure of the shape spaces, even if the shapes themselves are quite different. This allows us to use standard affine registration for point-clouds to align the shape-spaces, and then find a functional cross-map using a linear solve. We demonstrate the results of our algorithm on various shape collections and discuss its properties.Item Pattern-Based Quadrangulation for N-Sided Patches(The Eurographics Association and John Wiley and Sons Ltd., 2014) Takayama, Kenshi; Panozzo, Daniele; Sorkine-Hornung, Olga; Thomas Funkhouser and Shi-Min HuWe propose an algorithm to quadrangulate an N-sided patch with prescribed numbers of edge subdivisions at its boundary. Our algorithm is guaranteed to succeed for arbitrary valid input, which is proved using a canonical simplification of the input and a small set of topological patterns that are sufficient for supporting all possible cases. Our algorithm produces solutions with minimal number of irregular vertices by default, but it also allows the user to choose other feasible solutions by solving a set of small integer linear programs. We demonstrate the effectiveness of our algorithm by integrating it into a sketch-based quad remeshing system. A reference C++ implementation of our algorithm is provided as a supplementary material.