Mesh Data Structure in C++

Data Structures for Representing a Mesh Model and Calculating Normals in C++

1. Data Structures for Representing a 3D Mesh

A 3D mesh typically consists of three main components:

• Vertices: Points in 3D space.

• Normals: Vectors perpendicular to the surfaces of the mesh, used for lighting calculations.

• Faces: Triangular or polygonal faces defined by indices of vertices (and optionally, texture coordinates and normals).

1.1. Mesh Representation

In C++, we can use several basic data structures like std::vector to store the components of a mesh. Let’s start by defining the fundamental structures for vertices, normals, and faces.

Vertex Structure

The Vertex structure holds the position of a point in 3D space.

struct Vertex {
    float x, y, z;

    Vertex() : x(0), y(0), z(0) {}
    Vertex(float x, float y, float z) : x(x), y(y), z(z) {}

    // Optionally, implement basic vector math (dot product, cross product, etc.)
    Vertex operator-(const Vertex& other) const {
        return Vertex(x - other.x, y - other.y, z - other.z);
    }

    float dot(const Vertex& other) const {
        return x * other.x + y * other.y + z * other.z;
    }

    Vertex cross(const Vertex& other) const {
        return Vertex(
            y * other.z - z * other.y,
            z * other.x - x * other.z,
            x * other.y - y * other.x
        );
    }

    // Normalize the vertex (treat it as a vector)
    Vertex normalize() const {
        float length = std::sqrt(x * x + y * y + z * z);
        return Vertex(x / length, y / length, z / length);
    }
};

Normal Structure

Normals are also represented by Vertex (since they are vectors in 3D space) but are calculated based on the geometry of the mesh.

struct Normal {
    float nx, ny, nz;

    Normal() : nx(0), ny(0), nz(0) {}
    Normal(float nx, float ny, float nz) : nx(nx), ny(ny), nz(nz) {}

    Normal normalize() const {
        float length = std::sqrt(nx * nx + ny * ny + nz * nz);
        return Normal(nx / length, ny / length, nz / length);
    }

    float dot(const Normal& other) const {
        return nx * other.nx + ny * other.ny + nz * other.nz;
    }
};

Face Structure

Each Face is typically a triangle (for simplicity in this tutorial), but can be extended for polygons with more vertices. The face structure stores indices to the vertices and normals.

struct Face {
    int v1, v2, v3;   // Indices to the vertices of the triangle
    int n1, n2, n3;   // Indices to the normals for each vertex
};

1.2. Mesh Class

The Mesh class holds the vectors of vertices, normals, and faces, and provides an interface to interact with the mesh data.

class Mesh {
public:
    std::vector<Vertex> vertices;
    std::vector<Normal> normals;
    std::vector<Face> faces;

    void addVertex(const Vertex& vertex) {
        vertices.push_back(vertex);
    }

    void addNormal(const Normal& normal) {
        normals.push_back(normal);
    }

    void addFace(int v1, int v2, int v3, int n1, int n2, int n3) {
        faces.push_back(Face{v1, v2, v3, n1, n2, n3});
    }
};

---

2. Algorithm for Calculating Normals for Triangle Meshes

For a triangle mesh, normals can be computed per-face or per-vertex. In this tutorial, we will compute per-face normals and per-vertex normals.

2.1. Per-Face Normal Calculation

A face normal is calculated using the cross product of two edge vectors from the triangle. Given three vertices of a triangle, the two edges can be represented as:

Edge1=Vertex2−Vertex1\text{Edge1} = \text{Vertex2} - \text{Vertex1}Edge1=Vertex2−Vertex1 Edge2=Vertex3−Vertex1\text{Edge2} = \text{Vertex3} - \text{Vertex1}Edge2=Vertex3−Vertex1

The normal is then the cross product of these two edge vectors:

Normal=Edge1×Edge2\text{Normal} = \text{Edge1} \times \text{Edge2}Normal=Edge1×Edge2

This will give us a normal vector perpendicular to the triangle’s surface.

Normal calculateFaceNormal(const Vertex& v1, const Vertex& v2, const Vertex& v3) {
    Vertex edge1 = v2 - v1;
    Vertex edge2 = v3 - v1;
    Vertex normal = edge1.cross(edge2);
    return normal.normalize();
}

2.2. Per-Vertex Normal Calculation

To compute per-vertex normals, we average the normals of the faces that share each vertex. This smooths out lighting across the mesh. Here’s the algorithm:

1. For each vertex, find the faces that use it.

2. Sum the face normals of those faces.

3. Normalize the resulting vector.

void calculateVertexNormals(Mesh& mesh) {
    // Initialize normals to zero
    mesh.normals.resize(mesh.vertices.size(), Normal(0, 0, 0));

    // Calculate face normals and accumulate into vertex normals
    for (const auto& face : mesh.faces) {
        const Vertex& v1 = mesh.vertices[face.v1 - 1];
        const Vertex& v2 = mesh.vertices[face.v2 - 1];
        const Vertex& v3 = mesh.vertices[face.v3 - 1];
        
        // Calculate face normal
        Normal faceNormal = calculateFaceNormal(v1, v2, v3);

        // Add face normal to each vertex normal (for shared vertices)
        mesh.normals[face.v1 - 1] = mesh.normals[face.v1 - 1] + faceNormal;
        mesh.normals[face.v2 - 1] = mesh.normals[face.v2 - 1] + faceNormal;
        mesh.normals[face.v3 - 1] = mesh.normals[face.v3 - 1] + faceNormal;
    }

    // Normalize vertex normals
    for (auto& normal : mesh.normals) {
        normal = normal.normalize();
    }
}

2.3. Vector Operations

For the per-vertex normal calculation, you’ll need to implement basic vector operations like addition and normalization. Below is how you can add these operations:

Normal operator+(const Normal& n1, const Normal& n2) {
    return Normal(n1.nx + n2.nx, n1.ny + n2.ny, n1.nz + n2.nz);
}

3. Putting It All Together

Here’s how you can put everything together in your program:

int main() {
    Mesh mesh;

    // Add vertices (example)
    mesh.addVertex(Vertex(0.0f, 0.0f, 0.0f));
    mesh.addVertex(Vertex(1.0f, 0.0f, 0.0f));
    mesh.addVertex(Vertex(0.0f, 1.0f, 0.0f));

    // Add a face (triangle)
    mesh.addFace(1, 2, 3, 1, 1, 1);

    // Calculate per-face normals
    for (const auto& face : mesh.faces) {
        const Vertex& v1 = mesh.vertices[face.v1 - 1];
        const Vertex& v2 = mesh.vertices[face.v2 - 1];
        const Vertex& v3 = mesh.vertices[face.v3 - 1];
        
        Normal faceNormal = calculateFaceNormal(v1, v2, v3);
        std::cout << "Face Normal: " << faceNormal.nx << ", " << faceNormal.ny << ", " << faceNormal.nz << std::endl;
    }

    // Calculate per-vertex normals
    calculateVertexNormals(mesh);
    for (const auto& normal : mesh.normals) {
        std::cout << "Vertex Normal: " << normal.nx << ", " << normal.ny << ", " << normal.nz << std::endl;
    }

    return 0;
}

Conclusion

In this tutorial, we explored the data structures for representing a 3D mesh in C++, including vertices, normals, and faces. We also covered the algorithms for calculating normals for a triangle mesh, both per-face and per-vertex. The basic operations like cross product, dot product, and normalization were also demonstrated.

By calculating normals, you can enable accurate lighting effects for rendering 3D models, such as diffuse and specular lighting, which are essential for realistic graphics in 3D engines.

Let me know if you'd like to dive deeper into any of the topics covered!