mesh_reducer.cpp

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

    assert(topology_handler->vertex_flags[can1] & VERTEX_IS_ON_LONELY_EDGE);

    // So that we don't do anything numerically bizarre, we will scale
    // this normal vector so that it's the same length as the distance
    // between vertex_index0 and vertex_index1.

    Vector3 vertex_position_0, vertex_position_1;
    get_vertex_position(mesh, vertex_index0, &vertex_position_0);
    get_vertex_position(mesh, vertex_index1, &vertex_position_1);
    float length = distance(vertex_position_0, vertex_position_1);

    normal.safe_normalize();
    normal.scale(length);


    // Now let's gather the 2 points representing the edge.  Then
    // we'll manufacture a 3rd point, then tell the quadric guys
    // to go deal.  Right now we don't do anything with UV (unclear
    // whether we should).
    float point0[ERROR_QUADRIC_DIMENSIONS];
    float point1[ERROR_QUADRIC_DIMENSIONS];

    fill_point(point0, vertex_index0, face->material);
    fill_point(point1, vertex_index1, face->material);

    float point2[ERROR_QUADRIC_DIMENSIONS];

    assert(ERROR_QUADRIC_DIMENSIONS == 5);
    point2[0] = point1[0] + normal.x;
    point2[1] = point1[1] + normal.y;
    point2[2] = point1[2] + normal.z;
    point2[3] = point1[3];
    point2[4] = point1[4];

    Error_Quadric *quadric0 = get_quadric(vertex_index0);
    Error_Quadric *quadric1 = get_quadric(vertex_index1);
    
    quadric0->accumulate_plane(point0, point1, point2, tuning.lonely_edge_constraint_factor);
    quadric1->accumulate_plane(point0, point1, point2, tuning.lonely_edge_constraint_factor); 

    num_lonely_edges_detected++;
}

void Mesh_Reducer::handle_lonely_edges() {
    // Look for all lonely edges on this mesh.  For any that
    // we find, add a constraint to keep that edge from moving
    // much.

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

        int vertex_0_index = i;
        int canonical0 = mesh->canonical_vertex_map[vertex_0_index];

        Reducer_Face_Membership *membership = &topology_handler->face_membership[i];

        // For each face this vertex is on, take this vertex
        // and the 'forward' vertex along the face's winding
        // order to constitute the edge we are looking at now.
        // (We don't have to consider the guy behind us in the
        // winding order, because we will process that edge when
        // we are looking at that vertex, and he sees us in front
        // of him.)

        int j;
        for (j = 0; j < membership->faces.live_items; j++) {
            int face_index = membership->faces.data[j];
            Reducer_Face *face = &topology_handler->faces[face_index];

            int where_within_face = get_index_within_face(mesh, face, canonical0);
            assert(where_within_face != -1);


            int vertex_1_index = face->indices[(where_within_face + 1) % 3];
            int canonical1 = mesh->canonical_vertex_map[vertex_1_index];
            
            // Now... we search again through this vertex's membership
            // list, to find ANOTHER face containing this vertex,
            // which contains the edge appearing in the opposite winding
            // order (canonical1 followed by canonical0).  If we can find
            // no such face, then this edge is lonely.
            
            bool edge_is_lonely = true;

            Reducer_Face_Membership *mem1 = &topology_handler->face_membership[canonical1];

            int k;
            for (k = 0; k < mem1->faces.live_items; k++) {
                int face_index1 = mem1->faces.data[k];
                if (face_index1 == face_index) continue;

                Reducer_Face *face1 = &topology_handler->faces[face_index1];
                int where_within_face = get_index_within_face(mesh, face1, canonical0);
                if (where_within_face == -1) continue;

                int vertex_2_index = face1->indices[(where_within_face + 2) % 3];
                int canonical2 = mesh->canonical_vertex_map[vertex_2_index];
                if (canonical2 == canonical1) {
                    edge_is_lonely = false;
                    break;
                }
            }

            if (edge_is_lonely) {
                topology_handler->vertex_flags[canonical0] |= VERTEX_IS_ON_LONELY_EDGE;
                topology_handler->vertex_flags[canonical1] |= VERTEX_IS_ON_LONELY_EDGE;
                compensate_for_lonely_edge(face, canonical0, canonical1);
            }
        }
    }
}

void Mesh_Reducer::mark_face_as_seam(int index) {
    assert(index >= 0);
    assert(index < topology_handler->num_faces_remaining);
    topology_handler->faces[index].flags |= FACE_IS_A_SEAM_FILL;
}

void Mesh_Reducer::collapse_similar_vertices(float threshold) {
    double t2 = threshold * threshold;
    float hunt_radius = threshold;

    Auto_Array <int> to_collapse;
    
    int n;
    for (n = 0; n < mesh->num_vertices; n++) {
        if (n != mesh->canonical_vertex_map[n]) continue;
        if (!(topology_handler->vertex_flags[n] & VERTEX_IS_LIVE)) continue;

        Vector3 *pos = &mesh->vertices[n];

        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);

        to_collapse.reset();

        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 k;
                    for (k = 0; k < vertices->live_items; k++) {
                        int other_index = get_vertex_index(mesh, vertices->data[k]);
                        if (other_index == n) continue;
                        assert(topology_handler->vertex_flags[other_index] & VERTEX_IS_LIVE);

                        double d2 = distance_squared(mesh->vertices[other_index], *pos);
                        if (d2 <= t2) to_collapse.add(other_index);
                    }
                }
            }
        }

        int target;
        Array_Foreach(&to_collapse, target) {
            perform_one_reduction(target, n);
            topology_handler->check_degenerate_faces();
        } Endeach;
    }

}

void Mesh_Reducer::reduce(int _num_target_faces) {
    // Do setup regarding quadrics, etc.

    init_quadrics();
    handle_lonely_edges();

    priority_queue = new Priority_Queue(mesh->num_vertices * 10);
    init_priority_queue();


    // Actually do the reduction part now.


    //    AssertFacesAreSane(mesh);
    initial_num_vertices = mesh->num_vertices;
    num_target_faces = _num_target_faces;

    while (topology_handler->num_faces_remaining > num_target_faces) {
        perform_one_reduction();
        if (hunt_radius_expansion_factor > 10000) break;  // XXXX Give up!
    }
}

Mesh_Builder *Mesh_Reducer::prepare_result(int **remap) {
    assert(mesh);
    assert(topology_handler);

    topology_handler->compact_vertices();
    int num_vertices = topology_handler->num_vertices_remaining;
    int num_faces = topology_handler->num_faces_remaining;

    Mesh_Builder *result = new Mesh_Builder(num_vertices, num_faces);

    Vector2 *output_uvs = (Vector2 *)topology_handler->output_uvs;
    Quaternion *output_tangent_frames = topology_handler->output_tangent_frames;
    int *xref = new int[num_vertices];
    int i;
    for (i = 0; i < num_vertices; i++) {
        int index = result->add_vertex(topology_handler->output_vertices[i],
                                       output_uvs[i], 
                                       output_tangent_frames[i]);
        assert(index == i);
        xref[i] = index;
    }


    for (i = 0; i < num_faces; i++) {
        Reducer_Face *face = &topology_handler->faces[i];
        result->add_triangle(xref[face->indices[0]], xref[face->indices[1]],
                             xref[face->indices[2]], face->material);
    }

    if (remap) {
        *remap = xref;
    } else {
        delete [] xref;
    }
        
    for (i = 0; i < mesh->num_materials; i++) {
        // @Feature We don't check for no-longer-used materials and compact them.
        // This probably doesn't happen very often anyway, BUT we probably
        // we probably want to intentionally compact things into lower-res
        // textures at some point, for which we allocate one material for
        // the whole dude maybe?  Oh that would change the material shaders
        // and cause popping so it might actually suck.
        // Hmm, who the hell knows.
        result->add_material(&mesh->material_info[i]);
    }

    return result;
}

void Mesh_Reducer::get_result(Triangle_List_Mesh **result_return) {
    int *remap;
    Mesh_Builder *builder = prepare_result(&remap);

    // @Robustness: 0.01f threshold, or adjustable distance
    // @Robustness: integer remapper
    Triangle_List_Mesh *result = builder->build_mesh();

    int i;
    for (i = 0; i < topology_handler->num_vertices_originally; i++) {
        int xref = topology_handler->old_index_to_new_index[i];
        topology_handler->old_index_to_new_index[i] = remap[xref];
    }

    delete [] remap;

    *result_return = result;
}

// Mesh_Reducer looks at the dimensions of the model, then cooks up a
// roughly uniform 3D grid.  Allocates that grid, iterates over
// the model and plunks every vertex into the grid square where
// it goes.  At runtime we do a hunt_radius search through this grid,
// find everyone within a certain distance, and check them to see
// if they are a good collapse candidate.  (This way we are
// checking non-edges as vertex collapse candidates, which seems
// like a really good idea given the input data I've seen.)

void Mesh_Reducer::init(Triangle_List_Mesh *_mesh) {
    assert(mesh == NULL);
    mesh = _mesh;

    // Collect the dimensions of the mesh.

    Vector3 v0, v1;
    v0.x = v0.y = v0.z = FLT_MAX;
    v1.x = v1.y = v1.z = -FLT_MAX;

    int i;
    for (i = 0; i < mesh->num_vertices; i++) {
        Vector3 *v = &mesh->vertices[i];
        if (v->x < v0.x) v0.x = v->x;
        if (v->y < v0.y) v0.y = v->y;
        if (v->z < v0.z) v0.z = v->z;
        if (v->x > v1.x) v1.x = v->x;
        if (v->y > v1.y) v1.y = v->y;
        if (v->z > v1.z) v1.z = v->z;
    }

    if (mesh->num_vertices == 0) v1 = v0 = Vector3(0, 0, 0);

    Vector3 dv = v1 - v0;
    float widest = Max(dv.x, Max(dv.y, dv.z));
    const int RESOLUTION = 12;
    float ds = widest / (float)RESOLUTION;

    proximity_grid = new Lightweight_Proximity_Grid;
    proximity_grid->init(v0, dv, ds);

    for (i = 0; i < mesh->num_vertices; i++) {
        if (mesh->canonical_vertex_map[i] == i) {
            Vector3 *pos = &mesh->vertices[i];
            proximity_grid->add(pos);
        }
    }

    topology_handler = new Mesh_Topology_Handler();
    topology_handler->init(mesh);

}

void Mesh_Reducer::remove_vertex_from_grid(int vertex_index) {
    if (vertex_index != mesh->canonical_vertex_map[vertex_index]) return;
    Vector3 *pos = &mesh->vertices[vertex_index];
    bool success = proximity_grid->remove(pos);
    assert(success);
}