Sign in to follow this  
Aph3x

fao G.Rhodes - split from other thread

Recommended Posts

So as not to hijack the other thread...
Quote:
Original post by grhodes_at_work Freeware, working code from Stolfi can be found here: You need the source files libdelaunay and libquad folders. Its not much code. I've compiled and run it myself, and it works really well, though annoyingly he does a separate new/delete for each vertex/edge/face that is created or destroyed. And, he assumes 32-bit word size which is sufficient for now.
That code does some horrible things - do you know what that returned value is?!! A pointer to an edge_struct as an int??!

Share this post


Link to post
Share on other sites
Hi Aph3x,

I appreciate the new, non-hijacked thread!

Ha, ha, yes, I realize what Stolfi is doing. I should have
mentioned that. The thing is this. Stolfi's code basically
requires that: a) the word size on the machine is 32 bits; and
b) objects are word-aligned. Both of these assumptions are
reasonable on 32-bit Intel hardware, e.g. Pentium class
machines with the compiler set to its normal object packing
rules.

The magical thing that happens (and you may already realize
what's going on) is that when the objects are word-aligned,
then the lower few bits of a pointer are always zero. Stolfi
exploits this. His edge_ref integer value encodes BOTH a
pointer to an edge_struct object, AND an orientation
flag that determines the orientation of the edge. The upper 30
bits are the pointer and the bottom 2 bits are the flag. So,
when you get an edge_ref in return, you have the following:

edge_struct *object = (edge_struct*)(edgeref_value & 0xffffffc);

and,

orientation = edgeref_value & 3;

To really understand what is going on here, with the
orientation, you're going to have to read up on the quad edge
data structure that is the basis for Stolfi's algorithm. Paul
Heckbert has a good web page on it somewhere, and also wrote
code for one of the Graphics Gems books (I think the 4th book)
that talks about quad edge more intuitively than Guibas and
Stolfi.

I know the word-aligned 32-bit pointer + orientation = edge_ref
= unsigned int thing is bizarre and nonportable. But, it works.
If you really want to understand divide-and-conquer Delaunay
then Guibas and Stolfi's paper is kind of the definitive work.

I can say that if you look at Heckbert's implementation of Quad-
Edge (which is also available on the web and I think is
freeware for noncommercial use), you will find something more
normal, e.g., he does none of this weird embedding.

If you don't care that sometimes the triangulation will run
slowly, then you may just want to drop back to the simple
incremental insertion algorithm. Its somewhat more
straightforward to implement, but can be slow in some cases. To
make it reasonably fast you need to randomize the order in
which your points get inserted into the triangulation. There
are a good number of web docs that illustrate the incremental
insertion algorithm.

One more thing I should say about Stolfi's code....it never
actually produces triangles. Hmmm. It only gives you edges.
Hmmm. But, from the edges you can create triangles. How to do
it is this. When you create the edges initialize the left and
right faces to be zero. Then, use Stolfi's code to walk through
all the edges, visiting each edge exactly once. As you visit an
edge, do this for each edge a:


1) If the edge's left face is nonzero, skip to the next edge,
otherwise continue. Pseudocode:

edge_ref a = current edge
if (LEFT(a) != 0) continue;

2) Set its left face to be == 1. Pseudocode:

LEFT(a) = 1;

3) Now, walk around the edges connected on the left edge of the
edge a. You will find 3 edges, a being the first. Say your 3
edges are a, b, c. Create a new triangle using the 3 vertices
common to a, b, and c. And, set the left face of a, b, and c to
be 1 (so that you don't create the same triangle again). Pseudo-
code for this is:

edge_ref a = the current edge from the outer loop;
edge_ref b = LNEXT(a) = the next edge counterclockwise from a
edge_ref c = LNEXT(b) = the next edge counterclockwise from b

c closes the triangle
Create triangle using vertices of a, b, c.

LEFT(b) = 1
LEFT(c) = 1

4) Continue to the next edge using Stolfi's code.


Hope this helps.

Share this post


Link to post
Share on other sites
Woah - thanks very much for that lengthy description!

It is the most compact implementation I've seen by far -- I suppose there had to be some penalty for that ;)

I hope to be portable to other machines in the future.
Not really bothered about the speed - it's going to be pre-calculated on game init.
Mainly bothered that it's robust -- my entire game depends on the spatial partitioning being a valid delaunay triangulation (it's been hand-made up to now).
I'm really only interested in the edges rather than the actual triangles, so that fits in quite well with the quad edge thing.

I'll take a look at incremental insertion; seem to remember there were possible problems with thin triangles there...

Thanks again,
Aph

Share this post


Link to post
Share on other sites
Thin triangles cause problems with the divide-and-conquer method as well (which I know very well based on recent annoying experiences), but it seems with divide-and-conquer it may be easier to deal with them. I found with incremental insertion, it was quite easy to create so many edge flips that there would be a stack overflow or at least very slow searches for a containing triangle or edge at the next insertion. Eberly, Guibas and Stolfi, and Shewchuk, all discuss better ways to the container search for incremental insertion.

The biggest problems will arise when you have uniformly-spaced input points. If the points are really random, things will work 99.9% of the time.

I'll note that Stolfi's code includes an incremental insertion implementation as well, though if you don't like the weird pointer mangling you won't want to use it.

I played around with Eberly's old Delaunay implementation, but not his "2" version.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this