atul@NCoast.ORG (Atul Parulekar) (08/15/90)
I think there was a discussion some time back about delaunay triangulation of random points. I wrote a program to do this based on a paper by Cavendish JC, Field DA, Frey WH in the International Journal for Numerical Methods in Engineering, V21, 1985, but it ran too slowly (I have seen programs which run 5-10 times faster). Is there any fast (fastest ?) algorithm to do this? Also, I would like to include breaklines in the data. (These are lines which cannot be intersected by any triangle, i.e., the lines are a part of the triangulation.) Any suggestions? Finally, any suggestions on how this triangle network can be used for contouring directly (i.e., without first generating a grid of regularly spaced points)?
3003jalp@ucsbuxa.ucsb.edu (Applied Magnetics) (08/16/90)
(Mail bounces, hence this post.) -For a triangle-based contour plotter, get Algorithm 626 of the ACM Transactions on Mathematical Software, vol.10, no.4, pp.463-75, Dec.1984. Source available from Netlib; send mail to `netlib@ornl.gov' with a one-line message: `send 626 from toms'. You can use the whole thing, or interface your code to routine `trp00' and its dependents. -I can also help with breaklines and (maybe) speed, but not on the net. Try mail to `3003jalp@ucsbuxa.ucsb.edu' and give a fool-proof return address. In desperation, call 805-683-3871 x5570. --Pierre Asselin, Applied Magnetics Corp.
corkum@csri.toronto.edu (Brent Thomas Corkum) (08/16/90)
>> I think there was a discussion some time back about delaunay triangulation of >> random points. I wrote a program to do this based on a paper by Cavendish JC >> Field DA, Frey WH in the International Journal for Numerical Methods in >> Engineering, V21, 1985, but it ran too slowly (I have seen programs which run >> 5-10 times faster). Is there any fast (fastest ?) algorithm to do this? This is rather interesting as I am currently in the process of using this paper to write a mesher for a hybrid finite-boundary element 2D stress analysis program. I've just completed the node insertion program based on the 1974 paper by Cavendish and am just moving on to the triangulation routines based on the 1985 paper by Cavendish. I must say that I was rather disappointed as well with the grid overlay method for node insertion, I'll end up having to employ some smoothing no doubt. If anyone has any information or code for the triangulation I would be interested as well. For our application we're talking maybe 500 elements maximum so how long on a 386/20 PC would this take to triangulate? A better question might be , does anyone have any benchmarks for the dulaunay triangulation process? Brent Corkum corkum@ecf.toronto.edu
3003jalp@ucsbuxa.ucsb.edu (Applied Magnetics) (08/16/90)
In article <1990Aug15.145122.13588@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes: > [ He is disappointed by the speed of code he wrote based on > a paper by Cavendish et al. ] Wow! That's two people worrying about triangulation speed. I haven't seen the Cavendish papers, my own code evolved from C.L. Lawson, in "Mathematical Software III", Rice (ed.), Academic Press 1977. Also with an assist from David Shenton's thesis, Carnegie Mellon 1987, plus some original stuff. All I can say about performance is that mesh operations are *trivial* compared to what awaits you when you solve your finite-element system. With adaptive mesh refinement, I hit 3000 triangles in no time. Are we talking about 2D triangulations? The same would be true in 3D anyway. Lawson inserts new nodes by: a) finding the enclosing triangle; b) trisecting it; c) swapping edges to a Delaunay mesh. To find the triangle in step (a): aa) take a guess; ab) compute homogeneous coordinates; ac) stop if all three positive, or loop with the neighbour on the side correspoding to the negative coordinate (if two are negative, choose arbitrarily). You must maintain pointers to neighbouring triangles in your data structures. The search examines O(n**1/2) triangles, and may do much better in practice, because successive nodes are close to one another. --P. Asselin, Applied Magnetics
nwatson@enuxha.eas.asu.edu (Nathan F. Watson) (08/16/90)
In article <1990Aug15.003127.22609@NCoast.ORG>, atul@NCoast.ORG (Atul Parulekar) writes: > I think there was a discussion some time back about delaunay triangulation of > random points. I wrote a program to do this based on a paper by Cavendish JC, > ... > Finally, any suggestions on how this triangle network can be used for > contouring directly (i.e., without first generating a grid of regularly > spaced points)? A student here at Arizona State University recently completed his master's thesis: "Contouring Trivariate Surfaces", Brett Keith Bloomquist. The thesis describes methods for contouring bivariate and trivariate surfaces (f(x,y) and f(x,y,z)). I believe a paper will eventually be published. For the bivariate case, the scheme boils down to: (a) Triangulate the data points, and estimate the gradients of the function at each data point. (b) Use the stuff obtained in (a) to obtain a Clough-Tocher interpolant over each triangle, resulting in a number of triangular Bezier patches of degree 3, which you will want to contour. (c) Approximate each degree 3 patch with one or more degree 2 patches (according to some user-defined tolerance). The degree 2 patches describe quadratic functions, which may be contoured using at most six rational quadric bezier curves per patch. The scheme is too detailed to explain fully here. I will attempt to let those interested know when the article appears. --------------------------------------------------------------------- Nathan F. Watson Arizona State University nwatson@enuxha.eas.asu.edu Computer Science Department
corkum@csri.toronto.edu (Brent Thomas Corkum) (08/16/90)
>> Wow! That's two people worrying about triangulation speed. I haven't >> seen the Cavendish papers, my own code evolved from C.L. Lawson, in >> "Mathematical Software III", Rice (ed.), Academic Press 1977. Also >> with an assist from David Shenton's thesis, Carnegie Mellon 1987, plus >> some original stuff. All I can say about performance is that mesh >> operations are *trivial* compared to what awaits you when you solve >> your finite-element system. With adaptive mesh refinement, I hit 3000 >> triangles in no time. Are we talking about 2D triangulations? >> The same would be true in 3D anyway. I realize that compared to the actual FE calcs, triangulation is rather trivial but when you want to incorporate it into a user interface and make it interactive, speed is important. In my opinion, setting up a FE run is the most rigourous and time consuming part of the analysis. I don't mind letting it compute the results over night (I realize that some people run jobs that require a lot more time to compute) but when I have to spend a day or two sitting a terminal creating the data file(s), I get a little anxious, especially when I find that I've made a mistake somwhere and have to repeat the entire process. Anyways, enough of that, I'm lucky right now as I'm only worried about the 2D triangulation , 3D is next but you have to crawl before you can walk. I'm interested in locating and hearing about different 2D algorithms tah people are using for node insertion and triangulation, and am also interested in finding out a little more about quadtree methods for meshing. So if anyone has anything to say about there experiences with meshing I'd be glad to here it. To the author of the above comment, could you elaborate on David Shenton's thesis as to what it's about, and if it's not to much work , give the ISBN# if there is one or who to contact for a copy. Thanks Brent Corkum corkum@ecf.toronto.edu
Kessells_SR@cc.curtin.edu.au (08/17/90)
In article <1990Aug15.003127.22609@NCoast.ORG>, atul@NCoast.ORG (Atul Parulekar) writes: > I think there was a discussion some time back about delaunay triangulation of > random points. I wrote a program to do this based on a paper by Cavendish JC, > Field DA, Frey WH in the International Journal for Numerical Methods in > Engineering, V21, 1985, but it ran too slowly (I have seen programs which run > 5-10 times faster). Is there any fast (fastest ?) algorithm to do this? > > Also, I would like to include breaklines in the data. (These are lines which > cannot be intersected by any triangle, i.e., the lines are a part of the > triangulation.) Any suggestions? > > Finally, any suggestions on how this triangle network can be used for > contouring directly (i.e., without first generating a grid of regularly > spaced points)? I have developed a 2D Delaunay-based triangulation system with breaklines etc. The system has been running with a commercial package (no strings) and been hammered quite a bit without failing (as yet!). On a 12mhz 286 with 287, it can do about 1000 points in 50 sec. 386= got to about 19 secs. IRIS blinks ... It is based on Lee & Scachter's work, but bits are from everywhere. It was written as a 3rd year project and I am currently working with the 3D problem for honours. So I would like to hear from all who are interested. Also, I have a friend working in representing the surface to varying degrees of accuracy for his honours thesis.... The my code plus report is freely available to anybody who asks (no strings except for a little recognition). Michael ------------------------------------------------------------------------------- Aussie Post: Michael Evans Internet: TKESSELLS01@cc.curtin.edu.au ACSnet: TKESSELLS01@cc.cut.oz.au Bitnet: TKESSELLS01%cc.curtin.edu.au@cunyvm.bitnet UUCP: uunet!munnari.oz!cc.curtin.edu.au!TKESSELLS01 -------------------------------------------------------------------------------
pab@cs.arizona.edu (Peter A. Bigot) (08/20/90)
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).