Person:

Gortler, Steven

This work deals with the problem of practical mesh generation for surface normal approximation. Part of its contribution is in presenting previous work in a unified framework. A new algorithm for surface normal approximation is then introduced which improves upon existing ones in a number of aspects. In particular, it produces better approximations of surfaces both in practice and in the theoretical limit regime. Additionally, it resolves in a simple way some of the problems that previous methods for surface approximation suffered from.

We describe conditions under which an appropriately-defined anisotropic Voronoi diagram of a set of sites in Euclidean space is guaranteed to be composed of connected cells in any number of dimensions. These conditions are natural for problems in optimization and approximation, and algorithms already exist to produce sets of sites that satisfy them.

Sensor network localization is an instance of the NP-Hard graph realization problem. Thus, methods used in practice are not guaranteed to find the correct localization, even if it is uniquely determined by the input distances. In this article, we show the following: if the sensors are allowed to wiggle, giving us perturbed distance data, we can apply a novel algorithm to realize arbitrary Generically Globally Rigid graphs (GGR), or certain vertex subsets in non-GGR graphs whose relative positions are fixed (which include vertex sets of GGR subgraphs). And this strategy works in any dimension. In the language of structural rigidity theory, our approach corresponds to calculating the approximate kernel of a generic stress matrix for the given graph and distance data. To make our algorithm suitable for real-world applications, we also present: (i) various techniques for improving the robustness of the algorithm in the presence of measurement noise; (ii) an algorithm for detecting certain subsets of graph vertices whose relative positions are fixed in any generic realization of the graph and robustly localizing these subsets of vertices, (iii) a strategy for reducing the number of measurements needed by the algorithm. We provide simulation results of our algorithm.

Particles interacting with short-ranged potentials have attracted increasing interest, partly for their ability to model mesoscale systems such as colloids interacting via DNA or depletion. We consider the free-energy landscape of such systems as the range of the potential goes to zero. In this limit, the landscape is entirely defined by geometrical manifolds, plus a single control parameter. These manifolds are fundamental objects that do not depend on the details of the interaction potential and provide the starting point from which any quantity characterizing the system—equilibrium or nonequilibrium—can be computed for arbitrary potentials. To consider dynamical quantities we compute the asymptotic limit of the Fokker–Planck equation and show that it becomes restricted to the low-dimensional manifolds connected by “sticky” boundary conditions. To illustrate our theory, we compute the low-dimensional manifolds for Graphic identical particles, providing a complete description of the lowest-energy parts of the landscape including floppy modes with up to 2 internal degrees of freedom. The results can be directly tested on colloidal clusters. This limit is a unique approach for understanding energy landscapes, and our hope is that it can also provide insight into finite-range potentials.

In “Shape From Specular Flow: Is One Flow Enough?” (Vasilyev, et al., 2011 [5]) we show that mirror shape can often be reconstructed from the observation of a single specular flow. In this technical report we provide additional details that, due to space constraints, could not be included in the paper. First we provide a derivation of the linear system for the reflection field derivative in the direction orthogonal to the flow, ˆry. Second, we derive an expression for the determinant of this system which is independent of coordinate system. Third, we show that the sphere is reconstructable whenever the scene rotation is neither on the equator nor parallel to the view direction. Finally we provide additional details for the outline of the proof that reconstructability is a generic property and for our numerical investigation of the dimensionality of the variety described by the “bad” conditions.

We present a 3d deformation method based on Moving Least Squares that extends the work by Schaefer et al. [Schaefer et al. 2006] to the 3d setting. The user controls the deformation by manipulating a set of point handles. Locally, the deformation takes the form of either a rigid transformation or optionally a similarity transformation, and tends to preserve local features. Our derivation of the closed-form solution is based on singular value decomposition, and is applicable to deformation in arbitrary dimensions, as opposed to the planar case in [Schaefer et al. 2006]. Our prototype implementation allows interactive deformation of meshes of over 100k vertices. For the application of 3d mesh deformation, we further introduce a weighting scheme that determines the influence of point handles on vertices based on approximate mesh geodesics. In practice, the new scheme gives much better deformation results for limbed character models, compared with simple Euclidean distance based weighting. The new weighting scheme can be of use to the traditional skinny based deformation technique as well.

In this paper we study the property of generic global rigidity for frameworks of graphs embedded in d-dimensional complex space and in a d-dimensional pseudo-Euclidean space R(^{2}) with a metric of indefinite signature). We show that a graph is generically globally rigid in Euclidean space iff it is generically globally rigid in a complex or pseudo-Euclidean space. We also establish that global rigidity is always a generic property of a graph in complex space, and give a sufficient condition for it to be a generic property in a pseudo-Euclidean space. Extensions to hyperbolic space are also discussed.

Recently the light-field and lumigraph systems have been proposed as general methods of representing the visual information present in a scene. These methods represent this information as a 4D function of light over the domain of directed lines. These systems use the intersection points of the lines on two planes to parameterize the lines in space. This paper explores the structure of the two-plane parameterization in detail. In particular we analyze the association between the geometry of the scene and subsets of the 4D data. The answers to these questions are essential to understanding the relationship between a lumigraph, and the geometry that it attempts to represent. This knowledge is potentially important for a variety of applications such as extracting shape from lumigraph data, and lumigraph compression.

We introduce multi-chart geometry images, a new representation for arbitrary surfaces. It is created by resampling a surface onto a regular 2D grid. Whereas the original scheme of Gu et al. maps the entire surface onto a single square, we use an atlas construction to map the surface piecewise onto charts of arbitrary shape. We demonstrate that this added flexibility reduces parametrization distortion and thus provides greater geometric fidelity, particularly for shapes with long extremities, high genus, or disconnected components. Traditional atlas constructions suffer from discontinuous reconstruction across chart boundaries, which in our context create unacceptable surface cracks. Our solution is a novel zippering algorithm that creates a watertight surface. In addition, we present a new atlas chartification scheme based on clustering optimization.

Complex meshes tend to have intricate, detailed silhouettes. This paper proposes two algorithms for extracting a simpler, approximate silhouette from a high-resolution model. Our methods preserve the important features of the silhouette by using the silhouette of a coarser, simplified mesh as a guide. Our simple silhouettes have significantly fewer edges than the original silhouette, while still preserving its appearance.