Thought I could cross post this here too… http://www.gamedev.net/topic/628778-compressing-vertex-attribute-normals/
My question is this: Is it possible to compress a 3-float world space vertex normal to only 4 bytes and quickly unpack it to in a vertex shader?
Reading your problem from gamedev.net, it sounds like compressing normals isn’t really the best solution to your problem. If you have that much terrain data, but only a small amount of it is visible, you have a prime candidate for culling and LOD. That way you only really have to swap in the high-detail geometry for the small area around the player and the distance rendering uses a simpler mesh. If you combine this with normal mapping, it will be very likely nobody can notice it.
If you’re set on compressing the coordinates, you might look into using the integer vertex attribute types, but that might require masks and shifts and I can’t recall how well that’s supported (or if it’s even available in the newer shader models). I’m pretty sure that the floating point attributes are a fixed size, unlike with texture formats.
If you use object space normals in a normal map, then you don’t need vertex normals, and then you can compress those into a 2 component texture and reconstruct the z value.
Some fancy-pants precalculated lookup table might be usable.
Should be rather fast.
I’m heading out for awhile…search for m. Deering compression.
You’re doing it wrong. Focus on high-level optimizations first (like culling), only if you’re out of any useable high level optimizations and the design is ‘finished’ go crazy with low-level optimizations. There are of course exceptions to this advice, but this is not the case.
After doing proper optimizations you may also realize it doesn’t require high end GPU you’re developing for and could be useable also for mere mortals too.
As your normal data is all largely composed of 45 degree or 90 degree angles it would be reasonable to compress them down to just 3 bits each wouldn’t it? So that’s 9 bits for a normal.
Cas 
That’s roughly the base of deering’s. 3 (or 2 bits) for sign - map to first octant. Polar form is now [0,pi/2],[0,pi/2]. Next you can sort into a>=b>=c and keep the permutation. You now have polar form on [0,pi/4] & [0,~.6]. Approx sin/cos on this narrow range is easy and you can fit a pretty reasonable quality normal (of singles) in a 16-bits and really good in 32.
as princec said, if you have only a bunch of possibilities just encode these.
If you want to use a more general optionen, take a look at some papers from crytek. They used 3bytes instead of 12(3xfloat) I think.
They used some
The Idea behind this was, that with a normal you only use like 1% of the possible values when using 12bytes, because your normals are normalized.
the paper:
some log post about the technic:
there are som more articles about this technic on that blog
This isn’t focused on FPS performance but on VRAM usage. Your point still stands though. I’ll focus on other more important stuff. Thanks to everyone.