How To Do Fast Realtime Vertexnormal Calculation

Rodex/Calodox/Pointblue/tAAt/the Damned/STATiC

 ----   - --    ------ --  -  -  --------------   - --    ------ --  - -

 [Subject: How to do fast realtime vertexnormal calculation            ]
 [Author:  Henri 'Rodex' Tuhkanen                                      ]
 [email:   rodex@sci.fi    ]
 [Groups:  Calodox, Pointblue, tAAt, the Damned, STATiC, a few others  ]
 [Other interests: Hifi, fantasy books, roleplaying, old games,        ]
 [         weird music, splatter/horror/violent-movies                 ]

 ----   - --    ------ --  -  -  --------------   - --    ------ --  - -

I like dynamic/morphing/shape changing objects alot, but then I wanted to use light-sourcing with them. There I had a problem, I had no other choice than to calculate normals in realtime. And it sounded awfully expensive. Then I came across with idea of NPT (Normal Pointer Table).

Here I explain what is it and how to use it to produce nice accurate normal calulation in realtime with a cost of only one sqrt per vertex.

The NPTable is formated as long, it contains indexes to faces, which are connected to each vertex. It's dynamic, so you'll just reserve memory as 'long NPT[enough];'.

It's hard to tell how long the table should be, because it's very object specific. NPTable is calculated once in init.

Here are pseudo routines that calculate NPTable themselves.

            NPTbp = 0;  //Base pointer to NPTable entry.
            for (i=0; i<vertexes; a++)
            {
              NPTep=1;  //Internal pointer to entry.
              for (a=0; a<faces; a++)
              {
                if ((f[a].a==i) || (f[a].b==i) || (f[a].c==i))
                {
                  NPT[ NPTbp+NPTep ] = a;
                  NPTep++;
                }
              }
              NPT[ NPTbp ] = (NPTep - 1);
              NPTbp+=NPTep;
            }

Secondly you need to calculate face-normal-vectors. NOTE: All used variables are floats.

            for (p=0; p<faces; p++)
            {
              x1 = v[ f[p].a ].x
              y1 = v[ f[p].a ].y
              z1 = v[ f[p].a ].z
              ax1 = v[ f[p].b ].x - x1
              ay1 = v[ f[p].b ].y - y1
              az1 = v[ f[p].b ].z - z1
              ax2 = v[ f[p].c ].x - x1
              ay2 = v[ f[p].c ].y - y1
              az2 = v[ f[p].c ].z - z1
              fnv[p].x = ay1 * az2 - az1 * ay2
              fnv[p].y = az1 * ax2 - ax1 * az2
              fnv[p].z = ax1 * ay2 - ay1 * ax2
            }

So, no normalization in this stage. Next we'll go to vertexnormal calculation. NOTE: float cx, cy, cz, ln; long c, NPTc;

            NPTc=0;
            for (p=0; p<vertexes; p++)
            {
              max = NPT[ NPTc ]
              NPTc++;
              cx = cy = cz = 0;
              for (a=0; a<max; a++)
              {
                c = NPT[ NPTc ]
                NPTc++;
                cx += fnv[c].x
                cy += fnv[c].y
                cz += fnv[c].z
              }
              ln = sqrt(cx*cx + cy*cy + cz*cz);
              if (ln != 0)
              {
                ln = 1/ln;
                cx *= ln; cx *= ln; cx *= ln;
              }
              else
              {
                cx = cy = cz = 0;
              }

Here are the basics, you maybe have to develope it more to make it fit to your own engine. But idea should be clear.

If you have any questions or suggestions, feel free to mail me. Check out the example programs.

- Rodex/Calodox/Pointblue/tAAt/the Damned/STATiC