mesh_reducer.cpp

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

// @Cleanliness: Lightweight_Proximity_Grid should have an
// abstracted find() function.  That would be nice.

#include "../framework.h"
#include "mesh_reducer.h"
#include "lightweight_proximity_grid.h"
#include "priority_queue.h"
#include "../mesh.h"
#include "error_quadric.h"
#include "mesh_topology_handler.h"
#include "mesh_builder.h"

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

extern float GetArea(Vector3 v0, Vector3 v1, Vector3 v2);

struct Reducer_Priority_Queue_Data {
    int vertex0;
    int vertex1;
};

inline int go_to_next_coincident_vertex(Mesh_Topology_Handler *handler, int cursor) {
    assert(cursor < handler->mesh->num_vertices);
    int next = handler->vertex_coincidence_chain[cursor];
    return next;
}

void get_vertex_uv(Triangle_List_Mesh *mesh, int index, Vector3 *result) {
    result->x = mesh->uvs[index].x;
    result->y = mesh->uvs[index].y;
    result->z = 0;
}

void get_vertex_uv(Triangle_List_Mesh *mesh, int index, float *u_ret, float *v_ret) {
    *u_ret = mesh->uvs[index].x;
    *v_ret = mesh->uvs[index].y;
}

void get_vertex_position(Triangle_List_Mesh *mesh, int index, Vector3 *result) {
    *result = mesh->vertices[index];
}

void Mesh_Reducer::fill_point(float *point, int vertex_index, int material_index) {
    float uv_weight = tuning.texture_space_importance_factor;

    if (material_index != -1) {
        float specific_material_factor = material_factor_uv_over_xyz[material_index];
        uv_weight *= specific_material_factor;
    }

    point[0] = mesh->vertices[vertex_index].x;
    point[1] = mesh->vertices[vertex_index].y;
    point[2] = mesh->vertices[vertex_index].z;
    point[3] = mesh->uvs[vertex_index].x * uv_weight;
    point[4] = mesh->uvs[vertex_index].y * uv_weight;
}



void Mesh_Reducer::count_material_areas() {
    // Initialize the ratio of UV space to XYZ space for
    // each material.

    // First build the material arrays and initialize them to 0.

    material_area_uv = new float[mesh->num_materials];
    material_area_xyz = new float[mesh->num_materials];
    material_factor_uv_over_xyz = new float[mesh->num_materials];

    int i;
    for (i = 0; i < mesh->num_materials; i++) {
        material_area_uv[i] = 0;
        material_area_xyz[i] = 0;
        material_factor_uv_over_xyz[i] = 0;
    }

    // Now we iterate over all the faces and add up corresponding
    // areas.  Etc.

    for (i = 0; i < mesh->num_faces; i++) {
        Reducer_Face *face = &topology_handler->faces[i];
        int material_index = face->material;

        int N0 = face->indices[0];
        int N1 = face->indices[1];
        int N2 = face->indices[2];

        Vector3 pos0, pos1, pos2;
        Vector3 tex0, tex1, tex2;

        get_vertex_position(mesh, N0, &pos0);
        get_vertex_position(mesh, N1, &pos1);
        get_vertex_position(mesh, N2, &pos2);

        get_vertex_uv(mesh, N0, &tex0);
        get_vertex_uv(mesh, N1, &tex1);
        get_vertex_uv(mesh, N2, &tex2);

        float XYZArea = GetArea(pos0, pos1, pos2);
        float UVArea = GetArea(tex0, tex1, tex2);

        material_area_xyz[material_index] += XYZArea;
        material_area_uv[material_index] += UVArea;
    }

    for (i = 0; i < mesh->num_materials; i++) {
        if (material_area_uv[i]) {
            material_factor_uv_over_xyz[i] = sqrt(material_area_xyz[i] / material_area_uv[i]);
        } else {
            material_factor_uv_over_xyz[i] = 0;
        }
    }
}


void Mesh_Reducer::add_face_constraint_to_quadrics(Reducer_Face *face) {
    float point0[ERROR_QUADRIC_DIMENSIONS];
    float point1[ERROR_QUADRIC_DIMENSIONS];
    float point2[ERROR_QUADRIC_DIMENSIONS];

    fill_point(point0, face->indices[0], face->material);
    fill_point(point1, face->indices[1], face->material);
    fill_point(point2, face->indices[2], face->material);

    Error_Quadric *quadric0 = get_quadric(face->indices[0]);
    Error_Quadric *quadric1 = get_quadric(face->indices[1]);
    Error_Quadric *quadric2 = get_quadric(face->indices[2]);

    quadric0->accumulate_plane(point0, point1, point2);
    quadric1->accumulate_plane(point0, point1, point2);
    quadric2->accumulate_plane(point0, point1, point2);
}

void Mesh_Reducer::init_quadrics() {
    count_material_areas();
    error_quadrics = new Error_Quadric[mesh->num_vertices];

    int i;
    for (i = 0; i < mesh->num_vertices; i++) {
        error_quadrics[i].clear();
    }

    error_quadrics[0].init_index_table();  // Set up the static data.

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

        if (!(face->flags & FACE_IS_A_SEAM_FILL)) {
            add_face_constraint_to_quadrics(&topology_handler->faces[i]);
        }
    }
}

Error_Quadric *Mesh_Reducer::get_quadric(int index) {
    return &error_quadrics[index];
}

Mesh_Reducer::Mesh_Reducer() {
    tuning.material_boundary_penalty = 1000.0f;
    tuning.topology_change_penalty = 2.0f;
    tuning.icky_face_penalty = 1000.0f;
    tuning.texture_space_importance_factor = 2.0f;
    tuning.lonely_edge_constraint_factor = 3.0f;

    mesh = NULL;
    priority_queue = NULL;
    proximity_grid = NULL;
    error_quadrics = NULL;

    num_target_faces = 1000;
    num_lonely_edges_detected = 0;
    hunt_radius_expansion_factor = 1;

    topology_handler = NULL;
}

Mesh_Reducer::~Mesh_Reducer() {
    delete proximity_grid;
    delete priority_queue;
    delete topology_handler;
    delete [] error_quadrics;
    delete [] material_area_uv;
    delete [] material_area_xyz;
    delete [] material_factor_uv_over_xyz;
}

float Mesh_Reducer::compute_collapse_error(int index0, int index1) {
    // Step through every alias of index0.  Find best match
    // among aliases of index1.  Compute error due to the move,
    // accumulate to sum.

    // When done, divide sum by number of index0 aliases to
    // compute an average.

    float error_sum = 0;
    float penalty = 1;

    int first_alias = index0;
    int cursor = index0;
    int vertices_considered = 0;

    while (1) {
        int dest = topology_handler->simple_find_alias_to_map_to(cursor, index1);
        if (dest == -1) {
            // Material boundary detected.  There's no right answer
            // here, so let's just collapse to the canonical vertex,
            // and jack this reduction by a big penalty.  
            // (@Improvement: We might
            // in future want to try to find the vertex with the 
            // least amount of error, or something.)
            
            dest = index1;
            penalty = tuning.material_boundary_penalty;
        }

        Error_Quadric *quadric0 = get_quadric(cursor);
        Error_Quadric *quadric1 = get_quadric(dest);
        assert(quadric0 != quadric1);

        float pos_1_array[ERROR_QUADRIC_DIMENSIONS];
        fill_point(pos_1_array, dest, topology_handler->material_touched_by_vertex[dest]);

        float error = quadric0->evaluate_error(pos_1_array);
        error_sum += error;

        vertices_considered++;

        cursor = topology_handler->vertex_coincidence_chain[cursor];
        if (cursor == first_alias) break;
    }

    if (vertices_considered == 0) return 0;

    if (tuning.topology_change_penalty) {
        const float TOPOLOGY_CHANGE_EPSILON = 0.5f; // Arbitrary
        if (topology_handler->collapse_changes_topology(index0, index1)) {
            error_sum += TOPOLOGY_CHANGE_EPSILON;
            error_sum *= tuning.topology_change_penalty;
        }
    }

    if (topology_handler->collapse_creates_icky_face(index0, index1)) {
        return FLT_MAX;
    }

    return (error_sum * penalty) / (float)vertices_considered;
//    return (error_sum * penalty);
}

void Mesh_Reducer::update_best_candidates(int index0,
                                          int index1,
                                          float *best_error_result,
                                          int *best_v1_result) {
    if (index0 == index1) return;

    assert(topology_handler->vertex_flags[index0] & VERTEX_IS_LIVE);
    assert(topology_handler->vertex_flags[index1] & VERTEX_IS_LIVE);

    float Error = compute_collapse_error(index0, index1);

    if (Error < *best_error_result) {
        *best_error_result = Error;
        *best_v1_result = index1;
    }
}

int get_vertex_index(Triangle_List_Mesh *mesh, Vector3 *pos) {
    int index = pos - mesh->vertices;
    assert(index >= 0);
    assert(index < mesh->num_vertices);

    return index;
}

inline int get_index_within_face(Triangle_List_Mesh *mesh, Reducer_Face *face, int vertex_index) {
    int *canonical = mesh->canonical_vertex_map;
    assert(canonical[vertex_index] == vertex_index);

    int where_within_face;

    if (canonical[face->indices[0]] == vertex_index) where_within_face = 0;
    else if (canonical[face->indices[1]] == vertex_index) where_within_face = 1;
    else if (canonical[face->indices[2]] == vertex_index) where_within_face = 2;
    else where_within_face = -1;

    return where_within_face;
}

inline bool Mesh_Reducer::vertex_is_marked(int index) {
    return topology_handler->vertex_flags[index] & VERTEX_IS_MARKED;
}

inline void Mesh_Reducer::mark_vertex(int index) {
    topology_handler->vertex_flags[index] |= VERTEX_IS_MARKED;
}

inline void Mesh_Reducer::unmark_vertex(int index) {
    topology_handler->vertex_flags[index] &= ~VERTEX_IS_MARKED;
}


void Mesh_Reducer::collect_and_mark_vertex_star(int vertex_index, Auto_Array <int> *targets) {
    Reducer_Face_Membership *membership = &topology_handler->face_membership[vertex_index];

    int face_index;
    Array_Foreach(&membership->faces, face_index) {
        Reducer_Face *face = &topology_handler->faces[face_index];
        int within = get_index_within_face(mesh, face, vertex_index);
        assert(within != -1);

        int n1 = face->indices[(within + 1) % 3];
        int n2 = face->indices[(within + 2) % 3];

        n1 = mesh->canonical_vertex_map[n1];
        n2 = mesh->canonical_vertex_map[n2];

        if (!vertex_is_marked(n1)) {
            targets->add(n1);
            mark_vertex(n1);
        }


        if (!vertex_is_marked(n2)) {
            targets->add(n2);
            mark_vertex(n2);
        }