Author Topic: FPGA VGA Controller for 8-bit computer  (Read 49413 times)

0 Members and 1 Guest are viewing this topic.

Offline gcewing

  • Regular Contributor
  • *
  • Posts: 69
  • Country: nz
Re: FPGA VGA Controller for 8-bit computer
« Reply #1275 on: July 09, 2020, 09:44:29 am »
@BrianHG has pointed out, a diagonal line with an angle less than 45 degrees from horizontal will sometimes have more than one pixel on an edge with the same Y value, creating an overwritten line filling that segment of the triangle.
You need to move exactly one pixel in the y direction at each step, and however many pixels are needed in the x direction. As BrianHG said, your line generator may need modifying to make this possible.

But I don't think you need two different kinds of line generator, one for lines and one for triangles -- just one kind that's sufficiently general. You can use it for drawing lines as well, as long as you pick the right direction to step in depending on the slope.
 

Offline gcewing

  • Regular Contributor
  • *
  • Posts: 69
  • Country: nz
Re: FPGA VGA Controller for 8-bit computer
« Reply #1276 on: July 09, 2020, 10:48:48 am »
Here's some python3 code I wrote to try out the idea. It runs two Bresenham line algorithms in parallel. The outer loop takes one step in y on each iteration, and inner loops advance the left and right x coordinates the appropriate amount. It draws each pixel exactly once.

There may be a more efficient way that avoids the inner loops, but I haven't thought about it very deeply yet.

Code: [Select]
screen = [[' '] * 79 for y in range(23)]

def fill_triangle(x0, y0, x1, y1, x2):
    # Fills a flat-bottomed triangle with apex at (x0, y0) and
    # lower vertices at (x1, y1), (x2, y1). Assumes x1 <= x0 <= x2
    # and y0 <= y1.
   
    xL = xR = x0
    y = y0
    dxL = x0 - x1
    dxR = x2 - x0
    dy = y1 - y0
    eL = eR = 0
    n = dy
    while n > 0:
        fill_raster_line(xL, xR, y)
        eL += dxL
        while eL > 0:
            xL -= 1
            eL -= dy
        eR += dxR
        while eR > 0:
            xR += 1
            eR -= dy
        y += 1
        n -= 1

def fill_raster_line(x0, x1, y):
    x = x0
    n = x1 - x0 + 1
    while n > 0:
        draw_pixel(x, y)
        x += 1
        n -= 1

def draw_pixel(x, y):
    screen[y][x] = '*'

fill_triangle(50, 5, 10, 20, 60)
for row in screen:
    print(''.join(row))
 
The following users thanked this post: nockieboy

Offline nockieboy

  • Frequent Contributor
  • **
  • Posts: 994
  • Country: gb
Re: FPGA VGA Controller for 8-bit computer
« Reply #1277 on: July 09, 2020, 12:02:19 pm »
Here's some python3 code I wrote to try out the idea. It runs two Bresenham line algorithms in parallel. The outer loop takes one step in y on each iteration, and inner loops advance the left and right x coordinates the appropriate amount. It draws each pixel exactly once.

There may be a more efficient way that avoids the inner loops, but I haven't thought about it very deeply yet.

                                                  *                           
                                               *****                           
                                            *********                         
                                          ***********                         
                                       ***************                         
                                    *******************                       
                                  *********************                       
                               *************************                       
                            *****************************                     
                          *******************************                     
                       ***********************************                     
                    ***************************************                   
                  *****************************************                   
               *********************************************                   
            ************************************************* 

Thanks @gcewing, that works well :-+ - I don't know how it could be modified to draw a triangle in any orientation or point order, but I'm sure @BrianHG will have some thoughts on it. :)
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1278 on: July 09, 2020, 01:57:19 pm »
Method #3 it is.
It is easy enough to try in the geo.bas as you are just using counters.
If you are not sure about the 'absolute' edge of the triangle, remember, you can alway draw 3 connected normal line after the triangle is already filled, however, this may be up to you.

Since we are organizing the 3 sets or coordinates A,B,C in order by Y position first, vertically drawing LineGen#1 between A&C while the other LineGen#2 goes between A&B, then once it reaches B, it will start again going from B to C, all along using (well sort of) a dumb X axis line generator #3 only drawing from the coordinates of LineGen#1 to LineGen#2 after every Y increment.

The goal here is for every time you increment 1 Y axis on each line, what is the delta X.  A slight modification to the current line generators, however, because of your setup, you always know that Y is incrementing from top to bottom, otherwise the triangle is 1 pixel tall and you will end up filling a line from the most left X coordinates to the most right X coordinates among pints A,B,C.

You can still use your existing line generator to solve the triangle edges with a small penalty for it drawing in the edge pixels between each fill, however, it will still out-pace your pixel writer.

Let's see what kind of plan you have to do this.
I would stick with just using 2 of your existing line generators as you know they work.
Also, to speed things further up, you just completely skip a fill at each Y increment if the X coordinates of LineGen#1 & #2 have X coordinates within +/- 1 of each other as the line generators would have drawn those pixels.  (If you do it that way.)

__________
BrianHG.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1279 on: July 09, 2020, 02:08:27 pm »
Here, I'll start you off:

Step #1, sort points A,B,C into points new_A,B,C where the Y coordinate of new_A is the lowest coordinate and the Y coordinate of new_C is the highest.

Step #2, Setup (not run) line gen #1 & #2, and setup #3 which is still run by LineGen#2 once it reaches point new_B
LineGen#1 = new_A to new_C
LineGen#2 = new_A to new_B
LineGen#3 = new_B to new_C


Step #3:
 Make a screen_Y position loop from new_A(y) to new_C(y)

(What do you do in here).
(it will involve the line generators as is with only 2 tiny patches.  They will still function normally when used by themselves)
For now, only worry about 1 LineGen #1, see what you can come up with.

Next screen_Y

Hope this helps.

The only difference between my idea and gcewing python cod is that I don't care about sorting on the X coordinates as the line filler wont care (either it's bidirectional, or, it will swap the X coordinates and always draw from left to right) and we are still using our existing line generator code which may take a few additional clocks to generate a horizontal strip based on the edges of an angles of the line, however this does not matter as they will be doing the work where the line-fill missed the edges and corners of and extreme angle line at the beginning of a new Y coordinate.

Your other choice is to do M.N style floating point (still integer, just that you use the upper 12 bits as the mantissa) delta-X addition for every Y increment.  This means a 24 bit adder and a little additional setup math at the beginning.  You will also need to deal with how the edges of each line are filled especially when connecting 2 triangles to generate filled 4 sided polygons.  (.N is the err added at every Y step, however, it needs to be per-determined an can now be a value greater than 1 for every Y increment.)

How do you want to proceed.
« Last Edit: July 09, 2020, 03:09:48 pm by BrianHG »
__________
BrianHG.
 
The following users thanked this post: nockieboy

Offline nockieboy

  • Frequent Contributor
  • **
  • Posts: 994
  • Country: gb
Re: FPGA VGA Controller for 8-bit computer
« Reply #1280 on: July 09, 2020, 03:36:19 pm »
This is how far I've gotten based on the guidance above.  I've tried to convert the existing DrawLine function in our Free Basic test program to draw three lines.  There must be a simpler way of ordering the vertices at the start than what I've done?   :-//

After the ordering IF..ELSE IF structure, I set up some of the variables for the three line generators, sufficient to run all three in parallel.  Then I've made a start on the loop, but obviously it won't work as it currently stands.  I'm thinking that we need to draw a horizontal line between Ax and Cx every time y1 is incremented - but we need to make sure y2 has incremented as well, don't we? Or will they both increment at the same time by some weird conjunction of maths and the planets?

Code: [Select]
Sub drawTriangle (ByVal Ax as Integer, byval Ay as Integer, byval Bx as Integer, byval By as Integer, byval Cx as Integer, byval Cy as Integer, byval color_val As UByte)

   Dim As Integer new_Ax,new_Ay,new_Bx,new_By,new_Cx,new_Cy
   Dim As Integer dx1,dy1,x1,y1,sx1,sy1,errd1,magic1
   Dim As Integer dx2,dy2,x2,y2,sx2,sy2,errd2,magic2
   Dim As Integer dx3,dy3,x3,y3,sx3,sy3,errd3,magic3
   Dim As Boolean is_done

If (Ay > By > Cy ) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Bx
new_By = By
new_Cx = Cx
new_Cy = Cy
Else If (By > Cy > Ay) Then
new_Ax = Bx
new_Ay = By
new_Bx = Cx
new_By = Cy
new_Cx = Ax
new_Cy = Cy
Else If (Cy > Ay > By) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Ax
new_By = Ay
new_Cx = Bx
new_Cy = By
Else If (Ay > Cy > By) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Cx
new_By = Cy
new_Cx = Bx
new_Cy = By
Else If (Cy > By > Ay) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Bx
new_By = By
new_Cx = Ax
new_Cy = Ay
Else If (By > Ay > Cy) Then
new_Ax = Bx
new_Ay = By
new_Bx = Ax
new_By = Ay
new_Cx = Cx
new_Cy = Cy
EndIf

   Rem bounding box's width and height for the three line generators
   Rem And set the loop's sign
   Rem # Line Gen #1
   dx1 = new_Cx - new_Ax
   dy1 = new_Cy - new_Ay
   Rem # Line Gen #2
   dx2 = new_Bx - new_Ax
   dy2 = new_By - new_Ay
   Rem # Line Gen #3
   dx3 = new_Cx - new_Bx
   dy3 = new_Cy - new_By
   
   If (dx1 < 0) Then
      dx1 = -dx1
      sx1 = -1
   Else
      sx1 = 1
   End If
   
   If (dy1 > 0) Then
      dy1 = -dy1
      sy1 = 1
   Else
      sy1 = -1
   End If
   
   If (dx2 < 0) Then
      dx2 = -dx2
      sx2 = -1
   Else
      sx2 = 1
   End If
   
   If (dy2 > 0) Then
      dy2 = -dy2
      sy2 = 1
   Else
      sy2 = -1
   End If
   
   If (dx3 < 0) Then
      dx3 = -dx3
      sx3 = -1
   Else
      sx3 = 1
   End If
   
   If (dy3 > 0) Then
      dy3 = -dy3
      sy3 = 1
   Else
      sy3 = -1
   End If

   magic1 = 0
   errd1  = dx1 + dy1
   x1     = new_Ax
   y1     = new_Ay
   
magic2 = 0
   errd2  = dx2 + dy2
   x2     = new_Ax
   y2     = new_Ay
   
   magic3 = 0
   errd3  = dx3 + dy3
   x3     = new_Bx
   y3     = new_By
   
   For screen_Y = new_Ay To new_Cy
   
      draw_pixel (x1,y1,color_val)

      magic1 = errd1 shl 1
      if (magic1 > dy1) Then
         errd1 += dy1
         x1    += sx1
      End If
       
      if (magic1 < dx1) Then
         errd1 += dx1
         y1    += sy1
      End If
     
      draw_pixel (x2,y2,color_val)

      magic2 = errd2 shl 1
      if (magic2 > dy2) Then
         errd2 += dy2
         x2    += sx2
      End If
       
      if (magic2 < dx2) Then
         errd2 += dx2
         y2    += sy2
      End If
   
      draw_pixel (x3,y3,color_val)

      magic3 = errd3 shl 1
      if (magic3 > dy3) Then
         errd3 += dy3
         x3    += sx3
      End If
       
      if (magic3 < dx3) Then
         errd3 += dx3
         y3    += sy3
      End If
     
   Next

End Sub
 

Offline nockieboy

  • Frequent Contributor
  • **
  • Posts: 994
  • Country: gb
Re: FPGA VGA Controller for 8-bit computer
« Reply #1281 on: July 09, 2020, 03:44:11 pm »
Your other choice is to do M.N style floating point (still integer, just that you use the upper 12 bits as the mantissa) delta-X addition for every Y increment.  This means a 24 bit adder and a little additional setup math at the beginning.  You will also need to deal with how the edges of each line are filled especially when connecting 2 triangles to generate filled 4 sided polygons.  (.N is the err added at every Y step, however, it needs to be per-determined an can now be a value greater than 1 for every Y increment.)

How do you want to proceed.

 :o

Which way is going to be the quickest?

The M.N style sounds simpler and perhaps easier for me to grasp, but that's only because I don't really know the intricacies of either method - it just seems adding a constant value (be it a float or an integer) to x for every y increment is the easier-to-read way to go.  I can't imagine a 24-bit adder will take up too much space in the FPGA?  I'm running at about 85% logic usage currently, but with plans to expand to over double the resources in a BGA package later on, I'm not exactly scrimping and saving every last logic gate here.

Either way will involve lots of dumb expressions from me and stupid questions, so I'll defer to your expert knowledge of the subject.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1282 on: July 09, 2020, 03:59:53 pm »
The Y sort will be done in a single clock as the command is being called, IE 0 clock cycles.
Like before, the setup for all 3 lines will take 1 clock, then you can begin drawing the line.

As for the draw line function, for now, keep your setup and just draw line #1.

Then let's modify that line engine to temporarily escape at a chosen Y coordinate, then continue to another, being the next  Y coordinate.
 (make it a called sub-function for ease of reading.  You probably wont have the luxury of using a function's call arrays as this line generator when called will only complete part of a line at a time.  You might be stuck using 'Dim Shared' for the line arrays.)

We will stop here and make sure the alterations you make can implement in your verilog line generator.
__________
BrianHG.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1283 on: July 09, 2020, 05:16:12 pm »
For the M.N method, we need to calculate it this way, unless you can come up with a shorter method.


First for float:
Code: [Select]
div = abs( ay - by )
  if div = 0 then div=1
  delta_x_per_y_increment =  ( bx-ax ) / div
xp = ax

For yp = ay to by
  draw_pixel ( int(xp),int(yp),color_val)
  xp=xp + delta_x_per_y_increment
next yp

See new attached geo.bas  in the attached geo_trifill_testfloat.zip with everything updated.
I'm drawing the float line using the 'drawFilledTriangle' right at the end.

Now, since pixels will be filled from left to right, the line wont have bits in it.
However, I also plotted a normal line right on top of the third line and you see extra added pixels on the right which would not be caught by the left to right fill.

24 bit Integer version coming in next post so you can see what that will be like.
« Last Edit: July 09, 2020, 05:20:28 pm by BrianHG »
__________
BrianHG.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1284 on: July 09, 2020, 05:56:42 pm »
Damn it, I'm either too sleepy or cant get rid of that divide.
If it were a multiply, IE if I were to operate with everything at 4096x, (that's using M.N), multiply and bit shift as a divide by 4096 could work but my head is in the clouds. (divides are slow, like 11 clock cycles and eat resources.  You could speed this up by pipe-lining making the divides at 125 million a second, but I want to see filled triangle plots by Monday.)

Instead, lets use our existing line engine doubled.
Well use the 2 Bresenham line generators to plot/create the outer edges of the line and use a simple for x1 to x2 for filling in the inside.  At worst, you pixel drawing engine / command may have to draw a few repetitious pixels on a line, but since they are adjacent pixels, you are only talking 1/125 millionth of a second per extra dot.
« Last Edit: July 09, 2020, 05:58:41 pm by BrianHG »
__________
BrianHG.
 

Offline gcewing

  • Regular Contributor
  • *
  • Posts: 69
  • Country: nz
Re: FPGA VGA Controller for 8-bit computer
« Reply #1285 on: July 10, 2020, 12:19:48 am »
There must be a simpler way of ordering the vertices at the start than what I've done?   :-//
You could hard-code a 3-element bubble sort.

Keep in mind that these kinds of setup tasks can be done in software. I'd concentrate on just doing the parts that really need to be fast in hardware, at least initially. You can think about migrating some of the setup into hardware later if you want.

Google "sorting network" for some ideas on how to implement a sort in hardware.

Quote
After the ordering IF..ELSE IF structure, I set up some of the variables for the three line generators, sufficient to run all three in parallel.
You only need to run 2 line generators in parallel. When you reach the middle vertex, switch one of them from doing the upper half to doing the lower half.

Quote
we need to make sure y2 has incremented as well, don't we? Or will they both increment at the same time by some weird conjunction of maths and the planets?
In my Python code I only have one y variable shared between the two line generators, so this issue doesn't arise.  :)

Despite what I said earlier, I think it's better to think of the triangle filler as its own thing, and not try to make it share hardware with whatever you're using to draw lines. Instead of "liine generators" think of "side generators". There are two of them, but they're not completely independent, they share some state.
 

Offline gcewing

  • Regular Contributor
  • *
  • Posts: 69
  • Country: nz
Re: FPGA VGA Controller for 8-bit computer
« Reply #1286 on: July 10, 2020, 12:32:07 am »
The M.N style sounds simpler and perhaps easier for me to grasp,
It's certainly easier to get one's head around! The only reason I didn't suggest it myself is because of the need for divisions during the setup, but like I said before, you can leave that to software for now.

A nice property of the fixed-point approach is that a step in the y direction can be done in a single clock cycle, instead of potentially requiring multiple cycles to update the x coordinates.

Another benefit is that it may be easier to adapt for more complicated shapes such as circles and bezier curves if you want to go there later.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1287 on: July 10, 2020, 12:44:51 am »
There must be a simpler way of ordering the vertices at the start than what I've done?   :-//
You could hard-code a 3-element bubble sort.

Keep in mind that these kinds of setup tasks can be done in software. I'd concentrate on just doing the parts that really need to be fast in hardware, at least initially. You can think about migrating some of the setup into hardware later if you want.

Google "sorting network" for some ideas on how to implement a sort in hardware.

Quote
After the ordering IF..ELSE IF structure, I set up some of the variables for the three line generators, sufficient to run all three in parallel.
You only need to run 2 line generators in parallel. When you reach the middle vertex, switch one of them from doing the upper half to doing the lower half.

Quote
we need to make sure y2 has incremented as well, don't we? Or will they both increment at the same time by some weird conjunction of maths and the planets?
In my Python code I only have one y variable shared between the two line generators, so this issue doesn't arise.  :)

Despite what I said earlier, I think it's better to think of the triangle filler as its own thing, and not try to make it share hardware with whatever you're using to draw lines. Instead of "liine generators" think of "side generators". There are two of them, but they're not completely independent, they share some state.

2 Line generators running in parallel or series makes no difference plotting pixels speed wise since we use the line generators to plot the pixels on the line itself and if there is vacant space inbetween line gen #1 and #2, we fill in a straight line between them.  Having 2 run in parallel would only help if we had a 2 channel pixel writer where we can write 2 different pixels to ram at the same time.

In System verilog, this becomes easy as you make the all current line generators integers into arrays.  This way, at every clock, your single array selection variable will select which line generator increments.  On each increment, like the Y coordinate increasing, you can make the array pointer increment to work on the other face of the triangle, all with 0 latency in the transition.  Our pixel writer will not be able to keep up with this speed and as it's FIFO command buffer goes full, it will tell the geometry_xy_plotter to pause many times.

As for the top down sort, however it is done, a simple magnitude / if / else if would work in a single clock as no matter how you engineer the tree, the compiler would simplify it anyways.  Sorting based on 3 12 bit numbers should still reach our core clock of 125MHz.  If not, we would need to break that sort into 2 stages.

__________
BrianHG.
 

Offline gcewing

  • Regular Contributor
  • *
  • Posts: 69
  • Country: nz
Re: FPGA VGA Controller for 8-bit computer
« Reply #1288 on: July 10, 2020, 12:46:15 am »
At worst, you pixel drawing engine / command may have to draw a few repetitious pixels on a line, but since they are adjacent pixels, you are only talking 1/125 millionth of a second per extra dot.
I'd suggest treating the raster lines as half-open intervals, i.e. x1 <= x < x2. Then adjacent triangles will fit together without overdrawing or leaving gaps.

Overdraw is harmless if you're just overwriting pixels, but if you might want other drawing modes such as XOR or alpha blending, it's something you'll want to avoid.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1289 on: July 10, 2020, 12:57:29 am »
The M.N style sounds simpler and perhaps easier for me to grasp,
It's certainly easier to get one's head around! The only reason I didn't suggest it myself is because of the need for divisions during the setup, but like I said before, you can leave that to software for now.

A nice property of the fixed-point approach is that a step in the y direction can be done in a single clock cycle, instead of potentially requiring multiple cycles to update the x coordinates.

Another benefit is that it may be easier to adapt for more complicated shapes such as circles and bezier curves if you want to go there later.

It makes no difference about the Y direction in 1 clock since we have to draw those pixels anyways.  Remember, each clock, we draw a pixel.  When we enter a new Y coordinate on both line gen #1 and #2, we fill the void in between, then continue the Bresenham line gens #1 and #2 which will plot the missing pixels due to rounding errors which would not be done with the M.N method.  Remember, there is 0 pause or latency here, switching from the line fill back to incrementing the line gens will continue to push out pixels as if the horizontal fill generator was just continuing to fill a longer line.  The M.N would only fill the pixels in between the 2 points including the points.  Though, with the M.N, you can make a dithered line's edge knowing the relative analog center of the line's X location.

The ellipse and curve algorithm has also been with nothing more than adds and X^2 & Y^2 and multiples of 8 in the same way Bresenham's line algorithm works.  We already the ellipse running in geo.bas and it can be broken down into it's 8 quadrants to generate Bézier curves or rotated ellipses.  No divides needed.

« Last Edit: July 10, 2020, 01:00:12 am by BrianHG »
__________
BrianHG.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1290 on: July 10, 2020, 01:21:26 am »
Another benefit is that it may be easier to adapt for more complicated shapes such as circles and bezier curves if you want to go there later.

Bézier curves without divide on this web page.  I know that the author used 'long' and 'double' for his Bézier curves and Ellipse, but they work fine with all int's.  All the multiplies of divides are by 2 and by 4.  All the other multiplies total 8 which the Cyclone IV can handle in a single clock at 125MHz.  Also, our GPU has yet to use a single hardware multiplier in the Cyclone IV.

http://members.chello.at/easyfilter/bresenham.html

My plan is to eventually swap out the line gens and ellipse for the Bézier curve line gens and when a line or triangle is called, it's basically a Bézier curve line with an arc setting on the line itself, or 0.  Generating ellipses just calls 4 Béziers with the arc having the right delta.  Like this, we can now also generate rotated ellipses or triangles with curved faces.
« Last Edit: July 10, 2020, 01:25:36 am by BrianHG »
__________
BrianHG.
 

Offline nockieboy

  • Frequent Contributor
  • **
  • Posts: 994
  • Country: gb
Re: FPGA VGA Controller for 8-bit computer
« Reply #1291 on: July 10, 2020, 10:33:07 am »
Okay, thanks to spinning several plates (one of which is work) I'm losing track of where we are and what I'm supposed to be doing.  I had completed the setup for a three line (two line?) function to start drawing a triangle, but since then I've got Free BASIC code to draw triangle edges using M.N and the conversation has moved on.   ???

What should I be working on next?  :-/O
« Last Edit: July 10, 2020, 10:35:45 am by nockieboy »
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1292 on: July 10, 2020, 02:50:50 pm »
Go back here: https://www.eevblog.com/forum/fpga/fpga-vga-controller-for-8-bit-computer/msg3127872/#msg3127872

Your post after mine began ok.  Remember, we got it backwards, we want point new_A to have the lowest Ay and point new_Cy to have the highest Cy.

The geo.bas I've uploaded may have the 'divide' method of generating a line in the triangle_filled routine, however, you will erase that little line loop and place in the work you begun.  Since we have a working Bresenham's in Verilog, we will use one with with 3 set array which you may increment 1 of 3 at a time.  Follow my instructions to generate a proper rasterized fill.

When going to verilog, the 3 set array is the easiest upgrade to do.  If your FMAX drops too low, we will try downgrading to a 2 set array.  If the FMAX is still too low, we will go back to a single 1 set array line, like now, and add a second Bresenham's line generator to mimic a 2 set array, IE 2 line drawing engines.

Step 1, get it working in geo.bas.  (program to make it easy to switch to verilog)
Step 2, upgrade verilog code to mimic geo.bas.

« Last Edit: July 10, 2020, 09:16:22 pm by BrianHG »
__________
BrianHG.
 

Offline nockieboy

  • Frequent Contributor
  • **
  • Posts: 994
  • Country: gb
Re: FPGA VGA Controller for 8-bit computer
« Reply #1293 on: July 11, 2020, 01:49:16 pm »
Remember, we got it backwards, we want point new_A to have the lowest Ay and point new_Cy to have the highest Cy.

Right, so I've reversed the IF.. conditional in the setup:
Code: [Select]
If (Ay > By > Cy ) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Bx
new_By = By
new_Cx = Ax
new_Cy = Ay
ElseIf (By > Cy > Ay) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Cx
new_By = Cy
new_Cx = Bx
new_Cy = By
ElseIf (Cy > Ay > By) Then
new_Ax = Bx
new_Ay = by
new_Bx = Ax
new_By = Ay
new_Cx = Cx
new_Cy = Cy
ElseIf (Ay > Cy > By) Then
new_Ax = Bx
new_Ay = By
new_Bx = Cx
new_By = Cy
new_Cx = Ax
new_Cy = Ay
ElseIf (Cy > By > Ay) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Bx
new_By = By
new_Cx = Cx
new_Cy = Cy
ElseIf (By > Ay > Cy) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Ax
new_By = Ay
new_Cx = Bx
new_Cy = By
EndIf

The geo.bas I've uploaded may have the 'divide' method of generating a line in the triangle_filled routine, however, you will erase that little line loop and place in the work you begun.  Since we have a working Bresenham's in Verilog, we will use one with with 3 set array which you may increment 1 of 3 at a time.  Follow my instructions to generate a proper rasterized fill.

 ???  Okay, so you want the setup above inserted into the drawFilledTriangle routine, but Ax/Ay, Bx/By, Cx/Cy replaced with a 3-element array [x,y], then the loop modified to not just draw one line, but all three lines defined in the array?  I'm having trouble following.  :-//
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1294 on: July 11, 2020, 03:07:03 pm »
Yes you got it.  Remember, fill and setup the 3 line elements.

begin first pixel of line #1,#2,&#3.

Start a separate for loop raster_Y position counter from the lowest Y to the highest Y coordinate.
Should be equal to new_Ay and new_Cy. (line#1 beginning and ending Y position)

run/draw line #1 until you reach the raster_Y.
run/draw line #2 until you reach the raster_Y (when line#2 ends, swap line#2's into line#3's and step/run line #3.)

if there are pixels between line #1x and line #2x, do a horizontal fill
 
next raster_Y position.

Finish lines #1 and line #3.
« Last Edit: July 11, 2020, 04:14:31 pm by BrianHG »
__________
BrianHG.
 

Offline nockieboy

  • Frequent Contributor
  • **
  • Posts: 994
  • Country: gb
Re: FPGA VGA Controller for 8-bit computer
« Reply #1295 on: July 11, 2020, 06:53:38 pm »
Okay, got this far:
Code: [Select]
Sub drawFilledTriangle (ByVal x0 as Integer, byval y0 as Integer, byval x1 as Integer, byval y1 as Integer, byval x2 as Integer, byval y2 as Integer, byval color_val As UByte)
   
        Dim As double ax,ay,bx,by,cx,cy,div,xp,yp,delta_x_per_y_increment
Dim As Double x[2],y[2]

If (y0 > y1 > y2 ) Then
x[0] = x2
y[0] = y2
x[1] = x1
y[1] = y1
x[2] = x0
y[2] = y0
ElseIf (y1 > y2 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x2
y[1] = y2
x[2] = x1
y[2] = y1
ElseIf (y2 > y0 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x0
y[1] = y0
x[2] = x2
y[2] = y2
ElseIf (y0 > y2 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x2
y[1] = y2
x[2] = x0
y[2] = y0
ElseIf (y2 > y1 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x1
y[1] = y1
x[2] = x2
y[2] = y2
ElseIf (y1 > y0 > y2) Then
x[0] = x2
y[0] = y2
x[1] = x0
y[1] = y0
x[2] = x1
y[2] = y1
EndIf

div = abs( y[0] - y[2] )
If div = 0 then div = 1
delta_x_per_y_increment = ( x[1] - x[0] ) / div
xp = x[0]

For yp = y[0] to y[2]
  draw_pixel ( int(xp),int(yp),color_val )
  xp= xp + delta_x_per_y_increment
Next yp

End Sub

I'm not entirely sure what I'm doing with the setup near the start of the loop.  When setting delta_x_per_y_increment, shouldn't that be x[2] instead of x[1], and aren't I going to have to sort the x array to find the lowest and highest values and use those in the formula to calculate the correct delta_x_per_y_increment?
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1296 on: July 11, 2020, 07:23:28 pm »
Okay, got this far:
Code: [Select]
Sub drawFilledTriangle (ByVal x0 as Integer, byval y0 as Integer, byval x1 as Integer, byval y1 as Integer, byval x2 as Integer, byval y2 as Integer, byval color_val As UByte)
   
        Dim As double ax,ay,bx,by,cx,cy,div,xp,yp,delta_x_per_y_increment
Dim As Double x[2],y[2]

If (y0 > y1 > y2 ) Then
x[0] = x2
y[0] = y2
x[1] = x1
y[1] = y1
x[2] = x0
y[2] = y0
ElseIf (y1 > y2 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x2
y[1] = y2
x[2] = x1
y[2] = y1
ElseIf (y2 > y0 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x0
y[1] = y0
x[2] = x2
y[2] = y2
ElseIf (y0 > y2 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x2
y[1] = y2
x[2] = x0
y[2] = y0
ElseIf (y2 > y1 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x1
y[1] = y1
x[2] = x2
y[2] = y2
ElseIf (y1 > y0 > y2) Then
x[0] = x2
y[0] = y2
x[1] = x0
y[1] = y0
x[2] = x1
y[2] = y1
EndIf

div = abs( y[0] - y[2] )
If div = 0 then div = 1
delta_x_per_y_increment = ( x[1] - x[0] ) / div
xp = x[0]

For yp = y[0] to y[2]
  draw_pixel ( int(xp),int(yp),color_val )
  xp= xp + delta_x_per_y_increment
Next yp

End Sub

I'm not entirely sure what I'm doing with the setup near the start of the loop.  When setting delta_x_per_y_increment, shouldn't that be x[2] instead of x[1], and aren't I going to have to sort the x array to find the lowest and highest values and use those in the formula to calculate the correct delta_x_per_y_increment?
Reread my post here: https://www.eevblog.com/forum/fpga/fpga-vga-controller-for-8-bit-computer/msg3128938/#msg3128938

There may be some occasional repeat plots with really steep shrinking/converging X axis lines, but these triangles will need to be so flat and wide that they would look like a flat line.  We will spit out 125 million pixels a second in these cases and for a wide triangle, like the width of the screen and only 2-5 lines tall, we may be re-painting 50% of those pixels on those lines.  If you want to save these double pixel plots, I would say wait till after we got everything working then take a look back and perform that optimization step.

(Here's that optimization step, but don't let it mess with your head for now) When determining the beginning and ending X coordinates for the raster line fill, when the X direction of the line shrinks, wait for the line generator to leave the current raster_Y coordinate before pausing it's drawing and using it's X coordinate for the horizontal raster fill.  When the X line position increases, pause the line generator as it enters the current raster_Y coordinate and then use it's current X coordinate for the horizontal raster fill.


(Remember, we cant use a divide nor does that routine with the divide work out the bleeding pixels along the edge of the triangle, you need to use and adapt Bresenham's line algorithm.)

(Well, we can use a divide, but there is a huge setup penalty and gate count resources)

« Last Edit: July 12, 2020, 12:23:59 am by BrianHG »
__________
BrianHG.
 

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1297 on: July 11, 2020, 08:08:35 pm »
Please insert and test this final version 3.0 of my 'FIFO_3word_0_latency.sv'.  Let me know if it works.
If you like, here is it's project thread: https://www.eevblog.com/forum/fpga/home-made-systemverilog-3-word-zero-latency-fifo-documented-for-beginners/msg3123336/#msg3123336
« Last Edit: July 12, 2020, 03:53:57 am by BrianHG »
__________
BrianHG.
 

Offline Nominal Animal

  • Super Contributor
  • ***
  • Posts: 1850
  • Country: fi
    • My home page and email address
Re: FPGA VGA Controller for 8-bit computer
« Reply #1298 on: July 12, 2020, 01:58:44 am »
An illustration of the possible different types of triangles might help here:

A row-scanning rasterizer first sorts the three vertices according to the y coordinates.  There are six types of triangles, based on the y coordinates:
  • y1 == y2 == y3: A horizontal line. Draw from min(x1,x2,x3) to max(x1,x2,x3) on that row.  Not included in above illustration.
  • y2 < y2 == y3: A "diverging" triangle (opens downwards).  Leftmost in above illustration.
  • y1 == y2 < y3: A "converging" triangle (opens upwards).  Second from left in above illustration.
  • y1 < y2 < y3 with xM = x1 + (x3 - x1)*(y2 - y1)/(y3 - y1) < x2: Second vertex is on the right side.  Third from left in above illustration.
  • y1 < y2 < y3 with xM = x1 + (x3 - x1)*(y2 - y1)/(y3 - y1) > x2: Second vertex is on the left side.  Rightmost in above illustration.
  • y1 < y2 < y3 with xM = x1 + (x3 - x1)*(y2 - y1)/(y3 - y1) == x2: Triangle is just a straight line.  Not included in above illustration, can be handled by either of the two previous cases.
If you use two Bresenham lines in parallel, you must remember the minimum x on each row y for the left side, and the maximum x on each row y for the right side, and draw the horizontal line between those (including the end points).

A filler loop that can draw a single triangle of the red or blue type above, but not a combination of both, is the simplest to implement.  Many triangles then involve running the filler loop twice, for y1 <= y < y2 and for y2 <= y <= y3.

Note that the filler loop could allow y coordinates smaller than the viewport minimum, and x coordinates outside the viewport.  Then, it can draw triangles partially outside the viewport without issues.  You simply avoid drawing any horizontal lines when y is smaller than the viewport minimum y coordinate, and draw only the part of the horizontal line that is within the viewport.

If you write a filler that can draw any triangle, you'll simply switch the error and delta terms in the inner loop if it enters x == x2, y == y2.

If you use fixed-point arithmetic, you should include an adjustment term for the left and right sides, for calculating the starting and ending x coordinates for the horizontal line for each y coordinate. (This corresponds to finding the minimum x included on the line on the left side, and maximum x included on the line on the right side.)
For the left side, the adjustment is zero if the slope is positive, and half a step if the slope is negative.
For the right side, the adjustment is zero if the slope is negative, and half a step if the slope is positive.

The slope itself, or the change in x coordinate whenever y changes, for the side from (xA, yA) to (xB, yB) is
    dx = (xB - xA) / (yB - yA)

Here's an example Python floating-point implementation:
Code: [Select]
x_min = 0
y_min = 0
x_max = 79
y_max = 39

def HLine(y, left, right):
    line = [ ]
    for x in range(x_min, x_max + 1):
        if x >= left and x <= right:
            line.append('#')
        else:
            line.append('.')
    print('%3d: %s (%d)' % (y, ''.join(line), len(line)))

def Fill(x1,y1, x2,y2, x3,y3):
    # Sort the points with increasing y
    if y1 > y2:
        x1,y1, x2,y2 = x2,y2, x1,y1
    if y1 > y3:
        x1,y1, x3,y3 = x3,y3, x1,y1
    if y2 > y3:
        x2,y2, x3,y3 = x3,y3, x2,y2

    # Completely outside the viewport?
    if y1 > y_max or y3 < y_min:
        return
    if min(x1, x2, x3) > x_max or max(x1, x2, x3) < x_min:
        return

    # Slope from (x1,y1) to (x2,y2)
    if y1 < y2:
        dx12 = (x2 - x1) / (y2 - y1)
    else:
        dx12 = 0

    # Slope from (x1,y1) to (x3,y3)
    if y1 < y3:
        dx13 = (x3 - x1) / (y3 - y1)
    else:
        dx13 = 0

    # Slope from (x2,y2) to (x3,y3)
    if y2 < y3:
        dx23 = (x3 - x2) / (y3 - y2)
    else:
        dx23 = 0

    # Start at x1,y1
    y,xL,xR = y1,x1,x1

    if dx12 >= dx13:
        # (x2,y2) is on the right side of the triangle
        dxL, dxL2 = dx13, dx13
        dxR, dxR2 = dx12, dx23
    else:
        # (x2,y2) is on the left side of the triangle
        dxL, dxL2 = dx12, dx23
        dxR, dxR2 = dx13, dx13

    # Left adjustments
    if dxL < 0:
        axL = dxL/2
    else:
        axL = 0
    if dxL2 < 0:
        axL2 = dxL2/2
    else:
        axL2 = 0

    # Right adjustments
    if dxR > 0:
        axR = dxR/2
    else:
        axR = 0
    if dxR2 > 0:
        axR2 = dxR2/2
    else:
        axR2 = 0

    # Do not progress outside the viewport.
    if y3 > y_max:
        y3 = y_max

    # Blitter loop
    while y <= y3:

        # Changeover point?
        if y == y2:
            dxL, axL = dxL2, axL2
            dxR, axR = dxR2, axR2

        # y within the viewport?
        if y >= y_min:

            # Adjust edges.
            iL = int(xL + axL)
            iR = int(xR + axR)

            # Any part of horizontal line within viewport?
            if iR >= x_min and iL <= x_max:
                HLine(y, max(x_min, iL), min(iR, x_max))

        # y step.
        y  = y  + 1
        xL = xL + dxL
        xR = xR + dxR

if __name__ == '__main__':
    # Fill(-35,-13, 75,13, 43,57)
    # Fill(99,-2, 17,15, -12,43)
    Fill(1,1, 78,15, 39,38)
There are three divisions (a fixed-point/float value divided by an integer) to get the slopes, and four halving of a fixed-point/float value.  Lots of comparisons in the inner loop, though.
 
The following users thanked this post: BrianHG

Online BrianHG

  • Super Contributor
  • ***
  • Posts: 4324
  • Country: ca
Re: FPGA VGA Controller for 8-bit computer
« Reply #1299 on: July 12, 2020, 02:16:33 am »
Thanks Nominal Animal.
My directions for nockieboy are intended for him to approach the problem of filling the triangles by making his existing HDL code perform what you illustrated by adding a few brackets and 1 extension to an IF() at the top.  It will perform the 2 right hand triangles with 1 more extension to that IF().

What my directions do not cover is the optimization involved in drawing the flat horizontal line in your first 2 illustrated triangles.  The flat line would be drawn twice, however, an addition to the IF() inside the raster fill may be used to prevent that fill.

My step 1 is to get the triangles filled with what we have.  Once done, optimizing the 6 conditions types in your list will be just a bit of juggling and selection of the 2/3 Bresenham's linegen setup.
__________
BrianHG.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf