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