make_world.cpp

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

int *identity_index_map(int num_vertices) {
    int *result = new int[num_vertices];

    int i;
    for (i = 0; i < num_vertices; i++) result[i] = i;

    return result;
}


World_Block::World_Block() {
    frame_index = 0;
    parent = NULL;

    children[0] = NULL;
    children[1] = NULL;
    children[2] = NULL;
    children[3] = NULL;

    num_children = 0;
    block_search_marker = 0;
    leaf_distance = 0;

    worldspace_error = 0;
}

World_Block::~World_Block() {
    delete mesh;
}


Mesh_Seam::Mesh_Seam(int _num_faces) {
    num_faces = _num_faces;
    indices = new Seam_Index[num_faces * 3];
    is_high_res_seam = false;
    block_membership[0] = NULL;
    block_membership[1] = NULL;
    block_membership[2] = NULL;
}

Mesh_Seam::~Mesh_Seam() {
    delete [] indices;
}

inline bool indices_match(Seam_Index *n0, Seam_Index *n1) {
    if (n0->which_mesh != n1->which_mesh) return false;
    if (n0->vertex_index != n1->vertex_index) return false;

    return true;
}

void Mesh_Seam::compute_uv_coordinates(Triangle_List_Mesh *mesh) {
    int num_indices = num_faces * 3;

    int last_anchor_point = -1;
    int num_anchor_points = 0;

    Vector3 p0, p1;
    Vector2 u0, u1;

    int i;
    for (i = 0; i < num_indices; i++) {
        if (indices[i].which_mesh == 0) {
            Vector2 uv = mesh->uvs[i];

            if (num_anchor_points == 0) {
                num_anchor_points++;

                last_anchor_point = i;
                p0 = mesh->vertices[i];
                u0 = uv;
            } else {
                if (indices[i].vertex_index == indices[last_anchor_point].vertex_index) continue;

                num_anchor_points++;

                p1 = mesh->vertices[i];
                u1 = uv;
            }
        }
    }

    if (num_anchor_points < 2) {
        Vector2 uv;

        if (num_anchor_points == 0) {
            uv.x = 0;
            uv.y = 0;
        } else {
            assert(last_anchor_point >= 0);
            int vertex_index = indices[last_anchor_point].vertex_index;
            uv = mesh->uvs[vertex_index];
        }

        int i;
        for (i = 0; i < num_indices; i++) {
            indices[i].uv = uv;
        }
    } else {
        // @Study: Seems like we have to break things into a direction
        // and length here, which is weird.  Can Clifford algebra help us
        // with this?
        Vector3 dp = p1 - p0;
        Vector2 du = u1 - u0;

        float dp_len = dp.length();
        Vector3 dp_dir;

        if (dp_len == 0) {
            dp_len = 1;
            dp_dir = Vector3(0, 0, 0);
        } else {
            dp_dir = dp;
            dp_dir.normalize();
        }

        int i;
        for (i = 0; i < num_indices; i++) {
            Vector3 pos = mesh->vertices[i];
            Vector3 relative = pos - p0;

            float proj_len = dot_product(relative, dp_dir);
            Vector2 uv = u0 + du * (proj_len / dp_len);

            indices[i].uv = uv;
        }            
    }
}

void sanity_seam(Mesh_Seam *seam, World_Block *block_a,
                 World_Block *block_b) {
    int i;
    for (i = 0; i < seam->num_faces * 3; i++) {
        Seam_Index *index = &seam->indices[i];
        assert((index->which_mesh == 0) || (index->which_mesh == 1));
        World_Block *block = block_a;
        if (index->which_mesh == 1) block = block_b;

        assert(index->vertex_index >= 0);
        assert(index->vertex_index < block->mesh->num_vertices);
    }
}


void Mesh_Seam::remove_degenerate_faces() {

    int i;
    for (i = 0; i < num_faces; i++) {
        Seam_Index *n0 = &indices[i*3+0];
        Seam_Index *n1 = &indices[i*3+1];
        Seam_Index *n2 = &indices[i*3+2];

        if (indices_match(n0, n1) || indices_match(n0, n2) || indices_match(n1, n2)) {
            // Actually copy the rest of the faces in the seam downward
            // I do this inefficient thing, rather than just copying the
            // guy out from the end, because I want the colored stripeys
            // to come out looking right in the "seam demo" and debug
            // visualization.

            // For a shipping tool where this is not a concern,
            // go ahead and just copy the end face into this slot.
            // (This is the code that's currently commented out).
/*
            int k = num_faces - 1;
            indices[i*3+0] = indices[k*3+0];
            indices[i*3+1] = indices[k*3+1];
            indices[i*3+2] = indices[k*3+2];
            num_faces--;
            i--;
*/
            int src_face = i + 1;
            while (src_face < num_faces) {
                int dest_face = src_face - 1;
                indices[dest_face*3+0] = indices[src_face*3+0];
                indices[dest_face*3+1] = indices[src_face*3+1];
                indices[dest_face*3+2] = indices[src_face*3+2];
                src_face++;
            }

            num_faces--;

            i--;

        }
    }
}



void do_face(Tangent_Frame_Maker *maker, Elevation_Map *map, int indices[3]) {
    Vector3 pos[3];
    Vector3 uv[3];

    pos[0] = get_position(map, indices[0]);
    pos[1] = get_position(map, indices[1]);
    pos[2] = get_position(map, indices[2]);

    uv[0] = get_uv(map, indices[0]);
    uv[1] = get_uv(map, indices[1]);
    uv[2] = get_uv(map, indices[2]);
    
    maker->accumulate_triangle(indices, pos, uv);
}


void build_tangent_frames(Elevation_Map *map) {
    Tangent_Frame_Maker maker;
    maker.begin_tangent_frames(map->num_samples_x * map->num_samples_y);
    int i, j;
    for (j = 0; j < map->num_samples_y-1; j++) {
        for (i = 0; i < map->num_samples_x-1; i++) {
            int face_type = (i ^ j) & 1;
            int n0 = map->get_index(i+0, j+0);
            int n1 = map->get_index(i+1, j+0);
            int n2 = map->get_index(i+1, j+1);
            int n3 = map->get_index(i+0, j+1);

            int indices[3];


            indices[0] = n0;
            indices[1] = n1;

            if (face_type == 0) {
                indices[2] = n2;
            } else {
                indices[2] = n3;
            }

            do_face(&maker, map, indices);

            if (face_type == 0) {
                indices[0] = n0;
            } else {
                indices[0] = n1;
            }

            indices[1] = n2;
            indices[2] = n3;

            do_face(&maker, map, indices);
        }
    }

    maker.complete_tangent_frames();
    map->tangent_frames = maker.tangent_frames;
}

// Helper function called by qsort in simplify_block_membership()
int compare_block_membership(const void *b1, const void *b2) {
    World_Block *block1 = *(World_Block **)b1;
    World_Block *block2 = *(World_Block **)b2;

    if (block1->block_id < block2->block_id) return -1;
    if (block1->block_id > block2->block_id) return +1;
    return 0;
}

int find_remapping(World_Block *old_block,
                   World_Block **new_blocks, int num_blocks) {
    int i;
    for (i = 0; i < num_blocks; i++) {
        if (new_blocks[i] == old_block) return i;
    }

    return -1;
}

void Mesh_Seam::simplify_block_membership() {
    // Copy block membership

    World_Block *new_membership[3];
    int num_blocks = 0;
    int i;
    for (i = 0; i < 3; i++) {
        new_membership[i] = block_membership[i];
        if (new_membership[i]) num_blocks++;
    }

    // Sort it

    qsort(new_membership, num_blocks, sizeof(new_membership[0]), compare_block_membership);

    // Check for duplicates

    if (new_membership[1] == new_membership[2]) {
        new_membership[2] = NULL;
    }

    if (new_membership[0] == new_membership[1]) {
        if (new_membership[2]) {
            new_membership[1] = new_membership[2];
            new_membership[2] = NULL;
        } else {
            new_membership[1] = NULL;
        }
    }

    // Figure out the index cross-reference for remapping.

    int remap[3];
    for (i = 0; i < num_blocks; i++) {
        int index = find_remapping(block_membership[i], new_membership, 3);
        assert(index != -1);
        remap[i] = index;
    }

    // Update the block membership array.

    for (i = 0; i < 3; i++) {
        block_membership[i] = new_membership[i];
    }

    // Actually remap the seam.

    for (i = 0; i < num_faces * 3; i++) {
        Seam_Index *index = &indices[i];
        index->which_mesh = remap[index->which_mesh];

        // Verify...
        World_Block *block = block_membership[index->which_mesh];
        assert(block);
        assert(index->vertex_index < block->mesh->num_vertices);
    }
}