I take the risk of appearing stupid, but is it possible to make the
assumption that if a ray hits an object, the rays next to it (next pixel
for example, or the next ray shot, or so ...) have a high probability to
hit the same object, thus avoiding useless tree-traversal and intersection
test? Would it be costful: if the test fails, then we go on with the normal
traversal with little overhead, and if success, we save a non neglectable
time?

Is it possible to collect ray-object intersection statistics while shooting
rays and intersecting, in order to make prediction?

    Bruno

Post a reply to this message

Bruno Cabasson nous apporta ses lumieres en ce 2007/09/21 09:18:
> I take the risk of appearing stupid, but is it possible to make the
> assumption that if a ray hits an object, the rays next to it (next pixel
> for example, or the next ray shot, or so ...) have a high probability to
> hit the same object, thus avoiding useless tree-traversal and intersection
> test? Would it be costful: if the test fails, then we go on with the normal
> traversal with little overhead, and if success, we save a non neglectable
> time?
> 
> Is it possible to collect ray-object intersection statistics while shooting
> rays and intersecting, in order to make prediction?
> 
>     Bruno
> 
> 
It may be worth investigating. The potential benefit would be largely scene 
dependent. May help in scenes containing hundreds to thousands of objects.

-- 
Alain
-------------------------------------------------
You know you've been raytracing too long when you can describe in perfect, 
legal, pov syntax, how to re-create everything in your computer room using 
primitives and csg operations.
fish-head

Post a reply to this message

Bruno Cabasson <bru### [at] alcatelaleniaspacefr> wrote:
> I take the risk of appearing stupid, but is it possible to make the
> assumption that if a ray hits an object, the rays next to it (next pixel
> for example, or the next ray shot, or so ...) have a high probability to
> hit the same object, thus avoiding useless tree-traversal and intersection
> test? Would it be costful: if the test fails, then we go on with the normal
> traversal with little overhead, and if success, we save a non neglectable
> time?

  Testing against the same object in the next pixel and getting a hit
doesn't tell us anything. There could be another object in front of
the object at that next pixel, so it would have to be tested anyways.

-- 
                                                          - Warp

Post a reply to this message

Alain <ele### [at] netscapenet> wrote:
> Bruno Cabasson nous apporta ses lumieres en ce 2007/09/21 09:18:
> > I take the risk of appearing stupid, but is it possible to make the
> > assumption that if a ray hits an object, the rays next to it (next pixel
> > for example, or the next ray shot, or so ...) have a high probability to
> > hit the same object, thus avoiding useless tree-traversal and intersection
> > test? Would it be costful: if the test fails, then we go on with the normal
> > traversal with little overhead, and if success, we save a non neglectable
> > time?
> >
> > Is it possible to collect ray-object intersection statistics while shooting
> > rays and intersecting, in order to make prediction?
> >
> >     Bruno
> >
> >
> It may be worth investigating. The potential benefit would be largely scene
> dependent. May help in scenes containing hundreds to thousands of objects.
>

This is in such scenes that ray-object intersection is costly. I think
POV-team members are likely to give an opinion. How could such a predictor
work for, say, a tree? Could it be adaptive? Can we imagine rules like:

   While in a csg object, if the previously predicted object is missed by
the ray, then try to traverse only the parent branch, and if still missed,
traverse the whole scene (or try a level further).

   Keep in memory a map of object/ray hits and exploit the info herein,
using local and global statistics.

   Etc ...

My knowledge in that is very poor, and I am absolutely not sure it's a good
idea... But who knows? Perhaps I am lucky with that (for once ;o))!


Bruno

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Bruno Cabasson <bru### [at] alcatelaleniaspacefr> wrote:
> > I take the risk of appearing stupid, but is it possible to make the
> > assumption that if a ray hits an object, the rays next to it (next pixel
> > for example, or the next ray shot, or so ...) have a high probability to
> > hit the same object, thus avoiding useless tree-traversal and intersection
> > test? Would it be costful: if the test fails, then we go on with the normal
> > traversal with little overhead, and if success, we save a non neglectable
> > time?
>
>   Testing against the same object in the next pixel and getting a hit
> doesn't tell us anything. There could be another object in front of
> the object at that next pixel, so it would have to be tested anyways.
>
> --
>                                                           - Warp

I am aware of that, of course. But what happens in our scenes? Does every
pixel concern a different object? Certainly not. What happens generally and
statistically? The case you mention (when the predicted object is occluded
for the next ray by another object) costs only one test, and the predictor
can be updated according to this new situation. In the worst case, we can
traverse the tree 'like usual'. Maybe someone intelligent (I am not), full
of math (I am not), and skilled in ray-tracing implementation concerns (I
am still not ....) could find something 'affordable'?

Bruno

Post a reply to this message

Bruno Cabasson <bru### [at] alcatelaleniaspacefr> wrote:
> I am aware of that, of course. But what happens in our scenes? Does every
> pixel concern a different object? Certainly not.

  But how can the program know that without actually testing for it?

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Bruno Cabasson <bru### [at] alcatelaleniaspacefr> wrote:
> > I am aware of that, of course. But what happens in our scenes? Does every
> > pixel concern a different object? Certainly not.
>
>   But how can the program know that without actually testing for it?
>
> --
>                                                           - Warp

As a first embryonic try for this idea, it might be enough to try to
intersect the previous object that was hit. If success, then time is saved;
if fail, go back to normal process, and no significant time was lost. I
think that statistically (I insist heavily on that word), we can gain
something because most of objects occupy an entire area of the scene, more
or less, even if they are plenty of them.

Bruno.

Post a reply to this message

Bruno Cabasson <bru### [at] alcatelaleniaspacefr> wrote:
> As a first embryonic try for this idea, it might be enough to try to
> intersect the previous object that was hit. If success, then time is saved;

  And again: That would miss an occluding object which was not hit the
last time but would be hit this time.

-- 
                                                          - Warp

Post a reply to this message

"Bruno Cabasson" <bru### [at] alcatelaleniaspacefr> wrote:
> thus avoiding useless tree-traversal and intersection
> test?

I think it's the wrong approach. I'd instead suggest an investigation along
these lines:

1. Is intersection-finding a major bottleneck in rendering "standard"
scenes?
2. Is POVRay's spatial partitioning algorithm far less than optimal?
3. Is POVRay's implementation of the spatial partitioning algorithm
inefficient?
4. If 1, 2 and 3 are true, which of the many well-established,
well-researched techniques in the published literature (much of which is
freely available on line) could be applied to resolve the matter?

If something besides intersection-finding slows down most scenes, then
clearly we can stop worrying about it right now. However, for that to be
the case would be a great surprise to me unless there is something
seriously wrong with the rest of the code.

Since (as far as I can see) the partitioning method used in 3.6 and earlier
is BVH, the answer to 2 is almost certainly yes. I think I saw something
about 3.7 supporting another subdivision method though.

I've been finding POV's BVH implementation quite difficult to read, so I
don't want to say anything about 3 yet.

My point with 4 is that we really don't need to spend effort thinking of
entirely new algorithms as in the first part of this thread. There are
loads that we could try. For example, ompf have a good collection of links,
most of which describe algorithms (ignore the hardware-specific stuff, they
are focussed on realtime):

http://ompf.org/forum/viewtopic.php?t=9


Thanks,

Tom

Post a reply to this message

Le 21.09.2007 15:18, Bruno Cabasson nous fit lire :
> I take the risk of appearing stupid, but is it possible to make the
> assumption that if a ray hits an object, the rays next to it (next pixel
> for example, or the next ray shot, or so ...) have a high probability to
> hit the same object, thus avoiding useless tree-traversal and intersection
> test? Would it be costful: if the test fails, then we go on with the normal
> traversal with little overhead, and if success, we save a non neglectable
> time?

That would be fine for a scanline renderer (excepted that I agree
with Warp on missing new intermediate objects), but that fail badly
for a raytracing renderer like povray: what about new rays created
for reflection & refraction ? Multiple reflections ? (just make a
nice pyramid of 10 reflective spheres, with some environment...like
a christmas tree...)

Whatever the solution for these issues, it might end up more
complexe and cpu-costly than the presentation of the idea. (you can
cache based on direction and origin of the ray, but that need to
define "near" for a 6 floating points arrays... and a criteria for
removing entries from the cache... searching the cache... cache
management could be more costly than the direct traversal of
bounding boxes...)

And I agree with Tom York too.

-- 
The superior man understands what is right;
the inferior man understands what will sell.
-- Confucius

Post a reply to this message