Triangle scanline problems

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 11, 2007 at 14:51

Hi it’s my first post on DevMaster forum. Im writing software rasterizer and i’m stuck with problem of duplicated pixels on shared vertex positions. I’ve writed the same algorithm with floats and fixed values. With both i’ve got duplicated pixels at vertex positions, i can’t end with scanline algorithm that don’t suffer from that problem.

Here is code for float version:

void gpSurfaces::DrawTriangle(gpVec2f p1, gpVec2f p2, gpVec2f p3, ULONG color)
{
    if (p1[0] == p2[0] && p2[0] == p3[0]) return;
    if (p1[1] == p2[1] && p2[1] == p3[1]) return;

    {
        // 1 - points 1, 2 x
        // 2 - points 1, 2 y
        // 3 - points 1, 3 x
        // 4 - points 1, 3 y
        // 5 - points 2, 3 x
        // 6 - points 2, 3 y
        char choosen;
        float dx12, dx13, dx23, dy12, dy13, dy23, biggest;
        dx12 = fabs(p1[0]-p2[0]);
        dx13 = fabs(p1[0]-p3[0]);
        dx23 = fabs(p2[0]-p3[0]);
        dy12 = fabs(p1[1]-p2[1]);
        dy13 = fabs(p1[1]-p3[1]);
        dy23 = fabs(p2[1]-p3[1]);

        choosen = 1;
        biggest = dx12;

        if (dx13 > dx12)
        {
            if (dx23 > dx13)
            {
                biggest = dx23;
                choosen = 5;
            }
            else
            {
                biggest = dx13;
                choosen = 3;
            }
        }
        else
            if (dx23 > dx12)
            {
                biggest = dx23;
                choosen = 5;
            }
        if (dy12 > biggest)
        {
            if (dy13 > dx12)
            {
                if (dy23 > dy13)
                {
                    biggest = dy23;
                    choosen = 6;
                }
                else
                {
                    biggest = dy13;
                    choosen = 4;
                }
            }
            else
                if (dy23 > dy12)
                {
                    biggest = dy23;
                    choosen = 6;
                }
                else
                {
                    biggest = dy12;
                    choosen = 2;
                }
        }
        else
            if (dy13 > biggest)
            {
                if (dy23 > dy13)
                {
                    biggest = dy23;
                    choosen = 6;
                }
                else
                {
                    biggest = dy13;
                    choosen = 4;
                }
            }
        float det;
        gpVec2f n, v;

        // test for cases where triangle is a line
        switch (choosen)
        {
        case 1:
            v = p2 - p3;
            n.Set(-(p2[1]-p1[1]), p2[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 2:
            v = p2 - p3;
            n.Set(-(p2[1]-p1[1]), p2[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 3:
            v = p3 - p2;
            n.Set(-(p3[1]-p1[1]), p3[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 4:
            v = p3 - p2;
            n.Set(-(p3[1]-p1[1]), p3[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 5:
            v = p3 - p1;
            n.Set(-(p3[1]-p2[1]), p3[0]-p2[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 6:
            v = p3 - p1;
            n.Set(-(p3[1]-p2[1]), p3[0]-p2[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        }
    }

    gpVec2f temp;

    // Sort: p1 = top, p2 = middle, p3 = bottom
    if(p1[1] > p3[1])
    {
        temp = p1;
        p1 = p3;
        p3 = temp;
    }
    if(p2[1] > p3[1])
    {
        temp = p2;
        p2 = p3;
        p3 = temp;
    }
    if(p1[1] > p2[1])
    {
        temp = p1;
        p1 = p2;
        p2 = temp;
    }

    bool tri_flat_top, tri_flat_bottom, tri_general;
    tri_flat_top = tri_flat_bottom = tri_general = false;
    float y1, y2, y3, fy1, fy2, fy3;
    y1 = ceil(p1[1]);
    y2 = ceil(p2[1]);
    y3 = ceil(p3[1]);
    fy1 = (ceil(p1[1]) - p1[1]);
    fy2 = (ceil(p2[1]) - p2[1]);
    fy3 = (ceil(p3[1]) - p3[1]);
    
    if (y1 == y2)
        tri_flat_top = true;
    else
        if (y2 == y3)
            tri_flat_bottom = true;
        else
            tri_general = true;
    if (tri_flat_top)
    { // flat top triangle begin
        float dy = y3-y1;
        float dxl = p3[0]-p1[0];
        float dxr = p3[0]-p2[0];
        float dxdyl = dxl / dy;
        float dxdyr = dxr / dy;
        if (dxdyl < dxdyr)
        { // flat top triangle (dxdyl > dxdyr) begin
            float tmp;
            tmp = dxdyl;
            dxdyl = dxdyr;
            dxdyr = tmp;
            int xs;
            int xe;
            float xl = p2[0] + fy2 * dxdyl;
            float xr = p1[0] + fy1 * dxdyr-1.0f;
            int ys = (int)y1;
            int ye = (int)y3;
            for (int y=0; y<ye-ys; y++)
            {
                xs = floor(xl+dxdyl*((float)y));
                xe = floor(xr+dxdyr*((float)y));
                for (int x=xs; x<=xe; x++)
                    if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                    else
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
            }
        } // flat top triangle (dxdyl > dxdyr) end
        else
        { // flat top triangle (dxdyl <= dxdyr) begin
            int xs;
            int xe;
            float xl = p1[0] + fy1 * dxdyl;
            float xr = p2[0] + fy2 * dxdyr - 1.0f;
            int ys = (int)y1;
            int ye = (int)y3;
            for (int y=0; y<ye-ys; y++)
            {
                xs = floor(xl+dxdyl*((float)y));
                xe = floor(xr+dxdyr*((float)y));
                for (int x=xs; x<=xe; x++)
                    if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                    else
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
            }
        } // flat top triangle (dxdyl <= dxdyr) end
    } // flat top triangle end
    else
        if (tri_flat_bottom)
        { // flat botoom triangle begin
            float dy = y3-y1;
            float dxl = p2[0]-p1[0];
            float dxr = p3[0]-p1[0];
            float dxdyl = dxl / dy;
            float dxdyr = dxr / dy;
            if (dxdyl > dxdyr)
            { // flat bottom triangle (dxdyl > dxdyr) begin
                float tmp;
                tmp = dxdyl;
                dxdyl = dxdyr;
                dxdyr = tmp;
                int xs;
                int xe;
                float xl = p1[0] + fy1 * dxdyl;
                float xr = p1[0] + fy1 * dxdyr - 1.0f;
                int ys = (int)y1;
                int ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = floor(xl+dxdyl*((float)y));
                    xe = floor(xr+dxdyr*((float)y));
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // flat bottom triangle (dxdyl > dxdyr) end
            else
            { // flat bottom triangle (dxdyl <= dxdyr) begin
                int xs;
                int xe;
                float xl = p1[0] + fy1 * dxdyl;
                float xr = p1[0] + fy1 * dxdyr - 1.0f;
                int ys = (int)y1;
                int ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = floor(xl+dxdyl*((float)y));
                    xe = floor(xr+dxdyr*((float)y));
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // flat bottom triangle (dxdyl <= dxdyr) end
        } // flat bottom triangle end
        else
        { // general triangle begin
            float dy1 = y2-y1;
            float dy2 = y3-y1;
            float dxl = p2[0]-p1[0];
            float dxr = p3[0]-p1[0];
            float dxdyl = dxl / dy1;
            float dxdyr = dxr / dy2;
            if (dxdyl > dxdyr)
            { // general triangle (dxdyl > dxdyr) begin
                float tmp;
                tmp = dxdyl;
                dxdyl = dxdyr;
                dxdyr = tmp;
                int xs;
                int xe;
                float xl = p1[0] + fy1 * dxdyl;
                float xr = p1[0] + fy1 * dxdyr - 1.0f;
                int ys = (int)y1;
                int ye = (int)y2;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = floor(xl+dxdyl*((float)y));
                    xe = floor(xr+dxdyr*((float)y));
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
                //xl = p1[0] + (fy1 * dxdyl) + (dy1 * dxdyl);
                float dy3 = ye-ys;
                xl = xl+dxdyl*dy3;
                dy1 = y3-y2;
                dxr = p3[0]-p2[0];
                dxdyr = dxr / dy1;
                xr = p2[0] + fy2 * dxdyr - 1.0f;
                ys = (int)y2;
                ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = floor(xl+dxdyl*((float)y));
                    xe = floor(xr+dxdyr*((float)y));
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // general triangle (dxdyl > dxdyr) end
            else
            { // general triangle (dxdyl <= dxdyr) begin
                int xs;
                int xe;
                float xl = p1[0] + fy1 * dxdyl;
                float xr = p1[0] + fy1 * dxdyr - 1.0f;
                int ys = (int)y1;
                int ye = (int)y2;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = floor(xl+dxdyl*((float)y));
                    xe = floor(xr+dxdyr*((float)y));
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
                //xr = p1[0] + (dy1 * dxdyr) + (fy1 * dxdyr);
                float dy3 = ye-ys;
                xr = xr+dxdyr*dy3;
                dy1 = y3-y2;
                dxl = p3[0]-p2[0];
                dxdyl = dxl / dy1;
                xl = p2[0] + fy2 * dxdyl;
                ys = (int)y2;
                ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = floor(xl+dxdyl*((float)y));
                    xe = floor(xr+dxdyr*((float)y));
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) != 0xFF000000)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // general triangle (dxdyl <= dxdyr) end
        } // general triangle end
}

and here is a fixed point version:

void gpSurfaces::DrawTriangle(gpVec2f p1, gpVec2f p2, gpVec2f p3, ULONG color)
{
    if (p1[0] == p2[0] && p2[0] == p3[0]) return;
    if (p1[1] == p2[1] && p2[1] == p3[1]) return;

    {
        // 1 - points 1, 2 x
        // 2 - points 1, 2 y
        // 3 - points 1, 3 x
        // 4 - points 1, 3 y
        // 5 - points 2, 3 x
        // 6 - points 2, 3 y
        char choosen;
        float dx12, dx13, dx23, dy12, dy13, dy23, biggest;
        dx12 = fabs(p1[0]-p2[0]);
        dx13 = fabs(p1[0]-p3[0]);
        dx23 = fabs(p2[0]-p3[0]);
        dy12 = fabs(p1[1]-p2[1]);
        dy13 = fabs(p1[1]-p3[1]);
        dy23 = fabs(p2[1]-p3[1]);

        choosen = 1;
        biggest = dx12;

        if (dx13 > dx12)
        {
            if (dx23 > dx13)
            {
                biggest = dx23;
                choosen = 5;
            }
            else
            {
                biggest = dx13;
                choosen = 3;
            }
        }
        else
            if (dx23 > dx12)
            {
                biggest = dx23;
                choosen = 5;
            }
        if (dy12 > biggest)
        {
            if (dy13 > dx12)
            {
                if (dy23 > dy13)
                {
                    biggest = dy23;
                    choosen = 6;
                }
                else
                {
                    biggest = dy13;
                    choosen = 4;
                }
            }
            else
                if (dy23 > dy12)
                {
                    biggest = dy23;
                    choosen = 6;
                }
                else
                {
                    biggest = dy12;
                    choosen = 2;
                }
        }
        else
            if (dy13 > biggest)
            {
                if (dy23 > dy13)
                {
                    biggest = dy23;
                    choosen = 6;
                }
                else
                {
                    biggest = dy13;
                    choosen = 4;
                }
            }
        float det;
        gpVec2f n, v;

        // test for cases where triangle is a line
        switch (choosen)
        {
        case 1:
            v = p2 - p3;
            n.Set(-(p2[1]-p1[1]), p2[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 2:
            v = p2 - p3;
            n.Set(-(p2[1]-p1[1]), p2[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 3:
            v = p3 - p2;
            n.Set(-(p3[1]-p1[1]), p3[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 4:
            v = p3 - p2;
            n.Set(-(p3[1]-p1[1]), p3[0]-p1[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 5:
            v = p3 - p1;
            n.Set(-(p3[1]-p2[1]), p3[0]-p2[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        case 6:
            v = p3 - p1;
            n.Set(-(p3[1]-p2[1]), p3[0]-p2[0]);
            det = n[0]*v[0] + n[1]*v[1];
            if (GPFLOATEQALZERO(det, 0.001f)) return;
            break;
        }
    }

    gpVec2f temp;

    // Sort: p1 = top, p2 = middle, p3 = bottom
    if(p1[1] > p3[1])
    {
        temp = p1;
        p1 = p3;
        p3 = temp;
    }
    if(p2[1] > p3[1])
    {
        temp = p2;
        p2 = p3;
        p3 = temp;
    }
    if(p1[1] > p2[1])
    {
        temp = p1;
        p1 = p2;
        p2 = temp;
    }

    bool tri_flat_top, tri_flat_bottom, tri_general;
    tri_flat_top = tri_flat_bottom = tri_general = false;
    int frac_part = 16;
    int frac_round = 0x00000;
    float mult_fixed, div_fixed;
    mult_fixed = (1 << frac_part);
    div_fixed = 1.0f / mult_fixed;
    int fy1, fy2, fy3;
    int y1, y2, y3, x1, x2, x3;
    x1 = p1[0] * mult_fixed;
    x2 = p2[0] * mult_fixed;
    x3 = p3[0] * mult_fixed;
    y1 = floorf(p1[1]);
    y2 = floorf(p2[1]);
    y3 = floorf(p3[1]);
    fy1 = ((ceil(p1[1]) - p1[1])*mult_fixed);
    fy2 = ((ceil(p2[1]) - p2[1])*mult_fixed);
    fy3 = ((ceil(p3[1]) - p3[1])*mult_fixed);
    if (y1 == y2)
        tri_flat_top = true;
    else
        if (y2 == y3)
            tri_flat_bottom = true;
        else
            tri_general = true;
    if (tri_flat_top)
    { // flat top triangle begin
        int dy = y3-y1;
        int dxl = x3-x1;
        int dxr = x3-x2;
        int dxdyl = dxl / dy;
        int dxdyr = dxr / dy;
        if (dxdyl < dxdyr)
        { // flat top triangle (dxdyl > dxdyr) begin
            int tmp;
            tmp = dxdyl;
            dxdyl = dxdyr;
            dxdyr = tmp;
            int xs;
            int xe;
            int xl = x2 + (((fy2*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
            int xr = (x1-(1 << frac_part)) + (((fy1*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
            int ys = (int)y1;
            int ye = (int)y3;
            for (int y=0; y<ye-ys; y++)
            {
                xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                for (int x=xs; x<=xe; x++)
                    if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                    else
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
            }
        } // flat top triangle (dxdyl > dxdyr) end
        else
        { // flat top triangle (dxdyl <= dxdyr) begin
            int xs;
            int xe;
            int xl = x1 + (((fy1*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
            int xr = x2-(1 << frac_part) + (((fy2*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
            int ys = (int)y1;
            int ye = (int)y3;
            for (int y=0; y<ye-ys; y++)
            {
                xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                for (int x=xs; x<=xe; x++)
                    if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                    else
                        *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
            }
        } // flat top triangle (dxdyl <= dxdyr) end
    } // flat top triangle end
    else
        if (tri_flat_bottom)
        { // flat botoom triangle begin
            int dy = y3-y1;
            int dxl = x2-x1;
            int dxr = x3-x1;
            int dxdyl = dxl / dy;
            int dxdyr = dxr / dy;
            if (dxdyl > dxdyr)
            { // flat bottom triangle (dxdyl > dxdyr) begin
                int tmp;
                tmp = dxdyl;
                dxdyl = dxdyr;
                dxdyr = tmp;
                int xs;
                int xe;
                int xl = x1 + (((fy1*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
                int xr = x1-(1 << frac_part) + (((fy1*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
                int ys = (int)y1;
                int ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                    xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // flat bottom triangle (dxdyl > dxdyr) end
            else
            { // flat bottom triangle (dxdyl <= dxdyr) begin
                int xs;
                int xe;
                int xl = x1 + (((fy1*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
                int xr = x1-(1 << frac_part) + (((fy1*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
                int ys = (int)y1;
                int ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                    xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // flat bottom triangle (dxdyl <= dxdyr) end
        } // flat bottom triangle end
        else
        { // general triangle begin
            int dy1 = y2-y1;
            int dy2 = y3-y1;
            int dxl = x2-x1;
            int dxr = x3-x1;
            int dxdyl = dxl / dy1;
            int dxdyr = dxr / dy2;
            if (dxdyl > dxdyr)
            { // general triangle (dxdyl > dxdyr) begin
                int tmp;
                tmp = dxdyl;
                dxdyl = dxdyr;
                dxdyr = tmp;
                int xs;
                int xe;
                int xl = x1  + (((fy1*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
                int xr = x1-(1 << frac_part) + (((fy1*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
                int ys = (int)y1;
                int ye = (int)y2;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                    xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
                xl = x1 + (((((dy1<<frac_part)+fy1)*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
                dy1 = y3-y2;
                dxr = x3-x2;
                dxdyr = dxr / dy1;
                xr = x2-(1<<frac_part) + (((fy2*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
                ys = (int)y2;
                ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                    xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // general triangle (dxdyl > dxdyr) end
            else
            { // general triangle (dxdyl <= dxdyr) begin
                int xs;
                int xe;
                int xl = x1 + (((fy1*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
                int xr = x1-(1 << frac_part) + (((fy1*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
                int ys = (int)y1;
                int ye = (int)y2;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                    xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
                xr = x1-(1 << frac_part) + (((((dy1<<frac_part)+fy1)*div_fixed) * (dxdyr*div_fixed))*mult_fixed);
                dy1 = y3-y2;
                dxl = x3-x2;
                dxdyl = dxl / dy1;
                xl = x2 + (((fy2*div_fixed) * (dxdyl*div_fixed))*mult_fixed);
                ys = (int)y2;
                ye = (int)y3;
                for (int y=0; y<ye-ys; y++)
                {
                    xs = ((xl + dxdyl * y) + frac_round) >> frac_part;
                    xe = ((xr + dxdyr * y) + frac_round) >> frac_part;
                    for (int x=xs; x<=xe; x++)
                        if (*(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) == 0xFFFFFFFF)
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = 0xFFFF0000;
                        else
                            *(m_secbufs.m_bufs[m_activebuffer]->m_scanlines[ys+y]+x) = color;
                }
            } // general triangle (dxdyl <= dxdyr) end
        } // general triangle end
}

the important part is after sorting, in both versions duplicated pixels occurs when triangles share vertex, but dont share edge, and i think that is the only case, in fixed version triangle looks like it is shaking a little when rotating and i dont want that effect, i think that more precision is needed, but for more precision i should use 64 bit integers, and that is not what i really want to do. I hope that someone help me to fix the problem of float version(switching from float to double doesn’t fix the problem, i’ve tested it), cause i think fixed version just need more bits.

Thanks for any help.

11 Replies

Please log in or register to post a reply.

8563f7b73aeb34bb8604f1dd8f546c88
0
Mattias_Gustavsson 101 Dec 11, 2007 at 15:42

You need to have a fill convention, such as don’t draw the last pixel of a scanline.

There’s a software rasterizer in my graphics lib, source is available to download from here:

http://www.colossusentertainment.com/DevelopmentStuff/PixieGameEngine.html

And here’s the file doing the rasterization

http://www.colossusentertainment.com/pixiedocs/_s_w_r___rasterizer_8cpp-source.html

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 11, 2007 at 16:30

I have the fill convention, duplicated pixels are only on vertex positions, when 2 triangles share this vertex, but don’t share edge, there are no duplicats when i’m drawing two triangles with shared edge(no duplicats between them). Your code do rounding at input, so you lost fractional part’s and your triangle will be shaking in motion, ive not implemented your code, but i know that, because i’ve tried that solution too.

I’ve got idea to do edge test on every scanline to make sure that pixels are really inside triangle, something like scanline/edge test hybrid algorithm.

// EDIT I’m starting to think that doing perfect scanline triangle rasterization on floats or 32-bit fixed point values is impossible.

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Dec 11, 2007 at 19:16

It is not impossible. It’s relative easy if you know how to do it.

Your triangle rasterizer is way to complex and has a lot of special cases that you don’t need to handle. I suggest you have a look at the code I posted some month ago:

http://www.devmaster.net/forums/showthread.php?t=8934

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 11, 2007 at 20:30

Thanks for replies, Nils i saw your code before, after your post i’ve implemented your code in my rasterizer and it looks great, however doesn’t it use int64? :]

That code is hard to understand at first look, i must just spend some time at it.

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 11, 2007 at 21:08

I understand now how your code works, is it possible to do the same thing but with fixed points as int32?

Sorry for 2 posts, it was mistakenly.

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Dec 11, 2007 at 22:22

@neodemon

I understand now how your code works, is it possible to do the same thing but with fixed points as int32?

Sure. The 64 bit integers are only used during setup. The rest is doing 16.16 fixed point arithmetic with 32 bit integers, so no 64 bit stuff in the inner loops.

If you don’t like the 64 bit math you can do the 64 bit multiply and divides using 32 bit arithmetic instead. That’s the way the compiler does it internally if no 64 bit multiplier and dividers are available.

You could as well simply reduce the precision until all math fits into 32 bit. 12.4-format would be my choice. 4 bits of subpixel precision has been good enough for nvidia and ati for years :-)

Nils

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 11, 2007 at 23:10

@Nils Pipenbrinck

If you troodon like the 64 bit math you can do the 64 bit multiply and divides using 32 bit arithmetic instead. That’s the way the compiler does it internally if no 64 bit multiplier and dividers are available.

You mean writing my own arithmetic functions that will hold result of 32bit * 32bit operation in two 32-bit integer variables?

Two more questions:
1. Does your code rasterize only CCW triangles?
2. In sDiv64Save function doesn’t it should be “if (b < 65536)” instead of “if (b <=65536)”, because 65536 = 1, and if b=1 then you should return a, no need to any calculation - n/1 = n

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Dec 12, 2007 at 00:25

65536 == 0, not 1, in 16-bit arithmetic.

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 12, 2007 at 01:12

Reedbeta - 0 = 0, 0 << 16 = still 0

(65536)dec = (10000)hex = 1 << 16, so 65536 = 1
@Nils Pipenbrinck

You could as well simply reduce the precision until all math fits into 32 bit. 12.4-format would be my choice. 4 bits of subpixel precision has been good enough for nvidia and ati for years :-) Nils

Nils you are joking with that 12.4 right? It is enough to do half space functions estimation, but not for scanline conversion 4 bits = 16, so if u for example have dx = 2, and dy = 768, then dx/dy = 0,002604…, and 0,002604 * 16 = 0,041666, so fixed point 12.4 will have zero value, it means that for change in y, x will not change at all.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Dec 12, 2007 at 02:52

@neodemon

Reedbeta - 0 = 0, 0 << 16 = still 0 (65536)dec = (10000)hex = 1 << 16, so 65536 = 1

Oh, you’re talking about 16.16 fixed point. My bad. I thought you were talking about plain old 16-bit arithmetic.

F3fc2f1bbec0935239ce8529a9b62910
0
neodemon 101 Dec 12, 2007 at 12:36

@Reedbeta

Oh, you’re talking about 16.16 fixed point. My bad. I thought you were talking about plain old 16-bit arithmetic.

Yes i was talking all the time about fixed point 32 bit integers, little misunderstanding :]

Nils today i have changed your code from fixed to floating point numbers, and it still works great, my own code must be bad, i will put there code for floating and fixed point version:

Fixed point version(Nils code, i only put all functions and structs in one function):

void DrawTriangle2(gpVec2f p1, gpVec2f p2, gpVec2f p3, unsigned long color)
{
    signed long xLeft;
    signed long xRight;
    signed long dxdy_left;
    signed long dxdy_right;

    struct Vertex
    {
        signed long   x;   // 16:16
        signed long   y;   // 16:16
        signed long   yceiled; // 0.32
    } vtx[3];

    vtx[0].x = p1[0] * 65536.0f;
    vtx[0].y = p1[1] * 65536.0f;
    vtx[1].x = p2[0] * 65536.0f;
    vtx[1].y = p2[1] * 65536.0f;
    vtx[2].x = p3[0] * 65536.0f;
    vtx[2].y = p3[1] * 65536.0f;

    int top  = 0;
    int bottom = 0;
    int left  = 1;
    int right = 2;

    if (vtx[1].y < vtx[0].y)
    {
        if (vtx[2].y < vtx[1].y)
        {
            top  = 2;
            left  = 0;
            right = 1;
        }
        else
        {
            top  = 1;
            left  = 2;
            right = 0; }
        }
    else
    {
        if (vtx[2].y < vtx[0].y)  
        {
            top  = 2;
            left  = 0;
            right = 1;
        }
        else
        {
            top  = 0;
            left  = 1;
            right = 2;
        }
    }
    if (vtx[1].y > vtx[bottom].y) bottom = 1;
    if (vtx[2].y > vtx[bottom].y) bottom = 2;

    vtx[0].yceiled = (vtx[0].y + 0xFFFF) >> 16;
    vtx[1].yceiled = (vtx[1].y + 0xFFFF) >> 16;
    vtx[2].yceiled = (vtx[2].y + 0xFFFF) >> 16;

    if (vtx[top].yceiled == vtx[bottom].yceiled) return;

    int height;
    int frac;
    __int64 aa, bb, cc;
    signed long a, b;

    height = vtx[left].y - vtx[top].y;
    if (height != 0)
    {
        frac = (vtx[top].yceiled << 16) - vtx[top].y;
        a = vtx[left].x - vtx[top].x;
        b = height;
        if (b == 65536)
            dxdy_left = a;
        else
            if (b < 65536)
            {
                cc = 0x40000000 / b;
                cc = (cc * a) >> 14;
                dxdy_left = (int)(cc & 0xFFFFFFFF);
            }
            else
            {
                aa = a;
                bb = b;
                aa <<= 16;
                aa /= bb;
                dxdy_left = (int)(aa & 0xFFFFFFFF);
            }
        a = dxdy_left;
        b = frac;
        aa = a;
        bb = b;
        cc = aa * bb;
        cc >>= 16;
        xLeft = vtx[top].x + (int)(cc & 0xFFFFFFFF);
    }

    height = vtx[right].y - vtx[top].y;
    if (height != 0)
    {
        frac = (vtx[top].yceiled << 16) - vtx[top].y;
        a = vtx[right].x - vtx[top].x;
        b = height;
        if (b == 65536)
            dxdy_right = a;
        else
            if (b < 65536)
            {
                cc = 0x40000000 / b;
                cc = (cc * a) >> 14;
                dxdy_right = (int)(cc & 0xFFFFFFFF);
            }
            else
            {
                aa = a;
                bb = b;
                aa <<= 16;
                aa /= bb;
                dxdy_right = (int)(aa & 0xFFFFFFFF);
            }
        a = dxdy_right;
        b = frac;
        aa = a;
        bb = b;
        cc = aa * bb;
        cc >>= 16;
        xRight = vtx[top].x + (int)(cc & 0xFFFFFFFF);
    }

    int middle = vtx[left].yceiled;
    if (middle > vtx[right].yceiled) middle = vtx[right].yceiled;

    for (int y=vtx[top].yceiled; y<middle; y++)
    {
        int x1 = (xLeft + 0xFFFF) >> 16;
        int x2 = (xRight + 0xFFFF) >> 16;
        //int fract = (x1<<16)-xLeft;
        for (int x=x1; x<x2; x++)
            buffer[x][y] = color;
        xLeft += dxdy_left;
        xRight += dxdy_right;
    }

    if (left == bottom)
    {
        height = vtx[bottom].y - vtx[right].y;
        if (height != 0)
        {
            frac = (vtx[right].yceiled << 16) - vtx[right].y;
            a = vtx[bottom].x - vtx[right].x;
            b = height;
            if (b == 65536)
                dxdy_right = a;
            else
                if (b < 65536)
                {
                    cc = 0x40000000 / b;
                    cc = (cc * a) >> 14;
                    dxdy_right = (int)(cc & 0xFFFFFFFF);
                }
                else
                {
                    aa = a;
                    bb = b;
                    aa <<= 16;
                    aa /= bb;
                    dxdy_right = (int)(aa & 0xFFFFFFFF);
                }
            a = dxdy_right;
            b = frac;
            aa = a;
            bb = b;
            cc = aa * bb;
            cc >>= 16;
            xRight = vtx[right].x + (int)(cc & 0xFFFFFFFF);
        }
    }
    else
    {
        height = vtx[bottom].y - vtx[left].y;
        if (height != 0)
        {
            frac = (vtx[left].yceiled << 16) - vtx[left].y;
            a = vtx[bottom].x-vtx[left].x;
            b = height;
            if (b == 65536)
                dxdy_left = a;
            else
                if (b < 65536)
                {
                    cc = 0x40000000 / b;
                    cc = (cc * a) >> 14;
                    dxdy_left = (int)(cc & 0xFFFFFFFF);
                } 
                else
                {
                    aa = a;
                    bb = b;
                    aa <<= 16;
                    aa /= bb;
                    dxdy_left = (int)(aa & 0xFFFFFFFF);
                }
            a = dxdy_left;
            b = frac;
            aa = a;
            bb = b;
            cc = aa * bb;
            cc >>= 16;
            xLeft = vtx[left].x + (int)(cc & 0xFFFFFFFF);
        }
    }
    for (int y=middle; y<vtx[bottom].yceiled; y++)
    {
        int x1 = (xLeft + 0xFFFF) >> 16;
        int x2 = (xRight + 0xFFFF) >> 16;
        //int fract = (x1<<16)-xLeft;
        for (int x=x1; x<x2; x++)
            buffer[x][y] = color;
        xLeft += dxdy_left;
        xRight += dxdy_right;
    }
}

floating point version:

void DrawTriangle3(gpVec2f p1, gpVec2f p2, gpVec2f p3, unsigned long color)
{
    float xLeft;
    float xRight;
    float dxdy_left;
    float dxdy_right;

    struct Vertex
    {
        float   x;   // 16:16
        float   y;   // 16:16
        int   yceiled; // 0.32
    } vtx[3];

    vtx[0].x = p1[0];
    vtx[0].y = p1[1];
    vtx[1].x = p2[0];
    vtx[1].y = p2[1];
    vtx[2].x = p3[0];
    vtx[2].y = p3[1];

    int top  = 0;
    int bottom = 0;
    int left  = 1;
    int right = 2;

    if (vtx[1].y < vtx[0].y)
    {
        if (vtx[2].y < vtx[1].y)
        {
            top  = 2;
            left  = 0;
            right = 1;
        }
        else
        {
            top  = 1;
            left  = 2;
            right = 0; }
        }
    else
    {
        if (vtx[2].y < vtx[0].y)  
        {
            top  = 2;
            left  = 0;
            right = 1;
        }
        else
        {
            top  = 0;
            left  = 1;
            right = 2;
        }
    }
    if (vtx[1].y > vtx[bottom].y) bottom = 1;
    if (vtx[2].y > vtx[bottom].y) bottom = 2;

    vtx[0].yceiled = ceil(vtx[0].y);
    vtx[1].yceiled = ceil(vtx[1].y);
    vtx[2].yceiled = ceil(vtx[2].y);

    if (vtx[top].yceiled == vtx[bottom].yceiled) return;

    float height;
    float frac;
    float a, b;

    height = vtx[left].y - vtx[top].y;
    if (height != 0)
    {
        frac = ((float)vtx[top].yceiled) - vtx[top].y;
        a = vtx[left].x - vtx[top].x;
        b = height;
        dxdy_left = a / b;
        xLeft = vtx[top].x + dxdy_left*frac;
    }

    height = vtx[right].y - vtx[top].y;
    if (height != 0)
    {
        frac = ((float)vtx[top].yceiled) - vtx[top].y;
        a = vtx[right].x - vtx[top].x;
        b = height;
        dxdy_right = a / b;
        xRight = vtx[top].x + dxdy_right*frac;
    }

    int middle = vtx[left].yceiled;
    if (middle > vtx[right].yceiled) middle = vtx[right].yceiled;

    for (int y=vtx[top].yceiled; y<middle; y++)
    {
        int x1 = ceil(xLeft);
        int x2 = ceil(xRight);
        //int fract = (x1<<16)-xLeft;
        for (int x=x1; x<x2; x++)
            buffer[x][y] = color;
        xLeft += dxdy_left;
        xRight += dxdy_right;
    }

    if (left == bottom)
    {
        height = vtx[bottom].y - vtx[right].y;
        if (height != 0)
        {
            frac = ((float)vtx[right].yceiled) - vtx[right].y;
            a = vtx[bottom].x - vtx[right].x;
            b = height;
            dxdy_right = a / b;
            xRight = vtx[right].x + dxdy_right*frac;
        }
    }
    else
    {
        height = vtx[bottom].y - vtx[left].y;
        if (height != 0)
        {
            frac = ((float)vtx[left].yceiled) - vtx[left].y;
            a = vtx[bottom].x-vtx[left].x;
            b = height;
            dxdy_left = a / b;
            xLeft = vtx[left].x + dxdy_left*frac;
        }
    }
    for (int y=middle; y<vtx[bottom].yceiled; y++)
    {
        int x1 = ceil(xLeft);
        int x2 = ceil(xRight);
        //int fract = (x1<<16)-xLeft;
        for (int x=x1; x<x2; x++)
            buffer[x][y] = color;
        xLeft += dxdy_left;
        xRight += dxdy_right;
    }
}

i made test’s for 3 rasterization algorithms, all of them drawing the same triangles, tested algorithms was two above scanline algorithms, and half-space function estimation algorithm(i dont really know if it is it’s name) - this is actually this algorithm - http://www.devmaster.net/codespotlight/show.php?id=17 , but with optimizations that are in comment’s for this article, results in seconds are:

1st time
Fixed point scanline rasterization: 0.722081
Floating point scanline rasterization: 1.013470
Half-space function rasterization: 1.735897

2nd time
Fixed point scanline rasterization: 0.666595
Floating point scanline rasterization: 1.023368
Half-space function rasterization: 1.739916

3rd time
Fixed point scanline rasterization: 0.684434
Floating point scanline rasterization: 1.015587
Half-space function rasterization: 1.737426

In that test’s drawed geometry has only 18 triangles, but that triangles were drawed about 3600 times, every time rotated about angle of 0.1 degrees, so it gives 18*3600 = 64800 triangles.