 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] gmx de
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
|
|
| |
| |
|
|
|
|
| |
|
|
