On 4/7/2011 5:48 PM, Trevor G Quayle wrote:
> 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.

Yeah. Authors of such articles seem to only touch upon construction 
methods... What is the parabola exactly? A dense point curve or a pure 
function?

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

Wow, Excel uses Visual Basic, right? How did you view it? I always 
thought Excel's VB support was crudimentary, at best.

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

Dude, if you can do /that/, then you've made a full-POV-SDL 
implementation of Voronoi cell computation. It may not be the fastest 
way to go about it, but it's a step in the right direction.

I hope that one day POV-Ray will have some native method for computing a 
point set's nearest neighbors. Some fast core routine where the original 
authors gladly let their code fall under the new license. POV's use as a 
scientific visualization tool would surely increase...

~Sam

Post a reply to this message