mesh_chopper.cpp

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

        intermediate_result_a.register_seam_edge(&spec_n1, &spec_n2);
        intermediate_result_b.register_seam_edge(&spec_n1, &spec_n2);
        return;
    }

    if ((c2 == 0) && (c0 == 0)) {
        intermediate_result_a.register_seam_edge(&spec_n2, &spec_n0);
        intermediate_result_b.register_seam_edge(&spec_n2, &spec_n0);
        return;
    }

    assert(c0 >= 0);
    assert(c2 == -1);

    Vertex_Specifier spec_m1, spec_m2;

    if (c1 >= 0) {
        do_an_edge_split(n1, n2, c1, c2, &spec_m1);
        do_an_edge_split(n2, n0, c2, c0, &spec_m2);

        add_triangle(&spec_n0, &spec_n1, &spec_m1, &intermediate_result_a);
        add_triangle(&spec_m1, &spec_m2, &spec_n0, &intermediate_result_a);
        add_triangle(&spec_m1, &spec_n2, &spec_m2, &intermediate_result_b);
    } else {
        do_an_edge_split(n0, n1, c0, c1, &spec_m1);
        do_an_edge_split(n2, n0, c2, c0, &spec_m2);

        add_triangle(&spec_n0, &spec_m1, &spec_m2, &intermediate_result_a);
        add_triangle(&spec_m2, &spec_m1, &spec_n1, &intermediate_result_b);
        add_triangle(&spec_n1, &spec_n2, &spec_m2, &intermediate_result_b);
    }

    intermediate_result_a.register_seam_edge(&spec_m1, &spec_m2);
    intermediate_result_b.register_seam_edge(&spec_m1, &spec_m2);
}


void add_a_seam_quad(Mesh_Seam *seam,
                     Intermediate_Result *res_a, Intermediate_Result *res_b,
                     Intermediate_Result::Seam_Edge *edge_a,
                     Intermediate_Result::Seam_Edge *edge_b) {

    int cursor = seam->num_faces * 3;
    Seam_Index *index;

    index = &seam->indices[cursor++];
    index->which_mesh = 1;
    index->vertex_index = edge_b->index_1;
    index->uv = res_b->mesh_builder->vertex_uvs[index->vertex_index];

    index = &seam->indices[cursor++];
    index->which_mesh = 0;
    index->vertex_index = edge_a->index_1;
    index->uv = res_a->mesh_builder->vertex_uvs[index->vertex_index];

    index = &seam->indices[cursor++];
    index->which_mesh = 1;
    index->vertex_index = edge_b->index_0;
    index->uv = res_b->mesh_builder->vertex_uvs[index->vertex_index];



    index = &seam->indices[cursor++];
    index->which_mesh = 0;
    index->vertex_index = edge_a->index_1;
    index->uv = res_a->mesh_builder->vertex_uvs[index->vertex_index];

    index = &seam->indices[cursor++];
    index->which_mesh = 0;
    index->vertex_index = edge_a->index_0;
    index->uv = res_a->mesh_builder->vertex_uvs[index->vertex_index];

    index = &seam->indices[cursor++];
    index->which_mesh = 1;
    index->vertex_index = edge_b->index_0;
    index->uv = res_b->mesh_builder->vertex_uvs[index->vertex_index];


    seam->num_faces += 2;
}

inline bool seam_edges_match(Intermediate_Result::Seam_Edge *edge_a,
                             Intermediate_Result::Seam_Edge *edge_b) {
    if (!specs_match(&edge_a->spec_0, &edge_b->spec_0)) return false;
    if (!specs_match(&edge_a->spec_1, &edge_b->spec_1)) return false;
    return true;
}

Mesh_Seam *Mesh_Chopper::build_seam() {
    Intermediate_Result *res_a = &intermediate_result_a;
    Intermediate_Result *res_b = &intermediate_result_b;

    Intermediate_Result::Seam_Edge *edge_a, *edge_b;

    Mesh_Seam *result = new Mesh_Seam(res_a->seam_edges.items * 2);
    result->num_faces = 0;

    Foreach(&res_a->seam_edges, edge_a) {
        // Find a potentially matching edge in b; if it's there,
        // we will make a seam quad.  This loop is O(n^2) right
        // now though it's easy to make it O(n) if it becomes
        // a drag on execution time.  

        // Actually as this demo is currently written, this whole
        // phase is unnecessary since we can do all the seam binding
        // back when we create the edges.  But so that we can deal
        // with more complex boundary cases in the future, and 
        // allow easy out-of-core LOD generation, we do this here in 
        // a separate phase.

        Foreach(&res_b->seam_edges, edge_b) {
            if (seam_edges_match(edge_a, edge_b)) {
                add_a_seam_quad(result, res_a, res_b, edge_a, edge_b);

                // @Robustness:  This break is not really correct for non-manifold geometry, 
                // since we could have other edges that match also.  If we care enough
                // we should fix this!

                break;
            }
        } Endeach;
    } Endeach;

    result->remove_degenerate_faces();
    return result;
}


void Mesh_Chopper::chop_mesh(Triangle_List_Mesh *_input_mesh,
                             Plane3 *plane, int plane_id,
                             Chopped_Result *result_a,
                             Chopped_Result *result_b,
                             Mesh_Seam **seam_a_to_b_return) {

    input_mesh = _input_mesh;

    intermediate_result_a.my_chopper = this;
    intermediate_result_b.my_chopper = this;

    // Init stuff...
    intermediate_result_a.init(input_mesh);
    intermediate_result_b.init(input_mesh);

    // Okay now actually do some work...

    current_plane_index = plane_id;




    int i;
    for (i = 0; i < input_mesh->num_materials; i++) {
        intermediate_result_a.mesh_builder->add_material(&input_mesh->material_info[i]);
        intermediate_result_b.mesh_builder->add_material(&input_mesh->material_info[i]);
    }

    plane_d = plane->d;
    plane_normal = Vector3(plane->a, plane->b, plane->c);

    int k;
    for (k = 0; k < input_mesh->num_triangle_lists; k++) {
        Triangle_List_Info *info = &input_mesh->triangle_list_info[k];
        current_material_index = info->material_index;

        int i;
        for (i = 0; i < info->num_vertices; i += 3) {
            int n0 = input_mesh->indices[info->start_of_list + i + 0];
            int n1 = input_mesh->indices[info->start_of_list + i + 1];
            int n2 = input_mesh->indices[info->start_of_list + i + 2];

            add_one_triangle(n0, n1, n2);
        }
    }

    result_a->result_mesh = intermediate_result_a.mesh_builder->build_mesh();
    result_b->result_mesh = intermediate_result_b.mesh_builder->build_mesh();
    
    result_a->vertex_hash_table = intermediate_result_a.vertex_hash_table;
    result_b->vertex_hash_table = intermediate_result_b.vertex_hash_table;

    // Prevent these guys from deleting their hash tables.
    intermediate_result_a.vertex_hash_table = NULL;
    intermediate_result_b.vertex_hash_table = NULL;

    Mesh_Seam *seam = build_seam();
    *seam_a_to_b_return = seam;

    // Cleanup stuff...
    intermediate_result_a.clean();
    intermediate_result_b.clean();
}


Intermediate_Result::Intermediate_Result() {
    mesh_builder = NULL;
}

Intermediate_Result::~Intermediate_Result() {
    clean();
}

void Intermediate_Result::init(Triangle_List_Mesh *mesh) {
    mesh_builder = new Mesh_Builder(mesh->num_vertices * 2,  // This is overconservative
                                            mesh->num_faces * 2);

    vertex_hash_table = new Hash_Table(mesh->num_vertices / 2);
}

void Intermediate_Result::register_seam_edge(Vertex_Specifier *spec_0,
                                             Vertex_Specifier *spec_1) {
    assert(!specs_match(spec_0, spec_1));

    spec_0->debug_condition_code = 0;  // It's a seam edge!
    spec_1->debug_condition_code = 0;  // It's a seam edge!

    Seam_Edge *edge = new Seam_Edge();
    edge->index_0 = find_vertex(spec_0);
    edge->index_1 = find_vertex(spec_1);

    assert(edge->index_0 != -1);
    assert(edge->index_1 != -1);

    edge->spec_0 = *spec_0;
    edge->spec_1 = *spec_1;

    assert(spec_0->input_n0 >= 0);
    assert(spec_0->input_n1 >= 0);
    assert(spec_1->input_n0 >= 0);
    assert(spec_1->input_n1 >= 0);

    seam_edges.add(edge);
}

void Intermediate_Result::clean() {
    delete mesh_builder;
    mesh_builder = NULL;

    delete vertex_hash_table;
    vertex_hash_table = NULL;

    Seam_Edge *edge;
    Foreach(&seam_edges, edge) { 
        delete edge;
    } Endeach;
    seam_edges.clean();
}



inline int Vertex_Specifier::get_hash_code() {
    return input_n0 * 5 + input_n1 * 3;  // @Speed: Compute a real hash code here instead of this lame thing!
}

int Intermediate_Result::add_vertex(Vector3 position, Vector2 uv, 
                                    Quaternion tangent_frame,
                                    Vertex_Specifier *specifier) {
    int index = mesh_builder->add_vertex(position, uv, tangent_frame);
    specifier->output_index = index;

    vertex_hash_table->add(new Vertex_Specifier(specifier));
    return index;
}

int Intermediate_Result::find_vertex(Vertex_Specifier *specifier) {
    Vertex_Specifier *already_defined = (Vertex_Specifier *)vertex_hash_table->find(specifier);
    if (already_defined) {
        return already_defined->output_index;
    }

    return -1;
}

int Intermediate_Result::maybe_add_vertex(Vector3 position, Vector2 uv,
                                          Quaternion tangent_frame,
                                          Vertex_Specifier *specifier) {
    int index = find_vertex(specifier);
    if (index != -1) return index;

    return add_vertex(position, uv, tangent_frame, specifier);
}