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

"Bruno Cabasson" <bru### [at] alcatelaleniaspacefr> wrote:
> 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.

I know nothing of how a ray-tracer works internally, so I may be spouting
nonsense, but I think you're on to something. The way I would do it is
based on the observation that the generic bounding box as seen in the
camera plane will appear as an irregular hexagon. I don't know how to save
an irregular hexagon, but if it can be done efficiently, then align
bounding boxes projection from furthest to the camera to closest, exactly
as it's done in splatting.
Just by using the trigonometry you'd save a significant number of rays.

Regarding tracing inside the box, if a ray gives a hit on the object, skip
the next both in up and side directions, and trace the second ray instead.
If it's a hit again, then assume the intermediate (skipped) ray is a hit
too. If it's a miss, then go back to the skipped ray and trace it.
I can already hear purists screaming to the top of their lungs that it's not
accurate, and I happen to agree, but since it appears we're writing the
wish-list of Pov 4, I might as well chime in. This method might be useful
for previews, quick tests, big renders and hopefully for real-time
raytracing. The final render would take the usual route, although that
should be up to the user.

Also the probabilistic thing you mention reminds me a lot of bayesian
statistics.

Post a reply to this message

> 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?

I believe this is already done for shadow rays. Shadow rays have the
advantage that once any (opaque) object is hit, we can stop and say the
point is in shadow. Normal rays, as Warp pointed out, still have to be
tested for other objects between the ray origin and the object that was hit
last time.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message