preprocess_world.cpp

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

        for (j = 0; j < 3; j++) {
            Seam_Index *index = &seam->indices[i*3+j];
            orig_index[j] = index->vertex_index;

            World_Block *block = seam->block_membership[index->which_mesh];

            if (block == root) {
                spec_a[j] = get_spec(index, result_a);
                spec_b[j] = get_spec(index, result_b);

                int xref_a, xref_b;
                xref_a = find_output_vertex(index, result_a);
                xref_b = find_output_vertex(index, result_b);
                if (xref_a != -1) {
                    block = block_a;
                    results[j] = result_a;

                    tmp_indices[j] = *index;
                    tmp_indices[j].vertex_index = xref_a;
                    tmp_indices_a[j] = tmp_indices[j];

                    dest_seams[j] = result_seam_a;
                    num_a_indices++;
                }

                if (xref_b != -1) {
                    block = block_b;
                    results[j] = result_b;

                    tmp_indices[j] = *index;
                    tmp_indices[j].vertex_index = xref_b;
                    tmp_indices_b[j] = tmp_indices[j];

                    dest_seams[j] = result_seam_b;
                    num_b_indices++;
                }
            } else {
                tmp_indices[j] = *index;
                tmp_indices_a[j] = *index;
                tmp_indices_b[j] = *index;
                results[j] = NULL;
                dest_seams[j] = NULL;

                n0 = j;
                n1 = (j + 1) % 3;
                n2 = (j + 2) % 3;

                num_c_indices++;
            }

            blocks[j] = block;
        }

        if ((num_c_indices == 2) && (num_a_indices + num_b_indices > 1)) {
            // XXX Fucking fuck it for now
        }

        if (num_a_indices + num_c_indices == 3) {
            add_face(result_seam_a, tmp_indices_a);
        } 

        if (num_b_indices + num_c_indices == 3) {
            add_face(result_seam_b, tmp_indices_b);
        }

        if ((num_a_indices == 1) && (num_b_indices == 1) && (num_c_indices == 1)) {
            // This face spans 3 blocks now... gotta clip it!

            // n0 is the vertex that is not on the block being
            // split... which must exist, so n0 != -1.
            assert(n0 != -1);


            Vertex_Specifier spec(orig_index[n1], orig_index[n2]);
            rectify(&spec);

            Seam_Index new_face[3];
            new_face[0] = tmp_indices[n0];

            int xref_1 = find_clip_vertex(&spec, results[n1]);
            if (xref_1 == -1) continue;  // XXX Think harder about this

            new_face[1] = tmp_indices[n1];
            new_face[2] = tmp_indices[n1];
            new_face[2].vertex_index = xref_1;

            add_face(dest_seams[n1], new_face);


            int xref_2 = find_clip_vertex(&spec, results[n2]);
            if (xref_2 == -1) continue;  // XXX Think harder about this

            new_face[1] = tmp_indices[n2];
            new_face[1].vertex_index = xref_2;
            new_face[2] = tmp_indices[n2];
            add_face(dest_seams[n2], new_face);



            Mesh_Seam *new_seam = new Mesh_Seam(1); // XXX spammy!
            new_seam->num_faces = 0;
            new_seam->block_membership[0] = blocks[n0];
            new_seam->block_membership[1] = blocks[n1];
            new_seam->block_membership[2] = blocks[n2];

            // new_face[0].vertex_index stays the same from above.
            new_face[0].which_mesh = 0;
            new_face[1].which_mesh = 1;
            new_face[2].which_mesh = 2;

            new_face[1].vertex_index = xref_1;
            new_face[2].vertex_index = xref_2;

            add_face(new_seam, new_face);
            maybe_add(construction_database, new_seam);
        }
    }

//    sanity_check(result_seam_a);
//    sanity_check(result_seam_b);

    maybe_add(construction_database, result_seam_a);
    maybe_add(construction_database, result_seam_b);
}

void World_Processor::do_rewrite_rules(World_Block *root,
                                       World_Block *block_a,
                                       World_Block *block_b,
                                       Chopped_Result *result_a,
                                       Chopped_Result *result_b) {
    Auto_Array <Mesh_Seam *> seams;
    construction_database->find_seams_containing_at_least_this_block(root, &seams);

    Mesh_Seam *seam;
    Array_Foreach(&seams, seam) {
        do_single_rewrite(root, seam, block_a, block_b, result_a, result_b);
    } Endeach;
}

Plane3 get_plane_from_mesh(Triangle_List_Mesh *mesh) {
    assert(mesh->num_vertices > 0);

    Vector3 mean(0, 0, 0);
    Covariance3 cov;
    cov.reset();

    // XXXXXXXXXXXXXXXXX do barycenter here, not mesh->vertex
    int i;
    for (i = 0; i < mesh->num_vertices; i++) {
        mean += mesh->vertices[i];
        cov.accumulate(mesh->vertices[i]);
    }

    float factor = (1.0f / (float)mesh->num_vertices);
    mean *= factor;
    cov.scale(factor);

    Covariance3 local;
    cov.move_to_local_coordinates(&local, mean);
    
    float eigenvalues[3];
    Vector3 eigenvectors[3];
    local.find_eigenvectors(eigenvalues, eigenvectors);

//    mean = Vector3(0, 0, 0);
//    eigenvectors[0] = Vector3(1, 0, 0);

    Vector3 normal = eigenvectors[0];
/*
    if ((fabs(normal.x) > fabs(normal.y)) && (fabs(normal.x) > fabs(normal.z))) {
        normal.set(1, 0, 0);
    } else if ((fabs(normal.y) > fabs(normal.x)) && (fabs(normal.y) > fabs(normal.z))) {
        normal.set(0, 1, 0);
    } else {
        normal.set(0, 0, 1);
    }
*/
    return Plane3(mean, normal);
}

void World_Processor::chop_leaves(World_Block *root) {
    Triangle_List_Mesh *mesh = root->mesh;
    if (!mesh) return;  // Shouldn't happen??

    if (mesh->num_faces <= TRIANGLE_MAXIMUM) return;


    printf("Split %d (%d)\n", root->leaf_distance, mesh->num_faces);

    // Split mesh...


    Mesh_Chopper chopper;
    Chopped_Result result_a;
    Chopped_Result result_b;

    
    Plane3 plane = get_plane_from_mesh(mesh);

    int plane_id = 0;
    Mesh_Seam *seam_a_to_b;
    chopper.chop_mesh(mesh, &plane, plane_id,
                      &result_a, &result_b, &seam_a_to_b);

    World_Block *block_a = new World_Block();
    block_init_for_subdivide_step(block_a, result_a.result_mesh);

    World_Block *block_b = new World_Block();
    block_init_for_subdivide_step(block_b, result_b.result_mesh);

    seam_a_to_b->block_membership[0] = block_a;
    seam_a_to_b->block_membership[1] = block_b;

    block_a->leaf_distance = root->leaf_distance - 1;
    block_b->leaf_distance = root->leaf_distance - 1;
    if (seam_a_to_b->num_faces) construction_database->add(seam_a_to_b);

    root->children[0] = block_a;
    root->children[1] = block_b;
    root->num_children = 2;

    do_rewrite_rules(root, block_a, block_b, &result_a, &result_b);
    delete result_a.vertex_hash_table;
    delete result_b.vertex_hash_table;


    // Get rid of it!

    delete mesh;
    root->mesh = NULL;

    if (root->num_children) {
        int i;
        for (i = 0; i < root->num_children; i++) {
            chop_leaves(root->children[i]);
        }
    }
}

World_Processor::World_Processor() {
    next_block_id = 1;  // 0 is reserved!
    construction_database = new Seam_Database();
    root = NULL;
}

World_Processor::~World_Processor() {
    delete construction_database;
}

World_Block *World_Processor::chop_mesh(Triangle_List_Mesh *mesh,
                                        Plane3 *planes, int num_planes) {
    World_Block *block = new World_Block();
    block_init_for_subdivide_step(block, mesh);
    block->leaf_distance = 500;

    int i;
    for (i = 0; i < num_planes; i++) {
        chop_leaves(block);
    }

    root = block;
    return block;
}

void main(int argc, char **argv) {
    Elevation_Map *map;
    char *filename = NULL;

    if (argc > 1) {
        filename = argv[1];
    }

/*
    if (filename == NULL) {
        fprintf(stderr, "Please specify a file to load!\n");
        exit(1);
    }

    if (map == NULL) {
        assert(filename);
        fprintf(stderr, "Unable to open map file '%s'!\n", filename);
        exit(1);
    }

*/

    Triangle_List_Mesh *mesh = load_quake();

    char *output_filename = "output.world_lod";
    FILE *f = fopen(output_filename, "wb");
    if (f == NULL) {
        fprintf(stderr, "Unable to open output file '%s' for writing!\n",
                output_filename);
        exit(1);
    }

    // Make some splitting planes
    
    const int MAX_PLANES = 20;
    Plane3 planes[MAX_PLANES];
    int num_planes = 0;
    const float k = 1.0f;

    planes[num_planes++] = Plane3(Vector3(0, 0, 0), Vector3(1, 0, 0));
    planes[num_planes++] = Plane3(Vector3(0, 0, 3), Vector3(0, 0, 1));

    Vector3 weird1(1, 0, 1);
    weird1.normalize();
    Vector3 weird2(.11, -.4, 1);
    weird2.normalize();
    planes[num_planes++] = Plane3(Vector3(0.5, 0, 3), weird1);
    planes[num_planes++] = Plane3(Vector3(0, 0, 2.6), weird2);

    World_Processor processor;
    processor.chop_mesh(mesh, planes, num_planes);
    processor.finish_subdivide_phase();

    processor.do_merges();

    printf("Leaf distances.\n");
    processor.recompute_leaf_distances(processor.root);

    save_world(processor.root, processor.construction_database, f);
    fclose(f);
    printf("Saved result as '%s'.\n", output_filename);

    exit(0);
}