## News:

Message to All Guests

## Fastest Line clipping

Started by Biterider, August 30, 2021, 01:35:11 AM

#### 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

#### avcaballero

I think so. Line clipping using Cohen-Sutherland algo

#### 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

my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

#### 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

#### avcaballero

I think I did it according to the pseudocode of the paper
`// 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 fend 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

#### avcaballero

> 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.

`    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