3

In a lot of 3D design programs such as Blender and 3D Studio Max you can select which surfaces of a shape you want smooth as opposed to hard and flat. This amounts to averaging (I assume) the normals of the vertices which share the same position as a particular vertex. I am trying to write something of the sort, but this is my first time doing this and the way I came up with must be really inefficient and I believe is n^2 time complexity. So given we have a 3D shape with 99 vertices, then the loop must run 99 x 99 times, almost 10,000 times.

With a ball it's easy as each vertex's normal is just the normalised position of the vertex (the unit vector of the position). I can do that easy as shown below:

enter image description here

I was wondering how these programs do it and if there's a more efficient way than this. My method is to loop through i from 0 to 99 and j from 0 to 99. I basically go through and check if another vertex has the same position, if so, I check whether the angle between its normal and the normal of the other vertex is under the desired angle threshold. If so, I add it to the sum of the vector, then I divide by the number of vertices that were matched. I'm not sure if this is correct.

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

float thresholdAngle = 60 /*degrees*/ / 180 * 3.14159; // In radians

struct vec3
{
    float x, y, z;
    bool hasSamePositionAs(vec3& other)
    {
        if (other.x == this->x &&
            other.y == this->y &&
            other.z == this->z)
            return true;
        return false;
    }

    bool angleIsUnderThresholdWith(vec3& other)
    {//THIS SHOULD BE IF DOTPRODUCT > COS(THRESHOLDANGLE)
        return dotProductWith(other) < thresholdAngle ? true : false;
    }

    float dotProductWith(vec3& other)
    {
        return x * other.x + y * other.y + z * other.z;
    }

    void operator +=(vec3 other) { x += other.x; y += other.y; z + other.z; }

int main() 
{
    // 33 triangles, 99 vertices
    vector<vec3> vertices(99); // ALL UNIT VECTORS, NORMALS
    vector<vec3> newNormals(99);

    for (int i = 0; i < 99; i++)
    {
        vec3 normal = vertices[i];

        for (int j = 0; j < 99; j++)
        {
            if (j == i) continue;
            if (vertices[i].hasSamePositionAs(vertices[j]))
            {
                if (vertices[i].angleIsUnderThresholdWith(vertices[j]))
                {
                    normal += vertices[j];
                }
            }
        }

        normalise(normal);          
        newNormals[i] = normal;
        }
    }

Edit: OK so using this code I managed to get what I was after, but the algorithm is still n^2. You can notice the blue lines, which are the normals, are separated for each face in flat shading, and merged together (averaged) when passing it through this code.

enter image description here

Zebrafish
  • 11,682
  • 3
  • 43
  • 119
  • May be a duplicate of [this](https://stackoverflow.com/questions/13205226/most-efficient-algorithm-to-calculate-vertex-normals-from-set-of-triangles-for-g) question? –  Jul 04 '18 at 02:44
  • Or maybe something from the [tag:Phong] shading questons. – 1201ProgramAlarm Jul 04 '18 at 04:59
  • Your sample code has your vertices on a unit circle, and normals that match the vertices. The normals are not stored with the faces. Since every face with a particular vertex has the same normal, you don't need to compute an average. Also, the dot product of two unit vectors gives you the cosine of the angle between them (what's the dot product of a vector with itself?). Your `angleIsUnderThresholdWith` will always return true. – 1201ProgramAlarm Jul 04 '18 at 05:07
  • @1201ProgramAlarm Ah thanks, it should be if dot product is less than cos(thresholdAngle). What do you mean I don't need to compute an average? The pictures are just showing how I made smooth or flat on a ball by simply normalising the vertex positions, the code I have runs through every vertex and averages it because no information about the mesh is known. My understanding is that each vertex needs to be averaged with any other vertex touching it forming another face. – Zebrafish Jul 04 '18 at 05:26
  • @1201ProgramAlarm A unit vector dotted with itself should give 1, I need to take the cosine of that and check it against the threshold angle. My problem is avoiding having it n^2. I'm thinking I can run through it and save which vertices touch which, but I haven't figured it out. – Zebrafish Jul 04 '18 at 05:35
  • I might be nitpicking, but unless the x, y, z values are `int` or similar, you may run into problems with that `==` check. – a concerned citizen Jul 04 '18 at 06:00
  • @a concerned citizen Your concern is appreciated. Yes, I know exactly what you're talking about, touching faces aren't guaranteed to have exactly the same vertex positions. This is just a working example, eventually I might include any vertex within a certain distance of any others. I used to use 3D Studio Max a lot and took for granted a lot of the stuff it does. Diving into it for my graphics engine is pretty interesting. – Zebrafish Jul 04 '18 at 06:29
  • @Zebrafish What I mean about the average is that since you don't have a separate normal for the vertex (you're using the vertex as both the position and the normal) all the normals for all copies of the vertex will be the same. If you have separate normals for the verts then you'd want to average them. – 1201ProgramAlarm Jul 04 '18 at 14:51

0 Answers0