6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Tue Nov 12, 2024 3:37 pm

All times are UTC




Post new topic Reply to topic  [ 609 posts ]  Go to page Previous  1 ... 26, 27, 28, 29, 30, 31, 32 ... 41  Next
Author Message
PostPosted: Tue Apr 09, 2013 2:18 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
I see your problem. I don't recall issues with fat lines but I will dust off my AVR video project and test those same coordinates to see.

A better alternative, which I have been noodling out, may be to split the slope processing into 4 groups (right now its only two - slope up or slope down). The new groups would be positive slope with DX > DY, positive slope with DX<= DY, negative slope with DX>DY, and neg slope with DX<=DY. That way will be faster as each interation through the loop results in 1 point being plotted. The lines should also be thinner! The downside is a little heavier processing up front (1 division) but the end result should be worth it unless you draw a lot of very short sloped lines.

I will test the current method on the AVR and let you know the results. Thanks for your help and sorry for all the frustrations I'm sure your having.

Daryl

_________________
Please visit my website -> https://sbc.rictor.org/


Top
 Profile  
Reply with quote  
PostPosted: Tue Apr 09, 2013 2:51 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
No frustration here, no timetable either so it's all good. I enjoy the troubleshooting aspect. Looking forward to your code! Also, I would be grateful if you would see if you get the same results on your AVR project. I have this nagging feeling it's something I'm doing wrong.

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


Top
 Profile  
Reply with quote  
PostPosted: Tue Apr 09, 2013 5:02 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
It might be helpful to plot some lines of various slopes to verify if the issue is confined to one region.

Try
0,240 (common start point

to:
50, 0 (steep + slope)
240,0 (45 + degree)
640, 160 (low + slope)
640, 400 (low - slope)
240, 480 (45 - slope)
50, 480 (steep - slope)

You could also run a loop stepping x from 0 to 640 by 20's using y=0 and y=480 and use 320,240 as the origin.
Then step y from 0 to 480 by 20's with x=0 and x=640 with the same origin to cover the everything.

It might prove useful in the debugging.

Daryl

_________________
Please visit my website -> https://sbc.rictor.org/


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 10, 2013 4:55 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
ElEctric_EyE wrote:
No frustration here, no timetable either so it's all good. I enjoy the troubleshooting aspect. Looking forward to your code! Also, I would be grateful if you would see if you get the same results on your AVR project. I have this nagging feeling it's something I'm doing wrong.


Just dusted off the AVR project. I set up a line from 5,0 to 319, 199 (max display size) but it is not drawing correctly at all. Looks more like 319, 80. I will need to take some time to see what I messed up. I know this worked on my SBC-3.
Guess I didn't quite test the AVR thoroughly enough.

Will keep you informed.

Daryl

_________________
Please visit my website -> https://sbc.rictor.org/


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 10, 2013 11:23 am 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
8BIT wrote:
Just dusted off the AVR project. I set up a line from 5,0 to 319, 199 (max display size) but it is not drawing correctly at all. Looks more like 319, 80. I will need to take some time to see what I messed up. I know this worked on my SBC-3...

When you say it worked on your SBC-3, did you notice the issue with double wide pixels?

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


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 10, 2013 12:15 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
ElEctric_EyE wrote:
When you say it worked on your SBC-3, did you notice the issue with double wide pixels?


There were no noticable issues with the lines at all. I did not use the optimization method I added to you code. My first post of the line drawing code was taken directly from the SBC-3 drawing routine.

Daryl

_________________
Please visit my website -> https://sbc.rictor.org/


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 10, 2013 2:40 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Ok, I went back to that one did a few basic changes to some of the branches and made a video where the program plots lines from the center and does a radar sweep. You can see some error creep in on the right side. I did this for a speed reference. When the timer was active for plotting 1 line from (319,239) to (0,0) it took 7,278,210 cycles.


Attachments:
Line16.f.asm [4.45 KiB]
Downloaded 65 times

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502
Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 10, 2013 9:09 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Aha! I found an error.
There are 3 times in your original code, without optimizations, an LSR is done before modifying the DX & DY variables on lines 17,31,80. Removing these, got rid of the errors. So the radar sweep results in a solid screen now. Also, it's abit faster. I removed the check for when DX or DY was zero as well.

Next step is to replace all the JSR PLTPXL and insert the actual plot code.


Attachments:
Line16.g.asm [4.45 KiB]
Downloaded 61 times

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502
Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 10, 2013 10:37 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
8BIT wrote:
...A better alternative, which I have been noodling out, may be to split the slope processing into 4 groups (right now its only two - slope up or slope down). The new groups would be positive slope with DX > DY, positive slope with DX<= DY, negative slope with DX>DY, and neg slope with DX<=DY. That way will be faster as each interation through the loop results in 1 point being plotted...

This is going to be the way to go I think as well.

There's an error plotting a single line from (319,239) to (320,0), it only shifts to the right at the very last pixel, so doing an LSR for DY might work in this case. Also I tried (320,0) to (319,239) with the same result.

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


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 11, 2013 2:25 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
I have created and tested the new line drawing routine. This is using QuickBASIC. I placed my line next to the line generated by the built-in QB LINE function and they look almost identical accross a wide range of slopes.

I am attaching the source. The next step will be convert this to assembly. It does require 1 division which will always be a positive fraction, i.e. 200/245 or 2/630. The best way to do this in my mind is to make this a 32 bit number divided by a 16 bit number. We essentially multiply the top number by 65536 then do the division. The 16 bit result is the fractional value. This value gets added to an intermediate variable and a carry indicated time to adjust the lesser axis plot point (hope that makes sense).

Daryl


Attachments:
LINE.BAS.TXT [1.76 KiB]
Downloaded 62 times

_________________
Please visit my website -> https://sbc.rictor.org/
Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 11, 2013 11:14 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Multiplying by 65536 would not be a problem in the .b core but the fraction would slow things down...
Back when I was trying to do lines in Verilog, I was trying to implement Bresenham because it works with integers only. Arlet got pretty far with his implementation that drew multiple lines from a single point. One thing I have considered is experimenting with Verilog to write the coordinates straight to RAM... Anyway, this is the most optimized one, near the bottom of the wiki page, for 1 slope:
Code:
plotLine(x0,y0, x1,y1)
  dx=x1-x0
  dy=y1-y0

  D = 2*dy - dx
  plot(x0,y0)
  y=y0

  for x from x0+1 to x1
    if D > 0
      y = y+1
      plot(x,y)
      D = D + (2*dy-2*dx)
    else
      plot(x,y)
      D = D + (2*dy)

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


Top
 Profile  
Reply with quote  
PostPosted: Fri Apr 12, 2013 12:40 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
ElEctric_EyE wrote:
Multiplying by 65536 would not be a problem in the .b core but the fraction would slow things down...
Back when I was trying to do lines in Verilog, I was trying to implement Bresenham because it works with integers only. Arlet got pretty far with his implementation that drew multiple lines from a single point. One thing I have considered is experimenting with Verilog to write the coordinates straight to RAM... Anyway, this is the most optimized one, near the bottom of the wiki page, for 1 slope:
Code:
plotLine(x0,y0, x1,y1)
  dx=x1-x0
  dy=y1-y0

  D = 2*dy - dx
  plot(x0,y0)
  y=y0

  for x from x0+1 to x1
    if D > 0
      y = y+1
      plot(x,y)
      D = D + (2*dy-2*dx)
    else
      plot(x,y)
      D = D + (2*dy)


This should be easier to implement and faster too.

_________________
Please visit my website -> https://sbc.rictor.org/


Top
 Profile  
Reply with quote  
PostPosted: Fri Apr 12, 2013 1:37 am 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
8BIT wrote:
This should be easier to implement and faster too.

This is great then!
You could work on this algorithm and hopefully for your benefit as well!
As for me, I would like to tackle the Verilog, realizing the project speed will take a big hit with this extra burden of a hardware line plotter. If I'm successful with the Veriog, the cpu speed should match the pixel clock @ at least 25MHz, but hopefully 50MHz. This would be something worth comparing against your software running on the present 100MHz .b core. :D

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


Top
 Profile  
Reply with quote  
PostPosted: Fri Apr 12, 2013 10:19 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
I don't know why I struggled months ago when I was first attempting Bresenham. Maybe I was trying to implement one of the unoptimized formula's. But it only took me an hour to get the example on the wiki to work, outputting the correct coordinates. I'll have to add a 'LOAD' input signal to this module, and an output 'DONE' signal, which will go to set one of the unused cpu flag bits. So far this is a separate module not part of the project yet, and I still have to add checks for the other slopes. This implementation uses 75 slice registers, 117 slice LUTs and 55 LUT FF pairs. Each pixel coordinate takes 2 cycles:
Code:
module LineGen ( input clk,
                 output reg [9:0] X = 0,         
                 output reg [8:0] Y = 0         
               );
               
reg [9:0] x0;
reg [8:0] y0;
reg [9:0] x1;   
reg [8:0] y1;
reg [9:0] dx;
reg [8:0] dy;
reg [16:0] D;

reg [2:0] state;
parameter LOAD = 0, CALC1 = 1, CALC2 = 2, PLOT = 3;
            
always @(posedge clk) begin
   state <= LOAD;

      case (state)
         LOAD:
            state <= CALC1;
            
         CALC1:
            state <= CALC2;
            
         CALC2:
            state <= PLOT;
               
         PLOT:
            if ( x0+1 <= x1 )
            state <= CALC2;
            else
            state <= LOAD;
      endcase
end

always @(posedge clk) begin
   case (state)
      LOAD:
      begin
         x0 <= 0;
         y0 <= 1;
         x1 <= 6;
         y1 <= 4;
      end

      CALC1:
      begin
         X <= x0;
         Y <= y0;
         dx <= x1 - x0;
         dy <= y1 - y0;
         D <= y1*2 - y0*2 - x1 + x0;
      end
   
      CALC2:
      if ( D[16] == 0 ) begin
            x0 <= x0 + 1;
            y0 <= y0 + 1;
            D <= D + dy*2 - dx*2;
         end
         else begin
            x0 <= x0 + 1;
            D <= D + dy*2;
         end
      
      PLOT:                        
      begin
         X <= x0;
         Y <= y0;
      end
endcase

end

endmodule


EDIT: Fixed the detect when D goes negative. Seems to work only when DX>DY.

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


Top
 Profile  
Reply with quote  
PostPosted: Sat Apr 13, 2013 2:30 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 9:02 pm
Posts: 1746
Location: Sacramento, CA
Very cool. I read in the WIKI that flipping the x & y coordinated before input then flipping them back on output is used in hardware frequently. That would essential flip DX and DY.

I have not started any code for the software approach. My weekend is full but will try to squeeze in some code time too.

Daryl

_________________
Please visit my website -> https://sbc.rictor.org/


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 609 posts ]  Go to page Previous  1 ... 26, 27, 28, 29, 30, 31, 32 ... 41  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 14 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: