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

Interpolated Tracing Patch for POVRay

Note: Irrespective of what says, there will be no binary releases or patches for non-UNIX povray. Why? Because the only platform I have is Linux, so unless somebody else provides a Windows/Mac patch (should not be hard), there will be none.

NEW: Difference images below.
NEW: The patch now applies cleanly to UNIX povray-3.50c.

In an efford to achieve shorter rendering times (and slightly reduced image quality), I wrote this patch (14kb) for POVRay. The patch should apply cleanly against UNIX POVRay 3.5 sources.
NOTE: If you apply this patch, the patched version will use the interpolated trating method (and no longer use anti-aliasing). To get the old behaviour, simply comment out the line
in povray.cpp.
NOTE also that you currently have to switch off the vista buffer (option -UV) when using interpolation because the patch does trace pixels which are slighly outside the viewport (see below).

Okay, now about the results. I'm not sure about whether the stuff is worth the effort. I expected to be able to trace fewer pixels than I currently do while getting the same quality. Check yourself below.

But first some explanation on how it works:
The complete image is divided up it into tiles of size 16x16. (16x16 prooved to be good but you may try any power of 2).
First, every second pixel on the tile boundary is traced (4*16/2=32 pixels). Then, the boundary is examinated: If two neighbouring traced pixels differ more than some threshold, then this is considered an edge and the (not yet traced) pixel in between is traced. Else, the pixel in between is interpolated.
Now, the complete border is already calculated. If less than 2 edges were found or 2 edges on different sides of the tile were found, the tile is considered simple and the least discrepancy direction is calculated. Then, the tile center (everything but the border) is interpolated along the least discrepancy direction. (This is the most complicated part.)
In case the tile is considered not simple, it is divided into 4 equally-sized sub-tiles which are processed recursively.
Tiles with sizes smaller than 4 (i.e. 1,2) get different treatment: In case the tile size is 1, the pixel is simply traced.
In case it is 2, the tile is bilinearly interpolated using the edge points if the color difference of these points is below some threshold. Otherwise, the tile is traced completely.
Note:It is not necessary that the image size is a multiple of the tile size. You can render any image size. However, this means that the tiles on the right and bottom border are only partly inside the viewport. This has 2 consequences:
(1) You cannot use the vista buffer.
(2) Some pixels get traced (namely the tile border) which are not visible. (This is the reason for the "invisible" pixels in the statistics below.)

Before rendering the image, a bilinearly interpolated preview (with the same tile size as above, 16x16) is traced. The traced pixels are saved for later use in the final rendering. Memory requirements are low:
- Preview buffer: sizeof(COLOUR)*width*height/(16*16) bytes
- Image lines for tiles & interpolation: 16+1=17 lines, i.e. sizeof(COLOUR)*width*17 bytes

Obviously, some scenes get interpolated better than others. The algorithm performs badly on small checker pigments (introducing aliasing). But it even sometimes gets large checkers wrong... Of course, if you use fine textures (marble, granite), then the patch will probably not save anything because each tile has to be rendered completely. However, please note that this patch is thought as an aid in desing and thus to be used in design previews of the scenery, not the final rendering. Also, anti-aliasing is not supported (which is just consequent).

And finally the results of all that (nearly 40kb code!):
On the left, you can see the original code, in the middle the interpolated one and on the right the (inverted!) image difference. Also check the statistics below the images.
NOTE that the difference between interpolation and tracing comes to effect when rendering takes long. No one will interpolate a scene which renders in less than 10 seconds.

test.png [101kb]
test-ipt.png [121kb]
Traced 52027 (540 invisible) of 172800 pixels (30.1%).
test-diff.png [63kb]
Difference image (inverted)
platform.png [53kb]
platform-ipt.png [66kb]
Traced 45113 (603 invisible) of 172800 pixels (26.1%).
platform-diff.png [23kb]
Difference image (inverted)
scene.png [61kb]
Time: 9:36.21 (573.58 seconds user time)
scene-ipt.png [68kb]
Time: 3:05.76 (184.23 seconds user time) (32%)
Traced 36236 (337 invisible) of 110592 pixels (32.8%).
scene-diff.png [32kb]
Difference image (inverted)
benchmark.png [202kb]
Time: 14:45.67 (871.16 seconds user time)
benchmark-ipt.png [190kb]
Time: 5:18.92 (317.92 seconds user time) (36%)
Traced 55224 (294 invisible) of 110592 pixels (49.9%).
benchmark-diff.png [101kb]
Difference image (inverted)

Okay, in case you are interested in the least discrepancy thingy, here are two images which illustrate the least discrepancy direction for all tiles of two of the images above. The least discrepancy direction is parallel the line in the tile. The red pixels (as well as the pixels that make up the line showing the least discrepancy direction) will get interpolated based on the border of the tile.

test-disc.png [126kb] scene-disc.png [63kb]

[home] [site map]
Valid HTML 4.01!
Copyright © 2003-2004 by Wolfgang Wieser
Last modified: 2004-08-03 17:26:38