AW: Constructing Power Diagrams (related to voronoi diagrams) with VisAD

• To: <visad@xxxxxxxxxxxxxxxx>
• Subject: AW: Constructing Power Diagrams (related to voronoi diagrams) with VisAD
• From: "Thomas Wenger" <wenger@xxxxxxxxxxxx>
• Date: Wed, 5 Jan 2005 08:26:39 +0100

Hi Bill,

cool - the page of Nina Amenta you found is the reason,
why I have to build power diagrams in 3D... :-)
I want to implement her "power crust" as a reconstruction method for surfaces
from unorganized point clouds.

The shown diagram there is a 2D example just to make
the concept of power diagrams clear. 

Power diagrams are weighted voronoi diagrams. This means,
that a site has an additional paramter how much influence
it has. The voronoi cell of a site is then of course
bigger if the weight of the site is bigger.

The dual of power diagrams are weighted (or regular) delaunay triangulations.

The main difference between normal and weighted triangulations are the different
metrics to measure the distance between two points.

So I think if one could make the metric abstract and pull the concrete
definition out of the code, one could calculate power diagrams.

I will see, if I can find out how this can be done.

Thank you for your help!

Greetings from Switzerland
Thomas 

> -----Ursprüngliche Nachricht-----
> Von: Bill Hibbard [mailto:billh@xxxxxxxxxxxxx]
> Gesendet: Dienstag, 4. Januar 2005 16:07
> An: Thomas Wenger
> Cc: visad@xxxxxxxxxxxxxxxx
> Betreff: Re: Constructing Power Diagrams (related to voronoi 
> diagrams) with VisAD
> 
> 
> Hi Thomas,
> 
> I googled "power diagram" and came up with:
> 
>   http://www.cs.utexas.edu/users/amenta/powercrust/tools.html
> 
> However, in the example figure they provide, they
> say the points are at the centers of the "balls"
> (I assume this means the circles) but the centers
> of the circles would not give the overlaid Voronoi
> diagram. If they did, I'd just say draw the Voronoi
> diagram then draw the circles.
> 
> Perhaps someone else knows more about power diagrams.
> 
> Good luck,
> Bill
> 
> On Tue, 4 Jan 2005, Thomas Wenger wrote:
> 
> > Hello VisAD users,
> >
> > I want to construct 3D Voronoi Diagrams from an
> > unorganized 3D point cloud. This can be done in
> > VisAD by first constructing the dual Delaunay
> > Triangulation and converting it.
> >
> > So far fine. But I should be able to construct
> > the so called "Power Diagram" of a 3D point
> > cloud as well. This is a "weighted Voronoi
> > Diagram". Voronoi Diagram and Power diagram
> > are related and it should be possible to construct
> > power diagrams with only little modifications
> > to the existing delaunay code.
> >
> > Does anybody know of how power diagrams can
> > be calculated with VisAD?
> >
> > Any hint is of great value. Thank you.
> >
> > Tom
> >
> >
> >
> 

• References:
  • Re: Constructing Power Diagrams (related to voronoi diagrams) with
    • From: Bill Hibbard