Hi,

Happy new year to all !!

Recently looking (for curiosity) at acceleration structures, I am wondering how
would a relatively small complex object within a relatively large scene be
stored in an octree if centered (bbox includes origin). How would the object's
components be stored? Is a centered object stored at the root of the octree?
Some precisions would be welcome.

 Bruno.

Post a reply to this message

Am 07.01.2013 19:58, schrieb Bruno Cabasson:

> Recently looking (for curiosity) at acceleration structures, I am wondering how
> would a relatively small complex object within a relatively large scene be
> stored in an octree if centered (bbox includes origin). How would the object's
> components be stored? Is a centered object stored at the root of the octree?
> Some precisions would be welcome.

That would depend on how you'd align the octree with coordinate space.

The question is somewhat off-topic though, as POV-Ray does not use an 
octree for bounding. Instead, you have the choice between a hierarchy of 
bounding boxes (old mechanism), or a BSP tree with coordinate-aligned 
partition planes (almost a kd-tree, except that partition planes are 
chosen dynamically at every node).

AFAIK the only place where POV-Ray uses an octree is for storing 
radiosity samples.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 07.01.2013 19:58, schrieb Bruno Cabasson:
>
> > Recently looking (for curiosity) at acceleration structures, I am wondering how
> > would a relatively small complex object within a relatively large scene be
> > stored in an octree if centered (bbox includes origin). How would the object's
> > components be stored? Is a centered object stored at the root of the octree?
> > Some precisions would be welcome.
>
> That would depend on how you'd align the octree with coordinate space.
>
> The question is somewhat off-topic though, as POV-Ray does not use an
> octree for bounding. Instead, you have the choice between a hierarchy of
> bounding boxes (old mechanism), or a BSP tree with coordinate-aligned
> partition planes (almost a kd-tree, except that partition planes are
> chosen dynamically at every node).
>
> AFAIK the only place where POV-Ray uses an octree is for storing
> radiosity samples.

I was not asking specifically concerning POV-Ray, which I know for long it is
using BHV and more recently BSP. The question addressed those who might have an
advanced knowledge on ray-tracing techniques. I was just curious about what if a
complex object is at the center of the octants.

Post a reply to this message

Am 07.01.2013 23:42, schrieb Bruno Cabasson:

> I was not asking specifically concerning POV-Ray, which I know for long it is
> using BHV and more recently BSP. The question addressed those who might have an
> advanced knowledge on ray-tracing techniques. I was just curious about what if a
> complex object is at the center of the octants.

One possible approach to this dilemma would be to store objects in the 
octree not based on which smallest node they completely fit in, but file 
them in the smallest node that contains their center point and is big 
enough to fit half the object.

The drawback is that object lookup in such a tree would require to visit 
multiple branches.

This is actually how it's done in POV-Ray's radiosity sample tree.

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 07.01.2013 23:42, schrieb Bruno Cabasson:
>
> > I was not asking specifically concerning POV-Ray, which I know for long it is
> > using BHV and more recently BSP. The question addressed those who might have an
> > advanced knowledge on ray-tracing techniques. I was just curious about what if a
> > complex object is at the center of the octants.
>
> One possible approach to this dilemma would be to store objects in the
> octree not based on which smallest node they completely fit in, but file
> them in the smallest node that contains their center point and is big
> enough to fit half the object.
>
> The drawback is that object lookup in such a tree would require to visit
> multiple branches.
>
> This is actually how it's done in POV-Ray's radiosity sample tree.


Thanks for those informations. I have in mind to figure out what acceleration
techniques and structures are currenlty used by renderers and how they work :
spatial grids, BVH, BSP trees, octrees, k-d trees, and so forth ...

Post a reply to this message