How to compute accurate vertex normals on irregular triangle meshes
There are various ways to compute normals of a triangle mesh. This can greatly impact the accuracy of rendering. In this note, we will see simple alternatives to the standard averaging of triangle normals.
Wires
Uniform weights
Area weights
Angle weights
Wires
Uniform weights
Area weights
Angle weights
Let's define \(\vec n_t\) as the normal of a single triangle:
\[ \vec n_t = \frac{(\vec p_j - \vec p_i) \times (\vec p_k - \vec p_i)}{ \|(\vec p_j - \vec p_i) \times (\vec p_k - \vec p_i)\|} \]
To compute the normal of a vertex \(\vec n_v\) on a triangle mesh, one would usually average the normal of the neighboring triangles. For one cell of the mesh we could mathematically describe it as:
\[ \vec n_v = \frac{ \sum\limits_{t=0}^{ \text{nb_triangles}} w_t \ \vec n_t }{ \left \| \sum\limits_{t=0}^{ \text{nb_triangles}} w_t \ \vec n_t \right \| } \quad \text{ with } w_t \in \mathbb R \]The standard way is to not weight the normal, or rather use uniform weights (\(w_t = 1\)). This may produce inaccurate normals (and ultimately inaccurate lighting) for meshes with an uneven distribution of vertices. Another solution is to pick \(w_t\) as the area of the current triangle \(t\) (essentially the norm of the cross product divided by 2) or better the angle of the incident edges to the central vertex \(p_i\)
void off_create_adjacency( vector< int > *adj_list, OFFTrilist *off_tris)
{
for( int i = 0 ; i < (*off_tris).size() ; i++ ) {
adj_list[ (*off_tris)[i].v[0] ].push_back(i);
adj_list[ (*off_tris)[i].v[1] ].push_back(i);
adj_list[ (*off_tris)[i].v[2] ].push_back(i);
}
}
The standard way:
void off_compute_uniform_normals(Vector *off_normals, vector< int > *adj_list, OFFVertlist *off_verts, OFFTrilist *off_tris) {
std::cerr << "[INFO]: Using uniform weights";
Vector *face_normal = new Vector [ (*off_tris).size() ];
Vector p0, p1;
for( int i = 0 ; i < (*off_tris).size() ; i++ ) {
p0 = (*off_verts)[(*off_tris)[i].v[1]] - (*off_verts)[(*off_tris)[i].v[0]] ;
p1 = (*off_verts)[(*off_tris)[i].v[2]] - (*off_verts)[(*off_tris)[i].v[0]] ;
face_normal[i] = Normalize(Cross(p0, p1));
}
for( int k = 0 ; k < (*off_verts).size() ; k++) {
Vector n(0.f);
for( int j = 0 ; j < adj_list[k].size() ; j++ ) {
n += face_normal[ (adj_list[k])[j] ];
}
off_normals[k] = Normalize( n );
}
}
Area based
Since we compute the normal with a cross product \( \vec v = \vec a \times \vec b\) and that the norm \(\| \vec v \|\) represent the area of the parallelogram spread by \(\vec a, \vec b\) if we skip normalizing \(\vec v\) at the triangle level
void off_compute_area_normals(Vector *off_normals, vector< int > *adj_list, OFFVertlist *off_verts, OFFTrilist *off_tris) {
std::cerr << "[INFO]: Using area weights";
Vector *face_normal = new Vector [ (*off_tris).size() ];
Vector p0, p1, p2;
for( int i = 0 ; i < (*off_tris).size() ; i++ ) {
p0 = (*off_verts)[(*off_tris)[i].v[1]] - (*off_verts)[(*off_tris)[i].v[0]] ;
p1 = (*off_verts)[(*off_tris)[i].v[2]] - (*off_verts)[(*off_tris)[i].v[0]] ;
face_normal[i] = Cross(p0, p1);
}
for( int k = 0 ; k < (*off_verts).size() ; k++) {
Vector n(0.f);
for( int j = 0 ; j < adj_list[k].size() ; j++ ) {
n += face_normal[ (adj_list[k])[j] ];
}
off_normals[k] = Normalize( n );
}
}
Angle based
void off_compute_angle_normals(Vector *off_normals, vector< int > *adj_list, OFFVertlist *off_verts, OFFTrilist *off_tris) {
std::cerr << "[INFO]: Using geodesic angle weights";
Vector *face_normal = new Vector [ (*off_tris).size() ];
float *face_angles = new float [ 3*(*off_tris).size() ];
Vector p0, p1, p2;
float n0, n1, n2;
for( int i = 0 ; i < (*off_tris).size() ; i++ ) {
p0 = (*off_verts)[(*off_tris)[i].v[1]] - (*off_verts)[(*off_tris)[i].v[0]] ;
p1 = (*off_verts)[(*off_tris)[i].v[2]] - (*off_verts)[(*off_tris)[i].v[0]] ;
p2 = (*off_verts)[(*off_tris)[i].v[2]] - (*off_verts)[(*off_tris)[i].v[1]] ;
n0 = p0.Length();
n1 = p1.Length();
n2 = p2.Length();
face_angles[3*i] = acos ( Dot( p0, p1)/(n0*n1) );
face_angles[3*i+1] = acos ( Dot(-p0, p2)/(n0*n2) );
face_angles[3*i+2] = M_PI - face_angles[3*i] - face_angles[3*i+1];
face_normal[i] = Normalize(Cross(p0, p1));
}
for( int k = 0 ; k < (*off_verts).size() ; k++) {
Vector n(0.f);
for( int j = 0 ; j < adj_list[k].size() ; j++ ) {
int s = (adj_list[k])[j];
for (int l=0 ; l < 3 ; l++ ) {
if ( (*off_tris)[s].v[l] == k) {
n += face_angles[3*s+l] * face_normal[ s ];
}
}
off_normals[k] = Normalize( n );
}
}
}
Going further
Papers
- Nelson Max. “Weights for Computing Vertex Normals from Facet Normals.” Journal of Graphics, GPU, and Game Tools 4:2 (1999), 1–6.
- Shuangshuang Jin, Robert R. Lewis, and David West. “A Comparison of Algorithms for Vertex-Normal Computation.” The Visual Computer 21:1–2 (2005), 71–82.
Skinning
If your mesh is deformed with skinning, you can also more accurately compute how the normals deform. If you're interested see the paper Accurate and Efficient Lighting for Skinned Models by Marco Tarini & Al (Eurographics 2014)
References
- Book: Polygon Mesh processing (Chapter 3 "Differential Geometry" Section 3.3.2
"Normal Vectors"
- Code snippets and images comes from http://w3.impa.br/~zang/pg2012/exe2.html
No comments