Hi,

I'm trying to find an efficient way to test all points within a set 
against each other. Quadtrees/octrees seem like the way to go, but... it 
appears that I need arrays containing vectors with other arrays mixed 
in. POV doesn't allow that sort of thing.

Would something like this work for quad/octrees?

#declare Array =
  array[2]{
   array[1]{
    <0,0,0>
   },
   array[2]{
    array[1]{
     <0,0,0>
    },
    array[1]{
     <0,0,0>
    }
   }
  }

Am I assuming the worst? What would be a good way to structure my data? 
Can it even be done in POV? This would be my first foray into using such 
data structures, so I'm totally lost here :(

~Sam

Post a reply to this message

stbenge <"egnebts <-inverted"@hotmail.com> wrote:
> I'm trying to find an efficient way to test all points within a set 
> against each other. Quadtrees/octrees seem like the way to go, but... it 
> appears that I need arrays containing vectors with other arrays mixed 
> in. POV doesn't allow that sort of thing.

  The current SDL isn't expressive enough to easily create such data
structures. The next SDL will have, if it ever comes to be, but until
them you'll just have to use arrays or use some scripting/programming
language to generate the scene.

-- 
                                                          - Warp

Post a reply to this message

On 3/31/2011 11:54 AM, Warp wrote:
> stbenge<"egnebts<-inverted"@hotmail.com>  wrote:
>> I'm trying to find an efficient way to test all points within a set
>> against each other. Quadtrees/octrees seem like the way to go, but... it
>> appears that I need arrays containing vectors with other arrays mixed
>> in. POV doesn't allow that sort of thing.
>
>    The current SDL isn't expressive enough to easily create such data
> structures. The next SDL will have, if it ever comes to be, but until
> them you'll just have to use arrays or use some scripting/programming
> language to generate the scene.

Argh, that's what I was afraid of :(

I'll keep looking into the matter...

Post a reply to this message

On 3/31/2011 12:15 PM, stbenge wrote:
> Argh, that's what I was afraid of :(
>
> I'll keep looking into the matter...

...and thanks for the reply, Warp!

Post a reply to this message

stbenge <"egnebts <-inverted"@hotmail.com> wrote:
> Hi,
>
> I'm trying to find an efficient way to test all points within a set
> against each other. Quadtrees/octrees seem like the way to go, but... it
> appears that I need arrays containing vectors with other arrays mixed
> in. POV doesn't allow that sort of thing.
>
> Would something like this work for quad/octrees?
>
> #declare Array =
>   array[2]{
>    array[1]{
>     <0,0,0>
>    },
>    array[2]{
>     array[1]{
>      <0,0,0>
>     },
>     array[1]{
>      <0,0,0>
>     }
>    }
>   }
>
> Am I assuming the worst? What would be a good way to structure my data?
> Can it even be done in POV? This would be my first foray into using such
> data structures, so I'm totally lost here :(
>
> ~Sam

When you say testing points against each other, what exactly are you trying to
do?  Find equal points?

-tgq

Post a reply to this message

> I'm trying to find an efficient way to test all points within a set 
> against each other. Quadtrees/octrees seem like the way to go, but... it 
> appears that I need arrays containing vectors with other arrays mixed 
> in. POV doesn't allow that sort of thing.

You might be better off exporting data from another programming
language. Also, how to proceed might depend on whether your main
focus is on non-intersection (where you only need to track close
neighbors) or gravity simulation (where you need to consider
points that are farther away as well. Better than efficient
tests is of course if you can avoid having to test each
point against every other point.

Your scene reminds me a bit of astronomical simulations for
star/galaxy formation and the likes. Their point counts are now
over the 10 billion makr (i.e. 10^10) ;) Typically these use
a hierarchical data structure, i.e. you group points into
clumps of matter and over longer distances only consider
the total attraction between increasingly larger clumps,
ignoring the constituent points.

Post a reply to this message

On 3/31/2011 12:33 PM, Trevor G Quayle wrote:
> stbenge<"egnebts<-inverted"@hotmail.com>  wrote:
>>
>> I'm trying to find an efficient way to test all points within a set
>> against each other.
>
> When you say testing points against each other, what exactly are you trying to
> do?  Find equal points?
>

Basically I want to find close neighbors. They don't even have to be the 
nearest ones for what I'm doing.

One case would involve placing spheres in 3D space without having any 
one sphere intersect another. I *could* simply reference all the points 
every time a point is added, but the parse time is compounded as new 
points are introduced.

In another case I would have a number of points generated from a mesh. 
For each point there would be a blob, and each blob would be subtracted 
by blob components based on close points.

For the second scenario I might take up Christian Froeschlin's idea of 
sorting everything along one direction and then just testing the array 
in a padded fashion. That would probably be the easiest implementation, 
but for higher-density point sets and blobs with large radii, it might 
not be very efficient.

Directional sorting has got to be better than what I'm doing now, though...

Sam

Post a reply to this message

On 3/31/2011 12:59 PM, Christian Froeschlin wrote:
>> I'm trying to find an efficient way to test all points within a set
>> against each other. Quadtrees/octrees seem like the way to go, but...
>> it appears that I need arrays containing vectors with other arrays
>> mixed in. POV doesn't allow that sort of thing.
>
> You might be better off exporting data from another programming
> language. Also, how to proceed might depend on whether your main
> focus is on non-intersection (where you only need to track close
> neighbors) or gravity simulation (where you need to consider
> points that are farther away as well. Better than efficient
> tests is of course if you can avoid having to test each
> point against every other point.

Currently all I want to do is find close neighbors. If I export that 
data I would probably have one array for the point vectors and another 
array as a list of pointers tracking said neighbors. I might even be 
able to use one of the Voronoi libraries, depending on how accessible 
the data is.

> Your scene reminds me a bit of astronomical simulations for
> star/galaxy formation and the likes.

The animation I posted was just an interesting side effect caused by a 
small adjustment. If I take it any further, I would keep the attractive 
force of each point localized, with a radius slightly larger than the 
repulsive force. In this way I could model certain fluids. I would then 
only really need to track the close neighbors...

> Their point counts are now
> over the 10 billion makr (i.e. 10^10) ;) Typically these use
> a hierarchical data structure, i.e. you group points into
> clumps of matter and over longer distances only consider
> the total attraction between increasingly larger clumps,
> ignoring the constituent points.

Wow, that sounds very interesting!

Post a reply to this message

Have a look at this thread from a few years ago

http://news.povray.org/povray.advanced-users/thread/%3C446b33a3@news.povray.org%3E/?ttop=356390&toff=300


-tgq

Post a reply to this message

"Trevor G Quayle" <Tin### [at] hotmailcom> wrote:
> Have a look at this thread from a few years ago
>
>
http://news.povray.org/povray.advanced-users/thread/%3C446b33a3@news.povray.org%3E/?ttop=356390&toff=300
>
>
> -tgq

Odd, link doesn;t show up in the web interface.

-tgq

Post a reply to this message