Fastest Line clipping

[Biterider]

Hi
When I was halfway through coding the Liang-Barsky algorithm in asm, I came across this paper https://arxiv.org/pdf/1908.01350.pdf
It claims that it is faster than any other algo. Before I leave my previous efforts and get into this code, I want to ask if anyone has coded or researched anything in this area?

Biterider

[caballero]

I think so. Line clipping using Cohen-Sutherland algo

http://abreojosensamblador.epizy.com/?Tarea=5&SubTarea=2&Lang=1#Lineas

[daydreamer]

seem HSE has done some research on line clipping in game forum
maybe gpu hardware is fastest approach,you can also use gpu for a list of lines,pixels ,not only polygon vertex data?
anyway isnt timing different algos,this is the right place

[Biterider]

Hi Caballero
Cohen-Sutherland is the first match when looking for line clipping. Unfortunately, it is also the slowest in the benchmark. The Liang-Barsky algorithm performs better because it discards unwanted lines instead of calculating unnecessary intersections.
Other algos behave similarly. See International Journal of Computer Graphics & Animation (IJCGA) Vol.9, No.4, July 2019, page 12.
That is why I was surprised to find something faster.

Biterider

[caballero]

I think I did it according to the pseudocode of the paper

Code: [Select]

// x1 , y1 , x2 , y2 , xmin , ymax , xmax , ymin //
i f not ( x1<xmin and x2<xmin ) and not ( x1>xmax and x2>xmax ) th en
  i f not ( y1<ymin and y2<ymin ) and not ( y1>ymax and y2>ymax ) th en
    x [ 1 ]= x1
    y [ 1 ]= y1
    x [ 2 ]= x2
    y [ 2 ]= y2
    i =1
    r e p e a t
      i f x [ i ] < xmin th en
        x [ i ] = xmin
        y [ i ] = ( ( y2-y1 ) / ( x2-x1 ) ) * ( xmin-x1)+y1
        e l s e i f x [ i ] > xmax th en
        x [ i ] = xmax
        y [ i ] = ( ( y2-y1 ) / ( x2-x1 ) ) * ( xmax-x1)+y1
      end i f
      i f y [ i ] < ymin th en
        y [ i ] = ymin
        x [ i ] = ( ( x2-x1 ) / ( y2-y1 ) ) * ( ymin-y1)+x1
        e l s e i f y [ i ] > ymax th en
        y [ i ] = ymax
        x [ i ] = ( ( x2-x1 ) / ( y2-y1 ) ) * ( ymax-y1)+x1
      end i f
      i = i + 1
    u n t i l i >2
    i f not ( x [1 ] < xmin and x [2 ] < xmin ) and not ( x [1 ] >xmax and x [2 ] >xmax ) th en
      drawL ine ( x [ 1 ] , y [ 1 ] , x [ 2 ] , y [ 2 ] )
    end i f
  end i f
end i f

But it appears something wrong in the middle of the paint. In the shot, the upper one is for the Cohen-Sutherland I had before, the bottom is for the new one.

I did it in a hurry, so something could be wrong. Now to bed 

[Biterider]

Hi Caballero
That was quick
Did you code it for floating point or integers?

For most of the circle the result is similar to that of the Cohen-Sutherland algo. Maybe something went wrong in the other 2 sections.

Since you have both algorithms on the same application, it would be interesting to know if you see an increase in performance. 

Biterider

[caballero]

> Did you code it for floating point or integers?
  As you say that, I realized where my fault was. It is an algo for integers, but the slope must be calculated as float, otherwise would give rounding errors as the previous code. Once it is fixed, the algo works as expected 

[Biterider]

Hi
I finally managed to find some time to code the algo using floating point. The reason for this is that in my case the data source are floats, so it is more effective to do the calculations in the native format. I wrote the code so that I can easily switch between REAL4 and REAL8 using the FPU.
The original algorithm loops to get both ends of a line. I unrolled it, which results in larger but faster code.
At the end of the day, it works just fine. 
What I can't tell is how it compares to other algos, but it's fast enough for my purposes.
This is the extract of the main loop to convert an array of float tuples.

Code: [Select]

    mov ebx, [xdi].dDataFrom
    add ebx, [xdi].dDataCount
    dec ebx

    .while (SDWORD ptr ebx > [xdi].dDataFrom)
      OCall xdi::ChartSeries.ItemAt, 0, ebx
      fld [xsi].ScaleX.fScaleMin
      fld [xsi].ScaleX.fScaleMax
      fld CHT_FLOAT ptr [xax - 2*sizeof(CHT_FLOAT)]     ;xa, xmax, xmin
      fst fX0
      fcomi st(0), st(2)
      fld CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]     ;xb, xa, xmax, xmin
      fst fX1
      jae @F
      fcomi st(0), st(3)
      jb @NextLine4                                     ;=> fUnload 4
  @@:
      fcomip st(0), st(2)                               ;xa, xmax, xmin
      jbe @F
      fcomi st(0), st(1)                                ;xa, xmax, xmin
      ja @NextLine3                                     ;=> fUnload 3
  @@:
      fUnload 3

      fld [xsi].ScaleY.fScaleMin
      fld [xsi].ScaleY.fScaleMax
      fld CHT_FLOAT ptr [xax - 1*sizeof(CHT_FLOAT)]     ;ya, ymax, ymin
      fst fY0
      fcomi st(0), st(2)
      fld CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]     ;yb, ya, ymax, ymin
      fst fY1
      jae @F
      fcomi st(0), st(3)
      jb @NextLine4                                     ;=> fUnload 4
  @@:
      fcomip st(0), st(2)                               ;ya, ymax, ymin
      jbe @F
      fcomi st(0), st(1)                                ;ya, ymax, ymin
      ja @NextLine3                                     ;=> fUnload 3
  @@:
      fUnload 1                                         ;ymax, ymin
      ;If we are here, we excluded all obvious lines outside the clipping rectangle

      fld fX1
      fsub fX0
      fstp fXdelta
      fld fY1
      fsub fY0
      fstp fYdelta

      fld fY0                                           ;fY0, ymax, ymin
      fcomi st(0), st(1)
      jbe @F
      ;Calc intersection on top edge
      fUnload
      fst fY0                                           ;ymax, ymin
      fsub CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]    ;ymax - fYb, ymin
      fmul fXdelta
      fdiv fYdelta
      fadd CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]    ;(fXdelta/fYdelta)(ymax - fYb) + fXb, ymin
      fstp fX0                                          ;ymin
      fUnload
      jmp @1C
  @@:
      fcomi st(0), st(2)                                ;fY0, ymax, ymin
      jae @1B                                           
      ;Calc intersection on bottom edge
      fUnload 2                                         ;ymin
      fst fY0
      fsub CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]    ;ymin - fYb
      fmul fXdelta
      fdiv fYdelta
      fadd CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]    ;(fXdelta/fYdelta)(ymin - fYb) + fXb
      fstp fX0
      jmp @1C
  @1B:
      fUnload 3
  @1C:
      fld [xsi].ScaleX.fScaleMin
      fld [xsi].ScaleX.fScaleMax
      fld fX0                                           ;fX0, xmax, xmin
      fcomi st(0), st(1)
      jbe @F
      fUnload                                           ;xmax, xmin
      ;Calc intersection on right edge
      fst fX0
      fsub CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]
      fmul fYdelta
      fdiv fXdelta
      fadd CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]
      fstp fY0
      jmp @2A                                           ;xmin
  @@:
      fcomi st(0), st(2)                                ;fX0, xmax, xmin
      fUnload 2                                         ;xmin
      jae @2A
      ;Calc intersection on left edge
      fst fX0
      fsub CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]
      fmul fYdelta
      fdiv fXdelta
      fadd CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]
      fst fY0
  @2A:
      fUnload

      fld [xsi].ScaleY.fScaleMin
      fld [xsi].ScaleY.fScaleMax
      fld fY1                                           ;fY1, ymax, ymin
      fcomi st(0), st(1)
      jbe @F
      ;Calc intersection on top edge
      fUnload
      fst fY1                                           ;ymax, ymin
      fsub CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]    ;ymax - fYb, ymin
      fmul fXdelta
      fdiv fYdelta
      fadd CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]    ;(fXdelta/fYdelta)(ymax - fYb) + fXb, ymin
      fstp fX1                                          ;ymin
      fUnload
      jmp @2C
  @@:
      fcomi st(0), st(2)                                ;fY1, ymax, ymin
      jae @2B                                           
      ;Calc intersection on bottom edge
      fUnload 2                                         ;ymin
      fst fY1
      fsub CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]    ;ymin - fYb
      fmul fXdelta
      fdiv fYdelta
      fadd CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]    ;(fXdelta/fYdelta)(ymin - fYb) + fXb
      fstp fX1
      jmp @2C
  @2B:
      fUnload 3
  @2C:
      fld [xsi].ScaleX.fScaleMin
      fld [xsi].ScaleX.fScaleMax
      fld fX1                                           ;fX1, xmax, xmin
      fcomi st(0), st(1)
      jbe @F
      fUnload                                           ;xmax, xmin
      ;Calc intersection on right edge
      fst fX1
      fsub CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]
      fmul fYdelta
      fdiv fXdelta
      fadd CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]
      fstp fY1
      jmp @3                                            ;xmin
  @@:
      fcomi st(0), st(2)
      fUnload 2                                         ;xmin
      jae @3
      ;Calc intersection on left edge
      fst fX1
      fsub CHT_FLOAT ptr [xax - 0*sizeof(CHT_FLOAT)]
      fmul fYdelta
      fdiv fXdelta
      fadd CHT_FLOAT ptr [xax + 1*sizeof(CHT_FLOAT)]
      fst fX1
  @3:
      fUnload
      ;If we are here, we will check our results

      fld [xsi].ScaleX.fScaleMin
      fld [xsi].ScaleX.fScaleMax
      fld fX0                                           ;fX0, xmax, xmin
      fcomi st(0), st(2)
      fld fX1                                           ;fX1, fX0, xmax, xmin
      jae @F
      fcomi st(0), st(3)
      jb @NextLine4                                     ;=> fUnload 4
  @@:
      fcomip st(0), st(2)                               ;fX0, xmax, xmin
      jbe @F
      fcomi st(0), st(1)                                ;xa, xmax, xmin
      ja @NextLine3                                     ;=> fUnload 3
  @@:
      fUnload 3

      ;If we are here, we will draw finally our line
      fld fX0
      fsub [xsi].ScaleX.fScaleMin
      fmul [xsi].ScaleX.fScaleFactor
      fistp p0.x
      mov edx, [xsi].PlotRect.left
      add p0.x, edx
      fld fY0
      fsub [xsi].ScaleY.fScaleMin
      fmul [xsi].ScaleY.fScaleFactor
      fistp p0.y
      neg p0.y
      mov edx, [xsi].PlotRect.bottom
      add p0.y, edx
      invoke MoveToEx, hDC, p0.x, p0.y, NULL
     
      fld fX1
      fsub [xsi].ScaleX.fScaleMin
      fmul [xsi].ScaleX.fScaleFactor
      fistp p1.x
      mov edx, [xsi].PlotRect.left
      add p1.x, edx
      fld fY1
      fsub [xsi].ScaleY.fScaleMin
      fmul [xsi].ScaleY.fScaleFactor
      fistp p1.y
      neg p1.y
      mov edx, [xsi].PlotRect.bottom
      add p1.y, edx
      invoke LineTo, hDC, p1.x, p1.y

      jmp @F
@NextLine4:
      fUnload
@NextLine3:
      fUnload 3
@@:
      dec ebx
    .endw
Biterider