Results 1 to 9 of 9

Thread: 16.16 integer fixed-point line drawer :)

  1. #1

    16.16 integer fixed-point line drawer :)

    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


    Code:
    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

  2. #2

    16.16 integer fixed-point line drawer :)

    what is/are its advantage(s) over other ways? Speed?
    http://3das.noeska.com - create adventure games without programming

  3. #3

    16.16 integer fixed-point line drawer :)

    Quote Originally Posted by noeska
    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

  4. #4

    16.16 integer fixed-point line drawer :)

    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.
    Imagine I've written something clever here inspiring you to make something awesome. If that happens give me credits

  5. #5

    16.16 integer fixed-point line drawer :)

    Quote Originally Posted by 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.
    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:

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

    Code:
        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:

    Code:
    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:

    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

  6. #6

    16.16 integer fixed-point line drawer :)

    Quote Originally Posted by paul_nicholls
    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):
    Code:
     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.

  7. #7

    16.16 integer fixed-point line drawer :)

    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

  8. #8

    16.16 integer fixed-point line drawer :)

    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.

  9. #9

    16.16 integer fixed-point line drawer :)

    Quote Originally Posted by Lifepower
    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

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •