wmlrasterdrawing.cpp

来自「3D Game Engine Design Source Code非常棒」· C++ 代码 · 共 883 行 · 第 1/2 页

// Magic Software, Inc.
// http://www.magic-software.com
// http://www.wild-magic.com
// Copyright (c) 2003.  All Rights Reserved
//
// The Wild Magic Library (WML) source code is supplied under the terms of
// the license agreement http://www.magic-software.com/License/WildMagic.pdf
// and may not be copied or disclosed except in accordance with the terms of
// that agreement.

#include "WmlRasterDrawing.h"
#include "WmlMath.h"
#include "WmlTInteger.h"
using namespace Wml;

//----------------------------------------------------------------------------
void Wml::Line2D (int iX0, int iY0, int iX1, int iY1,
    void (*oCallback)(int,int))
{
    // starting point of line
    int iX = iX0, iY = iY0;

    // direction of line
    int iDx = iX1-iX0, iDy = iY1-iY0;

    // increment or decrement depending on direction of line
    int iSx = (iDx > 0 ? 1 : (iDx < 0 ? -1 : 0));
    int iSy = (iDy > 0 ? 1 : (iDy < 0 ? -1 : 0));

    // decision parameters for voxel selection
    if ( iDx < 0 ) iDx = -iDx;
    if ( iDy < 0 ) iDy = -iDy;
    int iAx = 2*iDx, iAy = 2*iDy;
    int iDecX, iDecY;

    // determine largest direction component, single-step related variable
    int iMax = iDx, iVar = 0;
    if ( iDy > iMax ) { iVar = 1; }

    // traverse Bresenham line
    switch ( iVar )
    {
    case 0:  // single-step in x-direction
        iDecY = iAy - iDx;
        for (/**/; /**/; iX += iSx, iDecY += iAy)
        {
            // process pixel
            oCallback(iX,iY);

            // take Bresenham step
            if ( iX == iX1 )  break;
            if ( iDecY >= 0 ) { iDecY -= iAx; iY += iSy; }
        }
        break;
    case 1:  // single-step in y-direction
        iDecX = iAx - iDy;
        for (/**/; /**/; iY += iSy, iDecX += iAx)
        {
            // process pixel
            oCallback(iX,iY);

            // take Bresenham step
            if ( iY == iY1 ) break;
            if ( iDecX >= 0 ) { iDecX -= iAy; iX += iSx; }
        }
        break;
    }
}
//----------------------------------------------------------------------------
void Wml::Line3D (int iX0, int iY0, int iZ0, int iX1, int iY1, int iZ1,
    void (*oCallback)(int,int,int))
{
    // starting point of line
    int iX = iX0, iY = iY0, iZ = iZ0;

    // direction of line
    int iDx = iX1-iX0, iDy = iY1-iY0, iDz = iZ1-iZ0;

    // increment or decrement depending on direction of line
    int iSx = (iDx > 0 ? 1 : (iDx < 0 ? -1 : 0));
    int iSy = (iDy > 0 ? 1 : (iDy < 0 ? -1 : 0));
    int iSz = (iDz > 0 ? 1 : (iDz < 0 ? -1 : 0));

    // decision parameters for voxel selection
    if ( iDx < 0 ) iDx = -iDx;
    if ( iDy < 0 ) iDy = -iDy;
    if ( iDz < 0 ) iDz = -iDz;
    int iAx = 2*iDx, iAy = 2*iDy, iAz = 2*iDz;
    int iDecX, iDecY, iDecZ;

    // determine largest direction component, single-step related variable
    int iMax = iDx, iVar = 0;
    if ( iDy > iMax ) { iMax = iDy; iVar = 1; }
    if ( iDz > iMax ) { iVar = 2; }

    // traverse Bresenham line
    switch ( iVar )
    {
    case 0:  // single-step in iX-direction
        iDecY = iAy - iDx;
        iDecZ = iAz - iDx;
        for (/**/; /**/; iX += iSx, iDecY += iAy, iDecZ += iAz)
        {
            // process voxel
            oCallback(iX,iY,iZ);

            // take Bresenham step
            if ( iX == iX1 ) break;
            if ( iDecY >= 0 ) { iDecY -= iAx; iY += iSy; }
            if ( iDecZ >= 0 ) { iDecZ -= iAx; iZ += iSz; }
        }
        break;
    case 1:  // single-step in iY-direction
        iDecX = iAx - iDy;
        iDecZ = iAz - iDy;
        for (/**/; /**/; iY += iSy, iDecX += iAx, iDecZ += iAz)
        {
            // process voxel
            oCallback(iX,iY,iZ);

            // take Bresenham step
            if ( iY == iY1 ) break;
            if ( iDecX >= 0 ) { iDecX -= iAy; iX += iSx; }
            if ( iDecZ >= 0 ) { iDecZ -= iAy; iZ += iSz; }
        }
        break;
    case 2:  // single-step in iZ-direction
        iDecX = iAx - iDz;
        iDecY = iAy - iDz;
        for (/**/; /**/; iZ += iSz, iDecX += iAx, iDecY += iAy)
        {
            // process voxel
            oCallback(iX,iY,iZ);

            // take Bresenham step
            if ( iZ == iZ1 ) break;
            if ( iDecX >= 0 ) { iDecX -= iAz; iX += iSx; }
            if ( iDecY >= 0 ) { iDecY -= iAz; iY += iSy; }
        }
        break;
    }
}
//----------------------------------------------------------------------------
void Wml::Line4D (int iX0, int iY0, int iZ0, int iW0, int iX1, int iY1,
    int iZ1, int iW1,  void (*oCallback)(int,int,int,int))
{
    // starting point of line
    int iX = iX0, iY = iY0, iZ = iZ0, iW = iW0;

    // direction of line
    int iDx = iX1-iX0, iDy = iY1-iY0, iDz = iZ1-iZ0, iDw = iW1-iW0;

    // increment or decrement depending on direction of line
    int iSx = (iDx > 0 ? 1 : (iDx < 0 ? -1 : 0));
    int iSy = (iDy > 0 ? 1 : (iDy < 0 ? -1 : 0));
    int iSz = (iDz > 0 ? 1 : (iDz < 0 ? -1 : 0));
    int iSw = (iDw > 0 ? 1 : (iDw < 0 ? -1 : 0));

    // decision parameters for voxel selection
    if ( iDx < 0 ) iDx = -iDx;
    if ( iDy < 0 ) iDy = -iDy;
    if ( iDz < 0 ) iDz = -iDz;
    if ( iDw < 0 ) iDw = -iDw;
    int iAx = 2*iDx, iAy = 2*iDy, iAz = 2*iDz, iAw = 2*iDw;
    int iDecX, iDecY, iDecZ, iDecW;

    // determine largest direction component, single-step related variable
    int iMax = iDx, iVar = 0;
    if ( iDy > iMax ) { iMax = iDy; iVar = 1; }
    if ( iDz > iMax ) { iMax = iDz; iVar = 2; }
    if ( iDw > iMax ) { iVar = 3; }

    // traverse Bresenham line
    switch ( iVar )
    {
    case 0:  // single-step in iX-direction
        iDecY = iAy - iDx;
        iDecZ = iAz - iDx;
        iDecW = iAw - iDx;
        for (/**/; /**/; iX += iSx, iDecY += iAy, iDecZ += iAz, iDecW += iAw)
        {
            // process hypervoxel
            oCallback(iX,iY,iZ,iW);

            // take Bresenham step
            if ( iX == iX1 ) break;
            if ( iDecY >= 0 ) { iDecY -= iAx; iY += iSy; }
            if ( iDecZ >= 0 ) { iDecZ -= iAx; iZ += iSz; }
            if ( iDecW >= 0 ) { iDecW -= iAx; iW += iSw; }
        }
        break;
    case 1:  // single-step in iY-direction
        iDecX = iAx - iDy;
        iDecZ = iAz - iDy;
        iDecW = iAw - iDy;
        for (/**/; /**/; iY += iSy, iDecX += iAx, iDecZ += iAz, iDecW += iAw)
        {
            // process hypervoxel
            oCallback(iX,iY,iZ,iW);

            // take Bresenham step
            if ( iY == iY1 ) break;
            if ( iDecX >= 0 ) { iDecX -= iAy; iX += iSx; }
            if ( iDecZ >= 0 ) { iDecZ -= iAy; iZ += iSz; }
            if ( iDecW >= 0 ) { iDecW -= iAy; iW += iSw; }
        }
        break;
    case 2:  // single-step in iZ-direction
        iDecX = iAx - iDz;
        iDecY = iAy - iDz;
        iDecW = iAw - iDz;
        for (/**/; /**/; iZ += iSz, iDecX += iAx, iDecY += iAy, iDecW += iAw)
        {
            // process hypervoxel
            oCallback(iX,iY,iZ,iW);

            // take Bresenham step
            if ( iZ == iZ1 ) break;
            if ( iDecX >= 0 ) { iDecX -= iAz; iX += iSx; }
            if ( iDecY >= 0 ) { iDecY -= iAz; iY += iSy; }
            if ( iDecW >= 0 ) { iDecW -= iAz; iW += iSw; }
        }
        break;
    case 3:  // single-step in iP-direction
        iDecX = iAx - iDw;
        iDecY = iAy - iDw;
        iDecZ = iAz - iDw;
        for (/**/; /**/; iW += iSw, iDecX += iAx, iDecY += iAy, iDecZ += iAz)
        {
            // process voxel
            oCallback(iX,iY,iZ,iW);

            // take Bresenham step
            if ( iW == iW1 ) break;
            if ( iDecX >= 0 ) { iDecX -= iAw; iX += iSx; }
            if ( iDecY >= 0 ) { iDecY -= iAw; iY += iSy; }
            if ( iDecZ >= 0 ) { iDecZ -= iAw; iZ += iSz; }
        }
        break;
    }
}
//----------------------------------------------------------------------------
void Wml::Circle2D (int iXC, int iYC, int iR, void (*oCallback)(int,int))
{
    for (int iX = 0, iY = iR, iDec = 3-2*iR; iX <= iY; iX++)
    {
        oCallback(iXC+iX,iYC+iY);
        oCallback(iXC+iX,iYC-iY);
        oCallback(iXC-iX,iYC+iY);
        oCallback(iXC-iX,iYC-iY);
        oCallback(iXC+iY,iYC+iX);
        oCallback(iXC+iY,iYC-iX);
        oCallback(iXC-iY,iYC+iX);
        oCallback(iXC-iY,iYC-iX);

        if ( iDec >= 0 )
            iDec += -4*(iY--)+4;
        iDec += 4*iX+6;
    }
}
//----------------------------------------------------------------------------
void Wml::Ellipse2D (int iXC, int iYC, int iA, int iB,
    void (*oCallback)(int,int))
{
    int iA2 = iA*iA, iB2 = iB*iB;
    int iX, iY, iDec;

    for (iX = 0, iY = iB, iDec = 2*iB2+iA2*(1-2*iB); iB2*iX <= iA2*iY; iX++)
    {
        oCallback(iXC+iX,iYC+iY);
        oCallback(iXC-iX,iYC+iY);
        oCallback(iXC+iX,iYC-iY);
        oCallback(iXC-iX,iYC-iY);

        if ( iDec >= 0 )
            iDec += 4*iA2*(1-(iY--));
        iDec += iB2*(4*iX+6);
    }
    if ( iY == 0 && iX < iA )
    {
        // The discretization caused us to reach the y-axis before the
        // x-values reached the ellipse vertices.  Draw a solid line along
        // the x-axis to those vertices.
        for (/**/; iX <= iA; iX++)
        {
            oCallback(iXC+iX,iYC);
            oCallback(iXC-iX,iYC);
        }
        return;
    }

    for (iX = iA, iY = 0, iDec = 2*iA2+iB2*(1-2*iA); iA2*iY <= iB2*iX; iY++)
    {
        oCallback(iXC+iX,iYC+iY);
        oCallback(iXC-iX,iYC+iY);
        oCallback(iXC+iX,iYC-iY);
        oCallback(iXC-iX,iYC-iY);

        if ( iDec >= 0 )
            iDec += 4*iB2*(1-(iX--));
        iDec += iA2*(4*iY+6);
    }
    if ( iX == 0 && iY < iB )
    {
        // The discretization caused us to reach the x-axis before the
        // y-values reached the ellipse vertices.  Draw a solid line along
        // the y-axis to those vertices.
        for (/**/; iY <= iB; iY++)
        {
            oCallback(iXC,iYC+iY);
            oCallback(iXC,iYC-iY);
        }
    }
}
//----------------------------------------------------------------------------
static void SelectEllipsePoint (int iA2, int iB2, float fX, float fY, int& iX,
    int& iY)
{
    int iXFloor = int(Mathf::Floor(fX)), iYFloor = int(Mathf::Floor(fY));
    int iXIncr = iB2*(2*iXFloor+1), iYIncr = iA2*(2*iYFloor+1);
    int iBase = iB2*iXFloor*iXFloor+iA2*iYFloor*iYFloor-iA2*iB2;
    int iA00 = abs(iBase);
    int iA10 = abs(iBase+iXIncr);
    int iA01 = abs(iBase+iYIncr);
    int iA11 = abs(iBase+iXIncr+iYIncr);

    int iMin = iA00;
    iX = iXFloor;
    iY = iYFloor;
    if ( iA10 < iMin )
    {
        iMin = iA10;
        iX = iXFloor+1;
        iY = iYFloor;
    }
    if ( iA01 < iMin )
    {
        iMin = iA01;
        iX = iXFloor;
        iY = iYFloor+1;
    }
    if ( iA11 < iMin )
    {
        iMin = iA11;
        iX = iXFloor+1;
        iY = iYFloor+1;
    }
}
//----------------------------------------------------------------------------
static int WhichArc (int iA2, int iB2, int iX, int iY)
{
    if ( iX > 0 )
    {
        if ( iY > 0 )
            return ( iB2*iX <  iA2*iY ? 0 : 1 );
        else if ( iY < 0 )
            return ( iB2*iX > -iA2*iY ? 2 : 3 );
        else
            return 2;
    }
    else if ( iX < 0 )
    {
        if ( iY < 0 )
            return ( iA2*iY <  iB2*iX ? 4 : 5 );
        else if ( iY > 0 )
            return ( iA2*iY < -iB2*iX ? 6 : 7 );
        else
            return 6;
    }
    else
    {
        return ( iY > 0 ? 0 : 4 );
    }
}
//----------------------------------------------------------------------------
void Wml::EllipseArc2D (int iXC, int iYC, int iA, int iB, float fX0,
    float fY0, float fX1, float fY1, void (*oCallback)(int,int))
{
    // Assert (within floating point roundoff errors):
    //   (x0-xc)^2/a^2 + (y0-yc)^2/b^2 = 1
    //   (x1-xc)^2/a^2 + (y1-yc)^2/b^2 = 1
    // Assume if (x0,y0) == (x1,y1), then entire ellipse should be drawn.
    //
    // Pixels on arc are guaranteed to be traversed clockwise.

    const int iA2 = iA*iA, iB2 = iB*iB;

    // get integer end points for iArc
    int iX0, iY0, iX1, iY1;
    SelectEllipsePoint(iA2,iB2,fX0-iXC,fY0-iYC,iX0,iY0);
    SelectEllipsePoint(iA2,iB2,fX1-iXC,fY1-iYC,iX1,iY1);

    int iDx = iX0 - iX1, iDy = iY0 - iY1, iSqrLen = iDx*iDx+iDy*iDy;
    if ( iSqrLen == 1 || ( iSqrLen == 2 && abs(iDx) == 1 ) )
    {
        oCallback(iXC+iX0,iYC+iY0);
        oCallback(iXC+iX1,iYC+iY1);
        return;
    }

    // determine initial case for arc drawing
    int iArc = WhichArc(iA2,iB2,iX0,iY0);
    while ( true )
    {
        // process the pixel
        oCallback(iXC+iX0,iYC+iY0);

        // Determine next pixel to process.  Notation <(x,y),dy/dx> indicates
        // point on ellipse and slope at that point.
        int iSigma;
        switch ( iArc )
        {
        case 0:  // <(0,b),0> to <(u0,v0),-1>
            iX0++;
            iDx++;
            iSigma = iB2*iX0*iX0+iA2*(iY0-1)*(iY0-1)-iA2*iB2;
            if ( iSigma >= 0 )
            {
                iY0--;
                iDy--;
            }
            if ( iB2*iX0 >= iA2*iY0 )
            {
                // Slope dy/dx is no longer between 0 and -1.  Switch to next
                // arc drawer.  For large a and b, you expect to go to
                // 'iArc = 1'.  But for small a or b, it is possible that the
                // next arc is so small (on the discrete raster) that it is
                // skipped.
                if ( iY0 > 0 )
                    iArc = 1;
                else
                    iArc = 2;
            }
            break;
        case 1:  // <(u0,v0),-1> to <(a,0),infinity>
            iY0--;
            iDy--;
            iSigma = iB2*iX0*iX0+iA2*iY0*iY0-iA2*iB2;
            if ( iSigma < 0 )
            {
                iX0++;
                iDx++;