*=======================================================*
*	BSP-Descent: latest update 27/11/95		*
*=======================================================*
*	Descend BSP tree, generating sectors & walls.	*
*=======================================================*
*     >	New 68030 replacement by Douglas Little.	*
*     >	Atari C conversion by Johan Klockars.		*
*     >	Original C++ code for the PC by Jake Hill.	*
*=======================================================*
*	Some improvements made to 68030 version:	*
*=======================================================*
*     >	Node-quadrant checks changed to octants.	*
*     >	Nodes projected & checked against viewcone. 	*
*     >	Nodes checked against wall occlusion list.	*
*     >	Program recursion removed & replaced by stack.	*
*     >	Optimised for latent-memory references.		*
*     >	Accuracy of 3D calculations improved (32 bit).	*
*     >	Local variables accessed from structure.	*
*     >	Temporary lighting effects just for fun.	*
*     >	Several 16-bit offset-addressing bug fixes.	*
*     >	Logic flow simplified around AddWall		*
*     >	Projection now peformed in realtime.		*
*=======================================================*

invisible_code	=	0
visible_code	=	1

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Descend Binary Space Partitioning Tree		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
descend_bsp:
*-------------------------------------------------------*
*	Place start & terminator on heap and descend	*
*-------------------------------------------------------*
	move.l		sp,bsp_return
	lea		display_struct,a6
	push.w		#terminator
	push.w		maxnode
	bra		next_node
*-------------------------------------------------------*
*	Thread returns here when tree is exhausted	*
*-------------------------------------------------------*
finish_tree:
*-------------------------------------------------------*
	move.l		bsp_return,sp
	rts

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	[node] = [sector] -> draw this node		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
ssector_node:
*-------------------------------------------------------*
*	Stop drawing when [width] columns are filled	*
*-------------------------------------------------------*
	tst.w		columns
	beq.s		finish_tree
*-------------------------------------------------------*
*	Stop drawing when last node has been popped	*
*-------------------------------------------------------*
	not.w		d0
	beq.s		finish_tree
	eor.w		#$7FFF,d0

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Render ssector into run-buffer			*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
build_ssector:
*-------------------------------------------------------*
*	Locate [segs] for this [ssector]		*
*-------------------------------------------------------*
	move.l		display_ssectors(a6),a0
	moveq		#0,d4
	move.w		ssec_first(a0,d0.w*4),d4
	moveq		#0,d3
	move.w		ssec_segments(a0,d0.w*4),d3
*-------------------------------------------------------*
*	Locate [linedef] & [sidedef] for first [seg]	*
*-------------------------------------------------------*
	move.l		d4,d0
	move.l		display_segs(a6),a2
	add.l		d0,d0
	add.l		d4,d0
	lsl.l		#2,d0
	add.l		d0,a2				; a+(d*12)
	moveq		#0,d0
	move.w		seg_linedef(a2),d0
	moveq		#0,d2
	move.w		seg_sidedef(a2),d2
*-------------------------------------------------------*
*	Locate right [sidedef] for this [linedef]	*
*-------------------------------------------------------*
	move.l		d0,d1
	move.l		display_linedefs(a6),a0
	lsl.l		#3,d0
	sub.l		d1,d0
	add.l		d0,d0
	add.l		d0,a0				; a+(d*14)
	moveq		#0,d1
	move.w		linedef_right(a0,d2.w*2),d1 
*-------------------------------------------------------*
*	Locate [sector] for this [sidedef]		*
*-------------------------------------------------------*
	move.l		d1,d0 
	move.l		display_sidedefs(a6),a0
	lsl.l		#4,d0 
	sub.l		d1,d0				; a+(d*30)
	move.w		sidedef_sector(a0,d0.l*2),d1	
*-------------------------------------------------------*
*	Set up floor & ceiling heights for this sector	*
*-------------------------------------------------------*
	move.l		d1,d0
	add.l		d0,d0
	move.l		d0,d2
	lsl.l		#3,d0
	move.l		display_sectors(a6),a0
	sub.l		d2,d0
	sub.l		d1,d0				; a+(d*26)
	add.l		d0,d0
	add.l		d0,a0
	move.l		a0,this_sector
	move.w		sector_floorht(a0),floor_ht
	move.w		sector_ceilht(a0),ceiling_ht
*-------------------------------------------------------*
*	Are we in this sector?				*
*-------------------------------------------------------*
	tst.w		first_ssector
	beq.s		.skip
	clr.w		first_ssector
*-------------------------------------------------------*
*	Set viewcone to (sector_height+player_height)	*
*-------------------------------------------------------*
	move.w		floor_ht,d0
	add.w		#player_height,d0
	move.w		d0,Ph
*-------------------------------------------------------*
*	Set up segment-heap for loop			*
*-------------------------------------------------------*
.skip:	move.l		d4,d2
	move.w		d2,display_segbase(a6)
	move.w		d3,display_segnum(a6)
	ble		end_ssector
*-------------------------------------------------------*
*	Process simple lighting effects (temporary!)	*
*-------------------------------------------------------*
	ifd		lighting_effects
	bsr		process_lighting
	endc
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Render segments surrounding this ssector	*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
segment_loop:
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Hidden surface removal stage #1			*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Is viewer on left or right side of this line?	*
*-------------------------------------------------------*
*	((y2-y1)*(Px-x1))) => (((x2-x1)*(Py-y1)) ?	*
*-------------------------------------------------------*
	move.l		display_vertices(a6),a0
	moveq		#0,d0
	moveq		#0,d1
	move.w		linedef_from(a2),d0
	move.w		linedef_to(a2),d1
	move.w		vtx_x(a0,d0.l*4),d5
	move.w		vtx_x(a0,d1.l*4),d6
	move.w		vtx_y(a0,d0.l*4),d0
	move.w		vtx_y(a0,d1.l*4),d1
	sub.w		d5,d6			; x2-x1
	sub.w		d0,d1			; y2-y1
	neg.w		d5
	add.w		display_px(a6),d5	; px-x1
	neg.w		d0
	add.w		display_py(a6),d0	; py-y1
	muls.w		d6,d0			; (x2-x1)*(Py-y1)
	muls.w		d5,d1			; (y2-y1)*(Px-x1)
	cmp.l		d0,d1
	bmi		invisible
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Segment is visible				*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
	pea		(a2)
*-------------------------------------------------------*
	moveq		#0,d0
	move.w		display_segbase(a6),d0
	move.l		d0,d1
	move.l		display_segs(a6),a5
	add.l		d0,d0
	add.l		d1,d0
	lsl.l		#2,d0
	add.l		d0,a5			; a+(d*12)
*-------------------------------------------------------*
*	Locate segment vertices				*
*-------------------------------------------------------*
	move.l		display_vertices(a6),a0
	moveq		#0,d0
	move.w		seg_from(a5),d0
	move.l		a0,a1
	moveq		#0,d1
	move.w		seg_to(a5),d1 
	lsl.l		#2,d0
	lsl.l		#2,d1
	add.l		d0,a0			; a+(d*4)
	add.l		d1,a1			; a+(d*4)
*-------------------------------------------------------*
*	Fetch X1,Y1 / X2,Y2 & centre around viewpoint	*
*-------------------------------------------------------*
	move.w		display_px(a6),d1
	move.w		display_py(a6),d7
	move.w		vtx_x(a0),d4
	move.w		vtx_y(a0),d5
	move.w		vtx_x(a1),d6
	move.w		vtx_y(a1),d2
	sub.w		d1,d4		; dx1
	sub.w		d7,d5		; dy1
	sub.w		d1,d6		; dx2
	sub.w		d7,d2		; dy2
*-------------------------------------------------------*
*	Rotate X & Y into canonical VX & VZ		*
*-------------------------------------------------------*
	move.w		display_sina(a6),d0
	move.w		display_cosa(a6),d7
*-------------------------------------------------------*
*	x1 = (dx1)*sin(a) + (dy1)*cos(a)		*
*	z1 = (dx1)*cos(a) - (dy1)*sin(a)		*
*-------------------------------------------------------*
	move.w		d4,d3
	move.w		d5,d1
	muls.w		d7,d4
	muls.w		d0,d5
	muls.w		d0,d3
	muls.w		d7,d1
	sub.l		d5,d4
	add.l		d1,d3
*-------------------------------------------------------*
*	x2 = (dx2)*sin(a) + (dy2)*cos(a)		*
*	z2 = (dx2)*cos(a) - (dy2)*sin(a)		*
*-------------------------------------------------------*
	move.w		d6,d5
	move.w		d2,d1
	muls.w		d7,d6
	muls.w		d0,d2
	muls.w		d0,d5
	muls.w		d7,d1
	sub.l		d2,d6
	add.l		d1,d5
*-------------------------------------------------------*
*	Renormalize output from matrix			*
*-------------------------------------------------------*
	lsl.l		#2,d3		; x1
	lsl.l		#2,d4		; z1
	lsl.l		#2,d5		; x2
	lsl.l		#2,d6		; z2
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Z-clipping of walls				*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
	moveq		#ZMIN,d0
	swap		d0
*-------------------------------------------------------*
*	Check for intersection with viewplane		*
*-------------------------------------------------------*
	cmp.l		d0,d4
	bgt.s		.vis1
*-------------------------------------------------------*
*	Skip segment if both points are behind viewer	*
*-------------------------------------------------------*
	cmp.l		d0,d6
	ble		end_segment
*-------------------------------------------------------*
*	Case #1 - clip X1,Z1 against ZMIN		*
*-------------------------------------------------------*
	sub.l		d4,d0		; (cz-z1)
	move.l		d5,d1
	sub.l		d3,d1		; (x2-x1)
	muls.l		d0,d2:d1	; (x2-x1)*(cz-z1)
	move.l		d6,d0
	sub.l		d4,d0		; (z2-z1)
	divs.l		d0,d2:d1	; ((x2-x1)*(cz-z1))/(z2-z1)
	add.l		d1,d3		; (((x2-x1)*(cz-z1))/(z2-z1))+x1
	moveq		#ZMIN,d4
	swap		d4		; z1 = cz
	bra.s		.vis2
*-------------------------------------------------------*
*	Draw segment if both points are in view		*
*-------------------------------------------------------*
.vis1:	cmp.l		d0,d6
	bgt.s		.vis2
*-------------------------------------------------------*
*	Case #2 - clip X2,Z2 against ZMIN		*
*-------------------------------------------------------*
	sub.l		d6,d0		; (cz-z2)
	move.l		d3,d1
	sub.l		d5,d1		; (x1-x2)
	muls.l		d0,d2:d1	; (x1-x2)*(cz-z2)
	move.l		d4,d0
	sub.l		d6,d0		; (z1-z2)
	divs.l		d0,d2:d1	; ((x1-x2)*(cz-z2))/(z1-z2)
	add.l		d1,d5		; (((x1-x2)*(cz-z2))/(z1-z2))+x2
	moveq		#ZMIN,d6
	swap		d6		; z2 = cz
*-------------------------------------------------------*
*	Project points into 2D viewspace		*
*-------------------------------------------------------*
.vis2:	moveq		#0,d1
	move.w		display_shwid(a6),d1
	swap		d1
	muls.l		d1,d0:d3
	divs.l		d4,d0:d3
	muls.l		d1,d0:d5
	divs.l		d6,d0:d5
	move.l		d1,d0
	add.l		d0,d0
*-------------------------------------------------------*
*	Centre screen coordinates & check bounds	*
*-------------------------------------------------------*
	neg.l		d5
	add.l		d1,d5
	ble		end_segment
	move.l		d5,d7
	cmp.l		d0,d7
	bmi.s		.i2in
	move.l		d0,d7	
.i2in:	neg.l		d3
	add.l		d1,d3
	move.l		d3,d1
	bpl.s		.i1in
	moveq		#0,d1
.i1in:	cmp.l		d0,d3
	bpl		end_segment
*-------------------------------------------------------*
*	Check size (i2-i1)				*
*-------------------------------------------------------*
	swap		d1
	swap		d7
	move.w		d7,d0
	sub.w		d1,d0
	ble		end_segment
*-------------------------------------------------------*
*	Discard fully occluded walls			*
*-------------------------------------------------------*
	ifd		dsp
*-------------------------------------------------------*
	dspwrite.l	#scan_command
	ext.l		d1
	dspwrite.l	d1
	ext.l		d7
	dspwrite.l	d7
	dspread.w	d0
	cmp.w		#visible_code,d0
	bne		end_segment
*-------------------------------------------------------*
	elseif
*-------------------------------------------------------*
	lea		occlusion_list,a2
	add.w		d1,a2
	moveq		#4-1,d2
	and.w		d0,d2
	lsr.w		#2,d0
	bra.s		.sbs
.sb:	tst.b		(a2)+
	bne.s		.draw
.sbs:	dbra		d2,.sb
	bra.s		.sls
.sl:	tst.l		(a2)+
	bne.s		.draw
.sls:	dbra		d0,.sl
	bra		end_segment
*-------------------------------------------------------*
	endc
*-------------------------------------------------------*
*	Write coordinates into addwall struct		*
*-------------------------------------------------------*
.draw:	lea		addwall_struct,a2
	move.l		d3,addwall_i1(a2)
	move.l		d4,addwall_z1(a2)
	move.l		d5,addwall_i2(a2)
	move.l		d6,addwall_z2(a2)
*-------------------------------------------------------*
*	Look up linedef for this seg			*
*-------------------------------------------------------*
	moveq		#0,d1
	move.w		seg_linedef(a5),d1
	move.l		d1,d0 
	move.l		display_linedefs(a6),a0
	lsl.l		#3,d0 
	sub.l		d1,d0
	add.l		d0,d0
	add.l		d0,a0
	move.l		a0,a1
*-------------------------------------------------------*
*	Determine one or two-sided linedef		*
*-------------------------------------------------------*
	moveq		#attrib_twosided,d0
	and.w		linedef_attrib(a0),d0
	move.b		d0,twosided_flag
*-------------------------------------------------------*
*	Determine which sidedef is facing us		*
*-------------------------------------------------------*
	move.w		seg_sidedef(a5),d0
	moveq		#0,d5
	move.w		linedef_right(a0,d0.l*2),d5	; visible sidedef
	bchg		#0,d0
	moveq		#0,d6
	move.w		linedef_right(a0,d0.l*2),d6	; invisible sidedef
*-------------------------------------------------------*
*	Look up sidedef for visible side of linedef	*
*-------------------------------------------------------*
	move.l		d5,d0
	move.l		d0,d1
	move.l		display_sidedefs(a6),a3
	lsl.l		#4,d0
	sub.l		d1,d0
	add.l		d0,d0
	add.l		d0,a3				; a+(d*30)
*-------------------------------------------------------*
*	(a6) pointer to addwall structure		*
*-------------------------------------------------------*
	lea		addwall_struct,a6
*-------------------------------------------------------*
*	Hack colours & lighting to something useful	*
*-------------------------------------------------------*
	move.w		a3,sector_colour
	move.w		sidedef_sector(a3),d0
	bsr		select_colours
*-------------------------------------------------------*
*	Check for main wall texture			*
*-------------------------------------------------------*
	cmpi.b		#'-',sidedef_mtns(a3) 
	beq.s		sector_window
*-------------------------------------------------------*
*	Valid texture indicates a solid sector wall	*
*-------------------------------------------------------*
sector_wall:	
*-------------------------------------------------------*
	move.b		twosided_flag,addwall_opaque(a6)
	move.w		Ph,d0
	move.w		d0,d1
	sub.w		ceiling_ht,d1
	move.w		d0,d2
	sub.w		floor_ht,d2
	cmp.w		d1,d2
	bmi		end_segment
	move.w		d1,addwall_y1(a6)
	move.w		d2,addwall_y2(a6)
	move.b		#WALL_TYPE,addwall_type(a6)
	bsr		AddWall
	bra		end_segment
*-------------------------------------------------------*
sector_window:
*-------------------------------------------------------*
	move.b		#0,addwall_opaque(a6)
*-------------------------------------------------------*
*	Locate [sector] on opposite side of [linedef]	*
*-------------------------------------------------------*
	move.l		d6,d0
	move.l		Side_Array,a4
	move.l		d0,d1
	lsl.l		#4,d0
	sub.l		d1,d0
	move.w		sidedef_sector(a4,d0.l*2),a0	; a+(d*30)
	lea		(a0,a0.l*2),a2
	move.l		Sector_Array,a1
	move.l		a2,d0 
	lsl.l		#2,d0
	add.l		a0,d0
	lea		(a1,d0.l*2),a4			; a+(d*26)
*-------------------------------------------------------*
*	Check for lower wall texture			*
*-------------------------------------------------------*
	move.w		floor_ht,d1 
	cmp.b		#'-',sidedef_ltns(a3) 
	beq.s		lower_floor
*-------------------------------------------------------*
*	Valid texture indicates a solid lower wall	*
*-------------------------------------------------------*
lower_wall:
*-------------------------------------------------------*
	move.w		sector_floorht(a4),d1
	cmp.w		ceiling_ht,d1
	bmi.s		lower_floor
	move.w		ceiling_ht,d1
*-------------------------------------------------------*
lower_floor:
*-------------------------------------------------------*
	move.w		floor_ht,d2 
	neg.w		d1
	neg.w		d2
	add.w		Ph,d1
	add.w		Ph,d2
	cmp.w		d1,d2
	bpl.s		.fix
	move.w		d2,d1
.fix:	move.w		d1,addwall_y1(a6)
	move.w		d2,addwall_y2(a6)
	move.b		#LOWER_TYPE,addwall_type(a6)
	bsr		AddWall 
	tst.w		columns
	beq.s		end_segment		 
*-------------------------------------------------------*
*	Check for upper wall texture			*
*-------------------------------------------------------*
	move.w		ceiling_ht,d2 
	cmp.b		#'-',sidedef_utns(a3) 
	beq.s		upper_ceiling
*-------------------------------------------------------*
*	Valid texture indicates a solid upper wall	*
*-------------------------------------------------------*
upper_wall:
*-------------------------------------------------------*
	move.w		sector_ceilht(a4),d2
	cmp.w		floor_ht,d2
	bpl.s		upper_ceiling
	move.w		floor_ht,d2
*-------------------------------------------------------*
upper_ceiling:
*-------------------------------------------------------*
	move.w		ceiling_ht,d1 
	neg.w		d1
	neg.w		d2
	add.w		Ph,d1
	add.w		Ph,d2
	cmp.w		d1,d2
	bpl.s		.fix
	move.w		d1,d2
.fix:	move.w		d1,addwall_y1(a6)
	move.w		d2,addwall_y2(a6)
	move.b		#UPPER_TYPE,addwall_type(a6)
	bsr		AddWall 
*-------------------------------------------------------*
end_segment:
*-------------------------------------------------------*
	pop.l		a2
*-------------------------------------------------------*
*	Proceed to next segment				*
*-------------------------------------------------------*
invisible:
*-------------------------------------------------------*
	lea		display_struct,a6
	lea		seg_len(a2),a2
	addq.w		#1,display_segbase(a6)
	subq.w		#1,display_segnum(a6)
	beq		end_ssector
	tst.w		columns
	bne		segment_loop
*-------------------------------------------------------*
end_ssector:
*-------------------------------------------------------*
*	Fetch next node from heap and descend again	*
*-------------------------------------------------------*
next_node:
*-------------------------------------------------------*
	move.w		(sp)+,d0
	bmi		ssector_node

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	[node] /= [sector] -> descend again		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
dividing_node:
*-------------------------------------------------------*
	move.l		display_nodes(a6),a1	
	move.l		(a1,d0.w*4),a1
*-------------------------------------------------------*
*	Inverse descent rules for left side of tree	*
*-------------------------------------------------------*
*	(dy*(x1-Px))) => ((dx*(y1-Py)) ?		*
*-------------------------------------------------------*
	move.w		node_dx(a1),d2
	move.w		node_x(a1),d0
	move.w		node_dy(a1),d3
	move.w		node_y(a1),d1
	add.w		d2,d0			; x2 = (x1+dx)
	sub.w		display_px(a6),d0	; (x2-px)
	add.w		d3,d1			; y2 = (y1+dy)
	sub.w		display_py(a6),d1	; (xy-py)
	muls.w		d2,d1			; (y2-py) * dx
	muls.w		d3,d0			; (x2-px) * dy
	cmp.l		d0,d1 
	bmi.s		node_leftside
*-------------------------------------------------------*
*	Viewer is on right side of node divider		*
*-------------------------------------------------------*
node_rightside:
*-------------------------------------------------------*
	lea		node_lvtx(a1),a0
	bsr.s		nodeincone
	beq.s		.noln
	move.w		node_left(a1),-(sp)
.noln:	lea		node_rvtx(a1),a0
	bsr.s		nodeincone
	beq.s		next_node
	move.w		node_right(a1),-(sp) 
	bra.s		next_node
*-------------------------------------------------------*
*	Viewer is on left side of node divider		*
*-------------------------------------------------------*
node_leftside:
*-------------------------------------------------------*
	lea		node_rvtx(a1),a0
	bsr.s		nodeincone
	beq.s		.noln
	move.w		node_right(a1),-(sp) 
.noln:	lea		node_lvtx(a1),a0
	bsr.s		nodeincone
	beq.s		next_node
	move.w		node_left(a1),-(sp)
	bra.s		next_node

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Determine visibility of a child node.		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Only exposed nodes are dealt with.		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*

*-------------------------------------------------------*
*	Check #1 -> Octal node elimination		* 
*-------------------------------------------------------*
*	All nodes are checked against the 3 octal	*
*	segments immediately in front of viewcone.	*
*	Nodes from 5 of all 8 octants are discarded.	*
*-------------------------------------------------------*
*	Check #2 -> Canonical volume intersection	* 
*-------------------------------------------------------*
*	The remaining nodes are fully intersected	*
*	with the projected canonical view volume.	*
*	Any nodes outside the viewcone are discarded.	*
*-------------------------------------------------------*
*	Check #3 -> Occlusion check			* 
*-------------------------------------------------------*
*	Any nodes remaining in view are checked		*
*	against the occlusion table. Any nodes		*
*	completely occluded by walls are discarded.	*
*-------------------------------------------------------*
nodeincone:
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Octal segment BSP node eliminator		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Eliminates nodes from 5 out of all 8 octants	*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
qx1	equr		d1
qy1	equr		d2
qx2	equr		d3
qy2	equr		d4
*-------------------------------------------------------*
	move.w		display_px(a6),d5
	move.w		display_py(a6),d6
	move.w		display_octant(a6),d7
	moveq		#0,d0
	jmp		octs(pc,d7.w)
*-------------------------------------------------------*
*	Octant elimination table		 	*
*-------------------------------------------------------*
*	Octants are out of phase by 1/4 turn		*
*-------------------------------------------------------*
octs:	dc.w		oct_2-octs
	dc.w		oct_3-octs
	dc.w		oct_4-octs
	dc.w		oct_5-octs
	dc.w		oct_6-octs
	dc.w		oct_7-octs
	dc.w		oct_0-octs
	dc.w		oct_1-octs
*-------------------------------------------------------*
*	Octant elimination routines		 	*
*-------------------------------------------------------*
oct_0:	move.w		nodevtx_y1(a0),qy1
	move.w		nodevtx_x2(a0),qx2
	sub.w		d6,qy1
	bpl.s		.x
	sub.w		d5,qx2
	cmp.w		qy1,qx2
	bpl		project_node
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_1:	move.w		nodevtx_x2(a0),qx2
	move.w		nodevtx_y1(a0),qy1
	sub.w		d5,qx2
	bmi.s		.x
	sub.w		d6,qy1
	cmp.w		qy1,qx2
	bpl		project_node
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_2:	move.w		nodevtx_x2(a0),qx2
	move.w		nodevtx_y2(a0),qy2
	sub.w		d5,qx2
	bmi.s		.x
	sub.w		d6,qy2
	neg.w		qy2
	cmp.w		qy2,qx2
	bpl.s		project_node
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_3:	move.w		nodevtx_y2(a0),qy2
	move.w		nodevtx_x2(a0),qx2
	sub.w		d6,qy2
	bmi.s		.x
	sub.w		d5,qx2
	neg.w		qy2
	cmp.w		qy2,qx2
	bpl.s		project_node
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_4:	move.w		nodevtx_y2(a0),qy2
	move.w		nodevtx_x1(a0),qx1
	sub.w		d6,qy2
	bmi.s		.x
	sub.w		d5,qx1
	cmp.w		qy2,qx1
	bmi.s		project_node
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_5:	move.w		nodevtx_x1(a0),qx1
	move.w		nodevtx_y2(a0),qy2
	sub.w		d5,qx1
	bpl.s		.x
	sub.w		d6,qy2
	cmp.w		qy2,qx1
	bmi.s		project_node
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_6:	move.w		nodevtx_x1(a0),qx1
	move.w		nodevtx_y1(a0),qy1
	sub.w		d5,qx1
	bpl.s		.x
	sub.w		d6,qy1
	neg.w		qy1
	cmp.w		qy1,qx1
	bmi.s		project_node	
.x:	tst.l		d0
	rts
*-------------------------------------------------------*
oct_7:	move.w		nodevtx_y1(a0),qy1
	move.w		nodevtx_x1(a0),qx1
	sub.w		d6,qy1
	bpl.s		.x
	sub.w		d5,qx1
	neg.w		qy1
	cmp.w		qy1,qx1
	bmi.s		project_node
.x:	tst.l		d0
	rts
	
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*	Intersect node with viewcone in 2D		*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
project_node:	
*-------------------------------------------------------*
	pea		(a1)
*-------------------------------------------------------*
	move.w		#$1000,d0
	move.l		d0,display_imin(a6)
	neg.l		d0
	move.l		d0,display_imax(a6)
*=======================================================*
*	Prefetch X2,Y2 for polygon loop			*
*=======================================================*
	move.w		nodevtx_x1(a0),d4
	move.w		nodevtx_y2(a0),d6
	sub.w		display_px(a6),d4
	sub.w		display_py(a6),d6
*-------------------------------------------------------*
*	Rotate NY & NZ into canonical VZ & VX		*
*-------------------------------------------------------*
*	x = (dx)*sin(a) + (dy)*cos(a)			*
*	z = (dx)*cos(a) - (dy)*sin(a)			*
*-------------------------------------------------------*
	move.w		display_sina(a6),d1
	move.w		display_cosa(a6),d2
	move.w		d4,d3
	move.w		d6,d5
	muls.w		d2,d4
	muls.w		d1,d6
	muls.w		d1,d3
	muls.w		d2,d5
	sub.l		d6,d4
	add.l		d5,d3
	lsl.l		#2,d3
	lsl.l		#2,d4
*-------------------------------------------------------*
*	Limit & hold as X2,Y2				*
*-------------------------------------------------------*
	move.l		d3,a2
	move.l		d4,a3
*=======================================================*
*	2D polygon cone-intersection 			*
*=======================================================*
	lea		nodev_indices,a1
	moveq		#4-1,d7
*-------------------------------------------------------*
*	Fetch new X1,Y1 & centre at origin		*
*-------------------------------------------------------*
.rect:	move.w		(a1)+,d6
	move.w		(a1)+,d2
	move.w		(a0,d6.w),d6
	move.w		(a0,d2.w),d2
	sub.w		display_px(a6),d6
	sub.w		display_py(a6),d2
*-------------------------------------------------------*
*	Rotate NY & NZ into canonical VZ & VX		*
*-------------------------------------------------------*
*	x = (dx)*sin(a) + (dy)*cos(a)			*
*	z = (dx)*cos(a) - (dy)*sin(a)			*
*-------------------------------------------------------*
	move.w		display_sina(a6),d3
	move.w		display_cosa(a6),d4
	move.w		d6,d5
	move.w		d2,d1
	muls.w		d4,d6
	muls.w		d3,d2
	muls.w		d3,d5
	muls.w		d4,d1
	sub.l		d2,d6
	add.l		d1,d5
	lsl.l		#2,d5
	lsl.l		#2,d6
*-------------------------------------------------------*
*	Clip X1,Y1 / store next X2,Y2 / get this X2,Y2	*
*-------------------------------------------------------*
	move.l		a2,d3
	move.l		a3,d4
	move.l		d5,a2
	move.l		d6,a3
*-------------------------------------------------------*
*	Reorient line and check against viewplane	*
*-------------------------------------------------------*
	cmp.l		d4,d6
	bpl.s		.swap
	exg.l		d3,d5
	exg.l		d4,d6
.swap:	moveq		#ZMIN,d1
	swap		d1
	cmp.l		d1,d6
	ble.s		.next	
*-------------------------------------------------------*
*	z-clip line if it intersects with viewplane	*	
*-------------------------------------------------------*
	moveq		#ZMIN,d0
	swap		d0
	sub.l		d4,d0		; (cz-z1)
	ble.s		.nzcl	
	move.l		d5,d1
	sub.l		d3,d1		; (x2-x1)
	muls.l		d0,d2:d1	; (x2-x1)*(cz-z1)
	move.l		d6,d0
	sub.l		d4,d0		; (z2-z1)
	divs.l		d0,d2:d1	; ((x2-x1)*(cz-z1))/(z2-z1)
	add.l		d1,d3		; (((x2-x1)*(cz-z1))/(z2-z1))+x1
	moveq		#ZMIN,d4
	swap		d4		; z1 = cz
*-------------------------------------------------------*
*	Project points into 2D viewspace		*
*-------------------------------------------------------*
.nzcl:	moveq		#0,d1
	move.w		display_shwid(a6),d1
	muls.l		d1,d0:d3
	divs.l		d4,d0:d3
	muls.l		d1,d0:d5
	divs.l		d6,d0:d5
*-------------------------------------------------------*
*	Adjust bounds					*
*-------------------------------------------------------*
	move.l		display_imin(a6),d1
	neg.l		d3
	neg.l		d5
	move.l		display_imax(a6),d2
	cmp.l		d1,d3
	bpl.s		.n1
	move.l		d3,d1
.n1:	cmp.l		d2,d3
	ble.s		.n2
	move.l		d3,d2
.n2	cmp.l		d1,d5
	bpl.s		.n3
	move.l		d5,d1
.n3:	cmp.l		d2,d5
	ble.s		.n4
	move.l		d5,d2
.n4:	move.l		d1,display_imin(a6)
	move.l		d2,display_imax(a6)
.next:	dbra		d7,.rect
*-------------------------------------------------------*
*	Inside / outside viewport check			*
*-------------------------------------------------------*
	move.l		display_imin(a6),d3
	moveq		#0,d0
	move.l		display_imax(a6),d5
	subq.l		#1,d3
	addq.l		#1,d5
	moveq		#0,d2
	move.w		display_width(a6),d2
	move.l		d2,d1
	lsr.l		d1
	add.l		d1,d5
	bmi.s		.end
	add.l		d1,d3
	bpl.s		.x1in
	moveq		#0,d3
.x1in:	cmp.l		d2,d3
	bpl.s		.end
	cmp.l		d2,d5
	bmi.s		.x2in
	move.l		d2,d5
.x2in:	sub.l		d3,d5
	ble.s		.end
*-------------------------------------------------------*
*	Occlusion check					*
*-------------------------------------------------------*
	ifd		dsp
*-------------------------------------------------------*
	add.l		d3,d5
	dspwrite.l	#scan_command
	dspwrite.l	d3
	dspwrite.l	d5
	dspread.w	d0
	ext.l		d0
*-------------------------------------------------------*
	elseif
*-------------------------------------------------------*
	moveq		#1,d0
	lea		occlusion_list,a2
	add.w		d3,a2
	moveq		#4-1,d2
	and.w		d5,d2
	lsr.w		#2,d5
	bra.s		.sbs
.sb:	tst.b		(a2)+
	bne.s		.end
.sbs:	dbra		d2,.sb
	bra.s		.sls
.sl:	tst.l		(a2)+
	bne.s		.end
.sls:	dbra		d5,.sl
	moveq		#0,d0
*-------------------------------------------------------*
	endc
*-------------------------------------------------------*
.end:	pop.l		a1
*-------------------------------------------------------*
*	Return exitcode					*
*-------------------------------------------------------*
end_nodecheck:
*-------------------------------------------------------*
	tst.l		d0
	rts 

*-------------------------------------------------------*
			data
*-------------------------------------------------------*

*-------------------------------------------------------*
*	Ordered list of node->polygon vertex defs	*
*-------------------------------------------------------*
nodev_indices:		dc.w	nodevtx_x1,nodevtx_y1
			dc.w	nodevtx_x2,nodevtx_y1
			dc.w	nodevtx_x2,nodevtx_y2
			dc.w	nodevtx_x1,nodevtx_y2

*-------------------------------------------------------*
			bss
*-------------------------------------------------------*

maxnode:		ds.l	1	
floor_ht:		ds.l	1	
ceiling_ht:		ds.l	1	
first_ssector:		ds.w	1	
sector_colour:		ds.w	1
this_sector:		ds.l	1
bsp_return:		ds.l	1
twosided_flag:		ds.b	1
			even

*-------------------------------------------------------*
			text
*-------------------------------------------------------*