POV-Ray

The Persistence of Vision Raytracer (POV-Ray).

This is the legacy Bug Tracking System for the POV-Ray project. Bugs listed here are being migrated to our github issue tracker. Please refer to that for new reports or updates to existing ones on this system.

FS#264 - Improve precision of photon direction information

Attached to Project: POV-Ray
Opened by Christoph Lipka (clipka) - Friday, 04 January 2013, 23:39 GMT
Last edited by William F Pokorny (wfpokorny) - Tuesday, 25 April 2017, 12:21 GMT
Task Type Unimp. Feature/TODO Backend → Photons Tracked on GitHub No-one All Low Low 3.70 RC6 Undecided Undecided 1 Simon (infoised) (2013-02-25) No

Details

In the photons map, the direction of each photon is stored as separate latitude & longitude angles (encoded in one byte each), causing the longitudinal direction component’s precision to be unnecessarily high for directions close to the “poles” (Y axis); in addition, encoded value -128 is never used. For better overall precision as well as precision homogenity, the following scheme could be used instead:

• Encode the latitude (-pi/2 to +pi/2) into LatCount=226 distinct values (= 256*sqrt(pi)/2) rounded to the next even number) from 0 to LatCount-1 using
```latCode = (int)((LatCount-1) * (lat/M_PI + 0.5) + 0.5)
```
• For each latitude code, define a specific number of encodable longitude values, LngCount[latCode] = approx. cos(lat)*pi*65536/(2*LatCount); this can be a pre-computed table, and may need slight tweaking for optimum use of the code space. Encode the longitude (-pi to +pi) into a value from 0 to (LngCount[lat]-1) using
```LC = LngCount[latCode];
lngCode = (int)(LC * (lng/(2*M_PI) + 0.5) + 0.5) % LC;
```
• Besides LngCount[latCode], also store the sum of LngCount[i] with i < latCode as LatBase[latCode]; encode the direction as
```dirCode = LatBase[latCode] + lngCode;
```
• For decoding, a simple lookup from a precomputed list of directions could be used (2^15 entries, i.e. one hemisphere, will suffice). To conserve space, direction vectors could be scaled by (2^N-1) and stored as (N+1)-bit signed integer triples rather than floating point values; due to the limited precision of the lat/long information, 8 bits per coordinate might be enough, giving a table size of 96k. A full double-precision table would require 786k instead.

Comment by Simon (infoised) - Wednesday, 13 March 2013, 16:11 GMT

A relevant paper for this task:

Comment by Christoph Lipka (clipka) - Thursday, 14 March 2013, 09:50 GMT

Thanks for the reference, Simon. Looks like exactly the same basic idea, except that they used a more precise formula for LngCount[] (which they call N[Theta]), and add a few more ideas on top of that. Unfortunately their main focus appears to be variable-length encoding into a bit stream, while our problem is fixed-length encoding, so the actual steps of encoding latCode and lngCode into a single fixed-width value, and decoding that value into latCode and lngCode again, are not addressed by the paper.

Comment by Simon (infoised) - Wednesday, 27 March 2013, 15:43 GMT

If you encode the precomputed map in 8-bit precision, there is no reason to encode at all. You don't save any space with that. A look at the code shows that the photon structure is
float[3] #location (12 bytes)
char[4] #color (4 bytes)
char #info (1 byte)
char[2] #direction information (2 bytes)
On all modern architectures, the memory alignment is at least 4, if not 8 bytes, so the entire structure is packed into 20 bytes (sizeof(Photon) on gcc 4.7.2, x86_64). Having char[3] for location would have the same precision as a 8-bit precomputed list, and would take no more space in the structure. Encoding only makes sense if you save space or increase precision by using it. I think that having simply char[3]=(x,y,z) for direction is just fine if you decide for 8-bit precomputation - simplicity over obfuscation :)

For our specific case, the location data takes much more space than the direction anyway, and it cannot really be reduced, because you need sharp location for accurate caustics.

Edit: for 8-bit encoded components, you need normalization after conversion to float (so this precomputation does not help increase speed). So:
if you keep it as is, you have precomputed sin/cos values (fast)
if you make the encoding more complicated (more accuracy), you can either have built-in char[3] (simple but slow because of required renormalization) or 16-bit encoding with global float[3] lookup table (fast and more precision).

Or, of course, you can ignore that 8-bit precision can result in vector length a bit different than 1 and live with the consequences.

Comment by William F Pokorny (wfpokorny) - Tuesday, 25 April 2017, 12:21 GMT
• Field changed: Status (New → Tracked on GitHub)

Now tracked on github as issue #283.