Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!sdd.hp.com!ucsd!hub.ucsb.edu!ucsbuxa!3003jalp
From: 3003jalp@ucsbuxa.ucsb.edu (Applied Magnetics)
Newsgroups: comp.graphics
Subject: Re: triangulation and contouring
Keywords: triangulation
Message-ID: <6123@hub.ucsb.edu>
Date: 15 Aug 90 21:34:10 GMT
References: <1990Aug15.003127.22609@NCoast.ORG> <1990Aug15.145122.13588@jarvis.csri.toronto.edu>
Sender: news@hub.ucsb.edu
Lines: 26

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