any simple blitter around? (looking for FPGA design)

[legacy]

Code: [Select]

|........................................|
|........................................|
|........................................|
|.....................................x..|
|....................................x*..|
|..................................*xx...|
|.................................*xxx...|
|................................*xxx*...|
|...............................xxxxx....|
|..............................xxxxxx....|
|............................*xxxxxx*....|
|...........................*xxxxxxx.....|
|..........................*xxxxxxxx.....|
|.........................xxxxxxxxx*.....|
|........................xxxxxxxxxx*.....|
|......................*xxxxxxxxxxx......|
|.....................*xxxxxxxxxxx*......|
|....................*xxxxxxxxxxxx*......|
|...................xxxxxxxxxxxxxx.......|
|..................xxxxxxxxxxxxxx*.......|
|................*xxxxxxxxxxxxxxx*.......|
|...............*xxxxxxxxxxxxxxxx........|
|..............*xxxxxxxxxxxxxxxxx........|
|.............xxxxxxxxxxxxxxxxxx*........|
|............xxxxxxxxxxxxxxxxxxx.........|
|..........*xxxxxxxxxxxxxxxxxxxx.........|
|.........*xxxxxxxxxxxxxxxxxxxx*.........|
|........*xxxxxxxxxxxxxxxxxxxxx..........|
|.......xxxxxxxxxxxxxxxxxxxxxxx..........|
|......xxxxxxxxxxxxxxxxxxxxxxx*..........|
|....*xxxxxxxxxxxxxxxxxxxxxxxx*..........|
|...*xxxxxxxxxxxxxxxxxxxxxxxxx...........|
|..xxxxxxxxxxxxxxxxxxxxxxxxxx*...........|
|....**xxxxxxxxxxxxxxxxxxxxxx*...........|
|........**xxxxxxxxxxxxxxxxxx............|
|............**xxxxxxxxxxxxx*............|
|................**xxxxxxxxx*............|
|....................**xxxxx.............|
|........................**x.............|
|........................................|

so, digging into the GE of the consoles made in the 90s, I 've found another way to fill the triangle by a module able to determine whether a point is "on", "above" or "below" a line, defined by 2 points; The module uses two multipliers, several adders, and combinational logic, and three of these modules are used to determine which side of the line formed by 2 of the vertices of the triangle the third point is on. By doing this for all three vertices, a set of three sides is used by the line finders in the drawing stage to check if the processed pixel is also on the same side of the three lines as the third point, and, If this is true for all the vertices of the triangle, the point is within it.

bits market as '*' represent the correct outline of the triangle
bits market as 'x' represent the output of the new module

pro: it doesn't require a table, and it's fast
con: it doesn't interpolate, and it's a bit defective on borders since it loses some bits.

[legacy]

bits market as '*' represent the correct outline of the triangle
bits market as 'x' represent the output of the new module

I have pre-drawn the outline of the triangle with the correct method, and then over the same bitplane, I allowed the new module to redraw, and you can see it eats some bits, but not all the bits of the outline.

I have to investigate for the reason for this 

[BrianHG]

Code: [Select]

|........................................|
|........................................|
|........................................|
|.....................................x..|
|....................................x*..|
|..................................*xx...|
|.................................*xxx...|
|................................*xxx*...|
|...............................xxxxx....|
|..............................xxxxxx....|
|............................*xxxxxx*....|
|...........................*xxxxxxx.....|
|..........................*xxxxxxxx.....|
|.........................xxxxxxxxx*.....|
|........................xxxxxxxxxx*.....|
|......................*xxxxxxxxxxx......|
|.....................*xxxxxxxxxxx*......|
|....................*xxxxxxxxxxxx*......|
|...................xxxxxxxxxxxxxx.......|
|..................xxxxxxxxxxxxxx*.......|
|................*xxxxxxxxxxxxxxx*.......|
|...............*xxxxxxxxxxxxxxxx........|
|..............*xxxxxxxxxxxxxxxxx........|
|.............xxxxxxxxxxxxxxxxxx*........|
|............xxxxxxxxxxxxxxxxxxx.........|
|..........*xxxxxxxxxxxxxxxxxxxx.........|
|.........*xxxxxxxxxxxxxxxxxxxx*.........|
|........*xxxxxxxxxxxxxxxxxxxxx..........|
|.......xxxxxxxxxxxxxxxxxxxxxxx..........|
|......xxxxxxxxxxxxxxxxxxxxxxx*..........|
|....*xxxxxxxxxxxxxxxxxxxxxxxx*..........|
|...*xxxxxxxxxxxxxxxxxxxxxxxxx...........|
|..xxxxxxxxxxxxxxxxxxxxxxxxxx*...........|
|....**xxxxxxxxxxxxxxxxxxxxxx*...........|
|........**xxxxxxxxxxxxxxxxxx............|
|............**xxxxxxxxxxxxx*............|
|................**xxxxxxxxx*............|
|....................**xxxxx.............|
|........................**x.............|
|........................................|

so, digging into the GE of the consoles made in the 90s, I 've found another way to fill the triangle by a module able to determine whether a point is "on", "above" or "below" a line, defined by 2 points; The module uses two multipliers, several adders, and combinational logic, and three of these modules are used to determine which side of the line formed by 2 of the vertices of the triangle the third point is on. By doing this for all three vertices, a set of three sides is used by the line finders in the drawing stage to check if the processed pixel is also on the same side of the three lines as the third point, and, If this is true for all the vertices of the triangle, the point is within it.

bits market as '*' represent the correct outline of the triangle
bits market as 'x' represent the output of the new module

pro: it doesn't require a table, and it's fast
con: it doesn't interpolate, and it's a bit defective on borders since it loses some bits.

If it is significantly faster than 4x the previous method, you can operate internally at double X&Y resolution, then output.  Though, if you are painting ontop of other graphics, it now becomes valuable to maintain an at least 2 bit depth stencil so when you draw ontop of other items, you can have soft edges.

[KE5FX]

Thats Breshenans line drawing algorithm, there is also a circle drawing variant and an improved line drawing one that exploits the symmetry.

"Graphics Gems" by Glassner (Academic Press) is IMHO the bible for CPU based graphics stuff, dated by todays standards but very, very good stuff when you lack a modern graphics processor.

Regards, Dan.

Also there's Mike Abrash, whose older VGA-era books are now free. 

[hamster_nz]

Thats Breshenans line drawing algorithm, there is also a circle drawing variant and an improved line drawing one that exploits the symmetry.

"Graphics Gems" by Glassner (Academic Press) is IMHO the bible for CPU based graphics stuff, dated by todays standards but very, very good stuff when you lack a modern graphics processor.

Regards, Dan.

Also there's Mike Abrash, whose older VGA-era books are now free.

Those books (and the series of Dr Dobbs articles) were great. For those who wan't there:

- It was the at the time that Desktop OSs went from 16-bit ot 32-bit - 32-bit DOS extenders were required to run 32-but code

- It was also the time of the 486 -> Original Pentium transition, where super-scalar CPUs first hit the desktop.

- It was also the time when Graphics cards were starting to escape the VGA 320x200 8-bit graphics mode (enabled by larger address space of the 32-bit OSs)

- It was the time that First Person Shooter games first appeared (Wolf3d gave way to Doom and Descent)

Optimization from the "pretty bland" 486 code that compilers generated to the foibles of the Pentium's architecture allowed for great improvements in speed. Compilers took a while to catch up.

The rate of change was amazing to look back on.

Ah, nostalgia isn't what it used to be.

[legacy]

"Graphics Gems" by Glassner (Academic Press) is IMHO the bible for CPU based graphics stuff, dated by todays standards but very, very good stuff when you lack a modern graphics processor.

Mike Abrash

I still have to buy the Graphics Gems, I have already downloaded Mike Abrash, and I have found good hints in this book:

Real-Time Collision Detection - Christer Ericson - ott 2004

available in Kindle format, which I prefer 

it's funny to know the Sony Playstation's GTE implemented a trick, consisting of three modules in parallel of two multipliers each, plus adders, for a total of six multipliers (all is fixed-point).

But it's not clear to me how the GTE did color interpolation.

[legacy]

Code: [Select]

|........................................|
|........................................|
|........................................|
|.....................................*..|
|....................................**..|
|..................................***...|
|.................................*..*...|
|................................*...*...|
|...............................*...*....|
|..............................*....*....|
|............................**.....*....|
|...........................*......*.....|
|..........................*.......*.....|
|.........................*........*.....|
|........................*.........*.....|
|......................**.........*......|
|.....................*...........*......|
|....................*............*......|
|...................*............*.......|
|..................*.............*.......|
|................**..............*.......|
|...............*...............*........|
|..............*................*........|
|.............*.................*........|
|............*.................*.........|
|..........**..................*.........|
|.........*....................*.........|
|........*....................*..........|
|.......*.....................*..........|
|......*......................*..........|
|....**.......................*..........|
|...*........................*...........|
|..**........................*...........|
|....****....................*...........|
|........****...............*............|
|............****...........*............|
|................****.......*............|
|....................****..*.............|
|........................***.............|
|........................................|

well, the triangle filler trick is fast, nice and neat, but it is defective at drawing just the edge, hence I am back to the pipe of with three line-filler-modules in parallel; each module computes one edge of the triangle, and the whole doesn't fill anything, it just draws the triangle's edge.

I have modified the HDL simulator to show the bitplane at each step, also showing if a blitter unit has completed the job, and the whole process stops when all the blitters have completed their job.

and here it is the output of the simulator, you can see how it evolves

[legacy]

Code: [Select]

Benchmark data: Pentium III 450Mhz, Visual C++ 6.0 Release Build, Optimizations on...

Algorithm         Lines Drawn (x1000)   Seconds     Lines Per Second
DDA               1600                  529.101      3023.997
Bresenham         1600                   83.220     19226.147
Wu                1600                   75.949     21066.767
EFLA Variation D  1600                   65.914     24274.053


so, on google group, there was this discussion on the world's fastest line algorithm, and it seems EFLA beats the Wu and Bresenham algorithms 

[T3sl4co1l]

Funny, doing it with fixed point ("EFLA") is exactly equivalent to Bresenham's, the latter is just normally written as a conditional check.

Apparently changing a branch instruction to a carry instruction counts as novel enough to license a half page of code?  Well, I bet they aren't selling many, anyway...

Tim

[KE5FX]

Funny, doing it with fixed point ("EFLA") is exactly equivalent to Bresenham's, the latter is just normally written as a conditional check.

They aren't actually 100% equivalent.  A straightforward fixed-point solution will never write more than one pixel at each coordinate on the major axis, so it won't add an extra pixel at the stairstep when the direction changes.  This will result in a less "solid"-appearing line compared to what you get from a classical Bresenham implementation. 

It doesn't usually matter that much, but a naive polygon-fill routine might rely on that extra pixel to fill in holes at T-junctions.

Apparently changing a branch instruction to a carry instruction counts as novel enough to license a half page of code?  Well, I bet they aren't selling many, anyway...

Tim

Yeah, that's pretty funny.  Somebody hasn't read their Abrash.

[T3sl4co1l]

I've never seen a plain line drawing algorithm implemented with doubling up of pixels at minor-axis steps, of course if you want to do it that way you can.

Whether poly fills will "leak" simply depends on if they use a von Neumann / Moore neighborhood.

Tim

[KE5FX]

I've never seen a plain line drawing algorithm implemented with doubling up of pixels at minor-axis steps, of course if you want to do it that way you can.

The distinction is known as "4-connected" versus "8-connected", although I never encountered that terminology before I Googled it just now.

Whether poly fills will "leak" simply depends on if they use a von Neumann / Moore neighborhood.

More terms I had to look up -- but I think we're referring to the same thing. 



Of course, relying on 8-connectivity to fix T-junctions is going to cause endless grief when you introduce alpha blending into the equation.  AFAIK there is really no substitute for fixing T-junctions at the geometry stage rather than the rasterizer.

[legacy]

So, yesterday night I wanted to check if better solutions exist for drawing a line, and I ended up by confirming the Bresenham's algorithm because it's the best (in terms of simplicity and efficiency) to be rewritten in VHDL.

as proof of concept, this is the last C prototype

Code: [Select]

void gfx_draw_line_bresenham
(
    uint32_t x0,
    uint32_t y0,
    uint32_t x1,
    uint32_t y1,
    color_rgb_t color
)
{
    sint32_t  dx;
    sint32_t  dy;
    uint32_t  x;
    uint32_t  y;
    sint32_t  sx;
    sint32_t  sy;
    sint32_t  err;
    sint32_t  magic;
    boolean_t is_done;

    /*
     * bounding box's width and height
     * set the loop's sign
     */
    dx = x1 - x0;
    dy = y1 - y0;
    if (dx < 0)
    {
        dx = -dx;
        sx = -1;
    }
    else
    {
        sx = 1;
    }
    if (dy > 0)
    {
        dy = -dy;
        sy = 1;
    }
    else
    {
        sy = -1;
    }

    magic = 0;
    err   = dx + dy;
    x     = x0;
    y     = y0;

    is_done = False;
    while (is_done isEqualTo False)
    {
        /*
         * plot(x, y,color);
         */
        pixel_set_xy(x, y,color);

        /*
         * Reached the end
         */
        is_done = ((x isEqualTo x1) logicalAnd(y isEqualTo y1));

        /*
         * Loop carried
         */
        magic = err shiftLeft 1;
        if (magic > dy)
        {
            err += dy;
            x   += sx;
        }
        if (magic < dx)
        {
            err += dx;
            y   += sy;
        }
    }
}


This algorithm is good, neat, fast, and it doesn't use any MUL or DIV for the setup, and it can be implemented in three or four units to calculate points in parallel.

This algorithm is good, neat, fast, and it doesn't use any MUL or DIV for the setup, and it can be implemented in three or four units to calculate points in parallel.

The SONY Playstation's GTE has four units of this kind (it's not specified which algorithm is used) to draw up to four lines in parallel once given vertices.

A defect of this algorithm (or of this implementation) is that it cannot handle any cases where the line endpoints do not lie exactly on integer points of the pixel grid: in this case, either it eats the pixel or it adds an extra pixel. This little bad effect has been shown by the edges calculated by the previous method I used where the algorithm tests directly the points using a test-in-polygon. There are marginal differences on the edges, but it's acceptable.

Definitively: approved 

[DJohn]

You should read Fabian Giesen's series "A Trip Through the Graphics Pipeline (2011)" https://fgiesen.wordpress.com/2011/07/09/a-trip-through-the-graphics-pipeline-2011-index/.  And definitely follow the links.  This is how it's done in real hardware.

[legacy]

I have done a ton of personal research for a new algorithm, and I have developed my own, again with pro and con.

pro: it interpolates, and it's extremely faster since it removes MULs during the loop, it only uses ADDs, that speeds up a lot
con: it adds 12 MULs and 3 DIVs for the initialization of the context, and it's numerically weak

I am still with the C prototype, I haven't implemented it yet on HDL, and I am with fixedpoint16.16, but this is critical

Code: [Select]

        /*
         * step2
         * 1/2 is added as a workaround
         * to compensate the numerical error
         * caused by the loss of bits that are
         * amplified by step3 and during the loop
         */
        color_v[0] = fx1616_add_fp(color_v[0], 0.5);
        color_v[0] = fx1616_add_fp(color_v[1], 0.5);
        color_v[0] = fx1616_add_fp(color_v[2], 0.5);
        color_v[0] = fx1616_div(color_v[0], scale);
        color_v[1] = fx1616_div(color_v[1], scale);
        color_v[2] = fx1616_div(color_v[2], scale);


Code: [Select]

        /*
         * step3
         */
        magic_TW_0 = fx1616_mul(magic_TW_0, color_v[0]);
        magic_TW_1 = fx1616_mul(magic_TW_1, color_v[1]);
        magic_TW_2 = fx1616_mul(magic_TW_2, color_v[2]);
        magic_U_12 = fx1616_mul(magic_U_12, color_v[0]);
        magic_U_20 = fx1616_mul(magic_U_20, color_v[1]);
        magic_U_01 = fx1616_mul(magic_U_01, color_v[2]);
        magic_W_12 = fx1616_mul(magic_W_12, color_v[0]);
        magic_W_20 = fx1616_mul(magic_W_20, color_v[1]);
        magic_W_01 = fx1616_mul(magic_W_01, color_v[2]);

life is complex