I don't really get the use of normal-mapping. Graphics cards have triangle output ability, fillrate, and math power.

Normal-mapping uses fillrate in the form of an extra texture lookup (right?), and even more math power, to save triangle output.

The problem is, math power and fillrate are much more precious on a graphics card than triangle output. You'll hit limits on them faster.

I've seen slides showing a 20k model using a 1 million k normal map, being 10x faster than using a million k model with no normal map. The only problem with this test is that a 20k model with a 1 million k normal map, is going to end up looking like a 60k-500k model, not a 1 million k model.

Fillrate and memory bandwidth are not quite the same thing. Normalmaps don't really hit fillrate outside of a deferred or light prepass render, just memory bandwidth. However, their access patterns are fairly predictable, and scale better (assuming mipmaps) than random vertex access.

Given that every card imaginable these days shades and rasterizes in units larger than a pixel, 2x2 quads at the least, and far larger in practice, any ALU gains you get by not bothering with normalmaps will be consumed by small triangle overhead. 1x1 pixel triangles will generally compute as 2x2 quads, or worse, and throw away most of the results, so pixel for pixel they're 4-16x more expensive than a more reasonably sized triangle.

Lastly, mipmaps provide a more automatic method of LOD. With discrete triangles, lighting, texturing, etc will almost certainly break down into a flickery, sparkly mess as the triangles shrink to sub-pixel resolution.

Thanks guys. You saved me from the mistake of not using normal-mapping!

It's also important to point out that one really useful property of normal maps in modern games is in detail maps. Forgelight (the Planetside 2) engine and probably others have a normal map atlas they use a UV channel for detail normals on a lot of their meshes. When you get close to models the pixel shader looks up the detail normal and uses the atlas to map it along the object creating much finer details. Like being able to see stitching on cloth and fine patterns when zooming into surface rather than a pixelation. You can't really get that detail without really pushing the tessellation shaders.