RE: [Algorithms] Normal map compression and fitting a circle to a set of 3d points

[Nick C. <nc...@nv...>]

Doug,
 
Circle-fitting in the quantized domain you describe (that is, points on a
sphere, quantized to 8 bits per component) can perhaps be done by brute
force.  A great circle of the sphere can be defined by a normal vector
perpendicular to the circle's plane -- that's only 2 degrees of freedom,
yielding on the order of 256x256 distinct circles worth considering.
Certainly not efficient, but enough for prototyping, and maybe even good
enough for offline texture compression.
 
All you would need to find a best-fit circle would be a direct way to go
from a given circle to a pallette (which you've already suggested, see my
reservations below), and an appropriate error metric given a particular
pallette.  For the error metric, I'd suggest a summation of the inverse
cosine of the dot products between each of the original and compressed
normals -- each term of the sum would then correspond to a distance along
the surface of the unit sphere.  Sum-of-square-distances might also give
good results.
 
I'm not certain I agree with the construction you describe for finding the
best sub-arc of a given great circle.  Suppose that there's one extremal
normal, with the rest of the normals clustered nicely some distance away on
another part of the unit sphere.  Just taking the minimum arc that
encompasses all the points would result in bias in the compression.  Is
there a reason to guarantee perfect compresson of these extremal points?
You may want to consider taking an 'average' point, and using that as the
center of your arc.
 
Also, the greatest arc you can possibly describe with this scheme is an arc
of 180 degrees -- the renormalization of the interpolants is like projecting
a chord (of the unit sphere) onto the unit sphere from the origin.  How will
you handle the case where the maximum arc-distance between two adjacent
points on the circle is less than 180 degrees?  For tangent-space bump
mapping, you usually don't see z components less than zero, so you might be
working in a hemispherical domain to begin with; but you may very will have
to deal with this if the bump maps are intended for object-space bump
mapping.
 
 - nick carter
 
 -----Original Message-----
From: Doug Rogers 
Sent: Monday, July 14, 2003 4:29 PM
To: gda...@li...
Subject: [Algorithms] Normal map compression and fitting a circle to a set
of 3d points



I am exploring an implementation for compressing normal maps using DXT/S3TC.
 
Given
   hardware decode 3 or 4 palette entries for each 16 pixel block.  
 
Assumptions:
   pixel shader will renormalize texels
 
so, hardware reconstructs an arc on a circle during decompression (because
the texels are renormalized)
 
So I wanted an algorithm that does a fit of a circle centered on the origin
and radius = 1 to a set of 3D points on a sphere (normals).  Any ideas how
to do this?
 
After that, I could choose the palette endpoints (the most extreme normals
on the arc) and find the closest palette entry for each normal.
 
 
-Doug