Conceptual normal problem

I am trying to get static objects into my terrain system.

The best source I have for them supplies objects in wavefront OBJ format.

Sadly most of them do not include normals, so my code generates them but it’s not working.

The problem is that OBJ format does not force triangle ordering. So I have no idea if a triangle is clockwise or anti-clockwise.

Has anyone come up with a solution for this case?

I am thinking abut finding the centre point of the triangle and forming a direction vector from that to the centre of the object.

If the angle between this vector and the calculated normal is less than PI, then the normal must be inverted.

Anyone tried this?

Dataformats do not force ordering - the 3D editor or exporter does. I don’t see why an 3d editor should mix clockwise/counterclockwise triangle ordering randomly … the 3d editor would need that information too. afaik .obj are just text-files with lists of vertices, normals, uvs ( etc) and indices (structured by material name or something) - some years ago I worked with them because it was easier in my case to parse that data.

Your approach only works for simple geometry, where it is guaranteed that every triangles face away from the center (rarely true). If so, you can just use the dotproduct of the normal and the direction vector, if it’s negative, invert the normal.

If you find that all triangles in a single obj share the same ordering (cw/ccw) you can just use crossproduct. Just be aware, that you can possibly have shared vertices (smooth shading) where you’d need to average the normals of all faces sharing that vertex to get a smooth normal on that edge

Why not import the OBJ files into something like Blender, which has a ‘recalculate normals’ function that can add them to your mesh automatically. You can then export again into whatever format you like, and the exporter will probably let you choose what data to include in the models, and the triangle winding.

1 Like

I’ve never had to do this, but I can think of two solutions

First solution, only if the 3d model is “closed” (there are no holes which allow to see the backside of the object), is centered at 0,0,0 and all the triangles have the same winding (it’d be stupid if it wasn’t this way):

Throw a ray from a distant position which is outside the model (i.e. 10000,0,0) to (0,0,0). The first triangle that intersects the ray defines the winding for all the triangles. Choose the normal which is not in the same direction as the ray.

The second solution, easier but worse, is considering all triangles double-sided. Generate 2 triangles for each triangle, each with a different winding. Of course it’ll take twice the time to render, but will always be correctly rendered (even in the improbable case the windings change between triangles)

If the model itself is hosed er made messed up, then you are going to have to fix it in a model editor or ditch it. Plain as that.

It seems like you are saying the model is designed properly but the normals are some how missing in the model and you need to generate them ?

If this is the case then.

Normals can be generated by a predefined normal pair via the cross product that xna monogame uses
(which is the short form of the following).
Generated by the winding order of the triangle vertices ABC by the following Vertice based cross product formula.

        /// <summary>
        /// Positional CrossProduct of three points.
        /// The returned direction of the surface normal depends on the winding order of the vertices. 
        /// a b c vs a c b
        /// </summary>
        public static Vector3 CrossProduct3d(Vector3 a, Vector3 b, Vector3 c)
            return new Vector3
                ((b.Y - a.Y) * (c.Z - b.Z)) - ((c.Y - b.Y) * (b.Z - a.Z)),
                ((b.Z - a.Z) * (c.X - b.X)) - ((c.Z - b.Z) * (b.X - a.X)),
                ((b.X - a.X) * (c.Y - b.Y)) - ((c.X - b.X) * (b.Y - a.Y))

To flip a surface normal you just change the Vector3’s sign.
normal = -normal; // or multiply by -1f

Note though that if you want to smooth a vertice normal that is used by multiple triangles in a mesh, that is a step you do after this on each vertice.

You can look to the “smooth normal” function in this class below.
Its a fairly simple idea you average the directions of all connected triangle normals to a vertice then you normalize the resulting vector. But you have to know what the surface normal is for each triangle first which is found by the cross product of 3 vertices in the previous mentioned formula or by using monogames.

Actually provided the model is wound correctly and composed of indexed triangles and you get it into vertex position normal color structure then alter the below function to operate on that, then it should work on your models mesh. Its a pretty general function.

I cannot assume any winding order.

Looking at the meshes, it appears they were created with quads, then converted to triangles.

When the conversion took place, one tri is clockwise, one anti-clockwise. Sigh

My idea turned out to be rubbish, it didn’t take account things like pillars and doorways.

Interestingly I put one of the meshes through accutrans as a test, and it can re-generate the normals correctly.
This means there IS a technique that works.

I just don’t know what it is :smiley:

The whole point of using these meshes is that all the conversion can be done in code, not by hand.

There are 10’s of thousands of objects in the database and I need them all if I am to generate maps for any location on the planet.

I am going to keep thinking about it, I can feel I am close to something, but it has just not made it from the subconscious to the conscious mind

You could probably make a python script in Blender which imports every mesh in a folder, regenerates the normals, and saves the corrected output to a different folder in a for loop! It probably wouldn’t be that much code, but if you’re new to Blender or Python it might take a while to get it right.

Without special assumptions there is no way to determine which way the normal of a given triangle should be facing. Take a box for example. Outward facing normals make sense if the box is actually a box, inward facing normals make sense if it’s a room, and you are looking at it from the inside. Or what’s the correct normal for a plane?

I guess in your case the special assumption is that the meshes are closed and the normals should face outwards. In this case a distant ray-intersection method like KatCAT suggested should work to find the right normal for the first triangle.

From there you can work your way outwards by looking at adjacent triangles, and determine if they have the same winding, and flip them, if they don’t.
That’s actually quite simple, you just need to look at the vertex indices of the shared edge. I’ll explain by example:

The first triangle is made up of three vertices v1 - v2 - v3. The shared edge is v2 - v3. In the adjacent triangle those two vertices are v2 - v1. The key is that for one triangle the numbers go up, and for the other they go down, which is what you want, because it means the winding is the same. If for both triangles the numbers go up, or for both they go down, you need to flip.

And I forgot about the edge between v1 and v3. For my explanation to be correct v3-v1 counts as “numbers going up”, and v1-v3 counts as “numbers going down”.

if the whole thing is made of quads then there is Only 4 possible combinations.

quad 1 triangle 1 is either cw or ccw triangle 2 is either cw or ccw.

if it has a a vertex list. Then count every 3 triangles and generate the normal from the given function. the next one is its counter part. If it has a indexed list then you probably have to determine the winding mesh by mesh and quad vertice layout which probably would be 0 1 2 then 2 1 3 per each 4 vertices. Really though they should all be the same sort of layout if its just a vertice list the below should apply.

Make a function that allows for any of the 4 possible combinations and run it. Try with the simplest model first. Add a couple keyboard keys in update to change the option and to regenerate them and another to flip the graphics device states culling direction.

Untested pesudo code Edit woops fudged that up.

        public void GenerateNormalPattern(int zeroToThree)
            switch (zeroToThree)
                case 0:
                    vertices = GenerateNormals(false, false, vertices);
                case 1:
                    vertices = GenerateNormals(true, false, vertices);
                case 2:
                    vertices = GenerateNormals(false, true, vertices);
                case 3:
                    vertices = GenerateNormals(true, true, vertices);

        public VertexNormalPosition[] GenerateNormals(bool isTriangle0CCW, bool isTriangle1CCW, VertexNormalPosition[] v)
            int triangleCounter = 0;
            int Even = 0;
            while (triangleCounter < v.Length)
                Vector3 n = new Vector3();
                if (Even == 0)
                    if (isTriangle0CCW)
                        n = CrossProduct3d(v[triangleCounter + 0].pos, v[triangleCounter + 1].pos, v[triangleCounter + 2].pos);
                        n =CrossProduct3d(v[triangleCounter + 0].pos, v[triangleCounter + 2].pos, v[triangleCounter + 1].pos);
                if (Even == 1)
                    if (isTriangle1CCW)
                        n =CrossProduct3d(v[triangleCounter + 0].pos, v[triangleCounter + 1].pos, v[triangleCounter + 2].pos);
                        n =CrossProduct3d(v[triangleCounter + 0].pos, v[triangleCounter + 2].pos, v[triangleCounter + 1].pos);
                // assign n to the vertice normals 0 1 2
                v[triangleCounter + 0].Normal = n;
                v[triangleCounter + 1].Normal = n;
                v[triangleCounter + 2].Normal = n;
                triangleCounter += 3;
                if (Even > 1)
                    Even = 0;
            return v;

If one of those looks about right you still have to smooth it unless its a flat shaded model.

You could also then draw out the normals per triangle vertice to see it in monogame thats what i do for the models i load in just to make sure the model normals were made properly and are in order.

A while ago I had to come up with a way of calculating the volume of a mesh.

In the end I found a solution based on the signed volume of a triangle.

Basically I created a tetrahedron with each triangle and the centre of the object. The volume of this was combined with the face normal to create a signed volume. The sum for all triangles is the volume of the mesh.

I am sure I can do something with this here. Just can’t quite make the last step.

This is an art problem not a programming problem. If you have no normals, and you have a wide variety of geometry (ie, terrain, grass, doorways…) then even if you could figure out which side of the triangle was outward facing, your auto-generated normal would still end up looking terrible in most cases.

Actually that function i posted will generate perfectly smooth normals for vertices with any number of triangles attached to it provided you know the outward inward direction.

Its really not that complicated its just averaging then a final

your average model with bones is in a sense, regenerating them on the fly.

so its not about art its about the model exporter being badly programed.

Sure, if you always want perfectly smooth normals. The original poster however said he has a wide variety of objects, including pillars, doorways, and thousands of other objects. Even something as simple as a barrel will not look good with normals generated from averages.

But it will look fine when you are at 150 feet flying past it at 650 knots with your tail on fire.

Without normals, objects appear to glow and stand out in the landscape

Solved it.

The wavefront format allows groups, but most exporters don’t use them.

So instead I used the material to group triangles.

Once I did that I could calculate a local centre point for each group, and from that I could calculate winding order and hence normals.

It’s by no means perfect, but will do fo my needs

Thanks guys

tool in action , uses the monoforms code which works nicely