6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Sat Nov 23, 2024 11:18 am

All times are UTC




Post new topic Reply to topic  [ 56 posts ]  Go to page Previous  1, 2, 3, 4  Next
Author Message
PostPosted: Fri Nov 16, 2012 6:07 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
An issue I'm having on paper is I have to test for a negative slope for X, in order to know when to decrease the horizontal pixel counter
Code:
If ( X1 - X0 ) < 0
and let's say X0, X1 are 9 bit registers. I think in Verilog for this to work, I have to have a separate 10 bit register to store the result and test the 10th bit for '1'. Can anyone comment on my suspicion?

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Fri Nov 16, 2012 7:21 pm 
Offline

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679
ElEctric_EyE wrote:
Hi WF, I have read you first post more than once and it is packed with info. And thanks for responding again. I need to do more research, but I figured I could get any line drawing algorithm, get the outputted X and Y coordinates into a BRAM, then sort them by Y. This is probably not the most efficient method though. Have you ever done something similar?


I've done a kabillion different software renderers, both commercially and for hobby use. I understand a lot of the hardware design issues, but I'm not technically a hardware guy. What you describe will work, but obviously you'll be very limited in terms of how many lines you can store per frame. I think the idea of the scanline buffer and drawing lines in parallel as the screen is scanned is a really cool and very doable idea.

In your prerendered list-of-points approach, you don't actually need to sort the list of points by Y: Draw from point A to point B. If A's y-coordinate is greater than B's y-coordinate, then swap the 2 points before you even begin. Then the natural loop ordering from A to B will always be in increasing Y order. (well, technically non-decreasing order)

Regarding the comparison, can you access the carry output of the subtraction? If not, then yes you need the result to be wide enough that a set MSB unambiguously indicates a negative number. Given two 9-bit unsigned input values, the output must be at least 10 bits. Not sure about the Verilog specifics, though.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor


Top
 Profile  
Reply with quote  
PostPosted: Fri Nov 16, 2012 9:56 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
White Flame wrote:
I've done a kabillion different software renderers, both commercially and for hobby use...

Excellent, glad to have your input!

I'm pretty sure about detecting the negative numbers as Arlet uses the same detector in his H/VSync generator on a count down circuit, I was just wondering if there was a better way to do it in my situation...

One more question for Verilog experts. Can I do something like this to either increase or decrease a counter, depending on whether sx = 0 or 1?
Code:
x0 = sx ? x0 + 1 :
          x0 - 1;

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Fri Nov 16, 2012 10:12 pm 
Offline
User avatar

Joined: Mon Apr 23, 2012 12:28 am
Posts: 760
Location: Huntsville, AL
Quote:
One more question for Verilog experts. Can I do something like this to either increase or decrease a counter, depending on whether sx = 0 or 1?
Code:
x0 = sx ? x0 + 1 :
          x0 - 1;


Yes, but as code I expect that it will be a combinatorial logic loop since it is an asynchronous logic construction that you're using, and the output variable is also an input variable. If x0 is registered, then the operation will synthesize to a single add/sub primitive.

_________________
Michael A.


Top
 Profile  
Reply with quote  
PostPosted: Fri Nov 16, 2012 10:24 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
It's probably easier to say:
Code:
if( x1 < x0 )

But if you want to get access to the carry, just do temp <= x1 - x0, where temp has 1 bit more than x0 and x1. The MSB of temp will contain the carry out.


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 2:21 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Thanks for the tip and confirmation...

I think I finally get it. I haven't been able to throw alot of time at this and so I'm making small steps. But I think of the problem often and I've come to the conclusion that I'm going to have to use division. At least for the first step, until I can comprehend a different way. For a more horizontal line (i.e. dx>dy) I will have to use dx/dy in order to know when to perform y=y+1. For a more vertical line (dy>dx) I'll have to use dy/dx in order to know when to perform x=x+1 or x=x-1, depending on sx, the slope of the line.

I have 3 days off this week, so I'll be able to focus on completing the code and seeing the results. Because Verilog doesn't do fractions, the division is going to present a rounding error. How to properly and accurately deal with this fact is where I am conceptually at right now.

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 2:42 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Bresenham's method doesn't use division. For vector based drawing where you draw the lines top-down during a scan I recommend replacing the division by a multiplication.

By the way, verilog supports the division operator, but ISE won't synthesize it.


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 4:06 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Multiplication? What is your concept?

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 4:32 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
For each scanline, we know the Y coordinate, but the problem is figuring out the X coordinate. If the line starts at (x0, y0) and goes to (x0+dx, y0+dy), we can determine x = x0 + y * dx/dy. The dx/dy fraction is constant and we can calculate it in advance, and store it in the block RAM with the other line parameters. The advance calculation could be done by the CPU using a software division algorithm, or maybe in hardware during vertical sync.

Note that I've simplified the problem somewhat. For flat lines (dx > dy), you need both a starting X and a stopping X for each Y, and draw a short horizontal line between them. Also,the case dy=0 needs to be handled properly.

Another method is to use a Bresenham algorithm. It avoids the multiplication/division, but requires keeping track of the 'err' values in a memory, as well as the current X coordinate. If you don't care about the memory consumption, it is probably an easier method overall.


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 9:00 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Arlet wrote:
...Note that I've simplified the problem somewhat. For flat lines (dx > dy), you need both a starting X and a stopping X for each Y...

This is the part I am wrestling with. For lines dx>dy, this amount is dx/dy before going on to the next scanline. A similar situation for lines dy>dx... Maybe I will go back to Bresenham formula and figure something out for
Code:
if e2 > -dy then
. This is really the only part holding me up, from that angle of attack, which is why I started down the path of my previous post.

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 9:14 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
ElEctric_EyE wrote:
For lines dx>dy, this amount is dx/dy before going on to the next scanline.

Yes, but if you precalculate dx/dy, this value is already available. If you're willing to use some memory, a simple method is just to add dx/dy to the old x coordinate, to produce the new one. Then draw a horizontal line segment between old x and new x.


Top
 Profile  
Reply with quote  
PostPosted: Sun Nov 18, 2012 9:32 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Ok, I see. So if I understand correct, the length of this dx/dy table would be 1/2 total horizontal resolution? And I could use the same table for dy/dx?

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Mon Nov 19, 2012 6:28 am 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Since we've discussed several ways to draw lines, there may be some confusion here. I'm talking about the "vector type" display, where lines are generated on the fly, based on a table with line info (x0, y0, dx/dy). For every line currently on the screen, there would be an entry in this table, containing a dx/dy value. So if you have 1000 lines on the screen, there would be 1000 precalculated dx/dy values. Since all lines are drawn during a scan, the Y coordinate is known, so there's only a need for a dx/dy value to calculate the corresponding X, We don't need a dy/dx.

For a line drawing method where you store the pixels (either in a table or in a bitmap), the Bresenham method is much easier, since it avoids the division altogether.


Top
 Profile  
Reply with quote  
PostPosted: Tue Nov 20, 2012 12:18 am 
Offline

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679
Note that you also need to store x1 and y1 in the line info, so you know where to stop. I agree that adding a fixed-point delta is probably going to be the most straightforward approach, but it might be more memory hungry than Bresenham (doubling of register sizes due to fixed-point calculations), and needs to perform all those divisions before it can start working.

EE: He's not talking about a lookup table to calculate dx/dy, but a table which holds the info for every active line you'll be drawing. Each line will have to have its slope delta calculated via a fixed-point-result division operation once per frame.

Regarding lines where dx>dy (ie, multiple pixels per scanline), the logic remains this for when you're using fixed-point deltas:

You need to remember both the old x and the new x' = x + dx/dy:
  • If x' is still the same as x, then just draw the 1 pixel. This is a vertical portion of the line.
  • If x' changed, then draw all the pixels between x and x', not including x.

If you're using Bresenham, then each pass of the 'error' accumulation loop will plot 1 pixel in your horizontal span of the line.

But yeah, there are a number of approaches being batted around. Focusing on learning one that you don't already know, or focusing on implementing one which you do know would be good.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor


Top
 Profile  
Reply with quote  
PostPosted: Tue Nov 20, 2012 8:21 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
I think I bit off more than I can chew with this goal of line drawing project in pure Verilog, but I will stick with Bresenham...
I found a line drawing module on github within the orsoc project I had looked into before. I had missed it the first time. At the very least, it gave me clues to the structure needed of a line drawing state machine in Verilog. The prep_state is the only one that appears correct. The other 2 'state's are incomplete at this point and nothing is tested. Currently, I manually set the internal x0,x1,y0,y1 variables. When it's functional, these 4 will be inputs.
Critique's of the code are most welcome, even flaming critiques. :lol:

Code:
module LineGen( input clk108,
                input countflag,            //flag, plot inside borders
                input vblank,
                input vsync,
                output reg [9:0] X,         //H component of pixel to BRAM
                output reg [8:0] Y         //V component of pixel to BRAM
               );
               
reg [9:0] x0 = 0;
reg [9:0] x1 = 639;         
reg [8:0] y0 = 0;
reg [8:0] y1 = 479;
reg [9:0] dx;
reg [8:0] dy;
reg [9:0] err;
reg [10:0] e2;
reg [0:0] sx;

reg [2:0] state;
parameter prep_state = 0, errcalc_state = 1, draw_state = 2;

//state machine for plotting a line
always @(posedge clk108)
   if ( vblank & vsync )
      state <= prep_state;
         else
            case (state)

               prep_state:                     //calculate dx/dy and slope of X
                  state <= errcalc_state;
            
               errcalc_state:                  //calculate error
                  state <= draw_state;
               
               draw_state:
                  if ( !countflag )
                     state <= prep_state;

            endcase
            
always @(posedge clk108) begin
   case (state)
      prep_state:                     
         begin
            if ( x1 > x0 ) begin         //negative "\" slope
               dx <= x1 - x0;
               sx <= 0;
            end
               else begin               //positive "/" slope
                  dx <= x0 - x1;
                  sx <= 1;
               end
      
            if ( y1 > y0)
               dy <= y1 - y0;
               else
                  dy <= y0 - y1;
         end
   
      errcalc_state:                     
         begin
            if ( dx > dy )
               err <= dx - dy;
               else
                  err <= dy - dx;
         end
   
      draw_state:
         begin
            e2 <= err + err;      
            X <= x0;
            Y <= y0;                     //output origin
            if ( e2 < dy ) begin
               err <= err + dy;
               x0 <= sx ? x0 + 1 :
                          x0 - 1;
               X <= x0;
            end
               else if (( x0 = err ) | ( y0 != y1 )) begin
                  y0 <= y0 + 1;
                  Y <= y0;
               end
         end
   endcase
end

endmodule

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 56 posts ]  Go to page Previous  1, 2, 3, 4  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 9 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: