MeshFaces.cpp

Go to the documentation of this file.

/* Copyright © 2009, 2010 James Legg.
    This program 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 3 of the License, or
    (at your option) any later version.
*/

#include "MeshFaces.h"

#include "../stream_loader.h"
#include <Debug.h>

#include <fstream>
#include <LinearMath/btMatrix3x3.h>

namespace Track
{

MeshFaces::FaceVertex::FaceVertex()
{
}

MeshFaces::FaceVertex::FaceVertex(std::size_t vertex_index)
    :   vertex_index(vertex_index)
{
}

MeshFaces::Face::Face()
{
}

MeshFaces::Face::Face(std::size_t v1, std::size_t v2, std::size_t v3)
    :
    fv1(v1),
    fv2(v2),
    fv3(v3)
{
}

MeshFaces::Face::Face(const FaceVertex & v1, const FaceVertex & v2, const FaceVertex & v3)
    :
    fv1(v1),
    fv2(v2),
    fv3(v3)
{
}

MeshFaces::Edge::Edge(std::size_t v1, std::size_t v2)
    :
    v1(v1),
    v2(v2)
{
}

bool MeshFaces::Edge::operator<(MeshFaces::Edge o) const
{
    // arrange so we are comparing the elements regardless of order.
    std::size_t m_small, m_large;
    if (v1 < v2)
    {
        m_small = v1;
        m_large = v2;
    } else {
        m_small = v2;
        m_large = v1;
    }
    std::size_t o_small, o_large;
    if (o.v1 < o.v2)
    {
        o_small = o.v1;
        o_large = o.v2;
    } else {
        o_small = o.v2;
        o_large = o.v1;
    }
    if (m_small < o_small) return true;
    if (m_small > o_small) return false;
    if (m_large < o_large) return true;
    return false;
}

MeshFaces::FaceGraph::FaceGraph(const Face & face)
    :   Face(face)
{
}

btVector3 MeshFaces::FaceGraph::to_face_coords(btVector3 world_coords) const
{
    btVector3 local = world_coords - vertex_positions[0];
    return btVector3(world_to_face.tdotx(local),
                     world_to_face.tdoty(local),
                     world_to_face.tdotz(local));
}

btVector3 MeshFaces::FaceGraph::to_world_coords(btVector3 face_coords) const
{
    btVector3 local = btVector3(face_to_world.tdotx(face_coords),
                                face_to_world.tdoty(face_coords),
                                face_to_world.tdotz(face_coords));
    return  local + vertex_positions[0];
}

void MeshFaces::FaceGraph::set_conversions()
{
    face_to_world = btMatrix3x3(edges[0].x(), edges[0].y(), edges[0].z(),
                                edges[1].x(), edges[1].y(), edges[1].z(),
                                face_normal.x(), face_normal.y(), face_normal.z());
    world_to_face = face_to_world.inverse();
    edge_line_segments[0] = Line(vertex_positions[0], vertex_positions[1]);
    edge_line_segments[1] = Line(vertex_positions[1], vertex_positions[2]);
    edge_line_segments[2] = Line(vertex_positions[2], vertex_positions[0]);
    for (int i = 0; i < 3; i++)
    {
        edge_planes[i] = edge_line_segments[i].get_plane_including(face_normal);
    }
    
    face_plane = Plane(face_normal, -face_normal.dot(vertex_positions[0]));
}

btVector3 MeshFaces::FaceGraph::find_nearest_point(btVector3 position) const
{
    for (int i = 0; i < 3; i++)
    {
        if (!edge_planes[i].find_side(position))
        {
            // outside, find nearest point on the line segment.
            return edge_line_segments[i].closest_point_segment(position);
        }
    }
    // On the inside of the triangle.
    // Find the nearest point to the plane, because that is the nearest point.
    return face_plane.find_nearest_point(position);
}

MeshFaces::MeshFaces()
{
}

MeshFaces::MeshFaces(std::istream & source)
{
    load_from_stream(source);
}

MeshFaces::MeshFaces(std::string & filename)
{
    std::ifstream file(filename.c_str());
    load_from_stream(file);
}

void MeshFaces::load_from_stream(std::istream & source)
{
    DEBUG_MESSAGE("Loading Track::MeshFaces from stream.");
    
    std::size_t number_of_vertices;
    source >> number_of_vertices;
    DEBUG_MESSAGE("Loading " << number_of_vertices << " verticies. Now at "  << source.tellg());
    vertices_position.reserve(number_of_vertices);
    for(unsigned int i = 0; i < number_of_vertices; i++)
    {
        btScalar x, y, z;
        source >> x >> y >> z;
        vertices_position.push_back(btVector3(x, y, z));
        bounds |= btVector3(x, y, z);
    } 
    
    std::size_t number_of_faces;
    source >> number_of_faces;
    DEBUG_MESSAGE("Loading " << number_of_faces << " faces. Now at " << source.tellg());
    faces.reserve(number_of_faces);
    for(unsigned int f = 0; f < number_of_faces; f++)
    {
        FaceVertex fvs[3];
        for (unsigned int i = 0; i < 3; i++)
        {
            // vertex normal
            btScalar x, y, z;
            source >> x >> y >> z;
            fvs[i].normal = btVector3(x, y, z);
            
            // texture coordinates
            source >> fvs[i].texture_coord_u;
            source >> fvs[i].texture_coord_v;
            
            // vertex position index in vertices_position array.
            source >> fvs[i].vertex_index;
        }
        add_face(Face(fvs[0], fvs[1], fvs[2]));
    }
    DEBUG_MESSAGE("Finished loading Track::MeshFaces. Now at " << source.tellg());
}

MeshFaces::~MeshFaces()
{
}

btVector3 MeshFaces::get_vertex_pos(std::size_t index) const
{
    assert(index < vertices_position.size()); 
    return vertices_position[index];
}

void MeshFaces::add_vertex(const btVector3 & position)
{
    vertices_position.push_back(position);
    bounds |= position;
}

std::size_t MeshFaces::get_num_vertices() const
{
    return vertices_position.size();
}
    
const MeshFaces::Face & MeshFaces::get_face(std::size_t index) const
{
    assert(index < faces.size());
    return faces[index];
}

std::vector<MeshFaces::Edge> MeshFaces::get_edges_for_face(std::size_t face_index) const
{
    assert(face_index < faces.size());
    const Face & face = faces[face_index];
    
    std::vector<MeshFaces::Edge> result;
    result.reserve(3);
    result.push_back(Edge(face.fv1.vertex_index, face.fv2.vertex_index));
    result.push_back(Edge(face.fv2.vertex_index, face.fv3.vertex_index));
    result.push_back(Edge(face.fv3.vertex_index, face.fv1.vertex_index));
    return result;
}

void MeshFaces::add_face(std::size_t v1, std::size_t v2, std::size_t v3)
{
    add_face(Face(v1, v2, v3));
}

void MeshFaces::add_face(MeshFaces::Face face)
{
    std::size_t face_index = faces.size();
    faces.push_back(face);
}

void MeshFaces::add_edge(std::size_t v1, std::size_t v2, std::size_t face_index,
              std::map<EdgeGraph, std::size_t> & edge_to_face,
              std::vector<std::pair<std::size_t, std::size_t> > & graph_edges,
              std::vector<EdgeGraph> & edge_properties) const
{
    EdgeGraph edge(v1, v2);
    std::pair<std::map<EdgeGraph, std::size_t>::iterator, bool> it(
            edge_to_face.insert(std::pair<EdgeGraph, std::size_t>(edge, face_index))
        );
    if (!it.second)
    {
        // already used by one face.
        // add to list of graph edges.
        graph_edges.push_back(
                                std::pair<std::size_t, std::size_t>
                                (edge_to_face[edge], face_index)
                             );
        // find other edge data.
        edge.v1_pos = vertices_position[v1];
        edge.v2_pos = vertices_position[v2];
        edge.length = (edge.v1_pos - edge.v2_pos).length();
        
        edge_properties.push_back(edge);
    }
}

std::size_t MeshFaces::get_number_of_faces() const
{
    return faces.size();
}

MeshFaces::Graph MeshFaces::get_connectivity() const
{
    // Find the shared edges. An edge should belong to only one face or two.
    // We take the index of the first face we find using an edge and store it
    // When we find another face using the same edge, this edge needs to be
    // inserted into a graph of the edges.
    std::map<EdgeGraph, std::size_t> edge_to_face;
    std::vector<std::pair<std::size_t, std::size_t> > graph_edges;
    std::vector<EdgeGraph> edge_properties;
    std::size_t face_index = 0;
    for (std::vector<Face>::const_iterator face_it = faces.begin();
         face_it != faces.end();
         face_it++, face_index++)
    {
        // find the 3 edges
        add_edge(face_it->fv1.vertex_index, face_it->fv2.vertex_index,
                 face_index,
                 edge_to_face, graph_edges, edge_properties);
        add_edge(face_it->fv2.vertex_index, face_it->fv3.vertex_index,
                 face_index,
                 edge_to_face, graph_edges, edge_properties);
        add_edge(face_it->fv3.vertex_index, face_it->fv1.vertex_index,
                 face_index,
                 edge_to_face, graph_edges, edge_properties);
    }
    // create a graph from the list of faces sharing an edge.
    Graph result(graph_edges.begin(), graph_edges.end(), edge_properties.begin(),
                  faces.size());
    assert(boost::num_vertices(result) == faces.size());
    assert(boost::num_edges(result) == graph_edges.size());
    typedef boost::graph_traits<Graph>::vertex_iterator VertexIterator;
    std::pair<VertexIterator, VertexIterator> vp = boost::vertices(result);
    for (std::vector<Face>::const_iterator face_it = faces.begin();
         vp.first != vp.second;
         ++vp.first, face_it++)
    {
        Graph::vertex_descriptor v = *vp.first;
        FaceGraph & face_graph = result[v];
        // copy information about the face to the graph.
        face_graph = FaceGraph(*face_it);
        // add additional data about the face.
        face_graph.vertex_positions[0] = vertices_position[face_it->fv1.vertex_index];
        face_graph.vertex_positions[1] = vertices_position[face_it->fv2.vertex_index];
        face_graph.vertex_positions[2] = vertices_position[face_it->fv3.vertex_index];
        face_graph.face_centre = (face_graph.vertex_positions[0] +
                                  face_graph.vertex_positions[1] +
                                  face_graph.vertex_positions[2]) / 3.0;
        face_graph.edges[0] = face_graph.vertex_positions[1] - face_graph.vertex_positions[0];
        face_graph.edges[1] = face_graph.vertex_positions[2] - face_graph.vertex_positions[0];
        face_graph.face_normal = face_graph.edges[0].cross(face_graph.edges[1]).normalized();
        face_graph.set_conversions();
    }
    return result;
}

MeshFaces::VertexGraph MeshFaces::get_vertex_graph()
{
    VertexGraph result;
    // add vertex positions.
    for (std::vector<btVector3>::iterator it = vertices_position.begin();
         it != vertices_position.end();
         it++)
    {
        boost::add_vertex(*it, result);
    }
    // add edges
    for (std::vector<Face>::iterator it = faces.begin();
         it != faces.end();
         it++)
    {
#define do_edge(v1, v2)\
        boost::add_edge(it->fv##v1.vertex_index, it->fv##v2.vertex_index,\
                        FaceEdgePointers(&(*it), &(it->fv##v1), &(it->fv##v2),\
                                         vertices_position[it->fv##v1.vertex_index].distance(vertices_position[it->fv##v2.vertex_index])),\
                        result)
        do_edge(1,2);
        do_edge(2,3);
        do_edge(3,1);
#undef do_edge
    }
    return result;
}

void MeshFaces::copy_faces(const MeshFaces & other)
{
    faces = other.faces;
    // Set normals for each face vertex.
    for (std::vector<Face>::iterator it = faces.begin(); it != faces.end(); it++)
    {
        // solid shading: face normals are consistant across a face
        btVector3 & v1 = vertices_position[it->fv1.vertex_index];
        btVector3 & v2 = vertices_position[it->fv2.vertex_index];
        btVector3 & v3 = vertices_position[it->fv3.vertex_index];
        btVector3 n = (v2-v1).cross(v3-v1).normalize();
        it->fv1.normal = n;
        it->fv2.normal = n;
        it->fv3.normal = n;
    }
}

void MeshFaces::add_faces(btTriangleMesh & shape) const
{
    for (std::vector<Face>::const_iterator it = faces.begin(); it != faces.end(); it++)
    {
        btVector3 verts[3];
#define face_vertex( index, vert ) \
        verts[index] = vertices_position[vert.vertex_index]
        
        face_vertex(0, it->fv1);
        face_vertex(1, it->fv2);
        face_vertex(2, it->fv3);
#undef face_vertex
        shape.addTriangle(verts[2], verts[1], verts[0]);
    }
}

AxisAlignedBoundingBox MeshFaces::get_bounds() const
{
    return bounds;
}

void MeshFaces::merge_doubles(btScalar distance2)
{
    // Check each vertex against each vertex before it.
    // If the distances are too small, remember a substitution.
    std::size_t offset(0);
    std::map<std::size_t, std::size_t> substitutions;
    std::set<std::size_t> deletion_queue;
    for(std::size_t search_index = 0;
        search_index < vertices_position.size();
        search_index++)
    {
        bool provided_substitution = false;
        for(std::size_t compare_index = 0;
            compare_index < search_index;
            compare_index++)
        {
            if (vertices_position[search_index].distance2(vertices_position[compare_index]) < distance2)
            {
                // Always use the lower numbered vertex, so we don't need 
                // change substitutions for vertices already scanned.
                // Use one extra layer of substitution, this corrects offset
                // adjustments and merging into a vertex already merged.
                substitutions[search_index] = substitutions[compare_index];
                provided_substitution = true;
                deletion_queue.insert(search_index);
                // Now all later vertices will need a lower number.
                offset++;
                // We only merge one at a time, so don't look for more.
                break;
            }
        }
        // substitute for a lower number since preceeding vertices will
        // be deleted, unless we already made a substitution.
        if (!provided_substitution)
        {
            // We do this even if offset is 0 to make a 1-1 mapping, where
            // we don't need to check if a substitution has been made before
            // using it.
            substitutions[search_index] = search_index - offset;
        }
    }
    if (offset > 0)
    {
        // Make the substitutions.
        for (std::vector<Face>::iterator it = faces.begin();
             it != faces.end(); it++)
        {
            std::map<std::size_t, std::size_t>::iterator sub_it;
            #define do_vert(vertex_number)\
            sub_it = substitutions.find(it->fv##vertex_number.vertex_index);\
            it->fv##vertex_number.vertex_index = sub_it->second;
            
            do_vert(1);
            do_vert(2);
            do_vert(3);
            #undef do_vert
        }
        
        // delete vertices no longer needed.
        for (std::set<std::size_t>::reverse_iterator it = deletion_queue.rbegin();
             it != deletion_queue.rend();
             it++)
        {
            vertices_position.erase(vertices_position.begin() + *it);
        }
    }
    // bounds may become minimally smaller, but we don't bother checking.
}

void MeshFaces::operator|=(const MeshFaces & source)
{
    // New faces will have a different vertex indecies, depening on how many
    // we already have.
    std::size_t offset = vertices_position.size();
    
    // Add vertices on the end of the list.
    vertices_position.insert(vertices_position.end(),
                             source.vertices_position.begin(),
                             source.vertices_position.end());
    
    // expand bounds to include these new vertices.
    bounds |= source.bounds;
    
    // copy the faces in, but change their vertex indices using the offset.
    for (std::vector<Face>::const_iterator it = source.faces.begin();
         it != source.faces.end();
         it++)
    {
        Face f = *it;
        f.fv1.vertex_index += offset;
        f.fv2.vertex_index += offset;
        f.fv3.vertex_index += offset;
        // because we use add_face, edges and graph_edges are updated.
        add_face(f);
    }
}

void MeshFaces::set_source(bool is_edge, unsigned long int object_name)
{
    for (std::vector<Face>::iterator it = faces.begin();
         it != faces.end();
         it++)
    {
        it->is_edge = is_edge;
        it->object_name = object_name;
    }
}

}

---

Generated at Mon Sep 6 00:41:11 2010 by Doxygen version 1.4.7 for Racer version svn335.