凸四角形同士の転送ルーチン(3)

凸四角形同士の転送ルーチンのソースです。

めちゃめちゃ長いので、続きを見る場合にはご注意を。

void VertexBlt(
    word* dst,                      // 転送先
    const Point* dstPoints_,        // 転送先の位置（４点）
    const Rectangle& dstClip,       // 転送先クリッピング情報
    int dp,                         // 転送先ピッチ
    byte* src,                      // 転送元
    const Point* srcPoints_,        // 転送元の位置（４点）
    const Rectangle& srcClip,       // 転送元クリッピング情報
    int sp,                         // 転送元ピッチ
    word* pal,                      // 転送元のパレット
)
{
    // 転送に関する情報。
    // dstY と dstDY が無いのは、dstY はループ中の y のことだし、
    // dstDY を基準に増分等を出しているので dstDY は必ず 1 になるから。
    struct VertexBltInfo
    {
        int     dstX;         // 転送先X の開始位置
        int     srcX;         // 転送元X の開始位置
        int     srcY;         // 転送元Y の開始位置
        int     dstDX;        // dstX の増分
        int     srcDX;        // srcX の増分
        int     srcDY;        // srcY の増分
    };
    int             ybase[4];
    VertexBltInfo   vertexBltInfo[4][2];

    // 初期設定

    Point dstPoints[4];
    Point srcPoints[4];
    // いろいろ操作するのでコピー
    for (int i = 0 ; i < 4 ; i++)
    {
        dstPoints[i] = dstPoints_[i];
        srcPoints[i] = srcPoints_[i];
    }
    // 転送先クリッピングに関する処理
    Size dstSize;
    int cl, cr, cu, cd;
    {
        // 転送先の最小矩形を求める
        int dx = min(min(min(dstPoints[0].x, dstPoints[1].x), dstPoints[2].x), dstPoints[3].x);
        int dy = min(min(min(dstPoints[0].y, dstPoints[1].y), dstPoints[2].y), dstPoints[3].y);
        dstSize.w = max(max(max(dstPoints[0].x, dstPoints[1].x), dstPoints[2].x), dstPoints[3].x) - dx + 1;
        dstSize.h = max(max(max(dstPoints[0].y, dstPoints[1].y), dstPoints[2].y), dstPoints[3].y) - dy + 1;

        // 完全に範囲外
        // ほんとは線分の交差判定もするべきなんだろうけど、めんどいのでパス
        if (dx + dstSize.w < dstClip.x ||
            dy + dstSize.h < dstClip.y ||
            dx >= dstClip.x + dstClip.w ||
            dy >= dstClip.y + dstClip.h)
        {
            return;
        }

        cl = cr = cu = cd = 0;

        // 左
        if (dx < dstClip.x)
        {
            cl = dstClip.x - dx;
        }
        // 右（これは広さではなく、右側の座標そのもの）
        if (dx > dstClip.x)
        {
            cr = dx - dstClip.x;
        }
        cr = cl + dstClip.x + dstClip.w - cr;

        // 上
        if (dy < dstClip.y)
        {
            cu = dstClip.y - dy;
        }
        // 下
        if (dy + dstSize.h > dstClip.y + dstClip.h)
        {
            cd = (dy + dstSize.h) - (dstClip.y + dstClip.h);
        }

        dst = (word*)((byte*)dst + dx * sizeof(word) + dy * dp);

        // dstPoints をずらす
        for (int i = 0; i < 4; i++)
        {
            dstPoints[i].x -= dx;
            dstPoints[i].y -= dy;
        }
    }
    // 転送元クリッピングに関する処理
    Size srcSize;
    bool bSrcClip;
    {
        // 転送先の最小矩形を求める
        int sx = min(min(min(srcPoints[0].x, srcPoints[1].x), srcPoints[2].x), srcPoints[3].x);
        int sy = min(min(min(srcPoints[0].y, srcPoints[1].y), srcPoints[2].y), srcPoints[3].y);
        srcSize.w = max(max(max(srcPoints[0].x, srcPoints[1].x), srcPoints[2].x), srcPoints[3].x) - sx + 1;
        srcSize.h = max(max(max(srcPoints[0].y, srcPoints[1].y), srcPoints[2].y), srcPoints[3].y) - sy + 1;

        // 完全に範囲外
        if (sx + srcSize.w < srcClip.x ||
            sy + srcSize.h < srcClip.y ||
            sx >= srcClip.x + srcClip.w ||
            sy >= srcClip.y + srcClip.h)
        {
            return;
        }

        // 転送元に対してクリッピングを行う必要があるか
        if (sx < srcClip.x ||
            sy < srcClip.y ||
            sx + srcSize.w > srcClip.x + srcClip.w ||
            sy + srcSize.h > srcClip.y + srcClip.h)
        {
            bSrcClip = true;
        }
        else
        {
            bSrcClip = false;
        }

        src = (byte*)((byte*)src + srcClip.x * sizeof(byte) + srcClip.y * sp);
        // srcPoints をずらす
        for (int i = 0; i < 4; i++)
        {
            srcPoints[i].x -= srcClip.x;
            srcPoints[i].y -= srcClip.y;
        }
    }

    // 16bit の固定小数で計算する
    for (int i = 0; i < 4; i++)
    {
        dstPoints[i].x <<= 16;
        dstPoints[i].y <<= 16;
        srcPoints[i].x <<= 16;
        srcPoints[i].y <<= 16;
    }

    // 描画情報を計算
    {
        // 次のラインの Y 座標情報
        int nextY[2];
        // 前回のラインのインデックス
        int line[2];
        // ラインの向き（順方向→1、逆方向→-1）
        int dir[2];
        // y == 0 の時点での初期情報を計算
        {
            // 最初は必ずゼロ
            ybase[0] = 0;

            int num = 0;
            int i;
            for (i = 0; i < 4; i++)
            {
                int n1, n2;
                n1 = i;
                n2 = (i + 1) & 3;
                Point p1 = dstPoints[n1];
                Point p2 = dstPoints[n2];
                Point s1 = srcPoints[n1];
                Point s2 = srcPoints[n2];
                // 線の繋がっている方向
                int d = 1;
                // X軸に平行
                if (p1.y == p2.y)
                {
                    continue;
                }
                if (p2.y == 0)
                {
                    // p1.y に 0 が来るようにする
                    swap(p1, p2);
                    swap(s1, s2);
                    swap(n1, n2);
                    // 逆方向
                    d = -1;
                }
                if (p1.y == 0)
                {
                    VertexBltInfo* info = &vertexBltInfo[0][num];
                    info->dstX = p1.x;
                    info->srcX = s1.x;
                    info->srcY = s1.y;
                    info->dstDX = (int)(((int64)(p2.x - p1.x) << 16) / p2.y);
                    info->srcDX = (int)(((int64)(s2.x - s1.x) << 16) / p2.y);
                    info->srcDY = (int)(((int64)(s2.y - s1.y) << 16) / p2.y);

                    line[num] = n1;
                    dir[num] = d;
                    nextY[num] = (p2.y >> 16);

                    // y == 0 地点で２点以上交差することって無いよね？
                    num++;
                    if (num == 2)
                    {
                        break;
                    }
                }
            }
            // 交点が見つからなかった→全ての点のY座標が同じ
            if (i == 4)
            {
                // ほんとうは１行のラインが描画されるべきなんだろうけど、めんどいからいいや……。
                return;
            }
        }
        int infoNum = 1;
        // 左右両方のラインが一番下までいけば終了
        while (nextY[0] != dstSize.h - 1 || nextY[1] != dstSize.h - 1)
        {
            int min, max;
            // Y の小さい方を見る
            if (nextY[0] <= nextY[1])
            {
                min = 0;
                max = 1;
            }
            else
            {
                min = 1;
                max = 0;
            }

            int n1, n2;
            Point p1, p2, s1, s2;

            n1 = (line[min] + dir[min]) & 3;
            n2 = (n1 + dir[min]) & 3;
            while (true)
            {
                p1 = dstPoints[n1];
                p2 = dstPoints[n2];
                // こうなってる（p1.y >= p2.y）時点で凸四角形じゃないんだけど、
                // とりあえずエラーは出ないようにしておく
                if (p1.y >= p2.y)
                {
                    n1 = (n1 + dir[min]) & 3;
                    n2 = (n1 + dir[min]) & 3;
                }
                else
                {
                    break;
                }
            }
            s1 = srcPoints[n1];
            s2 = srcPoints[n2];

            ybase[infoNum] = nextY[min];

            VertexBltInfo* info = &vertexBltInfo[infoNum][min];
            info->dstX = p1.x;
            info->srcX = s1.x;
            info->srcY = s1.y;
            info->dstDX = (int)(((int64)(p2.x - p1.x) << 16) / (p2.y - p1.y));
            info->srcDX = (int)(((int64)(s2.x - s1.x) << 16) / (p2.y - p1.y));
            info->srcDY = (int)(((int64)(s2.y - s1.y) << 16) / (p2.y - p1.y));
            // ◇ ←のような菱形の図形の場合、中央の２箇所の交点での Y 座標が同じになるので、
            // 反対側の情報も更新しなければならない
            if (nextY[min] == nextY[max])
            {
                line[min] = n1;
                // nextY[min] を次のラインの Y 座標に設定
                if (nextY[min] != dstSize.h - 1)
                {
                    nextY[min] = (dstPoints[n2].y >> 16);
                }

                // max 側の情報も更新
                {
                    n1 = (line[max] + dir[max]) & 3;
                    n2 = (n1 + dir[max]) & 3;
                    while (true)
                    {
                        p1 = dstPoints[n1];
                        p2 = dstPoints[n2];
                        if (p1.y >= p2.y)
                        {
                            n1 = (n1 + dir[max]) & 3;
                            n2 = (n1 + dir[max]) & 3;
                        }
                        else
                        {
                            break;
                        }
                    }
                    s1 = srcPoints[n1];
                    s2 = srcPoints[n2];

                    line[max] = n1;
                    if (nextY[max] != dstSize.h - 1)
                    {
                        nextY[max] = (dstPoints[n2].y >> 16);
                    }

                    info = &vertexBltInfo[infoNum][max];

                    info->dstX = p1.x;
                    info->srcX = s1.x;
                    info->srcY = s1.y;
                    info->dstDX = (int)(((int64)(p2.x - p1.x) << 16) / (p2.y - p1.y));
                    info->srcDX = (int)(((int64)(s2.x - s1.x) << 16) / (p2.y - p1.y));
                    info->srcDY = (int)(((int64)(s2.y - s1.y) << 16) / (p2.y - p1.y));
                }
            }
            else
            {
                line[min] = n1;
                // nextY[min] を次のラインの Y 座標に設定
                if (nextY[min] != dstSize.h - 1)
                {
                    nextY[min] = (dstPoints[n2].y >> 16);
                }

                // max 側は前の位置からの差分で動かしてやるだけ
                info = &vertexBltInfo[infoNum][max];
                VertexBltInfo* prevInfo = &vertexBltInfo[infoNum - 1][max];
                int height = ybase[infoNum] - ybase[infoNum - 1];

                info->dstX = prevInfo->dstX + prevInfo->dstDX * height;
                info->srcX = prevInfo->srcX + prevInfo->srcDX * height;
                info->srcY = prevInfo->srcY + prevInfo->srcDY * height;
                info->dstDX = prevInfo->dstDX;
                info->srcDX = prevInfo->srcDX;
                info->srcDY = prevInfo->srcDY;
            }
            infoNum++;
        }
        // 最後は dstSize.h より大きくないといけない
        ybase[infoNum] = dstSize.h;
    }


    VertexBltInfo* info1 = &vertexBltInfo[0][0];
    VertexBltInfo* info2 = &vertexBltInfo[0][1];
    int infoNum = 1;

    int y = 0;
    // Y座標クリッピング処理
    {
        while (ybase[infoNum] < cu)
        {
            y = ybase[infoNum];
            info1 = &vertexBltInfo[infoNum][0];
            info2 = &vertexBltInfo[infoNum][1];
            infoNum++;
        }
        int h = cu - y;
        info1->srcX += info1->srcDX * h;
        info1->srcY += info1->srcDY * h;
        info1->dstX += info1->dstDX * h;
        info2->srcX += info2->srcDX * h;
        info2->srcY += info2->srcDY * h;
        info2->dstX += info2->dstDX * h;
        dst = (word*)((byte*)dst + (dp * cu));
        y += h;

        dstSize.h -= cd;
    }
    // 転送開始
    for (; y < dstSize.h; y++)
    {
        // ybase の位置で転送情報を変える
        if (y == ybase[infoNum])
        {
            info1 = &vertexBltInfo[infoNum][0];
            info2 = &vertexBltInfo[infoNum][1];
            infoNum++;
        }
        // 正当な凸四角形であればループの外でこれを行ってもいいが、
        // 途中で交差してる四角形のためにここで swap してやる。
        if (info1->dstX > info2->dstX)
        {
            swap(info1, info2);
        }

        // X 方向の開始位置と増分を計算
        int s, e, SX, SY, SDX, SDY;
        {
            int frame = (info2->dstX - info1->dstX + (1 << 16));
            SDX = (int)(((int64)(info2->srcX - info1->srcX) << 16) / frame);
            SDY = (int)(((int64)(info2->srcY - info1->srcY) << 16) / frame);
        }
        SX = info1->srcX;
        SY = info1->srcY;
        s = info1->dstX >> 16;
        e = info2->dstX >> 16;

        // X座標クリッピング処理
        {
            if (s < cl)
            {
                int ccl = cl - s;
                SX += SDX * ccl;
                SY += SDY * ccl;
                s += ccl;
            }
            if (e >= cr)
            {
                e -= e - cr + 1;
            }
        }

        // 更に高速化を考えるのであれば Y ループの外側に出すべき。
        // BREW の場合は容量との兼ね合いもあるのでここで分岐させておく。
        if (!bSrcClip)
        {
            // X方向に転送開始（転送元クリッピング無し）
            for (; s <= e ;s++)
            {
                dst[s] = pal[src[(SY >> 16) * sp + (SX >> 16)]];
                SX += SDX;
                SY += SDY;
            }
        }
        else
        {
            // X方向に転送開始（転送元クリッピング有り）
            for (; s <= e; s++)
            {
                if ((uint32)(SX >> 16) < (uint32)srcClip.w && (uint32)(SY >> 16) < (uint32)srcClip.h)
                {
                    dst[s] = pal[src[(SY >> 16) * sp + (SX >> 16)]];
                }
                SX += SDX;
                SY += SDY;
            }
        }

        // 直線の増分を加算
        info1->srcX += info1->srcDX;
        info1->srcY += info1->srcDY;
        info1->dstX += info1->dstDX;
        info2->srcX += info2->srcDX;
        info2->srcY += info2->srcDY;
        info2->dstX += info2->dstDX;
        dst = (word*)((byte*)dst + dp);
    }
}

(;´ρ`)ﾁｶﾚﾀﾖ･･･