Nav:  [home][render][povray][patches] > [prt-patch]
 
← [What are these? Why?]

Progressive Refinement Patch for POVRay

The PRT patch draws a progressively refining bilinearly interpolated preview and enables you to select regions to be traced by POVRay using the mouse. Patch against UNIX POVRay-3.6.1.

Local: [News] [Idea] [Implementation] [Description] [Purpose] [Download] [Usage] [Overhead] [Examples]

News

08/2004: Version 1.0 for POVRay-3.6.1
Overhauled documentation and description on this site (including some content fixes). Minor code change and ported code to POVRay-3.6.1 (now version 1.0); also fixed a color distortion bug.
07/2004: Version 0.98 for POVRay-3.6:
Ported patch to POVRay-3.6. Verified to support radiosity and photons. Source code cleaned up and split into several files. Memory footprint reduced again (trace flag now has 2bits instead of 2 bytes).
2003: New im version 0.95:
Key 'q' can be used to abort render saving the current image.
Memory footprint of tile hash reduced.

The idea...

The idea behind PRT is quite simple: Those regions of an image which have a higher color variation are normally the more interesting parts while the ones with little color variation can easily be interpolated. This sounds a bit like the IPT patch written by me, but in contrast to IPT, PRT will have traced all pixels in the end and thus deliver the same image as normal POVRay.

So, PRT will first trace a grid of typically 12x12 pixels and display a bilinearly interpolated preview. It will now go on and sub-divide these 12x12 tiles and thus progressively refining the preview. The major trick is, that those tiles which have the largest color variation get refined first.

Furthermore, the user may manually tell the PRT patch which parts to trace first by pressing (and possibly dragging) the mouse in the POVRay window.

In the end, each pixel of the image was traced exactly once (and no additional pixels were traced).

...and the implementation

PRT requires that the complete image is held in core memory. While this is also true for the standard POVRay X11 display, PRT needs to store the image in better quality than 24 bit RGB. Currently, the image is stored using 6.25 bytes per pixel which includes 16 bit per color channel and a 2 bit (not byte) trace flag. Furthermore, the tile heap must be stored; each tile normally occupies 16 bytes on a 32-bit box.

It is clear that PRT cannot write the image data to file before the image is completely rendered. As a consequence, I decided that PRT should save the current image (i.e. with interpolation) in case it is aborted (using e.g. Control-C). Consequently, you cannot continue aborted traces.

Detailed description

The image is divided into tiles, initially normally of size 12x12. Each tile has the egde pixels traced (3 of the 4 traces egde pixels actually belong to neighbouring tiles unless the tile hits the viewport border). Using the color values of these 4 pixels, the complete tile can be be bilinearly interpolated. The standard deviation of the color of these 4 pixels (summed up over all color channels) together with a tile size factor make up the interest value. All tiles get pushed on a heap.

The main rendering loop (after the initial pass) takes the most interesting tile from the heap and divides it along the longer border into two sub-tiles. Each sub-tile has the 4 border pixels rendered (3 of these are again actually outside the tile...), is re-displayed with updated interpolation and then inserted into the heap again. In case the tile is too small (less than 4x4 normally), it is not divided but instead traced completely and removed from the heap. Tracing is over when no tile is left in the heap.
Note that no pixel is ever rendered if it already was rendered. Interpolated pixels will never overwrite traced ones.

You may click on some position in the window and thus have a region around the mouse position traced. The size of the region depends on the mouse button (normally 16,32,64 for buttons 1,2,3). What internally happens is that the tile gets added to a list of manually generated tiles.
In case you drag the mouse while a button is pressed, more tiles will be added to the manual list.
The manual refinement applies a clever algorithm: If you add a tile while another manual tile is traced, tracing will immediately continue in the new tile. Once the new tile is done, PRT will go on with the older one. If no manual tiles are left, usual refinement is continued. Note, however, that the manual tile "memory" is limited to usually 32 tiles; i.e. if you order more than these many manual tiles, it will forget about the oldest ones and leave them partly traced. But this is exactly what you want and in the end the complete image will always be traced.
In case you move the mouse with a button pressed, a new tile is only added if either there is no one left in the manual list or you moved the mouse a distance which is larger than half the current manual tile size (which depends on the button pressed).
Note that any manually-ordered tile is updated every 300 msec while being traced.

What is it good for?

PRT should enable you to see the interesting parts of the image more quickly.
Hence, PRT is designed to be an aid when designing a scene.
Consequently, it does not support anti-aliasing (rediosity and photons should, however, work as usual). The image data buffer and tile heap consume memory which is proportional to the size of the image but that is no problem as you are using small images during design. You cannot resume aborted traces but that is normally not needed during design.

Bugs:
Transparency and filter values are not stored in the PRT image buffer (are they needed at all??).

Download and Install

Download: PRT can only be obtained as patch against UNIX POVRay-3.6.1.
I will neither provide binaries nor port that patch to any other platform. If you want to do so, please contact me.

Source: prt-patch.diff   [56kb patch diff]
Version:1.0   (2007-04-04)
Author:Wolfgang Wieser   (report bugs here)
License:POVRay license (povlegal.doc)

Install: First, patch your POVRay-3.6.1 using patch(1).
Then, you may adjust the tuning variables in prt_render.cpp right after all the #includes. It is safe to leave them untouched.
Finally, run automake because the Makefile.am was changed by the patch.
Finally, compile POVRay as usual. You may need to replace powf() and sqrtf() by pow() and sqrt() if your system lacks the float variants of these functions.

Activate: The PRT-patched POVRay will behave exactly like the non-patched. To enable PRT, pass +AM4 on the command line.

Usage (important)

PRT is easy to use. In ordet to enable it, you have to pass +AM4 on the command line.

During rendering, it knows the following keys and buttons:

  • Key 't': Toggle between displaying traced and interpolated and traced only pixels. For traced-only pixels, the background will be a dark grey and black checker.
  • Buttons 1,2,3: Manually add tile to be traced immediately; size depends on button. Move the mouse with a button pressed to "paint the image".
  • Keys 'q','Q' and User abort: Save current image with all traced and interpolated pixels. Same as window close.

Performance and overhead

Concerning performance (rendering speed), the patch has little impact. Of course, all the intepolation and constant screen updating does introduce overhead but PRT does never trace pixels more than once so that in the end you're better off with PRT than with mosaic preview, even if you stop mosaic preview before the 2x2 pixel size.

As an example, these are the timings of a 320x320 trace of an isosurface (actually Alex Kluchikov's "favourite isosurface" which can also be seen on the bottom of this page). The timings were done with POVRay-3.6 compiled with gcc-3.4.1 on AthlonXP 1.47GHz running Linux. The displayed time is the elapsed (real) time on an idle system.

  Vanilla POVRay, no preview: 54.45 seconds    
  PRT-patched POVRay: 55.74 seconds    (+AM4)  
  Vanilla POVRay, mosaic preview:    58.06 seconds    (+SP16 +EP4)  

The other main point is memory consumption. Keep in mind that PRT needs to save the complete image in memory which is currently 6.25 bytes per pixel and additionally needs the tile heap to store all the not-yet-rendered regions of the image. These are values for two typical scenes ("spy probe robot" and "architecture"; both can be seen in the examples section) at different resolutions:

      Spy probe robot     Architecture
  Size:     Tiles     Heap buf   Image buf     Total     Tiles     Heap buf   Image buf     Total  
400x300     4096 64kb 732kb 796kb     8192 128kb 732kb 860kb
800x600     16384 256kb 2929kb 3185kb     32768 512kb 2929kb 3441kb

Given the amount of memory in current computers, <1Mb for a 400x300 image and <4Mb for 800x600 used by PRT is still acceptable. Note that memory consumption scales linearly with image size (i.e. number of pixels), so for larger images quite a lot of memory will be consumed. But since PRT is thougt for the design and not for final renderings, this should not be a problem.

Example scenes

Now after having talked such long it's time to have a look at some real results and images.

Note: These images are examples of the POVRay-3.5 version of the patch. The current version only differs in the images by using a checkered background instead a plain black one.

The images below show an object I call "spy probe robot", after tracing only 3% (top), 20% (center) and the complete image (bottom). The right column shows traced pixels and the left one the bilinearly interpolated image based on these pixels. (You can switch between these using the 't' key.) Of course, no manual refinement using the mouse was done.

  Interpolated Traced
3% SpyProbeRobot, 3% interpolated [42kb] SpyProbeRobot, 3% traced [7kb]
20% SpyProbeRobot, 20% interpolated [43kb] SpyProbeRobot, 20% traced [29kb]
100% SpyProbeRobot, complete [40kb]

As one can see, the overall structure is represented very early but details like the lamp on the top or the red rings arount the main lens will only appear partly at early stages. Nevertheless, all the smooth transitions (including the specular reflection) get interpolated very nicely.

Another scene of a tower-like architecture. This is a typical modelling scene where the background objects have plain colors for better visibility of CSG operations and where I am currently adjusting the texture on the the foreground tower and passway.
Again, this shows the image after tracing only 3% (top), 20% (center) and 100% (bottom) and no manual refinement using the mouse was done.

  Interpolated Traced
3% Architecture, 3% interpolated [56kb] Architecture, 3% traced [10kb]
20% Architecture, 20% interpolated [67kb] Architecture, 20% traced [40kb]
100% Architecture, complete [94kb]

Of course, the fine structure of the tower wall is not very suitable for PRT but note that larger structures like the black/yellow stripes in the doors get caught quite early. However, the fine railing along the passways get missed for quite a long time. (But that is a case where you would notmally use the mouse.)

When using the mouse, you can manually select regions to be traced. Just to give you a clue, I "painted" some part of the scene below and saved two incomplete snapshots: one with traced pixels only and one with interpolation (note that I marked slightly different regions in these images). The images show Alex Kluchikov's "favourite isosurface".

manual selection, traced pixels [12kb]   manual selection, interpolated [12kb]

[home] [site map]
Valid HTML 4.01!
Copyright © 2003-2005 by Wolfgang Wieser
Last modified: 2005-04-10 16:57:38