mesh_topology_handler.cpp

国外游戏开发者杂志2003年第七期配套代码

#include "../framework.h"
#include "../mesh.h"
#include "mesh_reducer.h"
#include "mesh_topology_handler.h"

#include <float.h>
#include <math.h>

void get_vertex_uv(Triangle_List_Mesh *mesh, int index, Vector3 *result);
extern float GetArea(Vector3 v0, Vector3 v1, Vector3 v2);

Mesh_Topology_Handler::~Mesh_Topology_Handler() {
    delete [] faces;
    delete faces_to_check;
    delete [] material_touched_by_vertex;
    delete [] face_membership;
    delete [] vertex_flags;
    delete [] vertex_coincidence_chain;

    delete [] new_index_to_old_index;
    delete [] old_index_to_new_index;
    delete [] vertex_collapse_destination;
    delete [] output_vertices;
    delete [] output_uvs;
}

float GetArea(Vector3 v0, Vector3 v1, Vector3 v2) {
    Vector3 w1 = v1 - v0;
    Vector3 w2 = v2 - v0;
    Vector3 cross = cross_product(w1, w2);
    return cross.length();
}

void Mesh_Topology_Handler::get_listed_faces(Triangle_List_Mesh *lmesh) {
    int i;
    // Count up all the faces.
    for (i = 0; i < lmesh->num_triangle_lists; i++) {
        Triangle_List_Info *info = &lmesh->triangle_list_info[i];

        assert(info->num_vertices > 2);
        assert(info->num_vertices % 3 == 0);

        num_faces_remaining += (info->num_vertices / 3);
    }

    // Allocate face data; walk over all the strips again, and fill out
    // the face data.

    faces = new Reducer_Face[num_faces_remaining];
    int face_cursor = 0;
    for (i = 0; i < lmesh->num_triangle_lists; i++) {
        Triangle_List_Info *info = &lmesh->triangle_list_info[i];

        int k;
        for (k = 0; k < info->num_vertices; k += 3) {
            assert(face_cursor < num_faces_remaining);
            Reducer_Face *face = &faces[face_cursor];
            face->material = info->material_index;
            face->flags = 0;

            face->indices[0] = lmesh->indices[info->start_of_list + k + 0];
            face->indices[1] = lmesh->indices[info->start_of_list + k + 1];
            face->indices[2] = lmesh->indices[info->start_of_list + k + 2];
            assert(face->indices[0] >= 0);
            assert(face->indices[1] >= 0);
            assert(face->indices[2] >= 0);

            material_touched_by_vertex[face->indices[0]] = face->material;
            material_touched_by_vertex[face->indices[1]] = face->material;
            material_touched_by_vertex[face->indices[2]] = face->material;

            face_cursor++;
        }
    }

    assert(face_cursor == num_faces_remaining);
}

void Mesh_Topology_Handler::init(Triangle_List_Mesh *_mesh) {
    mesh = _mesh;
    faces_to_check = new Auto_Array <int>;
    faces = NULL;
    face_membership = NULL;
    vertex_coincidence_chain = NULL;


    num_vertices_remaining = mesh->num_vertices;
    num_vertices_originally = mesh->num_vertices;
    max_vertices = num_vertices_remaining;

    output_vertices = NULL;
    output_uvs = NULL;
    new_index_to_old_index = NULL;
    vertex_flags = NULL;


    material_touched_by_vertex = new int[num_vertices_remaining];
    old_index_to_new_index = new int[num_vertices_remaining];
    vertex_collapse_destination = new int[num_vertices_remaining];

    int i;
    for (i = 0; i < max_vertices; i++) {
        material_touched_by_vertex[i] = -1;
        old_index_to_new_index[i] = -1;
        vertex_collapse_destination[i] = -1;
    }

    build_vertex_coincidence_chain();

    num_faces_remaining = 0;

    get_listed_faces((Triangle_List_Mesh *)mesh);

    face_membership = new Reducer_Face_Membership[num_vertices_remaining];
    vertex_flags = new unsigned char[num_vertices_remaining];
    for (i = 0; i < num_vertices_remaining; i++) vertex_flags[i] = VERTEX_IS_LIVE;

    init_face_membership_info();
}

void Mesh_Topology_Handler::build_vertex_coincidence_chain() {
    vertex_coincidence_chain = new int[num_vertices_remaining];

    int *last_vertex_in_chain_from_canonical = new int[num_vertices_remaining];

    int i;
    for (i = 0; i < num_vertices_remaining; i++) {
        last_vertex_in_chain_from_canonical[i] = i;
    }

    for (i = 0; i < num_vertices_remaining; i++) {
        int canonical = mesh->canonical_vertex_map[i];
        assert(canonical == mesh->canonical_vertex_map[canonical]);

        if (canonical != i) {
            assert(canonical < i);
            assert(canonical >= 0);
            int last = last_vertex_in_chain_from_canonical[canonical];
            vertex_coincidence_chain[last] = i;

            last_vertex_in_chain_from_canonical[canonical] = i;
        }

        vertex_coincidence_chain[i] = canonical;
    }

    // Done; clean up.
    delete [] last_vertex_in_chain_from_canonical;
}

void Mesh_Topology_Handler::assert_face_in_membership(Reducer_Face_Membership *membership, Reducer_Face *face) {
    int i;
    for (i = 0; i < membership->faces.live_items; i++) {
        if (&faces[membership->faces.data[i]] == face) return;
    }

    assert(0);
}

void Mesh_Topology_Handler::sanity_membership() {
    int i;
    for (i = 0; i < mesh->num_vertices; i++) {
        if (vertex_flags[i] & VERTEX_IS_LIVE) sanity_membership(i);
    }
}

void Mesh_Topology_Handler::sanity_membership(int orig_vertex_index) {
    int vertex_index = mesh->canonical_vertex_map[orig_vertex_index];
    Reducer_Face_Membership *membership = &face_membership[vertex_index];

    int i;
    for (i = 0; i < membership->faces.live_items; i++) {
        Reducer_Face *face;
        face = &faces[membership->faces.data[i]];
        if (mesh->canonical_vertex_map[face->indices[0]] == vertex_index) continue;
        if (mesh->canonical_vertex_map[face->indices[1]] == vertex_index) continue;
        if (mesh->canonical_vertex_map[face->indices[2]] == vertex_index) continue;

        assert(0);
    }

    for (i = 0; i < num_faces_remaining; i++) {
        Reducer_Face *face = &faces[i];
        if (face->indices[0] == orig_vertex_index) assert_face_in_membership(membership, face);
        if (face->indices[1] == orig_vertex_index) assert_face_in_membership(membership, face);
        if (face->indices[2] == orig_vertex_index) assert_face_in_membership(membership, face);
    }
}

void Mesh_Topology_Handler::remap_face_membership_face_indices_helper(int orig_vertex_index,
                                                                      int old_face_index,
                                                                      int new_face_index) {
    int vertex_index = mesh->canonical_vertex_map[orig_vertex_index];
    Reducer_Face_Membership *membership = &face_membership[vertex_index];

    int num_found = 0;
    int i;
    for (i = 0; i < membership->faces.live_items; i++) {
        if (membership->faces[i] == old_face_index) {
            membership->faces[i] = new_face_index;
            num_found++;
        }
    }

    // We would like to assert here, but if it is the case that two vertices
    // in the face aliased to the same thing, we will have already removed
    // the face from this membership list, so we won't find it.
    //    assert(num_found);
}

void Mesh_Topology_Handler::remap_face_membership_face_indices(int old_index,
                                                               int new_index) {
    Reducer_Face *face = &faces[new_index];
    remap_face_membership_face_indices_helper(face->indices[0], old_index, new_index);
    remap_face_membership_face_indices_helper(face->indices[1], old_index, new_index);
    remap_face_membership_face_indices_helper(face->indices[2], old_index, new_index);
}

void Mesh_Topology_Handler::remap_vertex_face_indices(int old_index, int new_index) {
    vertex_collapse_destination[old_index] = new_index;

    int i;
    for (i = 0; i < num_faces_remaining; i++) {
        Reducer_Face *face = &faces[i];

        int j;
        for (j = 0; j < 3; j++) {
            if (face->indices[j] == old_index) {
                face->indices[j] = new_index;
                add_face_membership_to_vertex(i, new_index);
                add_face_to_check(i);
            }
        }
    }
}

void Mesh_Topology_Handler::remove_face_membership_from_vertex(int orig_vertex_index, int face_index) {
    int vertex_index = mesh->canonical_vertex_map[orig_vertex_index];
    Reducer_Face_Membership *membership = &face_membership[vertex_index];
    membership->faces.remove(face_index);
}

void Mesh_Topology_Handler::eliminate_vertex_from_mesh(int dead_vertex) {
    num_vertices_remaining--;
    vertex_flags[dead_vertex] &= ~VERTEX_IS_LIVE;
}



bool is_alias_of(Mesh_Topology_Handler *handler, int target, int other) {
    Triangle_List_Mesh *mesh = handler->mesh;
    if (mesh->canonical_vertex_map[target] == mesh->canonical_vertex_map[other]) return true;
    return false;
}


bool face_is_degenerate2(Mesh_Topology_Handler *handler, Reducer_Face *face) {
    if (is_alias_of(handler, face->indices[0], face->indices[1])) return true;
    if (is_alias_of(handler, face->indices[1], face->indices[2])) return true;
    if (is_alias_of(handler, face->indices[2], face->indices[0])) return true;

    return false;
}

void Mesh_Topology_Handler::clear_faces_to_check() {
    faces_to_check->reset();
}

void Mesh_Topology_Handler::add_face_to_check(int index) {
    faces_to_check->add(index);
}

/*
void assert_faces_are_clean(Mesh_Topology_Handler *handler) {
    int i;
    for (i = 0; i < handler->num_faces_remaining; i++) {
        Reducer_Face *face = &handler->faces[i];
        assert(face->indices[0] != face->indices[1]);
        assert(face->indices[0] != face->indices[2]);
        assert(face->indices[1] != face->indices[2]);
    }
}
*/

void Mesh_Topology_Handler::check_degenerate_faces() {
    int num_changes = 0;

    int i;
    for (i = 0; i < faces_to_check->live_items; i++) {
        int index = faces_to_check->data[i];

        Reducer_Face *face = &faces[index];

        if (face_is_degenerate2(this, face)) {
            // Take this guy out of our own local array...
            num_changes++;
            faces_to_check->data[i] = faces_to_check->data[faces_to_check->live_items - 1];
            faces_to_check->live_items--;
            i--;

            // Now do the actual global manipulations...

            remove_face_membership_from_vertex(face->indices[0], index);
            remove_face_membership_from_vertex(face->indices[1], index);
            remove_face_membership_from_vertex(face->indices[2], index);

            int old_index = num_faces_remaining - 1;
            *face = faces[old_index];
            num_faces_remaining--;

            // This Remap must happen after we copy the face.
            if (old_index != index) {
                remap_face_membership_face_indices(old_index, index);

                int j;
                for (j = 0; j < faces_to_check->live_items; j++) {
                    if (faces_to_check->data[j] == old_index) faces_to_check->data[j] = index;
                }
            }
        }
    }

    if (num_changes) {
        // This collapse may have made more faces degenerate, so we need to recurse!
        // Though I am actually not sure if this is totally necessary;
        // @Simplify: investigate this question sometime?
        check_degenerate_faces();
    }