The restricted Delaunay triangulation of a closed surface Σ and a finite point set V ⊂ Σ is a subcomplex of the Delaunay tetrahedralization of V whose triangles approximate Σ. It is well known that if V is a sufficiently dense sample of a smooth Σ, then the union of the restricted Delaunay triangles is homeomorphic to Σ. We show that an ε-sample with ε ≤ 0.3245 suffices. By comparison, Dey proves it for a 0.18-sample; our improved sampling bound reduces the number of sample points required by a factor of 3.25. More importantly, we improve a related sampling bound of Cheng et al. for Delaunay surface meshing, reducing the number of sample points required by a factor of 21. The first step of our homeomorphism proof is particularly interesting: we show that for a 0.44-sample, the restricted Voronoi cell of each site v ∈ V is homeomorphic to a disk, and the orthogonal projection of the cell onto T_vΣ (the plane tangent to Σ at v) is star-shaped.

A linear neural network computes a linear transformation of its input vector. Given a fully-connected linear network, the set of all weight vectors for which the network computes the same linear transformation is an algebraic variety in weight space, called a fiber under the matrix multiplication map. Sometimes this variety is a manifold, but usually not. The rank stratification of a fiber is a natural partition of the fiber into manifolds of various dimensions called strata. We characterize how these strata are connected to each other. They satisfy the frontier condition: if a stratum intersects the closure of another stratum, then the former stratum is a subset of the closure of the latter stratum. This subset relationship can be expressed as a partial order with a single minimal element. Our main result describes the relationship between this partial order and the ranks of certain matrices in the network. Each stratum represents a different pattern of information flow through the network, expressed as a barcode. Connections among the strata are best understood through simple transformations of the barcodes called barcode moves.

We introduce the restricted constrained Delaunay triangulation (restricted CDT), a generalization of both the restricted Delaunay triangulation and the constrained Delaunay triangulation. The restricted CDT is a triangulation of a surface whose edges include a set of user-specified constraining segments. We define the restricted CDT to be the dual of a restricted Voronoi diagram defined on a surface that we have extended by topological surgery. We prove several properties of restricted CDTs, including sampling conditions under which the restricted CDT contains every constraining segment and is homeomorphic to the underlying surface.

Abstract QuadriFlow is a scalable algorithm for generating quadrilateral surface meshes based on the Instant Field‐Aligned Meshes of Jakob et al. (ACM Trans. Graph. 34(6):189, 2015). We modify the original algorithm such that it efficiently produces meshes with many fewer singularities. Singularities in quadrilateral meshes cause problems for many applications, including parametrization and rendering with Catmull‐Clark subdivision surfaces. Singularities can rarely be entirely eliminated, but it is possible to keep their number small. Local optimization algorithms usually produce meshes with many singularities, whereas the best algorithms tend to require non‐local optimization, and therefore are slow. We propose an efficient method to minimize singularities by combining the Instant Meshes objective with a system of linear and quadratic constraints. These constraints are enforced by solving a global minimum‐cost network flow problem and local boolean satisfiability problems. We have verified the robustness and efficiency of our method on a subset of ShapeNet comprising 17,791 3D objects in the wild. Our evaluation shows that the quality of the quadrangulations generated by our method is as good as, if not better than, those from other methods, achieving about four times fewer singularities than Instant Meshes. Other algorithms that produce similarly few singularities are much slower; we take less than ten seconds to process each model. Our source code is publicly available.

The restricted Delaunay triangulation can be conceived as an operator that takes as input a k-manifold (typically smooth) embedded in R^d and a set of points sampled with sufficient density on that manifold, and produces as output a k-dimensional triangulation of the manifold, the input points serving as its vertices. What happens if we feed that triangulation back into the operator, replacing the original manifold, while retaining the same set of input points? If k = 2 and the sample points are sufficiently dense, we obtain another triangulation of the manifold. Iterating this process, we soon reach an iteration for which the input and output triangulations are the same. We call this triangulation a fixed point of the restricted Delaunay triangulation operator. With this observation, and a new test for distinguishing "critical points" near the manifold from those near its medial axis, we develop a provably good surface reconstruction algorithm for R^3 with unusually modest sampling requirements. We develop a similar algorithm for constructing a simplicial complex that models a 2-manifold embedded in a high-dimensional space R^d, also with modest sampling requirements (especially compared to algorithms that depend on sliver exudation). The latter algorithm builds a non-manifold representation similar to the flow complex, but made solely of Delaunay simplices. The algorithm avoids the curse of dimensionality: its running time is polynomial, not exponential, in d.

Most algorithms for guaranteed-quality tetrahedral mesh generation create Delaunay meshes. Delaunay triangulations have many good properties, but the requirement that all tetrahedra be Delaunay often forces mesh generators to overrefine where boundary polygons meet at small angles---that is, they produce too many tetrahedra, making them too small. Relaxing the Delaunay property makes it possible both to reduce overrefinement and to obtain higher-quality tetrahedra.

The most commonly implemented method of constructing a constrained Delaunay triangulation (CDT) in the plane is to first construct a Delaunay triangulation, then incrementally insert the input segments one by one. For typical implementations of segment insertion, this method has a Θ(kn2) worst-case running time, where n is the number of input vertices and k is the number of input segments. We give a randomized algorithm for inserting a segment into a CDT in expected time linear in the number of edges the segment crosses, and demonstrate with a performance comparison that it is faster than gift-wrapping for segments that cross many edges. A result of Agarwal, Arge, and Yi implies that randomized incremental construction of CDTs by our segment insertion algorithm takes expected O(n log n + n log2 k) time. We show that this bound is tight by deriving a matching lower bound. Although there are CDT construction algorithms guaranteed to run in O(n log n) time, incremental CDT construction is easier to program and competitive in practice. Moreover, the ability to incrementally update a CDT by inserting a segment is useful in itself.

This article describes a Lagrangian finite element method that simulates the behavior of liquids and solids in a unified framework. Local mesh improvement operations maintain a high-quality tetrahedral discretization even as the mesh is advected by fluid flow. We conserve volume and momentum, locally and globally, by assigning to each element an independent rest volume and adjusting it to correct for deviations during remeshing and collisions. Incompressibility is enforced with per-node pressure values, and extra degrees of freedom are selectively inserted to prevent pressure locking. Topological changes in the domain are explicitly treated with local mesh splitting and merging. Our method models surface tension with an implicit formulation based on surface energies computed on the boundary of the volume mesh. With this method we can model elastic, plastic, and liquid materials in a single mesh, with no need for explicit coupling. We also model heat diffusion and thermoelastic effects, which allow us to simulate phase changes. We demonstrate these capabilities in several fluid simulations at scales from millimeters to meters, including simulations of melting caused by external or thermoelastic heating.

We present warp-canceling corotation , a nonlinear finite element formulation for elastodynamic simulation that achieves fast performance by making only partial or delayed changes to the simulation's linearized system matrices. Coupled with an algorithm for incremental updates to a sparse Cholesky factorization, the method realizes the stability and scalability of a sparse direct method without the need for expensive refactorization at each time step. This finite element formulation combines the widely used corotational method with stiffness warping so that changes in the per-element rotations are initially approximated by inexpensive per-node rotations. When the errors of this approximation grow too large, the per-element rotations are selectively corrected by updating parts of the matrix chosen according to locally measured errors. These changes to the system matrix are propagated to its Cholesky factor by incremental updates that are much faster than refactoring the matrix from scratch. A nested dissection ordering of the system matrix gives rise to a hierarchical factorization in which changes to the system matrix cause limited, well-structured changes to the Cholesky factor. We show examples of simulations that demonstrate that the proposed formulation produces results that are visually comparable to those produced by a standard corotational formulation. Because our method requires computing only partial updates of the Cholesky factor, it is substantially faster than full refactorization and outperforms widely used iterative methods such as preconditioned conjugate gradients. Our method supports a controlled trade-off between accuracy and speed, and unlike most iterative methods its performance does not slow for stiffer materials but rather it actually improves.

We propose a finite element simulation method that addresses the full range of material behavior, from purely elastic to highly plastic, for physical domains that are substantially reshaped by plastic flow, fracture, or large elastic deformations. To mitigate artificial plasticity, we maintain a simulation mesh in both the current state and the rest shape, and store plastic offsets only to represent the non-embeddable portion of the plastic deformation. To maintain high element quality in a tetrahedral mesh undergoing gross changes, we use a dynamic meshing algorithm that attempts to replace as few tetrahedra as possible, and thereby limits the visual artifacts and artificial diffusion that would otherwise be introduced by repeatedly remeshing the domain from scratch. Our dynamic mesher also locally refines and coarsens a mesh, and even creates anisotropic tetrahedra, wherever a simulation requests it. We illustrate these features with animations of elastic and plastic behavior, extreme deformations, and fracture.

We present algorithms for simulating and visualizing the insertion and steering of needles through deformable tissues for surgical training and planning. Needle insertion is an essential component of many clinical procedures such as biopsies, injections, neurosurgery, and brachytherapy cancer treatment. The success of these procedures depends on accurate guidance of the needle tip to a clinical target while avoiding vital tissues. Needle insertion deforms body tissues, making accurate placement difficult. Our interactive needle insertion simulator models the coupling between a steerable needle and deformable tissue. We introduce (1) a novel algorithm for local remeshing that quickly enforces the conformity of a tetrahedral mesh to a curvilinear needle path, enabling accurate computation of contact forces, (2) an efficient method for coupling a 3D finite element simulation with a 1D inextensible rod with stick-slip friction, and (3) optimizations that reduce the computation time for physically based simulations. We can realistically and interactively simulate needle insertion into a prostate mesh of 13,375 tetrahedra and 2,763 vertices at a 25 Hz frame rate on an 8-core 3.0 GHz Intel Xeon PC. The simulation models prostate brachytherapy with needles of varying stiffness, steering needles around obstacles, and supports motion planning for robotic needle insertion. We evaluate the accuracy of the simulation by comparing against real-world experiments in which flexible, steerable needles were inserted into gel tissue phantoms.

The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7° and 164.8°, or (with a change in parameters) between 8.9° and 158.8°. The algorithm is whip fast, numerically robust, and easy to implement because, like Marching Cubes, it generates tetrahedra from a small set of precomputed stencils. A variant of the algorithm creates a mesh with internal grading: on the boundary, where high resolution is generally desired, the elements are fine and uniformly sized, and in the interior they may be coarser and vary in size. This combination of features makes isosurface stuffing a powerful tool for dynamic fluid simulation, large-deformation mechanics, and applications that require interactive remeshing or use objects defined by smooth implicit surfaces. It is the first algorithm that rigorously guarantees the suitability of tetrahedra for finite element methods in domains whose shapes are substantially more challenging than boxes. Our angle bounds are guaranteed by a computer-assisted proof. If the isosurface is a smooth 2-manifold with bounded curvature, and the tetrahedra are sufficiently small, then the boundary of the mesh is guaranteed to be a geometrically and topologically accurate approximation of the isosurface.

No abstract available.

We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing spatial finalization into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.

Star splaying is a general-dimensional algorithm that takes as input a triangulation or an approximation of a convex hull, and produces the Delaunay triangulation, weighted Delaunay triangulation, or convex hull of the vertices in the input. If the input is "nearly Delaunay" or "nearly convex" in a certain sense quantified herein, and it is sparse (i.e. each input vertex adjoins only a constant number of edges), star splaying runs in time linear in the number of vertices. Thus, star splaying can be a fast first step in repairing a high-quality finite element mesh that has lost the Delaunay property after its vertices have moved in response to simulated physical forces. Star splaying is akin to Lawson's edge flip algorithm for converting a triangulation to a Delaunay triangulation, but it works in any dimensionality.

This paper describes a method for building interpolating or approximating implicit surfaces from polygonal data. The user can choose to generate a surface that exactly interpolates the polygons, or a surface that approximates the input by smoothing away features smaller than some user-specified size. The implicit functions are represented using a moving least-squares formulation with constraints integrated over the polygons. The paper also presents an improved method for enforcing normal constraints and an iterative procedure for ensuring that the implicit surface tightly encloses the input vertices.

We introduce anisotropic Voronoi diagrams, a generalization of multiplicatively weighted Voronoi diagrams suitable for generating guaranteed-quality meshes of domains in which long, skinny triangles are required, and where the desired anisotropy varies over the domain. We discuss properties of anisotropic Voronoi diagrams of arbitrary dimensionality---most notably circumstances in which a site can see its entire Voronoi cell. In two dimensions, the anisotropic Voronoi diagram dualizes to a triangulation under these same circumstances. We use these properties to develop an algorithm for anisotropic triangular mesh generation in which no triangle has an angle smaller than 20A, as measured from the skewed perspective of any point in the triangle.

I discuss algorithms based on bistellar flips for inserting and deleting constraining (d - 1)-facets in d-dimensional constrained Delaunay triangulations (CDTs) and weighted CDTs, also known as constrained regular triangulations. The facet insertion algorithm is likely to outperform other known algorithms on most inputs. The facet deletion algorithm is the first proposed for d > 2, short of recomputing the CDT from scratch. An incremental facet insertion algorithm that begins with an unconstrained Delaunay triangulation can construct the CDT of a ridge-protected piecewise linear complex with nv vertices in O(nv[d / 2] + 1 log nv) time. Hence, in odd dimensions, CDT construction by incremental facet insertion is within a factor of log nv of worst-case optimal. Perhaps the most important feature of these algorithms is that they are relatively easy to implement.

No abstract available.

Nonmanifold geometric domains having small angles present special problems for triangular and tetrahedral mesh generators.Although small angles inherent in the input geometry cannot be removed, one would like to find a way to triangulate a domain without creating any new small angles.Unfortunately, this problem is not always soluble.I discuss how mesh generation algorithms based on Delaunay refinement can be modified to ensure that they always produce a mesh.A two-dimensional algorithm presented here creates a mesh with no new angle smaller than arcsin[sin(~/2)/v'~], where ~b < 60 ° is the smallest angle separating two segments of the input domain.Furthermore, new angles smaller than 20.7 ° appear only near input angles smaller than 60 ° .In practice, the algorithm's performance is better than these bounds suggest.A threedimensional algorithm presented here creates a mesh in which all tetrahedra have circumradius-to-shortest edge ratios no greater than two, except near acute input angles (angles separating segments and/or facets of the input domain).

I discuss algorithms for constructing constrained Delaunay triangulations (CDTs) in dimensions higher than two.If the CDT of a set of vertices and constraining simplices exists, it can be constructed in (.9 (nv ns) time, where nv is the number of input vertices and ns is the number of output d-simplices.In practice, the running time is likely to be O(n~ + n, logn~) in all but the most pathological cases.The CDT of a star-shaped polytope can be constructed in O(n8 log n~) time, yielding an efficient way to delete a vertex from a CDT.

Let X be a complex of vertices and piecewise linear constraining facets embedded in E d . Say that a simplex is strongly Delaunay if its vertices are in X and there exists a sphere that passes through its vertices but passes through and encloses no other vertex. Then X has a d-dimensional constrained Delaunay triangulation if each k-dimensional constraining facet in X with k d \\Gamma 2 is a union of strongly Delaunay k-simplices. This theorem is especially useful in E 3 for forming tetrahedralizations that respect specified planar facets. If the bounding segments of these facets are subdivided so that the subsegments are strongly Delaunay, then a constrained tetrahedralization exists. Hence, fewer vertices are needed than in the most common practice in the literature, wherein additional vertices are inserted in the relative interiors of facets to form a conforming (but unconstrained) Delaunay tetrahedralization. 1 Introduction Many applications can benefit from triangulations...

Given a complex of vertices, constraining segments, and planar straight-line constraining facets in E 3 , with no input angle less than 90 ffi , an algorithm presented herein can generate a conforming mesh of Delaunay tetrahedra whose circumradius-to-shortest edge ratios are no greater than two. The sizes of the tetrahedra can provably grade from small to large over a relatively short distance. An implementation demonstrates that the algorithm generates excellent meshes, generally surpassing the theoretical bounds, and is effective in eliminating tetrahedra with small or large dihedral angles, although they are not all covered by the theoretical guarantee. 1 Introduction Meshes of triangles or tetrahedra have many applications, including interpolation, rendering, and numerical methods such as the finite element method. Most such applications demand more than just a triangulation of the object or domain being rendered or simulated. To ensure accurate results, the triangles or tetr...

Irregular applications based on sparse matrices are at the core of many important scientific computations. Since the importance of such applications is likely to increase in the future, high-performance parallel and distributed systems must provide adequate support for such applications. We characterize a family of irregular scientific applications and derive the demands they will place on the communication systems of future parallel systems. Running time of these applications is dominated by repeated sparse matrix vector product (SMVP) operations. Using simple performance models of the SMVP, we investigate requirements for bisection bandwidth, sustained bandwidth on each processing element (PE), burst bandwidth during block transfers, and block latencies for PEs under different assumptions about sustained computational throughput. Our model indicates that block latencies are likely to be the most problematic engineering challenge for future communication networks.

. Automated route planning consists of using real maps to automatically find good map routes. Two shortcomings to standard methods are (1) that domain information may be lacking, and (2) that a ‘good’ route can be hard to define. Most on-line map representations do not include information that may be relevant for the purpose of generating good realistic routes, such as traffic patterns, construction, and one-way streets. The notion of a good route is dependent not only on geometry (shortest path),but also on a variety of other factors, such as the day and time, weather conditions,and perhaps most importantly,user-dependent preferences. These features can be learned by evaluating real-world execution experience. These difficulties motivate our work on applying analogical reasoning to route planning. Analogical reasoning is a method of using past experience to improve problem solving performance in similar new situations.Our approach consists of the accumulation and reuse of previously traversed routes. We exploit the geometric characteristics of the map domain in the storage, retrieval, and reuse phases of the analogical reasoning process. Our route planning method retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan. To find a good set of past routes, we have designed a similarity metric that takes into account the geometric and continuous-valued characteristics of a city map. The metric evaluates its own performance and uses execution experience to improve its prediction of case similarity, adaptability and executability. The planner uses a replay mechanism to produce a route plan based on analogy with past routes retrieved by the similarity metric. We use illustrative examples and show some empirical results from a detailed on-line map of the city of Pittsburgh, containing over 18,000 intersections and 25,000 street segments.

Fast C implementations of four geometric predicates, the 2D and 3D orientation and incircle tests, are publicly available. Their inputs are ordinary single or double precision floating-point numbers. They owe their speed to two features. First, they employ new fast algorithms for arbitrary precision arithmetic that have a strong advantage over other software techniques in computations that manipulate values of extended but small precision. Second, they are adaptive; their running time depends on the degree of uncertainty of the result, and is usually small. These algorithms work on computers whose floating-point arithmetic uses radix two and exact rounding, including machines that comply with the IEEE 754 floating-point standard. Timings of the predicates, in isolation and embedded in 2D and 3D Delaunay triangulation programs, verify their effectiveness. 1 Introduction Algorithms that make decisions based on geometric tests, such as determining which side of a line a point falls on, ...