.INCLUDE GRAFTYPES.TEXT ;------------------------------------------------------------------ ; ; --> SORTPOINTS.TEXT ; ; Routines to sort inversion points and cull duplicates. ; .PROC SortPoints ;------------------------------------------------------------- ; ; PROCEDURE SortPoints(ptBuf: PointsPtr; ptCount: INTEGER); ; ; PERFORMS A NON-RECURSIVE QUICKSORT ON AN ARRAY OF POINTS ; TO PUT THEM IN INCREASING VERT.HORIZ ORDER. ; ; RE-WROTE 5 SEPT 83 TO CUT DOWN WORST CASE STACK USAGE ; ; See Algorithms + Data Structures = Programs, p.80 ; ; A6 OFFSETS OF PARAMETERS AFTER LINK: ; PARAMSIZE .EQU 6 PTBUF .EQU PARAMSIZE+8-4 ;LONG PTCOUNT .EQU PTBUF-2 ;WORD LINK A6,#0 ;NO LOCAL VARIABLES MOVEM.L D3-D4/A2-A4,-(SP) ;SAVE REGS MOVE.L PTBUF(A6),A3 ;LEFTPTR:=START OF PT ARRAY MOVE A3,D3 AND #3,D3 ;SET UP LOBITS FOR SORT CLR.L D0 MOVE PTCOUNT(A6),D0 ;GET PTCOUNT BLE.S GOHOME ;DO NOTHING IF NO POINTS LSL.L #2,D0 ;QUAD PTCOUNT FOR BYTES MOVE.L A3,A4 ADD.L D0,A4 ;ADD TO DSTSTART SUB #4,A4 ;RIGHTPTR:=DSTEND-4 MOVE.L SP,D4 ;REMEMBER STACK MARKER MOVEM.L A3/A4,-(SP) ;PUSH LEFTPTR AND RIGHTPTR POPNXT MOVEM.L (SP)+,A3/A4 ;POP LEFTPTR AND RIGHTPTR SPLIT MOVE.L A3,A1 ;IPTR := LEFTPTR MOVE.L A4,A2 ;JPTR := RIGHTPTR ; ; CALC MIDPTR AND MIDPT ; MOVE.L A3,D0 ;ADD LEFTPTR ADD.L A4,D0 ;AND RIGHTPTR ROXR.L #1,D0 ;THEN DIVIDE BY 2 FOR MIDPTR AND #$FFFC,D0 ;TRUNC TO MULTIPLE OF 4 BYTES OR D3,D0 ;OR IN LOBITS FOR POINT BOUNDARY MOVE.L D0,A0 ;GET MIDPTR INTO A-REG MOVE H(A0),D1 ;GET MIDPT.H MOVE V(A0),D2 ;AND MIDPT.V SCAN ; ; WHILE IPTR^ < MIDPT DO BUMP IPTR TO RIGHT ; BRA.S TWO ;GO TO LOOP START ONE ADD #4,A1 ;BUMP IPTR TO RIGHT TWO CMP V(A1),D2 ;IS MIDPT.V > IPTR^.V ? BGT ONE ;YES, BUMP SOME MORE BLT.S THREE ;BR IF DONE WITH IPTR. CMP H(A1),D1 ;IF SAME VERT, LOOK AT HORIZ BGT ONE ;KEEP BUMPING IF MIDPT.H > IPTR^.H THREE ; ; WHILE JPTR^ > MIDPT DO BUMP JPTR TO LEFT ; BRA.S FIVE ;GO TO LOOP START FOUR SUB #4,A2 ;BUMP JPTR TO LEFT FIVE CMP V(A2),D2 ;IS MIDPT.V < JPTR^.V ? BLT FOUR ;YES, BUMP SOME MORE BGT.S SIX ;BR IF DONE BUMPING JPTR CMP H(A2),D1 ;IF SAME VERT, LOOK AT HORIZ BLT FOUR ;KEEP BUMPING IF MIDPT.H < JPTR^.H SIX ; ; if IPtr <= JPtr then swap IPtr^ and JPtr^, and bump both pointers ; CMP.L A2,A1 ;IS IPTR > JPTR ? BGT.S NOSWAP ;YES, ALL DONE MOVE.L (A1),D0 MOVE.L (A2),(A1) MOVE.L D0,(A2) ;SWAP POINTS ADD #4,A1 ;BUMP IPTR TO RIGHT SUB #4,A2 ;BUMP JPTR TO LEFT ; ; repeat until this partitioning is complete, IPtr > JPtr ; NOSWAP CMPA.L A2,A1 ;IS IPTR > JPTR ? BLS SCAN ;NO, LOOP AGAIN ; ; IF i < right then stack request to sort right partition ; CMPA.L A4,A1 ;IS IPTR < RIGHTPTR ? BHS.S RIGHTOK ;YES, CONTINUE MOVEM.L A1/A4,-(SP) ;NO, PUSH IPTR,RIGHTPTR RIGHTOK MOVE.L A2,A4 ;RIGHTPTR := JPTR CMPA.L A4,A3 ;IS LEFTPTR >= RIGHTPTR ? BLO SPLIT ;NO, PARTITION AGAIN CMPA.L D4,SP ;IS STACK EMPTY YET ? BNE POPNXT ;NO, LOOP FOR MORE GOHOME MOVEM.L (SP)+,D3-D4/A2-A4 ;RESTORE REGS UNLINK PARAMSIZE,'SORTPOIN' .PROC CullPoints,2 ;------------------------------------------------------------- ; ; PROCEDURE CullPoints(ptBuf: PointsPtr; VAR ptCount: INTEGER); ; ; CANCEL ANY DUPLICATE PAIRS OF POINTS IN AN ARRAY OF POINTS. ; ; ; A6 OFFSETS OF PARAMETERS AFTER LINK: ; PARAMSIZE .EQU 8 PTBUF .EQU PARAMSIZE+8-4 ;LONG PTCOUNT .EQU PTBUF-4 ;LONG, VAR LINK A6,#0 ;NO LOCAL VARIABLES MOVEM.L D0-D7/A1-A5,-(SP) ;SAVE REGS MOVE.L PTCOUNT(A6),A0 ;GET VAR ADDR OF PTCOUNT MOVE (A0),D0 ;GET PTCOUNT BLE GOHOME ;DO NOTHING IF NO POINTS MOVE.L PTBUF(A6),A1 ;SRCPTR:=START PTR MOVE.L A1,A3 ;COPY START EXT.L D0 ;CLEAR HI WORD LSL.L #2,D0 ;QUAD PTCOUNT FOR BYTES ADD.L D0,A3 ;ADD TO START SUB #4,A3 ;LAST POINT IS AT END-4 MOVE.L A1,D5 ;SAVE START FOR LATER MOVE.L A1,A2 ;DSTPTR:=START BRA.S WHILE1 ;GO TO LOOP START DELETE ADD #4,A1 ;SKIP OVER BOTH SRC POINTS BRA.S WHILE1 ;GO TO LOOP START MORE1 MOVE.L (A1)+,D0 ;GET CURRENT SRC POINT CMP.L (A1),D0 ;IS IT SAME AS NEXT ? BEQ DELETE ;YES, DELETE BOTH MOVE.L D0,(A2)+ ;NO, COPY TO DST WHILE1 CMP.L A3,A1 ;IS SRCPTR < LASTPTR ? BLT.S MORE1 ;YES, GO FOR MORE BGT.S DONE MOVE.L (A1)+,(A2)+ ;FINISH UP LAST POINT DONE MOVE.L A2,D0 ;GET DST PTR SUB.L D5,D0 ;SUBTRACT START PTR LSR #2,D0 ;DIV BY 4 FOR PTCOUNT MOVE.L PTCOUNT(A6),A0 ;GET VAR ADDR MOVE D0,(A0) ;UPDATE PTCOUNT TO REFLECT DELETIONS GOHOME MOVEM.L (SP)+,D0-D7/A1-A5 ;RESTORE REGS UNLINK PARAMSIZE,'CULLPOIN' .END