Re: [GD-General] Representable range mini-rant

[Thatcher U. <tu...@tu...>]

On 10/3/06, Jon Watte <hp...@mi...> wrote:
> This is about representation of data, specifically with respects to
> closed intervals, and using fixed point representation.
>
> For example, representing components for normals, you need the range
> [-1,1]. (let's ignore the dropping of components for compression reasons
> for now) Same thing with various tree coordinates (if you allow the
> topmost coordinate value), vertex components, and pretty much any other
> quantity. This gets annoying when you are dealing with fixed point data.
>
> This is perhaps made most famous with the color->byte conversion, where
> 255 means 1.0. The problem with this is that you can't exactly represent
> the midpoint (0.5 maps to 127.5, in this case). If all you want to do is
> representing the midpoint, you can throw away the top value, and
> represent 1.0 using 254, and thus 0.5 as 127. For example, with sound
> samples, and geo-measurement data, it's common to make -32768 mean "no
> data" or "invalid", and normalize -32767 to 32767 as the peak-to-peak
> range. However, then you run into the same problem with mid-midpoints,
> which isn't so much a problem for colors (or audio samples), but a whole
> other kettle of fish for trees of various kinds, or vertex values that
> need to quantize into some tree-based structure.
>
> What I find myself doing is repersenting the midpoint and the two
> endpoints, and throwing away almost a whole bit of precision. For
> example, to represent 0..1 using 8 bits, I'd represent 0 as 0, and 1 as
> 128, and then "throwing away" data in the range 129-255. For data that
> needs more precision, I'd represent it using 16 bits, with 32768 being
> 1.0 and 0 being 0.0, and ignoring values 32769 through 65535.
>
> It just annoys me that I leave almost a whole bit (6 dB!) of dynamic
> range un-used, but for these cases (closed ranges, must support
> subdivision) I really don't see any better option.
>
> Comments?

Interesting, I guess this is the problem of labelling the boundaries
between units, rather than the units themselves.  The only thought I
have at the moment is, for subdivision, using a different base than 2.
 E.g. to label the boundaries between units in a complete tree, you
need (base^levels + 1) labels for base^levels units.

For a binary tree, it's optimally bad.  For other tree bases, it might
be good, depending on how many bits you have:

units          labels
-----          ------

2-ary
1          --> 2
2          --> 3
4          --> 5
etc

3-ary
1          --> 2
3          --> 4   *
9          --> 10
27         --> 28  *
81         --> 82
243        --> 244 *

5-ary
1
5          --> 6   *
25         --> 26  *
125        --> 126 *
625        --> 626

6-ary
1
6          --> 7   *
36         --> 37
216        --> 217 *
1296       --> 1297

I've put stars next to the ones that don't waste so much code space in binary.

I'm not sure if that is any use whatsoever, but it's kind of interesting.

-T