We describe a simple and practical algorithm for compact routing on connected random unit disk graphs. Using a recursive nested dissection of an n -vertex graph based on compact and balanced vertex separators, we construct routing tables with an average of O (log 2 n ) entries per vertex in a preprocessing step. The routing tables then support handshaking-based routing, where the handshaking can be implemented similarly to a DNS lookup. Our routing algorithm is guaranteed to deliver on the graph, while incurring moderate stretch. We describe a basic version of the algorithm that requires modifiable headers and a more advanced version that eliminates this need and incurs less stretch.

Geodesic distances between pairs of points on a 3D mesh surface are a crucial ingredient of many geometry processing tasks, but are notoriously difficult to compute efficiently on demand. We propose a novel method for the compact storage of geodesic distance information, which enables answering point-to-point geodesic distance queries very efficiently. For a triangle mesh with n vertices, if computing the geodesic distance to all vertices from a single source vertex costs O(f(n)) time, then we generate a database of size O(mnlogn) in O((f(n)+m3n)√n) time in a preprocessing stage, where m is a constant that depends on the geometric complexity of the surface. We achieve this by computing a nested bisection of the mesh surface using separator curves and storing compactly-described functions approximating the distances between each mesh vertex and a small relevant subset of these curves. Using this database, the geodesic distance between two mesh vertices can then be approximated well by solving a small number of simple univariate minimization problems in O(mlogn) worst case time and O(m) average case time. Our method provides an excellent tradeoff between the size of the database, query runtime, and accuracy of the result. It can be used to compress exact or approximate geodesic distances, e.g., those obtained by VTP (exact), fast DGG, fast marching, or the heat method (approximate) and is very efficient if f(n) = n, as for the fast DGG method.

Abstract We study the landmark distance function between two points in a simply connected planar polygon. We show that if the polygon vertices are used as landmarks, then the resulting landmark distance function to any given point in the polygon has a maximum principle and also does not contain local minima. The latter implies that a path between any two points in the polygon may be generated by steepest descent on this distance without getting “stuck” at a local minimum. Furthermore, if landmarks are increasingly added along polygon edges, the steepest descent path converges to the minimal geodesic path. Therefore, the landmark distance can be used, on the one hand in robotic navigation for routing autonomous agents along close‐to‐shortest paths and on the other for efficiently computing approximate geodesic distances between any two domain points, a property which may be useful in an extension of our work to surfaces in 3D. In the discrete setting, the steepest descent strategy becomes a greedy routing algorithm along the edges of a triangulation of the interior of the polygon, and our experiments indicate that this discrete landmark routing always delivers (i.e., does not get stuck) on “nice” triangulations.

In the age of real-time online traffic information and GPS-enabled devices, fastest-path computations between two points in a road network modeled as a directed graph, where each directed edge is weighted by a “travel time” value, are becoming a standard feature of many navigation-related applications. To support this, very efficient computation of these paths in very large road networks is critical. Fastest paths may be computed as minimal-cost paths in a weighted directed graph, but traditional minimal-cost path algorithms based on variants of the classical Dijkstra algorithm do not scale well, as in the worst case they may traverse the entire graph. A common improvement, which can dramatically reduce the number of graph vertices traversed, is the A* algorithm, which requires a good heuristic lower bound on the minimal cost. We introduce a simple, but very effective, heuristic function based on a small number of values assigned to each graph vertex. The values are based on graph separators and are computed efficiently in a preprocessing stage. We present experimental results demonstrating that our heuristic provides estimates of the minimal cost superior to those of other heuristics. Our experiments show that when used in the A* algorithm, this heuristic can reduce the number of vertices traversed by an order of magnitude compared to other heuristics.

Abstract Path generation is an important problem in many fields, especially robotics. One way to create a path between a source point z and a target point y inside a complex planar domain Ω is to define a non‐negative distance function d(y, z), such that following the negative gradient of d (by z) traces out such a path. This presents two challenges: (1) The mathematical challenge of defining d, such that d(y, z) has a single minimum at z = y for any fixed y, because the gradient‐descent path may otherwise terminate at a local minimum before reaching y; (2) The computational challenge of defining d, such that it can be computed efficiently. Using the concepts of harmonic measure and f‐divergence, we show how to assign a set of reduced coordinates to each point in Ω and to define a family of distance functions based on these coordinates, such that both the mathematical and the computational challenge are met. Since in practice, especially in robotics applications, the path is often restricted to follow the edges of a discrete network defined on a finite set of sites sampled from Ω, any method that works well in the continuous setting must be discretized appropriately to preserve the important properties of the continuous case. We show how to define a network connecting a finite set of sites, such that a greedy routing algorithm, which is the discrete equivalent of continuous gradient descent, based on our reduced coordinates is guaranteed to generate a path in the network between any two sites. In many cases, this network is close to a planar graph, especially if the set of sites is dense. Guaranteeing the existence of a greedy route between any two points in the graph is a significant advantage in practical applications, avoiding the complexity of other path‐planning methods, such as the shortest‐path and A* algorithms. While the paths generated by our algorithm are not the shortest possible, in practice we found that they are close to that.

Abstract Continuous conformal maps are typically approximated numerically using a triangle mesh which discretizes the plane. Computing a conformal map subject to user‐provided constraints then reduces to a sparse linear system, minimizing a quadratic ‘conformal energy’. We address the more general case of non‐triangular elements, and provide a complete analysis of the case where the plane is discretized using a mesh of regular polygons, e.g. equilateral triangles, squares and hexagons, whose interiors are mapped using barycentric coordinate functions. We demonstrate experimentally that faster convergence to continuous conformal maps may be obtained this way. We provide a formulation of the problem and its solution using complex number algebra, significantly simplifying the notation. We examine a number of common barycentric coordinate functions and demonstrate that superior approximation to harmonic coordinates of a polygon are achieved by the Moving Least Squares coordinates. We also provide a simple iterative algorithm to invert barycentric maps of regular polygon meshes, allowing to apply them in practical applications, e.g. for texture mapping.

Abstract Discrete conformal mappings of planar triangle meshes, also known as the As‐Similar‐As‐Possible (ASAP) mapping, involve the minimization of a quadratic energy function, thus are very easy to generate and are popular in image warping scenarios. We generalize this classical mapping to the case of quad meshes, taking into account the mapping of the interior of the quad, and analyze in detail the most common case ‐ the unit grid mesh. We show that the generalization, when combined with barycentric coordinate mappings between the source and target polygons, spawns an entire family of new mappings governed by quadratic energy functions, which allow to control quite precisely various effects of the mapping. This approach is quite general and applies also to arbitrary planar polygon meshes. As an application of generalized ASAP mappings of the unit grid mesh, we demonstrate how they can be used to warp digital photographs to achieve a variety of effects. One such effect is modifying the perspective of the camera that took a given photograph (without moving the camera). A related, but more challenging, effect is re‐photography ‐ warping a contemporary photograph in order to reproduce the camera view present in a vintage photograph of the same scene ‐ taken many years before with a different camera from a different viewpoint. We apply the generalized ASAP mapping to these images, discretized to a unit grid. Using a quad mesh (as opposed to a triangle mesh) permits biasing towards affine maps of the unit squares. This allows the introduction of an As‐Affine‐As‐Possible (AAAP) mapping for a good approximation of the homographies present in these warps, achieving quite accurate results. We demonstrate the advantages of the AAAP mapping on a variety of synthetic and real‐world examples.

Abstract Transfinite barycentric kernels are the continuous version of traditional barycentric coordinates and are used to define interpolants of values given on a smooth planar contour. When the data is two‐dimensional, i.e. the boundary of a planar map, these kernels may be conveniently expressed using complex number algebra, simplifying much of the notation and results. In this paper we develop some of the basic complex‐valued algebra needed to describe these planar maps, and use it to define similarity kernels, a natural alternative to the usual barycentric kernels. We develop the theory behind similarity kernels, explore their properties, and show that the transfinite versions of the popular three‐point barycentric coordinates (Laplace, mean value and Wachspress) have surprisingly simple similarity kernels. We furthermore show how similarity kernels may be used to invert injective transfinite barycentric mappings using an iterative algorithm which converges quite rapidly. This is useful for rendering images deformed by planar barycentric mappings.

In recent years, the As-Rigid-As-Possible (ARAP) shape deformation and shape interpolation techniques gained popularity, and the ARAP energy was successfully used in other applications as well. We improve the ARAP animation technique in two aspects. First, we introduce a new ARAP-type energy, named SR-ARAP, which has a consistent discretization for surfaces (triangle meshes). The quality of our new surface deformation scheme competes with the quality of the volumetric ARAP deformation (for tetrahedral meshes). Second, we propose a new ARAP shape interpolation method that is superior to prior art also based on the ARAP energy. This method is compatible with our new SR-ARAP energy, as well as with the ARAP volume energy.

Polyhedral meshes (PM)-meshes having planar faces-have enjoyed a rise in popularity in recent years due to their importance in architectural and industrial design. However, they are also notoriously difficult to generate and manipulate. Previous methods start with a smooth surface and then apply elaborate meshing schemes to create polyhedral meshes approximating the surface. In this paper, we describe a reverse approach: given the topology of a mesh, we explore the space of possible planar meshes having that topology. Our approach is based on a complete characterization of the maximal linear spaces of polyhedral meshes contained in the curved manifold of polyhedral meshes with a given topology. We show that these linear spaces can be described as nullspaces of differential operators, much like harmonic functions are nullspaces of the Laplacian operator. An analysis of this operator provides tools for global and local design of a polyhedral mesh, which fully expose the geometric possibilities and limitations of the given topology.

Abstract We present ArtiSketch – a system which allows the conversion of a wealth of existing 2D content into 3D content by users who do not necessarily possess artistic skills. Using ArtiSketch, a novice user may describe a 3D model as a set of articulated 2D sketches of a shape from different viewpoints. ArtiSketch then automatically converts the sketches to an articulated 3D object. Using common interactive tools, the user provides an initial estimate of the 3D skeleton pose for each frame, which ArtiSketch refines to be consistent between frames. This skeleton may then be manipulated independently to generate novel poses of the 3D model.

Abstract Constraining 3D meshes to restricted classes is necessary in architectural and industrial design, but it can be very challenging to manipulate meshes while staying within these classes. Specifically, polyhedral meshes—those having planar faces—are very important, but also notoriously difficult to generate and manipulate efficiently. We describe an interactive method for computing, optimizing and editing polyhedral meshes. Efficiency is achieved thanks to a numerical procedure combining an alternating least‐squares approach with the penalty method. This approach is generalized to manipulate other subsets of polyhedral meshes, as defined by a variety of other constraints.

We describe a snake-type method for shape registration in 2D and 3D, by fitting a given polygonal template to an acquired image or volume data. The snake aspires to fit itself to the data in a shape which is locally As-Similar-As-Possible (ASAP) to the template. Our ASAP regulating force is based on the Moving Least Squares (MLS) similarity deformation. Combining this force with the traditional internal and external forces associated with a snake leads to a powerful and robust registration algorithm, capable of extracting precise shape information from image data.

Abstract We describe a fast sampling algorithm for generating uniformly‐distributed point patterns with good blue noise characteristics. The method, based on constrained farthest point optimization, is provably optimal and may be easily parallelized, resulting in an algorithm whose performance/quality tradeoff is superior to other state‐of‐the‐art approaches.

Abstract Barycentric coordinates are an established mathematical tool in computer graphics and geometry processing, providing a convenient way of interpolating scalar or vector data from the boundary of a planar domain to its interior. Many different recipes for barycentric coordinates exist, some offering the convenience of a closed‐form expression, some providing other desirable properties at the expense of longer computation times. For example, harmonic coordinates, which are solutions to the Laplace equation, provide a long list of desirable properties (making them suitable for a wide range of applications), but lack a closed‐form expression. We derive a new type of barycentric coordinates based on solutions to the biharmonic equation. These coordinates can be considered a natural generalization of harmonic coordinates, with the additional ability to interpolate boundary derivative data. We provide an efficient and accurate way to numerically compute the biharmonic coordinates and demonstrate their advantages over existing schemes. We show that biharmonic coordinates are especially appealing for (but not limited to) 2D shape and image deformation and have clear advantages over existing deformation methods.

Effective communication using current video conferencing systems is severely hindered by the lack of eye contact caused by the disparity between the locations of the subject and the camera. While this problem has been partially solved for high-end expensive video conferencing systems, it has not been convincingly solved for consumer-level setups. We present a gaze correction approach based on a single Kinect sensor that preserves both the integrity and expressiveness of the face as well as the fidelity of the scene as a whole, producing nearly artifact-free imagery. Our method is suitable for mainstream home video conferencing: it uses inexpensive consumer hardware, achieves real-time performance and requires just a simple and short setup. Our approach is based on the observation that for our application it is sufficient to synthesize only the corrected face. Thus we render a gaze-corrected 3D model of the scene and, with the aid of a face tracker, transfer the gaze-corrected facial portion in a seamless manner onto the original image.

Abstract Barycentric coordinates are very popular for interpolating data values on polyhedral domains. It has been recently shown that expressing them as complex functions has various advantages when interpolating two‐dimensional data in the plane, and in particular for holomorphic maps. We extend and generalize these results by investigating the complex representation of real‐valued barycentric coordinates, when applied to planar domains. We show how the construction for generating real‐valued barycentric coordinates from a given weight function can be applied to generating complex‐valued coordinates, thus deriving complex expressions for the classical barycentric coordinates: Wachspress, mean value, and discrete harmonic. Furthermore, we show that a complex barycentric map admits the intuitive interpretation as a complex‐weighted combination of edge‐to‐edge similarity transformations, allowing the design of “home‐made” barycentric maps with desirable properties. Thus, using the tools of complex analysis, we provide a methodology for analyzing existing barycentric mappings, as well as designing new ones.

We present a new technique for passive and markerless facial performance capture based on anchor frames . Our method starts with high resolution per-frame geometry acquisition using state-of-the-art stereo reconstruction, and proceeds to establish a single triangle mesh that is propagated through the entire performance. Leveraging the fact that facial performances often contain repetitive subsequences, we identify anchor frames as those which contain similar facial expressions to a manually chosen reference expression. Anchor frames are automatically computed over one or even multiple performances. We introduce a robust image-space tracking method that computes pixel matches directly from the reference frame to all anchor frames, and thereby to the remaining frames in the sequence via sequential matching. This allows us to propagate one reconstructed frame to an entire sequence in parallel, in contrast to previous sequential methods. Our anchored reconstruction approach also limits tracker drift and robustly handles occlusions and motion blur. The parallel tracking and mesh propagation offer low computation times. Our technique will even automatically match anchor frames across different sequences captured on different occasions, propagating a single mesh to all performances.

We describe a simple algorithm to reconstruct the surface of smooth three-dimensional multilabeled objects from sampled planar cross-sections of arbitrary orientation. The algorithm has the unique ability to handle cross-sections in which regions are classified as being inside the object, outside the object, or unknown. This is achieved by constructing a scalar function on R 3 , whose zero set is the desired surface. The function is constructed independently inside every cell of the arrangement of the cross-section planes using transfinite interpolation techniques based on barycentric coordinates. These guarantee that the function is smooth, and its zero set interpolates the cross-sections. The algorithm is highly parallelizable and may be implemented as an incremental update as each new cross-section is introduced. This leads to an efficient online version, performed on a GPU, which is suitable for interactive medical applications.

Abstract We define a generalized distance function on an unoriented 3D point set and describe how it may be used to reconstruct a surface approximating these points. This distance function is shown to be a Mahalanobis distance in a higher‐dimensional embedding space of the points, and the resulting reconstruction algorithm a natural extension of the classical Radial Basis Function (RBF) approach. Experimental results show the superiority of our reconstruction algorithm to RBF and other methods in a variety of practical scenarios.

Studying the behavior of the heat diffusion process on a manifold is emerging as an important tool for analyzing the geometry of the manifold. Unfortunately, the high complexity of the computation of the heat kernel -- the key to the diffusion process - limits this type of analysis to 3D models of modest resolution. We show how to use the unique properties of the heat kernel of a discrete two dimensional manifold to overcome these limitations. Combining a multi-resolution approach with a novel approximation method for the heat kernel at short times results in an efficient and robust algorithm for computing the heat kernels of detailed models. We show experimentally that our method can achieve good approximations in a fraction of the time required by traditional algorithms. Finally, we demonstrate how these heat kernels can be used to improve a diffusion-based feature extraction algorithm.

Conformal maps are considered very desirable for planar deformation applications, since they allow only local rotations and scale, avoiding shear and other visually disturbing distortions of local detail. Conformal maps are also orientation-preserving C ∞ diffeomorphisms, meaning they are extremely smooth and prevent unacceptable "foldovers" in the plane. Unfortunately, these maps are also notoriously difficult to control, so working with them in an interactive animation scenario to achieve specific effects is a significant challenge, sometimes even impossible. We describe a novel 2D shape deformation system which generates conformal maps, yet provides the user a large degree of control over the result. For example, it allows discontinuities at user-specified boundary points, so true "bends" can be introduced into the deformation. It also allows the prescription of angular constraints at corners of the target image. Combining these provides for a very effective user experience. At the heart of our method is a very natural differential shape representation for conformal maps, using so-called "conformal factors" and "angular factors", which allow more intuitive control compared to representation in the usual spatial domain. Beyond deforming a given shape into a new one at each key frame, our method also provides the ability to interpolate between shapes in a very natural way, such that also the intermediate deformations are conformal. Our method is extremely efficient: it requires only the solution of a small dense linear system at preprocess time and a matrix-vector multiplication during runtime (which can be implemented on a modern GPU), thus the deformations, even on extremely large images, may be performed in real-time.

We present a novel approach to localization of sensors in a network given a subset of noisy inter-sensor distances. The algorithm is based on “stitching” together local structures by solving an optimization problem requiring the structures to fit together in an “As-Rigid-As-Possible” manner, hence the name ARAP. The local structures consist of reference “patches” and reference triangles, both obtained from inter-sensor distances. We elaborate on the relationship between the ARAP algorithm and other state-of-the-art algorithms, and provide experimental results demonstrating that ARAP is significantly less sensitive to sparse connectivity and measurement noise. We also show how ARAP may be distributed.

Abstract We present a general approach to shape deformation based on energy minimization, and applications of this approach to the problems of image resizing and 2D shape deformation. Our deformation energy generalizes that found in the prior art, while still admitting an efficient algorithm for its optimization. The key advantage of our energy function is the flexibility with which the set of “legal transformations” may be expressed; these transformations are the ones which are not considered to be distorting. This flexibility allows us to pose the problems of image resizing and 2D shape deformation in a natural way and generate minimally distorted results. It also allows us to strongly reduce undesirable foldovers or self‐intersections. Results of both algorithms demonstrate the effectiveness of our approach.

Barycentric coordinates are heavily used in computer graphics applications to generalize a set of given data values. Traditionally, the coordinates are required to satisfy a number of key properties, the first being that they are real and positive. In this paper we relax this requirement, allowing the barycentric coordinates to be complex numbers. This allows us to generate new families of barycentric coordinates, which have some powerful advantages over traditional ones. Applying complex barycentric coordinates to data which is itself complex-valued allows to manipulate functions from the complex plane to itself, which may be interpreted as planar mappings. These mappings are useful in shape and image deformation applications. We use Cauchy’s theorem from complex analysis to construct complex barycentric coordinates on (not necessarily convex) polygons, which are shown to be equivalent to planar Green coordinates. These generate conformal mappings from a given source region to a given target region, such that the image of the source region is close to the target region. We then show how to improve the Green coordinates in two ways. The first provides a much better fit to the polygonal target region, and the second allows to generate deformations based on positional constraints, which provide a more intuitive user interface than the conventional cage-based approach. These define two new types of complex barycentric coordinates, which are shown to be very effective in interactive deformation and animation scenarios.

A space deformation is a mapping from a source region to a target region within Euclidean space, which best satisfies some userspecified constraints. It can be used to deform shapes embedded in the ambient space and represented in various forms -- polygon meshes, point clouds or volumetric data. For a space deformation method to be useful, it should possess some natural properties: e.g. detail preservation, smoothness and intuitive control. A harmonic map from a domain ω ⊂ R d to R d is a mapping whose d components are harmonic functions. Harmonic mappings are smooth and regular, and if their components are coupled in some special way, the mapping can be detail-preserving, making it a natural choice for space deformation applications. The challenge is to find a harmonic mapping of the domain, which will satisfy constraints specified by the user, yet also be detail-preserving, and intuitive to control. We generate harmonic mappings as a linear combination of a set of harmonic basis functions, which have a closed-form expression when the source region boundary is piecewise linear. This is done by defining an energy functional of the mapping, and minimizing it within the linear span of these basis functions. The resulting mapping is harmonic, and a natural "As-Rigid-As-Possible" deformation of the source region. Unlike other space deformation methods, our approach does not require an explicit discretization of the domain. It is shown to be much more efficient, yet generate comparable deformations to state-of-the-art methods. We describe an optimization algorithm to minimize the deformation energy, which is robust, provably convergent, and easy to implement.

Abstract We present an efficient method to conformally parameterize 3D mesh data sets to the plane. The idea behind our method is to concentrate all the 3D curvature at a small number of select mesh vertices, called cone singularities, and then cut the mesh through those singular vertices to obtain disk topology. The singular vertices are chosen automatically. As opposed to most previous methods, our flattening process involves only the solution of linear systems of Poisson equations, thus is very efficient. Our method is shown to be faster than existing methods, yet generates parameterizations having comparable quasi‐conformal distortion.

Abstract Depth and visual hulls are useful for quick reconstruction and rendering of a 3D object based on a number of reference views. However, for many scenes, especially multi‐object, these hulls may contain significant artifacts known as phantom geometry. In depth hulls the phantom geometry appears behind the scene objects in regions occluded from all the reference views. In visual hulls the phantom geometry may also appear in front of the objects because there is not enough information to unambiguously imply the object positions. In this work we identify which parts of the depth and visual hull might constitute phantom geometry. We define the notion of reduced depth hull and reduced visual hull as the parts of the corresponding hull that are phantom‐free. We analyze the role of the depth information in identification of the phantom geometry. Based on this, we provide an algorithm for rendering the reduced depth hull at interactive frame‐rates and suggest an approach for rendering the reduced visual hull. The rendering algorithms take advantage of modern GPU programming techniques. Our techniques bypass explicit reconstruction of the hulls, rendering the reduced depth or visual hull directly from the reference views.

Abstract We present a technique for steganography in polygonal meshes. Our method hides a message in the indexed rep‐resentation of a mesh by permuting the order in which faces and vertices are stored. The permutation is relative to a reference ordering that encoder and decoder derive from the mesh connectivity in a consistent manner. Our method is distortion‐free because it does not modify the geometry of the mesh. Compared to previous steganographic methods for polygonal meshes our capacity is up to an order of magnitude better. Our steganography algorithm is universal and can be used instead of the standard permutation steganography algorithm on arbitrary datasets. The standard algorithm runs in Ω (n2 log2 n log log n) time and achieves optimal O(nlog n) bit capacity on datasets with n elements. In contrast, our algorithm runs in O(n) time, achieves a capacity that is only one bit per element less than optimal, and is extremely simple to implement.

Abstract We present a novel approach to parameterize a mesh with disk topology to the plane in a shape‐preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global “stitch” operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as‐similar‐as‐possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as‐rigid‐as‐possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre‐factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape‐preserving results than other state‐of‐the‐art approaches. We present also a more general “hybrid” parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.

Abstract We present an algorithm for acquiring the 3D surface geometry and motion of a dynamic piecewise‐rigid object using a single depth video camera. The algorithm identifies and tracks the rigid components in each frame, while accumulating the geometric information acquired over time, possibly from different viewpoints. The algorithm also reconstructs the dynamic skeleton of the object, thus can be used for markerless motion capture. The acquired model can then be animated to novel poses. We show the results of the algorithm applied to synthetic and real depth video.

Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol -- one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol based on the "virtual" coordinates of the nodes derived from the embedding.

We introduce an algorithm for approximating a 2-manifold 3D mesh by a set of developable surfaces. Each developable surface is a generalized cylinder represented as a strip of triangles not necessarily taken from the original mesh. Our algorithm is automatic, creates easy-to-assemble pieces, and provides L_\alpha global error bounds. The approximation quality is controlled by a user-supplied parameter specifying the allowed Hausdorff distance between the input mesh and its piecewise-developable approximation. The strips generated by our algorithm may be parameterized to conform with the parameterization of the original mesh, if given, to facilitate texture mapping. We demonstrate this by physically assembling papercraft models from the strips generated by our algorithm when run on several polygonal 3D mesh data sets.

Abstract We describe a system for the animation of a skeleton‐controlled articulated object that preserves the fine geometric details of the object skin and conforms to the characteristic shapes of the object specified through a set of examples. The system provides the animator with an intuitive user interface and produces compelling results even when presented with a very small set of examples. In addition it is able to generalize well by extrapolating far beyond the examples.

Geometric meshes consist of a set of points in 3D space connected in a (typically manifold) graph structure. As such a vector of 3n real values may represent them, where n is the number of vertices in the mesh. Unfortunately, although straightforward, this is not a very useful representation of the mesh, as it is difficult to naturally manipulate the mesh data using this representation. A better representation would capture the spatial correlation between vertices, be invariant to a class of natural transformations, not be too redundant, and be efficiently invertible. Recent years have seen the development of a variety of mesh representation schemes, intended primarily for mesh editing applications. The author surveys some of these representation schemes, discuss the pros and cons, and demonstrate how the may be used to edit, animate and morph mesh datasets.

Linear parameterization of 3D meshes with disk topology is usually performed using the method of barycentrie coordinates pioneered by Tutte and Floater. This imposes a convex boundary on the parameterization, which can significantly distort the result. Recently, several methods showed how to relax the convex boundary requirement while still using the barycentric coordinates formulation. However, this relaxation can result in other artifacts in the parameterization. In this paper we explore these methods and give a general recipe for "natural" boundary conditions for the family of so-called "three point" barycentric coordinates. We discuss the shortcomings of these methods and show how they may be rectified using an iterative scheme or a carefully crafted "virtual boundary". Finally, we show how these methods adapt easily to solve the problem of constrained parameterization.

Gotsman et al. (SIGGRAPH 2003) presented the first method to generate a provably bijective parameterization of a closed genus-0 manifold mesh to the unit sphere. This involves the solution of a large system of non-linear equations. However, they did not show how to solve these equations efficiently, so, while theoretically sound, the method has remained impractical till now. We show why simple iterative methods to solve the equations are bound to fail, and provide an efficient numerical scheme that succeeds. Our method uses a number of optimization methods combined with an algebraic multigrid technique. With these, we are able to spherically parameterize meshes containing up to a hundred thousand vertices in a matter of minutes.

Spectral compression of the geometry of triangle meshes achieves good results in practice, but there has been little or no theoretical support for the optimality of this compression. We show that, for certain classes of geometric mesh models, spectral decomposition using the eigenvectors of the symmetric Laplacian of the connectivity graph is equivalent to principal component analysis on that class, when equipped with a natural probability distribution. Our proof treats connected one-and two-dimensional meshes with fixed convex boundaries, and is based on an asymptotic approximation of the probability distribution in the two-dimensional case. The key component of the proof is that the Laplacian is identical, up to a constant factor, to the inverse covariance matrix of the distribution of valid mesh geometries. Hence, spectral compression is optimal, in the mean square error sense, for these classes of meshes under some natural assumptions on their distribution.

The ability to position a small subset of mesh vertices and produce a meaningful overall deformation of the entire mesh is a fundamental task in mesh editing and animation. However, the class of meaningful deformations varies from mesh to mesh and depends on mesh kinematics, which prescribes valid mesh configurations, and a selection mechanism for choosing among them. Drawing an analogy to the traditional use of skeleton-based inverse kinematics for posing skeletons. we define mesh-based inverse kinematics as the problem of finding meaningful mesh deformations that meet specified vertex constraints.Our solution relies on example meshes to indicate the class of meaningful deformations. Each example is represented with a feature vector of deformation gradients that capture the affine transformations which individual triangles undergo relative to a reference pose. To pose a mesh, our algorithm efficiently searches among all meshes with specified vertex positions to find the one that is closest to some pose in a nonlinear span of the example feature vectors. Since the search is not restricted to the span of example shapes, this produces compelling deformations even when the constraints require poses that are different from those observed in the examples. Furthermore, because the span is formed by a nonlinear blend of the example feature vectors, the blending component of our system may also be used independently to pose meshes by specifying blending weights or to compute multi-way morph sequences.

Partitioning is a fundamental operation on graphs. In this paper we briefly review the basic concepts of graph partitioning and its relationship to digital mesh processing. We also elaborate on the connection between graph partitioning and spectral graph theory. Applications in computer graphics are described.

Abstract We show that the average entropy of the distribution of valences in valence sequences for the class of manifold 3D triangle meshes and the class of manifold 3D polygon meshes is strictly less than the entropy of these classes themselves. This implies that, apart from a valence sequence, another essential piece of information is needed for valence‐based connectivity coding of manifold 3D meshes. Since there is no upper bound on the size of this extra piece of information, the result implies that the question of optimality of valence‐based connectivity coding is still open.

Parameterization of 3D mesh data is important for many graphics applications, in particular for texture mapping, remeshing and morphing. Closed manifold genus-0 meshes are topologically equivalent to a sphere, hence this is the natural parameter domain for them. Parameterizing a triangle mesh onto the sphere means assigning a 3D position on the unit sphere to each of the mesh vertices, such that the spherical triangles induced by the mesh connectivity are not too distorted and do not overlap. Satisfying the non-overlapping requirement is the most difficult and critical component of this process. We describe a generalization of the method of barycentric coordinates for planar parameterization which solves the spherical parameterization problem, prove its correctness by establishing a connection to spectral graph theory and show how to compute these parameterizations.

Texture mapping enhances the visual realism of 3D models by adding fine details. To achieve the best results, it is often necessary to force a correspondence between some of the details of the texture and the features of the model.The most common method for mapping texture onto 3D meshes is to use a planar parameterization of the mesh. This, however, does not reflect any special correspondence between the mesh geometry and the texture. The Matchmaker algorithm presented here forces user-defined feature correspondence for planar parameterization of meshes. This is achieved by adding positional constraints to the planar parameterization. Matchmaker allows users to introduce scores of constraints while maintaining a valid one-to-one mapping between the embedding and the 3D surface. Matchmaker 's constraint mechanism can be used for other applications requiring parameterization besides texture mapping, such as morphing and remeshing. Matchmaker begins with an unconstrained planar embedding of the 3D mesh generated by conventional methods. It moves the constrained vertices to the required positions by matching a triangulation of these positions to a triangulation of the planar mesh formed by paths between constrained vertices. The matching triangulations are used to generate a new parameterization that satisfies the constraints while minimizing the deviation from the original 3D geometry.

This video describes a simple automatic method for visually tracking activity on a 3D mesh surface. Such a method is useful in interactive algorithm visualization. Its operation is demonstrated on a sample visualization of Rossignac's Edgebreaker connectivity compression algorithm.

We present a method to code the multiresolution structure of a 3D triangle mesh in a manner that allows progressive decoding and efficient rendering at a client machine. The code is based on a special ordering of the mesh vertices which has good locality and continuity properties, inducing a natural multiresolution structure. This ordering also incorporates information allowing efficient rendering of the mesh at all resolutions using the contemporary vertex buffer mechanism. The performance of our code is shown to be competitive with existing progressive mesh compression methods, while achieving superior rendering speed.

We present methods to generate rendering sequences for triangle meshes which preserve mesh locality as much as possible. This is useful for maximizing vertex reuse when rendering the mesh using a FIFO vertex buffer, such as those available in modern 3D graphics hardware. The sequences are universal in the sense that they perform well for all sizes of vertex buffers, and generalize to progressive meshes. This has been verified experimentally.

In this video we introduce a 3D shape representation that is based sol ely on mesh connectivity -- the {\em connectivity shape}. Given a connectivity, we define its natural geometry as a smooth embedding in space with uniform edge lengths and describe efficient techniques to compute it. Furthermore, we show how to generate connectivity shapes that approximate given shapes. The details will soon be published in form of a full paper.

A "stick figure" is a connected straight-line plane graph, sometimes called a "skeleton". Compatible stick figures are those with the same topological structure. We present a method for naturally morphing between two compatible stick figures in a manner that preserves compatibility throughout the morph. In particular, this guarantees that the intermediate shapes are also stick figures (e.g. they do not self-intersect). Our method generalizes existing algorithms for morphing compatible planar polygons using Steiner vertices, and improves the complexity of those algorithms by reducing the number of Steiner vertices used.

We describe a method to visualize the connectivity graph of a mesh using a natural embedding in 3D space. This uses a 3D shape representation that is based solely on mesh connectivity: the connectivity shape. Given a connectivity, we define its natural geometry as a smooth embedding in space with uniform edge lengths and describe efficient techniques to compute it. Our main contribution is to demonstrate that a surprising amount of geometric information is implicit in the connectivity. We also show how to generate connectivity shapes that approximate given 3D shapes. Potential applications of connectivity shapes to modeling and mesh coding are described.

We show how to continuously map a texture onto a 3D triangle mesh when some of the mesh vertices are constrained to have given (u, v) coordinates. This problem arises frequently in interactive texture mapping applications and, to the best of our knowledge, a complete and efficient solution is not available. Our techniques always guarantee a solution by introducing extra (Steiner) vertices in the triangulation if needed. We show how to apply our methods to texture mapping in multi-resolution scenarios and image warping and morphing.

This paper offers a novel detection method, which works well even in the case of a complicated image collection. It can also be applied to detect 3D objects under different views. The detection problem is solved by sequentially applying very simple filters (or detectors), which are designed to yield small results on the multitemplate (hence antifaces), and large results on "random" natural images. This is achieved by making use of a simple probabilistic assumption on the distribution of natural images, which is borne out well in practice. Only images which passed the threshold test imposed by the first detector are examined by the second detector, etc. The detectors are designed to act independently so that their false alarms are uncorrelated; this results in a false alarm rate which decreases exponentially in the number of detectors. The algorithm's performance compares favorably to the well-known eigenface and support vector machine based algorithms, but is substantially faster.

Two planar triangulations with a correspondence between the pair of vertex sets are compatible ( isomorphic ) if they are topologically equivalent. This work describes methods for morphing compatible planar triangulations with identical convex boundaries in a manner that guarantees compatibility throughout the morph. These methods are based on a fundamental representation of a planar triangulation as a matrix that unambiguously describes the triangulation. Morphing the triangulations corresponds to interpolations between these matrices.We show that this basic approach can be extended to obtain better control over the morph, resulting in valid morphs with various natural properties. Two schemes, which generate the linear trajectory morph if it is valid, or a morph with trajectories close to linear otherwise, are presented. An efficient method for verification of validity of the linear trajectory morph between two triangulations is proposed. We also demonstrate how to obtain a morph with a natural evolution of triangle areas and how to find a smooth morph through a given intermediate triangulation.

Describes an efficient algorithm for coding the connectivity information of general polygon meshes. In contrast to most existing algorithms, which are suitable only for triangular meshes and pay a penalty for the treatment of non-triangular faces, this algorithm codes the connectivity information in a direct manner. Our treatment of the special case of triangular meshes is shown to be equivalent to the Edgebreaker algorithm. Using our methods, any triangle mesh may be coded in no more than two bits/triangle (approximately four bits/vertex), a quadrilateral mesh in no more than 3.5 bits/quad (approximately 3.5 bits/vertex), and the most common case of a quadrilateral mesh with few triangles in no more than four bits/polygon.

Recently, a wealth of algorithms for the efficient coding of 3D triangle meshes have been published. All these focus on achieving the most compact code for the connectivity data. The geometric data, i.e. the vertex coordinates, are then coded in an order induced by the connectivity code, which is probably not optimal. This is a pity, as the geometric portion of the data set dominates the code. We propose a way to optimize the geometry code without sacrificing too much in the connectivity code. In our approach, we achieve approximately two bits/triangle for the connectivity before entropy coding, which is not as good as other published algorithms but certainly not significantly worse. Our approach is based on the parallelogram prediction method for mesh geometry. This method is based on the observation that two adjacent triangles in a typical mesh tend to form a shape similar to a parallelogram. If an algorithm uses a parallelogram prediction method then it should build a traversal structure of triangles covering all vertices. The vertex coordinates are then predicted as the structure is traversed. The cost of this code is then the entropy of the distribution of the vertex prediction errors. Since this entropy is hard to manipulate, the accepted practice is to measure the code's effectiveness in the approximation sense, i.e. as the sum of the lengths of the vertex prediction error vectors. The full version of this paper is available at.

We show how spectral methods may be applied to 3D mesh data to obtain compact representations. This is achieved by projecting the mesh geometry onto an orthonormal basis derived from the mesh topology. To reduce complexity, the mesh is partitioned into a number of balanced submeshes with minimal interaction, each of which are compressed independently. Our methods may be used for compression and progressive transmission of 3D content, and are shown to be vastly superior to existing methods using spatial techniques, if slight loss can be tolerated.

Article Free Access Share on Geometric algorithms for message filtering in decentralized virtual environments Authors: Yohai Makbily Computer Science Dept., Technion - Israel Institute of Technology, Haifa 32000, Israel Computer Science Dept., Technion - Israel Institute of Technology, Haifa 32000, IsraelView Profile , Craig Gotsman Virtue Ltd., P.O. Box 199, Tirat Carmel 30200, Israel Virtue Ltd., P.O. Box 199, Tirat Carmel 30200, IsraelView Profile , Reuven Bar-Yehuda Computer Science Dept., Technion - Israel Institute of Technology, Haifa 32000, Israel Computer Science Dept., Technion - Israel Institute of Technology, Haifa 32000, IsraelView Profile Authors Info & Claims I3D '99: Proceedings of the 1999 symposium on Interactive 3D graphicsApril 1999 Pages 39–46https://doi.org/10.1145/300523.300527Published:26 April 1999Publication History 15citation334DownloadsMetricsTotal Citations15Total Downloads334Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Inspired by the drawings of “impossible” objects by artists such as M.C. Escher, we describe a mathematical theory which captures some of the underlying principles of their work. Using this theory, we show how impossible three‐dimensional scenes may be modeled and rendered synthetically.

A problem which often arises while fitting implicit polynomials to 2D and 3D data sets is the following: although the data set is simple, the fit exhibits undesired phenomena, such as loops, holes, extraneous components, etc. Previous work tackled these problems by optimizing heuristic cost functions, which penalize some of these topological problems in the fit. The paper suggests a different approach-to design parameterized families of polynomials whose zero-sets are guaranteed to satisfy certain topological properties. Namely, we construct families of polynomials with star-shaped zero-sets, as well as polynomials whose zero-sets are guaranteed not to intersect an ellipse circumscribing the data or to be entirely contained in such an ellipse. This is more rigorous than using heuristics which may fail and result in pathological zero-sets. The ability to parameterize these families depends heavily on the ability to parameterize positive polynomials. To achieve this, we use some powerful results from real algebraic geometry.

All image warping algorithms to date are image-independent, namely, relate only to the geometry of the image plane, ignoring the content of the image. We show that taking the image content into account yields elaborate warping schemes which may be used to enhance, sharpen and scale images. Sharpening the image is achieved by "squashing" the pixels in edge areas, and "stretching" the pixels in flat areas. Since image pixels are only moved, not modified, some drawbacks of classical linear filtering methods are avoided. We also lay the mathematical foundation for the use of an image-dependent warping scheme in traditional warping applications, such as distortion minimization.

Large, complex 3D scenes are best rendered in an output-sensitive way, i.e., in time largely independent of the entire scene model's complexity. Occlusion culling is one of the key techniques for output-sensitive rendering. We generalize existing occlusion culling algorithms, intended for static scenes, to handle dynamic scenes having numerous moving objects. The data structure used by an occlusion culling method is updated to reflect the objects' possible positions. To avoid updating the structure for every dynamic object at each frame, a temporal bounding volume (TBV) is created for each occluded dynamic object, using some known constraints on the object's motion. The TBV is inserted into the structure instead of the object. Subsequently, the object is ignored as long as the TBV is occluded and guaranteed to contain the object. The generalized algorithms' rendering time is linearly affected only by the scene's visible parts, not by hidden parts or by occluded dynamic objects. Our techniques also save communications in distributed graphic systems, e.g., multiuser virtual environments, by eliminating update messages for hidden dynamic objects. We demonstrate the adaptation of two occlusion culling algorithms to dynamic scenes: hierarchical Z-buffering and BSP tree projection.

The authors describe a software system supporting interactive visualization of large terrains in a resource-limited environment, i.e. a low-end client computer accessing a large terrain database server through a low-bandwidth network. By "large", they mean that the size of the terrain database is orders of magnitude larger than the computer RAM. Superior performance is achieved by manipulating both geometric and texture data at a continuum of resolutions, and, at any given moment, using the best resolution dictated by the CPU and bandwidth constraints. The geometry is maintained as a Delaunay triangulation of a dynamic subset of the terrain data points, and the texture compressed by a progressive wavelet scheme. A careful blend of algorithmic techniques enables the system to achieve superior rendering performance on a low-end computer by optimizing the number of polygons and texture pixels sent to the graphics pipeline. It guarantees a frame rate depending only on the size and quality of the rendered image, independent of the viewing parameters and scene database size. An efficient paging scheme minimizes data I/O, thus enabling the use of the system in a low-bandwidth client/server data-streaming scenario, such as on the Internet.

The efficient rendering of large dynamic scenes is an important open problem.Optimization techniques for static scenes, such as output-sensitive visibility calculation, must be carefully adapted to dynamic models in order to remain effective.Distributed virtual environments pose a particular difficulty, because communication between the users must be minimized in addition to each user's rendering time, We show how output-sensitive visibility calculation algorithms can be adapted to dynamic scenes, and used to reduce the communication requirements between workstations in a distributed virtual environment.The solution is based on temporal bounding volumes, guaranteed to contain the dynamic objects for some period of time.These volumes are inserted into a visibility algorithm's main data structure instead of hidden dynamic objects.Subsequently a dynamic object is ignored until its bounding volume becomes visible or is no longer guaranteed to contain the object.In a distributed virtual environment, this saves not only the rendering of the object, but its update through a communication network too.We show an algorithm which combines this method with BSP tree based output-sensitive visibility calculation, and report on the implementation of our system.

A dynamic task allocation algorithm for ray‐tracing by progressive refinement on a distributed‐memory parallel computer is described. Parallelization of progressive ray‐tracing is difficult because of the inherent sequential nature of the sample location generation process, which is optimized (and different) for any given image. We report on experimental results obtained from our implementation of this algorithm on a Meiko parallel computer. The three performance measures of the algorithm, namely, load‐balance, speedup, and image quality, are shown to be good.

Abstract An output‐sensitive visibility algorithm is one whose runtime is proportional to the number of visible graphic primitives in a scene model—not to the total number of primitives, which can be much greater. The known practical output‐sensitive visibility algorithms are suitable only for static scenes, because they include a heavy preprocessing stage that constructs a spatial data structure which relies on the model objects’ positions. Any changes to the scene geometry might cause significant modifications to this data structure. We show how these algorithms may be adapted to dynamic scenes. Two main ideas are used: first, update the spatial data structure to reflect the dynamic objects’ current positions; make this update efficient by restricting it to a small part of the data structure. Second, use temporal bounding volumes (TBVs) to avoid having to consider every dynamic object in each frame. The combination of these techniques yields efficient, output‐sensitive visibility algorithms for scenes with multiple dynamic objects. The performance of our methods is shown to be significantly better than previous output‐sensitive algorithms, intended for static scenes. TBVs can be adapted to applications where no prior knowledge of the objects’ trajectories is available, such as virtual reality (VR), simulations etc. Furthermore, they save updates of the scene model itself; notjust of the auxiliary data structure used by the visibility algorithm. They can therefore be used to greatly reduce the communications overhead in client‐server VR systems, as well as in general distributed virtual environments.

A space-filling curve is a linear traversal of a discrete finite multidimensional space. In order for this traversal to be useful in many applications, the curve should preserve "locality". We quantify "locality" and bound the locality of multidimensional space-filling curves. Classic Hilbert space-filling curves come close to achieving optimal locality.

We investigate architechural schemes, generalizing that of existing graphics engines, supporting fast rendering of traingle meshes. A mesh defined on n vertices is rendered by sending vertices down a graphics pipeline, after which they are pushed on a stack to by popped when no longer needed. Only individual traingles whose vertices are present in the stack may be rendered. The storage cost of the mesh rendering is the size of the stack required to store mesh vertices during the rendering process. This may be significantly less than n . The time cost of the mesh rendering is the number of vertices sent down the graphics pipeline. If a large enough stack is available, it usuffices to send each vertix once. If only a small stack is available, some vertices may have to be sent more than once, so a time/space tradeoff exists. With our architecture, stack of size O(√n) is sufficient to render any triangle mesh defined on n vertices, such that each vertex is sent only once through the graphics pipeline (time cost = n ). We provide an algorithm that generates an appropriate “rendering sequence” of commands for any given mesh. Moreover, we show that no algorithm can do better, that is, Ω(√n) is a lower bound. Some n -vertex meshes may be rendered using a stack whose size is significantly less than O(√n). An algorithm generating a minimum-time rendering sequence rquiring the minimum stack size is an open question. We provide an approximation: if it is theoretically possible to render a triangle mesh is minimum time with a stack of size S , our algoithm generates a minimum-time rendering sequence requiring a stack of size no larger than 2 S log 3/2 n . If only a stack of size k is available, we provide an algorithm generating a rendering sequence requiring a stack of size no larger than k , such that at most n(1+c/k) vertices must be sent through the pipeline, for some constant c .

We present an efficient algorithm for dynamic adaptive color quantization of 24 bit image (video) sequences, important in multimedia applications. Besides producing hi fidelity 8 bit imagery, our algorithm runs with minimal computational cost and the generated colormaps are robust to small differences in consecutive images. Apart from the two standard color quantization tasks, colormap design and quantizer mapping, our algorithm includes colormap filling-an operation unique to dynamic color quantization. This task solves the problem of screen flicker, a serious problem in dynamic quantization of image sequences, resulting from rapid changes in display of colormaps. Our solution is based on two ideas: including in the current colormap a small set of color representatives from the previous image; assigning representatives to the colormap entries in an order that reduces the difference between contents of equal entries in consecutive colormaps. Our algorithm runs in near real time on medium range workstations.>

Discrete space-filling curves are commonly used to reduce a multidimensional problem to a one-dimensional problem, and, as such, are exploited in a variety of image processing applications. The space-filling curve is essentially a linear traversal of the discrete multidimensional space. In order that this traversal be effective, the curve should preserve "locality", namely, that points close in the original multidimensional space be close in their ordering along the curve, and vice versa. We quantify "locality" and provide upper and lower bounds on the locality of multidimensional space-filling curves. We also bound the locality of the classic Hilbert space-filling curves, showing that they come close to achieving optimal locality.

We consider the problem of approximating a smooth surface f(x, y), based on n scattered samples {(x/sub i/, y/sub i/, z/sub i/)/sub i=1//sup n/} where the sample values {z/sub i/} are contaminated with noise: z/sub i/=f(x/sub i/, y/sub i/)=/spl epsiv//sub i/. We present an algorithm that generates a PLS (piecewise linear surface) f', defined on a triangulation of the sample locations V={(x/sub i/, y/sub i/)/sub i=1//sup n/}, approximating f well. Constructing the PLS involves specifying both the triangulation of V and the values of f' at the points of V. We demonstrate that even when the sampling process is not noisy, a better approximation for f is obtained using our algorithm, compared to existing methods. This algorithm is useful for DTM (digital terrain map) manipulation by polygon-based graphics engines for visualization applications.>

Let f: (+1,-1)/sup n/ to R be a read function on the n-dimensional hypercube such that f=g(H), where g is monotonic and h is a linear combination of Walsh functions of degreed.>