## Fastest Voronoi in 3D

### Fastest Voronoi in 3D

Hello,

I am looking for a fast voronoi algorithm in three dimensional space.
while surfing the net (www.voronoi.com) and newsgroups i got a lot
ideas, but which algorithm is the fastest?
in my case all points move slightly from one time step to the next. do
i really need to construct the diagram every frame? i know there are
algorithms to move one point, at least i have found one for the 2D
case.
form time to time the amount of points grows, that means i insert
points. thats not that problem with the existing standrad incremental
algorithm in 3D, which runs in O(n^2) for n points as far i know.
If you remeber any nice papers or have a good idea please answer me!

Greetings Chris

### Fastest Voronoi in 3D

Quote:> in my case all points move slightly from one time step to the next. do
> i really need to construct the diagram every frame?

Please excuse me if my response seems dense, my knowledge of Voroni stuff
comes via my faint but increasing knowledge of convex hull algorithms. I
believe that one can use a convex hull finding algorithm in the search for a
Voronoi diagram. If this is not the case then please discard the rest of
this post.

The first step of quickhull is to find an arbitrary convex shape (usually a
d+1 vertexed form for a d dimensional space, but it doesn't have to be), and
to throw away any points which are already inside this. If you have a hull
from a previous time step it strikes me that you should be able to do a
pretty good job of guessing a quite inclusive initial shape.

With this in mind, perhaps a quickhull derived method might be what you
seek? At the very simple end you could do something like pick d+1 points
which certainly used to be on the boundary and use them for a new simplex,
therefore hoping to bypass many tests that a dumb point selection could not.

-Thomas

### Fastest Voronoi in 3D

> Hello,

> I am looking for a fast voronoi algorithm in three dimensional space.
> while surfing the net (www.voronoi.com) and newsgroups i got a lot
> ideas, but which algorithm is the fastest?
> in my case all points move slightly from one time step to the next. do
> i really need to construct the diagram every frame? i know there are
> algorithms to move one point, at least i have found one for the 2D
> case.
> form time to time the amount of points grows, that means i insert
> points. thats not that problem with the existing standrad incremental
> algorithm in 3D, which runs in O(n^2) for n points as far i know.
> If you remeber any nice papers or have a good idea please answer me!

> Greetings Chris

You might give the dynamic (insertion and removal) algorithm implemented
in CGAL, the Computational Geometry Algorithm Library, a try. It is free

Concerning your moving points, do you know how they move, I mean,
do you have a function with time as parameter for each vertex. There
is some literature about "kinetic data structures" you might look at.
The idea is to precompute the next couple of topological changes which
makes it a discrete problem again.

andreas

### Fastest Voronoi in 3D

> Hello,

> I am looking for a fast voronoi algorithm in three dimensional space.
> while surfing the net (www.voronoi.com) and newsgroups i got a lot
> ideas, but which algorithm is the fastest?
> in my case all points move slightly from one time step to the next. do
> i really need to construct the diagram every frame? i know there are
> algorithms to move one point, at least i have found one for the 2D
> case.
> form time to time the amount of points grows, that means i insert
> points. thats not that problem with the existing standrad incremental
> algorithm in 3D, which runs in O(n^2) for n points as far i know.
> If you remeber any nice papers or have a good idea please answer me!

> Greetings Chris

Hi Chris,

Let me offer the following comments.  Let me preface them by saying
that I prefer to write about 3-d Delaunay triangulation algorithms.
But it should be clear that if you have an algorithm for computing
Delaunay triangulations, you also have an algorithm for computing
Voronoi diagrams.

It's hard to say which algorithm is the "fastest" but my experience is
that a randomized incremental algorithm is "good."  First, it is worth
mentioning that all 3-d Delaunay triangulation algorithms can run in
O(n^2), simply because the output size of a 3-d Delaunay triangulation
can be O(n^2).  Sample any set of n points on the "moment curve
paramaterized by (t, t^2, t^3).  However, in practice, this worst case
output size is uncommon.  Although it is possible that an incremental
algorithm can spend O(n^2) computing a Delaunay triangulation of
complexity O(n), by randomizing the insertion order of your points,
this behavior is very unlikely to occur in practice.  (It's very
similar to the average- vs. worst-case running times of quick sort.)

Moving points in a Delaunay triangulation is a bit tricky.  However,
if you are willing to move points one at a time, you can certainly do
better than recomputing the triangulation at each time step.  If you
use CGAL, as another poster suggested, you could implement a move by
first deleting the point to be moved from the triangulation it and
then reinserting it at its new position.  That would give you an
off-the-shelf solution that you could evaluate right away.  I guess
this is pretty much the same as recomputing, but I'm not sure. If your
points are going to move "far" at each time step, my guess is this is
the best you could do.

If your points are not going to move "far" at each time step, meaning
there would be few to none structural changes in the triangulation
caused by the move, there is an algorithm that is sensitive to the
number of structural changes in the Delaunay triangulation.  The
algorithm does not differ too much in spirit from algorithms for
inserting and deleting points in a triangulation.  If you understands
how those work, then the algorithm is trivial.  If you are interested,
I can send you the details.  However, my advice is to try the
delete-reinsert strategy in CGAL first.  Once you have that running,
implementing a move operation for CGAL would not be too difficult --
maybe a few days of programming at the worst, I'm just too lazy).

Mickey

### Fastest Voronoi in 3D

Quote:> [...]
> You might give the dynamic (insertion and removal) algorithm implemented
> in CGAL, the Computational Geometry Algorithm Library, a try. It is free

This continuous pimping of your for-sale product -- even though
it happens to be free for academic usage -- is bad netiquette at
best and spam at worst.

Christer Ericson
Sony Computer Entertainment, Santa Monica

### Fastest Voronoi in 3D

On Tue, 01 Jul 2003 04:20:54 GMT, Christer Ericson

>> [...]
>> You might give the dynamic (insertion and removal) algorithm implemented
>> in CGAL, the Computational Geometry Algorithm Library, a try. It is free
>This continuous pimping of your for-sale product -- even though
>it happens to be free for academic usage -- is bad netiquette at
>best and spam at worst.
>Christer Ericson
>Sony Computer Entertainment, Santa Monica

Can you suggest a better open-source alternative with GPL or the like?
If not, I point out the following encouraging statement

| Starting with the next release of CGAL in spring 2003 it will fall
| under an Open Source license.

on the web site

| A commercial license for release 1.2 is free of charge.

I'd hardly call this pimping or spam. But if you have a complaint, you
will find at

<http://www.cgal.org/Manual/doc_html/index.html>

that the manual preface states the following relevant information.

| CGAL is a Computational Geometry Algorithms Library written
| in C++, developed by a consortium consisting of ETH Zrich
| (Switzerland), Freie Universit?t Berlin (Germany), INRIA
| Sophia-Antipolis (France), Martin-Luther-Universit?t
| Halle-Wittenberg (Germany), Max-Planck Institut fr
| Informatik, Saarbrcken (Germany), RISC Linz (Austria)
| Tel-Aviv University (Israel), and Utrecht University (The
|
| Should you have any questions, comments, remarks or
| criticism concerning CGAL, please send a message to

### Fastest Voronoi in 3D

>>[...]
>>You might give the dynamic (insertion and removal) algorithm implemented
>>in CGAL, the Computational Geometry Algorithm Library, a try. It is free

> This continuous pimping of your for-sale product -- even though
> it happens to be free for academic usage -- is bad netiquette at
> best and spam at worst.

> Christer Ericson
> Sony Computer Entertainment, Santa Monica

Dear Christer, Dear All,

I would be glad to hear other opinions on that topic. If those who give
a lot of advice on this newsgroup agree with you I will stop it.

Otherwise I will continue, because I think there is really a lack
of knowledge about existing, that is implemented, fast, and reliable
solutions for standard problems. To me it appears as a waste
of time to recode algorithms, be they in CGAL or not. One may
have good reasons for recoding, but lack of knowledge isn't.

You should also note that I tell people to look at ANN, if they ask
again  and again the Nearest Neighbor questions, look at VRONI, if
they need Voronoi of segments, or I tell them to search for KDS, if
they need Kinetic Data Structures without knowing the right search term.

As another poster pointed out, CGAL will in its next release be
available under an open source license. This will not make go all
problems away, as it is one that doesn't allow commercial usage.
So probably thast doesn't change lot for you.

Note further that some months ago, I was told that I should make it
clear that CGAL is NOT free for non-academic users, because not

Again, it is up to the community of this newsgroup to decide if they
want to see this kind of information or not.

Best regards,

Andreas

### Fastest Voronoi in 3D

> > This continuous pimping of your for-sale product -- even though
> > it happens to be free for academic usage -- is bad netiquette at
> > best and spam at worst.
> > Christer Ericson
> > Sony Computer Entertainment, Santa Monica
> Dear Christer, Dear All,

> I would be glad to hear other opinions on that topic. If those who give
> a lot of advice on this newsgroup agree with you I will stop it.
...
> Best regards,
> Andreas

Andreas,

I am not a CGAL user, but after having a look at the website I think
its a reasonable policy: plenty free information, free acadamic use
but not free for commercial applications.

You may consider the objection as a special kind of Sony Entertainment,
(which I found disgusting, after visiting the Sony exhibition in Berlin,
Potsdamer Platz, February 2000. For recreation I moved to the Bauhaus
Archiv nearby  ... but thats off-topic, I know).

Best regards --Gernot Hoffmann

### Fastest Voronoi in 3D

Quote:> [...]
> I'd hardly call this pimping or spam.

Searching comp.graphics.algorithms for "fabri andreas cgal"
gives 45 posts from Andreas Fabri on Google groups.
"fabri andreas -cgal" returns 7 posts of his.

In other words, around 87% of his posts to c.g.a concern GCAL,
thus I'm justified in my use of "continuous".

I'm also justified in my use of "pimping" because CGAL _is_
a commercial product. Whether it is provided free of charge
in some manner to select groups of people, does not change
this fact.

Just, you've been on usenet news long enough and a frequenter
of this group long enough to know that repeated announcements
of commercial products has never been welcome here (nor
anywhere else on news, except for the groups created specifically
for that purpose).

Quote:> But if you have a complaint, you will find at

>   <http://www.cgal.org/Manual/doc_html/index.html>

> that the manual preface states the following relevant information.
> [...]

I fail to see the relevance of your comment, including what is
relevant about that information. My objection is with Andreas
Fabri's repeated plugging of his for-sale product, not with the
product itself.

I would equally object if, say, Dave Eberly was posting
page references to his books, thus plugging them (but he's
not). In fact, I did back when Joe O'Rourke used to
continuously plug his book here, when it first came out.

If Andreas' concern is that people do not know about CGAL (as
entry in the FAQ about what CGAL can do? That should be good
enough for Andreas if indeed his posts are not commercially
motivated.

Christer Ericson
Sony Computer Entertainment, Santa Monica

### Fastest Voronoi in 3D

Quote:> [...]
> You may consider the objection as a special kind of Sony Entertainment,

Am I to consider that remark as some special kind of German humor?

"Humor ist, wenn man trotzdem lacht," I assume.

Christer Ericson
Sony Computer Entertainment, Santa Monica

### Fastest Voronoi in 3D

On Wed, 02 Jul 2003 04:29:11 GMT, Christer Ericson

>I'm also justified in my use of "pimping" because CGAL _is_
>a commercial product. Whether it is provided free of charge
>in some manner to select groups of people, does not change
>this fact.

I really wish it was not encumbered with a commercial license. Yet I'm
quite sure that many of the people asking for assistance here will not
be in the commercial use category. So while it doesn't change the fact
that some must pay, it does affect my feeling about whether it should
be considered pimping.

Quote:>Just, you've been on usenet news long enough and a frequenter
>of this group long enough to know that repeated announcements
>of commercial products has never been welcome here (nor
>anywhere else on news, except for the groups created specifically
>for that purpose).

Yes, true unrelenting commercial spam would destroy the group. (And
I'm not keen on flame wars either.) I've read the charter looking for
guidance on this topic.

| comp.graphics.algorithms is an unmoderated newsgroup
| intended as a forum for the discussion of the algorithms
| used in the process of generating computer graphics. These
| algorithms may be recently proposed in published journals or
| papers, old or previously known algorithms, or hacks used
| incidental to the process of computer graphics. The scope of
| these algorithms may range from an efficient way to multiply
| matrices, all the way to a global illumination method
| incorporating raytracing, radiosity, infinite spectrum
| modeling, and perhaps even mirrored balls and lime jello.

I've also found a link to CGAL there.

"Subject 0.07: Where is all the source?"

Siggraph proceedings are not free, nor jgt, nor the many books often
mentioned. Whenever possible, as with my recent link to the Mirtich
polyhedron moments article, I prefer to cite free online sources. It's
one of the great developments of the Web for the average citizen who
doesn't have access to good free technical libraries. Yet it is just
not practical to censor everything else.

Quote:>> But if you have a complaint, you will find at

>>   <http://www.cgal.org/Manual/doc_html/index.html>

>> that the manual preface states the following relevant information.
>> [...]

>I fail to see the relevance of your comment, including what is
>relevant about that information. My objection is with Andreas
>Fabri's repeated plugging of his for-sale product, not with the
>product itself.

I quoted from the preface for two reasons. First, you refer to CGAL as
if it were written by Fabri, calling it "his product". That is highly
misleading. I do not even know to what extent Fabri profits from any
licensing. Second, it gives an email address for complaints. Given the
originators of CGAL, I would expect them to take objections seriously.

Ideally code like CGAL would be free as in "free beer". Ideally Fabri
would post discussions of algorithms, not just links to CGAL. Both
those options are beyond my control. Given that a link to CGAL *is* in
the FAQ, what would you suggest the most helpful and least offensive
behavior of Fabri should be?

Can someone post a link to an article featuring a 3D Voronoi algorithm
that runs in O(n lg n) or whatever is
the most efficient ?
The literature points to Fang & Piegl 's 1995 method as being quite
efficient but I haven't seen it yet,
but whatever happened to Fortune's algorithm with the moving plane,
can't that work well in 3D ?

Unless someone feels like posting their IEEE Computer Society