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 (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
I think so. Line clipping using Cohen-Sutherland algo
http://abreojosensamblador.epizy.com/?Tarea=5&SubTarea=2&Lang=1#Lineas
seem HSE has done some research on line clipping in game forum :thumbsup:
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 :greenclp:
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 (https://arxiv.org/pdf/1908.01350.pdf).
That is why I was surprised to find something faster.
Biterider
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 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 :azn:
Hi Caballero
That was quick :biggrin:
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. :cool:
Biterider
> Did you code it for floating point or integers?
:biggrin: 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 :thumbsup:
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. :cool:
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