16.16 integer fixed-point line drawer :)

[paul_nicholls]

Hi all,
If any of you are interested, I have created a very simple and fast 16.16 integer based fixed-point 2d line drawer.

This means the code uses numbers with 16 bit integer part, and 16 bit fractional part.

The idea is definitely not new and I didn't invent it but here it is for anyone to use :)




Type
{................................................. ..........................}
TFixed = LongInt;
TInterpolant = Record
Value : TFixed;
Delta : TFixed;
End;
{................................................. .............................}

{................................................. .............................}
Function CalculateInterpolant(v1,v2,span : LongInt) : TInterpolant;
Begin
Result.Value := v1 * 65536;
Result.Delta := 0;
If span > 0 Then Result.Delta := ((v2 - v1) * 65536) Div span;
End;
{................................................. .............................}

{................................................. .............................}
Procedure SDLSurface_DrawLine2d(Const s : PSDL_Surface;
x1,y1,x2,y2 : Integer;
Const r,g,b,a : Byte;
Const SetPixel : TSetPixel);
Var
x,y : Integer;
dx,dy : Integer;
span : Integer;
i : Integer;
ix,iy : TInterpolant;
Begin
dx := Abs(x2 - x1);
dy := Abs(y2 - y1);
Case dx >= dy Of
False : span := dy;
True : span := dx;
End;
ix := CalculateInterpolant(x1,x2,span);
iy := CalculateInterpolant(y1,y2,span);
For i := 0 To span Do
Begin
x := ix.Value Shr 16;
y := iy.Value Shr 16;
SetPixel(s,x,y,r,g,b,a);
Inc(ix.Value,ix.Delta);
Inc(iy.Value,iy.Delta);
End;
End;



Enjoy :)
cheers,
Paul

[noeska]

what is/are its advantage(s) over other ways? Speed?

[paul_nicholls]

what is/are its advantage(s) over other ways? Speed?

It is faster than using floating point numbers to calculate points on the line, and it is simpler (and possibly faster) than using the Bresenham integer line drawer.

cheers,
Paul

[pstudio]

Have you tested it against Bresenham's technique?

Also... is it faster to use a case than a if then else?
I find it funny to use a case to test a boolean.

[paul_nicholls]

Have you tested it against Bresenham's technique?

Also... is it faster to use a case than a if then else?
I find it funny to use a case to test a boolean.

I haven't tested it yet against the Bresenham technique, but my version doesn't have any if-then statements in the main loop like that version does, so it may be faster in that respect.

I haven't looked at the assembly generated so I am not sure if the case is faster/slower than an if-then instead.

Perhaps this would be faster:

changing this:



Case dx >= dy Of
False : span := dy;
True : span := dx;
End;


to:



span := dy;
If dx >= dy Then span := dx;


I still haven't got any timing figures, but here is a rewrite to get rid of the CalculateInterpolant() function call too:



Procedure SDLSurface_DrawLine2d(Const s : PSDL_Surface;
x1,y1,x2,y2 : Integer;
Const r,g,b,a : Byte;
Const SetPixel : TSetPixel);
Var
x,y : Integer;
spanx : Integer;
spany : Integer;
span : Integer;
i : Integer;
ix,iy : TInterpolant;
Begin
spanx := Abs(x2 - x1);
spany := Abs(y2 - y1);
span := spany;
If spanx >= spany Then span := spanx;
ix.Value := x1 * 65536;
iy.Value := y1 * 65536;
ix.Delta := 0;
iy.Delta := 0;
If span > 0 Then
Begin
ix.Delta := ((x2 - x1) * 65536) Div span;
iy.Delta := ((y2 - y1) * 65536) Div span;
End;
For i := 0 To span Do
Begin
x := ix.Value Shr 16;
y := iy.Value Shr 16;
SetPixel(s,x,y,r,g,b,a);
Inc(ix.Value,ix.Delta);
Inc(iy.Value,iy.Delta);
End;
End;

Also if anyone wants to do some timing tests, here is a bresenham version I translated from C code:



Procedure SDLSurface_DrawLine2d(Const s : PSDL_Surface;
x1,y1,x2,y2 : Integer;
Const r,g,b,a : Byte;
Const SetPixel : TSetPixel);
Var
i,dx,dy,sdx,sdy,dxabs,dyabs,x,y,px,py : Integer;
Begin
dx := x2 - x1; // the horizontal distance of the line
dy := y2 - y1; // the vertical distance of the line
dxabs := Abs(dx);
dyabs := Abs(dy);
sdx := Sign(dx);
sdy := Sign(dy);
x := dyabs Shr 1;
y := dxabs Shr 1;
px := x1;
py := y1;

SetPixel(s,px,py,r,g,b,a);
If dxabs >= dyabs Then // the line is more horizontal than vertical
Begin
For i := 0 To dxabs - 1 Do
Begin
y := y + dyabs;
If y >= dxabs Then
Begin
y := y - dxabs;
py := py + sdy;
End;
px := px + sdx;
SetPixel(s,px,py,r,g,b,a);
End;
End
else // the line is more vertical than horizontal
Begin
For i := 0 To dyabs - 1 Do
Begin
x := x + dxabs;
If x >= dyabs Then
Begin
x := x - dyabs;
px := px + sdx;
End;
py := py + sdy;
SetPixel(s,px,py,r,g,b,a);
End;
End;
End;

cheers,
Paul

[LP]

Also if anyone wants to do some timing tests, here is a bresenham version I translated from C code:


Yes, this is one variant of Bresenham algorithm. However, your own algorithm can be adapted to give Bresenham lines without branching. Something like this (very short example):


Span:= Max(Abs(y2 - y1), Abs(x2 - x1));

if (Abs(y2 - y1) > Abs(x2 - x1)) then
begin // vertical line
y:= Min(y1, y2);
x := x1 * 65536;
dx:= (x2 - x1) * 65536 div Span;

// !! if y2 < y1, set x to x2 and invert dx here

for i&#58;= 0 to Span - 1 do
begin
PutPixel&#40;x div 65536, y + i&#41;;
Inc&#40;x, dx&#41;;
end;
end else // do the same, but on x axis
end;


In the above example, the inner loop has no branching and produces clean lines like the Bresenham algorithm.

[paul_nicholls]

Hi Lifepower,
I am not sure what you mean by not branching...

Both my code and the snippit you posted has if-then statements outside of the main loop(s), and non inside the main loop(s).

Can you clarify what you mean?

cheers,
Paul

[LP]

The Bresenham's algorithm has branching in the inner loop, which may be slower; your routine, on the other hand, may produce non-solid lines because you advance on both axes simultaneously, which may give errors with lack of precision.

The alternative I suggested produces Bresenham looking lines without branching in the inner loop and is faster than both - it has one less increment in the inner loop than your routine and suffers less with lack of precision. The only drawback is slightly higher setup cost (max and min functions can be branchless, by the way). It requires minimal modifications to your code, so I suggest you try it.

[paul_nicholls]

The Bresenham's algorithm has branching in the inner loop, which may be slower; your routine, on the other hand, may produce non-solid lines because you advance on both axes simultaneously, which may give errors with lack of precision.

The alternative I suggested produces Bresenham looking lines without branching in the inner loop and is faster than both - it has one less increment in the inner loop than your routine and suffers less with lack of precision. The only drawback is slightly higher setup cost (max and min functions can be branch less, by the way). It requires minimal modifications to your code, so I suggest you try it.

Hi Lifepower,
I can see your point that your alternative may be faster in the inner loop as it only has 1 increment instead of 2.

On the other hand, my unmodified version shouldn't produce non-solid lines due to the fact that the primary? span will produce a increment of -1 or +1 only for that variable.

I may try modifying my code to see if I can do as you suggested anyhow.

cheers,
Paul