M EQU Byte Ptr 0[BX] TITLE 'COHEN-SUTHERLAND CLIPPING ALGORITHM' DGROUP GROUP DATA ; **************************************************************************** ; * * ; * CLIPIT : Clip the endpoint of a line to the current Plot strip edge * ; * * ; **************************************************************************** ; * ; Revision : Jan. 11, 1983 File "CLIPIT.A86" * ; * ;***** MODE NOTES : ********************************************************* ; * ; 1) SET LINE ENDPOINT POSITION FLAG FOR SWAPPING LINE DIRECTION * ; ROUTINE, ABOVE : 0 = POINTS INSIDE OR BELOW PLOT STRIP * ; 1 = Y2 IS ABOVE, -1= Y1 IS ABOVE STRIP * ; * ;***** MODE NOTES : ********************************************************* ; ; ; * ; Clipit (x1,y1,x2,y2,rejected,topy,boty) * ; * ; Function : * ; * ; Clip the endpoints of a line to the current Plot Strip window * ; * ; Input : * ; * ; TOPY, BOTY : Y Coord. of the Top and Bottom edges of current Strip * ; X1,Y1,X2,Y2 : The endpoints of the line to be clipped * ; * ; Output : * ; * ; X1,Y1,X2,Y2 : The new endpoints trimmed to the window * ; ZERO STATUS : Flag indicating that the Line lies entirely * ; outside of the plot strip window (REJECTED) * ; * ; Process : * ; * ; FILTER (y1,flag1) ;Determine the position of the first end point * ; FILTER (y2,flag2) ;and the second point relative to the edges * ; * ; REJECT (flag1,flag2) ;Test to see if the line can be trivially * ; rejected * ; if not rejected * ; ACCEPT (flag1,flag2) ;Test to see if the line can be trivially * ; accepted * ; if not accepted * ; if (flag1 not 0) ;Test to see if the first point needs to be * ; TRIM(x1,y1) ;Trimmed * ; if (flag2 not 0) ;Trim the second endpoint if needed * ; TRIM(x2,y2) * ; * ; FILTER returns * ; position flag bit 2 | 1 | * ; ------------ * ; point above 1 | 0 | * ; ------------ top y edge of strip * ; point inside 0 | 0 | * ; ------------ bottom y edge of strip * ; point below 0 | 1 | * ; * ;----------------------------------------------------------------------------* ; + ; CALL CLIPIT + ; X1,Y1,X2,Y2,TOPY,BOTY passed in meory + ; RET + ; new X1,Y1,X2,Y2 stored + ; zero = on, line clipped + ; = off,line rejected (lies outside window) + ; above : 0=both points inside/below, 1=y2 above, -1=y1 above + ;----------------------------------------------------------------------------+ PUBLIC CLIPIT, FILTER EXTRN ABSHL:near, SUBDH:near EXTRN MIDH:near, DIDH:near, MULFRA:near, DIVFRA:near dseg EXTRN X1:word, Y1:word, X2:word, Y2:word, TOPY:word, BOTY:word EXTRN DX1:word, DY:word, XMAX:word EXTRN FLG1:word, FLG2:word, ABOVE:byte DX1DY RS 02 ;Variables used to compute new x intersection DIFFY RS 02 ;diffy = y2 - y1 DFRAC RS 01 cseg CLIPIT: ; Initialize above flag MOV Byte Ptr ABOVE,0 ;----------------------------------------------------------------------------+ ; Filter y-coordinate of the first endpoint y1 against strip + ;----------------------------------------------------------------------------+ MOV BX,Word Ptr Y1 CALL FILTER ;Returns position flag flg1 ;Flg1 : 0 = boty < y1 < topy MOV Byte Ptr FLG1,CH ; >0 = y1 above or below strip ; Filter second endpoint MOV BX,Word Ptr Y2 CALL FILTER ;flg2 : 0 = boty < y2 < topy ; >0 = y2 above or below strip MOV Byte Ptr FLG2,CH ;----------------------------------------------------------------------------+ ; Test : line lies entirely outside strip & can be trivially rejected ? ;----------------------------------------------------------------------------+ MOV AL,Byte Ptr FLG1 ;reject line if (fg1 .and. flg2) NOT= 0 AND AL,CH ; = flg2, = flg1 ; TRIVIALLY REJECT LINE JZ L@1 RET ;Zero flag off indicating line rejected L@1: ;----------------------------------------------------------------------------+ ; Test : line lies entirely inside strip & can be trivially accepted ? ;----------------------------------------------------------------------------+ MOV AL,Byte Ptr FLG1 ;accept line if (flg1 .or. flg2) = 0 OR AL,CH ; = flg2, = flg1 ; TRIVIALLY ACCEPT LINE JNZ L@2 RET ;Zero flag set indicating line accepted L@2: ;----------------------------------------------------------------------------+ ; Line can not be trivially accepted or rejected + ; CLIP line to the new intersection point + ;----------------------------------------------------------------------------+ MOV BX,Word Ptr X2 ;DX1 = x2 - x1 SUB BX,Word ptr X1 MOV Word Ptr DX1,BX MOV BX,Word Ptr Y2 ;DY = y2 - y1 SUB BX,Word Ptr Y1 MOV Word Ptr DY,BX ;----------------------------------------------------------------------------+ ; If point 2 is outside strip (flg2 NOT= 0), Trim x2,y2 to edge + ;----------------------------------------------------------------------------+ MOV AL,Byte Ptr FLG2 ;Test flg2 = 0 ? OR AL,AL JZ CLIJ01 ; TRIM X2,Y2 TO strip edge (toy, or boy) MOV CH,AL RCR AL,1 ;Y2 Above Plot Strip indicator in Bit 1 MOV Byte Ptr ABOVE,AL ;Set above flag for Y2 MOV AL,CH MOV DX,Word Ptr Y2 MOV BX,Word Ptr X2 CALL TRIM ;Replace new y coordinate & MOV Word Ptr X2,BX ;Compute new x coordinate MOV Word Ptr Y2,DX ;----------------------------------------------------------------------------+ ; If point x1,y1 is outside strip (flg1 NOT= 0), trim it to the edge + ;----------------------------------------------------------------------------+ CLIJ01: MOV AL,Byte Ptr FLG1 ;Test position flag = 0 ? OR AL,AL JZ CLIPED ;No trimming needed ; Update the Above Flag for Y1 MOV CH,AL ROR AL,1 ;Above Plot Strip flag in Bit 1 JB CLIJ02 MOV AL,0FFH ;Y1 is Above Plot Strip ;set Above = -1, if Y1 is above, then Y2 JMPS CLIJ03 ;must not be above, only one endpoint ;should be above the Plot Strip, never both CLIJ02: ;Y1 is Below Plot Strip, set ABOVE = 1 MOV AL,01H CLIJ03: MOV Byte Ptr ABOVE,AL MOV AL,CH ;Restore FLag ; Trim the point to strip edge MOV BX,Word Ptr Y1 XCHG BX,DX MOV BX,Word Ptr X1 CALL TRIM ;Compute new x coordinate & MOV Word Ptr X1,BX ;Replace new y coordinate XCHG BX,DX MOV Word Ptr Y1,BX CLIPED: XOR AL,AL ;Set zero flag to indicate line accepted RET ; **************************************************************************** ; * FILTER : Determine whether Y lies above, inside or below the * ; * current Plot Strip edges (toy, boy) * ; **************************************************************************** ; * ; Filter (y, topy, boty, flag) * ; * ; Input : y = the y-coordinate of point been tested * ; topy = the y-coordinate of top edge * ; boty = the y-coordinate of bottom edge * ; * ; Output : flag = indicate the relative position of y * ; * ; Process : * ; flag (bit 2) = sign bit of (topy - y) * ; flag (bit 1) = sign bit of (y - boty) * ; * ; * ; FILTER returns * ; position flag bit 2 1 * ; * ; point above 1 | 0 | * ; ------------ top y edge of strip * ; point inside 0 | 0 | * ; ------------ bottom y edge of strip * ; point below 0 | 1 | * ; * ;***************************************************************************** ; CALL FILTER ; = Y ; TOPY, BOTY passed in memory ; RET ; = FLAG FILTER: ; Test Y against top edge TOPY MOV CH,0 ;Initialize flag = 0 (inside) MOV DX,Word Ptr TOPY ; = y CMP BX,DX ;Carry set = topy < y JNA FILJ01 ;Carry off = topy > y ; Set flag to indicate y above top edge INC CH INC CH ;Set bit 2 RET ; Test y against bottom edge : boty FILJ01: ; = y MOV DX,Word Ptr BOTY ; = boty CMP BX,DX ;Carry set = y < boty JNAE L@3 RET ;Carry off = y > boty : point inside strip L@3: ; Set flag to indicate y below bottom edge INC CH ;Set bit 1 RET EJECT ; **************************************************************************** ; * TRIM : Trim endpoint of line to the edge of strip * ; **************************************************************************** ; * ; Trim (flag, x, y, topy, boty) * ; * ; Input : * ; flag : 2 = point above, 0 = point inside, 1 = point below * ; x, y : coordinate of point * ; topy : top edge of strip * ; boty : bottom edge of strip * ; * ; Outpyt : * ; x, y : new x,y coordinate trimmed to inside the strip * ; * ; Process : * ; if (flag = above) * ; newy = topy + 1 * ; else * ; newy = boty * ; compute new x intersection * ; DX1dy = (x2-x1) / (y2-y1) * ; newx = x + DX1dy * (newy - oldy) * ; * ;----------------------------------------------------------------------------* ; CALL TRIM ; = OLDX1 ; = OLDY ; = FLAG ; TOPY, BOTY passed in memory ; RET ; = NEWX ; = NEWY TRIM: MOV CX,BX ;Put olDX1 in ; Point above strip ? ROR AL,1 ;bit 1 set : point below strip ; Set new y to top edge of strip MOV BX,Word Ptr TOPY INC BX JNB TRIJ01 ; Else set new y to bottom edge of strip MOV BX,Word Ptr BOTY ; Compute the new x intersection at new y ; newx = olDX1 + DX1dy * (newy - oldy) TRIJ01: LAHF ;Save flag XCHG AL,AH PUSH AX XCHG AL,AH PUSH CX ;Save olDX1 PUSH BX ;save newy ; = new y ; = old y SUB BX,DX ; = newy - oldy MOV Word Ptr DIFFY,BX ;Save diffy ;---------------------------------------------------------------------------+ ; Get newx using integer arithmetics AND handles overflow correctly + ; DX1 = (x2-x1), dy = (y2-y1), diffy = (newy - oldy) + ; Q1 = Quotient (DX1/dy) + ; R1 = Remainder (DX1/dy) + ; FRAC = Fraction (r1/dy) + ; QX1 = q1 * diffy + ; RX1 = frac * diffy + ; NEWX = olDX1 + (qx1 + rx1) + ;---------------------------------------------------------------------------+ MOV DX,Word Ptr DX1 MOV BX,Word Ptr DY ;* ;* Save sign of integer part (Q1) : sgn(Q1) = sgn(DX1) xor sgn(DY) ;* MOV AL,BH XOR AL,DH LAHF ;Save sign of Integer part XCHG AL,AH PUSH AX XCHG AL,AH CALL DIDH ; = Q1, = R1 PUSH BX ;Save Q1 MOV BX,0 MOV AL,CH OR AL,CL ;R1 = 0 ? JNZ TRIJ07 PUSH BX ;Save Integer Fraction value on stack JMPS TRIJ03 ;Fraction part = 0 ; Get Fraction Part TRIJ07: MOV BX,CX MOV CX,Word Ptr DY CALL DIVFRA ;Returns FRAC in PUSH DX ;Save Integer Fraction value on stack MOV BX,Word Ptr DIFFY ;Get diffy CALL MULFRA ; = RX1 : FRAC * DIFFY TRIJ03: POP CX ;Get Integer fraction from stack POP DX ;Get Q1 MOV AL,DH OR AL,DL ;Is DX1/dy < 0.2 ? MOV AL,034H JNZ TRIJ08 CMP AL,CH JS TRIJ08 XOR AL,AL TRIJ08: MOV Byte Ptr DFRAC,AL ;dfrac = 0, if DX1/dy < 0.2 ;dfrac = 34h, if DX1/dy > 0.2 POP AX ;Get sign flag of Q1 XCHG AL,AH SAHF PUSH BX ;Put RX1 on stack MOV BX,Word Ptr DIFFY MOV AL,BH ;Update Sign flag of QX1 ROL AL,1 JNS TRIJ06 CMC ;If Q1 < 0, sign(QX1) = Negate sign(DIFFY) TRIJ06: LAHF ;Stack it XCHG AL,AH PUSH AX XCHG AL,AH CALL MIDH ;----------------------------------------------------------------------------+ ;* Integer and Fraction calculations are each done independant of + ;* their sign parts + ;----------------------------------------------------------------------------+ CALL ABSHL ;Use Unsigned Integer Part XCHG BX,DX POP BX ;Get RX1 from stack MOV BP,SP ; = QX1, = RX1 XCHG BX,[BP] ADD BX,DX ; = QX1 + RX1 POP AX ;Check the sign bit of integer part XCHG AL,AH SAHF JNB L@4 NEG BX ;Negate if sign(QX1) = minus L@4: POP CX ;Unstack new y POP DX ;Unstack old x ADD BX,DX ; = newx = olDX1 + QX1 + RX1 POP AX ;Check new y flag XCHG AL,AH SAHF XCHG BX,DX ;Put newx in JB TRIJ10 ; If newy is topy, adjust newy and newx to within plot strip ; because topy + 1 is used to compute newx DEC CX ;Readjust newy to equal topy ; Check sign(DX1/dy) to adjust newx by 1, optimize new x, y to ; eliminate zigzaging of rasterization as a result of clipping to ; Plot Strip edge MOV AL,Byte Ptr DFRAC OR AL,AL JZ TRIJ10 ;If DX1/dy < 0.2, new x not changed MOV BX,Word Ptr DX1 MOV AL,BH OR AL,BL JZ TRIJ10 ;If DX1 = 0, newx not changed MOV AL,BH MOV BX,Word Ptr DY ;Check sign(DX1/dy) XOR AL,BH JS TRIJ09 DEC DX ;If sign > 0, newx = newx - 1 JMPS TRIJ10 ;Return TRIJ09: INC DX ;If sign < 0, newx = newx + 1 ; Clip newx to within 0 and XMAX TRIJ10: XOR AL,AL OR AL,DH JNS TRIJ11 MOV DX,0 ;If newx < 0, then newx = 0 TRIJ11: MOV BX,Word Ptr XMAX CMP DX,BX JAE TRIJ99 ;If newx >= XMAX, then newx = XMAX XCHG BX,DX ;newx < XMAX, = newx TRIJ99: MOV DX,CX ; = new y RET END