[osg-users] code for merging tri strips in a cache friendly way

[Christian Buchner]

When loading .obj files (e.g. exported from Blender) into OSG - especially
those that are exported with the "group by material" option - you might
find a lot of individual tri strips in the resulting OSG geometry.

Here is a piece of code (a node visitor) that will join these tri strips
into a single large strip, taking into account cache locality aspects: The
tri strips are sorted by their median vertex index before joining. This can
be useful to improve the performance of hardware instancing.

Some C++11 language features may be used in the code (range based for and
others). Feel free to modify/use/improve on this code.

Christian

/**
 * A visitor that merges triangle strip drawables by creating some
degenerate triangles.
 */
class TriStripMergeVisitor : public osg::NodeVisitor
{
public:

    TriStripMergeVisitor():
        osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN) {}

    virtual void apply(osg::Node& node)
    {
        traverse(node);
    }

    virtual void apply(osg::Geode& node)
    {
        for(unsigned int i=0;i<node.getNumDrawables();++i)
        {
            osg::Drawable* drawable = node.getDrawable(i);
            if (drawable) apply(*drawable);
        }

        traverse(node);
    }

    virtual void apply(osg::Drawable& drawable)
    {
        osg::Geometry *geo = dynamic_cast<osg::Geometry*>(&drawable);
        if (geo != NULL) apply(*geo);
    }

    virtual void apply(osg::Geometry& geometry)
    {
        osg::Geometry::PrimitiveSetList &psl =
geometry.getPrimitiveSetList();

        // count the number of tri strips
        int num_tristrips = 0;
        unsigned int total_indices = 0;
        std::vector< std::pair<std::vector<unsigned int>, unsigned int> >
tristrips;
        bool first = true;
        for (auto &ps : psl)
        {
            osg::DrawElements *de =
dynamic_cast<osg::DrawElements*>(ps.get());
            if (de != NULL)
            {
                if (de->getMode() == osg::PrimitiveSet::TRIANGLE_STRIP)
                {
                    num_tristrips++;
                    std::vector<unsigned int> indices;
                    unsigned int num_indices = de->getNumIndices();
                    if (!first) total_indices += 2;
                    total_indices += num_indices;
                    indices.reserve(num_indices);
                    for (unsigned int i=0; i < num_indices; i++)
indices.push_back(de->index(i));

                    std::vector<unsigned int> sorted_indices(indices);
                    std::sort(sorted_indices.begin(), sorted_indices.end());
                    int median_index =
sorted_indices[sorted_indices.size()/2];
                    tristrips.emplace_back(indices, median_index);
                    first = false;
                }
            }
        }

        // merge all tri-strips in a cache-friendly manner
        if (num_tristrips >= 2)
        {
            std::sort(tristrips.begin(), tristrips.end(),
[](std::pair<std::vector<unsigned int>, unsigned int> &a,
std::pair<std::vector<unsigned int>, unsigned int> &b) {
                return b.second > a.second;
            });

            std::vector< unsigned int > joined_tristrips;
            joined_tristrips.reserve(total_indices);
            first = true;
            for (auto ts : tristrips)
            {
                if (!first)
                {
                    joined_tristrips.push_back(joined_tristrips.back());
                    joined_tristrips.push_back(ts.first.front());
                }
                joined_tristrips.insert(joined_tristrips.end(),
ts.first.begin(), ts.first.end());

                first = false;
            }

            unsigned int max_element =
*std::max_element(joined_tristrips.begin(), joined_tristrips.end());
            osg::ref_ptr<osg::DrawElements> new_de;
            if (max_element < 256)        new_de = new
osg::DrawElementsUByte(osg::PrimitiveSet::TRIANGLE_STRIP,
joined_tristrips.size());
            else if (max_element < 65536) new_de = new
osg::DrawElementsUShort(osg::PrimitiveSet::TRIANGLE_STRIP,
joined_tristrips.size());
            else                          new_de = new
osg::DrawElementsUInt(osg::PrimitiveSet::TRIANGLE_STRIP,
joined_tristrips.size());
            for (unsigned int i=0; i < joined_tristrips.size(); i++)
                new_de->setElement(i, joined_tristrips[i]);

            osg::Geometry::PrimitiveSetList new_psl;
            new_psl.push_back(new_de);

            // append all non tri strip geometry
            for (auto &ps : psl)
            {
                osg::DrawElements *de =
dynamic_cast<osg::DrawElements*>(ps.get());
                if (!(de != NULL && de->getMode() ==
osg::PrimitiveSet::TRIANGLE_STRIP))
                     new_psl.push_back(ps);
            }

            geometry.setPrimitiveSetList(new_psl);
        }
    }
};
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20170103/1b3863e9/attachment-0002.htm>