Drawing Large Numbers of Triangles Efficiently

[hypnotix]

   I have these concave shapes, most of which have more than 500 points. After dividing and storing each shape in its own array of triangles (std::vector<sf::ConvexShape>), I proceed to draw them one by one. As you've no doubt guessed, it doesn't happen very quickly, dropping frame rates from around 1200 to less than 100 (frame rate in the top right corner).



The thing is, the machine I'm running it on is somewhat high-end, so the program runs even worse on older PCs, dipping below 20 on computers made before 2011, for example.
   My question is the following, how can this be improved on to avoid these lag spikes and improve performance?

[eXpl0it3r]

Run it through a profiler and find out what the bottleneck is.

With a minimal and compilable example, we can't really tell you anything.

[shadowmouse]

I would suggest going to the tutorials section and looking at vertex arrays rather than using a vector of triangle and iterating through each one as it is my understanding that vertex array allows you to draw it all with one draw call, which would speed up your program if the slowness isn't caused by a different bottleneck.

[Nexus]

After dividing and storing each shape in its own array of triangles (std::vector<sf::ConvexShape>)

Did you do that manually?

I'd just like to let you know that I've written a class thor::ConcaveShape which does exactly that. If you require an offline convex representation, you can still use the underlying triangulation algorithm directly, with thor::triangulate() and its variants.

Other than that, I agree with the other answers: vertex arrays are probably the best bet in your case. But to be sure whether drawing is the actual (and only) bottleneck I would use a profiler.

[hypnotix]

First off, thanks for the quick response.
After running it through a profiler, the program spends 89.02 % of the time in this function, 62.1 % of which on the "if" line:

void region::drawRegions(std::vector<region>*& regions, sf::RenderWindow& window)
{
        window.setView(worldView);
        sf::Vector2f viewCenter = worldView.getCenter();
        for (std::vector<region>::iterator i = regions->begin(); i != regions->end(); ++i)
        {
                for (std::vector<sf::ConvexShape>::iterator j = i->_region.begin(); j != i->_region.end(); ++j)
                {
                        sf::FloatRect buffer = j->getGlobalBounds();
            //This checks if the object is within the visible area (monitor)
                        if (buffer.left + buffer.width >= viewCenter.x - viewWidth / 2.00 && buffer.left <= viewCenter.x + viewWidth / 2.00 && buffer.top + buffer.height >= worldViewTopBounds && buffer.top <= worldViewBottomBounds)window.draw(*j);
                }
        }
}

Thus my next question would be, how would I go about turning this vector of triangles into an sf::VertexArray?
@Nexus, I did write those functions myself, didn't know what you posted was available. I'll have to check it out.

[Nexus]

Yes, so it looks like the draw() call takes up the majority of the time.
(The few comparisons in the if are definitely negligible, but it would be good to write those statements on different lines in any case.)

You can use sf::VertexArray with the sf::Triangles primitive.

Note that thor::ConcaveShape already uses vertex arrays internally, and it will be much easier to transition from your current sf::ConvexShape implementation, as both classes have a very similar API. One little thing to keep in mind is that there's still one vertex array per concave shape; but if there are only a few dozens of concave shapes in total, that should not be a problem. You could use the master branch of Thor, or one of eXpl0it3r's nightly builds. If you need help setting things up, just tell me

[Jesper Juhl]

void region::drawRegions(std::vector<region>*& regions, sf::RenderWindow& window)
 

Why the reference to a pointer? Also, you don't modify regions, so make it const. I'd say "const std::vector<region>& regions" should do the trick.

{
        window.setView(worldView);
        sf::Vector2f viewCenter = worldView.getCenter();
 

I'd make the variable const since you use it as a constant.

        for (std::vector<region>::iterator i = regions->begin(); i != regions->end(); ++i)
        {
                for (std::vector<sf::ConvexShape>::iterator j = i->_region.begin(); j != i->_region.end(); ++j)
 

Why not use range-based for loops here? They are potentially faster (only evaluate end() once and modern compilers try hard to vectorize them) and they are certainly a lot easier to read.

                {
                        sf::FloatRect buffer = j->getGlobalBounds();
 

const?

Personally I'd probably rewrite the function roughly like this:

void region::drawRegions(const std::vector<region>& regions, sf::RenderWindow& window)
{
    window.setView(worldView);
    const auto viewCenter = worldView.getCenter();
    for (const auto& region : regions) {
        for (const auto polygon& : region) {
            const auto buffer = polygon.getGlobalBounds();
            //This checks if the object is within the visible area (monitor)
            if (buffer.left + buffer.width >= viewCenter.x - viewWidth / 2.00 &&
                buffer.left <= viewCenter.x + viewWidth / 2.00 &&
                buffer.top + buffer.height >= worldViewTopBounds &&
                buffer.top <= worldViewBottomBounds) {
                window.draw(*j);
            }
        }
    }
}

But, as others have said, a solution involving VertexArray will probably perform better. Just wanted to provide some feedback/suggestions

[hypnotix]

Thanks, everyone, for your input. Having redone it hastily a moment ago so as to see the difference with Vertex Arrays, I must say it is staggering - frame rates stay within the 1200 - 1400 range throughout.
@Jesper Juhl Thank you, I'll look over your remarks in the morning.