.module Triangle

JustMovedY           = 0
FoundFirstValidY     = 1
FillFlags            = asm_Flag1

InitPlotFill
	ld hl,($A0E4) ; HIMEM
	ld de,($A0E2) ; Free memory after heap.
	or a
	sbc hl,de ; HL = amount of free space between top of heap and HIMEM
	ld de,768 ; Minimum amount of free RAM for triangle.
	or a
	sbc hl,de
	ret c
	
	ld hl,($A0E2)
	ld (Triangle.Edges),hl
	
	call SetPatternBuffer
	call PlotUpdateColours
	
	ld hl,(VisitedPoints+ 0) \ call Graphics.ScaleX.HL \ ld (Triangle.VertexA.X),hl
	ld hl,(VisitedPoints+ 2) \ call Graphics.ScaleY.HL \ call Graphics.FlipY16 \ ld (Triangle.VertexA.Y),hl
	ld hl,(VisitedPoints+ 4) \ call Graphics.ScaleX.HL \ ld (Triangle.VertexB.X),hl
	ld hl,(VisitedPoints+ 6) \ call Graphics.ScaleY.HL \ call Graphics.FlipY16 \ld (Triangle.VertexB.Y),hl
	ld hl,(VisitedPoints+ 8) \ call Graphics.ScaleX.HL \ ld (Triangle.VertexC.X),hl
	ld hl,(VisitedPoints+10) \ call Graphics.ScaleY.HL \ call Graphics.FlipY16 \ld (Triangle.VertexC.Y),hl
	or a
	ret

Fill

;-------------------------------------------------------------------------------
; Sort vertices from top-to-bottom.
;-------------------------------------------------------------------------------

	ld hl,(VertexA.Y)
	ld de,(VertexC.Y)
	or a
	sbc hl,de
	jp m,+
	ld (VertexA.Y),de
	add hl,de
	ld (VertexC.Y),hl
	ld hl,(VertexA.X)
	ld de,(VertexC.X)
	ld (VertexA.X),de
	ld (VertexC.X),hl
+	ld hl,(VertexA.Y)
	ld de,(VertexB.Y)
	or a
	sbc hl,de
	jp m,+
	ld (VertexA.Y),de
	add hl,de
	ld (VertexB.Y),hl
	ld hl,(VertexA.X)
	ld de,(VertexB.X)
	ld (VertexA.X),de
	ld (VertexB.X),hl
+	ld hl,(VertexB.Y)
	ld de,(VertexC.Y)
	or a
	sbc hl,de
	jp m,+
	ld (VertexB.Y),de
	add hl,de
	ld (VertexC.Y),hl
	ld hl,(VertexB.X)
	ld de,(VertexC.X)
	ld (VertexB.X),de
	ld (VertexC.X),hl
+

;-------------------------------------------------------------------------------
; A.Y <= B.Y <= C.Y
;-------------------------------------------------------------------------------

	; Quick cull check. If A.Y > MaxY...
	ld hl,(Graphics.Bounds+3)
	ld h,0
	ld de,(VertexA.Y)
	or a
	sbc hl,de
	scf
	ret m
	
	; ...or if MinY > C.Y...
	ld hl,(VertexC.Y)
	ld de,(Graphics.Bounds+2)
	ld d,0
	or a
	sbc hl,de
	scf
	ret m

	ld a,63
	ld (TopOfTriangle),a
	xor a
	ld (BottomOfTriangle),a

;-------------------------------------------------------------------------------
; Trace the three sides of the triangle.
;-------------------------------------------------------------------------------
	
	exx
	push hl
	push de
	push bc
	exx

	push iy
	ld iy,(TIOS.IY)

	ld hl,(Edges)
	ld de,128
	add hl,de
	ld (TraceEdgeOutputA),hl
	ld de,64
	add hl,de
	ld (TraceEdgeOutputB),hl
	
	ld hl,VertexA
	ld de,VertexC
	call TraceEdge

	ld hl,(Edges)
	ld (TraceEdgeOutputA),hl
	ld de,64
	add hl,de
	ld (TraceEdgeOutputB),hl
	
	ld hl,VertexA
	ld de,VertexB
	call TraceEdge

	ld hl,(Edges)
	inc h
	ld (TraceEdgeOutputA),hl
	ld de,64
	add hl,de
	ld (TraceEdgeOutputB),hl
	ld hl,VertexB
	ld de,VertexC
	call TraceEdge
	
	pop iy
	
	exx
	pop bc
	pop de
	pop hl
	exx
	
;-------------------------------------------------------------------------------
; Draw top half (A.Y <= y < B.Y).
;-------------------------------------------------------------------------------

Fill.AlreadyTraced
	
	; First half cannot be drawn if MinY > B.Y.
	ld hl,(VertexB.Y)
	ld de,(Graphics.Bounds+2)
	ld d,0
	or a
	sbc hl,de
	jp m,SkipTopHalf
	
;	or a
;	ld de,(TopOfTriangle)
;	sbc hl,de
;	ex de,hl
;	jp m,SkipTopHalf
	
	ld a,(TopOfTriangle)
	call ClipY8

	ld h,0
	ld e,l

	ld bc,(Edges)
	add hl,bc
	ld bc,128
	add hl,bc
	push hl
	pop ix
	
	ld hl,(VertexB.Y)
	call ClipY16
	
	; E = top, L = bottom.
	ld a,l
	sub e
	or a
	jr z,SkipTopHalf
	ld d,a
	; D = rows to fill.

	call FillScanlines
	
SkipTopHalf

;-------------------------------------------------------------------------------
; Draw bottom half (B.Y <= y <= C.Y).
;-------------------------------------------------------------------------------

	; Second half cannot be drawn if B.Y > MaxY.
	ld hl,(Graphics.Bounds+3)
	ld h,0
	ld de,(VertexB.Y)
	or a
	sbc hl,de
	jp m,SkipBottomHalf

;	or a
;	ld hl,(BottomOfTriangle)
;	sbc hl,de
;	jp m,SkipBottomHalf

CanDrawBottomHalf

	ex de,hl
	call ClipY16
	ld h,0
	
	ld e,l
	ld bc,(Edges)
	add hl,bc
	inc h
	push hl
	pop ix
	
	ld a,(BottomOfTriangle)
	call ClipY8

	; E = top, L = bottom.
	ld a,l
	sub e
	inc a
	ld d,a
	; D = rows to fill.

FillScanlines
-	ld b,(ix-128)
	ld c,(ix+0)
	ld a,b
	cp c
	jr c,+
	ld b,c
	ld c,a
+	
	
	; We have dealt with two of points, and b <= c.
	; Now try the other two points. If they're more extreme (<b or >c) use them instead.

	ld a,(ix-64)
	cp b
	jr nc,+
	ld b,a
+	cp c
	jr c,+
	ld c,a
+

	ld a,(ix+64)
	cp b
	jr nc,+
	ld b,a
+	cp c
	jr c,+
	ld c,a
+
	ld a,e	
	push hl
	push de
	call HLineFill
	pop de
	pop hl	
	inc ix
	inc e
	dec d
	jr nz,-
	or a
	ret

SkipBottomHalf
	; Well, we skipped drawing the bottom scanline last time.
	ld de,(Graphics.Bounds+3)
	ld d,1
	call FillScanlines
	or a	
	ret

;------------------------------------------------------------------------------- 
;@doc:routine
; 
; === Triangle.ClipY16 ===
;
;   Clamps a signed 16-bit Y coordinate to the viewport.
;
; INPUTS:
;   REGISTERS
;   * HL - Coordinate to clip.
;   MEMORY
;   * Graphics.Bounds - Graphics viewport boundaries.
;
; OUTPUTS:
;   REGISTERS
;   * L - Clipped coordinate.
;
; DESTROYED:
;   REGISTERS
;   * AF.
;
;@doc:end
;------------------------------------------------------------------------------- 
ClipY16
	ld a,h
	or a
	jr z,+
	ld l,63
	jp p,+
	ld l,0	
+	ld a,(Graphics.Bounds+2) ; MinY
	cp l
	jr c,+
	ld l,a
+	ld a,(Graphics.Bounds+3) ; MaxY
	cp l
	ret nc
	ld l,a
	ret

;------------------------------------------------------------------------------- 
;@doc:routine
; 
; === Triangle.ClipY16 ===
;
;   Clamps an unsigned 8-bit Y coordinate to the viewport.
;
; INPUTS:
;   REGISTERS
;   * A - Coordinate to clip.
;   MEMORY
;   * Graphics.Bounds - Graphics viewport boundaries.
;
; OUTPUTS:
;   REGISTERS
;   * L - Clipped coordinate.
;
; DESTROYED:
;   REGISTERS
;   * AF.
;
;@doc:end
;------------------------------------------------------------------------------- 
ClipY8
	ld l,a
+	ld a,(Graphics.Bounds+2) ; MinY
	cp l
	jr c,+
	ld l,a
+	ld a,(Graphics.Bounds+3) ; MaxY
	cp l
	ret nc
	ld l,a
	ret
	
;------------------------------------------------------------------------------- 
;@doc:routine
; 
; === Triangle.TraceEdge ===
;
;   Traces the edge of a triangle.
;
; INPUTS:
;   REGISTERS
;   * HL - Pointer to top point (16-bit).
;   * DE - Pointer to bottom point (16-bit).
;   MEMORY
;   * Graphics.Bounds - Graphics viewport boundaries.
;   * TraceEdgeOutputA - Pointer to 64 bytes for one side's edge output.
;   * TraceEdgeOutputB - Pointer to 64 bytes for one side's edge output.
;
; DESTROYED:
;   REGISTERS
;   * AF, BC, DE, HL, IX, BC', DE', HL'.
;
;@doc:end
;------------------------------------------------------------------------------- 
TraceEdge

	; Copy top/bottom gubbins.
	push de
	ld de,VertexTop
	ld bc,4
	ldir
	pop hl
	ld de,VertexBottom
	ld c,4
	ldir
	
	ld a,63
	ld (FirstValidY),hl
	ld a,0
	ld (LastValidY),hl

	res FoundFirstValidY,(iy+FillFlags)
	
	; Calculate initial variables.
	
	ld hl,(VertexBottom.X)
	ld de,(VertexTop.X)
	or a
	sbc hl,de
	ld (TraceDX),hl
	bit 7,h
	jr z,+
	dec hl
	ld a,h
	cpl
	ld h,a
	ld a,l
	cpl
	ld l,a
+	push hl
	
	ld hl,(VertexBottom.Y)
	ld de,(VertexTop.Y)
	or a
	sbc hl,de
	ld (TraceDY),hl
	bit 7,h
	jr z,+
	dec hl
	ld a,h
	cpl
	ld h,a
	ld a,l
	cpl
	ld l,a
+	
	pop de
	or a
	sbc hl,de
	jp nc,TraceEdgeDYOverDX

; ..................................
TraceEdgeDXOverDY ; |dy|>|dx|

	ld hl,(TraceDX)
	bit 7,h
	jp nz,TraceEdgeDXOverDYNegative

TraceEdgeDXOverDYPositive ; dx >= 0

	ld hl,(TraceDX)
	sra h
	rr l
	ld (TraceError),hl
	
	ld de,(TraceDY)
	dec de
	ld a,d \ cpl \ ld d,a
	ld a,e \ cpl \ ld e,a
	
	ld bc,(TraceDX)
	
	exx	
	
	ld hl,(VertexTop.X)
	ld de,(VertexTop.Y)
	ld bc,(TraceDX)
	inc bc
	
	--	ld ix,(TraceEdgeOutputA)
		call SetClippedEdge
		res JustMovedY,(iy+FillFlags)
		
	-	ld ix,(TraceEdgeOutputB)
		call SetClippedEdge
		
		inc hl
		
		exx
			add hl,de
			bit 7,h
			jr z,+
				add hl,bc
				exx \ inc de \ exx
				set JustMovedY,(iy+FillFlags)
			+
		exx
		
		dec bc
		ld a,b
		or c
		jp z,UpdateTracedBounds
		
		bit JustMovedY,(iy+FillFlags)
		jr z,-
	jr --

TraceEdgeDXOverDYNegative ; dx < 0

	ld hl,(TraceDX)
	dec hl
	ld a,h \ cpl \ ld h,a
	ld a,l \ cpl \ ld l,a
	sra h
	rr l
	ld (TraceError),hl
	
	ld de,(TraceDY)
	dec de
	ld a,d \ cpl \ ld d,a
	ld a,e \ cpl \ ld e,a
	
	ld bc,(TraceDX)
	dec bc
	ld a,b \ cpl \ ld b,a
	ld a,c \ cpl \ ld c,a
	
	exx	
	
	ld hl,(VertexTop.X)
	ld de,(VertexBottom.X)
	push de
	or a
	sbc hl,de
	ld b,h \ ld c,l
	inc bc
	pop hl
	ld de,(VertexBottom.Y)
	
	--	ld ix,(TraceEdgeOutputA)
		call SetClippedEdge
		res JustMovedY,(iy+FillFlags)
		
	-	ld ix,(TraceEdgeOutputB)
		call SetClippedEdge
		
		inc hl
		
		exx
			add hl,de
			bit 7,h
			jr z,+
				add hl,bc
				exx \ dec de \ exx
				set JustMovedY,(iy+FillFlags)
			+
		exx
		
		dec bc
		ld a,b
		or c
		jr z,+
		
		bit JustMovedY,(iy+FillFlags)
		jr z,-
		
	jr --
+
	ld a,(FirstValidY)
	ld l,a
	ld a,(LastValidY)
	ld (FirstValidY),a
	ld a,l
	ld (LastValidY),a
	jp UpdateTracedBounds

; ..................................
TraceEdgeDYOverDX ; |dx|>|dy|
	ld hl,(TraceDY)	
	sra h
	rr l
	ld (TraceError),hl
	
	ld hl,(TraceDX)
	bit 7,h
	jr nz,TraceDXNegative

TraceDXPositive

	; DE = -HL
	dec hl
	ld a,h
	cpl
	ld d,a
	ld a,l
	cpl
	ld e,a
	
	ld hl,(TraceError)
	ld bc,(TraceDY)
	exx
	
	ld hl,(VertexTop.X)
	ld de,(VertexTop.Y)
	ld bc,(TraceDY)
	inc bc
	
	-	ld ix,(TraceEdgeOutputA)
		call SetClippedEdge
		ld ix,(TraceEdgeOutputB)
		call SetClippedEdge

		exx
			add hl,de
			bit 7,h
			jr z,+
				add hl,bc
				exx \ inc hl \ exx
			+
		exx
		
		inc de
		dec bc
		ld a,b
		or c
	
	jr nz,-
	jr UpdateTracedBounds

TraceDXNegative

	ld de,(TraceError)
	ex de,hl
	ld bc,(TraceDY)
	exx
	
	ld hl,(VertexTop.X)
	ld de,(VertexTop.Y)
	ld bc,(TraceDY)
	inc bc
	
	-	ld ix,(TraceEdgeOutputA)
		call SetClippedEdge
		ld ix,(TraceEdgeOutputB)
		call SetClippedEdge

		exx
		add hl,de
		bit 7,h
		jr z,+
			add hl,bc
			exx \ dec hl \ exx
		+
		exx
		
		inc de
		dec bc
		ld a,b
		or c
	jr nz,-

UpdateTracedBounds

	bit FoundFirstValidY,(iy+FillFlags)
	ret z


	ld a,(TopOfTriangle)
	ld b,a
	ld a,(FirstValidY)
	cp b
	jr nc,+
	ld (TopOfTriangle),a
+
	
	ld a,(BottomOfTriangle)
	ld b,a
	ld a,(LastValidY)
	cp b
	jr c,+
	ld (BottomOfTriangle),a
+

	ret


;------------------------------------------------------------------------------- 
;@doc:routine
; 
; === Triangle.SetClippedEdge ===
;
;   Clips and stores an edge point (X,Y) in the edge table.
;
; INPUTS:
;   REGISTERS
;   * HL - X coordinate to clip.
;   * DE - Y coordinate to clip.
;   MEMORY
;   * TraceEdgeOutput - Pointer to 64 bytes for traced edge table.
;   * Graphics.Bounds - Graphics viewport boundaries.
;
; DESTROYED:
;   REGISTERS
;   * AF.
;
;@doc:end
;------------------------------------------------------------------------------- 
SetClippedEdge
	; Clip to Y.
	ld a,d
	or a
	ret nz
	ld a,e
	and ~63
	ret nz
	
	push hl
	
	; So, Y is between 0..63, so can go on our buffer somewhere!
	ld a,h
	or a
	jr z,SetClippedEdgeL

	ld a,(Graphics.Bounds+1) ; MaxX
	bit 7,h
	jr z,FoundClippedEdge
	ld a,(Graphics.Bounds+0) ; MinX
	jr FoundClippedEdge


SetClippedEdgeL
	; We need to clip L between MinX..MaxX
	ld a,(Graphics.Bounds+0) ; MinX
	cp l
	jr z,FoundValidClippedEdge
	jr nc,FoundClippedEdge

	ld a,(Graphics.Bounds+1) ; MaxX
	cp l
	jr c,FoundClippedEdge

FoundValidClippedEdge
	ld a,e
	bit FoundFirstValidY,(iy+FillFlags)
	jr nz,+
		ld (FirstValidY),a
		set FoundFirstValidY,(iy+FillFlags)
	+
	ld (LastValidY),a
	ld a,l
FoundClippedEdge
	push ix
	pop hl
	add hl,de
	ld (hl),a
	pop hl
	ret	

.endmodule