Cohen-Sutherland Clipping

[p. specht]

COHEN/SUTHERLAND-LINECLIPPING
==========================
So, hier wieder ein Gustostückchen, was einem alles passieren kann: Ich hatte das C++ Beispiel aus einem Wikipedia-Artikel über Cohen/Sutherland Clipping - Quatsch, natürlich dieses hier, unter Verwendung von Longinteger-Variablen in XProfan11 übersetzt. Das sah (nach erstem Debugging) schon recht gut aus - blieb aber nach durchschnittlich 11 Sekunden unerklärlicherweise stecken. Und langsam wurden bei der Fehlersuche die Haare grau.

Hinweise auf die Ursache ergaben sich dann aus der folgenden Beobachtung: Die Endpunkte der Linien werden im Hauptteil jeweils via Zufallsgenerator definiert. Liegen diese Punkte aber genau über- oder nebeneinander (oder lediglich 1 pixel Unterschied), wurde in der Innenschleife die Abbruchbedingung ("Geclippte Linie liegt nun komplett im innern des Sichtfenster-Rechtecks") nie mehr erreicht.

Nun zur endgültigen Klärung: C++ liefert bei der Division von zwei Integervariablen automatisch einen Integer-Wert zurück. XProfan versucht bei Verwendung der herkömmlichen Division aber, genau zu sein und liefert einen Floatwert - die Ursache für das merkwürdige Verhalten. Nach Ersatz des / Operators durch die Funktion @div&(a&,b&) bzw. künftig durch das \ Integerdivisionszeichen funktioniert nun alles. Interessant wäre die Beschleunigung mittels Inline-Assemblercode. Freiwillige?

Gruss

' Cohen-Sutherland Clipping Demo
' Keine Haftung, Verwendung auf eigene Gefahr!
' P. Specht 2011-01 für Paule´s PC Forum
' Anmerkung: Es gibt inzwischen bereits viel schnellere Algorithmen!

Def %CLIPLEFT  1  '  Binär   0001
Def %CLIPRIGHT 2  '          0010
Def %CLIPLOWER 4  '          0100
Def %CLIPUPPER 8  '          1000
Def %TRUE 1
Def %FALSE 0

Proc ClipLine
var K1%=0
var K2%=0 
declare dx&,dy&
dx&=x2&-x1&
dy&=y2&-y1&

y1test
y2test

'  Schleife nach Cohen/Sutherland, die maximal 2 mal durchlaufen wird
 while K1% OR K2%
 
   rtn% = %TRUE
   if K1% & K2% : rtn% = %FALSE : BREAK : endif   
   
   if K1%
   
     if K1% & %CLIPLEFT
       y1& = y1& + (XMin&-x1&)*dy&\dx&
       x1& = XMin&
     elseif K1% & %CLIPRIGHT
       y1& = y1& + (XMax&-x1&)*dy&\dx&
       x1& = XMax&
     endif
     if K1% & %CLIPLOWER
       x1& = x1& + (YMin&-y1&)*dx&\dy&
       y1& = YMin&
     elseif K1% & %CLIPUPPER
       x1& = x1& + (YMax&-y1&)*dx&\dy&
       y1& = YMax&
     endif
     
     K1% = 0
     y1test
   endif

   if K1% & K2% : rtn% = %FALSE : BREAK : endif

   if K2%
     if K2% & %CLIPLEFT
       y2& = y2& + (XMin&-x2&)*dy&\dx&
       x2& = XMin&
     elseif K2% & %CLIPRIGHT
       y2& = y2& + (XMax&-x2&)*dy&\dx&
       x2& = XMax&
     endif
     if K2% & %CLIPLOWER
       x2& = x2& + (YMin&-y2&)*dx&\dy&
       y2& = YMin&
     elseif K2% & %CLIPUPPER
       x2& = x2& + (YMax&-y2&)*dx&\dy&
       y2& = YMax&
     endif
     K2% = 0
     y2test
    
   endif
   
 EndWhile
return rtn%
EndProc

proc y1test
if y1&<YMin&
    K1% = %CLIPLOWER
elseif y1& > YMax&
    K1% = %CLIPUPPER
endif
if x1& < XMin&
    K1% = K1% | %CLIPLEFT
elseif x1&>XMax&
    K1% = K1% | %CLIPRIGHT
endif
endproc


proc y2test
if y2&<YMin&
  K2% = %CLIPLOWER
elseif y2&>YMax&
  K2% = %CLIPUPPER
endif
if x2&<XMin&
  K2% = K2% | %CLIPLEFT
elseif (x2&>XMax&)
  K2% = K2% | %CLIPRIGHT
endif
endproc

'INIT
Declare XMax&,YMax&,XMin&,YMin&,rtn%
Declare x1&,y1&,x2&,y2&,colo&
RANDOMIZE
WindowTitle "Cohen/Sutherland Clipping Demo"
WindowStyle  4 | 8 | 16

'MAIN
WHILE 1
XMin& = Rnd(300)
YMin& = Rnd(200)
XMax& = XMin& + Rnd(500)
YMax& = YMin& + Rnd(250)
CLS
colo&=rgb(rnd(256),rnd(256),rnd(256))
UsePen 0,3,colo&
rectangle XMin&,YMin& - XMax&,YMax&

'print XMin&,YMin&,XMax&,YMax&
  WhileLoop 1000
  x1& = rnd(Width( %HWnd))
  y1& = rnd(Height(%Hwnd))
  x2& = rnd(Width( %HWnd))
  y2& = rnd(Height(%Hwnd))
  colo&=rgb(rnd(256),rnd(256),rnd(256))
    UsePen 3,1,colo&
    Line x1&,y1& - x2&,y2&
    if ClipLine()
      UsePen 0,3,colo&
      Line x1&,y1& - x2&,y2&
    endif
  EndWhile
ENDWHILE
END