Computer Shopper 275/DPCS0111DVD.ISO/Toolkit/Audio-Visual/VirtualDub/Source/VirtualDub-1.9.10-src.7z/src/Kasumi/source/region.cpp

C/C++ Source or Header | 2009-09-14 | 31.8 KB | 1,335 lines

//    VirtualDub - Video processing and capture application
//    Graphics support library
//    Copyright (C) 1998-2007 Avery Lee
//
//    This program is free software; you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation; either version 2 of the License, or
//    (at your option) any later version.
//
//    This program is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with this program; if not, write to the Free Software
//    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

#include <vd2/Kasumi/pixmap.h>
#include <vd2/Kasumi/pixmaputils.h>
#include <vd2/Kasumi/region.h>
#include <vd2/system/math.h>
#include <vd2/system/vdstl.h>

void VDPixmapRegion::swap(VDPixmapRegion& x) {
    mSpans.swap(x.mSpans);
    std::swap(mBounds, x.mBounds);
}

VDPixmapPathRasterizer::VDPixmapPathRasterizer()
    : mpEdgeBlocks(NULL)
    , mpFreeEdgeBlocks(NULL)
    , mEdgeBlockIdx(kEdgeBlockMax)
    , mpScanBuffer(NULL)
{
    ClearScanBuffer();
}

VDPixmapPathRasterizer::VDPixmapPathRasterizer(const VDPixmapPathRasterizer&)
    : mpEdgeBlocks(NULL)
    , mpFreeEdgeBlocks(NULL)
    , mEdgeBlockIdx(kEdgeBlockMax)
    , mpScanBuffer(NULL)
{
    ClearScanBuffer();
}

VDPixmapPathRasterizer::~VDPixmapPathRasterizer() {
    Clear();
    FreeEdgeLists();
}

VDPixmapPathRasterizer& VDPixmapPathRasterizer::operator=(const VDPixmapPathRasterizer&) {
    return *this;
}

void VDPixmapPathRasterizer::Clear() {
    ClearEdgeList();
    ClearScanBuffer();
}

void VDPixmapPathRasterizer::QuadraticBezier(const vdint2 *pts) {
    int x0 = pts[0].x;
    int x1 = pts[1].x;
    int x2 = pts[2].x;
    int y0 = pts[0].y;
    int y1 = pts[1].y;
    int y2 = pts[2].y;

    // P = (1-t)^2*P0 + 2t(1-t)*P1 + t^2*P2
    // P = (1-2t+t^2)P0 + 2(t-t^2)P1 + t^2*P2
    // P = (P0-2P1+P2)t^2 + 2(P1-P0)t + P0

    int cx2 =    x0-2*x1+x2;
    int cx1 = -2*x0+2*x1;
    int cx0 =    x0;

    int cy2 =    y0-2*y1+y2;
    int cy1 = -2*y0+2*y1;
    int cy0 =    y0;

    // This equation is from Graphics Gems I.
    //
    // The idea is that since we're approximating a cubic curve with lines,
    // any error we incur is due to the curvature of the line, which we can
    // estimate by calculating the maximum acceleration of the curve.  For
    // a cubic, the acceleration (second derivative) is a line, meaning that
    // the absolute maximum acceleration must occur at either the beginning
    // (|c2|) or the end (|c2+c3|).  Our bounds here are a little more
    // conservative than that, but that's okay.
    //
    // If the acceleration of the parametric formula is zero (c2 = c3 = 0),
    // that component of the curve is linear and does not incur any error.
    // If a=0 for both X and Y, the curve is a line segment and we can
    // use a step size of 1.

    int maxaccel1 = abs(cy2);
    int maxaccel2 = abs(cx2);

    int maxaccel = maxaccel1 > maxaccel2 ? maxaccel1 : maxaccel2;
    int h = 1;

    while(maxaccel > 8 && h < 1024) {
        maxaccel >>= 2;
        h += h;
    }

    int lastx = x0;
    int lasty = y0;

    // compute forward differences
    sint64 h1 = (sint64)(0x40000000 / h) << 2;
    sint64 h2 = h1/h;

    sint64 ax0 = (sint64)cx0 << 32;
    sint64 ax1 =   h1*(sint64)cx1 +   h2*(sint64)cx2;
    sint64 ax2 = 2*h2*(sint64)cx2;

    sint64 ay0 = (sint64)cy0 << 32;
    sint64 ay1 =   h1*(sint64)cy1 +   h2*(sint64)cy2;
    sint64 ay2 = 2*h2*(sint64)cy2;

    // round, not truncate
    ax0 += 0x80000000;
    ay0 += 0x80000000;

    do {
        ax0 += ax1;
        ax1 += ax2;
        ay0 += ay1;
        ay1 += ay2;

        int xi = (int)((uint64)ax0 >> 32);
        int yi = (int)((uint64)ay0 >> 32);

        FastLine(lastx, lasty, xi, yi);
        lastx = xi;
        lasty = yi;
    } while(--h);
}

void VDPixmapPathRasterizer::CubicBezier(const vdint2 *pts) {
    int x0 = pts[0].x;
    int x1 = pts[1].x;
    int x2 = pts[2].x;
    int x3 = pts[3].x;
    int y0 = pts[0].y;
    int y1 = pts[1].y;
    int y2 = pts[2].y;
    int y3 = pts[3].y;

    int cx3 = -  x0+3*x1-3*x2+x3;
    int cx2 =  3*x0-6*x1+3*x2;
    int cx1 = -3*x0+3*x1;
    int cx0 =    x0;

    int cy3 = -  y0+3*y1-3*y2+y3;
    int cy2 =  3*y0-6*y1+3*y2;
    int cy1 = -3*y0+3*y1;
    int cy0 =    y0;

    // This equation is from Graphics Gems I.
    //
    // The idea is that since we're approximating a cubic curve with lines,
    // any error we incur is due to the curvature of the line, which we can
    // estimate by calculating the maximum acceleration of the curve.  For
    // a cubic, the acceleration (second derivative) is a line, meaning that
    // the absolute maximum acceleration must occur at either the beginning
    // (|c2|) or the end (|c2+c3|).  Our bounds here are a little more
    // conservative than that, but that's okay.
    //
    // If the acceleration of the parametric formula is zero (c2 = c3 = 0),
    // that component of the curve is linear and does not incur any error.
    // If a=0 for both X and Y, the curve is a line segment and we can
    // use a step size of 1.

    int maxaccel1 = abs(2*cy2) + abs(6*cy3);
    int maxaccel2 = abs(2*cx2) + abs(6*cx3);

    int maxaccel = maxaccel1 > maxaccel2 ? maxaccel1 : maxaccel2;
    int h = 1;

    while(maxaccel > 8 && h < 1024) {
        maxaccel >>= 2;
        h += h;
    }

    int lastx = x0;
    int lasty = y0;

    // compute forward differences
    sint64 h1 = (sint64)(0x40000000 / h) << 2;
    sint64 h2 = h1/h;
    sint64 h3 = h2/h;

    sint64 ax0 = (sint64)cx0 << 32;
    sint64 ax1 =   h1*(sint64)cx1 +   h2*(sint64)cx2 + h3*(sint64)cx3;
    sint64 ax2 = 2*h2*(sint64)cx2 + 6*h3*(sint64)cx3;
    sint64 ax3 = 6*h3*(sint64)cx3;

    sint64 ay0 = (sint64)cy0 << 32;
    sint64 ay1 =   h1*(sint64)cy1 +   h2*(sint64)cy2 + h3*(sint64)cy3;
    sint64 ay2 = 2*h2*(sint64)cy2 + 6*h3*(sint64)cy3;
    sint64 ay3 = 6*h3*(sint64)cy3;

    // round, not truncate
    ax0 += 0x80000000;
    ay0 += 0x80000000;

    do {
        ax0 += ax1;
        ax1 += ax2;
        ax2 += ax3;
        ay0 += ay1;
        ay1 += ay2;
        ay2 += ay3;

        int xi = (int)((uint64)ax0 >> 32);
        int yi = (int)((uint64)ay0 >> 32);

        FastLine(lastx, lasty, xi, yi);
        lastx = xi;
        lasty = yi;
    } while(--h);
}

void VDPixmapPathRasterizer::Line(const vdint2& pt1, const vdint2& pt2) {
    FastLine(pt1.x, pt1.y, pt2.x, pt2.y);
}

void VDPixmapPathRasterizer::FastLine(int x0, int y0, int x1, int y1) {
    int flag = 1;

    if (y1 == y0)
        return;

    if (y1 < y0) {
        int t;

        t=x0; x0=x1; x1=t;
        t=y0; y0=y1; y1=t;
        flag = 0;
    }

    int dy = y1-y0;
    int xacc = x0<<13;

    // prestep y0 down
    int iy0 = (y0+3) >> 3;
    int iy1 = (y1+3) >> 3;

    if (iy0 < iy1) {
        int invslope = (x1-x0)*65536/dy;

        int prestep = (4-y0) & 7;
        xacc += (invslope * prestep)>>3;

        if (iy0 < mScanYMin || iy1 > mScanYMax) {
            ReallocateScanBuffer(iy0, iy1);
            VDASSERT(iy0 >= mScanYMin && iy1 <= mScanYMax);
        }

        while(iy0 < iy1) {
            int ix = (xacc+32767)>>16;

            if (mEdgeBlockIdx >= kEdgeBlockMax) {
                if (mpFreeEdgeBlocks) {
                    EdgeBlock *newBlock = mpFreeEdgeBlocks;
                    mpFreeEdgeBlocks = mpFreeEdgeBlocks->next;
                    newBlock->next = mpEdgeBlocks;
                    mpEdgeBlocks = newBlock;
                } else {
                    mpEdgeBlocks = new EdgeBlock(mpEdgeBlocks);
                }

                mEdgeBlockIdx = 0;
            }

            Edge& e = mpEdgeBlocks->edges[mEdgeBlockIdx];
            Scan& s = mpScanBufferBiased[iy0];
            VDASSERT(iy0 >= mScanYMin && iy0 < mScanYMax);
            ++mEdgeBlockIdx;

            e.posandflag = ix*2+flag;
            e.next = s.chain;
            s.chain = &e;
            ++s.count;

            ++iy0;
            xacc += invslope;
        }
    }
}

void VDPixmapPathRasterizer::ScanConvert(VDPixmapRegion& region) {
    // Convert the edges to spans.  We couldn't do this before because some of
    // the regions may have winding numbers >+1 and it would have been a pain
    // to try to adjust the spans on the fly.  We use one heap to detangle
    // a scanline's worth of edges from the singly-linked lists, and another
    // to collect the actual scans.
    vdfastvector<int> heap;

    region.mSpans.clear();
    int xmin = INT_MAX;
    int xmax = INT_MIN;
    int ymin = INT_MAX;
    int ymax = INT_MIN;

    for(int y=mScanYMin; y<mScanYMax; ++y) {
        uint32 flipcount = mpScanBufferBiased[y].count;

        if (!flipcount)
            continue;

        // Keep the edge heap from doing lots of stupid little reallocates.
        if (heap.capacity() < flipcount)
            heap.resize((flipcount + 63)&~63);

        // Detangle scanline into edge heap.
        int *heap0 = heap.data();
        int *heap1 = heap0;
        for(const Edge *ptr = mpScanBufferBiased[y].chain; ptr; ptr = ptr->next)
            *heap1++ = ptr->posandflag;

        VDASSERT(heap1 - heap0 == flipcount);

        // Sort edge heap.  Note that we conveniently made the opening edges
        // one more than closing edges at the same spot, so we won't have any
        // problems with abutting spans.

        std::sort(heap0, heap1);

#if 0
        while(heap0 != heap1) {
            int x = *heap0++ >> 1;
            region.mSpans.push_back((y<<16) + x + 0x80008000);
            region.mSpans.push_back((y<<16) + x + 0x80008001);
        }
        continue;
#endif

        // Trim any odd edges off, since we can never close on one.
        if (flipcount & 1)
            --heap1;

        // Process edges and add spans.  Since we only check for a non-zero
        // winding number, it doesn't matter which way the outlines go. Also, since
        // the parity always flips after each edge regardless of direction, we can
        // process the edges in pairs.

        size_t spanstart = region.mSpans.size();

        int x_left;
        int count = 0;
        while(heap0 != heap1) {
            int x = *heap0++;

            if (!count)
                x_left = (x>>1);

            count += (x&1);

            x = *heap0++;

            count += (x&1);

            if (!--count) {
                int x_right = (x>>1);

                if (x_right > x_left) {
                    region.mSpans.push_back((y<<16) + x_left  + 0x80008000);
                    region.mSpans.push_back((y<<16) + x_right + 0x80008000);

                }
            }
        }

        size_t spanend = region.mSpans.size();

        if (spanend > spanstart) {
            if (ymin > y)
                ymin = y;

            if (ymax < y)
                ymax = y;

            int x1 = (region.mSpans[spanstart] & 0xffff) - 0x8000;
            int x2 = (region.mSpans[spanend-1] & 0xffff) - 0x8000;

            if (xmin > x1)
                xmin = x1;

            if (xmax < x2)
                xmax = x2;
        }
    }

    if (xmax > xmin) {
        region.mBounds.set(xmin, ymin, xmax, ymax);
    } else {
        region.mBounds.set(0, 0, 0, 0);
    }

    // Dump the edge and scan buffers, since we no longer need them.
    ClearEdgeList();
    ClearScanBuffer();
}

void VDPixmapPathRasterizer::ClearEdgeList() {
    if (mpEdgeBlocks) {
        EdgeBlock *block = mpEdgeBlocks;

        while(EdgeBlock *next = block->next)
            block = next;

        block->next = mpFreeEdgeBlocks;
        mpFreeEdgeBlocks = mpEdgeBlocks;
        mpEdgeBlocks = NULL;
    }

    mEdgeBlockIdx = kEdgeBlockMax;
}

void VDPixmapPathRasterizer::FreeEdgeLists() {
    ClearEdgeList();

    while(EdgeBlock *block = mpFreeEdgeBlocks) {
        mpFreeEdgeBlocks = block->next;

        delete block;
    }
}

void VDPixmapPathRasterizer::ClearScanBuffer() {
    delete[] mpScanBuffer;
    mpScanBuffer = mpScanBufferBiased = NULL;
    mScanYMin = 0;
    mScanYMax = 0;
}

void VDPixmapPathRasterizer::ReallocateScanBuffer(int ymin, int ymax) {
    //
    // check if there actually is a scan buffer to avoid unintentionally pinning at zero
    if (mpScanBuffer) {
        int nicedelta = (mScanYMax - mScanYMin);

        if (ymin < mScanYMin) {
            int yminnice = mScanYMin - nicedelta;
            if (ymin > yminnice)
                ymin = yminnice;

            ymin &= ~31;
        } else
            ymin = mScanYMin;

        if (ymax > mScanYMax) {
            int ymaxnice = mScanYMax + nicedelta;
            if (ymax < ymaxnice)
                ymax = ymaxnice;

            ymax = (ymax + 31) & ~31;
        } else
            ymax = mScanYMax;

        VDASSERT(ymin <= mScanYMin && ymax >= mScanYMax);
    }

    // reallocate scan buffer
    Scan *pNewBuffer = new Scan[ymax - ymin];
    Scan *pNewBufferBiased = pNewBuffer - ymin;

    if (mpScanBuffer) {
        memcpy(pNewBufferBiased + mScanYMin, mpScanBufferBiased + mScanYMin, (mScanYMax - mScanYMin) * sizeof(Scan));
        delete[] mpScanBuffer;

        // zero new areas of scan buffer
        for(int y=ymin; y<mScanYMin; ++y) {
            pNewBufferBiased[y].chain = NULL;
            pNewBufferBiased[y].count = 0;
        }

        for(int y=mScanYMax; y<ymax; ++y) {
            pNewBufferBiased[y].chain = NULL;
            pNewBufferBiased[y].count = 0;
        }
    } else {
        for(int y=ymin; y<ymax; ++y) {
            pNewBufferBiased[y].chain = NULL;
            pNewBufferBiased[y].count = 0;
        }
    }

    mpScanBuffer = pNewBuffer;
    mpScanBufferBiased = pNewBufferBiased;
    mScanYMin = ymin;
    mScanYMax = ymax;
}

bool VDPixmapFillRegion(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
    if (dst.format != nsVDPixmap::kPixFormat_XRGB8888)
        return false;

    // fast out
    if (region.mSpans.empty())
        return true;

    // check if vertical clipping is required
    const size_t n = region.mSpans.size();
    uint32 start = 0;
    uint32 end = n;

    uint32 spanmin = (-x) + ((-y) << 16) + 0x80008000;

    if (region.mSpans.front() < spanmin) {
        uint32 lo = 0, hi = n;

        // compute top clip
        while(lo < hi) {
            int mid = ((lo + hi) >> 1) & ~1;

            if (region.mSpans[mid + 1] < spanmin)
                lo = mid + 2;
            else
                hi = mid;
        }

        start = lo;

        // check for total top clip
        if (start >= n)
            return true;
    }

    uint32 spanlimit = (dst.w - x) + ((dst.h - y - 1) << 16) + 0x80008000;

    if (region.mSpans.back() > spanlimit) {
        // compute bottom clip
        int lo = start;
        int hi = n;

        while(lo < hi) {
            int mid = ((lo + hi) >> 1) & ~1;

            if (region.mSpans[mid] >= spanlimit)
                hi = mid;
            else
                lo = mid+2;
        }

        end = lo;

        // check for total bottom clip
        if (start >= end)
            return true;
    }

    // fill region
    const uint32 *pSpan = ®ion.mSpans[start];
    const uint32 *pEnd  = ®ion.mSpans[0] + end;
    int lasty = -1;
    uint32 *dstp;

    for(; pSpan != pEnd; pSpan += 2) {
        uint32 span0 = pSpan[0];
        uint32 span1 = pSpan[1];

        uint32 py = (span0 >> 16) - 0x8000 + y;
        uint32 px = (span0 & 0xffff) - 0x8000 + x;
        uint32 w = span1-span0;

        VDASSERT(py < (uint32)dst.h);
        VDASSERT(px < (uint32)dst.w);
        VDASSERT(dst.w - (int)px >= (int)w);

        if (lasty != py)
            dstp = (uint32 *)vdptroffset(dst.data, dst.pitch * py);

        uint32 *p = dstp + px;
        do {
            *p++ = color;
        } while(--w);
    }

    return true;
}

namespace {
    void RenderABuffer32(const VDPixmap& dst, int y, const uint8 *alpha, uint32 w, uint32 color) {
        if (!w)
            return;

        // update dest pointer
        uint32 *dstp = (uint32 *)vdptroffset(dst.data, dst.pitch * y);

        const uint32 color_rb = color & 0x00FF00FF;
        const uint32 color_g  = color & 0x0000FF00;
        do {
            const uint32 px = *dstp;
            const uint32 px_rb = px & 0x00FF00FF;
            const uint32 px_g  = px & 0x0000FF00;
            const sint32 a     = *alpha++;

            const uint32 result_rb = (((px_rb << 6) + ((sint32)(color_rb - px_rb)*a + 0x00200020)) & 0x3FC03FC0);
            const uint32 result_g  = (((px_g  << 6) + ((sint32)(color_g  - px_g )*a + 0x00002000)) & 0x003FC000);

            *dstp++ = (result_rb + result_g) >> 6;
        } while(--w);
    }

    void RenderABuffer8(const VDPixmap& dst, int y, const uint8 *alpha, uint32 w, uint32 color) {
        if (!w)
            return;

        // update dest pointer
        uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);

        do {
            const uint8 px = *dstp;
            const sint8 a = *alpha++;

            *dstp++ = px + (((sint32)(color - px) * a + 32) >> 6);
        } while(--w);
    }

    void RenderABuffer8_128(const VDPixmap& dst, int y, const uint8 *alpha, uint32 w, uint32 color) {
        if (!w)
            return;

        // update dest pointer
        uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);

        do {
            const uint8 px = *dstp;
            const sint16 a = *alpha++;

            *dstp++ = px + (((sint32)(color - px) * a + 64) >> 7);
        } while(--w);
    }

    void RenderABuffer8_256(const VDPixmap& dst, int y, const uint16 *alpha, uint32 w, uint32 color) {
        if (!w)
            return;

        // update dest pointer
        uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);

        do {
            const uint8 px = *dstp;
            const sint32 a = *alpha++;

            *dstp++ = px + (((sint32)(color - px) * a + 128) >> 8);
        } while(--w);
    }

    void RenderABuffer8_1024(const VDPixmap& dst, int y, const uint16 *alpha, uint32 w, uint32 color) {
        if (!w)
            return;

        // update dest pointer
        uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);

        do {
            const uint8 px = *dstp;
            const sint32 a = *alpha++;

            *dstp++ = px + (((sint32)(color - px) * a + 512) >> 10);
        } while(--w);
    }
}

bool VDPixmapFillRegionAntialiased_32x_32x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
    if (dst.format != nsVDPixmap::kPixFormat_Y8)
        return false;

    // fast out
    if (region.mSpans.empty())
        return true;

    // check if vertical clipping is required
    const size_t n = region.mSpans.size();
    uint32 start = 0;
    uint32 end = n;

    uint32 spanmin = -x + (-y << 16) + 0x80008000;

    if (region.mSpans.front() < spanmin) {
        // find first span : x2 > spanmin
        start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
        start &= ~1;

        // check for total top clip
        if (start >= n)
            return true;
    }

    uint32 spanlimit = (dst.w*32 - x) + (((dst.h*32 - y) - 1) << 16) + 0x80008000;

    if (region.mSpans.back() > spanlimit) {
        // find last span : x1 < spanlimit
        end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();

        end = (end + 1) & ~1;

        // check for total bottom clip
        if (start >= end)
            return true;
    }

    // allocate A-buffer
    vdfastvector<uint16> abuffer(dst.w, 0);

    // fill region
    const uint32 *pSpan = ®ion.mSpans[start];
    const uint32 *pEnd  = ®ion.mSpans[0] + end;
    int lasty = -1;

    sint32 dstw32 = dst.w * 32;
    sint32 dsth32 = dst.h * 32;

    for(; pSpan != pEnd; pSpan += 2) {
        uint32 span0 = pSpan[0];
        uint32 span1 = pSpan[1];

        sint32 py = (span0 >> 16) - 0x8000 + y;

        if ((uint32)py >= (uint32)dsth32)
            continue;

        sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
        sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
        sint32 w = span1-span0;

        if (lasty != py) {
            if (((lasty ^ py) & 0xFFFFFFE0)) {
                if (lasty >= 0) {
                    // flush scanline

                    RenderABuffer8_1024(dst, lasty >> 5, abuffer.data(), dst.w, color);
                }

                memset(abuffer.data(), 0, abuffer.size() * sizeof(abuffer[0]));
            }
            lasty = py;
        }

        if (px1 < 0)
            px1 = 0;
        if (px2 > dstw32)
            px2 = dstw32;

        if (px1 >= px2)
            continue;

        uint32 ix1 = px1 >> 5;
        uint32 ix2 = px2 >> 5;
        uint16 *p1 = abuffer.data() + ix1;
        uint16 *p2 = abuffer.data() + ix2;

        if (p1 == p2) {
            p1[0] += (px2 - px1);
        } else {
            if (px1 & 31) {
                p1[0] += 32 - (px1 & 31);
                ++p1;
            }

            while(p1 != p2) {
                p1[0] += 32;
                ++p1;
            }

            if (px2 & 31)
                p1[0] += px2 & 32;
        }
    }

    if (lasty >= 0)
        RenderABuffer8_1024(dst, lasty >> 5, abuffer.data(), dst.w, color);

    return true;
}

bool VDPixmapFillRegionAntialiased_16x_16x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
    if (dst.format != nsVDPixmap::kPixFormat_Y8)
        return false;

    // fast out
    if (region.mSpans.empty())
        return true;

    // check if vertical clipping is required
    const size_t n = region.mSpans.size();
    uint32 start = 0;
    uint32 end = n;

    uint32 spanmin = -x + (-y << 16) + 0x80008000;

    if (region.mSpans.front() < spanmin) {
        // find first span : x2 > spanmin
        start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
        start &= ~1;

        // check for total top clip
        if (start >= n)
            return true;
    }

    uint32 spanlimit = (dst.w*16 - x) + (((dst.h*16 - y) - 1) << 16) + 0x80008000;

    if (region.mSpans.back() > spanlimit) {
        // find last span : x1 < spanlimit
        end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();

        end = (end + 1) & ~1;

        // check for total bottom clip
        if (start >= end)
            return true;
    }

    // allocate A-buffer
    vdfastvector<uint16> abuffer(dst.w, 0);

    // fill region
    const uint32 *pSpan = ®ion.mSpans[start];
    const uint32 *pEnd  = ®ion.mSpans[0] + end;
    int lasty = -1;

    sint32 dstw16 = dst.w * 16;
    sint32 dsth16 = dst.h * 16;

    for(; pSpan != pEnd; pSpan += 2) {
        uint32 span0 = pSpan[0];
        uint32 span1 = pSpan[1];

        sint32 py = (span0 >> 16) - 0x8000 + y;

        if ((uint32)py >= (uint32)dsth16)
            continue;

        sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
        sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
        sint32 w = span1-span0;

        if (lasty != py) {
            if (((lasty ^ py) & 0xFFFFFFF0)) {
                if (lasty >= 0) {
                    // flush scanline

                    RenderABuffer8_256(dst, lasty >> 4, abuffer.data(), dst.w, color);
                }

                memset(abuffer.data(), 0, abuffer.size() * sizeof(abuffer[0]));
            }
            lasty = py;
        }

        if (px1 < 0)
            px1 = 0;
        if (px2 > dstw16)
            px2 = dstw16;

        if (px1 >= px2)
            continue;

        uint32 ix1 = px1 >> 4;
        uint32 ix2 = px2 >> 4;
        uint16 *p1 = abuffer.data() + ix1;
        uint16 *p2 = abuffer.data() + ix2;

        if (p1 == p2) {
            p1[0] += (px2 - px1);
        } else {
            if (px1 & 15) {
                p1[0] += 16 - (px1 & 15);
                ++p1;
            }

            while(p1 != p2) {
                p1[0] += 16;
                ++p1;
            }

            if (px2 & 15)
                p1[0] += px2 & 15;
        }
    }

    if (lasty >= 0)
        RenderABuffer8_256(dst, lasty >> 4, abuffer.data(), dst.w, color);

    return true;
}

bool VDPixmapFillRegionAntialiased_16x_8x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
    if (dst.format != nsVDPixmap::kPixFormat_XRGB8888 && dst.format != nsVDPixmap::kPixFormat_Y8)
        return false;

    // fast out
    if (region.mSpans.empty())
        return true;

    // check if vertical clipping is required
    const size_t n = region.mSpans.size();
    uint32 start = 0;
    uint32 end = n;

    uint32 spanmin = -x + (-y << 16) + 0x80008000;

    if (region.mSpans.front() < spanmin) {
        // find first span : x2 > spanmin
        start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
        start &= ~1;

        // check for total top clip
        if (start >= n)
            return true;
    }

    uint32 spanlimit = (dst.w*16 - x) + (((dst.h*8 - y) - 1) << 16) + 0x80008000;

    if (region.mSpans.back() > spanlimit) {
        // find last span : x1 < spanlimit
        end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();

        end = (end + 1) & ~1;

        // check for total bottom clip
        if (start >= end)
            return true;
    }

    // allocate A-buffer
    vdfastvector<uint8> abuffer(dst.w, 0);

    // fill region
    const uint32 *pSpan = ®ion.mSpans[start];
    const uint32 *pEnd  = ®ion.mSpans[0] + end;
    int lasty = -1;

    sint32 dstw16 = dst.w * 16;
    sint32 dsth8 = dst.h * 8;

    for(; pSpan != pEnd; pSpan += 2) {
        uint32 span0 = pSpan[0];
        uint32 span1 = pSpan[1];

        sint32 py = (span0 >> 16) - 0x8000 + y;

        if ((uint32)py >= (uint32)dsth8)
            continue;

        sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
        sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
        sint32 w = span1-span0;

        if (lasty != py) {
            if (((lasty ^ py) & 0xFFFFFFF8)) {
                if (lasty >= 0) {
                    // flush scanline

                    RenderABuffer8_128(dst, lasty >> 3, abuffer.data(), dst.w, color);
                }

                memset(abuffer.data(), 0, abuffer.size());
            }
            lasty = py;
        }

        if (px1 < 0)
            px1 = 0;
        if (px2 > dstw16)
            px2 = dstw16;

        if (px1 >= px2)
            continue;

        uint32 ix1 = px1 >> 4;
        uint32 ix2 = px2 >> 4;
        uint8 *p1 = abuffer.data() + ix1;
        uint8 *p2 = abuffer.data() + ix2;

        if (p1 == p2) {
            p1[0] += (px2 - px1);
        } else {
            if (px1 & 15) {
                p1[0] += 16 - (px1 & 15);
                ++p1;
            }

            while(p1 != p2) {
                p1[0] += 16;
                ++p1;
            }

            if (px2 & 15)
                p1[0] += px2 & 15;
        }
    }

    if (lasty >= 0)
        RenderABuffer8_128(dst, lasty >> 3, abuffer.data(), dst.w, color);

    return true;
}

bool VDPixmapFillRegionAntialiased8x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
    if (dst.format == nsVDPixmap::kPixFormat_YUV444_Planar ||
        dst.format == nsVDPixmap::kPixFormat_YUV422_Planar ||
        dst.format == nsVDPixmap::kPixFormat_YUV420_Planar ||
        dst.format == nsVDPixmap::kPixFormat_YUV410_Planar) {
        VDPixmap pxY;
        VDPixmap pxCb;
        VDPixmap pxCr;

        pxY.format = nsVDPixmap::kPixFormat_Y8;
        pxY.data = dst.data;
        pxY.pitch = dst.pitch;
        pxY.w = dst.w;
        pxY.h = dst.h;

        pxCb.format = nsVDPixmap::kPixFormat_Y8;
        pxCb.data = dst.data2;
        pxCb.pitch = dst.pitch2;
        pxCb.w = dst.w;
        pxCb.h = dst.h;

        pxCr.format = nsVDPixmap::kPixFormat_Y8;
        pxCr.data = dst.data3;
        pxCr.pitch = dst.pitch3;
        pxCr.w = dst.w;
        pxCr.h = dst.h;

        uint32 colorY = (color >> 8) & 0xff;
        uint32 colorCb = (color >> 0) & 0xff;
        uint32 colorCr = (color >> 16) & 0xff;

        VDPixmapFillRegionAntialiased8x(pxY, region, x, y, colorY);

        switch(dst.format) {
        case nsVDPixmap::kPixFormat_YUV410_Planar:
            pxCr.w = pxCb.w = dst.w >> 2;
            pxCr.h = pxCb.h = dst.h >> 2;
            x >>= 2;
            y >>= 2;
            VDPixmapFillRegionAntialiased_32x_32x(pxCb, region, x, y, colorCb);
            VDPixmapFillRegionAntialiased_32x_32x(pxCr, region, x, y, colorCr);
            return true;
        case nsVDPixmap::kPixFormat_YUV420_Planar:
            pxCr.w = pxCb.w = dst.w >> 1;
            pxCr.h = pxCb.h = dst.h >> 1;
            x >>= 1;
            y >>= 1;
            x += 2;
            VDPixmapFillRegionAntialiased_16x_16x(pxCb, region, x, y, colorCb);
            VDPixmapFillRegionAntialiased_16x_16x(pxCr, region, x, y, colorCr);
            return true;
        case nsVDPixmap::kPixFormat_YUV422_Planar:
            pxCr.w = pxCb.w = dst.w >> 1;
            x >>= 1;
            x += 2;
            VDPixmapFillRegionAntialiased_16x_8x(pxCb, region, x, y, colorCb);
            VDPixmapFillRegionAntialiased_16x_8x(pxCr, region, x, y, colorCr);
            return true;
        case nsVDPixmap::kPixFormat_YUV444_Planar:
            VDPixmapFillRegionAntialiased8x(pxCb, region, x, y, colorCb);
            VDPixmapFillRegionAntialiased8x(pxCr, region, x, y, colorCr);
            return true;
        }
    }

    if (dst.format != nsVDPixmap::kPixFormat_XRGB8888 && dst.format != nsVDPixmap::kPixFormat_Y8)
        return false;

    // fast out
    if (region.mSpans.empty())
        return true;

    // check if vertical clipping is required
    const size_t n = region.mSpans.size();
    uint32 start = 0;
    uint32 end = n;

    uint32 spanmin = -x + (-y << 16) + 0x80008000;

    if (region.mSpans.front() < spanmin) {
        // find first span : x2 > spanmin
        start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
        start &= ~1;

        // check for total top clip
        if (start >= n)
            return true;
    }

    uint32 spanlimit = (dst.w*8 - x) + (((dst.h*8 - y) - 1) << 16) + 0x80008000;

    if (region.mSpans.back() > spanlimit) {
        // find last span : x1 < spanlimit
        end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();

        end = (end + 1) & ~1;

        // check for total bottom clip
        if (start >= end)
            return true;
    }

    // allocate A-buffer
    vdfastvector<uint8> abuffer(dst.w, 0);

    // fill region
    const uint32 *pSpan = ®ion.mSpans[start];
    const uint32 *pEnd  = ®ion.mSpans[0] + end;
    int lasty = -1;

    sint32 dstw8 = dst.w * 8;
    sint32 dsth8 = dst.h * 8;

    for(; pSpan != pEnd; pSpan += 2) {
        uint32 span0 = pSpan[0];
        uint32 span1 = pSpan[1];

        sint32 py = (span0 >> 16) - 0x8000 + y;

        if ((uint32)py >= (uint32)dsth8)
            continue;

        sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
        sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
        sint32 w = span1-span0;

        if (lasty != py) {
            if (((lasty ^ py) & 0xFFFFFFF8)) {
                if (lasty >= 0) {
                    // flush scanline

                    if (dst.format == nsVDPixmap::kPixFormat_XRGB8888)
                        RenderABuffer32(dst, lasty >> 3, abuffer.data(), dst.w, color);
                    else
                        RenderABuffer8(dst, lasty >> 3, abuffer.data(), dst.w, color);
                }

                memset(abuffer.data(), 0, abuffer.size());
            }
            lasty = py;
        }

        if (px1 < 0)
            px1 = 0;
        if (px2 > dstw8)
            px2 = dstw8;

        if (px1 >= px2)
            continue;

        uint32 ix1 = px1 >> 3;
        uint32 ix2 = px2 >> 3;
        uint8 *p1 = abuffer.data() + ix1;
        uint8 *p2 = abuffer.data() + ix2;

        if (p1 == p2) {
            p1[0] += (px2 - px1);
        } else {
            if (px1 & 7) {
                p1[0] += 8 - (px1 & 7);
                ++p1;
            }

            while(p1 != p2) {
                p1[0] += 8;
                ++p1;
            }

            if (px2 & 7)
                p1[0] += px2 & 7;
        }
    }

    if (lasty >= 0) {
        if (dst.format == nsVDPixmap::kPixFormat_XRGB8888)
            RenderABuffer32(dst, lasty >> 3, abuffer.data(), dst.w, color);
        else
            RenderABuffer8(dst, lasty >> 3, abuffer.data(), dst.w, color);
    }

    return true;
}

void VDPixmapCreateRoundRegion(VDPixmapRegion& dst, float r) {
    int ir = VDCeilToInt(r);
    float r2 = r*r;

    dst.mSpans.clear();
    dst.mBounds.set(-ir, 0, ir+1, 0);

    for(int y = -ir; y <= ir; ++y) {
        int dx = VDCeilToInt(sqrtf(r2 - y*y));

        if (dx > 0) {
            dst.mSpans.push_back(0x80008000 + (y << 16) - dx);
            dst.mSpans.push_back(0x80008001 + (y << 16) + dx);
            if (dst.mBounds.top > y)
                dst.mBounds.top = y;
            if (dst.mBounds.bottom < y)
                dst.mBounds.bottom = y;
        }
    }
}

void VDPixmapConvolveRegion(VDPixmapRegion& dst, const VDPixmapRegion& r1, const VDPixmapRegion& r2, int dx1, int dx2, int dy) {
    dst.mSpans.clear();
    dst.mSpans.resize(r1.mSpans.size()+r2.mSpans.size());

    const uint32 *itA    = r1.mSpans.data();
    const uint32 *itAE    = itA + r1.mSpans.size();
    const uint32 *itB    = r2.mSpans.data();
    const uint32 *itBE    = itB + r2.mSpans.size();
    uint32 *dstp0 = dst.mSpans.data();
    uint32 *dstp = dst.mSpans.data();

    uint32 offset1 = (dy<<16) + dx1;
    uint32 offset2 = (dy<<16) + dx2;

    while(itA != itAE && itB != itBE) {
        uint32 x1;
        uint32 x2;

        if (itB[0] + offset1 < itA[0]) {
            // B span is earlier.  Use it.
            x1 = itB[0] + offset1;
            x2 = itB[1] + offset2;
            itB += 2;

            // B spans *can* overlap, due to the widening.
            while(itB != itBE && itB[0]+offset1 <= x2) {
                uint32 bx2 = itB[1] + offset2;
                if (x2 < bx2)
                    x2 = bx2;

                itB += 2;
            }

            goto a_start;
        } else {
            // A span is earlier.  Use it.
            x1 = itA[0];
            x2 = itA[1];
            itA += 2;

            // A spans don't overlap, so begin merge loop with B first.
        }

        for(;;) {
            // If we run out of B spans or the B span doesn't overlap,
            // then the next A span can't either (because A spans don't
            // overlap) and we exit.

            if (itB == itBE || itB[0]+offset1 > x2)
                break;

            do {
                uint32 bx2 = itB[1] + offset2;
                if (x2 < bx2)
                    x2 = bx2;

                itB += 2;
            } while(itB != itBE && itB[0]+offset1 <= x2);

            // If we run out of A spans or the A span doesn't overlap,
            // then the next B span can't either, because we would have
            // consumed all overlapping B spans in the above loop.
a_start:
            if (itA == itAE || itA[0] > x2)
                break;

            do {
                uint32 ax2 = itA[1];
                if (x2 < ax2)
                    x2 = ax2;

                itA += 2;
            } while(itA != itAE && itA[0] <= x2);
        }

        // Flush span.
        dstp[0] = x1;
        dstp[1] = x2;
        dstp += 2;
    }

    // Copy over leftover spans.
    memcpy(dstp, itA, sizeof(uint32)*(itAE - itA));
    dstp += itAE - itA;

    while(itB != itBE) {
        // B span is earlier.  Use it.
        uint32 x1 = itB[0] + offset1;
        uint32 x2 = itB[1] + offset2;
        itB += 2;

        // B spans *can* overlap, due to the widening.
        while(itB != itBE && itB[0]+offset1 <= x2) {
            uint32 bx2 = itB[1] + offset2;
            if (x2 < bx2)
                x2 = bx2;

            itB += 2;
        }

        dstp[0] = x1;
        dstp[1] = x2;
        dstp += 2;
    }

    dst.mSpans.resize(dstp - dst.mSpans.data());
}

void VDPixmapConvolveRegion(VDPixmapRegion& dst, const VDPixmapRegion& r1, const VDPixmapRegion& r2) {
    VDPixmapRegion temp;

    const uint32 *src1 = r2.mSpans.data();
    const uint32 *src2 = src1 + r2.mSpans.size();

    dst.mSpans.clear();
    while(src1 != src2) {
        uint32 p1 = src1[0];
        uint32 p2 = src1[1];
        src1 += 2;

        temp.mSpans.swap(dst.mSpans);
        VDPixmapConvolveRegion(dst, temp, r1, (p1 & 0xffff) - 0x8000, (p2 & 0xffff) - 0x8000, (p1 >> 16) - 0x8000);
    }
}