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

Le 2011/03/31 20:54, Trevor G Quayle a écrit :
> "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
>
>
No problem on my side. Your link works good.


Alain

Post a reply to this message

Alain <aze### [at] qwertyorg> wrote:
> Le 2011/03/31 20:54, Trevor G Quayle a écrit :
> > "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
> >
> >
> No problem on my side. Your link works good.
>
>
> Alain

It's odd.  I've seen it recently on the web version.  The link isn't there in
the message, but does appear in the reply box (I can see it while typing this
response, but it won't be visible on the actual post).  Must be some html thing.

-tgq

Post a reply to this message

On 31.03.11 20:39, stbenge 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?

You can build trees with POV-Ray arrays indeed. Note that arrays inside 
arrays do not need to have the same size or dimension.

     Thorsten

Post a reply to this message

On 3/31/2011 5:54 PM, Trevor G Quayle wrote:
> "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
>>

That discussion is interesting; it is now bookmarked :) I may eventually 
use a hybridized technique based on some of those principles.

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

The web interface is a bit buggy sometimes...

Post a reply to this message

On 4/1/2011 4:12 AM, Thorsten Froehlich wrote:
> On 31.03.11 20:39, stbenge wrote:
>>
>> 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>
>>   }
>>  }
>> }
>>
>
> You can build trees with POV-Ray arrays indeed. Note that arrays inside
> arrays do not need to have the same size or dimension.

Right, I figured out that one :) I just can't mix objects, vectors, 
floats, other arrays, etc. together.

Do you think the above array structure would work for data trees though? 
Where each 1D array entry corresponds to a filled bucket? As I said 
before, I'm a total newbie when it comes to these things :(

Thanks Thorsten,

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.

Great suggestion, Christian! I spent the better part of yesterday doing 
just that.

The best option (and the most accessible) was to use voro++, a Voronoi 
library for C++. Now I can generate a list of nearest neighbors for each 
point, which will be useful for many things. In POV, testing the 
neighbors of 1024 points (even adding spheres to each point, cylinders 
between them) takes less than a second to parse! The calculations that 
the voro++ app itself performs take hardly any time at all. Of course to 
do this I now need to export my points from POV, run my application, and 
then run my scene file.

I may investigate the possibility of calling a batch file from within 
POV-Ray so I can perform calculations iteratively between frames. If I 
can do /that/, I can run a particle simulation with even more points 
than before :)

Sam

Post a reply to this message

stbenge wrote:

> I may investigate the possibility of calling a batch file from within 
> POV-Ray so I can perform calculations iteratively between frames.

You can also take the reverse approach and write a batch
file that executes generator and render as needed.

Post a reply to this message

On 4/3/2011 3:39 PM, Christian Froeschlin wrote:
> stbenge wrote:
>
>> I may investigate the possibility of calling a batch file from within
>> POV-Ray so I can perform calculations iteratively between frames.
>
> You can also take the reverse approach and write a batch
> file that executes generator and render as needed.

Whichever way works best.... I'll find out :)

I read that for some discrete element methods (DEMs) the 
neighbor-finding part needs to only be calculated once every few frames. 
I'm sure this has its consequences, but it would be a good way to save 
time. Unfortunately I have no idea how to do that... I might need to 
write an extra program just to generate batch files on-the-fly...

Post a reply to this message