Fastest Voronoi in 3D

Fastest Voronoi in 3D

Post by Andreas Fabr » Thu, 03 Jul 2003 16:49:10



Christer,

can you make a constructive suggestion instead of offending me.

It's a fact that CGAL covers some parts of computational geometry,
if you like it or not, so it is kind of natural to tell people
when they ask about availability of algorithm X or datastructure Y.

Also it is natural that I post about things I know. Just as Dave
Eberly posts about things he knows, that is I consider it as normal
that he sends people to have a look at his free code, but isn't
this free  code also kind of an adverti*t for his web site where
he sells things about or on top of his free code?

Would it make it any if the responsible for a certain CGAL
package posts, if the topic concerned his or her package?
Or may only happy users, who do not profit from license sales
recommend.

Also I am suprised that "free for academia" (and soon open source)
is not an argument at all for you. It's a nice coincidence that
at the same time as we exchange these mails, there is a question
whether ANN can be integrated into commercial products.

Best regards,

Andreas

 
 
 

Fastest Voronoi in 3D

Post by Christer Ericso » Thu, 03 Jul 2003 18:06:05




Quote:> [...]
> I really wish it was not encumbered with a commercial license.

Yes. Especially since (AFAIK) it is a product developed purely
through financial support of (presumably) state-funded academic
institutions. It's pretty sad when these institutions feel a
need to capitalize on research products ("because we can").

Quote:> 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.

Where do you (and _you_) draw the line then? If, say, these
people came here and posted about their products at every
opportunity:

http://www.cadlook.com/source.htm
http://www.eds.com/products/plm/parasolid/
http://www.smlib.com/

would that be OK? (They're all commercial products, with
"relevance" to this newsgroup.) Would this be okay if they
were free to legal residents in the US? What if they were
only free to the ~900 legal residents of Vatican City? Or
only free to me? (I'd still object, btw.)

Quote:> (And I'm not keen on flame wars either.)

Me either. I'm for principles though, especially noble ones.

Quote:> I've read the charter looking for
> guidance on this topic.

Believe it or not, I checked the charter myself before
posting (which doesn't say anything either way, typical of
charters, especially those created before the spam boom).
I also checked a number of netiquette guides on commercial
postings, which all frowned on them (where mentioned).

It thus comes down to whether you see it as plugging of
a commercial product or not. I do, you do not. However, I'm
interested to see your reply to the above, about where
you draw the line.

Quote:> First, you refer to CGAL as
> if it were written by Fabri, calling it "his product". That is highly
> misleading.

"His product", not as in written (entirely) by him, but as in
the product he is actively involved in selling and marketing
through the entity Geometry Factory, a company(?) with which
Fabri associates, is listed on the "About us" page of and
even is the assigned owner of the domain name for.

Quote:> Second, it gives an email address for complaints.

But that's silly. Analogously, if I had a beef with you, I
wouldn't go to your boss or your coworker to settle it; I'd
talk to you directly. The issue is here, thus I replied here.

Quote:> 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?

How about replying to the OP by email. That way the OP gets
helped, and no plugging of a commercial product is made on
the newsgroup.

Christer Ericson
Sony Computer Entertainment, Santa Monica

 
 
 

Fastest Voronoi in 3D

Post by Christer Ericso » Thu, 03 Jul 2003 18:27:05




Quote:> [...]
> can you make a constructive suggestion instead of offending me.

I'm sorry you feel offended, that was never my intent. What did
I say that offended you? Other than the judgement issue whether
your original post was spam or not, have I misrepresented
something?

Constructive suggestion at the end, and in the reply to Just
elsewhere.

Quote:> It's a fact that CGAL covers some parts of computational geometry,
> if you like it or not, so it is kind of natural to tell people
> when they ask about availability of algorithm X or datastructure Y.

The same argument would be used by any spammer plugging
commercial products in a forum relevant to the product.

Quote:> Also it is natural that I post about things I know. Just as Dave
> Eberly posts about things he knows, that is I consider it as normal
> that he sends people to have a look at his free code, but isn't
> this free  code also kind of an adverti*t for his web site where
> he sells things about or on top of his free code?

No, it isn't. First, Dave doesn't sell things on his website.
(I don't consider 3 links to Amazon selling things, but feel
free to disagree, I'm not gonna argue that.)

Second, if you follow the links he posts once in a while, they
take you to directly downloadable source code. No registration
needed. No commercial license fees. Nothing.

If you mean that people, through his quality postings, will
be tempted to visit his website to see what you can find there
and that that constitutes an adverti*t for his website,
well, yes, by some stretch of the imagination, I guess you
can call it that.

However, even so, there is nothing _commercial_ going on.
That's the key.

Quote:> Would it make it any [better] if the responsible for a certain CGAL
> package posts, if the topic concerned his or her package?

No, why would it? It's still a commercial product. Plugged
by the "seller".

Quote:> Also I am suprised that "free for academia" (and soon open source)
> is not an argument at all for you.

I'm equally surprised. Why would it be?

Quote:> It's a nice coincidence that
> at the same time as we exchange these mails, there is a question
> whether ANN can be integrated into commercial products.

The only coincidence I see is that both articles would have been
more appropriate as email postings than newsgroup postings.
Needless to say you see it somewhat differently or you wouldn't
have mentioned it, so, what coincidence do you see?

Christer Ericson
Sony Computer Entertainment, Santa Monica

 
 
 

Fastest Voronoi in 3D

Post by Gernot Hoffma » Thu, 03 Jul 2003 19:51:48





> > [...]
> > 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

Christer,

we dont have a national humor. In this case its "Hoffmanns Erz?hlungen".
Please dont take it seriously, but I thought its really funny that you
sign by "Sony" and tell others not to advertise.

Best regards  --Gernot Hoffmann

 
 
 

Fastest Voronoi in 3D

Post by Christer Erics » Fri, 04 Jul 2003 03:38:48



> [...]
> we dont have a national humor.

See, _that_ would have been funny if you'd left "a national" out.

Quote:> In this case its "Hoffmanns Erz?hlungen". Please dont take it
> seriously, but I thought its really funny that you sign by "Sony"
> and tell others not to advertise.

It would be ironic (but hardly funny) if I was advertising, but
I fail to see what am I advertising through my signature. (In fact,
some would argue, I'm sure, that I'm doing SCEA a disservice by
including the company name in my signature.)

Since you do not seem to know, signatures are traditionally used
to serve as an identifier and to provide contact information (and,
sadly, sometimes as a place where you put random junk).

In my case, while there aren't as many Christer Ericsons as there
are John Smiths, it's still there to make it clear I'm not one of
these Christer Ericsons:

http://www.ibra.se/kontakt/team_alla.html
http://www.svid.se/EcoDesign/konf_ima/index_b.htm
http://www.sahlgrenska.se/arbete/medarb/perfusionist.htm
http://www.aik.se/fotboll/aikindex.html?/fotboll/arena/sodrasprofiler...

As for you, what do I know, you might or might not be this
Gernot Hoffmann:

http://www.ghsoft.de/Team.htm

Your lack of signature doesn't tell. Perhaps, like Just, that's
the way you like it, which is fine with me.

Christer Ericson
Sony Computer Entertainment, Santa Monica

 
 
 

Fastest Voronoi in 3D

Post by Just d' FAQ » Fri, 04 Jul 2003 09:17:01




>Your lack of signature doesn't tell. Perhaps, like Just, that's
>the way you like it, which is fine with me.

What?! Am I not unique? I did a web search and the closest I came to a
clone was on the following site:

  <http://www.durangoclub.com/HomePage.htm>

;-D

One brief thought about the more serious discussion. In both business
and academia one must know the competition. Perhaps in lieu of posting
theory, Fabri could occasionally mention other sources. Folks who only
ever mention their own work cast doubt on that work, yes? :)

 
 
 

Fastest Voronoi in 3D

Post by Andreas Fabr » Fri, 04 Jul 2003 16:56:03





>>Your lack of signature doesn't tell. Perhaps, like Just, that's
>>the way you like it, which is fine with me.

> What?! Am I not unique? I did a web search and the closest I came to a
> clone was on the following site:

>   <http://www.durangoclub.com/HomePage.htm>

> ;-D

> One brief thought about the more serious discussion. In both business
> and academia one must know the competition. Perhaps in lieu of posting
> theory, Fabri could occasionally mention other sources. Folks who only
> ever mention their own work cast doubt on that work, yes? :)

and that's what I do (you may argue to a too limited extent)

http://groups.google.fr/groups?q=Fabri+group:comp.graphics.algorithms...

http://groups.google.fr/groups?q=Fabri+group:comp.graphics.algorithms...

http://groups.google.fr/groups?q=ANN+Fabri+group:comp.graphics.algori...

And it even happened to refer to ANN, when CGAL was already mentioned
by another posting

http://groups.google.fr/groups?q=ANN+Fabri+group:comp.graphics.algori...

andreas

 
 
 

Fastest Voronoi in 3D

Post by Chri » Fri, 04 Jul 2003 17:46:15



> 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

Hello
After days of surfing i found a comparison between the algorithms:
http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html
thank you all who answered me.
now i am surfing to find an implementation of the octree algorithm :)
chris
 
 
 

Fastest Voronoi in 3D

Post by Mick » Sat, 05 Jul 2003 02:00:20


Hmm.  So it looks like an incremental algorithm using
an octree for the point location wins.  Interesting.
Does anyone know how the randomized point location algorithm
given in:

ftp://ftp.cfar.umd.edu/TRs/CVL-Reports-1996/TR3621-Mucke.ps.gz

competes?

Mickey



> > 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

> Hello
> After days of surfing i found a comparison between the algorithms:
> http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html
> thank you all who answered me.
> now i am surfing to find an implementation of the octree algorithm :)
> chris

 
 
 

Fastest Voronoi in 3D

Post by Andreas Fabr » Sat, 05 Jul 2003 16:58:19


And before implementing the ocreee based search structure
you might read this:

Sunghee Choi and Nina Amenta.
Delaunay triangulation programs on surface data,
The 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pages 135-136.

andreas


> Hmm.  So it looks like an incremental algorithm using
> an octree for the point location wins.  Interesting.
> Does anyone know how the randomized point location algorithm
> given in:

> ftp://ftp.cfar.umd.edu/TRs/CVL-Reports-1996/TR3621-Mucke.ps.gz

> competes?

> Mickey



>>>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

>>Hello
>>After days of surfing i found a comparison between the algorithms:
>>http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html
>>thank you all who answered me.
>>now i am surfing to find an implementation of the octree algorithm :)
>>chris

 
 
 

Fastest Voronoi in 3D

Post by Just d' FAQ » Sat, 05 Jul 2003 18:11:20


On Fri, 04 Jul 2003 09:58:19 +0200, Andreas Fabri


>Sunghee Choi and Nina Amenta.
>Delaunay triangulation programs on surface data,
>The 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pages 135-136.

 :D
 
 
 

Fastest Voronoi in 3D

Post by Chri » Fri, 11 Jul 2003 16:33:39



> On Fri, 04 Jul 2003 09:58:19 +0200, Andreas Fabri

> >Sunghee Choi and Nina Amenta.
> >Delaunay triangulation programs on surface data,
> >The 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pages 135-136.

>  :D

Hi
Thank you for the help.
I didn't expected that somebody already made thoughts about the fast localisation.
Chris