getTriangleGroup is pretty intense

[m-7761]

This is used all over the place to loop over every triangle in the model.

However triangles are stored they should have group IDs in their data.

int Model::getTriangleGroup(unsigned triangleNumber)const
{
    for(unsigned g = 0; g<m_groups.size(); g++)
    {
        Group *grp = m_groups[g];
        if(grp->m_triangleIndices.end()
              !=grp->m_triangleIndices.find(triangleNumber))
        {
            return g;
        }
    }

    // Triangle is not in a group
    return -1;
}

[m-7761]

Note, m_triangleIndices is std::set<int>, so it's not a linear search (nonlinear complexity.) I've changed it to unordered_set, which should be much better. I stumbled on this at the end of my day. I don't think I noticed "find" was used at all.

When I switched to unordered_set I looked over use cases of m_triangleIndices to determine conclusively that it doesn't require ordered iteration. It was the only case that wasn't trivial.

I think this is still bad, and that since the triangle objects are huge, I don't see a reason to not put some more data in them, but it's not as bad as my initial thought. I looked at it and just thought... every triangle, over every group, over every triangle in said group... and naturally (or not) rushed to the worst possible judgement.

Note, https://github.com/zturtleman/mm3d/issues/54 deals with this point of order obliquely. I'm going to see what the file-format situation is like. When checking for selected triangles it would make sense to iterate over the selection list, but it's not always used this way. I think the Model class should keep more information on its selection state in general. Looping over entire models should be avoided. Especially if it's to facilitate larger models.

[m-7761]

adjustTriangleIndices is a case where this model fails... it's death on undo... every triangle is pulled out one-by-one and this work-intensive operation is performed.

Apparently the central triangles list (m_triangles) used to be "std::list" going by removeTriangle, but it's currently a vector. That API counts over the triangles one-by-one.

This is unacceptable. It's pretty snappy in the installed program... probably because it's built without STL bound-checking.

void Model::adjustTriangleIndices(unsigned index, int count)
{
    for(unsigned g = 0; g<m_groups.size(); g++)
    {
        Group *grp = m_groups[g];
        std::unordered_set<int> newSet;
        for(auto it = grp->m_triangleIndices.cbegin();
                it!=grp->m_triangleIndices.cend();
                ++it)
        {
            if((unsigned)*it>=index)
                newSet.insert(*it+count);
            else
                newSet.insert(*it);
        }
        grp->m_triangleIndices.swap(newSet);
    }
}

EDITED: If not stored this way, triangles can be removed by swapping with the back of the vector, and popping. It doesn't keep order, but it's unclear if order is important. If indices must be adjusted, it's better to reassign one than drop all by one.

[m-7761]

Update: I suppose order must be preserved if the undo/redo system uses indices... looking at adjustTriangleIndices and adjustVertexIndices (unless there be bugs) it's easy to see that only groups index triangles, and only triangles index vertices... in which case it should be pretty simple to reorganize.

A fundamental problem I see is the undo/redo objects keep lists that they iterate over to operate on via Model methods that operate in isolation on single elements. That's fundamentally stupid since the procedures almost always do huge global loop heavy things that could be done once instead of thousands of times. Consider this example:

void MU_AddTriangle::undo(Model *model)
{
    log_debug("undo add triangle\n");

    AddTriangleList::reverse_iterator it;
    for(it = m_list.rbegin(); it!=m_list.rend(); it++)
    {
        model->removeTriangle((*it).index);
    }
}

removeTriangle here adjusts the indices (adjustTriangleIndices) every time, instead of doing it batch, and adjusting only at the end. It's magical thinking. I don't get why programmers do this kind of thing. I see it all the time.

Furthermore Model has loads of methods... and the "protected" ones can't even be distinguished from the "public" ones. It would make perfect sense to implement the utilities in terms of these undo/redo objects. Then the technical infrastructure would be removed from the Model class, so it could function as a friendly facade for the user.

It seems like probably I will have to tear down and rebuild the Model class. I think this code base is no good as is. After a rewrite it could have a second life... if anyone finds it. Unfortunately programmers have awful instincts, both when it comes to writing code, and selecting code off the shelf.

[m-7761]

Update: Immediate term I've changed m_triangleIndices to use vector and tried to optimize for using push_back and changed getGroupTriangles to return the vector by reference instead of copying. (I ran across adjustTriangleIndices again and just felt like copying the set (unordered_set or not) was prohibitive just to adjust those indices.)