preprocess_world.cpp

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

    unmark_blocks(root);

    // @Refactor: Assertion below... can be taken out when everything is working.
/*
    Mesh_Seam *seam;
    Array_Foreach(&construction_database->seams, seam) {
        int i;
        for (i = 0; i < 3; i++) {
            World_Block *block = seam->block_membership[i];
            if (block) assert(block->mesh);
        }
    } Endeach;
*/
}

void sanity_check(Triangle_List_Mesh *mesh) {
    int i;
    for (i = 0; i < mesh->num_vertices; i++) {
        assert(fabs(mesh->vertices[i].x) < 100000.0f);
        assert(!_isnan(mesh->vertices[i].x));
        assert(_finite(mesh->vertices[i].x));
    }
}

void World_Processor::recompute_leaf_distances(World_Block *block) {
    if (block->num_children == 0) {
        block->leaf_distance = 0;
        return;
    }

    int leaf_distance_min = 99999;   // @Refactor: Icky hack-type thing
    int i;
    for (i = 0; i < block->num_children; i++) {
        recompute_leaf_distances(block->children[i]);
        int dist = block->children[i]->leaf_distance;
        if (dist < leaf_distance_min) leaf_distance_min = dist;
    }

    block->leaf_distance = leaf_distance_min + 1;
}

float get_squared_error(Mesh_Reducer *reducer, int index) {
    Error_Quadric *quadric = reducer->get_quadric(index);

    float xyzuv[5];
    reducer->fill_point(xyzuv, index, -1);
    float error = quadric->evaluate_error(xyzuv);

    // The error we return takes into account textural error,
    // in addition to position error.  Maybe this is not strictly
    // what you want but for most applications it is
    // probably fine.  (ATTENTION: This differs from what was
    // originally written in the companion article; what was
    // written there was actually an incorrect solution to
    // the problem).

    if (error < 0) error = 0; // Takes care of floating-point rounding issue
    return sqrtf(error);
}

float get_root_mean_squared_error(Mesh_Reducer *reducer, Triangle_List_Mesh *orig_mesh) {
    float sum_of_squares = 0;

    Mesh_Topology_Handler *handler = reducer->topology_handler;

    int i;
    for (i = 0; i < reducer->initial_num_vertices; i++) {
        if (!(handler->vertex_flags[i] & VERTEX_IS_LIVE)) continue;
        if (orig_mesh->canonical_vertex_map[i] != i) continue;

        float square = get_squared_error(reducer, i);
        sum_of_squares += square;
    }

    return sqrt(sum_of_squares);
}

void World_Processor::do_recursive_merge(World_Block *root) {
    if (root->num_children == 0) return;

    // Make sure all the children are merged...

    int i;
    for (i = 0; i < root->num_children; i++) do_recursive_merge(root->children[i]);

    // Now let's compute our mesh!
    World_Block *node = root;
    assert(node->mesh == NULL);
    

    const int MAX_BLOCKS = 16;
    Triangle_List_Mesh *meshes[MAX_BLOCKS];
    World_Block *blocks[MAX_BLOCKS];

    Vector3 position_sum(0, 0, 0);
    int num_faces_before_seams = 0;
    int num_triangle_lists_before_seams = 0;

    printf("merge %d\n", node->leaf_distance);
    int num_blocks = 0;
    for (i = 0; i < node->num_children; i++) {
        assert(num_blocks < MAX_BLOCKS);

        World_Block *child = node->children[i];
        assert(child);

        meshes[num_blocks] = child->mesh;
        blocks[num_blocks] = child;
        blocks[num_blocks]->temporary_integer_storage = i;

        assert(_finite(blocks[num_blocks]->position.x));
        position_sum += blocks[num_blocks]->position;

        num_faces_before_seams += child->mesh->num_faces;
        num_triangle_lists_before_seams += child->mesh->num_triangle_lists;

        num_blocks++;
    }            

    assert(num_blocks > 0);

    World_Block *block = node;
    block->position = position_sum * (1.0f / (float)num_blocks);
    assert(_finite(block->position.x));

    // @Robustness: Maybe we should first merge, then compute the
    // bounding box, then figure out the new position and recenter
    // the box and mesh etc.
    Vector3 offsets[MAX_BLOCKS];
    for (i = 0; i < num_blocks; i++) {
        offsets[i] = blocks[i]->position - block->position;
    }


    // Figure out which seams to combine into this block
    Auto_Array <Mesh_Seam *> seams;
    construction_database->find_seams_containing_these_blocks(blocks, num_blocks, &seams);

    int *index_maps[MAX_BLOCKS];
    Triangle_List_Mesh *merged_mesh = merge_meshes(num_blocks, meshes, offsets,
                                                   index_maps, &seams);
    for (i = 0; i < num_blocks; i++) {
        blocks[i]->index_map_into_parent = index_maps[i];
    }

    Triangle_List_Mesh *reduced;
    Mesh_Reducer reducer;
    reducer.tuning.texture_space_importance_factor = 20.0f;
    reducer.init(merged_mesh);

    int seam_face_index = num_faces_before_seams;
    for (i = num_triangle_lists_before_seams; i < merged_mesh->num_triangle_lists; i++) {
        Triangle_List_Info *info = &merged_mesh->triangle_list_info[i];

        int j;
        assert(info->num_vertices % 3 == 0);
        for (j = 0; j < info->num_vertices / 3; j++) {
            reducer.mark_face_as_seam(seam_face_index);
            seam_face_index++;
        }
    }

    reducer.collapse_similar_vertices(0.001);
    reducer.reduce(TRIANGLE_MAXIMUM);
    reducer.get_result(&reduced);
    block->mesh = reduced;
    block->worldspace_error = get_root_mean_squared_error(&reducer, merged_mesh);

    for (i = 0; i < num_blocks; i++) {
        World_Block *child_block = blocks[i];
        if (block->worldspace_error < child_block->worldspace_error) 
            block->worldspace_error = child_block->worldspace_error;
    }

    void xref_block_index_map(World_Block *block, Mesh_Reducer *reducer);
    for (i = 0; i < num_blocks; i++) {
        xref_block_index_map(blocks[i], &reducer);
    }

    delete merged_mesh;

    find_bounding_box(reduced, 
                      &block->bounding_box_corner,
                      &block->bounding_box_extents);

    for (i = 0; i < num_blocks; i++) {
        Rewrite_Rule rule;
        rule.source_block = blocks[i];
        rule.dest_block = block;
        rule.index_map = blocks[i]->index_map_into_parent;
        construction_database->perform_rewrite_rule(&rule, 100);
    }
    
}

void World_Processor::do_merges() {
    do_recursive_merge(root);
}

void maybe_add(Seam_Database *database, Mesh_Seam *seam) {
    if (seam->num_faces == 0) {
        delete seam;
        return;
    }

    database->add(seam);
}

void rewrite_block_membership(Mesh_Seam *src_seam, Mesh_Seam *dest_seam,
                              World_Block *src_block, World_Block *dest_block) {
    int i;
    for (i = 0; i < 3; i++) {
        World_Block *block = src_seam->block_membership[i];
        if (block == src_block) block = dest_block;
        dest_seam->block_membership[i] = block;
    }
}


void add_face(Mesh_Seam *seam, Seam_Index *indices) {
    int i = seam->num_faces++;
    seam->indices[i*3+0] = indices[0];
    seam->indices[i*3+1] = indices[1];
    seam->indices[i*3+2] = indices[2];

//    sanity_check(seam);
}

Vertex_Specifier *get_spec(Seam_Index *index, Chopped_Result *result) {
    int pre_xref = index->vertex_index;
    Vertex_Specifier spec(pre_xref, pre_xref);
    Vertex_Specifier *found = (Vertex_Specifier *)result->vertex_hash_table->find(&spec);
    return found;
}

int find_output_vertex(Seam_Index *index, Chopped_Result *result) {
    int pre_xref = index->vertex_index;
    
    Vertex_Specifier spec(pre_xref, pre_xref);
    Vertex_Specifier *found = (Vertex_Specifier *)result->vertex_hash_table->find(&spec);
    if (!found) return -1;
    return found->output_index;
}

int find_clip_vertex(Vertex_Specifier *spec, Chopped_Result *result) {
    Vertex_Specifier *found = (Vertex_Specifier *)result->vertex_hash_table->find(spec);
    if (!found) return -1;

    assert(found->output_index != -1);
    return found->output_index;
}

void rectify(Vertex_Specifier *spec) {
    if (spec->input_n0 > spec->input_n1) {
        int tmp = spec->input_n0;
        spec->input_n0 = spec->input_n1;
        spec->input_n1 = tmp;
    }
}


const int MAX_HIERARCHY_DISTANCE = 999;
void World_Processor::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) {

    // Check to see if the resulting seam will be within the
    // proper hierarchy distance.  If it won't, we bail!
    int max_hierarchy_distance = MAX_HIERARCHY_DISTANCE;
    int leaf_distance_min, leaf_distance_max;
    leaf_distance_min = leaf_distance_max = block_a->leaf_distance;
    
    int i;
    for (i = 0; i < 3; i++) {
        World_Block *other = seam->block_membership[i];
        if (!other) break;
        if (other == root) continue;
        if (other->leaf_distance < leaf_distance_min) leaf_distance_min = other->leaf_distance;
        if (other->leaf_distance > leaf_distance_max) leaf_distance_max = other->leaf_distance;
    }

    int stride = leaf_distance_max - leaf_distance_min;
    if (stride > max_hierarchy_distance) return;


    // Okay let's actually do it...


//    sanity_check(seam);

    // @Memory: We are allocating a lot of extra memory that gets unused
    // for these seams, potentially.  Of course it'll get freed when we
    // delete them or save the database.  But still, maybe we want to
    // think about shrinking them or being more careful somehow.
    Mesh_Seam *result_seam_a = new Mesh_Seam(seam->num_faces * 2);
    Mesh_Seam *result_seam_b = new Mesh_Seam(seam->num_faces * 2);
    result_seam_a->num_faces = 0;
    result_seam_b->num_faces = 0;

    rewrite_block_membership(seam, result_seam_a, root, block_a);
    rewrite_block_membership(seam, result_seam_b, root, block_b);

    for (i = 0; i < seam->num_faces; i++) {

        int num_a_indices = 0;
        int num_b_indices = 0;
        int num_c_indices = 0;

        Seam_Index tmp_indices_a[3];
        Seam_Index tmp_indices_b[3];
        Seam_Index tmp_indices[3];
        int orig_index[3];
        World_Block *blocks[3];
        Chopped_Result *results[3];
        Mesh_Seam *dest_seams[3];

        Vertex_Specifier *spec_a[3], *spec_b[3], *spec_c[3];

        int k;
        for (k = 0; k < 3; k++) {
            spec_a[k] = spec_b[k] = spec_c[k] = NULL;
        }

        int n0, n1, n2;
        n0 = -1;

        int j;