2008

DelPSC: A Delaunay mesher for piecewise smooth complexes (Multimedia Submission)
Tamal K. Dey and Joshua A. Levine
Proc. 24th Annual Symposium on Computational Geometry, College Park, MD, June 2008
Watch the corresponding video

This video presents the working of a new algorithm/software called DelPSC that meshes piecewise smooth complexes in three dimensions with Delaunay simplices. Piecewise smooth complexes admit a large class of geometric domains including polyhedra, smooth and piecewise smooth surfaces with or without boundary, and non-manifolds. The algorithm and its proof of correctness are described in our manuscript [DL08].

2007

A practical Delaunay meshing algorithm for a large class of domains (Preprint)
Siu-Wing Cheng, Tamal K. Dey, and Joshua A. Levine
Proc. 16th International Meshing Roundtable, Seattle, WA, Oct. 2007
Download the DelPSC software!

Recently a Delaunay refinement algorithm has been proposed that can mesh domains as general as piecewise smooth complexes [CDR07]. In this paper we introduce a novel modification of the algorithm to make it implementable in practice. In particular, we replace four tests of the original algorithm with only a single test that is easy to implement. The algorithm has the following guarantees. The output mesh restricted to each manifold element in the complex is a manifold with proper incidence relations. More importantly, with increasing level of refinement which can be controlled by an input parameter, the output mesh becomes homeomorphic to the input while preserving all input features. Implementation results on a disparate array of input domains are presented to corroborate our claims.

A Delaunay simplification algorithm for vector fields (Preprint)
Tamal K. Dey, Joshua A. Levine, and Rephael Wenger
Proc. 15th Pacific Graphics Conference, Maui, HI, Oct. 2007

We present a Delaunay based algorithm for simplifying vector field datasets. Our aim is to reduce the size of the mesh on which the vector field is defined while preserving topological features of the original vector field. We leverage a simple paradigm, vertex deletion in Delaunay triangulations, to achieve this goal. This technique is effective for two reasons. First, we guide deletions by a local error metric that bounds the change of the vectors at the affected simplices and maintains regions near critical points to prevent topological changes. Second, piecewise-linear interpolation over Delaunay triangulations is known to give good approximations of scalar fields. Since a vector field can be regarded as a collection of component scalar fields, a Delaunay triangulation can preserve each component and thus the structure of the vector field as a whole. We provide experimental evidence showing the effectiveness of our technique and its ability to preserve features of both two and three dimensional vector fields.

Delaunay meshing of isosurfaces (Preprint)
Tamal K. Dey and Joshua A. Levine
Proc. Shape Modeling International (2007), 241-250, Lyon, France, June 2007
Presentation
Download the DelIso software!

We present an isosurface meshing algorithm DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation on a variety of volume datasets.

2006

Sampling-based planning, control, and verification of hybrid systems
Michael S. Branicky, Michael M. Curtiss, Joshua A. Levine, and Stuart B. Morgan
IEE Proc. Control Theory and Applications. 153(5):575-590, Sept. 2006

A sampling-based approach to planning, control and verification inspired by robotics motion planning algorithms such as rapidly exploring random trees (RRTs) and probabilistic roadmaps (PRMs) is surveyed. With the focus on RRTs, how to adapt them to solve standard non-linear control problems is demonstrated. RRTs are extended to purely discrete spaces (replacing distance metrics with cost-to-go heuristic estimates and substituting local planners for straight-line connectivity) and computational experiments comparing them to conventional methods, such as A* are provided. Finally, RRTs are extended to the case of hybrid systems and our modifications to LaValle's motion strategy library to allow for hybrid planning and verification are described. The work on the coverage and optimality properties of sampling-based techniques is also reviewed.

2005

Sampling-based reachability algorithms for control and verification of complex systems (Preprint)
Michael S. Branicky, Michael M. Curtiss, Joshua A. Levine, and Stuart B. Morgan
Proc. Thirteenth Yale Workshop on Adaptive and Learning Systems, New Haven, CT, May 2005

In this paper, we survey sampling-based reachability algorithms that may be used for planning, control, and verification of complex systems. These were inspired by two robotics motion planning algorithms: Rapidly-exploring Random Trees (RRTs) and Probabilistic RoadMaps (PRMs). Herein, we review RRTs and PRMs. We review our adaptations and extensions to nonlinear control problems, hybrid systems, and completely discrete problems. We also summarize our work on the properties of sampling-based techniques.

2003

RRTs for nonlinear, discrete, and hybrid planning and control.
Michael S. Branicky, Michael M. Curtiss, Joshua A. Levine, and Stuart B. Morgan
Proc. IEEE Conf. on Decision and Control, 657-663, Maui, HI, Dec. 2003
Presentation
Preprint

In this paper, we describe a planning and control approach in terms of sampling using Rapidly-exploring Random Trees (RRTs), which were introduced by LaValle. We review RRTs for motion planning and show how to use them to solve standard nonlinear control problems. We extend them to the case of hybrid systems and describe our modifications to LaValle's Motion Strategy Library to allow for hybrid motion planning. Finally, we extend them to purely discrete spaces (using heuristic evaluation as a distance metric) and provide computational experiments comparing them to conventional methods, such as A*.

Posters

Theses