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