Dear Adriaan,
I have been thinking about an improved Bressenham line drawing algorithm that eliminates this problem, but I never had the time to write one, maybe it already exists, it would be interesting.
I don't think this routine of mine is anything to brag about, but I'm curious to see what you think of it.
Integer arithemtic does not go much faster than real-number arithmetic (see our tests), and integer->real translation is fast, so I don't see any point in staying in integer-only math. Here's my line-drawer. The lines get clipped to a rectangle called analysis_bounds.
type {for 2-D integer geometry} ij_point_type=record i,j:integer; end; ij_line_type=record a,b:ij_point_type; end; ij_rectangle_type=record top,left,bottom,right:integer; end;
type {for 2-D real geometry} xy_point_type=record x,y:real; end; xy_line_type=record a,b:xy_point_type; end;
procedure draw_overlay_line (image_ptr:image_ptr_type;line:ij_line_type; color:overlay_pixel_type);
const rough_step_size=0.8;{pixels}
var num_steps,step_num:integer; p,q,step:xy_point_type; s:ij_point_type; image_rect:ij_rectangle_type; outside:boolean;
begin if not valid_image_ptr(image_ptr) then exit; if not valid_analysis_bounds(image_ptr) then exit; ij_clip_path(line,outside,image_ptr^.analysis_bounds); if outside then exit; if not ij_in_rectangle(line.a,image_ptr^.analysis_bounds) then exit; if not ij_in_rectangle(line.b,image_ptr^.analysis_bounds) then exit;
with line,image_ptr^ do begin overlay[a.j,a.i]:=color; overlay[b.j,b.i]:=color; p.x:=a.i; p.y:=a.j; q.x:=b.i; q.y:=b.j; s:=a; end;
if xy_separation(p,q)<rough_step_size then num_steps:=0 else num_steps:=round(xy_separation(p,q)/rough_step_size); step:=xy_scale(xy_difference(q,p),1/(num_steps+1));
for step_num:=1 to num_steps do begin p:=xy_sum(p,step); if p.x-s.i>0.5 then inc(s.i) else if p.x-s.i<-0.5 then dec(s.i); if p.y-s.j>0.5 then inc(s.j) else if p.y-s.j<-0.5 then dec(s.j); image_ptr^.overlay[s.j,s.i]:=color; end; end;
It is almost twice as fast as using round() to get s from p, and my 800 MHz iBook draws a 400-pixel line in 90 microseconds (-O3). The line clipping and checks at the top of the routine take up less than 10% of the execution time. As you can see, the rough step size of 0.8 makes sure we don't skip pixels. For 45-degree lines, we lose some efficiency. We could make the rough step size just under sqrt(2).
Yours, Kevan