[POVRay developers, please make sure to read part 2.3.]

Okay, let's come straightly to the point: 

Rendering complicated scenes can take ages, especially if you render 
animations. While this is often acceptable for the final rendering, it 
really has potential for improvement if you're just interested in 
a preview during modelling. 

Often, degrading quality (+Q0) is not an option because e.g. you need 
the shadow to better view the object orientation in space, etc. 

So, let's discuss a different idea (which I do not claim credit 
for [1]): 

The principle is to only render some pixels and calculate the color of 
other pixels using interpolation. 

I read some papers which indicate that (if done properly) speed can be 
increased by an order of magnitude while nearly not affecting quality 
(depending on the scene, of course). The stuff in question is called 
Directional Coherence Map.   [ Wow. Sounds cool, right? ;) ]

My first question is: Is somebody working on that for POVRay? 
Are there patches addressing this issue?

Being a passionate C/C++ programmer I thought that it is probably no 
good idea to wait until the POV Ray team implements something like that. 
So, I had a look at the source code myself two days ago. 

Let's come to the points which have to be discussed: 


1. (Mosaic) Preview: 

The current mosaic preview adds rendering time because the pixels 
rendered in the preview are not used in the final rendering. 
So, I think, one could use a fixed-grid (e.g. 8x8) bilinearly 
interpolated preview instead. This should be sufficient for a quick 
view of the image before actually rendering it and would produce 
nicer images than an 8x8 mosaic preview. 

I implemented that and it works fine. 


2. Actual image rendering:

The more interesting part. 
The easiest approch is to render every 8th pixel in X and Y direction. 
4 pixels ( (x,y), (x+8,y), (x,y+8), (x+8,y+8) ) build a block. If 
these four pixel differ less (in color) than a specified threshold, 
the whole 8x8 block is evaluated using bilinear interpolation. 

Else, the block is divided into 4 blocks of size 4x4 requiring that 
5 more pixels are rendered. Then, you subdivide into 2x2 and finally 
you render all the left pixels. 

This is what I implemented yesterday. To keep mem usage low, I am 
using a buffer of 9 image lines. The pixels rendered during the 
preview are stored in a separate width/8 x height/8 buffer and 
being re-used. [Dumb algo? - Read 2.3.]

However, there are several issues: 

2.1. First, the povray code structure: 

Some easy modifications would have to made (better control when 
plot_pixel() actually calls XPutImage() by adding a plot_flush(x,y,w,h) 
function, etc). 

More seriuos are: 

Prune_Vista_Tree()
  I don't know if it is speed critical but it has to be called much 
  more often, because 8x8 blocks are rendered sequentially which means 
  that the Y coordinate changes freqently. 

Do_Cooperate(). 
  Don't know when it should be called or if it can cope with the 
  situation. Could someone enlighten me on POVMS? It seems to deal 
  with "messages", "queues" and "objects" but I have no clue. 

Current_Line_Number and Current_Line. 
  These are global vars and the latter is hard to grep because of 
  the similarity with the first one. I don't use them as I use my 
  own line buffer (9 lines). 

Field_Render_Flag:
  Seems to be some strange thing skipping odd or even lines.  
  Probably not 100% incompatible but I currently see no reason for 
  supporting it. Maybe anyone has arguments [explain why useful]. 

Antialiasing:
  Not supported but there is currently not much point in it as we 
  are talking about rendering more quickly. 


2.2. Evaluation order:

I am currently rendering a rough preview and then rendering the image 
top to bottom, 8 lines at a time. This requires "only" 
9*width*sizeof(COLOUR) bytes of buffer memory. 8x8 blocks are computed 
sequentially. 

The other idea would be to keep the whole image im memory and execute 
the stages of the algorithm sequentially on the complete image. Nicer 
to look at but requires much more RAM (6 Mb for 640x480). No 
possibility to resume a half-done image. 


2.3. The algorithm itself:

As you probably guessed, I only explained the first step of the 
algorithm. After evaluating the 4 corer pixels one could render a 
complete rectangle border (32 pixels). Then apply the directional 
coherence map. 

However, after having rendered the 4 corner pixels, the main problem 
is to decide on how to go on. Using a checker plane, I currently get 
ugly 8x8 alias effects; objects like thin cones can be skipped 
completely (which is extremely annoing in animations). 

One idea would be to save which object had most influence on the 
color of the ray. If the 4 corner pixels come from different objects, 
do not interpolate immediately. 

Obviously, textures don't work well with the algorithm because they 
behave like fine detail. [2] suggests applying them afterwards but 
I doubt that this is feasible for povray. OTOH, you normally don't 
use lots of textures if you render a preview. 

MOST CRITICAL is the detection if there is more than one object 
inside the 8x8 block. A routine doing a quick test on that would 
come quite handy. Problems may occur with partial reflection or  
interior (ior) etc. but returning (false) positives for some parts 
of the scene is acceptable. Unfortunately, I am not familiar with 
the innermost workings of the POVRay "engine" so help is appreciated. 

[Hope someone is still reading this.] 

Regards,
Wolfgang

References:

[1] Baining Guo, Progressive Radiance Evaluation Using Directional 
      Coherence Maps, SIGGRAPH '98 Proceedings


Source code of my patch is delivered on request and may be used 
under the POV license as well as under the GNU GPL. 
It is not limited to 8x8 blocks but I used that here for 
simplicity. It is work in progress and far from complete but if 
anyone wants to comment on it i'll be happy.

Post a reply to this message

Wolfgang Wieser <wwi### [at] gmxde> wrote:
> Source code of my patch is delivered on request and may be used 
> under the POV license as well as under the GNU GPL. 

  You should be really careful here. Read povlegal.doc carefully to see
if you can do this.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

In article <3e3c4faa@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

> The principle is to only render some pixels and calculate the color of
> other pixels using interpolation.
>
> I read some papers which indicate that (if done properly) speed can be
> increased by an order of magnitude while nearly not affecting quality
> (depending on the scene, of course). The stuff in question is called
> Directional Coherence Map.   [ Wow. Sounds cool, right? ;) ]

In simpler terms: It is a kind of adaptive antialiasing on pixel blocks.

> My first question is: Is somebody working on that for POVRay?
> Are there patches addressing this issue?

None that I know about.

> 1. (Mosaic) Preview:
>
> The current mosaic preview adds rendering time because the pixels
> rendered in the preview are not used in the final rendering.

Yes.  I know it is intentional, but I do not know why.

> 2.1. First, the povray code structure:
>
> Some easy modifications would have to made (better control when
> plot_pixel() actually calls XPutImage() by adding a plot_flush(x,y,w,h)
> function, etc).

I assume XPutImage is some platform specific function.  I am not sure where
you are going here or what exactly you are talking about.  Please clarify.

> Do_Cooperate().
>   Don't know when it should be called or if it can cope with the
>   situation. Could someone enlighten me on POVMS? It seems to deal
>   with "messages", "queues" and "objects" but I have no clue.

POVMS is a way to abstract the different output streams and render control
in a way more suitable for GUI platforms.  It has nothing to do with the
actual ray-tracing core.  In future releases of the POV-Ray 3.5.x the other
means of handling output will be gradually removed and replaced by a
POVMS-only system with default code for command-line versions.

> Current_Line_Number and Current_Line.
>   These are global vars and the latter is hard to grep because of
>   the similarity with the first one. I don't use them as I use my
>   own line buffer (9 lines).

Some code depends on them.  So be careful, things may fail in unexpected
ways.

> Field_Render_Flag:
>   Seems to be some strange thing skipping odd or even lines.
>   Probably not 100% incompatible but I currently see no reason for
>   supporting it. Maybe anyone has arguments [explain why useful].

It is an easy way to create animations for interlaced display devices (aka
televisions).

> MOST CRITICAL is the detection if there is more than one object
> inside the 8x8 block. A routine doing a quick test on that would
> come quite handy. Problems may occur with partial reflection or
> interior (ior) etc. but returning (false) positives for some parts
> of the scene is acceptable. Unfortunately, I am not familiar with
> the innermost workings of the POVRay "engine" so help is appreciated.

The object found is always on the intersection stack, so you can use that.

    Thorsten

Post a reply to this message

Warp wrote:
> Wolfgang Wieser <wwi### [at] gmxde> wrote:
>> Source code of my patch is delivered on request and may be used
>> under the POV license as well as under the GNU GPL.
> 
>   You should be really careful here. Read povlegal.doc carefully to see
> if you can do this.
> 
Please explain the problem. 

I remember the paragraph 
"WHY ISN'T POV-RAY OPEN SOURCE ?" 
in povlega.doc, 

What I stated in these 2 lines just wants to express that my patch 
is covered by povegal.doc but there is no problem with my code if 
POVRay goes GPL.

Post a reply to this message

Thorsten Froehlich wrote:
> In article <3e3c4faa@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>
> wrote:
> 
>> The principle is to only render some pixels and calculate the color of
>> other pixels using interpolation.
>>
>> I read some papers which indicate that (if done properly) speed can be
>> increased by an order of magnitude while nearly not affecting quality
>> (depending on the scene, of course). The stuff in question is called
>> Directional Coherence Map.   [ Wow. Sounds cool, right? ;) ]
> 
> In simpler terms: It is a kind of adaptive antialiasing on pixel blocks.
> 
Kind of, yes. 
But the algorithm doing the adaption should be more clever than the 
current one and it is not about averaging supersample colors but 
guessing colors from fewer samples. 

>> 1. (Mosaic) Preview:
>>
>> The current mosaic preview adds rendering time because the pixels
>> rendered in the preview are not used in the final rendering.
> 
> Yes.  I know it is intentional, but I do not know why.
> 
One doesn't need a mosaic preview for the final rendering so there is no 
problem with additional time, I think. However, for a quick preview 
it would be nice to re-use the pixels like I do. 

>> 2.1. First, the povray code structure:
>>
>> Some easy modifications would have to made (better control when
>> plot_pixel() actually calls XPutImage() by adding a plot_flush(x,y,w,h)
>> function, etc).
> 
> I assume XPutImage is some platform specific function.  I am not sure
> where
> you are going here or what exactly you are talking about.  Please clarify.
> 
Okay the problem is simple:
Calling plot_pixel() should display the pixel on the screen (SVGAlib, X11 
or whatever). However, e.g. for X11, plot_pixel() just puts the pixel in 
offscreen storage and actually flushes the buffer once a complete image 
line was plotted (x coord == width-1) or some time elapses. 
Now, the problem is that I do not render lines from left to right, one 
at a time which breaks the simple update logic. 
So, I would introduce a flush function which explicitly tells 
the underlaying display routine to put some part on screen. For SVGAlib 
this would be a no-op. This would require a trivial one-line patch 
at two or three other positions where plot_pixel is used. 
Nothing really complicated. 

>> Do_Cooperate().
>>   Don't know when it should be called or if it can cope with the
>>   situation. Could someone enlighten me on POVMS? It seems to deal
>>   with "messages", "queues" and "objects" but I have no clue.
> 
> POVMS is a way to abstract the different output streams and render control
> in a way more suitable for GUI platforms.  It has nothing to do with the
> actual ray-tracing core.  In future releases of the POV-Ray 3.5.x the
> other means of handling output will be gradually removed and replaced by a
> POVMS-only system with default code for command-line versions.
> 
Okay, but when should I call Do_Cooperate()? And what does the param 
(int level) mean?
I always read something about "well documented" and "cleanly coded" 
patches to POVRay, so please look at povray.cpp (!)

/*****************************************************************************
*
* FUNCTION
*
*   Do_Cooperate
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*   
* AUTHOR
*
*   POV-Ray Team
*   
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

Sorry, but that's just [wasted] 312 bytes of source code telling 
essentially nothing just make it harder to keep an overview. 
[Don't want to start flame war and don't take that personally.]

>> Current_Line_Number and Current_Line.
>>   These are global vars and the latter is hard to grep because of
>>   the similarity with the first one. I don't use them as I use my
>>   own line buffer (9 lines).
> 
> Some code depends on them.  So be careful, things may fail in unexpected
> ways.
> 
I'll check that. 

>> Field_Render_Flag:
>>   Seems to be some strange thing skipping odd or even lines.
>>   Probably not 100% incompatible but I currently see no reason for
>>   supporting it. Maybe anyone has arguments [explain why useful].
> 
> It is an easy way to create animations for interlaced display devices (aka
> televisions).
> 
...and seems to do some sort of antialiasing?
I doubt it's worth the increased complexity for my patch, especially 
as most people probably watch previews on their computer screen. 
Maybe it can be added in the end. 

>> MOST CRITICAL is the detection if there is more than one object
>> inside the 8x8 block. A routine doing a quick test on that would
>> come quite handy. Problems may occur with partial reflection or
>> interior (ior) etc. but returning (false) positives for some parts
>> of the scene is acceptable. Unfortunately, I am not familiar with
>> the innermost workings of the POVRay "engine" so help is appreciated.
> 
> The object found is always on the intersection stack, so you can use that.
> 
...found in frame.h, struct istk_entry, struct istack_struct. 

So, if I understand you correctly, then the object hit by the ray 
is found on top of intersection stack (istk_entry.Object) 
once the ray is completely traced?
- How can I get access to the stack head. 
- What happens when the ray hits an object with 50% reflection? 
  (Thus the color of the pixel is determined by 2 objects.)
  How can I tell looking at the stack? 

The other point is that the algorithm would take most advantage if we 
can determine (quickly) if all the rays in the complete 8x8 _BOX_ hit 
the same object (without tracing the complete box). It's like shooting 
a ray with a diameter > 0. 
This way one can't leave out a horizontal 7 pixel thick cylinder which 
could currently be completely missed. 

How could one achieve that? It does not have to be 100% accurate, 
meaning that false positives are allowed (i.e. if we traverse an object 
with ior!=1). 

Wolfgang

Post a reply to this message

Wolfgang Wieser wrote:
> 
> >> Source code of my patch is delivered on request and may be used
> >> under the POV license as well as under the GNU GPL.
> >
> >   You should be really careful here. Read povlegal.doc carefully to see
> > if you can do this.
> >
> Please explain the problem.
> 
> I remember the paragraph
> "WHY ISN'T POV-RAY OPEN SOURCE ?"
> in povlega.doc,
> 
> What I stated in these 2 lines just wants to express that my patch
> is covered by povegal.doc but there is no problem with my code if
> POVRay goes GPL.

The thing Warp probably was trying to point out that there is no use in a
POV patch outside POV-Ray so the 'double licencing' is either not of any
use or tries to imply that POV-Ray with this patch can be distributed
under GPL which is not true.  It is very unlikely that POV-Ray will be
licenced under GPL anytime.

Another thing is that it would be more in the spirit of POV-Ray to make
the patch available without the necessity for a request.  Of course no one
forces you to publish your modifications at all but if you do they should
be freely available. 

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 31 Dec. 2002 _____./\/^>_*_<^\/\.______

Post a reply to this message

In article <3E3D0E3D.FFD75638@gmx.de> , Christoph Hormann 
<chr### [at] gmxde>  wrote:

> The thing Warp probably was trying to point out that there is no use in a
> POV patch outside POV-Ray so the 'double licencing' is either not of any
> use or tries to imply that POV-Ray with this patch can be distributed
> under GPL which is not true.  It is very unlikely that POV-Ray will be
> licenced under GPL anytime.

<offtopic>
In fact it will never be released under the GPL.  The GPL comes with a
political message that is not acceptable to all team members.  It certainly
isn't acceptable to me.
</offtopic>

    Thorsten

____________________________________________________
Thorsten Froehlich
e-mail: mac### [at] povrayorg

I am a member of the POV-Ray Team.
Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

Christoph Hormann wrote:
> Another thing is that it would be more in the spirit of POV-Ray to make
> the patch available without the necessity for a request.  Of course no one
> forces you to publish your modifications at all but if you do they should
> be freely available.
> 
No problem, I'm developing GPL software which can be downloaded by 
anyone, so it is also "in my spirit" to make it available. 
Just that it is highly experimental stuff...
So, I cleaned it up a bit. 

The patch is available at 
http://www.cip.physik.uni-muenchen.de/~wwieser/povray/

[Don't take the content of this "home page" seriously. Basically 
SOMETHING had to be put there...]

Please note that it patches povray in a way that it will always 
use my interpolated tracing -- no non-adaptive or adaptive tracing 
unless you change the lines in povray.cpp. 

Wolfgang

Post a reply to this message

In article <3e3d0765@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

> Okay the problem is simple:
> Calling plot_pixel() should display the pixel on the screen (SVGAlib, X11
> or whatever). However, e.g. for X11, plot_pixel() just puts the pixel in
> offscreen storage and actually flushes the buffer once a complete image
> line was plotted (x coord == width-1) or some time elapses.
> Now, the problem is that I do not render lines from left to right, one
> at a time which breaks the simple update logic.

Ah, but that is a platform specific problem.  So you should deal with
something like this in platform specific code and not add functions to
POV-Ray.  Just flush in plot_pixel or buffer calls to plot_pixel to flush
multiple pixels at once (in case you are concerned about performance).

> Okay, but when should I call Do_Cooperate()? And what does the param
> (int level) mean?

Look what the function does (it is really trivial) and then find out what
the macros inside do.  They are documented.

> I always read something about "well documented" and "cleanly coded"
> patches to POVRay, so please look at povray.cpp (!)

Well, guess how the code ended up in its current state ... you should really
think more about your argument before complaining.

> Sorry, but that's just [wasted] 312 bytes of source code telling
> essentially nothing just make it harder to keep an overview.

It is there so it can be added when somebody finds the time.  You are free
to go through the whole source code and document everything if you want ;-)

> ...and seems to do some sort of antialiasing?
> I doubt it's worth the increased complexity for my patch, especially
> as most people probably watch previews on their computer screen.

No, it just "skips lines".  Read the documentation about this feature to
find out more.

> So, if I understand you correctly, then the object hit by the ray
> is found on top of intersection stack (istk_entry.Object)
> once the ray is completely traced?
> - How can I get access to the stack head.
> - What happens when the ray hits an object with 50% reflection?
>   (Thus the color of the pixel is determined by 2 objects.)
>   How can I tell looking at the stack?

Basically yes, check function Trace, variable Best_Intersection.

> The other point is that the algorithm would take most advantage if we
> can determine (quickly) if all the rays in the complete 8x8 _BOX_ hit
> the same object (without tracing the complete box). It's like shooting
> a ray with a diameter > 0.

Beam tracing is not available in POV-Ray.

> This way one can't leave out a horizontal 7 pixel thick cylinder which
> could currently be completely missed.
>
> How could one achieve that? It does not have to be 100% accurate,
> meaning that false positives are allowed (i.e. if we traverse an object
> with ior!=1).

Not at all in a ray-tracer.

    Thorsten

Post a reply to this message

Wolfgang Wieser <wwi### [at] gmxde> wrote:
> Warp wrote:
>> Wolfgang Wieser <wwi### [at] gmxde> wrote:
>>> Source code of my patch is delivered on request and may be used
>>> under the POV license as well as under the GNU GPL.
>> 
>>   You should be really careful here. Read povlegal.doc carefully to see
>> if you can do this.
>> 
> Please explain the problem. 

  Your words seem to imply that your patched version of POV-Ray could be
published under the GNU GPL. As far as I know, that would be an outrageous
violation of the POV-Ray distribution license.
  If you didn't mean that, you should express yourself more clearly and
unambiguously.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message