preprocess_world.cpp

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

#include "framework.h"
#include "make_world.h"

#include <stdio.h>
#include <stdlib.h>

#include "seam_database.h"
#include "mesh.h"
#include "mesh_chopper.h"
#include "mesh_seam.h"
#include "tangent_frames.h"
#include <float.h>  // For FLT_MAX and FLT_MIN

#include "mesh_reducer.h"
#include "mesh_topology_handler.h"
#include "mesh_builder.h"
#include "error_quadric.h"
#include "covariance.h"

#include <math.h>  // For sqrtf

const int TRIANGLE_MAXIMUM = 6000;
    
void find_bounding_box(Triangle_List_Mesh *mesh, Vector3 *bbox_min, Vector3 *bbox_extents);


struct World_Processor {
    World_Processor();
    ~World_Processor();

    int next_block_id;
    Seam_Database *construction_database;
    World_Block *root;

    World_Block *chop_mesh(Triangle_List_Mesh *mesh,
                           Plane3 *planes, int num_planes);
    void finish_subdivide_phase();
    void do_merges();
    void recompute_leaf_distances(World_Block *block);

  protected:
    void block_init_for_subdivide_step(World_Block *block, Triangle_List_Mesh *mesh);
    void localize_block(World_Block *block);
    void chop_leaves(World_Block *root);
    void cleanup_non_root_blocks(World_Block *block);

    void do_single_rewrite(World_Block *root,
                           Mesh_Seam *seam, 
                           World_Block *block_a,
                           World_Block *block_b,
                           Chopped_Result *result_a,
                           Chopped_Result *result_b);
    void do_rewrite_rules(World_Block *root,
                          World_Block *block_a,
                          World_Block *block_b,
                          Chopped_Result *result_a,
                          Chopped_Result *result_b);

    void do_recursive_merge(World_Block *root);
    void unmark_blocks(World_Block *block);
};

void sanity_check(Mesh_Seam *seam) {
    int i;
    for (i = 0; i < seam->num_faces * 3; i++) {
        Seam_Index *index = &seam->indices[i];
        World_Block *block = seam->block_membership[index->which_mesh];
        assert(index->vertex_index < block->mesh->num_vertices);
    }
}

void scale_mesh(Triangle_List_Mesh *mesh, float factor) {
    int i;
    for (i = 0; i < mesh->num_vertices; i++) {
        mesh->vertices[i] *= factor;
    }
}

#include "quake3_bsp.h"

int get_num_triangles(BSP_BIQUADRATIC_PATCH *patch) {
    int t = patch->tesselation;
    return t*t*2;
}

void do_patch(Triangle_List_Mesh *mesh, int triangle_index, BSP_PATCH *patch) {

}

Triangle_List_Mesh *load_quake() {
    const int CURVE_TESSELATION = 8;

    BSP *bsp = new BSP();
//    bool success = bsp->load("data\\test1.bsp", CURVE_TESSELATION);
    bool success = bsp->load("hal9000_b_ta.bsp", CURVE_TESSELATION);
    if (!success) {
        printf("File load error.  Aborting!\n");
        exit(1);
    }

    assert(success);

    int num_faces = bsp->numPolygonFaces;
    int num_polyface_triangles = 0;
    int num_patch_triangles = 0;
    int num_mesh_face_triangles = 0;

    int i;
    for (i = 0; i < bsp->numPolygonFaces; i++) {
        int nvertices = bsp->polygonFaces[i].numVertices;
        assert(nvertices >= 3);
        num_polyface_triangles += nvertices - 2;
    }

    for (i = 0; i < bsp->numMeshFaces; i++) {
        BSP_MESH_FACE *face = &bsp->meshFaces[i];
        num_mesh_face_triangles += face->numMeshIndices / 3;
    }


    int j;
    for (i = 0; i < bsp->numPatches; i++) {
        BSP_PATCH *patch = &bsp->patches[i];

        for (j = 0; j < patch->numQuadraticPatches; j++) {
            num_patch_triangles += get_num_triangles(&patch->quadraticPatches[j]);
        }
    }

    int num_triangles = num_polyface_triangles + num_patch_triangles + num_mesh_face_triangles;

    Mesh_Builder builder(num_triangles * 3, num_triangles);
    for (i = 0; i < bsp->numTextures; i++) {
        Mesh_Material_Info *info = new Mesh_Material_Info;
        info->name = strdup(bsp->loadTextures[i].name);
        builder.add_material(info);
    }


    for (i = 0; i < bsp->numVertices; i++) {
        Vector3 position = bsp->vertices[i].position;
        float u = bsp->vertices[i].decalS;
        float v = bsp->vertices[i].decalT;
        
        builder.add_vertex(position, Vector2(u, v), Quaternion(0, 0, 0, 1));
    }

    for (i = 0; i < bsp->numPolygonFaces; i++) {
        int nvertices = bsp->polygonFaces[i].numVertices;
        int first_index = bsp->polygonFaces[i].firstVertexIndex;
        int material = bsp->polygonFaces[i].textureIndex;

        int j;
        for (j = 2; j < nvertices; j++) {
            int n0 = 0;
            int n1 = j-1;
            int n2 = j;

            // Flip the triangle's clockwiseness...

            builder.add_triangle(first_index + n0, first_index + n2,
                                 first_index + n1, material);
        }
    }


    for (i = 0; i < bsp->numPatches; i++) {
        BSP_PATCH *patch = &bsp->patches[i];
        int material = patch->textureIndex;

        for (j = 0; j < patch->numQuadraticPatches; j++) {
            BSP_BIQUADRATIC_PATCH *quadratic = &patch->quadraticPatches[j];
            
            int t = quadratic->tesselation;
            int num_vertices = (t+1)*(t+1);
            
            int vertex_offset = builder.num_vertices;

            int k;
            for (k = 0; k < num_vertices; k++) {
                BSP_VERTEX *vertex = &quadratic->vertices[k];
                builder.add_vertex(vertex->position,
                                   Vector2(vertex->decalS, vertex->decalT), Quaternion(0, 0, 0, 1));
            }


            int num_triangles_each_row = 2*t;

            int row;
            for (row = 0; row < t; row++) {
                int point;
                for (point = 0; point < t; point++) {
                    int n0 = row*(t+1)+point;
                    int n1 = (row+1)*(t+1)+point;
                    int n2 = n1 + 1;
                    int n3 = n0 + 1;

                    n0 += vertex_offset;
                    n1 += vertex_offset;
                    n2 += vertex_offset;
                    n3 += vertex_offset;

                    builder.add_triangle(n0, n1, n2, material);
                    builder.add_triangle(n0, n2, n3, material);
                }
            }
        }
    }



    for (i = 0; i < bsp->numMeshFaces; i++) {
        BSP_MESH_FACE *face = &bsp->meshFaces[i];
        int material = face->textureIndex;

        int k;
        for (k = 0; k < face->numMeshIndices; k += 3) {
            int n0 = bsp->meshIndices[face->firstMeshIndex + k];
            int n1 = bsp->meshIndices[face->firstMeshIndex + k + 1];
            int n2 = bsp->meshIndices[face->firstMeshIndex + k + 2];
            
            n0 += face->firstVertexIndex;
            n1 += face->firstVertexIndex;
            n2 += face->firstVertexIndex;

            builder.add_triangle(n0, n2, n1, material);
        }
    }


    printf("\nBuild mesh\n");

    Triangle_List_Mesh *mesh = builder.build_mesh();
    scale_mesh(mesh, 1.0f / 12.0f);

       
    Tangent_Frame_Maker maker;
    maker.compute_tangent_frames(mesh);
    delete [] mesh->tangent_frames;
    mesh->tangent_frames = maker.tangent_frames;
    maker.tangent_frames = NULL;

    return mesh;
}

void World_Processor::block_init_for_subdivide_step(World_Block *block, Triangle_List_Mesh *mesh) {
    find_bounding_box(mesh,
                      &block->bounding_box_corner,
                      &block->bounding_box_extents);

    block->position = Vector3(0, 0, 0);

    block->mesh = mesh;
    block->block_id = (Block_Identifier)(next_block_id++);
}


void World_Processor::localize_block(World_Block *block) {
    Vector3 position = block->bounding_box_corner + block->bounding_box_extents * 0.5f;

    block->bounding_box_corner -= position;
    block->position = position;

    int i;
    for (i = 0; i < block->mesh->num_vertices; i++) {
        block->mesh->vertices[i] -= position;
    }
}


void get_bounding_points(World_Block *root, Vector3 results[8]) {
    Vector3 p0 = root->position + root->bounding_box_corner;
    Vector3 p1 = p0 + root->bounding_box_extents;

    results[0] = Vector3(p0.x, p0.y, p0.z);
    results[1] = Vector3(p1.x, p0.y, p0.z);
    results[2] = Vector3(p1.x, p1.y, p0.z);
    results[3] = Vector3(p0.x, p1.y, p0.z);
    results[4] = Vector3(p0.x, p0.y, p1.z);
    results[5] = Vector3(p1.x, p0.y, p1.z);
    results[6] = Vector3(p1.x, p1.y, p1.z);
    results[7] = Vector3(p0.x, p1.y, p1.z);
}

bool block_crosses_plane(World_Block *root, Plane3 *plane) {
    Vector3 bounding_points[8];
    get_bounding_points(root, bounding_points);

    float dot_min = FLT_MAX;
    float dot_max = FLT_MIN;

    int i;
    for (i = 0; i < 8; i++) {
        float dot = plane_dot(plane, &bounding_points[i]);
        if (dot < dot_min) dot_min = dot;
        if (dot > dot_max) dot_max = dot;
    }

    if ((dot_min < 0) && (dot_max > 0)) return true;
    return false;
}

void World_Processor::cleanup_non_root_blocks(World_Block *block) {
    if (block->num_children) {
        block->block_search_marker = 1;
        delete block->mesh;
        block->mesh = NULL;
        
        int i;
        for (i = 0; i < block->num_children; i++) {
            cleanup_non_root_blocks(block->children[i]);
        }
    } else {
        block->block_search_marker = 0;
        localize_block(block);
    }
}

void World_Processor::unmark_blocks(World_Block *block) {
    block->block_search_marker = 0;
    int i;
    for (i = 0; i < block->num_children; i++) unmark_blocks(block->children[i]);
}

void World_Processor::finish_subdivide_phase() {
    printf("Cleanup non_root\n");
    cleanup_non_root_blocks(root);

    printf("Delete seams\n");
    construction_database->delete_seams_that_touch_marked_blocks();