FPGA VGA Controller for 8-bit computer

[BrianHG]

Black dot in first 2 images?
Which revision were you running?

Ok, I think we will need to redoo the entire system so linegen #2 stops on the same Y coordinates of linegen #1...

[nockieboy]

Black dot in first 2 images?
Which revision were you running?

Ok, I think we will need to redoo the entire system so linegen #2 stops on the same Y coordinates of linegen #1...

Right, yes, sounds like a plan.  Where do I begin?  I've added the input back to the line_generator module and in the geo_xy_plotter instances - also note that you'd already put the y_stop_coordinate check in the code in line_generator and commented it out previously, so I've un-commented it.

Latest versions of the modules attached.

[BrianHG]

I don't know exactly what to say.  It looks like things need to be simplified down, otherwise in the futurem you will never be able to debug an issue.

I'm thinking the best strategy for you would be 1:

1. Get rid of the linegen3 and make a simple Horizontal line filling engine with pass-through  A & B, and, line from A to B.
2. Fix up linegens 1 & 2, get rid of pass-through A-B, but keep the smart.  Make an input increment enable.
3. Make a make a vertical line Ay-By counter with enable module.

Now, go back to old fashioned sequencing and when a triangle is called:
Set the vertical counter's start and stop to Y[0] and Y[2].

loop:
Run linegen 1 until the Y output = vertical counter's y output.  (Also plot the linegen's output)
Run linegen 2 until the Y output = vertical counter's y output.  (Also plot the linegen's output)
If lgX1<>lgX2, run Horizontal line filling engine.
If lg2 is finished, restart lg2 with a[1] to b[2]
If lg1 is not finished, increment vertical counter and loop

This matches exactly what the 'Free Basic' code is doing.
This has no coordinate sorting or tests to see if we are drawing a point, horizontal line, or vertical line.

This means getting rid of my LUT solution in place for a case statement with numerical sequences like an old fashioned Basic line numbering code except each line needs the goto to the next.

[nockieboy]

Okay, I have only done BASIC testing so far, but I've been experimenting with unique preset values of y_stopped_int for each line generator and I have fixed the alignment error introduced with the previous system of specifying y_stopped_int as the same value for each linegen. 

The line_generator module now has an additional 1-bit input - lineIndex - which is set to 1 or 0 when the line generator is instantiated in geo_xy_plotter.  Line 150 (previously 149) in the line_generator module now reads:

Code: [Select]

ypos_stopped_int <= lineIndex ;
I've found that setting lineIndex to 1 for linegen's 1 & 2 and 0 for linegen#3 removes the misalignment and draws rectangles and quads without error, and draws filled triangles with no missing pixels due to misalignment of the linegens.

I will do more testing with other triangle shapes later this afternoon, but currently the patch is looking good and a lot less hassle than effectively re-writing the geo_xy_plotter module to start again. 

Lines and pixels are still drawn fine - I suppose if there's issues with any future functions (e.g. ellipses) then a LUT may be the answer, but currently it's working fine.  I'll probably change the name of lineIndex to something more descriptive shortly, but I'll wait and see if you shoot the fix down in flames because there's something I haven't spotted yet which means it breaks everything. 

[BrianHG]

Like I said, in the linegens, get rid of the pass-thru and the Y-inc stopped stuff.
Make a general -increment- enable.
Externally, you will  just compare the outpuy y position and decide to continue to increment or not.

Make that linegen -old-simple-stupid...

Too many little thing are going on inside it and you cant debug, or take control in the way you may like properly.

You will rely on code in the geometry_xy_plotter to make the linegens stop and go.

And you will rely on the next simple horizontal filler to select linegen1 or linegen 2 or draw a dumb horizontal line from linegen1 to linegen 2.

Get rid of my look-up tables and make a simple extension to the case statement to run your own sequences to generate each selected shape.  The only thing you want to keep is the output section with coordinates out of bounds check currently lines 395 through 407.

[nockieboy]

Like I said, in the linegens, get rid of the pass-thru and the Y-inc stopped stuff.
Make a general -increment- enable.
Externally, you will  just compare the outpuy y position and decide to continue to increment or not.

Make that linegen -old-simple-stupid...

Too many little thing are going on inside it and you cant debug, or take control in the way you may like properly.

You will rely on code in the geometry_xy_plotter to make the linegens stop and go.

And you will rely on the next simple horizontal filler to select linegen1 or linegen 2 or draw a dumb horizontal line from linegen1 to linegen 2.

Get rid of my look-up tables and make a simple extension to the case statement to run your own sequences to generate each selected shape.  The only thing you want to keep is the output section with coordinates out of bounds check currently lines 395 through 407.

...but I don't want to do all that if I don't have to as I've got the existing system working? 

Is there a big issue with what we've got at the moment (that I can't see) that will cause problems with ellipses?  I'm happy to rip it all up and start again if it really is unusable - there is, after all, still an issue with quads - but it seems silly to set myself back another couple of weeks whilst I rewrite the geo_xy_plotter for no good reason?

EDIT:  As for the quads issue - can't quads just be broken down into triangles by the geo_xy_plotter somehow?

[BrianHG]

The system isn't working good.  If it was, you should have been able to fix it.

As for the quads,  we aren't doing it right now.  with that Y counter, out of the 4 coordinates, you once again make the Y counter go from the min Y to the max Y.

Then for linegens 1&2, pretend you are filling a perfect diamond shape:
What's the difference for linegen #1 when drawing that diamond instead of a triangle.
What's the same about linegen #2 when drawing that diamond and the triangle.

Also, ellipse and rotated ellipse are just quads with arcs instead of straight lines.  Again, the ellipse is a diamond shape with an addition to the linegens to generate a x² arc.

However, you can try to patch up the current system.
Make sure empty pixels never come up anywhere.

I guess you should think about sorting the coordinates now for triangles and quads.

[nockieboy]

The system isn't working good.  If it was, you should have been able to fix it.

I have fixed it.   I'm not getting missing pixels in triangles or misaligned fills in any shapes that I've tested so far.  I'll keep testing (especially larger shapes), but so far so good. 

As for the quads,  we aren't doing it right now.  with that Y counter, out of the 4 coordinates, you once again make the Y counter go from the min Y to the max Y.

I was thinking of ordering the four points, then drawing a triangle with points 1, 2 and 3, then another triangle with points 2, 3 and 4.  That should cope with any shape of quad, unless you have a better idea?

However, you can try to patch up the current system.
Make sure empty pixels never come up anywhere.

That's what I've been saying, it seems I have patched the current system.    I'll keep testing it, though.

I guess you should think about sorting the coordinates now for triangles and quads.

Righto - will make a start on that soon.  We already have a coordinate-sorting module, or part of one, with the tri_comp module, right?

[BrianHG]

Righto - will make a start on that soon.  We already have a coordinate-sorting module, or part of one, with the tri_comp module, right?

Yes, the tri_comp gives you a set of flags which you may simplify just the ones you need into a new logic array, and feed that into 4 LUTs whose results will give your the sort selection based on sequence number and shape type.

The sort should also work for the quads.

I was thinking of ordering the four points, then drawing a triangle with points 1, 2 and 3, then another triangle with points 2, 3 and 4.  That should cope with any shape of quad, unless you have a better idea?

Given my response, you should easily be able to adapt the current setup to do exactly as I described.
You are allowed any number of sequences for linegen #1 and #2.

[BrianHG]

You can also do 2 triangles for the quad, but, it will be slower.

[nockieboy]

You can also do 2 triangles for the quad, but, it will be slower.

That's the way that immediately sprang to mind when I thought about how to cater for any quad shape, as the current setup obviously doesn't work properly for all cases.   I figured it wouldn't be the quickest way, but in terms of my understanding it, I think I can do that myself once the point-sorting is running.

Modern graphics cards don't draw quads/polygons anyway?  Quads are a valid primitive in 3D graphics (they're used regularly in 3D software like Blender, Maya etc and game engines like Unreal Engine and Unity, for example), but I think polygons and quads are broken down into triangles by the driver (or perhaps even by the software 3D engine itself) before the GPU gets to run transform calculations on it?

I'm not sure I fully understand how your method of quad drawing will work. 

[nockieboy]

Just taking a look at tri_comp.

It provides three outputs, each a 16-bit composite value, where each bit is HIGH if that value's comparison is true - i.e. in_a_eq_b tests equality between the three 12-bit input values:

• Bit 0 high if in[0] = in[0],
• Bit 1 high if in[0] = in[1],
• Bit 2 high if in[0] = in[2],
• Bit 3 high if in[0] = in[3],
• Bit 4 high if in[1] = in[0],
• Bit 5 high if in[1] = in[1],
• Bit 6 high if in[1] = in[2],
• Bit 7 high if in[1] = in[3],
• ...etc

And these can be simplified down to:

• BIT 11 - in[2] = in[3]
• BIT  7 - in[1] = in[3]
• BIT  6 - in[1] = in[2]
• BIT  3 - in[0] = in[3]
• BIT  2 - in[0] = in[2]
• BIT  1 - in[0] = in[1]

Is that right?

Where do I go from there with it, though?  The flags output from tri_comp need to influence the LUT_LG#_SEL_XY lookup tables somehow, but I'm not sure how?  You mentioned using four LUTs:

Yes, the tri_comp gives you a set of flags which you may simplify just the ones you need into a new logic array, and feed that into 4 LUTs whose results will give your the sort selection based on sequence number and shape type.

Erm, so these LUTs will affect the LUT_LG#_SEL_XY tables or replace them?  I'm not sure how the new LUTs should look.

[nockieboy]

Aaah dammit... 

[BrianHG]

What's wrong?
What was that suppose to look like?

[nockieboy]

What's wrong?
What was that suppose to look like?

It's not supposed to have the line of dots through the centre of the large triangle.  It seems my fix works for triangles where X[1] is greater than X[0], but not the other way around.  I'm just testing a fix for this case.

[BrianHG]

LUT Method:
Well, you need a LUT, right, 4 possible coordinates to set in the source lines.

There will be 2 sorting, 1 for triangles, 1 for quads.
The each sorting will have an output for first half or the triangle, then a second for the second half.

Feeding the compare module with Y[n], look at the  in_a_gt_b.

What's important is
y0>y1
y0>y2
y0>y3
y1>y2
y1>y3
y2>y3

That's 6 bitst for which shape, triangle or quad, so, make a 7 bit logic array:

Code: [Select]

y_cmp_sort = {in_a_gt_b[y2>y3],in_a_gt_b[y1>y3],in_a_gt_b[y1>y2],in_a_gt_b[y0>y3],in_a_gt_b[y0>y2],in_a_gt_b[y0>y1]} ;

Next, make a lut name:

Code: [Select]

logic [1:0]  LUT_SORT_SEL_LG  [0:511]  = '{  //  LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, COORD[1],COORD[0] } ]
// xy[3],xy[2],xy[1],xy[0],  xy[3],xy[2],xy[1],xy[0],
// Triangle  Quadra
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3],![y0>y2],![y0>y1] = 000000
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3],![y0>y2], [y0>y1] = 000001
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3], [y0>y2],![y0>y1] = 000010
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3], [y0>y2], [y0>y1] = 000011

.......  }; // Cross look up table.
Each 0,0,0,0 should have the new corresponding 0,1,2,3 filled in.

For you, it may be easier just to use the 'IF()' method.  IE, copy the basic code.

you should make an 4 12bit signed byte arrays:
sorted_x[ # ]
sorted_y[ # ]
And set them at line 553 in the latest geometry_xy_plotter code.

Code: [Select]

sorted_x[0] <= x[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd0 } ];
sorted_x[1] <= x[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd1 } ];
sorted_x[2] <= x[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd2 } ];
sorted_x[3] <= x[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd3 } ];
sorted_y[0] <= y[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd0 } ];
sorted_y[1] <= y[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd1 } ];
sorted_y[2] <= y[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd2 } ];
sorted_y[3] <= y[LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, 2'd3 } ];

Then in the 2 linegens:

Code: [Select]

  .aX             ( x[lgen_1ax]        ), // 12-bit X-coordinate for line start
  .aY             ( y[lgen_1ay]        ), // 12-bit Y-coordinate for line start
  .bX             ( x[lgen_1bx]        ), // 12-bit X-coordinate for line end
  .bY             ( y[lgen_1by]        ), // 12-bit Y-coordinate for line end
change those 2 into the 'sorted_x/y[ ... ]'

I hope this gives you ideas.
You may need to change the 'line_gen_starter' into a FF to delay the start by 1 clock for the new delayed 'sorted_xy[ # ]'s.

[nockieboy]

What's wrong?
What was that suppose to look like?

It's not supposed to have the line of dots through the centre of the large triangle.  It seems my fix works for triangles where X[1] is greater than X[0], but not the other way around.  I'm just testing a fix for this case.

Okay, fixed that issue.  Turns out some shapes (rectangles) need to have delays on the linegens whilst others don't.

[nockieboy]

LUT Method:
Well, you need a LUT, right, 4 possible coordinates to set in the source lines.

There will be 2 sorting, 1 for triangles, 1 for quads.
The each sorting will have an output for first half or the triangle, then a second for the second half.

Feeding the compare module with Y[n], look at the  in_a_gt_b.

What's important is
y0>y1
y0>y2
y0>y3
y1>y2
y1>y3
y2>y3

That's 6 bitst for which shape, triangle or quad, so, make a 7 bit logic array:

Code: [Select]

y_cmp_sort = {in_a_gt_b[y2>y3],in_a_gt_b[y1>y3],in_a_gt_b[y1>y2],in_a_gt_b[y0>y3],in_a_gt_b[y0>y2],in_a_gt_b[y0>y1]} ;

Oookay... but why a 7-bit logic array to hold 6 bits of data?

Next, make a lut name:

Code: [Select]

logic [1:0]  LUT_SORT_SEL_LG  [0:511]  = '{  //  LUT_SORT_SEL_LG[ { y_cmp_sort , SHAPE_IS_QUAD, COORD[1],COORD[0] } ]
// xy[3],xy[2],xy[1],xy[0],  xy[3],xy[2],xy[1],xy[0],
// Triangle  Quadra
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3],![y0>y2],![y0>y1] = 000000
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3],![y0>y2], [y0>y1] = 000001
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3], [y0>y2],![y0>y1] = 000010
   0,0,0,0, 0,0,0,0,  // ![y2>y3],![y1>y3],![y1>y2],![y0>y3], [y0>y2], [y0>y1] = 000011

.......  }; // Cross look up table.
Each 0,0,0,0 should have the new corresponding 0,1,2,3 filled in.

Riiight.. okay, well I've completed the LUT structure, but have yet to populate all the order combinations.  Any chance you could let me know if I'm on the right track?  The new LUT starts at line 233 in the attached code.

For you, it may be easier just to use the 'IF()' method.  IE, copy the basic code.

Hmm, well as soon as I spot a pattern in the table, I'm sure filling out the LUT will speed up.  Otherwise, I've only done the first four lines so far. 

EDIT:  Okay, so there's some weirdness going on here.  Some of the lines in the table are fine, but some are impossible and would (should?) never arise, unless some coordinates are exactly equal to each other, then all bets are off.

Take, for example, this case:

Code: [Select]

0,0,1,2, 1,2,3,0,  // ![y2>y3],![y1>y3],![y1>y2], [y0>y3],![y0>y2],![y0>y1] = 000100

The statement says that y3>y2, y3>y1, y2>y1, y0>y3, y2>y0, y1>y0 for a y_cmp_sort value of 000100.

How can y3 be greater than y2 when y0 is greater than y3, but y2 is greater than y0?  What should I be putting into the ordered coordinate values for lines like these?  Does it matter?  In theory, these cases will only arise when two sets of Y-coordinates are on the same line, so presumably it shouldn't matter in what order they go - except that it does for a quad?

Have I got the values the wrong way around as well? (i.e. the line above, should that be: 2,1,0,0 0,3,2,1 ?)

[BrianHG]

Yes, there are some impossible states.
Also, I go this backwards:

Code: [Select]

// xy[3],xy[2],xy[1],xy[0],  xy[3],xy[2],xy[1],xy[0],
It should be:

Code: [Select]

// xy[0],xy[1],xy[2],xy[3],  xy[0],xy[1],xy[2],xy[3],
So, flip everything around.
As for the lemmon states, just copy the best state which would still generate a valid output, or use 0,1,2,3.

Also for the triangle, I guess you can make xy[3] always equal 3 so it is passed through.

1 last thing, there is so much junk here, you can just engineer it as a module with an

Code: [Select]

input   clock
input   bypass            // makes output x_sort[0] to x_sort[3] = x_in[0] to x_in[3] no matter what.  Same for Y
input   shape_quad
input signed [11:0] x_in [0:3],
input signed [11:0] y_in [0:3],
output signed [11:0] x_sort [0:3],
output signed [11:0] y_sort [0:3],
output all_x_equal    // when drawing a triangle, only compare x0...x2, otherwise compare x0...x3
output all_y_equal    // when drawing a triangle, only compare x0...x2, otherwise compare x0...x3

Or you can make this part of the 'tri_comp' module.
This way if you want to change the lut_table to IF(a>b>c), you wont need to mangle the rest of the code.
The IF method compiles and simulates faster than the LUT and also eliminates those pesky dead conditions.

[nockieboy]

1 last thing, there is so much junk here, you can just engineer it as a module with an

Code: [Select]

input   clock
input   bypass            // makes output x_sort[0] to x_sort[3] = x_in[0] to x_in[3] no matter what.  Same for Y
input   shape_quad
input signed [11:0] x_in [0:3],
input signed [11:0] y_in [0:3],
output signed [11:0] x_sort [0:3],
output signed [11:0] y_sort [0:3],
output all_x_equal    // when drawing a triangle, only compare x0...x2, otherwise compare x0...x3
output all_y_equal    // when drawing a triangle, only compare x0...x2, otherwise compare x0...x3


Wait, what?  We're sorting X-coordinates as well? 

The IF method compiles and simulates faster than the LUT and also eliminates those pesky dead conditions.

I suppose the IF method also doesn't use up valuable RAM - or are LUTs stored in some other way?

Must admit - the IF method is very tempting.  I've got 64 sets of 8 values to enter... 

[BrianHG]

You are sorting based only the Y coordinates, but, remember, the coordinates come in pairs....
The IF method is easier to debug or swap output order as well.

Also add these 4 outputs:

signed [11:0] y-min
signed [11:0] y-max
signed [11:0] x-min
signed [11:0] x-max

If all Y coordinates are equal, then we sort based on the coordinates from x-min to x-max.
This is so you can generate an optimized horizontal only line, or vertical only line.
IE, run only 1 line generator once for the filled triangle or filled quadrilateral.

The IF() else IF() method would simplify down in gate much easier.

Remember, the module takes in the x/y 0,1,2,3, and spits out a new x/y 0,1,2,3 where the linegens always use those new outputs in the same order expecting the points to be ordered from low to high.

While the all_x_equal / all_y_equal tells the linegens section to skip a filled geometric shape and just draw 1 single line from min to max.

[nockieboy]

Okay, so I'm ready to make a start on this in the morning, just want to clarify this point:

Aside from the x/y-min/max outputs, the IF...ELSE IF structure is going to replace the new LUT and it's 512 values based off of the y_cmp_sort value and instead I'll be doing something similar to this?

Code: [Select]

if ( ( Y[0] >=  Y[1] ) && ( Y[1] >= Y[2] ) ) begin
    sorted_x[0] = x[2] ;
    sorted_y[0] = y[2] ;
    sorted_x[1] = x[1] ;
    sorted_y[1] = y[1] ;
    sorted_x[2] = x[0] ;
    sorted_y[2] = y[0] ;
    sorted_x[3] = x[3] ;
    sorted_y[3] = y[3] ;
end else if ( etc...)

But I'd need to include Y[3] in the conditionals as well?

And this would replace the tri_comp module as well, wouldn't it?  Can't see a need for tri_comp if I'm doing all the IF..ELSE IF structure?

[BrianHG]

Code: [Select]

always_ff @(posedge clk) begin

if (bypass) begin
for ( int i=0; i<=3 ; i++ ) begin
    sorted_x[i] <= x[i] ;
    sorted_y[i] <= y[i] ;
end
end else if (~shape_quad) begin // all triangle logic
    sorted_x[3] <= x[3] ;
    sorted_y[3] <= y[3] ;

if ( ( Y[0] >=  Y[1] ) && ( Y[1] >= Y[2] ) ) begin
    sorted_x[0] <= x[2] ;
    sorted_y[0] <= y[2] ;
    sorted_x[1] <= x[1] ;
    sorted_y[1] <= y[1] ;
    sorted_x[2] <= x[0] ;
    sorted_y[2] <= y[0] ;
end else if ( etc...)


end else begin // sorting for a triangle end, now sorting for a quadrilateral.

end

[/quote]

Finish this then we will worry about adding the IF ( y[0] == y[1] == y[2] ) at the top to sort the first linegen X min and X max as well as finish the all equal outputs.

Also, remember at the inputs,
input clk,
input enable,  // !pixel writer busy input...

I would also prefer feeding through this module the drawing function and drawing color as it should appear as a pipe in the command chain to the next lingen modules.

[nockieboy]

Okay, check out attached geo_xy_plotter module - line 684 onwards is the new poly_sort module.  Have done the triangle and quad sorting.

I would also prefer feeding through this module the drawing function and drawing color as it should appear as a pipe in the command chain to the next lingen modules.

Well this module is going to introduce a clock delay, so that makes sense I guess.  I'm just unsure how to feed the drawing function and colour through?  Should I be feeding geo_shape, geo_fill, geo_color etc into poly_sort, or passing in the fifo_cmd_in input from geo_xy_plotter, or...?

[BrianHG]

Well this module is going to introduce a clock delay, so that makes sense I guess.  I'm just unsure how to feed the drawing function and colour through?  Should I be feeding geo_shape, geo_fill, geo_color etc into poly_sort, or passing in the fifo_cmd_in input from geo_xy_plotter, or...?

Check out line 412:

Code: [Select]

    line_gen_starter     = !reset && ( !fifo_cmd_rdy_n && !geo_run ) && ( command_in[7:5] == 3'd0 && command_in[3:0] != 4'd0 )    ; // for now, only the draw line command

Now you just need to delay the ' line_gen_starter ' by 1 clock and everything should be honky dory.
Now tell me where you will be moving that line to to that?