Method InternSubdivide

code/Common/Subdivision.cpp:225–587

------------------------------------------------------------------------------------------------ Note - this is an implementation of the standard (recursive) Cm-Cl algorithm without further optimizations (except we're using some nice LUTs). A description of the algorithm can be found here: http://en.wikipedia.org/wiki/Catmull-Clark_subdivision_surface The code is mostly O(n), however parts are O(

// Previous data is replaced/deleted then.
// ------------------------------------------------------------------------------------------------
void CatmullClarkSubdivider::InternSubdivide(
        const aiMesh *const *smesh,
        size_t nmesh,
        aiMesh **out,
        unsigned int num) {
    ai_assert(nullptr != smesh);
    ai_assert(nullptr != out);

    INIT_EDGE_HASH_TEMPORARIES();

    // no subdivision requested or end of recursive refinement
    if (!num) {
        return;
    }

    UIntVector maptbl;
    SpatialSort spatial;

    // ---------------------------------------------------------------------
    // 0. Offset table to index all meshes continuously, generate a spatially
    // sorted representation of all vertices in all meshes.
    // ---------------------------------------------------------------------
    typedef std::pair<unsigned int, unsigned int> IntPair;
    std::vector<IntPair> moffsets(nmesh);
    unsigned int totfaces = 0, totvert = 0;
    for (size_t t = 0; t < nmesh; ++t) {
        const aiMesh *mesh = smesh[t];

        spatial.Append(mesh->mVertices, mesh->mNumVertices, sizeof(aiVector3D), false);
        moffsets[t] = IntPair(totfaces, totvert);

        totfaces += mesh->mNumFaces;
        totvert += mesh->mNumVertices;
    }

    spatial.Finalize();
    const unsigned int num_unique = spatial.GenerateMappingTable(maptbl, ComputePositionEpsilon(smesh, nmesh));

#define FLATTEN_VERTEX_IDX(mesh_idx, vert_idx) (moffsets[mesh_idx].second + vert_idx)
#define FLATTEN_FACE_IDX(mesh_idx, face_idx) (moffsets[mesh_idx].first + face_idx)

    // ---------------------------------------------------------------------
    // 1. Compute the centroid point for all faces
    // ---------------------------------------------------------------------
    std::vector<Vertex> centroids(totfaces);
    unsigned int nfacesout = 0;
    for (size_t t = 0, n = 0; t < nmesh; ++t) {
        const aiMesh *mesh = smesh[t];
        for (unsigned int i = 0; i < mesh->mNumFaces; ++i, ++n) {
            const aiFace &face = mesh->mFaces[i];
            Vertex &c = centroids[n];

            for (unsigned int a = 0; a < face.mNumIndices; ++a) {
                c += Vertex(mesh, face.mIndices[a]);
            }

            c /= static_cast<float>(face.mNumIndices);
            nfacesout += face.mNumIndices;