any simple blitter around? (looking for FPGA design)

[legacy]

Code: [Select]

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


Code: [Select]

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


Code: [Select]

|........................................|
|........................................|
|........................................|
|..-----------------------------------+..|
|..----------------------------------+-..|
|..---------------------------------++-..|
|..----------------------------------+-..|
|..------------------------------------..|
|..-----------------------------+---+--..|
|..----------------------------+----+--..|
|..---------------------------+--@-----..|
|..-----------------------------@--+---..|
|..----------------------------@@--+---..|
|..-----------------------+---@@@------..|
|..----------------------+--@@@@-------..|
|..---------------------+--@@@@@--+----..|
|..-----------------------@@@@@@-------..|
|..----------------------@@@@@@@-------..|
|..-----------------+---@@@@@@@--+-----..|
|..----------------+--@@@@@@@@@--------..|
|..---------------+--@@@@@@@@@@--------..|
|..-----------------@@@@@@@@@@--+------..|
|..----------------@@@@@@@@@@@--+------..|
|..-----------+--@@@@@@@@@@@@@---------..|
|..----------+--@@@@@@@@@@@@@--+-------..|
|..---------+--@@@@@@@@@@@@@@--+-------..|
|..-----------@@@@@@@@@@@@@@@----------..|
|..----------@@@@@@@@@@@@@@@--+--------..|
|..-----+--@@@@@@@@@@@@@@@@@--+--------..|
|..----+--@@@@@@@@@@@@@@@@@@-----------..|
|..---+----@@@@@@@@@@@@@@@@------------..|
|..------------@@@@@@@@@@@@--+---------..|
|..-+--------------@@@@@@@@------------..|
|..----++--------------@@@-------------..|
|..---------+---------------+----------..|
|..------------++----------------------..|
|..----------------++------------------..|
|..--------------------++--+-----------..|
|..------------------------------------..|
|........................................|


Code: [Select]

|........................................|
|........................................|
|........................................|
|..------------------------------------..|
|..----------------------------------2-..|
|..---------------------------------22-..|
|..--------------------------------222-..|
|..-------------------------------222--..|
|..-----------------------------22222--..|
|..----------------------------+22222--..|
|..---------------------------+++@++---..|
|..--------------------------+++@+++---..|
|..-------------------------+++@@+++---..|
|..-----------------------++++@@@++----..|
|..----------------------+++@@@@+++----..|
|..---------------------+++@@@@@+++----..|
|..--------------------+++@@@@@@++-----..|
|..-------------------+++@@@#@@@++-----..|
|..-----------------++++@@@##@@+++-----..|
|..----------------+++@@@###@@@++------..|
|..---------------+++@@@####@@@++------..|
|..--------------+++@@@#####@@+++------..|
|..-------------+++@@@#####@@@+++------..|
|..-----------+++@@@@######@@@++-------..|
|..----------+++@@@########@@+++-------..|
|..---------+++@@@########@@@+++-------..|
|..--------+++@@@#########@@@++--------..|
|..-------+++@@@##########@@+++--------..|
|..-----11+@@@@@@@#######@@@+++--------..|
|..----111@@@@@@@@@@@@###@@@++---------..|
|..---111++@@@@@@@@@@@@@@@@+++---------..|
|..--1111++++++@@@@@@@@@@@@+++---------..|
|..-11111++++++++++@@@@@@@@+0----------..|
|..----1+++++++++++++++@@@+00----------..|
|..---------++++++++++++++000----------..|
|..------------++++++++++000-----------..|
|..----------------+++++0000-----------..|
|..--------------------00000-----------..|
|..------------------------------------..|
|........................................|


Code: [Select]

------------------[screen]------------------
|........................................|
|........................................|
|........................................|
|..----------------------------------- ..|
|..---------------------------------- -..|
|..---------------------------------  -..|
|..--------------------------------   -..|
|..-------------------------------   --..|
|..-----------------------------     --..|
|..----------------------------      --..|
|..---------------------------      ---..|
|..--------------------------       ---..|
|..-------------------------        ---..|
|..-----------------------         ----..|
|..----------------------          ----..|
|..---------------------           ----..|
|..--------------------           -----..|
|..-------------------            -----..|
|..-----------------              -----..|
|..----------------              ------..|
|..---------------               ------..|
|..--------------                ------..|
|..-------------                 ------..|
|..-----------                  -------..|
|..----------                   -------..|
|..---------                    -------..|
|..--------                    --------..|
|..-------                     --------..|
|..-----                       --------..|
|..----                       ---------..|
|..---                        ---------..|
|..--                         ---------..|
|..-                         ----------..|
|..----                      ----------..|
|..---------                 ----------..|
|..------------             -----------..|
|..----------------         -----------..|
|..--------------------     -----------..|
|..------------------------------------..|

I have found, already implemented, simulated and synthesized an interpolation method to
- identify points inside the triangle
- identify points outside the triangle
- interpolate colors among three vertices

the implementation takes
- 12 MULs in parallel
- 3 DIVs in parallel
- 80 clock's ticks to compute a point

[BrianHG]

- 3 DIVs in parallel
- 80 clock's ticks to compute a point

What are the divs for?  You should be able to do everything with add/sub/multiply.
You may have a delay of a few clocks, like 4 to 8, until the first point, but then every single clock should then create a new point.

With divs, this should only add around 10 more clocks until the first new point, but then, once again, a new point should be coming out every single clock.

Waiting 80 clocks for a point, the another 80 for the next in an FPGA?  You would do much better with a cheap DS-Pic MCU.

[legacy]

What are the divs for?

to solve the last stage of the system of three linear equations to interpolate a point(x,y) inside/outside the triangle, you need to normalize the barycentric vector in order to find the correct RGB color of the final; the dividend to do that is not a precomputable constant, hence you need div.

[Bruce Abbott]

I have found, already implemented, simulated and synthesized an interpolation method to
- identify points inside the triangle
- identify points outside the triangle
- interpolate colors among three vertices

What exactly do the 5 ascii diagrams represent?

[legacy]

What exactly do the 5 ascii diagrams represent?

It's the local buffer memory x-y of the pixel plane with a poor resolution of color since I am only representing white, black, and a couple of tone of grey. In a real device, it would be DMA-copied into the framebuffer as soon as the whole "le'ts trace and fill a triangle with interpolation" process ends.

It's used in the HDL simulation, and it's one of the outputs from the test-bench, but I am willing to develop a module for GNU-plot to have x11-support and colors.

[legacy]

Now I have a different circuit, definitely simpler and smaller, but also able unable to interpolate color-pixels, it just fills a triangle with a solid color as fast as it can.

it's composed by
- a circuit that calculates the min(x,y) set of points of the triangle
- three line-fillers in parallel and each line-filler fills a table
- a horizontal line-filler that use the table as input


accordingly:
- you give the vertices v1(x,y), v2(x,y), v3(x,y) of the triangle, coordinates are positive numbers)
- the first stage calculates y.min as min({ v1.y, v2.y, v3.y })
 - the line-filler1 draws line { v1-v2 }, for each calculated point {x,y} it fills table[y-y.min]={x,_,_}
- the line-filler2 draws line { v2-v3 }, for each calculated point {x,y} it fills table[y-y.min]={_,x,_}
- the line-filler3 draws line { v3-v1 }, for each calculated point {x,y} it fills table[y-y.min]={_,_,x}
- line-fillers work in paralel, and this draws the outline of the triangle
- once completed, the last circuit scans the table, finds x_start,x_stop, and it draws horizontal lines

each table line or is empty, or it always only shows these configurations

Code: [Select]

table[i]={x'1,x'2,__} <--- v1-v2: x_start=x'1, x_stop=x'2, y=i+y.min
table[i]={x'1,__,x'3} <--- v3-v1: x_start=x'1, x_stop=x'3, y=i+y.min
table[i]={__,x'2,x'3} <--- v3-v1: x_start=x'2, x_stop=x'3, y=i+y.min

x'1 means x-point calculated by the line-filler1
x'2 means x-point calculated by the line-filler2
x'3 means x-point calculated by the line-filler3


pro: damn faster, it takes a max of 3 clocks per pixel, and the implementation takes less area
con: it requires an internal buffer for the table, and circuits to clear/set it, it doesn't interpolate pixel-colors

[Gribo]

Can't you do the color interpolation in the line drawing step? I assume all 3 lines have the same color.

[legacy]

I assume all 3 lines have the same color.

correct 

indeed this algorithm is simpler and faster, but can't do color-interpolation; vertices can only be of the same color and the triangle can only be filled with a solid color

[BrianHG]

You can think of it as 2 different steps.  Use your existing line filler.  Feed that output coordinates to a colorizer module which uses a blend of the set colors at outer coordinates of the triangle based on location to create a final paint color.

I still don't see why this step needs any divides inside the filler, they are just needed 1 shot in the setup to create the X&Y transition/vs/position factors.  (You may be approaching the colorizing math in a different way than I am...)  I created a full 2D video scaling system with bilinear and bicubic video scaling and blending without any divides in any of the color processing.  The only divides where used in the setup, computed once by a CPU, to initialize the geometry for the graphics rendering system.  The rendering system was totally based on multiply, add, and, bit shifting.

[legacy]

Feed that output coordinates to a colorizer module which uses a blend of the set colors at outer coordinates of the triangle based on location to create a final paint color

in my previous algorithm, a vertex was defined by position (x,y), and color.

the line-filler is not aware of the color, it's only able to calculate line's pixels. To describe the pixel's color you need to know the propagation of the color made by each vertex, hence you need an interpolator.

[legacy]

the interpolator needs to solve a system of three linear equations
how do you solve A x = b ?

- by Crammer?
- by Gauss-Jordan Elimination?
- by Gauss-Seidel ?
- by Jacobi?
- by LU-Factorization?
- ...?

[BrianHG]

Feed that output coordinates to a colorizer module which uses a blend of the set colors at outer coordinates of the triangle based on location to create a final paint color

in my previous algorithm, a vertex was defined by position (x,y), and color.

the line-filler is not aware of the color, it's only able to calculate line's pixels. To describe the pixel's color you need to know the propagation of the color made by each vertex, hence you need an interpolator.

I was thinking of a linear blend with 4 RGB/YUV references from 4 coordinates on the screen.  One method, the position X/Y sent from your vertex algorithm, of the screen's coordinates determines what weight of each of the 4 screen coordinates reference colors to blend together.  When using a triangle, the first 3 are taken from the triangles corners and the 4th, finalizing a rectangle of that triangle, is interpreted.  You can also deliberately mess with the RGB values in the fourth imaginary point to create an illusion of a shadow or light source towards the center of the triangle.

All the math would be geared so that your fractions results are first multiplied, then divided by 65536, either before or after the summing depending on the number of bits you want your adders to be.  All fractions are actually also integers / 65536.  The goal is to get everything done in 1-2 clock operations avoiding true division at all costs.  If you are using a huge FPGA with nice pipelined fixed 5-6 clock floating point multiply/divide, then, divide away!

However, this is a simple fast implementation for a small FPGA.  You will not get fancy non-linear filtering effects this way unless you implement curved lookup-tables, or, apply full floating point mathematics.

[legacy]

what weight of each of the 4 screen coordinates reference colors to blend together

and to do that, you need to solve a system of linear equations, hence an interpolator whose implementation intrinsically needs a division unit.

[legacy]

nice pipelined fixed 5-6 clock floating point multiply/divide

currently, I have implemented my own algorithm to multiply and divide fixed-point 32bit numbers with saturation. This algorithm does never overflow but it's not pipelined, it takes 1 clock cycle per bit, hence 32 clocks to complete the MUL/DIV. They are both required to solve the system of linear equations, for whose implementation I am using a modified version of Jacobi.

The simplicity of the MUL-DIV unit (in term of VHDL code) is both good and bad: good, because it is relatively easy to understand and simulate; bad, because it is not typically good performant in practice if compared to faster MUL-DIV unit, e.g. a pipelined version (the link offers a good example of 16 bit pipelined MUL for Xilinx FPGAs)

I have two FGPAs in my system, the first implements a Softcore, the second is dedicated to graphics, but a good point, I could recycle the Jacobi unit currently used for the blitter, making it available for the Softcore to compute a generic(1) system of linear equations.

This needs a redesign of resources, but it would be nice 

(1) generic? well ... not so confident it could be used for a general purpose algebra engine ... the original Jacobi's prerequisite for the convergence is that the matrix A is a diagonally dominant matrix for the problem A x = b. This is a sufficient but not necessary condition for the method to converge, hence I have modified the algorithm to estimate the best initial condition possible, and then to accelerate the convergence (in term of the number of interactions), and practically, for the interpolation problem, it seems converging very fast even if the Jacobi's prerequisite conditions are not satisfied. The interpolator has some particular characteristic in its matrix A, and the trick works, but the algorithm might blow up for other kinds of matrix A 

[BrianHG]

what weight of each of the 4 screen coordinates reference colors to blend together

and to do that, you need to solve a system of linear equations, hence an interpolator whose implementation intrinsically needs a division unit.

Are you talking about working out the necessary weights based on relative XY drawing coordinates inside the triangle?

Though there is a bit of trickery to generate the 4 weights, it can be done using the fractional integer m.n math trick.

Since I didn't generate your triangle fill algorithm,  I cannot see if your code can keep track of the fractional location inside the triangle going from 0/65535 (at triangles first left edge coordinates) to 65535/65535 (at the triangle's right edge coordinates).  (same thin for top and bottom coordinates)  Since every time I move a pixel on my raster scan fill, I can subtract either part of my main coordinate counters, or as part of separate fractional counters creating a floating point subtract dot by dot, or, line by line, which is exactly what a divide is, yet, no wasteful divide function.  These 4 fractional counters hold the 'weights' and using the top 8 bits of them when mixed with the appropriate RGB references at the ends of each line once again only requires an 8bit X 8bit integer number multiply, then use the top 8 bits of the 16 bit result.

(This is an example, I'm using RGB as a 3 8 bit integer matrix, the weight# would be identical for each color channel)
(1 clock example, slow FMAX)

Code: [Select]

RGB_out <= ((weight1 * RGB_point1) << 8) + ((weight2 * RGB_point2) << 8) + ((weight3 * RGB_point3) << 8) + ((weight4 * RGB_point4) << 8);
To make the FMAX top speed, like 200Mhz, each weight multiply with RGB would first be stored in a temp register, then next, you would do a 4 way add of the temps to get a final color.  Or even faster, you would have 2 by 2 way adds to 2 new temps, then a final add of those 2 temps to your results.

[BrianHG]

The first triangle-interpolator drawing algorithm was to look at every pixel in a bounding box around the triangle, then for each pixel, it calculated a vector to check if the point lies inside or outside of a triangle, and if inside, of which color it should be.

This is neat and nice, but it wastes a lot of cycles for all the pixels not lining inside the triangle 

Hence, an improvement to this comes by combining the three line-fillers in parallel to fill a table and the horizontal line-filler that use the table as input, with the interpolator.

- a circuit that calculates the min(x,y) set of points of the triangle
- three line-fillers in parallel and each line-filler fills a table
- a horizontal line-filler that use the table as input

vertices A,B,C ---> line fillers ---> table filled with the points of the triangle's outlines
triangle's outlines ---> horizontal line-filler ---> table filled with triangle's internal points
table of triangle's internal points ---> interpolator ---> bitplane(x,y,color)

Ohhhhh, you are not rendering a filled triangle beginning on each new scan line by working out the the beginning and ending coordinates of the 2 opposing edges of the triangle.  You are doing things the hard way...  Including the use of placing items into a table then reading that data back work out the fill.  And even the hassle of using multiple line fillers in parallel.  Your work must be turning into a monster...

[legacy]

The first triangle-interpolator drawing algorithm was to look at every pixel in a bounding box around the triangle, then for each pixel, it calculated a vector to check if the point lies inside or outside of a triangle, and if inside, of which color it should be.

This is neat and nice, but it wastes a lot of cycles for all the pixels not lining inside the triangle 

Code: [Select]

|........................................|
|........................................|
|........................................|
|..------------------------------------..|
|..----------------------------------2-..|
|..---------------------------------22-..|
|..--------------------------------222-..|
|..-------------------------------222--..|
|..-----------------------------22222--..|
|..----------------------------+22222--..|
|..---------------------------+++@++---..|
|..--------------------------+++@+++---..|
|..-------------------------+++@@+++---..|
|..-----------------------++++@@@++----..|
|..----------------------+++@@@@+++----..|
|..---------------------+++@@@@@+++----..|
|..--------------------+++@@@@@@++-----..|
|..-------------------+++@@@#@@@++-----..|
|..-----------------++++@@@##@@+++-----..|
|..----------------+++@@@###@@@++------..|
|..---------------+++@@@####@@@++------..|
|..--------------+++@@@#####@@+++------..|
|..-------------+++@@@#####@@@+++------..|
|..-----------+++@@@@######@@@++-------..|
|..----------+++@@@########@@+++-------..|
|..---------+++@@@########@@@+++-------..|
|..--------+++@@@#########@@@++--------..|
|..-------+++@@@##########@@+++--------..|
|..-----11+@@@@@@@#######@@@+++--------..|
|..----111@@@@@@@@@@@@###@@@++---------..|
|..---111++@@@@@@@@@@@@@@@@+++---------..|
|..--1111++++++@@@@@@@@@@@@+++---------..|
|..-11111++++++++++@@@@@@@@+0----------..|
|..----1+++++++++++++++@@@+00----------..|
|..---------++++++++++++++000----------..|
|..------------++++++++++000-----------..|
|..----------------+++++0000-----------..|
|..--------------------00000-----------..|
|..------------------------------------..|
|........................................|

points marked with '-' belong to the bounding box around the triangle but they lie outside the triangle, and the interpolator doesn't know it until it has wasted precious cycles to calculate it.

Hence, an improvement to this comes by combining the interpolator with the three line-fillers in parallel to fill a table and the horizontal line-filler that uses the table as input for the interpolation.

- a circuit that calculates the min(x,y) set of points of the triangle
- three line-fillers in parallel and each line-filler fills a table
- a horizontal line-filler that use the table as input

vertices A,B,C ---> line fillers ---> table filled with the points of the triangle's outlines
triangle's outlines ---> horizontal line-filler ---> table filled with triangle's internal points
table of triangle's internal points ---> interpolator ---> bitplane(x,y,color)

[legacy]

are you talking about working out the necessary weights based on relative XY drawing coordinates inside the triangle?

given
- three vertices { Vertex1(x,y) is color1, Vertex2(x,y) is color2, Vertex3(x,y) is color3 }
- an arbitrary point, P(x,y), inside of the triangle
I am talking about the problem of how do you mathematically define its color

[BrianHG]

Since you are not rasterizing a filled triangle in real time, you cannot perform a divide by subtracting a small integer as each dot/line is drawn, reseting those counters after reaching the edge of the triangle, and using those results as blend weights to interpolate the final color using my aforementioned matrix 4sum 8x8 multiply, shift by 8.  Ignore my recommendations unless you re-write your triangle rasterizer render fill directly like this from the beginning.

Basically, as you move either across, or down the screen during rasterization, following the line p1(x,y) to p2(x,y), to p3(x,y), plus imaginary p4(x,y) when drawing, you have a 16 bit counter following the relative position between each possible X,Y vertices, beginning at 0 when closest to P1, then 65535 at P2, (being a matrix, there are 2 counters for x&y).  You may need more than 16 bits for really high resolutions.  Then use these 4x2 integers, the top 8 bits which go from 0-255, and feed them to the color mixer.

[legacy]

you cannot perform a divide by subtracting a small integer as each dot/line is drawn, reseting those counters after reaching the edge of the triangle, and using those results as blend weights to interpolate the final color using my aforementioned matrix 4sum 8x8 multiply, shift by 8.  Ignore my recommendations unless you re-write your triangle rasterizer render fill directly like this from the beginning.

frankly, it not clear what you are talking about, and I haven't understood *HOW* you calculate the weight 

Code: [Select]

RGB_out <= ((weight1 * RGB_point1) << 8)
         + ((weight2 * RGB_point2) << 8)
         + ((weight3 * RGB_point3) << 8)
         + ((weight4 * RGB_point4) << 8);


[BrianHG]

Sorry, but if your triangle rasteriser isn't designed to loop and fill/draw the lines using a fractional counter, which I though you were, this becomes difficult to not possible.

Basically, as you move either across, or down the screen during rasterization, following the line p1(x,y) to p2(x,y), to p3(x,y), plus optional imaginary p4(x,y) when drawing, you have a 16 bit counter following the relative position between each possible X,Y vertices, beginning at 0 when closest to P1, then 65535 at P2, (being a matrix, there are 2 counters for x&y).  You may need more than 16 bits for really high resolutions.  Then use these 4x2 integers, the top 8 bits which go from 0-255, and feed them to the color mixer.

In other words, before you begin to draw, you solve once the how many times the number of X and Y screen pixels in each line of the triangle can divide into 65535 depending on X&Y screen pixels drawn.  When rendering the triangle, as you advance the X,Y painting position, you add/subtract those X&Y figures to the relative X&Y location counters.

The 65535 is using multiple 16 bit counters and should deliver good results up to 640x480.  Anything larger and I would increase that to 20 or 24 bits.

[legacy]

You are doing things the hard way

I am aware of cases where all the simplified intuitive algorithms I looked at were for likely nicer because easy to implement, but, under certain conditions, they tend to expose their bad side effects, e.g. when I shifted my triangle a bit, I saw the major problem with a simplified approach, specifically when the arbitrary point P lied directly on the straight line between two vertices and colors were all messed up 

[BrianHG]

Damn, too bad you cannot always slice up a source triangle into right angle triangles with a vertical and horizontal face.  That would simplify the algorithm and life...

[legacy]

That would simplify the algorithm and life

maybe, but I don't see how it solves the color-interpolation problem, haven't seen any mathematical evidence of your "tricks", and you haven't yet told how you calculate the weight 


hence I am going ahead with my solution, that at least is working on the paper, on the simulator with a rich test-cases, and on the FPGA 

[legacy]

you are not rendering a filled triangle beginning on each new scan line

the interpolator can do it, but it's not convenient since it wastes 80 cycles for nothing when the pixel is not inside the triangle. By scanning a line the interpolator doesn't know if the pixel belongs to the triangle until it has calculated it.