renderer/src/sk_rectanizer_skyline.cpp

/*
 * Copyright 2013 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 *
 * Initial import from
 * skia:b4171f5ba83048039097bbc664eaa076190f6239@src/gpu/RectanizerSkyline.cpp
 *
 * Copyright 2025 Rive
 */

#include "rive/renderer/sk_rectanizer_skyline.hpp"

#include <algorithm>
#include <cassert>

namespace skgpu
{

bool RectanizerSkyline::addRect(int width, int height, int16_t* x, int16_t* y)
{
    if ((unsigned)width > (unsigned)this->width() ||
        (unsigned)height > (unsigned)this->height())
    {
        return false;
    }

    // find position for new rectangle
    int bestWidth = this->width() + 1;
    int bestX = 0;
    int bestY = this->height() + 1;
    int bestIndex = -1;
    for (int i = 0; i < fSkyline.size(); ++i)
    {
        int y;
        if (this->rectangleFits(i, width, height, &y))
        {
            // minimize y position first, then width of skyline
            if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth))
            {
                bestIndex = i;
                bestWidth = fSkyline[i].fWidth;
                bestX = fSkyline[i].fX;
                bestY = y;
            }
        }
    }

    // add rectangle to skyline
    if (-1 != bestIndex)
    {
        this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
        *x = bestX;
        *y = bestY;

        fAreaSoFar += width * height;
        return true;
    }

    *x = 0;
    *y = 0;
    return false;
}

bool RectanizerSkyline::rectangleFits(int skylineIndex,
                                      int width,
                                      int height,
                                      int* ypos) const
{
    int x = fSkyline[skylineIndex].fX;
    if (x + width > this->width())
    {
        return false;
    }

    int widthLeft = width;
    int i = skylineIndex;
    int y = fSkyline[skylineIndex].fY;
    while (widthLeft > 0)
    {
        y = std::max(y, fSkyline[i].fY);
        if (y + height > this->height())
        {
            return false;
        }
        widthLeft -= fSkyline[i].fWidth;
        ++i;
        assert(i < fSkyline.size() || widthLeft <= 0);
    }

    *ypos = y;
    return true;
}

void RectanizerSkyline::addSkylineLevel(int skylineIndex,
                                        int x,
                                        int y,
                                        int width,
                                        int height)
{
    SkylineSegment& newSegment =
        *fSkyline.emplace(fSkyline.begin() + skylineIndex);
    newSegment.fX = x;
    newSegment.fY = y + height;
    newSegment.fWidth = width;

    assert(newSegment.fX + newSegment.fWidth <= this->width());
    assert(newSegment.fY <= this->height());

    // delete width of the new skyline segment from following ones
    for (int i = skylineIndex + 1; i < fSkyline.size(); ++i)
    {
        // The new segment subsumes all or part of fSkyline[i]
        assert(fSkyline[i - 1].fX <= fSkyline[i].fX);

        if (fSkyline[i].fX < fSkyline[i - 1].fX + fSkyline[i - 1].fWidth)
        {
            int shrink =
                fSkyline[i - 1].fX + fSkyline[i - 1].fWidth - fSkyline[i].fX;

            fSkyline[i].fX += shrink;
            fSkyline[i].fWidth -= shrink;

            if (fSkyline[i].fWidth <= 0)
            {
                // fully consumed
                fSkyline.erase(fSkyline.begin() + i);
                --i;
            }
            else
            {
                // only partially consumed
                break;
            }
        }
        else
        {
            break;
        }
    }

    // merge fSkylines
    for (int i = 0; i < fSkyline.size() - 1; ++i)
    {
        if (fSkyline[i].fY == fSkyline[i + 1].fY)
        {
            fSkyline[i].fWidth += fSkyline[i + 1].fWidth;
            fSkyline.erase(fSkyline.begin() + i + 1);
            --i;
        }
    }
}

} // End of namespace skgpu