meshmodifier.cpp

Go to the documentation of this file.

/*
    Sheep - A Rigid Body Dynamics Engine
    Copyright (C) 2001-2004 Francois Beaune
    Contact: http://toxicengine.sourceforge.net/

    This file is part of Sheep.

    Sheep is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    Sheep is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Sheep; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "meshmodifier.h"   // include first

#include <cassert>
#include <cmath>

//#define VERBOSE

#ifdef VERBOSE
#include <iostream>
#endif  // VERBOSE

using namespace sheep;
using namespace std;

void MeshModifier::ComputeSmoothedVertexNormals(Real smoothing_threshold_angle) {
    m_compute_smoothed_vn = true;
    m_smoothing_threshold_angle = smoothing_threshold_angle;
}

void MeshModifier::OptimizeMesh(Real vertex_welding_threshold_dist,
                                Real normal_welding_threshold_angle)
{
    m_optimize_mesh = true;
    m_vertex_welding_threshold_dist = vertex_welding_threshold_dist;
    m_normal_welding_threshold_angle = normal_welding_threshold_angle;
}

MeshModifier::MeshModifier(IMeshBuilder &builder) :
    m_builder(builder)
{
    m_compute_smoothed_vn = false;
    m_optimize_mesh = false;
}

MeshModifier::~MeshModifier() {
}

// IMeshBuilder interface.

IMeshBuilder::IGeometryBuilder *MeshModifier::GeometryBuilder() {
    if(m_builder.GeometryBuilder())
        return this;
    else return 0;
}

IMeshBuilder::IMaterialBuilder *MeshModifier::MaterialBuilder() {
    if(m_builder.MaterialBuilder())
        return this;
    else return 0;
}

// IGeometryBuilder interface.

void MeshModifier::BeginSubMesh(const string &name) {
    m_sub_mesh = new sub_mesh();
    m_sub_mesh->m_name = name;
    m_sub_mesh->m_material = -1;
}

void MeshModifier::EndSubMesh() {
    // Optimize vertices and faces.
    if(m_optimize_mesh) {
#ifdef VERBOSE
        cerr << "[MeshModifier] Before optimization:" << endl;
        cerr << "[MeshModifier]   Vertices: " << m_sub_mesh->m_vertices.size() << endl;
        cerr << "[MeshModifier]   Normals: " << m_sub_mesh->m_normals.size() << endl;
        cerr << "[MeshModifier]   Faces: " << m_sub_mesh->m_faces.size() << endl;
        cerr << "[MeshModifier] Optimizing faces..." << endl;
#endif  // VERBOSE

        m_sub_mesh->OptimizeFaces();

#ifdef VERBOSE
        cerr << "[MeshModifier] Optimizing vertices..." << endl;
#endif  // VERBOSE

        m_sub_mesh->OptimizeVertices(m_vertex_welding_threshold_dist);
    }

    // Compute smoothed normals.
    if(m_compute_smoothed_vn) {
#ifdef VERBOSE
        cerr << "[MeshModifier] Computing smoothed vertex normals..." << endl;
#endif  // VERBOSE

        m_sub_mesh->ComputeSmoothedVertexNormals(m_smoothing_threshold_angle);
    }

    // Optimize normals.
    if(m_optimize_mesh) {
#ifdef VERBOSE
        cerr << "[MeshModifier] Optimizing normals..." << endl;
#endif  // VERBOSE

        m_sub_mesh->OptimizeNormals(m_normal_welding_threshold_angle);

#ifdef VERBOSE
        cerr << "[MeshModifier] After optimization:" << endl;
        cerr << "[MeshModifier]   Vertices: " << m_sub_mesh->m_vertices.size() << endl;
        cerr << "[MeshModifier]   Normals: " << m_sub_mesh->m_normals.size() << endl;
        cerr << "[MeshModifier]   Faces: " << m_sub_mesh->m_faces.size() << endl;
#endif  // VERBOSE
    }

    // Begin sub mesh description.
    m_builder.GeometryBuilder()->BeginSubMesh(m_sub_mesh->m_name);

    // Send vertices.
    for(vector<Point3>::const_iterator i = m_sub_mesh->m_vertices.begin(),
        e = m_sub_mesh->m_vertices.end(); i != e; ++i)
    {
        m_builder.GeometryBuilder()->AppendVertex(*i);
    }

    // Send normals.
    for(vector<Vector3>::const_iterator i = m_sub_mesh->m_normals.begin(),
        e = m_sub_mesh->m_normals.end(); i != e; ++i)
    {
        m_builder.GeometryBuilder()->AppendNormal(*i);
    }

    // Send texture coordinates.
    for(vector<Vector2>::const_iterator i = m_sub_mesh->m_texcoords.begin(),
        e = m_sub_mesh->m_texcoords.end(); i != e; ++i)
    {
        m_builder.GeometryBuilder()->AppendTexCoord(*i);
    }

    // Send faces.
    for(vector<sub_mesh::face>::const_iterator i = m_sub_mesh->m_faces.begin(),
        e = m_sub_mesh->m_faces.end(); i != e; ++i)
    {
        const FeatureId v[3] = { i->m_v0, i->m_v1, i->m_v2 };
        const FeatureId fid = m_builder.GeometryBuilder()->AppendFace(3, v);

        if(i->m_n0 != -1) {
            const FeatureId vn[3] = { i->m_n0, i->m_n1, i->m_n2 };
            m_builder.GeometryBuilder()->SetFaceNormals(fid, 3, vn);
        }

        if(i->m_t0 != -1) {
            const FeatureId vt[3] = { i->m_t0, i->m_t1, i->m_t2 };
            m_builder.GeometryBuilder()->SetFaceTexCoords(fid, 3, vt);
        }
    }

    if(m_sub_mesh->m_material != -1)
        m_builder.GeometryBuilder()->SetMaterial(m_sub_mesh->m_material);

    // Close sub mesh.
    m_builder.GeometryBuilder()->EndSubMesh();

    delete m_sub_mesh;
}

IMeshBuilder::FeatureId MeshModifier::AppendVertex(const Vector3 &v) {
    m_sub_mesh->m_vertices.push_back(v);

    return m_sub_mesh->m_vertices.size() - 1;
}

IMeshBuilder::FeatureId MeshModifier::AppendNormal(const Vector3 &vn) {
    if(m_compute_smoothed_vn)
        return -1;

    m_sub_mesh->m_normals.push_back(vn);

    return m_sub_mesh->m_normals.size() - 1;
}

IMeshBuilder::FeatureId MeshModifier::AppendTexCoord(const Vector2 &vt) {
    m_sub_mesh->m_texcoords.push_back(vt);

    return m_sub_mesh->m_texcoords.size() - 1;
}

IMeshBuilder::FeatureId MeshModifier::AppendFace(int n, const FeatureId *v) {
    assert(n == 3);
    assert(v);

    sub_mesh::face f;

    f.m_v0 = v[0];
    f.m_v1 = v[1];
    f.m_v2 = v[2];

    f.m_n0 = f.m_n1 = f.m_n2 = -1;
    f.m_t0 = f.m_t1 = f.m_t2 = -1;

    m_sub_mesh->m_faces.push_back(f);

    return m_sub_mesh->m_faces.size() - 1;
}

void MeshModifier::SetFaceNormals(FeatureId face, int n, const FeatureId *vn) {
    assert(face >= 0 && face < m_sub_mesh->m_faces.size());
    assert(n == 3);
    assert(vn);

    if(!m_compute_smoothed_vn) {
        sub_mesh::face &f = m_sub_mesh->m_faces[face];

        f.m_n0 = vn[0];
        f.m_n1 = vn[1];
        f.m_n2 = vn[2];
    }
}

void MeshModifier::SetFaceTexCoords(FeatureId face, int n, const FeatureId *vt) {
    assert(face >= 0 && face < m_sub_mesh->m_faces.size());
    assert(n == 3);
    assert(vt);

    sub_mesh::face &f = m_sub_mesh->m_faces[face];

    f.m_t0 = vt[0];
    f.m_t1 = vt[1];
    f.m_t2 = vt[2];
}

void MeshModifier::SetMaterial(FeatureId material) {
    m_sub_mesh->m_material = material;
}

// IMaterialBuilder interface.

IMeshBuilder::FeatureId MeshModifier::BeginMaterial(const string &name) {
    return m_builder.MaterialBuilder()->BeginMaterial(name);
}

void MeshModifier::EndMaterial() {
    m_builder.MaterialBuilder()->EndMaterial();
}

void MeshModifier::SetAmbientColor(Real r, Real g, Real b) {
    m_builder.MaterialBuilder()->SetAmbientColor(r, g, b);
}

void MeshModifier::SetDiffuseColor(Real r, Real g, Real b) {
    m_builder.MaterialBuilder()->SetDiffuseColor(r, g, b);
}

void MeshModifier::SetSpecularColor(Real r, Real g, Real b) {
    m_builder.MaterialBuilder()->SetSpecularColor(r, g, b);
}

void MeshModifier::SetTexture(int w, int h, const unsigned char *texels) {  //!< 24-bit RGB format.
    m_builder.MaterialBuilder()->SetTexture(w, h, texels);
}

    // Build smoothed normals whithout threshold angle.

/*  m_submesh->m_normals.clear();
    m_submesh->m_normals.reserve(m_submesh->m_vertices.size());

    for(int i = 0; i < m_submesh->m_vertices.size(); ++i) {
        m_submesh->m_normals.push_back(Vector3(0.0));
    }

    for(GLMesh::SubMesh::FaceVectorIt i = m_submesh->m_faces.begin(),
        e = m_submesh->m_faces.end(); i != e; ++i)
    {
        GLMesh::SubMesh::Face &f = *i;

        const Point3 &v0 = m_submesh->m_vertices[f.m_v0];
        const Point3 &v1 = m_submesh->m_vertices[f.m_v1];
        const Point3 &v2 = m_submesh->m_vertices[f.m_v2];

        const Vector3 e0 = v1 - v0;
        const Vector3 e1 = v2 - v0;
        const Vector3 face_normal = (e0 ^ e1).Normalized();

        f.m_n0 = f.m_v0;
        f.m_n1 = f.m_v1;
        f.m_n2 = f.m_v2;

        m_submesh->m_normals[f.m_n0] += face_normal;
        m_submesh->m_normals[f.m_n1] += face_normal;
        m_submesh->m_normals[f.m_n2] += face_normal;
    }

    for(GLMesh::SubMesh::Vector3VectorIt i = m_submesh->m_normals.begin(),
        e = m_submesh->m_normals.end(); i != e; ++i)
    {
        i->Normalize();
    }*/

    // Build normals for flat-shading.

/*  m_submesh->m_normals.clear();

    for(GLMesh::SubMesh::FaceVectorIt i = m_submesh->m_faces.begin(),
        e = m_submesh->m_faces.end(); i != e; ++i)
    {
        GLMesh::SubMesh::Face &f = *i;

//      if(f.m_n0 == -1 || f.m_n1 == -1 || f.m_n2 == -1) {
            const Point3 &v0 = m_submesh->m_vertices[f.m_v0];
            const Point3 &v1 = m_submesh->m_vertices[f.m_v1];
            const Point3 &v2 = m_submesh->m_vertices[f.m_v2];

            const Vector3 e0 = v1 - v0;
            const Vector3 e1 = v2 - v0;
            const Vector3 vn = (e0 ^ e1).Normalized();

            m_submesh->m_normals.push_back(vn);

            f.m_n0 = f.m_n1 = f.m_n2 =
                static_cast<FeatureId>(m_submesh->m_normals.size() - 1);
//      }
    }*/

void MeshModifier::sub_mesh::ComputeSmoothedVertexNormals(Real smoothing_threshold_angle) {
    assert(smoothing_threshold_angle >= 0.0);

    const Real cos_smoothing_threshold_angle = cos(smoothing_threshold_angle);

    const int vertex_count = m_vertices.size();
    const int face_count = m_faces.size();

    // Compute geometric normal to each face.

    Vector3 *face_normals = new Vector3[face_count];

    for(int i = 0; i < face_count; ++i) {
        const face &f = m_faces[i];

        const Point3 &v0 = m_vertices[f.m_v0];
        const Point3 &v1 = m_vertices[f.m_v1];
        const Point3 &v2 = m_vertices[f.m_v2];

        const Vector3 e0 = v1 - v0;
        const Vector3 e1 = v2 - v0;

        face_normals[i] = (e0 ^ e1).Normalized();
    }

    // Find the list of faces each vertex belongs to.

    vector<int> *vertex_membership = new vector<int>[vertex_count];

    for(int i = 0; i < face_count; ++i) {
        const face &f = m_faces[i];

        vertex_membership[f.m_v0].push_back(i);
        vertex_membership[f.m_v1].push_back(i);
        vertex_membership[f.m_v2].push_back(i);
    }

    // Compute smoothed normals.

    vector<Vector3> smoothed_normals;

    for(int i = 0; i < vertex_count; ++i) {
        const vector<int> &member_faces = vertex_membership[i];

        // Make sure this vertex belongs to at least one face.
        assert(member_faces.size() > 0);

        for(int j = 0; j < member_faces.size(); ++j) {
            const int face1_index = member_faces[j];
            face &face1 = m_faces[face1_index];
            const Vector3 &face1_normal = face_normals[face1_index];

            const int smoothed_normal_index = smoothed_normals.size();
            Vector3 smoothed_normal = face1_normal;

            if(face1.m_v0 == i) face1.m_n0 = smoothed_normal_index;
            if(face1.m_v1 == i) face1.m_n1 = smoothed_normal_index;
            if(face1.m_v2 == i) face1.m_n2 = smoothed_normal_index;

            for(int k = 0; k < member_faces.size(); ++k) {
                if(j != k) {
                    const int face2_index = member_faces[k];
                    face &face2 = m_faces[face2_index];
                    const Vector3 &face2_normal = face_normals[face2_index];

                    if(face1_normal * face2_normal > cos_smoothing_threshold_angle) {
                        smoothed_normal += face2_normal;

                        if(face2.m_v0 == i) face2.m_n0 = smoothed_normal_index;
                        if(face2.m_v1 == i) face2.m_n1 = smoothed_normal_index;
                        if(face2.m_v2 == i) face2.m_n2 = smoothed_normal_index;
                    }
                }
            }

            smoothed_normal.Normalize();
            smoothed_normals.push_back(smoothed_normal);
        }
    }

    delete [] vertex_membership;
    delete [] face_normals;

    // Replace old normals with smoothed normals.
    m_normals.resize(smoothed_normals.size());
    copy(smoothed_normals.begin(), smoothed_normals.end(), m_normals.begin());
}

void MeshModifier::sub_mesh::OptimizeVertices(Real welding_threshold_dist) {
    assert(welding_threshold_dist >= 0.0);

    const Real welding_threshold_dist2 = sq(welding_threshold_dist);

    vector<Point3> new_vertices;
    int *tt = new int[m_vertices.size()];   // translation table

    for(int i = 0; i < m_vertices.size(); ++i) {
        const Point3 &p = m_vertices[i];

        tt[i] = -1;

        for(int j = 0; j < new_vertices.size(); ++j) {
            const Real distance2 = (p - new_vertices[j]).SquareNorm();

            if(distance2 < welding_threshold_dist2) {
                tt[i] = j;
                break;
            }
        }

        if(tt[i] == -1) {
            tt[i] = new_vertices.size();
            new_vertices.push_back(p);
        }
    }

    // Replace old vertices with new vertices.
    m_vertices.resize(new_vertices.size());
    copy(new_vertices.begin(), new_vertices.end(), m_vertices.begin());

    // Fix face vertex indices.
    for(vector<face>::iterator i = m_faces.begin(), e = m_faces.end(); i != e; ++i) {
        i->m_v0 = tt[i->m_v0];
        i->m_v1 = tt[i->m_v1];
        i->m_v2 = tt[i->m_v2];
    }

    delete [] tt;
}

void MeshModifier::sub_mesh::OptimizeNormals(Real welding_threshold_angle) {
    assert(welding_threshold_angle >= 0.0);

    const Real cos_welding_threshold_angle = cos(welding_threshold_angle);

    vector<Vector3> new_normals;
    int *tt = new int[m_normals.size()];    // translation table

    for(int i = 0; i < m_normals.size(); ++i) {
        const Vector3 &n = m_normals[i];

        assert(n.IsUnitLength());

        tt[i] = -1;

        for(int j = 0; j < new_normals.size(); ++j) {
            const Real cos_angle = n * new_normals[j];

            if(cos_angle > cos_welding_threshold_angle) {
                tt[i] = j;
                break;
            }
        }

        if(tt[i] == -1) {
            tt[i] = new_normals.size();
            new_normals.push_back(n);
        }
    }

    // Replace old normals with new normals.
    m_normals.resize(new_normals.size());
    copy(new_normals.begin(), new_normals.end(), m_normals.begin());

    // Fix face normal indices.
    for(vector<face>::iterator i = m_faces.begin(), e = m_faces.end(); i != e; ++i) {
        i->m_n0 = tt[i->m_n0];
        i->m_n1 = tt[i->m_n1];
        i->m_n2 = tt[i->m_n2];
    }

    delete [] tt;
}

void MeshModifier::sub_mesh::OptimizeFaces() {
    vector<face> new_faces;

    for(vector<face>::iterator i = m_faces.begin(), e = m_faces.end(); i != e; ++i) {
        face &f = *i;

        if( f.m_v0 != f.m_v1 &&
            f.m_v0 != f.m_v2 &&
            f.m_v1 != f.m_v2)
        {
            new_faces.push_back(f);
        }
    }

    // Replace old faces with new faces.
    m_faces.resize(new_faces.size());
    copy(new_faces.begin(), new_faces.end(), m_faces.begin());
}

---