KisRectsGrid Class Reference

A utility class to maintain a sparse grid of loaded/unloaded rects. More...

#include <KisRectsGrid.h>

Public Member Functions
QVector< QRect >	addAlignedRect (const QRect &rc)
QVector< QRect >	addRect (const QRect &rc)
QRect	alignRect (const QRect &rc) const
QRect	boundingRect () const
bool	contains (const QRect &rc) const
	KisRectsGrid (int gridSize=64)
QVector< QRect >	removeAlignedRect (const QRect &rc)
QVector< QRect >	removeRect (const QRect &rc)

Private Member Functions
void	resize (const QRect &newMappedAreaSize)

Static Private Member Functions
static QRect	shrinkRectToAlignedGrid (const QRect &srcRect, int lod)

Private Attributes
int	m_gridSize
int	m_logGridSize
QRect	m_mappedAreaSize
QVector< quint8 >	m_mapping

Detailed Description

A utility class to maintain a sparse grid of loaded/unloaded rects.

KisRectsGrid manages the presence of the rectangular cells in the grid covering some specific area. The main usecase of the class is to maintain an overlay device over another paint device.

When you need to ensure that the overlay has some particular rect loaded, you just call grid->addRect(rect) and get a list of rects that have not yet been loaded into the overlay. The returned list may be empty if all the grid cells intersecting rect has already been loaded (added to the grid).

The size of the cell is defined at the construction stage and must be power of 2.

Definition at line 30 of file KisRectsGrid.h.

Constructor & Destructor Documentation

KisRectsGrid()

KisRectsGrid::KisRectsGrid

(

int

gridSize = 64

)

Create a grid with cell size set to gridSize

Definition at line 18 of file KisRectsGrid.cpp.

    : m_gridSize(gridSize)
    , m_logGridSize(qFloor(std::log2(gridSize)))
{
    if (!qFuzzyCompare(std::log2(gridSize), qreal(m_logGridSize))) {
        KisUsageLogger::log(QString("Invalid grid configuration. Grid size: %1, log grid size: %2. Resetting to 64 and 6").arg(gridSize, m_logGridSize));
        m_gridSize = 64;
        m_logGridSize = 6;
    }
}

References KisUsageLogger::log(), m_gridSize, m_logGridSize, and qFuzzyCompare().

Member Function Documentation

addAlignedRect()

QVector< QRect > KisRectsGrid::addAlignedRect

(

const QRect &

rc

)

Add an aligned rect to the grid

The grid will form a list of cells that intersect rc and have not not yet been loaded, mark them as loaded and return the list to the caller.

Parameters

rc	the rect to be added, the rect must be aligned

Returns

the list of cells that has actually been changed

Definition at line 62 of file KisRectsGrid.cpp.

{
    if (rc.isEmpty()) return QVector<QRect>();
 
    const QRect mappedRect = KisLodTransformBase::scaledRect(rc, m_logGridSize);
 
    if (!m_mappedAreaSize.contains(mappedRect)) {
        QRect nextMappingSize = m_mappedAreaSize | mappedRect;
        nextMappingSize = KisAlgebra2D::blowRect(nextMappingSize, 0.2);
        resize(nextMappingSize);
    }
 
    QVector<QRect> addedRects;
 
    for (int y = mappedRect.y(); y <= mappedRect.bottom(); y++) {
        for (int x = mappedRect.x(); x <= mappedRect.right(); x++) {
            quint8 *ptr = &m_mapping[m_mappedAreaSize.width() * (y - m_mappedAreaSize.y()) + (x - m_mappedAreaSize.x())];
            if (!*ptr) {
                *ptr = 1;
                addedRects.append(KisLodTransformBase::upscaledRect(QRect(x, y, 1, 1), m_logGridSize));
            }
        }
    }
    return addedRects;
}

References KisAlgebra2D::blowRect(), m_logGridSize, m_mappedAreaSize, m_mapping, resize(), KisLodTransformBase::scaledRect(), and KisLodTransformBase::upscaledRect().

addRect()

QVector< QRect > KisRectsGrid::addRect

(

const QRect &

rc

)

Add an arbitrary (non-aligned) rect to the grid

The grid will form a list of cells that intersect rc and have not not yet been loaded, mark them as loaded and return the list to the caller.

Parameters

rc	the rect to be added, not necessary aligned to the grid

Returns

the list of cells that has actually been changed

Definition at line 57 of file KisRectsGrid.cpp.

{
    return addAlignedRect(alignRect(rc));
}

References addAlignedRect(), and alignRect().

alignRect()

QRect KisRectsGrid::alignRect

(

const QRect &

rc

)

const

Grow rectangle rc until it becomes aligned to the grid cell borders.

Definition at line 52 of file KisRectsGrid.cpp.

{
    return KisLodTransformBase::alignedRect(rc, m_logGridSize);
}

References KisLodTransformBase::alignedRect(), and m_logGridSize.

boundingRect()

QRect KisRectsGrid::boundingRect

(

)

const

Return the bounding box of the loaded cells of the grid

Definition at line 160 of file KisRectsGrid.cpp.

                                       {
    QRect gridBounds;
 
    for (int y = m_mappedAreaSize.y(); y <= m_mappedAreaSize.bottom(); y++) {
        for (int x = m_mappedAreaSize.x(); x <= m_mappedAreaSize.right(); x++) {
            gridBounds |= QRect(x, y, 1, 1);
        }
    }
 
    return KisLodTransformBase::upscaledRect(gridBounds, m_logGridSize);
}

References m_logGridSize, m_mappedAreaSize, and KisLodTransformBase::upscaledRect().

contains()

bool KisRectsGrid::contains

(

const QRect &

rc

)

const

Return is rc is fully covered by the loaded cells of the grid

Definition at line 144 of file KisRectsGrid.cpp.

{
    const QRect mappedRect = KisLodTransformBase::scaledRect(alignRect(rc), m_logGridSize);
 
    if (!m_mappedAreaSize.contains(mappedRect)) return false;
 
    for (int y = mappedRect.y(); y <= mappedRect.bottom(); y++) {
        for (int x = mappedRect.x(); x <= mappedRect.right(); x++) {
            const quint8 *ptr = &m_mapping[m_mappedAreaSize.width() * (y - m_mappedAreaSize.y()) + (x - m_mappedAreaSize.x())];
            if (!*ptr) return false;
        }
    }
 
    return true;
}

References alignRect(), m_logGridSize, m_mappedAreaSize, m_mapping, and KisLodTransformBase::scaledRect().

removeAlignedRect()

QVector< QRect > KisRectsGrid::removeAlignedRect

(

const QRect &

rc

)

Remove an aligned rect from the grid

The grid will form a list of loaded cells that are fully contained in rc, mark them as unloaded and return the list to the caller.

Parameters

rc	the rect to be removed, not necessary aligned to the grid

Returns

the list of cells that has actually been changed

Definition at line 123 of file KisRectsGrid.cpp.

{
    const QRect mappedRect = KisLodTransformBase::scaledRect(rc, m_logGridSize);
 
    // NOTE: we never shrink the size of the grid, just keep it as big as
    //       it ever was
 
    QVector<QRect> removedRects;
 
    for (int y = mappedRect.y(); y <= mappedRect.bottom(); y++) {
        for (int x = mappedRect.x(); x <= mappedRect.right(); x++) {
            quint8 *ptr = &m_mapping[m_mappedAreaSize.width() * (y - m_mappedAreaSize.y()) + (x - m_mappedAreaSize.x())];
            if (*ptr) {
                *ptr = 0;
                removedRects.append(KisLodTransformBase::upscaledRect(QRect(x, y, 1, 1), m_logGridSize));
            }
        }
    }
    return removedRects;
}

References m_logGridSize, m_mappedAreaSize, m_mapping, KisLodTransformBase::scaledRect(), and KisLodTransformBase::upscaledRect().

removeRect()

QVector< QRect > KisRectsGrid::removeRect

(

const QRect &

rc

)

Remove an arbitrary (non-aligned) rect from the grid

The grid will form a list of loaded cells that are fully contained in rc, mark them as unloaded and return the list to the caller.

TODO: please note that removing two neighbouring non-aligned rectangles may still leave some cells marked as loaded. Perhaps we should change the meaning of this function to remove "all intersecting rectangles" instead of "all contained rectangles".

Parameters

rc	the rect to be removed, not necessary aligned to the grid

Returns

the list of cells that has actually been changed

Definition at line 117 of file KisRectsGrid.cpp.

{
    const QRect alignedRect = shrinkRectToAlignedGrid(rc, m_logGridSize);
    return !alignedRect.isEmpty() ? removeAlignedRect(alignedRect) : QVector<QRect>();
}

References m_logGridSize, removeAlignedRect(), and shrinkRectToAlignedGrid().

resize()

void KisRectsGrid::resize ( const QRect & newMappedAreaSize )

private

Definition at line 29 of file KisRectsGrid.cpp.

{
    KIS_SAFE_ASSERT_RECOVER_NOOP(m_mappedAreaSize.isEmpty() || newMappedAreaSize.contains(m_mappedAreaSize));
 
    QVector<quint8> newMapping(newMappedAreaSize.width() * newMappedAreaSize.height());
 
    const int xDiff = m_mappedAreaSize.x() - newMappedAreaSize.x();
    const int yDiff = m_mappedAreaSize.y() - newMappedAreaSize.y();
 
    int dstRowStride = newMappedAreaSize.width();
    int dstRowStart = xDiff + yDiff * dstRowStride;
 
    for (int y = 0; y < m_mappedAreaSize.height(); y++) {
        int dstRowIndex = dstRowStart + dstRowStride * y;
        int srcRowIndex = m_mappedAreaSize.width() * y;
 
        memcpy(&newMapping[dstRowIndex], &m_mapping[srcRowIndex], m_mappedAreaSize.width());
    }
 
    std::swap(newMapping, m_mapping);
    m_mappedAreaSize = newMappedAreaSize;
}

References KIS_SAFE_ASSERT_RECOVER_NOOP, m_mappedAreaSize, and m_mapping.

shrinkRectToAlignedGrid()

QRect KisRectsGrid::shrinkRectToAlignedGrid ( const QRect & srcRect, int lod )

inlinestaticprivate

Definition at line 88 of file KisRectsGrid.cpp.

{
    qint32 alignment = 1 << lod;
 
    qint32 x1, y1, x2, y2;
    srcRect.getCoords(&x1, &y1, &x2, &y2);
 
    x1--;
    y1--;
    x2++;
    y2++;
 
    KisLodTransformBase::alignByPow2ButOneHi(x1, alignment);
    KisLodTransformBase::alignByPow2ButOneHi(y1, alignment);
 
    KisLodTransformBase::alignByPow2Lo(x2, alignment);
    KisLodTransformBase::alignByPow2Lo(y2, alignment);
 
    x1++;
    y1++;
    x2--;
    y2--;
 
    QRect rect;
    rect.setCoords(x1, y1, x2, y2);
 
    return rect;
}

References KisLodTransformBase::alignByPow2ButOneHi(), and KisLodTransformBase::alignByPow2Lo().

Member Data Documentation

m_gridSize

int KisRectsGrid::m_gridSize

private

Definition at line 109 of file KisRectsGrid.h.

m_logGridSize

int KisRectsGrid::m_logGridSize

private

Definition at line 110 of file KisRectsGrid.h.

m_mappedAreaSize

QRect KisRectsGrid::m_mappedAreaSize

private

Definition at line 112 of file KisRectsGrid.h.

m_mapping

QVector<quint8> KisRectsGrid::m_mapping

private

Definition at line 111 of file KisRectsGrid.h.

---

The documentation for this class was generated from the following files:

• libs/global/KisRectsGrid.h
• libs/global/KisRectsGrid.cpp