181 lines
7.1 KiB
Plaintext
Executable File
181 lines
7.1 KiB
Plaintext
Executable File
.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
|