Right, well here's a question I bet none of you have ever been asked
before...........................

..............Why is raytracing so slow?

OK, so on the surface I know it probably sounds daft, but think about it...
They have graphics cards that can render polygon meshes in realtime - meshes
with just downright silly numbers of polygons in them - so why does it take
a raytracer a few whole *seconds* to render a single sphere with 1 light
source? OK, OK, because it's in software, not hardware, I know... but I
played Quake II for years without hardware acceleration. (Poor deprived
student... *sniff*) So I say again, WHY is raytracing slower?

Obviouse answer #1 is that the results are higher quality. For something
like Quake (insert Half Life, Unreal, Alien vs Predetor, etc. instead if you
prefer) all the game needs to do is work out where each polygon fits on the
screen, calculate lighting (without shaddows - at least *I* have never seen
a game with shaddows!) and map a texture onto it. With hardware acceleration
it usually does texture smoothing too. And perhaps even edge antialiasing.
But essentially, the overall lighting of the map is recomputed radiosity (at
fairly low res). Now, what does a raytracer do that means a graphics card
can map a dozen textures onto several hundred polygons and animate it at 30
FPS while a raytracer takes seeveral seconds for a scene with a single
sphere?

The only answer I've ever come across (and correct me if this is no longer
true) is that ray intersection tests take up as much as 90% of the
calculation time. (3D hardware uses Z-buffers and elaborate coherence
techniques to ensure it can operate on just the polygons that are visible on
each line, if I'm not mistaken.) So if you wanted to make a raytracer go
faster, reducing the number of ray intersection tests would be the place to
start, yes?

Is that or is that not what POV-Ray's vista buffer and light buffers are
designed to do? And would I be right in thinking that these don't apply to
reflection and refraction?

Thanks.
Andrew.

PS. If the above text doesn't appear to have a particular POINT to it...
what can I say? I need more sleep!

Post a reply to this message

In article <3ee33411@news.povray.org>,
 "Andrew Coppin" <orp### [at] btinternetcom> wrote:

> But essentially, the overall lighting of the map is recomputed radiosity (at
> fairly low res). Now, what does a raytracer do that means a graphics card
> can map a dozen textures onto several hundred polygons and animate it at 30
> FPS while a raytracer takes seeveral seconds for a scene with a single
> sphere?

It actually simulates the light travelling through the scene. And modern 
hardware can render a sphere + light source at a decent framerate.


> The only answer I've ever come across (and correct me if this is no longer
> true) is that ray intersection tests take up as much as 90% of the
> calculation time.

They can. Texturing calculations also account for a lot, especially with 
the more complex procedural textures, but the main reason raytracing is 
slower is that it traces the rays of light through the scene instead of 
projecting triangles onto an image plane and "painting" them onto the 
image with an image map stretched across them.


> (3D hardware uses Z-buffers and elaborate coherence
> techniques to ensure it can operate on just the polygons that are visible on
> each line, if I'm not mistaken.) So if you wanted to make a raytracer go
> faster, reducing the number of ray intersection tests would be the place to
> start, yes?

Correct. You can also reduce the time taken for intersections, for 
example by replacing a slow isosurface with a mesh. And you can bound 
expensive-to-calculate objects with simpler objects like boxes or 
spheres: if the ray doesn't hit the bounding shape, you know it can't 
hit the real shape so you can just skip those computations. You can then 
bound a group of these bounding shapes with another single bouding 
shape, ending up with a tree structure that eliminates a great number of 
unnecessary calculations. POV builds such a structure automatically, 
though manual bounding can still give better results in some cases.


> Is that or is that not what POV-Ray's vista buffer and light buffers are
> designed to do? And would I be right in thinking that these don't apply to
> reflection and refraction?

Correct. These techniques are useful when you have a lot of rays from a 
known location. Reflections and refractions spawn rays from anywhere in 
the scene, so they can't be optimized in this way. The bounding tree 
works no matter where the ray comes from, though.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

The simple answer is that raytracing has a large default overhead.
That is, any scene with any object will take a *minimum* of time, which
is relatively large.

  However, while the rendering time of a 3D card increases linearly with
the number of polygons, raytracing time grows about logarithmically
(supposing we have some bounding box hierarchy).
  That is, rendering 20000 triangles with a 3D card will take roughly twice
the time required to render 10000 triangles. However, raytracing 20000
spheres takes only some percents more than raytracing 10000 spheres
(you can try it with POV-Ray if you want).

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

In article <3ee33411@news.povray.org> , "Andrew Coppin" 
<orp### [at] btinternetcom> wrote:

> Why is raytracing so slow?

It is not slow.  You have to understand a very important area when dealing
with algorithms in computer science to understand why.  Actually, it isn't
too difficult if you paid attention in the advance math you had in the last
few years in high school:

The comparison of ray-tracing with scanline rendering is a bit to complex to
understand the general concept, so I will pick a well described example of
sorting algorithms.  Sorting is a very well studied problem in computer
science, and one that can very well described mathematically as well.  You
can read about it in any book about algorithms.

It is possible to show that you can sort every sequence of n elements in a
maximum of n lg n steps (this is oversimplified, see the book" Introduction
to Algorithms" for an detailed discussion).  Now, there is a common and
popular algorithm called quicksort, for which you always find an input
sequence which takes n*n steps to get sorted.  So why is everybody using
quicksort if it takes so much longer for (for a big n) than the best
solution possible?  Well, the worst-case runtime of an algorithm does not
necessarily say anything relevant about its average running-time.  And in
case of quicksort that time is still n lg n.

It can even be shown that you will always need at least n lg n steps to sort
a sequence if you need to compare elements in that sequence (that is if you
use sorting algorithms form the family of comparison sorts).  But does this
mean you cannot sort any sequence of elements in less than n log n steps?

No, you just have to use more information than just saying you have
"elements".  For example if you know your elements are integers from 1 to n,
there are algorithms which sort these in n steps!

> OK, so on the surface I know it probably sounds daft, but think about it...
> They have graphics cards that can render polygon meshes in realtime - meshes
> with just downright silly numbers of polygons in them - so why does it take
> a raytracer a few whole *seconds* to render a single sphere with 1 light
> source? OK, OK, because it's in software, not hardware, I know... but I
> played Quake II for years without hardware acceleration. (Poor deprived
> student... *sniff*) So I say again, WHY is raytracing slower?

It has nothing to do with software or hardware at all.  The fundamental
property, the runtime bounds, cannot be changed.  But there is two more
things you need to know that I didn't mention above.

Every step you need to sort takes time.  And, obviously, it depends on a lot
of things how long a step takes.  In fact, depending on the algorithm, a
step can be relatively slow or fast.

Another thing I did not mention so far is that you cannot use average
runtime to compare algorithms where the elements are dissimilar.  Or, more
complex, the runtime is a combination of several dissimilar elements.  And
this is why your assumption that ray-tracing "is slower" based on looking at
a simple scene is misguided.

For (simple) ray-tracing you have to test for all the m pixels each of the n
objects in the scene, so the runtime to render will be about m*n.  For
scanline rendering you have n objects which consist of t triangles which
consist of p pixels, which itself is m/q, where q is the share of each
triangle of the overall image (one that is counts all *drawn* triangle
pixels, not all visible triangle pixels, you need to draw pixels to
determine their visibility, usually many pixels over each other and
selecting the closes pixel).  So the runtime to render will be about n*t*p.

Notice something?  For ray-tracing the render-time is directly proportional
to the number of pixels in the image.  But for scanline rendering it is not.
On the other hand, for ray-tracing the number of objects is just one part of
the equation.

So, to say anything about these two algorithms, we do need the constant
factors, and this is where your "is slower" statement can be shown to be
relative.  That is, we say c1*m*n and c2*n*t*m/q, or lets say q is a
constant fact, i.e. each triangle contributes 1/10000 to the image, so
c2*n*t*m/10000, which is simply c2*n*t*m.  Further, we assume every object
consists of (very few) triangles, say 10.  So we get, after eliminating
constants, c2*n*m.

See, something about the runtime now?  By setting some constants we were
able to make the two equations comparable!  And they now take both the same
time.  But wait, there are these annoying constant factors.  It turns out
that c2 is much smaller than c1.  So this shows ray-tracing will always be
slower?  Well, yes and no.  It shows that the simple algorithm I presented
as "ray-tracing" will always be slower.  Lets pick up at the number of
objects in our ray-tracing runtime estimation again.  Do we really need to
test each and every object each and every time?

No!  There are various ways to optimise the finding of the closes object.
Lets consider a very simple algorithm:  Assume all objects are approximately
evenly  distributed in a specific volume in the scene.  So subdivide the
space in the scene into cubes (like a grid on paper, but 3d), with an
average number of q objects in each cube.  So you have r*r*r = n/q cubes.
Now, to find an intersection you only need to follow a line (the ray)
through these cubes, and only those cubes you touch need to be checked.  The
longest line in the space consisting of r*r*r cubes is sqrt(r*r*3), which in
turn is n^(1/3), as we again, ignore constant factors (because they don't
change their constness).

So now the ray-tracing runtime is c2*m*sqrt(n^(1/3)) = c2*m*n^(1/6).  If you
compare this to the scanline rendering runtime of c1*m*n, do you notice what
will happen, even if you assume c1 = 1000000 and c2 = 1?  You simply pick an
n, that is the number of objects, big enough and the runtime of the
ray-tracing algorithm will be smaller than that of the scanline algorithm.

The problem is, for the constants I suggested, you need a really big n.  So,
only if you have a really lot of objects, ray-tracing will be faster.

Analysing algorithm depends on defining a function of their runtime and the
comparing the growth of their functions.  And as you know from school, just
looking at one, or even many of samples of a function will not tell you
much, if anything about the growths of a function!

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3ee46215@news.povray.org> , "Thorsten Froehlich" 
<tho### [at] trfde> wrote:

> c2*m*sqrt(n^(1/3)) = c2*m*n^(1/6)

Ups, this should be c2*m*sqrt((n^(1/3))^2*3) and thus c2*m*n^(1/3), but it
does not change anything.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

Wow. Now that was a explicit and long answer. Nice job! :-)

-- 
Tim Nikias v2.0
Homepage: http://www.digitaltwilight.de/no_lights
Email: Tim### [at] gmxde

Post a reply to this message

Hey Thorsten

[Really long and nice answer]

Thank you for that wonderful explanation! It really helped me to understand
the subject properly.

Florian

Post a reply to this message

>   However, while the rendering time of a 3D card increases linearly with
> the number of polygons, raytracing time grows about logarithmically
> (supposing we have some bounding box hierarchy).

Mmm... that's a very interesting observation... I gotta try this...

Andrew.

Post a reply to this message

OK, OK, let me try again...

Comparing a raytracer to scanline rendering is not really a like-for-like
comparism. They work in very different ways. All I was trying to get at is
  1) for a scene complex enough to make up part of, say, a computer game,
software raytracing takes a lot longer than hardware scanline rendering, and
  2) what can you do to a raytracer to make it go faster?

Personally, I have yet to create a texture complex enough for it to have any
measureable effect on render time. But throw in a shape that's difficult to
do intersection tests on - isosurface, text, or even just a torus - and the
render time goes up by miles. (Also turning on reflection or refraction.)
Lighting also slows things down more than would seem reasonable - I presume
due to the extra shaddow tests (which require - yes - more intersection
tests).

But anyway... I too have spent hours pondering the enigma of sorting lists.
(I don't have access to the books with all the answers, so I have to
reinvent the wheel.) It's a toughy, innit?

Thanks.
Andrew.

PS. I downloaded the POV-Ray sources once... I still have no friggin idea
what a Sturmian root solver is!!! Oh well...

Post a reply to this message

> It actually simulates the light travelling through the scene. And modern
> hardware can render a sphere + light source at a decent framerate.

Yeah, I know how a raytracer works - I've built one ;-)

I'd be interested to see one go in realtime... (Actually, some of my Chaos
Pendulunm renders nearly had POV-Ray in realtime... I presume it's preview
window isn't designed with realtime performance in mind. It goes way faster
if I switch it off!)

> They can. Texturing calculations also account for a lot, especially with
> the more complex procedural textures, but the main reason raytracing is
> slower is that it traces the rays of light through the scene instead of
> projecting triangles onto an image plane and "painting" them onto the
> image with an image map stretched across them.

I've yet to see texturing have any significant effect on my renders...
Complex object geometry slows it to a crawl, as does excessive lighting, and
media (which is a whole OTHER kettle of fish - you could do media
simulations without a raytracer). But texturing has never seemed to have any
effect at all. (Until you turn on AA, or reflection/refraction, but these
are due to other effects.)

> Correct.

Yay!

> POV builds such a structure automatically,
> though manual bounding can still give better results in some cases.

...such as building polyhedrons out of planes using CSG? (I do this all the
time... *is* there any other way to build polyhedrons in POV?!?)

> > Is that or is that not what POV-Ray's vista buffer and light buffers are
> > designed to do? And would I be right in thinking that these don't apply
to
> > reflection and refraction?
>
> Correct. These techniques are useful when you have a lot of rays from a
> known location. Reflections and refractions spawn rays from anywhere in
> the scene, so they can't be optimized in this way. The bounding tree
> works no matter where the ray comes from, though.

The other night I convinced myself that voxels were the answer to all our
problems, and I was about to post a message damanding that it be implemented
immediately in the name of speed. Fortunately, I just happened to enguage my
brain first. And I realised that it's actually a pretty lame idea after all.
Glad I didn't post that suggestion!

Andrew.

Post a reply to this message

Thanks for that really long explanation!

If I understand right you say that both, a scanline algorithm and an 
unoptimized ray-tracing algorithm will take [image pixel] * [objects in 
scene] * [some constant factor] time (the objects could be triangles).

Then you explain how the raytracing algorithm could be optimized and 
compare it again with the (unoptimized!) scanline algorithm. Hmmm...

But couldn't the same (or other - e.g. octree) optimizations be applied 
to the scanline algorithm too?

Maybe I'm completely wrong, but doesn't your posting suggest that a 
raytracer will always outperform a scanline-renderer if just the number 
of objects is large enough?

I really don't want to start another scanline vs. raytracing flame-war 
here - each has its pros and cons which have already been discussed a 
million times - I just doubt that speed is a pro of raytracing...

Sascha

Thorsten Froehlich wrote:
> In article <3ee46215@news.povray.org> , "Thorsten Froehlich" 
> <tho### [at] trfde> wrote:
> 
> 
>>c2*m*sqrt(n^(1/3)) = c2*m*n^(1/6)
> 
> 
> Ups, this should be c2*m*sqrt((n^(1/3))^2*3) and thus c2*m*n^(1/3), but it
> does not change anything.
> 
>     Thorsten
> 
> ____________________________________________________
> Thorsten Froehlich, Duisburg, Germany
> e-mail: tho### [at] trfde
> 
> Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3ee4de11$1@news.povray.org>,
 "Andrew Coppin" <orp### [at] btinternetcom> wrote:

> I'd be interested to see one go in realtime... (Actually, some of my Chaos
> Pendulunm renders nearly had POV-Ray in realtime... I presume it's preview
> window isn't designed with realtime performance in mind. It goes way faster
> if I switch it off!)

Yes, the display routines are not intended to display a high framerate. 
The time taken to display the image is not long enough to bother 
optimizing though...what's a few hundred milliseconds when the render 
takes seconds, let alone minutes or hours?
In addition to that, parsing is pretty slow, especially when you're 
talking about doing real-time stuff.


> I've yet to see texturing have any significant effect on my renders...

Texturing and lighting can have a surprisingly large impact, though you 
can easily overpower it with some forms of geometry. One of my earliest 
patches was a depth buffer render mode...it was much faster than doing 
all the texture calculations, and I used it as a quick preview for a 
while. You could use the quality switches to cut out most of these 
calculations in the official version.


> > POV builds such a structure automatically,
> > though manual bounding can still give better results in some cases.
> 
> ...such as building polyhedrons out of planes using CSG? (I do this all the
> time... *is* there any other way to build polyhedrons in POV?!?)

Yes, that is one good example. POV can't bound an intersection of 
infinite shapes, you really need to manually bound when making 
polyhedrons that way. There are alternate methods: you could use boxes 
or meshes. An intersection of two boxes makes an efficient octahedron, 
and of course a box is the best way to do a cube.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <3ee4e321$1@news.povray.org> , sascha 
<sas### [at] userssourceforgenet>  wrote:

> Then you explain how the raytracing algorithm could be optimized and
> compare it again with the (unoptimized!) scanline algorithm. Hmmm...

I knew somebody would ask, but answering it right along would have made a
long post even longer :-)

No, the problem is, you cannot optimise the scanline algorithm further than
what I outlined (at least not bringing down the complexity).  In fact, the
complexity I outlined holds for the first implementations 30 or so years ago
and it still holds in the 3d hardware accelerators of today.  The main
benefit of the scanline algorithm is that you can make the constant time
factor very, very small compared to ray-tracing.

> But couldn't the same (or other - e.g. octree) optimizations be applied
> to the scanline algorithm too?

No, because the scanline algorithm requires you to draw everything in the
viewing area to determine its visibility.  You can cull backfacing
triangles, but that only divides to constant factor by about two.

> Maybe I'm completely wrong, but doesn't your posting suggest that a
> raytracer will always outperform a scanline-renderer if just the number
> of objects is large enough?

Yes, it does.  The problem is, the one million to one difference of the
constant factors.  And due to the simplicity of the scanline algorithm, it
is, compared to ray-tracing, much easier to implement it in hardware (you
need only a few thousand gates, most of the logic on today's accelerator
chips is used for texture and geometry computations.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

> I knew somebody would ask, but answering it right along would have
 > made a long post even longer :-)

Well, with all your privious posts you gave the impression that you 
enjoy writing long posts :-)

Just one more stupid question: Are you talking about hardware-scanline 
renderers (OpenGL and the like) only or about REYES too? As far as I 
understand REYES is more related to scanline than raytracing and is in 
fact highly optimized to render huge amounts of primitives.

There are some test results and analysis about its time-complexity here: 
http://www.cis.ohio-state.edu/~stuart/cis781/final.html

[And again: I'm not trying to say that REYES is "better" than raytracing]

 > No, because the scanline algorithm requires you to draw everything in
 > the viewing area to determine its visibility.

I agree with you that raytracing would be the winner if there were *a 
lot* of primitives which appear smaller than a single pixel so that 
their bounding-boxes will never get hit by a ray - but usually both, 
REYES and game-engines use some sort of level-of-detail optimizations to 
prevent this scenario...

sascha

Thorsten Froehlich wrote:
> In article <3ee4e321$1@news.povray.org> , sascha 
> <sas### [at] userssourceforgenet>  wrote:
> 
> 
>>Then you explain how the raytracing algorithm could be optimized and
>>compare it again with the (unoptimized!) scanline algorithm. Hmmm...
> 
> 
> I knew somebody would ask, but answering it right along would have made a
> long post even longer :-)
> 
> No, the problem is, you cannot optimise the scanline algorithm further than
> what I outlined (at least not bringing down the complexity).  In fact, the
> complexity I outlined holds for the first implementations 30 or so years ago
> and it still holds in the 3d hardware accelerators of today.  The main
> benefit of the scanline algorithm is that you can make the constant time
> factor very, very small compared to ray-tracing.
> 
> 
>>But couldn't the same (or other - e.g. octree) optimizations be applied
>>to the scanline algorithm too?
> 
> 
> No, because the scanline algorithm requires you to draw everything in the
> viewing area to determine its visibility.  You can cull backfacing
> triangles, but that only divides to constant factor by about two.
> 
> 
>>Maybe I'm completely wrong, but doesn't your posting suggest that a
>>raytracer will always outperform a scanline-renderer if just the number
>>of objects is large enough?
> 
> 
> Yes, it does.  The problem is, the one million to one difference of the
> constant factors.  And due to the simplicity of the scanline algorithm, it
> is, compared to ray-tracing, much easier to implement it in hardware (you
> need only a few thousand gates, most of the logic on today's accelerator
> chips is used for texture and geometry computations.
> 
>     Thorsten
> 
> ____________________________________________________
> Thorsten Froehlich, Duisburg, Germany
> e-mail: tho### [at] trfde
> 
> Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3ee5a9ca@news.povray.org> , sascha 
<sas### [at] userssourceforgenet>  wrote:

> Well, with all your privious posts you gave the impression that you
> enjoy writing long posts :-)

They take a real lot of time, and I usually have a lot more things to do
that end up having to wait :-(

> Just one more stupid question: Are you talking about hardware-scanline
> renderers (OpenGL and the like) only or about REYES too?

It is still a scanline algorithm.  It simply uses a different subdivision
method to turn objects into triangles.  As the triangle size will be a
constant factor or some kind, it does not change the complexity.

> There are some test results and analysis about its time-complexity here:
> http://www.cis.ohio-state.edu/~stuart/cis781/final.html

Hmm, it says O(n*4^p/g) and g being "somewhat constant", which would suggest
the complexity really is O(n*4^p), or O(n*4^m) using the variable names I
used.  It would only make sense if g > p would always be true, and the
authors imply the best case will be g =< p.

Thus, I don't think this makes sense because it implies that the average
case, and not only the upper bound, is also n*4^m, which would make the
problem not solvable in polynomial time!  But I didn't read the whole paper,
maybe I missed something important ... Warp?

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3ee5829b$1@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> No, the problem is, you cannot optimise the scanline algorithm further than
> what I outlined (at least not bringing down the complexity).  In fact, the
> complexity I outlined holds for the first implementations 30 or so years ago
> and it still holds in the 3d hardware accelerators of today.  The main
> benefit of the scanline algorithm is that you can make the constant time
> factor very, very small compared to ray-tracing.

You could probably do something somewhat similar to bounding...do an 
assay render on the bounding box of a group of triangles. If it would 
have been drawn, fully render the individual triangles, if it would not 
have been drawn then ignore them. Probably not as efficient as in 
raytracing, but it could work...I don't see a way to get it to work with 
hardware accelerated rendering though, unless there's a way to check if 
the depth buffer would have been modified without actually modifying it. 
You could save/render/compare/restore, but that'd probably take longer, 
especially on large resolutions.


> Yes, it does.  The problem is, the one million to one difference of the
> constant factors.  And due to the simplicity of the scanline algorithm, it
> is, compared to ray-tracing, much easier to implement it in hardware (you
> need only a few thousand gates, most of the logic on today's accelerator
> chips is used for texture and geometry computations.

It can also be done easily with integer math, while raytracing requires 
floating point...even 64 bits isn't enough for practical fixed point 
raytracing. This lets the logic be simplified, cutting development costs 
and allowing higher speeds to be attained more easily.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <3ee5a9ca@news.povray.org>,
 sascha <sas### [at] userssourceforgenet> wrote:

> I agree with you that raytracing would be the winner if there were *a 
> lot* of primitives which appear smaller than a single pixel so that 
> their bounding-boxes will never get hit by a ray - but usually both, 
> REYES and game-engines use some sort of level-of-detail optimizations to 
> prevent this scenario...

The shapes don't need to appear smaller than a pixel, they just need to 
have another shape be hit in front of their bounds so the bounded shape 
isn't tested. If you have a lot of shapes partially or totally obscured 
by other shapes, raytracing gets better by testing fewer shapes while 
scanlining stays about the same, having to draw the same number of 
triangles and shade the same number of pixels.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <cja### [at] netplexaussieorg> , 
Christopher James Huff <cja### [at] earthlinknet>  wrote:

> You could probably do something somewhat similar to bounding...do an
> assay render on the bounding box of a group of triangles.

No, because you would have to be able to keep multiple levels.  A bounding
box is bigger than the actual geometry.  So only looking at the frontmost
bounding box isn't enough.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3ee5f3e7@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> > You could probably do something somewhat similar to bounding...do an
> > assay render on the bounding box of a group of triangles.
> 
> No, because you would have to be able to keep multiple levels.  A bounding
> box is bigger than the actual geometry.  So only looking at the frontmost
> bounding box isn't enough.

I don't think you understood what I meant. Draw from front to back. Use 
single bounding boxes for closely spatially related groups of triangles, 
maybe with an oct-tree structure. If the bounding box of a group is 
occluded by triangles that have already been drawn (it has no pixels at 
lesser depth), all those triangles are also occluded, so no need to draw 
them. I'm assuming no alpha-style transparency, because you mentioned 
backside culling. Nothing to do with the frontmost bounding box, except 
that you could skip the test for the frontmost few levels because they 
are so unlikely to be occluded.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

I've just read a paper which states that real-time ray-tracing might become
doable on the next generation GPUs using their fragment shaders:

Ray Tracing on Programmable Graphics Hardware - Purcell et al., SIGGRAPH
2002
http://graphics.stanford.edu/papers/rtongfx/

- Micha


-- 
POV-Ray Objects Collection: http://bjects.povworld.org

Post a reply to this message

> Yes, the display routines are not intended to display a high framerate.
> The time taken to display the image is not long enough to bother
> optimizing though...what's a few hundred milliseconds when the render
> takes seconds, let alone minutes or hours?

Yeah, entirely as I expected.

> In addition to that, parsing is pretty slow, especially when you're
> talking about doing real-time stuff.

Mmm... that's true... I wonder how much time the actual physics simulation
took up? hehehe

> > ...such as building polyhedrons out of planes using CSG? (I do this all
the
> > time... *is* there any other way to build polyhedrons in POV?!?)
>
> Yes, that is one good example. POV can't bound an intersection of
> infinite shapes, you really need to manually bound when making
> polyhedrons that way.

...and remember to tell POV-Ray *not* to remove them ;-)

> There are alternate methods: you could use boxes
> or meshes. An intersection of two boxes makes an efficient octahedron,
> and of course a box is the best way to do a cube.

Usually I just want to build million-sided mirror balls or gemstones or
such... and I don't like meshes. Somehow seems like a "trick". (OK, I'm
weird!)

Thanks.
Andrew.

Post a reply to this message

Micha Riser <mri### [at] gmxnet> wrote:
> I've just read a paper which states that real-time ray-tracing might become
> doable

  "Real-time raytracing" is not an unambiguous term.
  There have been real-time raytracers in the mid-90's for the first Pentium,
so in that sense that's old news. It doesn't *become* doable because it
has been doable for over 5 years.

  All this comes down to how we really want to define "realtime raytracing".
What kind of frame rates, scene complexity and image resolution is enough
to satisfy the conditions?

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Thorsten Froehlich wrote:

> In article <3ee4e321$1@news.povray.org> , sascha
> <sas### [at] userssourceforgenet>  wrote:
> 
> No, the problem is, you cannot optimise the scanline algorithm further
> than
> what I outlined (at least not bringing down the complexity).  In fact, the
> complexity I outlined holds for the first implementations 30 or so years
> ago
> and it still holds in the 3d hardware accelerators of today.  The main
> benefit of the scanline algorithm is that you can make the constant time
> factor very, very small compared to ray-tracing.
> 
>> But couldn't the same (or other - e.g. octree) optimizations be applied
>> to the scanline algorithm too?
> 
> No, because the scanline algorithm requires you to draw everything in the
> viewing area to determine its visibility.  You can cull backfacing
> triangles, but that only divides to constant factor by about two.

Well, there is further optimisation possible: view-frustum culling and
occlusion culling. You can determine on the CPU (using some Bounding Volume
Hierarchies) which groups of triangles are not visible from the viewpoint.
For example a scene in a house you can quickly determine which rooms one
sees into at all and which you don't. So there is no need to move these
triangles down the rendering pipline. Of course this triangle exculsion is
only an conservative estimation and no exact solution.

Another interesting thing to think about is: Why do we use triangles? As
today there are often tens of triangles per pixel in a detailed model one
doesn't really need the full triangles. So another idea is to stick to
points and not store the interconnections of the points but only the points
assosiated with a normal and a texture. This reduces the memory
requirements. For the rendering you draw either a small box for each point
(which is supported by todays GPUs) or more exact a small ellipse. Using
points as basing privmitives has another advantage: You can quickly
generate different LODs of models (which is much slower for triangle
meshs), so you can use a reduced-point version when an object is farther
away.

That this actuallly works can be seen in the video from:
http://www9.informatik.uni-erlangen.de/Research/Rendering/SPT

- Micha

-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

Warp wrote:

> Micha Riser <mri### [at] gmxnet> wrote:
>> I've just read a paper which states that real-time ray-tracing might
>> become doable
> 
>   "Real-time raytracing" is not an unambiguous term.
>   There have been real-time raytracers in the mid-90's for the first
>   Pentium,
> so in that sense that's old news. It doesn't *become* doable because it
> has been doable for over 5 years.

I know that it has been made on CPUs already.. but, if you had properly
quoted my statement it would say:

"I've just read a paper which states that real-time ray-tracing might become
doable on the next generation GPUs using their fragment shaders:"

so the new thing is that it's getting possible on the standard GPUs.

- Micha


-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

In article <3ee6649f@news.povray.org>, Micha Riser <mri### [at] gmxnet> 
wrote:

> Another interesting thing to think about is: Why do we use triangles? As
> today there are often tens of triangles per pixel in a detailed model one
> doesn't really need the full triangles. So another idea is to stick to
> points and not store the interconnections of the points but only the points
> assosiated with a normal and a texture. This reduces the memory
> requirements. For the rendering you draw either a small box for each point
> (which is supported by todays GPUs) or more exact a small ellipse. Using
> points as basing privmitives has another advantage: You can quickly
> generate different LODs of models (which is much slower for triangle
> meshs), so you can use a reduced-point version when an object is farther
> away.

Point fields can be raytraced as well...there's an algorithm that 
basically uses a disc for each point, intersecting with several nearby 
discs and interpolating normals and intersection points. I've been 
working on an implementation, but it isn't even rendering plain discs 
yet.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message