Method earclip

src/IO/OBJParser.cpp:359–475

}

OBJParser::FaceList OBJParser::earclip(const std::vector<size_t>& idx) {
    // This method implements the naive ear clipping algorithm with complexity
    // O(n^2).  It may be slow for large n.
    assert(idx.size() > 3);
    using List = std::list<size_t>;
    using Iterator = List::iterator;
    FaceList tris;
    List active_idx;
    const size_t num_idx = idx.size();
    for (size_t i=0; i<num_idx; i++) {
        active_idx.push_back(i);
    }

    auto cyclic_next = [&active_idx](Iterator itr) {
        itr++;
        if (itr == active_idx.end()) itr = active_idx.begin();
        return itr;
    };
    auto cyclic_prev = [&active_idx](Iterator itr) {
        if (itr == active_idx.begin()) {
            itr = active_idx.end();
        }
        itr--;
        return itr;
    };
    auto estimate_normal = [this, &idx]() {
        const size_t num_idx = idx.size();
        assert(num_idx > 0);
        Vector3F n(0.0, 0.0, 0.0);
        Vector3F seed;
        seed.segment(0, m_dim) = m_vertices[idx[0]];
        for (size_t i=0; i<num_idx-1; i++) {
            Vector3F vi,vj;
            vi.segment(0, m_dim) = m_vertices[idx[i]];
            vj.segment(0, m_dim) = m_vertices[idx[i+1]];
            n += (vi - seed).cross(vj - seed);
        }
        n.normalize();
        return n;
    };
    auto can_clip = [this, &idx, &cyclic_prev, &cyclic_next](const Iterator& itr, const Vector3F& normal) {
        const auto curr = itr;
        const auto next = cyclic_next(itr);
        const auto prev = cyclic_prev(itr);
        const size_t i = idx[*prev];
        const size_t j = idx[*curr];
        const size_t k = idx[*next];
        Vector3F vi,vj,vk;
        vi.segment(0, m_dim) = m_vertices[i];
        vj.segment(0, m_dim) = m_vertices[j];
        vk.segment(0, m_dim) = m_vertices[k];
        const Vector3F nj = (vk-vj).cross(vi-vj);
        if (nj.norm() <= 0.0) return false; // Degenerate ear.
        if (nj.dot(normal) <= 0.0) return false; // Concave face.
        for (Iterator itr = cyclic_next(next); itr != prev; itr=cyclic_next(itr)) {
            const size_t l = idx[*itr];
            const size_t m = idx[*cyclic_next(itr)];
            Vector3F vl,vm;