KisScanlineFill Class Reference

#include <kis_scanline_fill.h>

Inheritance diagram for KisScanlineFill:

Public Types
template<class T >
using	GreaterPriorityQueue = std::priority_queue<T, std::vector<T>, std::greater<T>>

Public Member Functions
void	clearNonZeroComponent ()
void	fill (const KoColor &fillColor)
void	fill (const KoColor &fillColor, KisPaintDeviceSP externalDevice)
void	fillContiguousGroup (KisPaintDeviceSP groupMapDevice, qint32 groupIndex)
QRect	fillExtent () const
void	fillSelection (KisPixelSelectionSP pixelSelection)
void	fillSelection (KisPixelSelectionSP pixelSelection, KisPaintDeviceSP boundarySelection)
void	fillSelectionUntilColor (KisPixelSelectionSP pixelSelection, const KoColor &boundaryColor)
void	fillSelectionUntilColor (KisPixelSelectionSP pixelSelection, const KoColor &boundaryColor, KisPaintDeviceSP boundarySelection)
void	fillSelectionUntilColorOrTransparent (KisPixelSelectionSP pixelSelection, const KoColor &boundaryColor)
void	fillSelectionUntilColorOrTransparent (KisPixelSelectionSP pixelSelection, const KoColor &boundaryColor, KisPaintDeviceSP boundarySelection)
void	fillUntilColor (const KoColor &fillColor, const KoColor &boundaryColor)
void	fillUntilColor (const KoColor &fillColor, const KoColor &boundaryColor, KisPaintDeviceSP externalDevice)
	KisScanlineFill (KisPaintDeviceSP device, const QPoint &startPoint, const QRect &boundingRect)
void	setCloseGap (int closeGap)
void	setOpacitySpread (int opacitySpread)
void	setThreshold (int threshold)
void	swapDirection ()
	~KisScanlineFill ()
Public Member Functions inherited from Private
	Private (KisCanvas2 *c)

Public Attributes
KisFillIntervalMap	backwardMap
QRect	boundingRect
int	closeGap
	try to close gaps up to this size in pixels
GreaterPriorityQueue< CloseGapFillPoint >	closeGapQueue
KisPaintDeviceSP	device
KisRandomAccessorSP	filledSelectionIterator
QRect	fillExtent
QStack< KisFillInterval >	forwardStack
KisGapMapSP	gapMapSp
	maintains the distance and opacity maps required for the algorithm
int	opacitySpread
int	rowIncrement
QPoint	startPoint
int	threshold
Public Attributes inherited from Private
KisCanvas2 *	canvas
int	displayedFrame
int	intendedFrame

Private Member Functions
template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >
KisFillInterval	closeGapPass (DifferencePolicy &differencePolicy, SelectionPolicy &selectionPolicy, PixelAccessPolicy &pixelAccessPolicy)
template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >
void	extendedPass (KisFillInterval *currentInterval, int srcRow, bool extendRight, DifferencePolicy &differencePolicy, SelectionPolicy &selectionPolicy, PixelAccessPolicy &pixelAccessPolicy)
template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >
bool	fillOpacity (DifferencePolicy &differencePolicy, SelectionPolicy &selectionPolicy, PixelAccessPolicy &pixelAccessPolicy, KisPaintDevice *const devicePtr, const QRect &rect) const
template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >
void	processLine (KisFillInterval interval, const int rowIncrement, DifferencePolicy &differencePolicy, SelectionPolicy &selectionPolicy, PixelAccessPolicy &pixelAccessPolicy)
template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >
void	runImpl (DifferencePolicy &differencePolicy, SelectionPolicy &selectionPolicy, PixelAccessPolicy &pixelAccessPolicy)
template<template< typename SrcPixelType > typename OptimizedDifferencePolicy, typename SlowDifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >
void	selectDifferencePolicyAndRun (const KoColor &srcColor, SelectionPolicy &selectionPolicy, PixelAccessPolicy &pixelAccessPolicy)
KisFillIntervalMap *	testingGetBackwardIntervals () const
QVector< KisFillInterval >	testingGetForwardIntervals () const
void	testingProcessLine (const KisFillInterval &processInterval)
bool	tryPushingCloseGapSeed (int x, int y, bool allowExpand)

Private Attributes
const QScopedPointer< Private >	m_d

Friends
class	KisScanlineFillTest

Detailed Description

Definition at line 277 of file kis_scanline_fill.cpp.

Member Typedef Documentation

GreaterPriorityQueue

template<class T >

using KisScanlineFill::GreaterPriorityQueue = std::priority_queue<T, std::vector<T>, std::greater<T>>

Definition at line 297 of file kis_scanline_fill.cpp.

Constructor & Destructor Documentation

KisScanlineFill()

KisScanlineFill::KisScanlineFill	(	KisPaintDeviceSP	device,
		const QPoint &	startPoint,
		const QRect &	boundingRect )

Definition at line 317 of file kis_scanline_fill.cpp.

    : m_d(new Private)
{
    m_d->device = device;
    m_d->startPoint = startPoint;
    m_d->boundingRect = boundingRect;
 
    m_d->rowIncrement = 1;
 
    m_d->threshold = 0;
    m_d->opacitySpread = 0;
    m_d->closeGap = 0;
}

References boundingRect, device, m_d, and startPoint.

~KisScanlineFill()

KisScanlineFill::~KisScanlineFill

(

)

Definition at line 331 of file kis_scanline_fill.cpp.

{
}

Member Function Documentation

clearNonZeroComponent()

void KisScanlineFill::clearNonZeroComponent

(

)

Clear the contiguous non-zero area of the device

WARNING: the threshold parameter is not counted!

Definition at line 1003 of file kis_scanline_fill.cpp.

{
    const int pixelSize = m_d->device->pixelSize();
    KoColor srcColor = KoColor::createTransparent(m_d->device->colorSpace());
 
    using namespace KisColorSelectionPolicies;
    
    FillWithColorPixelAccessPolicy pap(m_d->device, srcColor);
    SelectionPolicy<HardSelectionPolicy> sp(HardSelectionPolicy(m_d->threshold));
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = m_d->device->createRandomAccessorNG();
    }
 
    if (pixelSize == 1) {
        OptimizedIsNonNullDifferencePolicy<quint8> dp;
        runImpl(dp, sp, pap);
    } else if (pixelSize == 2) {
        OptimizedIsNonNullDifferencePolicy<quint16> dp;
        runImpl(dp, sp, pap);
    } else if (pixelSize == 4) {
        OptimizedIsNonNullDifferencePolicy<quint32> dp;
        runImpl(dp, sp, pap);
    } else if (pixelSize == 8) {
        OptimizedIsNonNullDifferencePolicy<quint64> dp;
        runImpl(dp, sp, pap);
    } else {
        SlowIsNonNullDifferencePolicy dp(pixelSize);
        runImpl(dp, sp, pap);
    }
}

References KoColor::createTransparent(), m_d, and runImpl().

closeGapPass()

template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >

KisFillInterval KisScanlineFill::closeGapPass ( DifferencePolicy & differencePolicy, SelectionPolicy & selectionPolicy, PixelAccessPolicy & pixelAccessPolicy )

private

Definition at line 529 of file kis_scanline_fill.cpp.

{
    KisFillInterval interval;
 
    while (!m_d->closeGapQueue.empty()) {
        const CloseGapFillPoint p = m_d->closeGapQueue.top();
        m_d->closeGapQueue.pop();
 
        // KisGapMap enforces x/y start at (0, 0).
        if ((p.x < 0) || (p.x >= m_d->boundingRect.width()) || (p.y < 0) || (p.y >= m_d->boundingRect.height())) {
            continue;
        }
 
        pixelAccessPolicy.m_srcIt->moveTo(p.x, p.y);
        quint8 *pixelPtr = const_cast<quint8*>(pixelAccessPolicy.m_srcIt->rawDataConst());
        const quint8 difference = differencePolicy.difference(pixelPtr);
        const quint8 opacity = selectionPolicy.opacityFromDifference(difference, p.x, p.y);
 
        // The initial pixel (before the fill) is non-opaque, so we try to fill it.
        if (opacity) {
            // However, check if it has already been filled during the ongoing operation.
            // If the test below is true, then the pixel is already in the selection.
            m_d->filledSelectionIterator->moveTo(p.x, p.y);
            if (*m_d->filledSelectionIterator->rawDataConst() == opacity) {
                continue;
            }
 
            const quint32 previousDistance = p.distance;
            const quint32 distance = m_d->gapMapSp->distance(p.x, p.y);
            const bool allowExpand = p.allowExpand && (distance >= previousDistance);
            const float relativeDiff = static_cast<float>(distance) / previousDistance;
 
            // This ratio determines whether the fill can spread to pixels with
            // a different gap distance compared to the previous pixel.
            //
            // <1.0 is a pixel closer to a gap, or more in a corner of lineart.
            // =1.0 is the same distance.
            // >1.0 is a pixel that is farther from a gap, or away from tight corners.
            //
            // At high gap sizes, the distance map can vary slightly and the fill could
            // leave out empty pixels. To prevent that, we allow spilling to a more distant
            // pixels as well, up to a given tolerance. If the value is too high,
            // the fill will spill too much.
 
            static constexpr float SpreadTolerance = 1.3f;
 
            if ((relativeDiff < SpreadTolerance) || allowExpand) {
                if (distance == KisGapMap::DISTANCE_INFINITE) {
                    // Only return one interval at a time. Otherwise, just skip this pixel.
                    if (!interval.isValid()) {
                        interval.start = p.x;
                        interval.end = p.x;
                        interval.row = p.y;
                    }
                    // We still continue the loop, to process all the pixels we can fill.
                } else {
                    pixelAccessPolicy.fillPixel(pixelPtr, opacity, p.x, p.y);
                    m_d->fillExtent = m_d->fillExtent.united(QRect(p.x, p.y, 1, 1));
 
                    // Forward the context information to the next pixels.
                    // Spread the fill in four directions: up, down, left, right.
 
                    CloseGapFillPoint next;
                    next.distance = distance;
                    next.allowExpand = allowExpand;
 
                    next.x = p.x - 1;
                    next.y = p.y;
                    m_d->closeGapQueue.push(next);
 
                    next.x = p.x + 1;
                    next.y = p.y;
                    m_d->closeGapQueue.push(next);
 
                    next.x = p.x;
                    next.y = p.y - 1;
                    m_d->closeGapQueue.push(next);
 
                    next.x = p.x;
                    next.y = p.y + 1;
                    m_d->closeGapQueue.push(next);
                }
            }
        }
    }
 
    // If valid, the scanline fill will take over next.
    return interval;
}

References distance(), KisGapMap::DISTANCE_INFINITE, KisFillInterval::end, KisFillInterval::isValid(), m_d, p, KisFillInterval::row, and KisFillInterval::start.

extendedPass()

template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >

void KisScanlineFill::extendedPass ( KisFillInterval * currentInterval, int srcRow, bool extendRight, DifferencePolicy & differencePolicy, SelectionPolicy & selectionPolicy, PixelAccessPolicy & pixelAccessPolicy )

private

Definition at line 392 of file kis_scanline_fill.cpp.

{
    int x;
    int endX;
    int columnIncrement;
    int *intervalBorder;
    int *backwardIntervalBorder;
    KisFillInterval backwardInterval(currentInterval->start, currentInterval->end, srcRow);
 
    if (extendRight) {
        x = currentInterval->end;
        endX = m_d->boundingRect.right();
        if (x >= endX) return;
        columnIncrement = 1;
        intervalBorder = &currentInterval->end;
 
        backwardInterval.start = currentInterval->end + 1;
        backwardIntervalBorder = &backwardInterval.end;
    } else {
        x = currentInterval->start;
        endX = m_d->boundingRect.left();
        if (x <= endX) return;
        columnIncrement = -1;
        intervalBorder = &currentInterval->start;
 
        backwardInterval.end = currentInterval->start - 1;
        backwardIntervalBorder = &backwardInterval.start;
    }
 
    do {
        x += columnIncrement;
 
        pixelAccessPolicy.m_srcIt->moveTo(x, srcRow);
        quint8 *pixelPtr = const_cast<quint8*>(pixelAccessPolicy.m_srcIt->rawDataConst()); // TODO: avoid doing const_cast
        const quint8 difference = differencePolicy.difference(pixelPtr);
        const quint8 opacity = selectionPolicy.opacityFromDifference(difference, x, srcRow);
        const bool stopOnGap = tryPushingCloseGapSeed(x, srcRow, false);
 
        if (!stopOnGap && opacity) {
            *intervalBorder = x;
            *backwardIntervalBorder = x;
            pixelAccessPolicy.fillPixel(pixelPtr, opacity, x, srcRow);
            if (extendRight) {
                m_d->fillExtent.setRight(qMax(m_d->fillExtent.right(), x));
            } else {
                m_d->fillExtent.setLeft(qMin(m_d->fillExtent.left(), x));
            }
        } else {
            break;
        }
    } while (x != endX);
 
    if (backwardInterval.isValid()) {
        m_d->backwardMap.insertInterval(backwardInterval);
    }
}

References KisFillInterval::end, KisFillInterval::isValid(), m_d, KisFillInterval::start, and tryPushingCloseGapSeed().

fill() [1/2]

void KisScanlineFill::fill

(

const KoColor &

fillColor

)

Fill the source device with fillColor

Definition at line 773 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(m_d->device->pixel(m_d->startPoint));
    KoColor fillColor(originalFillColor);
    fillColor.convertTo(m_d->device->colorSpace());
 
    using namespace KisColorSelectionPolicies;
 
    SelectionPolicy<HardSelectionPolicy> sp(HardSelectionPolicy(m_d->threshold));
    FillWithColorPixelAccessPolicy pap(m_d->device, fillColor);
 
    selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                (srcColor, sp, pap);
}

References KoColor::convertTo(), and m_d.

fill() [2/2]

void KisScanlineFill::fill	(	const KoColor &	fillColor,
		KisPaintDeviceSP	externalDevice )

Fill externalDevice with fillColor basing on the contents of the source device.

Definition at line 804 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(m_d->device->pixel(m_d->startPoint));
    KoColor fillColor(originalFillColor);
    fillColor.convertTo(m_d->device->colorSpace());
 
    using namespace KisColorSelectionPolicies;
 
    SelectionPolicy<HardSelectionPolicy> sp(HardSelectionPolicy(m_d->threshold));
    FillWithColorExternalPixelAccessPolicy pap(m_d->device, fillColor, externalDevice);
 
    selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                (srcColor, sp, pap);
}

References KoColor::convertTo(), and m_d.

fillContiguousGroup()

void KisScanlineFill::fillContiguousGroup	(	KisPaintDeviceSP	groupMapDevice,
		qint32	groupIndex )

A special filler algorithm for the Watershed initialization routine:

1) Clear the contiguous area in the destination device 2) At the same time, fill the corresponding area of groupMapDevice with value groupIndex 3) groupMapDevice must store 4 bytes per pixel

Definition at line 1035 of file kis_scanline_fill.cpp.

{
    KIS_SAFE_ASSERT_RECOVER_RETURN(m_d->device->pixelSize() == 1);
    KIS_SAFE_ASSERT_RECOVER_RETURN(groupMapDevice->pixelSize() == 4);
 
    const quint8 referenceValue = *m_d->device->pixel(m_d->startPoint).data();
 
    using namespace KisColorSelectionPolicies;
 
    GroupSplitDifferencePolicy dp(referenceValue);
    GroupSplitSelectionPolicy sp(m_d->threshold);
    GroupSplitPixelAccessPolicy pap(m_d->device, groupMapDevice, groupIndex);
 
    runImpl(dp, sp, pap);
}

References KIS_SAFE_ASSERT_RECOVER_RETURN, m_d, KisPaintDevice::pixelSize(), and runImpl().

fillExtent()

QRect KisScanlineFill::fillExtent

(

)

const

Returns the extent of the last filled region

fillOpacity()

template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >

bool KisScanlineFill::fillOpacity ( DifferencePolicy & differencePolicy, SelectionPolicy & selectionPolicy, PixelAccessPolicy & pixelAccessPolicy, KisPaintDevice *const devicePtr, const QRect & rect ) const

private

This opacity-only fill is used by KisGapMap.

Using the same policies as the main fill, load the opacity values for a rect of the main filled region. The rect typically corresponds to a tile of an opacity map maintained by KisGapMap, and is loaded on-demand during an ongoing runImpl() loop.

Definition at line 1060 of file kis_scanline_fill.cpp.

{
#if 0
    // These asserts affect the performance.
    KIS_SAFE_ASSERT_RECOVER_RETURN((m_d->boundingRect.left() == 0) && (m_d->boundingRect.top() == 0) &&
               "FATAL: The fill bounds must start at (0,0)");
    KIS_SAFE_ASSERT_RECOVER_RETURN(m_d->boundingRect.contains(rect) &&
               "FATAL: The rect is not fully inside the fill bounds");
#endif
    KisRandomAccessorSP accessor = devicePtr->createRandomAccessorNG();
 
    const int pixelSize = m_d->device->pixelSize();
    bool hasOpaquePixels = false;
 
    // We are relying on the knowledge of KisGapMap's paint device data organization.
    constexpr int OpacityOffset = 2;
 
    for (int y = rect.top(); y <= rect.bottom(); ++y) {
        int numPixelsLeft = 0;
        quint8* dataPtr;
 
        for (int x = rect.left(); x <= rect.right(); ++x) {
            if (numPixelsLeft <= 0) {
                pixelAccessPolicy.m_srcIt->moveTo(x, y);
                numPixelsLeft = pixelAccessPolicy.m_srcIt->numContiguousColumns(x) - 1;
                dataPtr = const_cast<quint8*>(pixelAccessPolicy.m_srcIt->rawDataConst());
            } else {
                numPixelsLeft--;
                dataPtr += pixelSize;
            }
 
            const quint8 difference = differencePolicy.difference(dataPtr);
            const quint8 opacity = selectionPolicy.opacityFromDifference(difference, x, y);
 
            if (opacity == MIN_SELECTED) {
                hasOpaquePixels = true;
 
                accessor->moveTo(x, y);
                quint8* outPtr = accessor->rawData() + OpacityOffset;
 
                *outPtr = opacity;
            }
        }
    }
 
    return hasOpaquePixels;
}

References KisPaintDevice::createRandomAccessorNG(), KIS_SAFE_ASSERT_RECOVER_RETURN, m_d, MIN_SELECTED, KisRandomConstAccessorNG::moveTo(), and KisBaseAccessor::rawData().

fillSelection() [1/2]

void KisScanlineFill::fillSelection

(

KisPixelSelectionSP

pixelSelection

)

Fill pixelSelection with the opacity of the contiguous area

Definition at line 862 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(m_d->device->pixel(m_d->startPoint));
 
    const int softness = 100 - m_d->opacitySpread;
 
    using namespace KisColorSelectionPolicies;
    
    CopyToSelectionPixelAccessPolicy pap(m_d->device, pixelSelection);
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = pixelSelection->createRandomAccessorNG();
    }
 
    if (softness == 0) {
        SelectionPolicy<HardSelectionPolicy> sp(HardSelectionPolicy(m_d->threshold));
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    } else {
        SelectionPolicy<SoftSelectionPolicy> sp(SoftSelectionPolicy(m_d->threshold, softness));
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    }
}

References KisPaintDevice::createRandomAccessorNG(), and m_d.

fillSelection() [2/2]

void KisScanlineFill::fillSelection	(	KisPixelSelectionSP	pixelSelection,
		KisPaintDeviceSP	boundarySelection )

Fill pixelSelection with the opacity of the contiguous area. This method uses an existing selection as boundary for the flood fill.

Definition at line 835 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(m_d->device->pixel(m_d->startPoint));
 
    const int softness = 100 - m_d->opacitySpread;
 
    using namespace KisColorSelectionPolicies;
 
    CopyToSelectionPixelAccessPolicy pap(m_d->device, pixelSelection);
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = pixelSelection->createRandomAccessorNG();
    }
 
    if (softness == 0) {
        MaskedSelectionPolicy<HardSelectionPolicy>
            sp(HardSelectionPolicy(m_d->threshold), boundarySelection);
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    } else {
        MaskedSelectionPolicy<SoftSelectionPolicy> 
            sp(SoftSelectionPolicy(m_d->threshold, softness), boundarySelection);
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    }
}

References KisPaintDevice::createRandomAccessorNG(), and m_d.

fillSelectionUntilColor() [1/2]

void KisScanlineFill::fillSelectionUntilColor	(	KisPixelSelectionSP	pixelSelection,
		const KoColor &	boundaryColor )

Fill pixelSelection with the opacity of the contiguous area, which encompass all the connected pixels as long as the color in the pixels of the source device is not similar to boundaryColor.

Definition at line 915 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(boundaryColor);
    srcColor.convertTo(m_d->device->colorSpace());
 
    const int softness = 100 - m_d->opacitySpread;
 
    using namespace KisColorSelectionPolicies;
    
    CopyToSelectionPixelAccessPolicy pap(m_d->device, pixelSelection);
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = pixelSelection->createRandomAccessorNG();
    }
 
    if (softness == 0) {
        SelectionPolicy<SelectAllUntilColorHardSelectionPolicy>
            sp(SelectAllUntilColorHardSelectionPolicy(m_d->threshold));
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    } else {
        SelectionPolicy<SelectAllUntilColorSoftSelectionPolicy> 
            sp(SelectAllUntilColorSoftSelectionPolicy(m_d->threshold, softness));
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    }
}

References KoColor::convertTo(), KisPaintDevice::createRandomAccessorNG(), and m_d.

fillSelectionUntilColor() [2/2]

void KisScanlineFill::fillSelectionUntilColor	(	KisPixelSelectionSP	pixelSelection,
		const KoColor &	boundaryColor,
		KisPaintDeviceSP	boundarySelection )

Fill pixelSelection with the opacity of the contiguous area, which encompass all the connected pixels as long as the color in the pixels of the source device is not similar to boundaryColor. This method uses an existing selection as boundary for the flood fill.

Definition at line 887 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(boundaryColor);
    srcColor.convertTo(m_d->device->colorSpace());
 
    const int softness = 100 - m_d->opacitySpread;
 
    using namespace KisColorSelectionPolicies;
    
    CopyToSelectionPixelAccessPolicy pap(m_d->device, pixelSelection);
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = pixelSelection->createRandomAccessorNG();
    }
 
    if (softness == 0) {
        MaskedSelectionPolicy<SelectAllUntilColorHardSelectionPolicy>
            sp(SelectAllUntilColorHardSelectionPolicy(m_d->threshold), boundarySelection);
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    } else {
        MaskedSelectionPolicy<SelectAllUntilColorSoftSelectionPolicy> 
            sp(SelectAllUntilColorSoftSelectionPolicy(m_d->threshold, softness), boundarySelection);
        selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                    (srcColor, sp, pap);
    }
}

References KoColor::convertTo(), KisPaintDevice::createRandomAccessorNG(), and m_d.

fillSelectionUntilColorOrTransparent() [1/2]

void KisScanlineFill::fillSelectionUntilColorOrTransparent	(	KisPixelSelectionSP	pixelSelection,
		const KoColor &	boundaryColor )

Fill pixelSelection with the opacity of the contiguous area, which encompass all the connected pixels as long as the color in the pixels of the source device is not similar to boundaryColor or transparent.

Definition at line 973 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(boundaryColor);
    srcColor.convertTo(m_d->device->colorSpace());
 
    const int softness = 100 - m_d->opacitySpread;
 
    using namespace KisColorSelectionPolicies;
    
    CopyToSelectionPixelAccessPolicy pap(m_d->device, pixelSelection);
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = pixelSelection->createRandomAccessorNG();
    }
 
    if (softness == 0) {
        SelectionPolicy<SelectAllUntilColorHardSelectionPolicy>
            sp(SelectAllUntilColorHardSelectionPolicy(m_d->threshold));
        selectDifferencePolicyAndRun<OptimizedColorOrTransparentDifferencePolicy,
                                     SlowColorOrTransparentDifferencePolicy>
                                    (srcColor, sp, pap);
    } else {
        SelectionPolicy<SelectAllUntilColorSoftSelectionPolicy> 
            sp(SelectAllUntilColorSoftSelectionPolicy(m_d->threshold, softness));
        selectDifferencePolicyAndRun<OptimizedColorOrTransparentDifferencePolicy,
                                     SlowColorOrTransparentDifferencePolicy>
                                    (srcColor, sp, pap);
    }
}

References KoColor::convertTo(), KisPaintDevice::createRandomAccessorNG(), m_d, and selectDifferencePolicyAndRun().

fillSelectionUntilColorOrTransparent() [2/2]

void KisScanlineFill::fillSelectionUntilColorOrTransparent	(	KisPixelSelectionSP	pixelSelection,
		const KoColor &	boundaryColor,
		KisPaintDeviceSP	boundarySelection )

Fill pixelSelection with the opacity of the contiguous area, which encompass all the connected pixels as long as the color in the pixels of the source device is not similar to boundaryColor or transparent. This method uses an existing selection as boundary for the flood fill.

Definition at line 943 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(boundaryColor);
    srcColor.convertTo(m_d->device->colorSpace());
 
    const int softness = 100 - m_d->opacitySpread;
 
    using namespace KisColorSelectionPolicies;
    
    CopyToSelectionPixelAccessPolicy pap(m_d->device, pixelSelection);
 
    if (m_d->closeGap > 0) {
        m_d->filledSelectionIterator = pixelSelection->createRandomAccessorNG();
    }
 
    if (softness == 0) {
        MaskedSelectionPolicy<SelectAllUntilColorHardSelectionPolicy>
            sp(SelectAllUntilColorHardSelectionPolicy(m_d->threshold), boundarySelection);
        selectDifferencePolicyAndRun<OptimizedColorOrTransparentDifferencePolicy,
                                     SlowColorOrTransparentDifferencePolicy>
                                    (srcColor, sp, pap);
    } else {
        MaskedSelectionPolicy<SelectAllUntilColorSoftSelectionPolicy> 
            sp(SelectAllUntilColorSoftSelectionPolicy(m_d->threshold, softness), boundarySelection);
        selectDifferencePolicyAndRun<OptimizedColorOrTransparentDifferencePolicy,
                                     SlowColorOrTransparentDifferencePolicy>
                                    (srcColor, sp, pap);
    }
}

References KoColor::convertTo(), KisPaintDevice::createRandomAccessorNG(), m_d, and selectDifferencePolicyAndRun().

fillUntilColor() [1/2]

void KisScanlineFill::fillUntilColor	(	const KoColor &	fillColor,
		const KoColor &	boundaryColor )

Fill the source device with fillColor until boundaryColor is reached

Definition at line 788 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(boundaryColor);
    srcColor.convertTo(m_d->device->colorSpace());
    KoColor fillColor(originalFillColor);
    fillColor.convertTo(m_d->device->colorSpace());
 
    using namespace KisColorSelectionPolicies;
    
    SelectionPolicy<SelectAllUntilColorHardSelectionPolicy> sp(SelectAllUntilColorHardSelectionPolicy(m_d->threshold));
    FillWithColorPixelAccessPolicy pap(m_d->device, fillColor);
 
    selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                (srcColor, sp, pap);
}

References KoColor::convertTo(), and m_d.

fillUntilColor() [2/2]

void KisScanlineFill::fillUntilColor	(	const KoColor &	fillColor,
		const KoColor &	boundaryColor,
		KisPaintDeviceSP	externalDevice )

Fill externalDevice with fillColor basing on the contents of the source device. Fills until boundaryColor is reached

Definition at line 819 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(boundaryColor);
    srcColor.convertTo(m_d->device->colorSpace());
    KoColor fillColor(originalFillColor);
    fillColor.convertTo(m_d->device->colorSpace());
 
    using namespace KisColorSelectionPolicies;
 
    SelectionPolicy<SelectAllUntilColorHardSelectionPolicy> sp(SelectAllUntilColorHardSelectionPolicy(m_d->threshold));
    FillWithColorExternalPixelAccessPolicy pap(m_d->device, fillColor, externalDevice);
 
    selectDifferencePolicyAndRun<OptimizedDifferencePolicy, SlowDifferencePolicy>
                                (srcColor, sp, pap);
}

References KoColor::convertTo(), and m_d.

processLine()

template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >

void KisScanlineFill::processLine ( KisFillInterval interval, const int rowIncrement, DifferencePolicy & differencePolicy, SelectionPolicy & selectionPolicy, PixelAccessPolicy & pixelAccessPolicy )

private

Definition at line 453 of file kis_scanline_fill.cpp.

{
    m_d->backwardMap.cropInterval(&interval);
 
    if (!interval.isValid()) return;
 
    int firstX = interval.start;
    int lastX = interval.end;
    int x = firstX;
    int row = interval.row;
    int nextRow = row + rowIncrement;
 
    KisFillInterval currentForwardInterval;
 
    int numPixelsLeft = 0;
    quint8 *dataPtr = 0;
    const int pixelSize = m_d->device->pixelSize();
 
    while(x <= lastX) {
        // a bit of optimization for not calling slow random accessor
        // methods too often
        if (numPixelsLeft <= 0) {
            pixelAccessPolicy.m_srcIt->moveTo(x, row);
            numPixelsLeft = pixelAccessPolicy.m_srcIt->numContiguousColumns(x) - 1;
            dataPtr = const_cast<quint8*>(pixelAccessPolicy.m_srcIt->rawDataConst());
        } else {
            numPixelsLeft--;
            dataPtr += pixelSize;
        }
 
        quint8 *pixelPtr = dataPtr;
        const quint8 difference = differencePolicy.difference(pixelPtr);
        const quint8 opacity = selectionPolicy.opacityFromDifference(difference, x, row);
        const bool stopOnGap = tryPushingCloseGapSeed(x, row, false);
 
        if (!stopOnGap && opacity) {
            if (!currentForwardInterval.isValid()) {
                currentForwardInterval.start = x;
                currentForwardInterval.end = x;
                currentForwardInterval.row = nextRow;
            } else {
                currentForwardInterval.end = x;
            }
 
            pixelAccessPolicy.fillPixel(pixelPtr, opacity, x, row);
            m_d->fillExtent = m_d->fillExtent.united(QRect(x, row, 1, 1));
 
            if (x == firstX) {
                extendedPass(&currentForwardInterval, row, false,
                             differencePolicy, selectionPolicy, pixelAccessPolicy);
            }
 
            if (x == lastX) {
                extendedPass(&currentForwardInterval, row, true,
                             differencePolicy, selectionPolicy, pixelAccessPolicy);
            }
 
        } else {
            if (currentForwardInterval.isValid()) {
                m_d->forwardStack.push(currentForwardInterval);
                currentForwardInterval.invalidate();
            }
        }
 
        x++;
    }
 
    if (currentForwardInterval.isValid()) {
        m_d->forwardStack.push(currentForwardInterval);
    }
}

References KisFillInterval::end, extendedPass(), KisFillInterval::invalidate(), KisFillInterval::isValid(), m_d, KisFillInterval::row, rowIncrement, KisFillInterval::start, and tryPushingCloseGapSeed().

runImpl()

template<typename DifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >

void KisScanlineFill::runImpl ( DifferencePolicy & differencePolicy, SelectionPolicy & selectionPolicy, PixelAccessPolicy & pixelAccessPolicy )

private

In the end of the first pass we should add an interval containing the starting pixel, but directed into the opposite direction. We cannot do it in the very beginning because the intervals are offset by 1 pixel during every swap operation.

Definition at line 622 of file kis_scanline_fill.cpp.

{
    KIS_ASSERT_RECOVER_RETURN(m_d->forwardStack.isEmpty());
 
    int gapSize = m_d->closeGap;
    KIS_SAFE_ASSERT_RECOVER(gapSize == 0 || (gapSize > 0 && m_d->filledSelectionIterator)) {
        gapSize = 0;
    }
 
#if MEASURE_FILL_TIME
    QElapsedTimer timerTotal;
    QElapsedTimer timerScanlineFill;
    QElapsedTimer timerGapClosingFill;
    quint64 totalScanlineFillNanos = 0;
    quint64 totalGapClosingFillNanos = 0;
 
    timerTotal.start();
#endif
 
    if (gapSize > 0) {
        // We need to reuse the complex policies used by this class and only provide the final
        // "projection" of opacity for the distance map calculation.
        auto opacityFunc = [&](KisPaintDevice* devicePtr, const QRect& rect) {
            return fillOpacity(differencePolicy, selectionPolicy, pixelAccessPolicy, devicePtr, rect);
        };
 
        // Prime the resources. The computations are made lazily, when distance at a pixel is requested.
        // Resources are freed automatically when the object is destroyed, that is together with the KisScanlineFill object.
        m_d->gapMapSp = KisGapMapSP(new KisGapMap(gapSize, m_d->boundingRect, opacityFunc));
    }
 
    m_d->fillExtent = QRect();
 
    KisFillInterval startInterval(m_d->startPoint.x(), m_d->startPoint.x(), m_d->startPoint.y());
 
    // Decide if we should start with a scanline fill or a gap closing fill.
    if (!tryPushingCloseGapSeed(startInterval.start, startInterval.row, true)) {
        m_d->forwardStack.push(startInterval);
    }
 
    // The outer loop is to continue scanline filling after a gap closing fill.
    do {
        bool firstPass = true;
 
#if MEASURE_FILL_TIME
        timerScanlineFill.start();
#endif
 
        // The scanline fill can only fill the pixels that are "in the open",
        // that is have DISTANCE_INFINITE. Gap pixels will be pushed to
        // the gap closing fill's queue.
 
        while (!m_d->forwardStack.isEmpty()) {
            while (!m_d->forwardStack.isEmpty()) {
                KisFillInterval interval = m_d->forwardStack.pop();
 
                if (interval.row > m_d->boundingRect.bottom() ||
                    interval.row < m_d->boundingRect.top()) {
 
                    continue;
                }
 
                processLine(interval, m_d->rowIncrement, differencePolicy, selectionPolicy, pixelAccessPolicy);
            }
            m_d->swapDirection();
 
            if (firstPass) {
                startInterval.row--;
                m_d->forwardStack.push(startInterval);
                firstPass = false;
            }
        }
 
#if MEASURE_FILL_TIME
        totalScanlineFillNanos += timerScanlineFill.nsecsElapsed();
        timerGapClosingFill.start();
#endif
 
        // Perform a gap closing pass. This pass can in turn feed the scanline fill's
        // forward stack. It can only fiill pixels with distance < DISTANCE_INFINITE.
        // This way, both passes complement each other to complete the fill.
 
        if (!m_d->closeGapQueue.empty()) {
            startInterval = closeGapPass(differencePolicy, selectionPolicy, pixelAccessPolicy);
            if (startInterval.isValid()) {
                m_d->forwardStack.push(startInterval);
            }
        }
 
#if MEASURE_FILL_TIME
        totalGapClosingFillNanos += timerGapClosingFill.nsecsElapsed();
#endif
    } while (!m_d->forwardStack.isEmpty());
 
#if MEASURE_FILL_TIME
    static constexpr quint64 MillisDivisor = 1000000ull;
    const quint64 totalTime = timerTotal.nsecsElapsed();
    const quint64 overheadTime = (totalTime - totalScanlineFillNanos - totalGapClosingFillNanos);
    qDebug() << "init overhead =" << qSetRealNumberPrecision(3)
              << static_cast<double>(overheadTime) / MillisDivisor << "ms ("
              << static_cast<double>(overheadTime) / totalTime << ")";
    qDebug() << "fill (scanline) =" << (totalScanlineFillNanos / MillisDivisor) << "ms ("
             << qSetRealNumberPrecision(3) << static_cast<double>(totalScanlineFillNanos) / totalTime << ")";
    qDebug() << "fill (gap) =" << (totalGapClosingFillNanos / MillisDivisor) << "ms ("
             << qSetRealNumberPrecision(3) << static_cast<double>(totalGapClosingFillNanos) / totalTime << ")";
    qDebug() << "fill total =" << (totalTime / MillisDivisor) << "ms";
#if KIS_GAP_MAP_MEASURE_ELAPSED_TIME
    if (gapSize > 0) {
        qDebug() << "incl. opacity load" << m_d->gapMapSp->opacityElapsedMillis() << "ms";
        qDebug() << "incl. distance load" << m_d->gapMapSp->distanceElapsedMillis() << "ms";
    }
#endif
    qDebug() << "----------------------------------------";
#endif
}

References closeGapPass(), fillOpacity(), KisFillInterval::isValid(), KIS_ASSERT_RECOVER_RETURN, KIS_SAFE_ASSERT_RECOVER, m_d, processLine(), KisFillInterval::row, KisFillInterval::start, and tryPushingCloseGapSeed().

selectDifferencePolicyAndRun()

template<template< typename SrcPixelType > typename OptimizedDifferencePolicy, typename SlowDifferencePolicy , typename SelectionPolicy , typename PixelAccessPolicy >

void KisScanlineFill::selectDifferencePolicyAndRun ( const KoColor & srcColor, SelectionPolicy & selectionPolicy, PixelAccessPolicy & pixelAccessPolicy )

private

Definition at line 749 of file kis_scanline_fill.cpp.

{
    const int pixelSize = srcColor.colorSpace()->pixelSize();
 
    if (pixelSize == 1) {
        OptimizedDifferencePolicy<quint8> dp(srcColor, m_d->threshold);
        runImpl(dp, selectionPolicy, pixelAccessPolicy);
    } else if (pixelSize == 2) {
        OptimizedDifferencePolicy<quint16> dp(srcColor, m_d->threshold);
        runImpl(dp, selectionPolicy, pixelAccessPolicy);
    } else if (pixelSize == 4) {
        OptimizedDifferencePolicy<quint32> dp(srcColor, m_d->threshold);
        runImpl(dp, selectionPolicy, pixelAccessPolicy);
    } else if (pixelSize == 8) {
        OptimizedDifferencePolicy<quint64> dp(srcColor, m_d->threshold);
        runImpl(dp, selectionPolicy, pixelAccessPolicy);
    } else {
        SlowDifferencePolicy dp(srcColor, m_d->threshold);
        runImpl(dp, selectionPolicy, pixelAccessPolicy);
    }
}

References KoColor::colorSpace(), m_d, KoColorSpace::pixelSize(), and runImpl().

setCloseGap()

void KisScanlineFill::setCloseGap

(

int

closeGap

)

Set the close gap size in pixels for the flood fill. The value 0 behaves like a regular fill. Values 1 and larger will cause a gap map to be computed for the area and then used for the fill. The gaps are small areas of non-opaque pixels that are roughly not larger than the selected gap size. If such a gap is detected, the fill will stop spreading beyond that area.

Definition at line 345 of file kis_scanline_fill.cpp.

{
    m_d->closeGap = closeGap;
}

References closeGap, and m_d.

setOpacitySpread()

void KisScanlineFill::setOpacitySpread

(

int

opacitySpread

)

Set the opacity spread for floodfill. The range is 0-100: 0% means that the fully opaque area only encompasses the pixels exactly equal to the seed point with the other pixels of the selected region being semi-transparent (depending on how similar they are to the seed pixel) up to the region boundary (given by the threshold value). 100 means that the fully opaque area will encompass all the pixels of the selected region up to the contour. Any value in between will make the fully opaque portion of the region vary in size, with semi-transparent pixels in between it and the region boundary

Definition at line 340 of file kis_scanline_fill.cpp.

{
    m_d->opacitySpread = opacitySpread;
}

References m_d, and opacitySpread.

setThreshold()

void KisScanlineFill::setThreshold

(

int

threshold

)

Set the threshold of the filling operation

Used in all functions except clearNonZeroComponent()

Definition at line 335 of file kis_scanline_fill.cpp.

{
    m_d->threshold = threshold;
}

References m_d, and threshold.

swapDirection()

void KisScanlineFill::swapDirection ( )

inline

Definition at line 305 of file kis_scanline_fill.cpp.

                                {
        rowIncrement *= -1;
        KIS_SAFE_ASSERT_RECOVER_NOOP(forwardStack.isEmpty() &&
                                     "FATAL: the forward stack must be empty "
                                     "on a direction swap");
 
        forwardStack = QStack<KisFillInterval>(backwardMap.fetchAllIntervals(rowIncrement));
        backwardMap.clear();
    }

References KisFillIntervalMap::clear(), KisFillIntervalMap::fetchAllIntervals(), and KIS_SAFE_ASSERT_RECOVER_NOOP.

testingGetBackwardIntervals()

KisFillIntervalMap * KisScanlineFill::testingGetBackwardIntervals ( ) const

private

Definition at line 1131 of file kis_scanline_fill.cpp.

{
    return &m_d->backwardMap;
}

References m_d.

testingGetForwardIntervals()

QVector< KisFillInterval > KisScanlineFill::testingGetForwardIntervals ( ) const

private

Definition at line 1126 of file kis_scanline_fill.cpp.

{
    return QVector<KisFillInterval>(m_d->forwardStack);
}

References m_d.

testingProcessLine()

void KisScanlineFill::testingProcessLine ( const KisFillInterval & processInterval )

private

Definition at line 1112 of file kis_scanline_fill.cpp.

{
    KoColor srcColor(QColor(0,0,0,0), m_d->device->colorSpace());
    KoColor fillColor(QColor(200,200,200,200), m_d->device->colorSpace());
 
    using namespace KisColorSelectionPolicies;
 
    OptimizedDifferencePolicy<quint32> dp(srcColor, m_d->threshold);
    SelectionPolicy<HardSelectionPolicy> sp(HardSelectionPolicy(m_d->threshold));
    FillWithColorPixelAccessPolicy pap(m_d->device, fillColor);
 
    processLine(processInterval, 1, dp, sp, pap);
}

References m_d, and processLine().

tryPushingCloseGapSeed()

bool KisScanlineFill::tryPushingCloseGapSeed ( int x, int y, bool allowExpand )

inlineprivate

Used with the scanline fill algorithm.

Determine if the (x, y) pixel is near a gap (i.e., has non-INFINITE distance). All gap pixels are pushed onto the gap closing fill queue, while the scanline fill proceeds with regular pixels.

Parameters

allowExpand

is only true for the initial gap closing seed.

Returns

true if a gap closing pixel was pushed; the scanline fill must not fill this pixel.

Definition at line 368 of file kis_scanline_fill.cpp.

{
    bool pushed = false;
 
    if (m_d->gapMapSp && m_d->gapMapSp->gapSize() > 0) {
        const quint32 distance = m_d->gapMapSp->distance(x, y);
 
        if (distance != KisGapMap::DISTANCE_INFINITE) {
            pushed = true;
 
            CloseGapFillPoint seed;
            seed.x = x;
            seed.y = y;
            seed.distance = distance;
            seed.allowExpand = allowExpand;
 
            m_d->closeGapQueue.push(seed);
        }
    }
 
    return pushed;
}

References distance(), KisGapMap::DISTANCE_INFINITE, and m_d.

Friends And Related Symbol Documentation

KisScanlineFillTest

friend class KisScanlineFillTest

friend

Definition at line 141 of file kis_scanline_fill.h.

Member Data Documentation

backwardMap

KisFillIntervalMap KisScanlineFill::backwardMap

Definition at line 286 of file kis_scanline_fill.cpp.

boundingRect

QRect KisScanlineFill::boundingRect

Definition at line 281 of file kis_scanline_fill.cpp.

closeGap

int KisScanlineFill::closeGap

try to close gaps up to this size in pixels

Definition at line 289 of file kis_scanline_fill.cpp.

closeGapQueue

GreaterPriorityQueue<CloseGapFillPoint> KisScanlineFill::closeGapQueue

Definition at line 298 of file kis_scanline_fill.cpp.

device

KisPaintDeviceSP KisScanlineFill::device

Definition at line 279 of file kis_scanline_fill.cpp.

filledSelectionIterator

KisRandomAccessorSP KisScanlineFill::filledSelectionIterator

Definition at line 302 of file kis_scanline_fill.cpp.

fillExtent

QRect KisScanlineFill::fillExtent

Definition at line 292 of file kis_scanline_fill.cpp.

forwardStack

QStack<KisFillInterval> KisScanlineFill::forwardStack

Definition at line 287 of file kis_scanline_fill.cpp.

gapMapSp

KisGapMapSP KisScanlineFill::gapMapSp

maintains the distance and opacity maps required for the algorithm

Definition at line 290 of file kis_scanline_fill.cpp.

m_d

const QScopedPointer<Private> KisScanlineFill::m_d

private

Definition at line 188 of file kis_scanline_fill.h.

opacitySpread

int KisScanlineFill::opacitySpread

Definition at line 283 of file kis_scanline_fill.cpp.

rowIncrement

int KisScanlineFill::rowIncrement

Definition at line 285 of file kis_scanline_fill.cpp.

startPoint

QPoint KisScanlineFill::startPoint

Definition at line 280 of file kis_scanline_fill.cpp.

threshold

int KisScanlineFill::threshold

Definition at line 282 of file kis_scanline_fill.cpp.

---

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

• libs/image/floodfill/kis_scanline_fill.cpp
• libs/image/floodfill/kis_scanline_fill.h