Path: utzoo!attcan!uunet!wuarchive!zaphod.mps.ohio-state.edu!ncar!noao!arizona!pab From: pab@cs.arizona.edu (Peter A. Bigot) Newsgroups: comp.graphics Subject: Re: triangulation and contouring Keywords: triangulation, tessellation, finite element, bibliography Message-ID: <24369@megaron.cs.arizona.edu> Date: 20 Aug 90 15:50:42 GMT References: <1990Aug15.003127.22609@NCoast.ORG> <1990Aug15.145122.13588@jarvis.csri.toronto.edu> <6123@hub.ucsb.edu> <1990Aug16.103450.19448@jarvis.csri.toronto.edu> Organization: U of Arizona CS Dept, Tucson Lines: 135 I spent a good part of the last six months on this problem at the University of Minnesota, so here're a few of my results. My particular problem was to generate finite element grids, ideally in three dimensions, of systems with multiple material properties, which meant that physical boundaries had to be observed in the tessellation. For tessellation (both triangles and tetrahedrons), I used the method of D.F. Watson (bibliography below). This is a generalized, n-dimensional Delaunay tessellation algorithm, which seems to be fairly quick (much faster than the original Lawson JPL algorithm when you're doing thousands of points). Because of the need to maintain physical boundaries, the domain was split into convex polyhedra, each of exactly one material. Densification was done in a hierarchical manner: first, the common edges between faces were densified using the method in Frey87, then the faces, then the volumes. Node spacing is specified by giving an ideal-distance-to-nearest-node at each point in the domain, then using this to iteratively generate points until this spacing is satisfied. The result is a fairly smooth gradation with nearly perfect triangles/tetrahedrons. If necessary, you can add a Laplacian smoothing algorithm after each face/volume is tessellated, but be careful that you don't move nodes on physical boundaries. Some problems encountered were: 1. The tessellation is done on the convex hull of the points in the domain, which means the domain had better be convex. Unfortunately, with the method in Watson, it is possible that the completed tessellation is not convex when the bounding points are removed. 2. Because of the Delaunay constraint of empty circumspheres, the tessellation algorithm is extremely susceptible to degeneracies: passing it a grid, for example, will cause it to (try to) solve singular systems of linear equations. This problem can be avoided to some degree by using a high precision matrix inversion algorithm (accumulated truncation error is the main source of the problem for automatically densified grids). However, most three dimensional cases I tried still caused failure after about 700 nodes; since we expected systems of 15000 plus nodes, this is a major problem. Watson presents some changes that decrease the likelihood of degeneracy, but they aren't enough for all cases. 3. It is difficult to specify the domain in a simple manner. Because every topological entity (edge, face, volume) must be tessellated exactly once, it must be specified exactly once. The solution to this was to list every vertex in the domain, then define the lines using those points, the faces using the lines, etc. This requires an extremely complex geometry description file which is a royal pain to modify. As for speed, it's hard to recall (it's been a while since I benchmarked it), but two dimensional systems (with densification) solved in about three minutes for 1100 nodes on a 10Mhz 286; 3d systems of up to 600 points in about five minutes. Plain 2d triangulation given the points already was satisfactorily fast; the main problem was memory limitations of the computer (about 650 nodes for a 3d system on a PC). Although I'm not working on the problem directly any more, any proposed solutions to the above problems (esp. # 2) would be appreciated. Here's a list of some papers I found while researching the problem. It's a rough attempt at the transitive closure of references from Cavendish's 1974 article which seems to have started the whole thing; they present several different methods, from which I chose Watson's and Frey's. No particular order, and no guarantees they're any use. Enjoy. ------ Watson, D.F. "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes" The Computer Journal, 24:2 (1981), p 167. [_The_ source for voronoi tessellation algorithms, IMHO] Bowyer, A. "Computing Dirichlet tessellations" The Computer Journal, 24:2 (1981), p 162. [Almost the same as Watson, but I found it harder to understand.] Frey, Wm. H. "Selective Refinement: A New Strategy for Automatic Node Placement in Graded Triangular Meshes" International Journal for Numerical Methods in engineering, 24 (1987), p 2183-2200. Akima, Hiroshi. "A Method of Bivariate Interpolation and Smooth Surface Fitting for Irregularly Distributed Data Points." ACM Transactions on Mathematical Software, 4:2 (June 1978), pp 148-159. [Useful if you want to do contouring; I think this is where I found Lawson's triangulation algorithm.] Green, P.J., and R. Sibson. "Computing Dirichlet tessellations in the plane" The Computer Journal, 21:2 (1978), p 168. [Good if all you need is 2d.] Cavendish, James C. "Automatic Triangulation of Arbitrary Planar Domains for the Finite Element Method" Int. J. Num.Meth.Eng., 8 (1974), p 679. Cavendish, James C., D. Field, Wm. Frey. "An Approach to Automatic Three-Dimensional Finite Element Mesh Generation". Int. J. Num.Meth.Eng., 21 (1985), p 329. Choi, B.K., H.Y. Shin, Y.I. Yoon, J.W. Lee. "Triangulation of scattered data in 3d space" Computer Aided Design, 20:5 (1988), p 239. [Triangulation of points known to be on a surface]. Lo, S.H. "A New Mesh Generation Scheme for Arbitrary Planar Domains" Int.J.Num.Meth.Eng., 21 (1985), p 1403. Watson, D.F., G.M. Philip. "Survey of Systematic Triangulations" Computer Vision, Graphics and Image Processing, 26 (1984), p 217. Lee, D.T., B.J. Schachter. "Two Algorithms for Constructing a Delaunay Triangulation". Int. Jnl. Computer and Information Sciences, 9:3 (1980), p 219. Clarkson, Kenneth L., R. E. Tarjan, C.J. van Wyk. "A Fast Las Vegas Algorithm for Triangulating a Simple Polygon" Discrete Computational Geometry 4 (1989), p 423. Aggarwal, A., L.J. Guibas, J. Saxe, P. Shor. "A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon". Disc.Comp.Geom. 4 (1989), p 591. Schroeder, W.J., M.S. Shepard. "A Combined Octree/Delaunay Method for Fully Automatic 3-d Mesh Generation" Int.Jnl.Num.Meth.Eng., 29 (1990), p 37. Zhou, J.M., K.R.Shao, J.D. Lavers. "Automatic Mesh Generation Allowing for Efficient a priori and a posteriori Control of the Number and Distribution of Elements" IEEE Trans. Magnetics, 25:4 (1989), p 2983. Joe, B., R.B. Simpson. "Triangular Meshes for Regions of Complicated Shape" Int. Jnl. Num.Meth.Eng. 23 (1986), p 751. Schroeder, W.J., M.S. Shepard. "Geometry-based Fully Automatic Mesh Generation and the Delaunay Triangulation" Int.J.Num.Meth.Eng., 26 (1988), p 2503. Lo, S.H. "Delaunay Triangulation of Non-convex Planar Domains". Int.J.Num.Meth.Eng., 28 (1989), p 2695. -- Peter A. Bigot -- pab@cs.arizona.edu Dept. of Computer Science, University of Arizona, Tucson AZ ---------------------------- The current quote is: ---------------------------- "Books, Charles, are like lobster shells. We carry them around with us, and we grow out of them, and leave them behind as evidence of our earlier stages of development." Lord Peter Wimsey (Ian Carmichael).