stbenge <"egnebts <-inverted"@hotmail.com> wrote:
> On 4/4/2011 1:57 PM, Trevor G Quayle wrote:
> > One interesting tidbit I had found about the Voronoi digrams when I had looked
> > at them a few years ago, is that they can be defined by projecting each point
> > vertically to a hyperboloid and defining a plane tangent to the hyperboloid at
> > this point.  The voronoi diagram of a set consists of the intersections of these
> > planes.
>
> I've read about using /parabolas/ (Fortune's algo) for the creation
> Voronoi cells, but am at a total loss about how to go about it. Your
> description seems clearer than Wikipedia's and Wolfram's. (did you  mean
> parabolas, not hyperboloids?)
>
> There's also the problem of using binary search trees. I haven't even
> tried to develop one yet, but like quad/octrees, their creation appears
> to be a very difficult undertaking. Maybe it's my frame of reference
> (POV) that is giving me trouble, or my total lack of formal math
> training. One of these days I'm going to need to have an understanding
> of such structures (if I ever expect to finish a video game :D).
>
> Sam

Sorry, perhaps it was paraboloid, it's been a while and I didn't look it up
first...

Odd , I can't find anything that relates the relationship so simply anymore at
present.  As you said, all the descriptions seem very complex to parse and
figure out the exact meaning.

The way I had understood it simply is to project the x-z plane point vertically
(y axis) onto the paraboloid and make a plane tangent to the paraboloid at that
point.  The voronoi digram for a given set of points will be represented by the
intersections of all the planes for that set.  I actually had set up some simple
mathematics to calculate this and display as a graph in excel at the time and it
seemed to work.

An interseting approach in POV would be to construct it directly in POV.  You
could take an array of each point and calculate the tangent plane for each
point, then create it as a plane object.  Give each plane a slightly different
colour value then do a simple intersection operation and view using orthographic
camera.  Using direct RGB values, you could theoretically create one for up to
16,777,216 (256^3) points (could probably do higher with HDR file type).  Of
course this would be only valid for a 2D set, and I'm not sure how render time
would be...  Perhaps it's time to test this out.

-tgq

Post a reply to this message