Check for degenerate triangles

[lilleyse]

Generating smooth normals goes through Cesium's GeometryPipeline.computeNormal function which will throw when normalizing a zero-vector normal. Rather than patching up broken normals we should fix the root cause which seems to be degenerate triangles. For this we can use some of the code lifted from @likangning93. This also affects face normals, so that may be an easier place to start.

Sample model: node bin/gltf-pipeline.js face.gltf -f or node bin/gltf-pipeline.js face.gltf -m
face.gltf.txt

'use strict';
var Cesium = require('cesium');

var Cartesian3 = Cesium.Cartesian3;
var CesiumMath = Cesium.Math;
var defined = Cesium.defined;
var DeveloperError = Cesium.DeveloperError;

module.exports = isTriangleDegenerate;

var triangleSideAScratch = new Cartesian3();
var triangleSideBScratch = new Cartesian3();
var crossProductResultScratch = new Cartesian3();

/**
 * Checks whether or not the triangle defined by the given positions has an area of zero.
 *
 * @param {Cartesian3} p0 Position of one triangle vertex.
 * @param {Cartesian3} p1 Position of one triangle vertex.
 * @param {Cartesian3} p2 Position of one triangle vertex.
 *
 * @returns {Boolean} Whether the triangle is degenerate.
 */
function isTriangleDegenerate(p0, p1, p2) {
    if (!defined(p0) || !defined(p1) || !defined(p2)) {
        throw new DeveloperError('p0, p1, and p2 are required.');
    }

    // are any of the points basically identical?
    if (Cartesian3.equalsEpsilon(p0, p1, CesiumMath.EPSILON10)) {
        return true;
    }
    if (Cartesian3.equalsEpsilon(p1, p2, CesiumMath.EPSILON10)) {
        return true;
    }
    if (Cartesian3.equalsEpsilon(p2, p0, CesiumMath.EPSILON10)) {
        return true;
    }

    // is the area 0?
    var sideA = Cartesian3.subtract(p1, p0, triangleSideAScratch);
    var sideB = Cartesian3.subtract(p2, p0, triangleSideBScratch);
    var cross = Cartesian3.cross(sideA, sideB, crossProductResultScratch);
    return CesiumMath.equalsEpsilon(cross.x + cross.y + cross.z, 0.0, CesiumMath.EPSILON10);
}

[likangning93]

It might be better to use the actual code that crashes for the triangle degeneracy check. Right now I'm using this for culling bad triangles in my prototype mesh processing tools:

var crossScratch1 = new Cartesian3();
var crossScratch2 = new Cartesian3();
function areaWeightedTriangleNormal(position0, position1, position2, result) {
    var leg1 = Cartesian3.subtract(position1, position0, crossScratch1);
    var leg2 = Cartesian3.subtract(position2, position0, crossScratch2);
    return Cartesian3.cross(leg1, leg2, result);
}

function isNormalLousy(normal) {
    // check if normalizing this vector will result in NaNs
    var magnitude = Cartesian3.magnitude(normal);

    var resultX = normal.x / magnitude;
    var resultY = normal.y / magnitude;
    var resultZ = normal.z / magnitude;

    return isNaN(resultX) || isNaN(resultY) || isNaN(resultZ);
}

Since this is based on Cartesian3 itself, I think using isNormalLousy as the basis for the check will be more watertight.

[likangning93]

We found another issue. When to triangles share vertices but have opposite winding order, the smooth normal computation for the shared vertices can cause this normalization problem:

If we have triangles [0, 1, 2] and [0, 3, 2] of equal area, the normals computed for vertices 0 and 2 will turn out to be zero since the face normals for the two triangles cancel out, since with counterclockwise winding the normal for [0, 1, 2] points into the screen and [0, 3, 2] points out.

[shehzan10]

Offline discussion:
The way to detect this occurence is fairly straight forward. However, fixing it by flipping the normals or other techniques may result in false positives where the model is designed to be that way.

Also, this problem could end up happening for any shape with one or more shared vertices where the normals on some faces are negate the others (eg. a hexagon with a center and the face normals result in the normal at the center being 0.

Probably the best compromise in this situation would be to duplicate the vertex for that specific vertex. However, in the case where there is more than two competing faces at the vertex (like the hexagon example), the question then becomes which face gets the duplicated vertex and all the other faces keep one vertex. But this could probably be solved by duplicating the vertex for all the faces.

[likangning93]

I think it's still worth implementing a winding order correction stage, but perhaps it should also include a documented toggle to switch between winding order correction and vertex duplication. Most "bad winding order" cases we've run into seem to be cases where the user isn't aware of the weird winding order, in which case automatic correction is more helpful.

[pjcozzi]

Let's just fix the winding order so it is consistent. There are (robust, I believe) algorithms surveyed in Real-Time Rendering. Perhaps @erich666 can suggest his favorite.