mesh_reducer.cpp

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

    } Endeach;
}


float Mesh_Reducer::find_hunt_radius_for_vertex(int vertex_index, Auto_Array <int> *targets) {
    float length_sum = 0;
    int length_count = 0;

    int other_index;
    Array_Foreach(targets, other_index) {
        length_count++;
        Vector3 delta1 = mesh->vertices[other_index] - mesh->vertices[vertex_index];
        length_sum += delta1.length();
    } Endeach;

    if (length_sum == 0) return 0; // @Think: something nonzero instead?

    float length_average = length_sum / (float)length_count;

    return length_average * hunt_radius_expansion_factor;
}


void Mesh_Reducer::update_best_candidates(int vertex_index,
                                          float *best_error_result,
                                          int *best_v1_result) {
    Vector3 *pos = &mesh->vertices[vertex_index];

    mark_vertex(vertex_index);

    Auto_Array <int> potential_targets;
    collect_and_mark_vertex_star(vertex_index, &potential_targets);

    float hunt_radius = find_hunt_radius_for_vertex(vertex_index, &potential_targets);

    int i0, i1, j0, j1, k0, k1;
    i0 = proximity_grid->get_index_x(pos->x - hunt_radius);
    i1 = proximity_grid->get_index_x(pos->x + hunt_radius);
    j0 = proximity_grid->get_index_y(pos->y - hunt_radius);
    j1 = proximity_grid->get_index_y(pos->y + hunt_radius);
    k0 = proximity_grid->get_index_z(pos->z - hunt_radius);
    k1 = proximity_grid->get_index_z(pos->z + hunt_radius);

    float r2 = hunt_radius * hunt_radius;

    int i, j, k;
    for (k = k0; k <= k1; k++) {
        for (j = j0; j <= j1; j++) {
            for (i = i0; i <= i1; i++) {
                int grid_index = proximity_grid->get_index(i, j, k);
                Lightweight_Proximity_Grid_Square *grid_square = &proximity_grid->grid_squares[grid_index];

                Auto_Array <Vector3 *> *vertices = &grid_square->vertices;

                int n;
                for (n = 0; n < vertices->live_items; n++) {
                    int other_index = get_vertex_index(mesh, vertices->data[n]);
                    if (!vertex_is_marked(other_index)) {
                        float d2 = distance_squared(*vertices->data[n], *pos);
                        if (d2 > r2) continue;

                        mark_vertex(other_index);
                        potential_targets.add(other_index);
                    }
                }
            }
        }
    }


    unmark_vertex(vertex_index);

    int other_index;
    Array_Foreach(&potential_targets, other_index) {
        unmark_vertex(other_index);
        update_best_candidates(vertex_index, other_index,
                               best_error_result, 
                               best_v1_result);
    } Endeach;

    if (*best_v1_result == -1) {
        int other_index;
        Array_Foreach(&potential_targets, other_index) {
            update_best_candidates(vertex_index, other_index,
                                   best_error_result, 
                                   best_v1_result);
        } Endeach;

    }

}

inline void Mesh_Reducer::update_single_vertex_without_queueing(int index,
                                                                float *error_result,
                                                                Reducer_Priority_Queue_Data *data_result) {
    data_result->vertex0 = index;
    data_result->vertex1 = -1;

    float best_error = FLT_MAX;
    update_best_candidates(index, &best_error, 
                           &data_result->vertex1);

    *error_result = best_error;
}

inline void Mesh_Reducer::queue_single_vertex(int index) {
    assert(mesh->canonical_vertex_map[index] == index);

    float best_error;
    Reducer_Priority_Queue_Data _data;
    update_single_vertex_without_queueing(index, &best_error, &_data);
    if ((_data.vertex1 != -1) && (best_error < FLT_MAX)) {
        Reducer_Priority_Queue_Data *data = new Reducer_Priority_Queue_Data;
        
        *data = _data;

        priority_queue->add(best_error, data);
    }
}


void Mesh_Reducer::init_priority_queue() {
    last_v0_examined = -1;
    last_v1_examined = -1;

    int i;
    for (i = 0; i < topology_handler->max_vertices; i++) {
        if (!(topology_handler->vertex_flags[i] & VERTEX_IS_LIVE)) continue;
        if (mesh->canonical_vertex_map[i] != i) continue;

        queue_single_vertex(i);
    }
}


int Mesh_Reducer::find_alias_to_map_to(int from_index, 
                                       int to_index) {
    int first_alias = to_index;
    int cursor = first_alias;

    int best_result = -1;
    float best_distance2 = FLT_MAX;

    float u0, v0;
    get_vertex_uv(mesh, from_index, &u0, &v0);
    
    // If we can find a vertex that represents uv coordinates within
    // the same material, map to that guy.
    while (1) {
        if (topology_handler->material_touched_by_vertex[from_index] ==
            topology_handler->material_touched_by_vertex[cursor]) {

            Vector3 tex0, tex1;
            get_vertex_uv(mesh, from_index, &tex0);
            get_vertex_uv(mesh, cursor, &tex1);

            float distance2 = (tex1 - tex0).length_squared();
            if (distance2 < best_distance2) {
                best_result = cursor;
                best_distance2 = distance2;
            }
        }

        // Go on to the next alias.

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

    if (best_result != -1) return best_result;

    // Give up, just give them an arbitrary one.  We could look into
    // creating a new vertex as a future extension, or moving this
    // one to the new position but... well... I just don't know.

    return to_index;
}


void Mesh_Reducer::perform_one_reduction() {
    int kill_v0 = -1;
    int kill_v1 = -1;

    float priority;
    Reducer_Priority_Queue_Data *data;
    while (1) {

        bool success = false;
        data = (Reducer_Priority_Queue_Data *)priority_queue->remove_head(&priority, &success);

        if (!success) {
            // @Improvement: Ugggh, this sucks, we need something better
            while (priority_queue->num_items == 0) {
                if (hunt_radius_expansion_factor > 10000) return;  // XXXX Give up!
                hunt_radius_expansion_factor *= 2;
                init_priority_queue();
            }

            continue;
        }

        assert(success);  // We must have one entry in queue per vertex
                          // on a face...

        int v0 = data->vertex0;
        int v1 = data->vertex1;

        if ((topology_handler->vertex_flags[v0] & VERTEX_IS_LIVE) && 
            (topology_handler->vertex_flags[v1] & VERTEX_IS_LIVE)) {
            // This is still potentially a valid collapse (both vertices still
            // exist) but we don't know whether other stuff has been collapsed
            // into V0, invalidating the priority computation that caused us
            // to just pull this guy off.  So.  We have this policy where we
            // always re-evaluate guys and throw them back on the queue.  If
            // we get the same guy twice in a row, we really want to process
            // him now, so away he goes.  Otherwise, he can wait.

            // Re-evaluate this guy and throw him back into the pond.

            float new_priority;
            update_single_vertex_without_queueing(v0, &new_priority, data);
            if (data->vertex1 == -1) {
                delete data;
                continue;
            }

            if (new_priority <= priority) { 
                kill_v0 = data->vertex0;
                kill_v1 = data->vertex1;

                delete data;
                break;
            } else {
                priority_queue->add(new_priority, data);
            }

            continue;
        }

        delete data;

        // Hmm, we nuked either the source or destination vertex since
        // that was completed...

        // If it was the source vertex, just continue.

        if (!(topology_handler->vertex_flags[v0] & VERTEX_IS_LIVE)) continue;

        // If on the other hand that guy is still alive, we need to
        // find a new place to tell him to go.  So find one, and
        // put it in the queue, and then keep on keepin' on.

        queue_single_vertex(v0);
    }

    perform_one_reduction(kill_v0, kill_v1);
}

void Mesh_Reducer::perform_one_reduction(int kill_v0, int kill_v1) {
    assert(kill_v1 >= 0);
    int first_alias = kill_v0;


    topology_handler->clear_faces_to_check();

    while (1) {
        int next = go_to_next_coincident_vertex(topology_handler, first_alias);
        assert(next != kill_v1);
        if (next == first_alias) break;

        int map_to = find_alias_to_map_to(next, kill_v1);

        // Accumulate quadrics.
        if (error_quadrics) {
            Error_Quadric *quadric0 = get_quadric(next);
            Error_Quadric *quadric1 = get_quadric(map_to);
            quadric1->accumulate_quadric(quadric0);
        }

        // Switch over the indices on all the faces.
        topology_handler->remap_vertex_face_indices(next, map_to);

        int next_next = go_to_next_coincident_vertex(topology_handler, next);
        topology_handler->vertex_coincidence_chain[first_alias] = next_next;
        topology_handler->vertex_coincidence_chain[next] = -1;

        topology_handler->eliminate_vertex_from_mesh(next);
    }

    topology_handler->vertex_coincidence_chain[first_alias] = -1;
    remove_vertex_from_grid(first_alias);
    int map_to = find_alias_to_map_to(first_alias, kill_v1);

    if (error_quadrics) { // If we are actually doing detail reduction...
        Error_Quadric *quadric0 = get_quadric(first_alias);
        Error_Quadric *quadric1 = get_quadric(map_to);

        quadric1->accumulate_quadric(quadric0);
    }

    topology_handler->remap_vertex_face_indices(first_alias, map_to);
    topology_handler->eliminate_vertex_from_mesh(first_alias);
    topology_handler->check_degenerate_faces();
}

void Mesh_Reducer::compensate_for_lonely_edge(Reducer_Face *face,
                                              int vertex_index0,
                                              int vertex_index1) {
    // Make some fake vertices that stick out from this face,
    // so's we like can pass them to the quadric thingy to
    // impose the constraint.

    // We start by getting the XYZ normal of the face.
    Vector3 position0;
    Vector3 position1;
    Vector3 position2;
    get_vertex_position(mesh, face->indices[0], &position0);
    get_vertex_position(mesh, face->indices[1], &position1);
    get_vertex_position(mesh, face->indices[2], &position2);

    Vector3 side1 = position1 - position0;
    Vector3 side2 = position2 - position0;
    Vector3 normal = cross_product(side1, side2);

    int can0 = mesh->canonical_vertex_map[vertex_index0];
    int can1 = mesh->canonical_vertex_map[vertex_index1];
    assert(topology_handler->vertex_flags[can0] & VERTEX_IS_ON_LONELY_EDGE);