ALGORITHMIC GEOMETRY AND MESH GENERATION
Math 579 Section 002, also offered as: ECE 595 Section 006
New Time/Place: T 18:00-20:00, Humanities 428, or a warmer room around the corner
University of New Mexico
Instructor: Scott A. Mitchell
No class Sept 28 - attend the
cubit tutorial instead.
No class Oct 5 - balloon fiesta
references, namely books
week 1 (due 31 Aug)
week 2 (due 9 Sept)
use this picture:
set 3 (due 13 or 20 October)
you can use these old course notes:
Turn in homework in class or email it to me
Simulation of Simplicity for degenerate points
Guaranteed Quality Meshes
Chew website - Guaranteed Quality Triangular Meshes
Chew paper - Guaranteed Quality Triangular Meshes
Ruppert - local feature size definition
BernEppsteinGilbert, quadtree triangulating for points sets
Labelle_thesis Tetrahedral meshes using point lattices (reminiscint of octrees, in that the lattices may be graded, but without the bookkeeping of octree geometric edges and faces). This is a a more modern treatment of my thesis topic, by one of Shewchuck's students. The student is no longer in mesh generation. Deals with point lattices structures that may be familiar to chemists such as body-centered cubic, face centered cubic.
Sliver Exudation external link to pdf of paper
Quality mesh generation in three dimensions" link to my thesis
hex mesh existence via duality
Geode template includes duality structure for tets refined into hexes.
Flipping and triangulation updating for moving points
CGAL 3d Triangulations package includes Triangulations are build incrementally and can be modified by... displacements ... of vertices''
Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica, 15:223-241, 1996. regular is what we've been calling the weighted DT.
Point Location. Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181-199, 2002. How to find the location of a point in a triangulation, that is, which triangle contains it so you know the local region to consider flipping.
Computational Geometry- from theory to practice, From linear objects to curved objects page 8 describes some practical choices of how to implement this. Walks with a few random decisions tends to be best.
Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163-180, 2002" Talks about how to save some information for faster point lookup later.
Point removal, using symbolic perturbation to resolve degeneracies. This is the most expensive operation when updating a triangulation, and flips are the cheapest. From CGAL we have:
Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in a 3D Delaunay triangulation. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 313-319, 2003.
Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in Delaunay and regular 3D triangulations. Research Report 5968, INRIA, 2006.
State of the Art: Updating Delaunay Triangulations for Moving Points is a survey of various techniques,
An empirical comparison of techniques for updating Delaunay triangulations
Includes molecular simulation in 3d as the motivating example.
Leonidas Guibas, Menelaos Karaveles, and Daniel Russel. A computational framework for handling motion. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, pages 129-141, 2004.
CGAL Kinetic Data Structures
The Kinetic Data Structure has been added to CGAL but is not used for relocationfor DT and power DT. The authors state that the following procedure is used instead: (1) insert point at new position;
(2) remove vertex at old position, leaving it disconnected;
(3) updating the info related to the disconnected vertex with the info of the inserted vertex, neighborhood (adjacent cells) and coordinates; (4) delete the vertex at the new position.
Kinetic Data Structures handbook by Guibas et al.
Pedro Machado Manhaes de Castro. Practical Ways to Accelerate Delaunay Triangulations. These de doctorat en sciences, Universite de Nice-Sophia Antipolis, France, 2010.
This describes general combinatorial operations, bibliography of several nice papers on this subject. May be what's in CGAL.
Russel thesis: Kinetic Data Structures in Practice
Delaunay Triangulations for Moving Points
Shewchuck's Star splaying: an algorithm for repairing delaunay triangulations and convex hulls That is flip-based and consequently fast.
Additional contact info is on my homepage.
Back to Scott's homepage