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 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).

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.

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.

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: 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.

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.

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.

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%
20%
100%		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%
20%
100%		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".