 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 4/5/2011 1:14 PM, Stephen wrote:
> On 05/04/2011 9:11 PM, Christian Froeschlin wrote:
>>
>> It wasn't a criticism, I was just frustrated that even
>> your test objects look better than what I get if I try
>> to render a stone ;)
>
> LOL I know what you mean. ;-)
You guys need to be less self-critical! (a critical statement if I ever
heard one ;) )
You've got to understand that 90% of my consciousness is taken up with
computer graphics-related ideas... It's makes it very difficult to live
like a normal person. My mind is uncontrollably expanding in all
directions, so I've got to direct into good paths. POV-Ray helps me to
do that :)
Sam
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 4/7/2011 4:57 PM, stbenge wrote:
> "It's makes"
^See what I mean? :(
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> > 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?
Pure function: f(y)= x^2 + z^2
> > 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.
>
No, I did it the difficult way: direct calculation of intersectiong lines then
intersecting points, then used the general x-y graphing to display it. A lot of
maths, that's why I only did it for a few points (3 or 4 I think it was)
> > 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.
It is only for a 2D array... The easiest way would be to get an image based on
it, from there it would be trying to convert that directly to a function or some
way to evaluate directly.
-tgq
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 08/04/2011 12:57 AM, stbenge wrote:
> On 4/5/2011 1:14 PM, Stephen wrote:
>> On 05/04/2011 9:11 PM, Christian Froeschlin wrote:
>>>
>>> It wasn't a criticism, I was just frustrated that even
>>> your test objects look better than what I get if I try
>>> to render a stone ;)
>>
>> LOL I know what you mean. ;-)
>
> You guys need to be less self-critical!
the troll king said. :-)
doubts, it is a tool for improvement.
(My tuppence worth)
(a critical statement if I ever
> heard one ;) )
>
LOL
> You've got to understand that 90% of my consciousness is taken up with
> computer graphics-related ideas... It's makes it very difficult to live
> like a normal person.
Time, is a thing that improves graphisc.
> My mind is uncontrollably expanding in all
> directions, so I've got to direct into good paths. POV-Ray helps me to
> do that :)
>
Personally, I find that PovRay helps to keep my mind flexible.
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Trevor G Quayle" <Tin### [at] hotmail com> wrote:
> > > 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?
>
> Pure function: f(y)= x^2 + z^2
>
> > > 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.
> >
>
> No, I did it the difficult way: direct calculation of intersectiong lines then
> intersecting points, then used the general x-y graphing to display it. A lot of
> maths, that's why I only did it for a few points (3 or 4 I think it was)
>
> > > 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.
>
> It is only for a 2D array... The easiest way would be to get an image based on
> it, from there it would be trying to convert that directly to a function or some
> way to evaluate directly.
>
>
> -tgq
Very simple demonstration of this concept.
-tgq
//START
camera {
orthographic
location <0, 3.5, 0>
look_at <0, 0, 0>
right x*1.2
up y*1.2
}
#declare C=0.001;//Flattens out paraboloid for viewing
#declare NumP=16;
#declare RS=seed(1);
#declare PT=array[NumP];
#for (i,0,NumP-1)//Pick random points <0,0,0>-<1,0,1>
#declare PT[i]=<rand(RS),0,rand(RS)>;
#end
union{
#for (i,0,NumP-1)
#declare xx=PT[i].x;
#declare zz=PT[i].z;
#declare V3=<-2*xx*C,1,-2*zz*C>*(pow(xx,2)+pow(zz,2))*C; //Paraboloid
surface normal at projected point
plane{V3,0 //plane oriented to normal
pigment{rgb i/NumP} //color by index
finish{ambient 0 emission 1 diffuse 0}
translate <xx,(xx*xx+zz*zz)*C,zz> // translate to projected point on
paraboloid
}
cylinder{0,y*(xx*xx+zz*zz)*C*1.1,0.01 //draw point
pigment{rgb <1,0,0>}
finish{ambient 0 emission 1 diffuse 0}
translate <xx,0,zz>
}
#end
translate <-0.5,0,-0.5>
}
//END
Post a reply to this message
Attachments:
Download 'voron.png' (17 KB)
Preview of image 'voron.png'
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 4/8/2011 6:55 AM, Trevor G Quayle wrote:
>
> Very simple demonstration of this concept.
>
Very interesting. I wonder how difficult it would be to make a list of
every point's nearest neighbors...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
stbenge <"egnebts <-inverted"@hotmail.com> wrote:
> On 4/8/2011 6:55 AM, Trevor G Quayle wrote:
> >
> > Very simple demonstration of this concept.
> >
>
> Very interesting. I wonder how difficult it would be to make a list of
> every point's nearest neighbors...
I don't know.
One thing that is certain is that for the object created, every cell will have a
unique normal that can be traced and they will be ordered in the sense that
adjacent cells will have the nearest normals.
-tgq
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
