Port of FS264 - Improve precision of photon direction information

[wfpokorny]

http://bugs.povray.org/task/264 (Christoph Lipka (clipka))

---

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)pi65536/(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.

---

Comments:

---

Comment by Simon (infoised) - Wednesday, 13 March 2013, 21:11 GMT+5

A relevant paper for this task:

http://faculty.cs.tamu.edu/schaefer/research/normalCompression.pdf

---

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

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, 20:43 GMT+5

I was thinking a bit about this, and came to the following conclusion:

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.