Incorrect object normals

[yperess]

Hey, I'm not really sure this belongs in this library but I don't have a much better way to communicate with you. I found a model https://poly.google.com/view/eydI4__jXpi that does not contain normal vectors for one of the material groups. This makes the model render all black when computing the diffuse color since it's multiplied by the dot product of the face normal and the light direction.

This can be computed by calculating the normal of every face that a vertex is a part of and taking the average of these as the vertex normal. I added code to ObjUtils.convertToRenderable that does this but it's slow (about 21.5 seconds on a Pixel phone), even then I clearly did something wrong because the color isn't quite right (I'm still getting some black spots). Here's the commit to my branch where I added the code to inject normals: GoMeta@aefde24

Do you know if there's a better way to make sure that all the faces/vertices have the appropriate normals?

[javagl]

Feel free to write mails to javagl (some @ sign here) javagl.de.

But I think that this question fits nicely here. Offering a method to compute missing normals is definitely in the scope of this library, in the spirit of "Load me this OBJ and give me its contents in a renderable form", because rendering usually needs normals.

The details may again be a bit tricky, considering the fact hat OBJ leaves some degrees of freedom: There could be one face containing normal indices, followed by one that does not contain normal indices... But (although some methods already assume some form of regularity) this should be managable.

---

Performance

Regarding the performance, there have been two things that raised an eyebrow:

• Although the idea of having this vertexToFacesCache conceptually makes a lot of sense, the way how the findFacesForVertex method was implemented and used ate up most of the performance benefits here. The method iterates over all faces, and all vertices of each face, and it is called for every vertex - thus, leading to a quadratic (O(n*n)) complexity with a large factor.
• Similarly: The findNormal method is called for each vertex, and iterates over all normals, yielding another O(n*n) search.

Both of them can be sped up significantly, basically by "reversing" the lookup. The idea is to

• Populate the whole vertexToFacesCache with all required information, by just running over all faces and vertices once. Afterwards, the O(1) lookup in the resulting map can be used
• Similarly, populate a normalToIndex map and use its O(1) lookup instead of the findNormal method

This is sketched here.

Warning - a bit of a mess ahead!

This is just hacked down, to see whether it brings the desired speedup. It basically replaces the whole insertion that you did at GoMeta@aefde24#diff-a1796caf057e8f098f0aa00c186c716dL464 , still keeping your method for a very simple comparison:

public static Obj injectMissingNormals(ReadableObj input)
{
    long beforeNs = 0;
    long afterNs = 0;

    beforeNs = System.nanoTime();
    DefaultObj result = injectMissingNormals(input, new DefaultObj());
    afterNs = System.nanoTime();
    System.out.println("Normals new  took " + (afterNs - beforeNs) / 1e6 + "ms");

    beforeNs = System.nanoTime();
    result = injectMissingNormalsOrig(input, new DefaultObj());
    afterNs = System.nanoTime();
    System.out.println("Normals orig took " + (afterNs - beforeNs) / 1e6 + "ms");


    return result;
}

private static Map<Integer, List<ObjFace>> computeVertexIndexToFacesMap(ReadableObj obj)
{
    Map<Integer, List<ObjFace>> vertexIndexToFaces = 
        new LinkedHashMap<Integer, List<ObjFace>>();
    for (int i=0; i<obj.getNumFaces(); i++)
    {
        ObjFace face = obj.getFace(i);
        for (int j=0; j<face.getNumVertices(); j++)
        {
            int vertexIndex = face.getVertexIndex(j);
            List<ObjFace> faces = vertexIndexToFaces.get(vertexIndex);
            if (faces == null)
            {
                faces = new ArrayList<ObjFace>();
                vertexIndexToFaces.put(vertexIndex, faces);
            }
            faces.add(face);
        }
    }
    return vertexIndexToFaces;
}

private static Map<FloatTuple, Integer> computeVertexNormalIndices(ReadableObj obj)
{
    Map<FloatTuple, Integer> vertexNormalIndices = new LinkedHashMap<FloatTuple, Integer>();
    for (int i = 0; i<obj.getNumNormals(); i++) {
        FloatTuple normal = obj.getNormal(i);
        vertexNormalIndices.put(normal, i);
    }
    return vertexNormalIndices;
}

public static DefaultObj injectMissingNormals(
    ReadableObj input, DefaultObj output)
{
    System.out.println("adding normals");
    
    output.setMtlFileNames(input.getMtlFileNames());
    addAll(input, output);
    
    Map<Integer, List<ObjFace>> vertexToFacesCache = 
        computeVertexIndexToFacesMap(input);
    Map<FloatTuple, Integer> vertexNormalIndices = 
        computeVertexNormalIndices(input);
    
    Map<ObjFace, FloatTuple> faceNormalCache = new HashMap<>();
    
    for (int faceIndex = 0, numFaces = input.getNumFaces(); faceIndex < numFaces; ++faceIndex)
    {
        ObjFace face = input.getFace(faceIndex);
        activateGroups(input, face, output);

        if (face.containsNormalIndices())
        {
            // Skip faces that already have all their normals
            output.addFace(face);
            continue;
        }

        int[] normalArray = new int[face.getNumVertices()];
        int[] vertexIndices = new int[face.getNumVertices()];
        int[] textureIndices = null;
        if (face.containsTexCoordIndices()) {
            textureIndices = new int[face.getNumVertices()];
        }

        // For each vertex in the face, compute the normals for all the faces it touches.
        for (int vertexFaceIndex = 0, numVertices = face.getNumVertices(); vertexFaceIndex < numVertices;
                ++vertexFaceIndex)
        {
            int vertexIndex = face.getVertexIndex(vertexFaceIndex);
            vertexIndices[vertexFaceIndex] = vertexIndex;
            if (face.containsTexCoordIndices()) {
                textureIndices[vertexFaceIndex] = face.getTexCoordIndex(vertexFaceIndex);
            }
            List<ObjFace> faces = vertexToFacesCache.get(vertexIndex);
            List<FloatTuple> normals = new ArrayList<>(faces.size());
            for (ObjFace f : faces)
            {
                FloatTuple normal = faceNormalCache.get(f);
                if (normal == null)
                {
                    // Normal doesn't exist for this face, calculate it and cache it.
                    normal = calculateNormalForFace(input, f);
                    faceNormalCache.put(f, normal);
                }
                normals.add(normal);
            }

            // Compute the average of the normals
            DefaultFloatTuple vertexNormal = new DefaultFloatTuple(0f, 0f, 0f);
            for (FloatTuple normal : normals)
            {
                vertexNormal.plus(normal);
            }
            vertexNormal.normalize();

            // Try to find this normal so we don't add duplicates
            Integer newNormalIndex = vertexNormalIndices.get(vertexNormal);
            if (newNormalIndex == null) {
                output.addNormal(vertexNormal);
                newNormalIndex = output.getNumNormals() - 1;
                vertexNormalIndices.put(vertexNormal, newNormalIndex);
            }
            else
            {
                // TODO Happens rarely:
                //System.out.println("Actually re-used normal...");
            }
            normalArray[vertexFaceIndex] = newNormalIndex;
        }

        output.addFace(new DefaultObjFace(vertexIndices, textureIndices, normalArray));
    }
    
    System.out.println("adding normals DONE");
    
    return output;
}


public static DefaultObj injectMissingNormalsOrig(
        ReadableObj input, DefaultObj output)
{
    System.out.println("adding normals");
    
    output.setMtlFileNames(input.getMtlFileNames());
    addAll(input, output);
    Map<Integer, List<ObjFace>> vertexToFacesCache = new HashMap<>();
    Map<ObjFace, FloatTuple> faceNormalCache = new HashMap<>();
    for (int faceIndex = 0, numFaces = input.getNumFaces(); faceIndex < numFaces; ++faceIndex)
    {
        ObjFace face = input.getFace(faceIndex);
        activateGroups(input, face, output);

        if (face.containsNormalIndices())
        {
            // Skip faces that already have all their normals
            output.addFace(face);
            continue;
        }

        int[] normalArray = new int[face.getNumVertices()];
        int[] vertexIndices = new int[face.getNumVertices()];
        int[] textureIndices = null;
        if (face.containsTexCoordIndices()) {
            textureIndices = new int[face.getNumVertices()];
        }

        // For each vertex in the face, compute the normals for all the faces it touches.
        for (int vertexFaceIndex = 0, numVertices = face.getNumVertices(); vertexFaceIndex < numVertices;
                ++vertexFaceIndex)
        {
            int vertexIndex = face.getVertexIndex(vertexFaceIndex);
            vertexIndices[vertexFaceIndex] = vertexIndex;
            if (face.containsTexCoordIndices()) {
                textureIndices[vertexFaceIndex] = face.getTexCoordIndex(vertexFaceIndex);
            }
            List<ObjFace> faces = vertexToFacesCache.get(vertexIndex);
            if (faces == null)
            {
                // Find all the faces that share this vertex and cache them.
                faces = findFacesForVertex(input, vertexIndex);
                vertexToFacesCache.put(vertexFaceIndex, faces);
            }
            List<FloatTuple> normals = new ArrayList<>(faces.size());
            for (ObjFace f : faces)
            {
                FloatTuple normal = faceNormalCache.get(f);
                if (normal == null)
                {
                    // Normal doesn't exist for this face, calculate it and cache it.
                    normal = calculateNormalForFace(input, f);
                    faceNormalCache.put(f, normal);
                }
                normals.add(normal);
            }

            // Compute the average of the normals
            DefaultFloatTuple vertexNormal = new DefaultFloatTuple(0f, 0f, 0f);
            for (FloatTuple normal : normals)
            {
                vertexNormal.plus(normal);
            }
            vertexNormal.normalize();

            // Try to find this normal so we don't add duplicates
            int newNormalIndex = findNormal(output, vertexNormal);
            if (newNormalIndex == -1) {
                output.addNormal(vertexNormal);
                newNormalIndex = output.getNumNormals() - 1;
            }
            normalArray[vertexFaceIndex] = newNormalIndex;
        }

        output.addFace(new DefaultObjFace(vertexIndices, textureIndices, normalArray));
    }
    
    System.out.println("adding normals DONE");
    
    return output;
}

private static List<ObjFace> findFacesForVertex(ReadableObj obj, int vertexIndex)
{
    List<ObjFace> faces = new ArrayList<>();
    for (int i = 0, numFaces = obj.getNumFaces(); i < numFaces; ++i)
    {
        ObjFace face = obj.getFace(i);
        for (int j = 0, numVertices = face.getNumVertices(); j < numVertices; ++j)
        {
            if (face.getVertexIndex(j) == vertexIndex)
            {
                faces.add(face);
                break;
            }
        }
    }
    return faces;
}

@VisibleForTesting
static FloatTuple calculateNormalForFace(ReadableObj obj, ObjFace face)
{
    if (face.getNumVertices() < 3)
    {
        throw new IllegalArgumentException("Cannot calculate normal for faces with less than 3 vertices: " +
                face.toString());
    }
    DefaultFloatTuple normal = new DefaultFloatTuple(0f, 0f, 0f);
    for (int i = 0, size = face.getNumVertices(); i < size; ++i)
    {
        FloatTuple current = obj.getVertex(face.getVertexIndex(i));
        FloatTuple next = obj.getVertex(face.getVertexIndex((i + 1) % size));
        normal.setX(normal.getX() + (current.getY() - next.getY()) * (current.getZ() + next.getZ()));
        normal.setY(normal.getY() + (current.getZ() - next.getZ()) * (current.getX() + next.getX()));
        normal.setZ(normal.getZ() + (current.getX() - next.getX()) * (current.getY() + next.getY()));
    }
    normal.normalize();
    return normal;
}

private static int findNormal(ReadableObj obj, FloatTuple normal) {
    for (int i = 0, size = obj.getNumNormals(); i < size; ++i) {
        if (obj.getNormal(i).equals(normal)) {
            return i;
        }
    }
    return -1;
}

From a quick test on a slow PC, the output with the "Flower.obj" is along the lines of

adding normals
adding normals DONE
Normals new  took 53.79287ms
adding normals
adding normals DONE
Normals orig took 2769.738053ms

So on your phone, the new version should hardly take longer than half a second.

---

Correctness

This is a bit harder to figure out. It's hard to see from the screenshot what exactly is wrong there. (I'll have to render the model, but am not my main development PC right now).

It looks like some sort of herringbone pattern. Until I can try it out: If you zoom in, can you see whether the triangles are right and wrong alternatingly? When you watch the petals from below, does the pattern seem to be inverted there? It might just be that some normals point up, and others point down.

If this is the case, then this is likely due to some faces containing the vertices in clockwise and others in counterclockwise order.

This could be an issue in the loader. I'd review the triangulate method, although I don't see a direct connection there - the method should already retain the given vertex order

What would seem more likely: Could it be that the online renderer jus assumes that the material is double-sided, whereas yours assumes a single-sided material? You mentioned that the diffuse intensity is basically computed with something like

float intensity = dot(faceNormal, lightDirection);

For a double-sided material, this could roughly and in the simplest case be changed to

float intensity = abs(dot(faceNormal, lightDirection));

(other adjustments in the shader may likely be necessary, though...)

If this doesn't help, I would try to create a test case consisting of a 5-vertex face (without normals) and try to reproduce the problem there.

[yperess]

Thanks for the write-up, what you said about performance makes sense and is exactly why I should not be writing code at 3AM. Funny, as I was walking my dog this morning I thought exactly what you said about the double sided material. I think that's exactly what's going on and I'll confirm ASAP.

[yperess]

Nailed it!

So I think it's wrong to force calculate the normals when missing. From what I've just seen basically the lack of normal in the face definition is what tells us that both sides are valid. So what I did here is check if the faces are missing normals, then in my renderer I pass a boolean to the fragment shader. So now I have:

#extension GL_OES_standard_derivatives : enable

...

void main() {
    ...
    vec3 viewNormal;
    if (u_UseVaryingNormal) {
        viewNormal = normalize(v_ViewNormal);
    } else {
        vec3 dX = dFdx(v_ViewPosition);
        vec3 dY = dFdy(v_ViewPosition);
        viewNormal = normalize(cross(dX, dY));
    }
    ...
}

[javagl]

OK, now you're now basically computing the normal on the fly in the shader.

I'm not sooo deeply familiar with GLSL, but knew (from a recent issue in another project) that WebGL (and analogously, GL ES 2.0) needs the OES_standard_derivatives extension for the dFdx function. However, I'm not sure about things like performance implications, or how widely this extension is supported.

I'm also not sure whether the implication "no normals -> double sided material" is right. In many cases, information about whether a material is double sided is stored explicitly in the material. (Not in MTL, though...).

In any case, I think that the option to compute normals would be nice to have. I have added a commit in a branch at 5d44c02
(The actual implementation is in a dedicated class. The ObjUtils start to become a bit bloated otherwise...)

Before this is moved into master, I'll have to sort a few things out:

• Should there be an option to re-compute all normals from scratch?
• Are there any corner cases or caveats not considered? (E.g.: It might be necessary to add some sort of boolean flipTheComputedNormals flag, to flip the normals for the case that they do not match the orientation of the existing ones - but this would be a bit cumbersome...)
• Should the normal computation be part of convertToRenderable?
• ...

For the latter, the I already know the answer: No - at least not directly, because this would change the behavior of this method in a possibly non-backward compatible way. There could be a convertToRenderable(..., boolean computeNormalsWhenMissing) overload, or something similar. But this doesn't scale well with future extensions. (I'd like to avoid having to add a boolean computeNormalsEvenWhenNotMissing flag and boolean flipTheComputedNormals flag soon...).

---

If I had to re-write it from scratch, I'd probably implement some of the ObjUtils methods in a slightly more object-oriented way. Then, these "configuration settings" could, for example, be part of a fluent interface, roughly like

Obj obj = load(file).triangulate()
    //.computeMissingNormals(flipThem) 
    .computeAllNormals(flipThem)
    .makeStuffUnique()
    .get();

I think it's still OK the way it is. But if it's supposed to be extended further, I might consider a refactoring.

BTW: I also considered to add some bounding box computation, like you suggested in your (pending) PR. This could be handy for renderers in order to easily implement a "Fit-To-View" functionality (as you also did, as far as I saw). But as I already mentioned, I'd rather implement this as a dedicated step, and not as part of the loading process.

[yperess]

I agree, I would have it done the same way as the bounding box (in the way you wanted it) so basically something like Obj::getBoundingBox() the value can be cached and the cache invalidated if a new vertex is added/removed from the object. Similarly Obj::computeMissingNormals() could only run if the obj is considered dirty.