Keenan Crane
CARNEGIE MELLON UNIVERSITY
surface
Keenan Crane
image
About
I am an Assistant Professor of Computer Science and Robotics at Carnegie Mellon University, and a member of the Center for Nonlinear Analysis. My research group applies insights from differential geometry to develop fundamental algorithms for working with real-world geometric data. I received my BS from UIUC, was a Google PhD Fellow at Caltech, and an NSF Mathematical Sciences Postdoctoral Fellow at Columbia University. I advise four terrific PhD students: Nick Sharp, Chris Yu, Rohan Sawhney, and Katherine Ye, and teach a course on Discrete Differential Geometry.
Research Overview
video
Publications


The Vector Heat Method

icon
Sharp, Soliman, Crane
(in submission, 2018)

Abstract

This paper describes a method for efficiently computing parallel transport of tangent vectors on curved surfaces, or more generally, any vector-valued data on a curved manifold. More precisely, it extends a vector field defined over any region to the rest of the domain via parallel transport along shortest geodesics. This basic operation enables fast, robust algorithms for extrapolating level set velocities, inverting the exponential map, computing geometric medians and Karcher/Fréchet means of arbitrary distributions, constructing centroidal Voronoi diagrams, and finding consistently ordered landmarks. Rather than evaluate parallel transport by explicitly tracing geodesics, we show that it can be computed via a short-time heat flow involving the connection Laplacian. As a result, transport can be achieved by solving three prefactored linear systems, each akin to a standard Poisson problem. Moreover, to implement the method we need only a discrete connection Laplacian, which we describe for a variety of geometric data structures (point clouds, polygon meshes, etc.). We also study the numerical behavior of our method, showing empirically that it converges under refinement, and augment the construction of intrinsic Delaunay triangulations (iDT) so that they can be used in the context of tangent vector field processing.

PDF Project


Variational Surface Cutting

icon
Sharp, Crane
ACM Trans. on Graph. (2018)

Abstract

This paper develops a global variational approach to cutting curved surfaces so that they can be flattened into the plane with low metric distortion. Such cuts are a critical component in a variety of algorithms that seek to parameterize surfaces over flat domains, or fabricate structures from flat materials. Rather than evaluate the quality of a cut solely based on properties of the curve itself (e.g., its length or curvature), we formulate a flow that directly optimizes the distortion induced by cutting and flattening. Notably, we do not have to explicitly parameterize the surface in order to evaluate the cost of a cut, but can instead integrate a simple evolution equation defined on the cut curve itself. We arrive at this flow via a novel application of shape derivatives to the Yamabe equation from conformal geometry. We then develop an Eulerian numerical integrator on triangulated surfaces, which does not restrict cuts to mesh edges and can incorporate user-defined data such as importance or occlusion. The resulting cut curves can be used to drive distortion to arbitrarily low levels, and have a very different character from cuts obtained via purely discrete formulations. We briefly explore potential applications to computational design, as well as connections to space filling curves and the problem of uniform heat distribution.

BibTeX

@article{Sharp:2018:VSC,
author = {Sharp, Nick and Crane, Keenan},
title = {Variational Surface Cutting},
journal = {ACM Trans. Graph.},
volume = {37},
number = {4},
year = {2018},
publisher = {ACM},
address = {New York, NY, USA},
}


Optimal Cone Singularities
for Conformal Flattening

icon
Soliman, Slepčev, Crane
ACM Trans. on Graph. (2018)

Abstract

Angle-preserving or conformal surface parameterization has proven to be a powerful tool across applications ranging from geometry processing, to digital manufacturing, to machine learning, yet conformal maps can still suffer from severe area distortion. Cone singularities provide a way to mitigate this distortion, but finding the best configuration of cones is notoriously difficult. This paper develops a strategy that is globally optimal in the sense that it minimizes total area distortion among all possible cone configurations (number, placement, and size) that have no more than a fixed total cone angle. A key insight is that, for the purpose of optimization, one should not work directly with curvature measures (which naturally represent cone configurations), but can instead apply Fenchel-Rockafellar duality to obtain a formulation involving only ordinary functions. The result is a convex optimization problem, which can be solved via a sequence of sparse linear systems easily built from the usual cotangent Laplacian. The method supports user-defined notions of importance, constraints on cone angles (e.g., positive, or within a given range), and sophisticated boundary conditions (e.g., convex, or polygonal). We compare our approach to previous techniques on a variety of challenging models, often achieving dramatically lower distortion, and demonstrating that global optimality leads to extreme robustness in the presence of noise or poor discretization.

BibTeX

@article{Soliman:2018:OCS,
author = {Soliman, Yousuf and Slep\v{c}ev, Dejan and Crane, Keenan},
title = {Optimal Cone Singularities for Conformal Flattening},
journal = {ACM Trans. Graph.},
volume = {37},
number = {4},
year = {2018},
publisher = {ACM},
address = {New York, NY, USA},
}



Developability of Triangle Meshes

icon
Stein, Grinspun, Crane
ACM Trans. on Graph. (2018)

Abstract

Developable surfaces are those that can be made by smoothly bending flat pieces without stretching or shearing. We introduce a definition of developability for triangle meshes which exactly captures two key properties of smooth developable surfaces, namely flattenability and presence of straight ruling lines. This definition provides a starting point for algorithms in developable surface modeling—we consider a variational approach that drives a given mesh toward developable pieces separated by regular seam curves. Computation amounts to gradient descent on an energy with support in the vertex star, without the need to explicitly cluster patches or identify seams. We briefly explore applications to developable design and manufacturing.

BibTeX

@article{Stein:2018:DSF,
author = {Stein, Oded and Grinspun, Eitan and Crane, Keenan},
title = {Developable Surface Flow},
journal = {ACM Trans. Graph.},
volume = {37},
number = {4},
year = {2018},
publisher = {ACM},
address = {New York, NY, USA},
}

Rapid Deployment of
Curved Surfaces via
Programmable Auxetics

icon
Konaković, Panetta, Crane, Pauly
ACM Trans. on Graph. (2018)

Abstract

Deployable structures are physical mechanisms that can easily transition between two or more geometric configurations; such structures enable industrial, scientific, and consumer applications at a wide variety of scales. This paper develops novel deployable structures that can approximate a large class of doubly-curved surfaces and are easily actuated from a flat initial state via inflation or gravitational loading. The structures are based on two-dimensional rigid mechanical linkages that implicitly encode the curvature of the target shape via a user-programmable pattern that permits locally isotropic scaling under load. We explicitly characterize the shapes that can be realized by such structures—in particular, we show that they can approximate target surfaces of positive mean curvature and bounded scale distortion relative to a given reference domain. Based on this observation, we develop efficient computational design algorithms for approximating a given input geometry. The resulting designs can be rapidly manufactured via digital fabrication technologies such as laser cutting, CNC milling, or 3D printing. We validate our approach through a series of physical prototypes and present several application case studies, ranging from surgical implants to large-scale deployable architecture.

BibTeX

@article{Konakovic:2018:RDC,
author = {Konakovi\'{c}, Mina and Panetta, Julian and Crane, Keenan and Pauly, Mark},
title = {Rapid Deployment of Curved Surfaces via Programmable Auxetics},
journal = {ACM Trans. Graph.},
volume = {37},
number = {4},
year = {2018},
publisher = {ACM},
address = {New York, NY, USA},
}

 
Boundary First Flattening

icon
Sawhney, Crane
ACM Trans. on Graph. (2017)

Abstract

A conformal flattening maps a curved surface to the plane without distorting angles—such maps have become a fundamental building block for problems in geometry processing, numerical simulation, and computational design. Yet existing methods provide little direct control over the shape of the flattened domain, or else demand expensive nonlinear optimization. Boundary first flattening (BFF) is a linear method for conformal parameterization which is faster than traditional linear methods, yet provides control and quality comparable to sophisticated nonlinear schemes. The key insight is that the boundary data for many conformal mapping problems can be efficiently constructed via the Cherrier formula together with a pair of Poincaré-Steklov operators; once the boundary is known, the map can be easily extended over the rest of the domain. Since computation demands only a single factorization of the real Laplace matrix, the amortized cost is about 50x less than any previously published technique for boundary-controlled conformal flattening. As a result, BFF opens the door to real-time editing or fast optimization of high-resolution maps, with direct control over boundary length or angle. We show how this method can be used to construct maps with sharp corners, cone singularities, minimal area distortion, and uniformization over the unit disk; we also demonstrate for the first time how a surface can be conformally flattened directly onto any given target shape.

PDF Project
BibTeX

@article{Sawhney:2017:BFF,
author = {Sawhney, Rohan and Crane, Keenan},
title = {Boundary First Flattening},
journal = {ACM Trans. Graph.},
volume = {37},
number = {1},
month = dec,
year = {2017},
issn = {0730-0301},
pages = {5:1--5:14},
articleno = {5},
numpages = {14},
url = {http://doi.acm.org/10.1145/3132705},
doi = {10.1145/3132705},
acmid = {3132705},
publisher = {ACM},
address = {New York, NY, USA}
}

Conformal Geometry of
Simplicial Surfaces

icon
Crane
Proceedings of Symposia in
Applied Mathematics (to appear)

Abstract

Conformal geometry studies geometric properties that are invariant with respect to angle-preserving transformations. In the discrete setting of polyhedral surfaces, the idea of naively preserving angles leads to a notion of conformal geometry that is far too rigid, i.e., it does not capture the rich behavior found in the smooth setting. These notes explore several alternative notions of discrete conformal structure, culminating with a recent uniformization theorem for general simplicial surfaces. Topics covered include circle packings, circle patterns, inversive distance, discrete Yamabe flow, and connections to variational principles for ideal hyperbolic polyhedra. (This chapter is an extended version of course notes developed for the 2018 AMS Short Course on Discrete Differential Geometry.)

Project
BibTeX

@incollection{Crane:2018:DCG,
author = "Keenan Crane",
title = {{Discrete Conformal Geometry}},
booktitle = "Proceedings of Symposia in Applied Mathematics",
publisher = "American Mathematical Society",
year = 2018,
}

The Heat Method
for Distance Computation

icon
Crane, Weischedel, Wardetzky
Communications of the ACM (2017)

Abstract

We introduce the heat method for solving the single- or multiple-source shortest path problem on both flat and curved domains. A key insight is that distance computation can be split into two stages: first find the direction along which distance is increasing, then compute the distance itself. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard sparse linear systems. These systems can be factored once and subsequently solved in near-linear time, substantially reducing amortized cost. Real-world performance is an order of magnitude faster than state-of-the-art methods, while maintaining a comparable level of accuracy. The method can be applied in any dimension, and on any domain that admits a gradient and inner product—including regular grids, triangle meshes, and point clouds. Numerical evidence indicates 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 desired.

Project
BibTeX

@article{Crane:2017:HMD,
author = {Crane, Keenan and Weischedel, Clarisse and Wardetzky, Max},
title = {The Heat Method for Distance Computation},
journal = {Commun. ACM},
issue_date = {November 2017},
volume = {60},
number = {11},
month = oct,
year = {2017},
issn = {0001-0782},
pages = {90--99},
numpages = {10},
url = {http://doi.acm.org/10.1145/3131280},
doi = {10.1145/3131280},
acmid = {3131280},
publisher = {ACM},
address = {New York, NY, USA},
}

Research Highlight
A Glimpse Into
Discrete Differential Geometry

icon
Crane, Wardetzky
Notices of the American Mathematical
Society (2017)

Abstract

The emerging field of discrete differential geometry (DDG) studies discrete analogues of smooth geometric objects, providing an essential link between analytical descriptions and computation. In recent years it has unearthed a rich variety of new perspectives on applied problems in computational anatomy/biology, computational mechanics, industrial design, computational architecture, and digital geometry processing at large. The basic philosophy of discrete differential geometry is that a discrete object like a polyhedron is not merely an approximation of a smooth one, but rather a differential geometric object in its own right. In contrast to traditional numerical analysis which focuses on eliminating approximation error in the limit of refinement (e.g., by taking smaller and smaller finite differences), DDG places an emphasis on the so-called “mimetic” viewpoint, where key properties of a system are preserved exactly, independent of how large or small the elements of a mesh might be. Just as algorithms for simulating mechanical systems might seek to exactly preserve physical invariants such as total energy or momentum, structure-preserving models of discrete geometry seek to exactly preserve global geometric invariants such as total curvature. More broadly, DDG focuses on the discretization of objects that do not naturally fall under the umbrella of traditional numerical analysis. This article provides an overview of some of the themes in DDG.

PDF
BibTeX

@article{Crane:2017:GID,
author={Keenan Crane and Max Wardetzky},
title={A Glimpse Into Discrete Differential Geometry},
journal={Notices of the American Mathematical Society},
month={November},
volume={64},
number={10},
pages={1153--1159},
year={2017}
}

SUBSTANCE and STYLE:
Domain-Specific Languages
for Mathematical Diagrams

icon
Ni, Ye, Sunshine, Aldrich, Crane
DSLDI (2017)

Abstract

Creating mathematical diagrams is essential for both developing one’s intuition and conveying it to others. However, formalizing diagrams in most general-purpose tools requires painstaking low-level manipulation of shapes and positions. We report on early work on PENROSE, a system we are building to automatically visualize mathematics from notation. PENROSE comprises two languages: SUBSTANCE, a domain-specific language that mimics the declarativeness of mathematical notation, and STYLE, a styling language that concisely specifies the visual semantics of the notation. Our system can automatically visualize set theory expressions with user-defined styles, and it can visualize abstract definitions of functions by producing concrete examples. We plan to extend the system to more domains of math.

PDF
BibTeX

@inproceedings{Ni:2017:SSD,
author={Wode Ni and Katherine Ye and Joshua Sunshine and Jonathan Aldrich and Keenan Crane},
title={SUBSTANCE and STYLE: domain-specific languages for mathematical diagrams},
booktitle={DSLDI (Domain-Specific Language Design and Implementation)},
year={2017}
}

 
A Dirac Operator for
Extrinsic Shape Analysis

icon
Liu, Jacobson, Crane
Symp. on Geom. Proc. (2017)

Abstract

The eigenfunctions and eigenvalues of the Laplace-Beltrami operator have proven to be a powerful tool for digital geometry processing, providing a description of geometry that is essentially independent of coordinates or the choice of discretization. However, since Laplace-Beltrami is purely intrinsic it struggles to capture important phenomena such as extrinsic bending, sharp edges, and fine surface texture. We introduce a new extrinsic differential operator called the relative Dirac operator, leading to a family of operators with a continuous trade-off between intrinsic and extrinsic features. Previous operators are either fully or partially intrinsic. In contrast, the proposed family spans the entire spectrum: from completely intrinsic (depending only on the metric) to completely extrinsic (depending only on the Gauss map). By adding an infinite potential well to this (or any) operator we can also robustly handle surface patches with irregular boundary. We explore use of these operators for a variety of shape analysis tasks, and study their performance relative to operators previously found in the geometry processing literature.

PDF
BibTeX

@article{Liu:2017:DOE,
author={Derek Liu and Alec Jacobson and Keenan Crane},
title={A Dirac Operator for Extrinsic Shape Analysis},
journal={Computer Graphics Forum (SGP)},
volume={36},
number={5},
year={2017}
}

Designing Extensible, Domain-Specific Languages for Mathematical Diagrams
icon
Ye, Crane, Aldrich, Sunshine
OBT (2017)

Abstract

In science, a well-chosen illustration can turn bafflement into enlightenment. Yet technical exposition remains largely textual, due to the tremendous expertise required to produce high-quality figures. We propose PENROSE, a system to automatically generate professional-quality mathematical illustrations from high-level, purely semantic descriptions of mathematical objects. Unlike low-level tools where diagrams are specified via graphical primitives, a mathematically-inclined user should not require any graphic design skill to create beautiful diagrams. PENROSE comprises two extensible domain-specific languages (DSLs): SUBSTANCE, which diagrammers use to specify mathematical objects and relationships, and STYLE, which implementers use to encode various ways of realizing these relationships visually, akin to the separation of content and style in modern HTML/CSS. To compile diagrams, we are developing a sophisticated constraint solver incorporating techniques from optimization and computer graphics.

PDF
BibTeX

@inproceedings{Ye:2017:DED,
author={Katherine Ye and Keenan Crane and Joshua Sunshine and Jonathan Aldrich},
title={Designing Extensible, Domain-Specific Languages for Mathematical Diagrams},
booktitle={OBT (Off the Beaten Track)},
year={2017}
}


Computational Design of
Telescoping Structures

icon
Yu, Crane, Coros
ACM Trans. on Graph. (2017)

Abstract

Telescoping structures are valuable for a variety of applications where mechanisms must be compact in size and yet easily deployed. So far, however, there has been no systematic study of the types of shapes that can be modeled by telescoping structures, nor practical tools for telescopic design. We present a novel geometric characterization of telescoping curves, and explore how free-form surfaces can be approximated by networks of such curves. In particular we consider piecewise helical space curves with torsional impulses, which significantly generalize the linear telescopes found in typical engineering designs. Based on this principle we develop a system for computational design and fabrication which allows users to explore the space of telescoping structures; inputs to our system include user sketches or arbitrary meshes, which are then converted to a curve skeleton. We prototype applications in animation, fabrication, and robotics, using our system to design a variety of both simulated and fabricated examples.

PDF
BibTeX

@article{Yu:2017:CDT,
author = {Yu, Chris and Crane, Keenan and Coros, Stelian},
title = {Computational Design of Telescoping Structures},
journal = {ACM Trans. Graph.},
volume = {36},
number = {4},
year = {2017},
publisher = {ACM},
address = {New York, NY, USA},
}

Beyond Developable: Computational Design and Fabrication with Auxetic Materials
icon
Konaković, 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 doubly-curved 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 spatially-varying 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 non-trivial topology and non-local 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 = {Konakovi\'{c}, 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

icon
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 user-specified orientation and line spacing. Patterns are characterized as global minimizers of a simple convex-quadratic energy which is well-defined in the smooth setting. Computation amounts to finding the smallest eigenvector of a symmetric positive-definite 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},
}


A General Framework for
Bilateral and Mean Shift Filtering

icon
Solomon, Crane, Butscher, Wojtan
arXiv:1405.4734 (2014)

Abstract
We present a generalization of the bilateral filter that can be applied to feature-preserving smoothing of signals on images, meshes, and other domains within a single unified framework. Our discretization is competitive with state-of-the-art 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 mean-shift schemes that handle a variety of extremely noisy signals. We also apply our framework to geometric edge-preserving 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 e-prints},
volume = {32},
archivePrefix = "arXiv",
eprint = {1405.4734},
primaryClass = "cs.GR",
keywords = {Computer Science - Graphics},
year = {2014},
month = {April}
}


Robust Fairing via
Conformal Curvature Flow

icon
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 length-preserving 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},
}



Globally Optimal Direction Fields

icon
Knöppel, Crane, Pinkall, Schröder
ACM Trans. on Graph. (2013)

Abstract

This paper presents a method for constructing smooth unit n-direction fields (line fields, cross fields, etc.) on surfaces that is an order of magnitude faster than state-of-the-art 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 cotan-Laplacian. 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},
}


Digital Geometry Processing with
Discrete Exterior Calculus

icon
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 real-world 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},
}


Spin Transformations
of Discrete Surfaces

icon
Crane, Pinkall, Schröder
ACM Trans. on Graph. (2011)

Abstract

This paper introduces a new method for computing conformal transformations of triangle meshes in R3. 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 R3. 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},
}


Discrete Connections
for Geometry Processing

icon
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 real-world 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 Levi-Civita 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:05282010-102307125}
}


Trivial Connections
on Discrete Surfaces

icon
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 Levi-Civita 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={1525-1533},
year={2010}
}

Best Paper Award

Lie Group Integrators for
Animation and Control of Vehicles

icon
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 state-space 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 user-specified 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},
}


Energy-Preserving Integrators
for Fluid Animation

icon
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 time-stepping 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 time-reversible 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 energy-preserving Harlow-Welch / Crank-Nicolson 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 = {Energy-preserving integrators for fluid animation},
journal = {ACM Trans. Graph.},
volume = {28},
number = {3},
month = {July},
year = {2009},
}


Multiscale 3D Reference Visualization

icon
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 viewpoint-determined 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 = {978-1-60558-429-4},
location = {Boston, Massachusetts},
pages = {225--232},
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},
}


Capturing and Animating
Occluded Cloth

icon
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 hole-filling 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},
}



Data Driven Cloth Animation

icon
White, Crane, Forsyth
SIGGRAPH 2007 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

icon
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 high-quality 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 = "Addison-Wesley",
year = "2007"
}


Rectangular Multi-Chart
Geometry Images

icon
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 one-to-one 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 Multi-Chart Geometry Images},
booktitle = {Proceedings of the fourth Eurographics symposium on Geometry processing},
year = {2006},
}


Fast GPU Ray Tracing of Dynamic
Meshes using Geometry Images

icon
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 = {1-56881-308-2},
location = {Quebec, Canada},
pages = {203--209},
numpages = {7},
url = {http://portal.acm.org/citation.cfm?id=1143079.1143113},
acmid = {1143113},
publisher = {Canadian Information Processing Society},
address = {Toronto, Ont., Canada, Canada},
}


A Two-Color Map of Pluto's
Sub-Charon Hemisphere

icon
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 sub-Charon hemisphere. We now use a data set of four light curves that were obtained in both B and V Johnson filters to construct a two-color map of Pluto's surface. We are able to resolve the central part of Pluto's sub-Charon 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 V-filter/B-filter normal reflectances ranging from 1.15 to 1.39 on Pluto's sub-Charon hemisphere.

BibTeX

@article{1538-3881-121-1-552,
author={Eliot F. Young and Richard P. Binzel and Keenan Crane},
title={A Two-Color Map of Pluto's Sub-Charon Hemisphere},
journal={The Astronomical Journal},
volume={121},
number={1},
pages={552},
url={http://stacks.iop.org/1538-3881/121/i=1/a=552},
year={2001}
}

Code
icon
BFF —fast interactive tool for surface parameterization, based on boundary first flattening.
icon
libgeodesic —highly optimized library for distance transforms, based on the heat method.
icon
stripes —computes evenly-spaced pattern of stripes aligned with a given direction field.
icon
fieldgen —fully automatic generation of optimal direction fields on surfaces, with optional curvature alignment. Also provides editing via trivial connections.
icon
Comb —optimal direction field design with user-specified singularities. Based on our trivial connections paper.
icon
SpinXForm —core solver for conformal (i.e., angle-preserving) geometry processing, based on spin transformations. Naturally preserves texture and mesh quality.
icon
DGPDEC —unified framework for geometry processing algorithms based on discrete exterior calculus (DEC).
icon
QJulia —fragment shader for real-time rendering of quaternion Julia sets.
icon
tilings —generates meshes of all the regular and semi-regular tilings of the plane (in Wavefront OBJ format).
Miscellaneous / Fun
An Overview of Conformal Geometry Processing (2017)
icon
The Emotional Rollercoaster of Research (2017)
icon
Laplace-Beltrami: The Swiss Army Knife of Geometry Processing (2014)
icon
LEARN.GRAPHICS (collaborative site for graphics education)
icon
Triangle Mesh Derivatives
Cheat Sheet (2018)

icon
Triangle Areas
Cheat Sheet (2010)

icon
Variational Principles
Cheat Sheet (2009)

icon
Synthesizing the
Sound of Splashing (2007)

icon
Homotopy, Homology,
and Cut Graphs (2006)

icon
A Survey of Efficient Structures
for Geometry Processing (2006)

icon
Bias in Rendering (2006)
icon
Making Fractals with Christmas Ornaments (2005)
icon

GraphDraw (2005)

icon

Poincaré-Hopf, Revisited (2005)

icon
Ray Tracing Quaternion
Julia Sets on the GPU (2004)

icon

3D Tashoku Go (2003)

icon

Straylight (2001)

icon