Method buildTree

source/bvh.cpp:731–810

three stages to BVH construction

// three stages to BVH construction
void BoundingVolumeHierarchy::buildTree(const hmesh_t& mesh_,
    const fixed_precision_number_t& enlargementEps_,
    uint32_t mp_,
    const SplitMethod& sm_)
{
    SCOPED_TIMER(__FUNCTION__);
    mesh = &(mesh_); ///
    MCUT_ASSERT(mesh->number_of_faces() >= 1);
    maxPrimsInNode = (std::min(255u, mp_)); //
    splitMethod = (sm_); //
    enlargementEps = (enlargementEps_);

    buildData.clear();
    primitives.clear();
    primitiveOrderedBBoxes.clear();
    nodes.clear();

    // First, bounding information about each primitive is computed and stored in an array
    // that will be used during tree construction.

    // initialize buildData array for primitives

    buildData.reserve(mesh->number_of_faces());

    primitiveOrderedBBoxes.resize(mesh->number_of_faces());
    primitives.resize(mesh->number_of_faces());

    // TODO make this parallel
    // for each face in mesh
    for (face_array_iterator_t f = mesh->faces_begin(); f != mesh->faces_end(); ++f) {
        const int i = static_cast<int>(*f);
        primitives[i] = *f;

        const std::vector<vd_t> vertices_on_face = mesh->get_vertices_around_face(*f);

        bounding_box_t<vec3> bbox;
        // for each vertex on face
        for (std::vector<vd_t>::const_iterator v = vertices_on_face.cbegin(); v != vertices_on_face.cend(); ++v) {
            const vec3 coords = mesh->vertex(*v);
            bbox.expand(coords);
        }

        if (enlargementEps > 0.0) {
            bbox.enlarge(enlargementEps);
        }

        primitiveOrderedBBoxes[i] = bbox;

        buildData.push_back(BVHPrimitiveInfo(i, primitiveOrderedBBoxes[i]));
    }

    // Next, the tree is built via a procedure that splits the primitives into subsets and
    // recursively builds BVHs for the subsets. The result is a binary tree where each
    // interior node holds pointers to its children and each leaf node holds references to
    // one or more primitives.

    uint32_t totalNodes = 0;
    std::vector<fd_t> orderedPrims;