Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow
Crane, Weischedel, Wardetzky
ACM Trans. on Graph. (2013)
Abstract
We introduce the heat method for computing the geodesic distance to a specified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard linear elliptic problems. The resulting systems can be prefactored once and subsequently solved in nearlinear time. In practice, distance is updated an order of magnitude faster than with stateoftheart methods, while maintaining a comparable level of accuracy. The method requires only standard differential operators and can hence be applied on a wide variety of domains (grids, triangle meshes, point clouds, etc.). We provide numerical evidence that the method converges to the exact distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where greater regularity is required.
Project
BibTeX
@article{Crane:2013:GH,
author = {Keenan Crane and Clarisse Weischedel and Max Wardetzky},
title = {{Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow}},
journal = {ACM Trans. Graph.},
volume = {32},
number = {5},
year = {2013},
publisher = {ACM},
address = {New York, NY, USA}
}
CACM Research Highlight
Spin Transformations of Discrete Surfaces
Crane, Pinkall, Schröder
ACM Trans. on Graph. (2011)
Abstract
This paper introduces a new method for computing conformal transformations of triangle meshes in R^{3}. Conformal maps are desirable in digital geometry processing because they do not exhibit shear, and therefore preserve texture fidelity as well as the quality of the mesh itself. Traditional discretizations consider maps into the complex plane, which are useful only for problems such as surface parameterization and planar shape deformation where the target surface is flat. We instead consider maps into the quaternions, which allows us to work directly with surfaces sitting in R^{3}. In particular, we introduce a quaternionic Dirac operator and use it to develop a novel integrability condition on conformal deformations. Our discretization of this condition results in a sparse linear system that is simple to build and can be used to efficiently edit surfaces by manipulating curvature and boundary data, as demonstrated via several mesh processing applications.
BibTeX
@article{Crane:2011:STD,
author = {Crane, Keenan and Pinkall, Ulrich and Schr\"{o}der, Peter},
title = {Spin Transformations of Discrete Surfaces},
journal = {ACM Trans. Graph.},
volume = {30},
number = {4},
year = {2011},
publisher = {ACM},
address = {New York, NY, USA},
}
Robust Fairing via Conformal Curvature Flow
Crane, Pinkall, Schröder
ACM Trans. on Graph. (2013)
Abstract
This paper presents a formulation of Willmore flow for triangulated surfaces that permits extraordinarily large time steps and naturally preserves the quality of the input mesh. The main insight is that Willmore flow becomes remarkably stable when expressed in curvature space—we develop the precise conditions under which curvature is allowed to evolve. The practical outcome is a highly efficient algorithm that naturally preserves texture and does not require remeshing during the flow. We apply this algorithm to surface fairing, geometric modeling, and construction of constant mean curvature (CMC) surfaces. We also present a new algorithm for lengthpreserving flow on planar curves, which provides a valuable analogy for the surface case.
BibTeX
@article{Crane:2013:RFC,
author = {Crane, Keenan and Pinkall, Ulrich and Schr\"{o}der, Peter},
title = {Robust Fairing via Conformal Curvature Flow},
journal = {ACM Trans. Graph.},
volume = {32},
number = {4},
year = {2013},
publisher = {ACM},
address = {New York, NY, USA},
}
Trivial Connections on Discrete Surfaces
Crane, Desbrun, Schröder
Symp. on Geometry Proc. (2010)
Abstract
This paper presents a straightforward algorithm for constructing connections on surfaces that are as smooth as possible everywhere but on a prescribed set of isolated singularities with given index. Such connections can be used to design rotationally symmetric direction fields, which are essential in applications such as quadrilateral remeshing and texture synthesis. We compute connections by solving a single sparse linear system built from standard operators. Our solutions are globally optimal in the sense that they describe the trivial connection closest to LeviCivita among all connections with the prescribed set of singularities. Relative to previous methods our algorithm is surprisingly simple, and can be implemented using standard operations from mesh processing and linear algebra.
BibTeX
@article{Crane:2010:TCD,
author={Keenan Crane and Mathieu Desbrun and Peter Schr\"{o}der},
title={Trivial Connections on Discrete Surfaces},
journal={Computer Graphics Forum (SGP)},
volume={29},
number={5},
pages={15251533},
year={2010}
}
Best Paper Award
Globally Optimal Direction Fields
Knöppel, Crane, Pinkall, Schröder
ACM Trans. on Graph. (2013)
Abstract
This paper presents a method for constructing smooth unit ndirection fields (line fields, cross fields, etc.) on surfaces that is an order of magnitude faster than stateoftheart methods, while still producing fields of equal or better quality. The method is based on a simple quadratic energy whose minimizers are globally optimal in the sense that they produce the smoothest fields over all possible configurations of singularities (number, location, and index). The method is fully automatic and can optionally produce fields aligned with a given guidance field, for example, principal curvature directions. Computationally the smoothest field is found via a sparse eigenvalue problem involving a matrix similar to the cotanLaplacian. When a guidance field is present, finding the optimal field amounts to solving a single linear Poisson problem.
BibTeX
@article{Knoppel:2013:GOD,
author = {Kn\"{o}ppel, Felix and Crane, Keenan and Pinkall, Ulrich and Schr\"{o}der, Peter},
title = {Globally optimal direction fields},
journal = {ACM Trans. Graph.},
volume = {32},
number = {4},
year = {2013},
publisher = {ACM},
address = {New York, NY, USA},
}
A General Framework for Bilateral and Mean Shift Filtering
Solomon, Crane, Butscher, Wojtan
arXiv:1405.4734 (2014)
Abstract
We present a generalization of the bilateral filter that can be applied to featurepreserving smoothing of signals on images, meshes, and other domains within a single unified framework. Our discretization is competitive with stateoftheart smoothing techniques in terms of both accuracy and speed, is easy to implement, and has parameters that are straightforward to understand. Unlike previous bilateral filters developed for meshes and other irregular domains, our construction reduces exactly to the image bilateral on rectangular domains and comes with a rigorous foundation in both the smooth and discrete settings. These guarantees allow us to construct unconditionally convergent meanshift schemes that handle a variety of extremely noisy signals. We also apply our framework to geometric edgepreserving effects like feature enhancement and show how it is related to local histogram techniques.
BibTeX
@article{Solomon:2014:GFB,
author = {Solomon, Justin and Crane, Keenan and Butscher, Adrian and Wojtan, Chris},
title = {A General Framework for Bilateral and Mean Shift Filtering},
journal = {ArXiv eprints},
volume = {32},
archivePrefix = "arXiv",
eprint = {1405.4734},
primaryClass = "cs.GR",
keywords = {Computer Science  Graphics},
year = {2014},
month = {April}
}
Digital Geometry Processing with Discrete Exterior Calculus
Crane, de Goes, Desbrun, Schröder
SIGGRAPH 2013 Course Notes
Abstract
This course provides an introduction to geometry processing using discrete exterior calculus (DEC). DEC provides a simple, flexible, and efficient framework within which one can build a unified platform for geometry processing. The course provides essential mathematical background as well as a large array of realworld examples. It also provides a short survey of the most relevant recent developments in digital geometry processing and discrete differential geometry.
BibTeX
@inproceedings{Crane:2013:DGP,
author = {Keenan Crane, Fernando de Goes, Mathieu Desbrun, Peter Schröder},
title = {Digital Geometry Processing with Discrete Exterior Calculus},
booktitle = {ACM SIGGRAPH 2013 courses},
series = {SIGGRAPH '13},
year = {2013},
location = {Anaheim, California},
numpages = {126},
publisher = {ACM},
address = {New York, NY, USA},
}
Lie Group Integrators for Animation and Control of Vehicles
Kobilarov, Crane, Desbrun
ACM Trans. on Graph. (2009)
Abstract
This paper is concerned with the animation and control of vehicles with complex dynamics such as helicopters, boats, and cars. Motivated by recent developments in discrete geometric mechanics we develop a general framework for integrating the dynamics of holonomic and nonholonomic vehicles by preserving their statespace geometry and motion invariants. We demonstrate that the resulting integration schemes are superior to standard methods in numerical robustness and efficiency, and can be applied to many types of vehicles. In addition, we show how to use this framework in an optimal control setting to automatically compute accurate and realistic motions for arbitrary userspecified constraints.
BibTeX
@article{Kobilarov:2009:LGI,
author = {Kobilarov, Marin and Crane, Keenan and Desbrun, Mathieu},
title = {Lie group integrators for animation and control of vehicles},
journal = {ACM Trans. Graph.},
volume = {28},
number = {2},
month = {May},
year = {2009},
}
EnergyPreserving Integrators for Fluid Animation
Mullen, Crane, Pavlov, Tong, Desbrun
ACM Trans. on Graph. (2009)
Abstract
Numerical viscosity has long been a problem in fluid animation. Existing methods suffer from intrinsic artificial dissipation and often apply complicated computational mechanisms to combat such effects. Consequently, dissipative behavior cannot be controlled or modeled explicitly in a manner independent of time step size, complicating the use of coarse previews and adaptive timestepping methods. This paper proposes simple, unconditionally stable, fully Eulerian integration schemes with no numerical viscosity that are capable of maintaining the liveliness of fluid motion without recourse to corrective devices. Pressure and fluxes are solved efficiently and simultaneously in a timereversible manner on simplicial grids, and the energy is preserved exactly over long time scales in the case of inviscid fluids. These integrators can be viewed as an extension of the classical energypreserving HarlowWelch / CrankNicolson scheme to simplicial grids.
BibTeX
@article{Mullen:2009:EIF,
author = {Mullen, Patrick and Crane, Keenan and Pavlov, Dmitry and Tong, Yiying and Desbrun, Mathieu},
title = {Energypreserving integrators for fluid animation},
journal = {ACM Trans. Graph.},
volume = {28},
number = {3},
month = {July},
year = {2009},
}
A TwoColor Map of Pluto's SubCharon Hemisphere
Young, Binzel, Crane
The Astronomical Journal (2001)
Abstract
Pluto and its satellite Charon regularly occulted or transited each other's disks from 1985 through 1990. The light curves resulting from these events (collectively called "mutual events") have been used to determine albedo maps of Pluto's subCharon hemisphere. We now use a data set of four light curves that were obtained in both B and V Johnson filters to construct a twocolor map of Pluto's surface. We are able to resolve the central part of Pluto's subCharon hemisphere. We find that the dark albedo feature that forms a band below Pluto's equator is comprised of several distinct color units. We detect ratios of Vfilter/Bfilter normal reflectances ranging from 1.15 to 1.39 on Pluto's subCharon hemisphere.
BibTeX
@article{153838811211552,
author={Eliot F. Young and Richard P. Binzel and Keenan Crane},
title={A TwoColor Map of Pluto's SubCharon Hemisphere},
journal={The Astronomical Journal},
volume={121},
number={1},
pages={552},
url={http://stacks.iop.org/15383881/121/i=1/a=552},
year={2001}
}
Beyond Developable: Computational Design and Fabrication with Auxetic Materials
Konakovic, Crane, Deng, Bouaziz, Pauly
ACM Trans. on Graph. (2016)
Abstract
We present a computational method for interactive 3D design and rationalization of surfaces via auxetic materials, i.e., flat flexible material that can stretch uniformly up to a certain extent. A key motivation for studying such material is that one can approximate doublycurved surfaces (such as the sphere) using only flat pieces, making it attractive for fabrication. We physically realize surfaces by introducing cuts into approximately inextensible material such as sheet metal, plastic, or leather. The cutting pattern is modeled as a regular triangular linkage that yields hexagonal openings of spatiallyvarying radius when stretched. In the same way that isometry is fundamental to modeling developable surfaces, we leverage conformal geometry to understand auxetic design. In particular, we compute a global conformal map with bounded scale factor to initialize an otherwise intractable nonlinear optimization. We demonstrate that this global approach can handle nontrivial topology and nonlocal dependencies inherent in auxetic material. Design studies and physical prototypes are used to illustrate a wide range of possible applications.
BibTeX
@article{Konakovic:2016:BDC,
author = {Konakovic, Mina and Crane, Keenan and Deng, Bailin and Bouaziz, Sofien and Piker, Daniel and Pauly, Mark},
title = {Beyond Developable: Computational Design and Fabrication with Auxetic Materials},
journal = {ACM Trans. Graph.},
volume = {35},
number = {4},
year = {2016},
publisher = {ACM},
address = {New York, NY, USA},
}
Stripe Patterns on Surfaces
Knöppel, Crane, Pinkall, Schröder
ACM Trans. on Graph. (2015)
Abstract
Stripe patterns are ubiquitous in nature, describing macroscopic phenomena such as stripes on plants and animals, down to material impurities on the atomic scale. We propose an algorithm for synthesizing stripe patterns on triangulated surfaces, where branch points are automatically inserted in order to achieve userspecified orientation and line spacing. Patterns are characterized as global minimizers of a simple convexquadratic energy which is welldefined in the smooth setting. Computation amounts to finding the smallest eigenvector of a symmetric positivedefinite matrix with the same sparsity pattern as the standard graph Laplacian. The resulting patterns are globally continuous, and can be applied to a variety of tasks in design and texture synthesis.
BibTeX
@article{Knoppel:2015:SPS,
author = {Kn\"{o}ppel, Felix and Crane, Keenan and Pinkall, Ulrich and Schr\"{o}der, Peter},
title = {Stripe Patterns on Surfaces},
journal = {ACM Trans. Graph.},
volume = {34},
number = {4},
year = {2015},
publisher = {ACM},
address = {New York, NY, USA},
}
Capturing and Animating Occluded Cloth
White, Crane, Forsyth
ACM Trans. on Graph. (2007)
Abstract
We capture the shape of moving cloth using a custom set of color markers printed on the surface of the cloth. The output is a sequence of triangle meshes with static connectivity and with detail at the scale of individual markers in both smooth and folded regions. We compute markers' coordinates in space using marker correspondence across multiple synchronized video cameras. Correspondence is determined from color information in small neighborhoods and refined using a novel strain pruning process. Final correspondence does not require neighborhood information. We use a novel data driven holefilling technique to fill occluded regions. Our results include several challenging examples: a wrinkled shirt sleeve, a dancing pair of pants, and a rag tossed onto a cup. Finally, we demonstrate that cloth capture is reusable by animating a pair of pants using human motion capture data.
BibTeX
@article{White:2007:CAO,
author = {White, Ryan and Crane, Keenan and Forsyth, D. A.},
title = {Capturing and animating occluded cloth},
journal = {ACM Trans. Graph.},
volume = {26},
number = {3},
month = {July},
year = {2007},
}
Discrete Connections for Geometry Processing
Keenan Crane
Caltech Master's Thesis (2010)
Abstract
Connections provide a way to compare local quantities defined at different points of a geometric space. This thesis develops a discrete theory of connections that naturally leads to practical, efficient numerical algorithms for geometry processing, including texture synthesis and quadrilateral remeshing. Our formulation is motivated by realworld applications where meshes may be noisy or coarsely discretized. Further, because our discrete framework closely parallels the smooth theory, we can draw upon a huge wealth of existing knowledge to develop and interpret mesh processing algorithms. The solutions we produce are globally optimal in the sense that they describe the trivial connection closest to LeviCivita among all solutions with the prescribed set of singularities. Relative to previous methods our algorithm is surprisingly simple, and can be implemented using standard operations from mesh processing and linear algebra.
BibTeX
@mastersthesis{caltechthesis5880,
title = {Discrete connections for geometry processing},
school = {California Institute of Technology},
author = {Keenan Crane},
year = {2010},
url = {http://resolver.caltech.edu/CaltechTHESIS:05282010102307125}
}
Multiscale 3D Reference Visualization
Glueck, Crane, Anderson, Rutnik, Khan
i3D (2009)
Abstract
Reference grids are commonly used in design software to help users to judge distances and to understand the orientation of the virtual workspace. However, despite their ubiquity in 3D graphics authoring applications, little research has gone into important design considerations of the 3D reference grids themselves, which directly impact their usefulness. In an effort to resolve some of these outstanding issues, we have developed two new techniques; the multiscale reference grid and position pegs that form a consistent foundation for presenting relative scale and position information to the user. Our design of a multiscale reference grid consistently subdivides and coalesces gridlines, based on the computation of a closeness metric, while ensuring that there are neither too many nor too few subdivisions. Position pegs extend the grid so that objects that are lying above or below the ground plane can be brought into a common environmental frame of reference without interfering with the grid or object data. We introduce an analytical system, similar to MIP mapping, to provide a stable viewpointdetermined result. Our design solves several depth cue problems in a way that is independent of viewing projection.
BibTeX
@inproceedings{Glueck:2009:MRV,
author = {Glueck, Michael and Crane, Keenan and Anderson, Sean and Rutnik, Andres and Khan, Azam},
title = {Multiscale 3D reference visualization},
booktitle = {Proceedings of the 2009 symposium on Interactive 3D graphics and games},
series = {I3D '09},
year = {2009},
isbn = {9781605584294},
location = {Boston, Massachusetts},
pages = {225232},
numpages = {8},
url = {http://doi.acm.org/10.1145/1507149.1507186},
doi = {http://doi.acm.org/10.1145/1507149.1507186},
acmid = {1507186},
publisher = {ACM},
address = {New York, NY, USA},
}
Data Driven Cloth Animation
White, Crane, Forsyth
SIGGRAPH 2009 Technical Sketches
Abstract
We present a new method for cloth animation based on data driven synthesis. In contrast to approaches that focus on physical simulation, we animate cloth by manipulating short sequences of existing cloth animation. While our source of data is cloth animation captured using video cameras, the method is equally applicable to simulation data. The approach has benefits in both cases: current cloth capture is limited because small tweaks to the data require filming an entirely new sequence. Likewise, simulation suffers from long computation times and complications such as tangling. In this sketch we create new animations by fitting cloth animation to human motion capture data, i.e., we drive the cloth with a skeleton.
BibTeX
@inproceedings{White:2007:DDC,
author = {White, Ryan and Crane, Keenan and Forsyth, D. A.},
title = {Data driven cloth animation},
booktitle = {ACM SIGGRAPH 2007 sketches},
series = {SIGGRAPH '07},
year = {2007},
location = {San Diego, California},
articleno = {37},
acmid = {1278825},
publisher = {ACM},
address = {New York, NY, USA},
}
Real Time Simulation and Rendering of 3D Fluids
Crane, Llamas, Tariq
GPU Gems 3 (2007)
Abstract
Physically based animation of fluids such as smoke, water, and fire provides some of the most stunning visuals in computer graphics, but has historically been the domain of highquality offline rendering due to great computational cost. In this chapter we not only show how these effects can be simulated and rendered in real time, but also how they can be seamlessly integrated into real time applications.
BibTeX
@InBook{Crane07,
author = "Crane, Keenan and Llamas, Ignacio, and Tariq, Sarah",
title = "Real Time Simulation and Rendering of 3D Fluids",
booktitle = "GPUGems 3",
editor = "Hubert Nguyen",
chapter = "30",
publisher = "AddisonWesley",
year = "2007"
}
Rectangular MultiChart Geometry Images
Carr, Hoberock, Crane, Hart
Symp. on Geom. Proc. (2006)
Abstract
Many mesh parameterization algorithms have focused on minimizing distortion and utilizing texture area, but few have addressed issues related to processing a signal on the mesh surface. We present an algorithm which partitions a mesh into rectangular charts while preserving a onetoone texel correspondence across chart boundaries. This mapping permits any computation on the mesh surface which is typically carried out on a regular grid, and prevents seams by ensuring resolution continuity along the boundary. These features are also useful for traditional texture applications such as surface painting where continuity is important. Distortion is comparable to other parameterization schemes, and the rectangular charts yield efficient packing into a texture atlas. We apply this parameterization to texture synthesis, fluid simulation, mesh processing and storage, and locating geodesics.
BibTeX
@inproceedings{Carr:2006:RMG,
author = {Carr, Nathan A. and Hoberock, Jared and Crane, Keenan and Hart, John C.},
title = {Rectangular MultiChart Geometry Images},
booktitle = {Proceedings of the fourth Eurographics symposium on Geometry processing},
year = {2006},
}
Fast GPU Ray Tracing of Dynamic Meshes using Geometry Images
Carr, Hoberock, Crane, Hart
Graphics Interface 2006
Abstract
Using the GPU to accelerate ray tracing may seem like a natural choice due to the highly parallel nature of the problem. However, determining the most versatile GPU data structure for scene storage and traversal is a challenge. In this paper, we introduce a new method for quick intersection of triangular meshes on the GPU. The method uses a threaded bounding volume hierarchy built from a geometry image, which can be efficiently traversed and constructed entirely on the GPU. This acceleration scheme is highly competitive with other GPU ray tracing methods, while allowing for both dynamic geometry and an efficient level of detail scheme at no extra cost.
BibTeX
@inproceedings{Carr:2006:FGR,
author = {Carr, Nathan A. and Hoberock, Jared and Crane, Keenan and Hart, John C.},
title = {Fast GPU ray tracing of dynamic meshes using geometry images},
booktitle = {Proceedings of Graphics Interface 2006},
series = {GI '06},
year = {2006},
isbn = {1568813082},
location = {Quebec, Canada},
pages = {203209},
numpages = {7},
url = {http://portal.acm.org/citation.cfm?id=1143079.1143113},
acmid = {1143113},
publisher = {Canadian Information Processing Society},
address = {Toronto, Ont., Canada, Canada},
}
