note
	description: "[
		r_bsp.c
		BSP traversal, handling of LineSegs for rendering
	]"
	license: "[
				Copyright (C) 1993-1996 by id Software, Inc.
				Copyright (C) 2005-2014 Simon Howard
				Copyright (C) 2021 Ilgiz Mustafin
		
				This program is free software; you can redistribute it and/or modify
				it under the terms of the GNU General Public License as published by
				the Free Software Foundation; either version 2 of the License, or
				(at your option) any later version.
		
				This program is distributed in the hope that it will be useful,
				but WITHOUT ANY WARRANTY; without even the implied warranty of
				MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
				GNU General Public License for more details.
		
				You should have received a copy of the GNU General Public License along
				with this program; if not, write to the Free Software Foundation, Inc.,
				51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
	]"

class 
	R_BSP

create 
	make

feature 

	i_main: I_MAIN

	make (a_i_main: I_MAIN)
		local
			i: INTEGER_32
		do
			i_main := a_i_main
			create solidsegs.make_filled (create {CLIPRANGE_T}, 0, Maxsegs - 1)
			from
				i := 0
			until
				i > solidsegs.upper
			loop
				solidsegs [i] := create {CLIPRANGE_T}
				i := i + 1
			end
			drawsegs := {REF_ARRAY_CREATOR [DRAWSEG_T]}.make_ref_array ({R_DEFS}.maxdrawsegs)
			create frontsector.make
			create curline.make
			create linedef.make
			create sidedef
		ensure
				{UTILS [DRAWSEG_T]}.invariant_ref_array (drawsegs, {R_DEFS}.maxdrawsegs)
		end
	
feature 

	Maxsegs: INTEGER_32 = 32

	newend: INTEGER_32
			-- one past the last valid seg

	solidsegs: ARRAY [CLIPRANGE_T]

	drawsegs: ARRAY [DRAWSEG_T]

	ds_p: INTEGER_32 assign set_ds_p
			-- pointer inside drawsegs

	set_ds_p (a_ds_p: like ds_p)
		do
			ds_p := a_ds_p
		end

	frontsector: SECTOR_T assign set_frontsector

	set_frontsector (a_frontsector: like frontsector)
		do
			frontsector := a_frontsector
		end

	backsector: detachable SECTOR_T assign set_backsector

	set_backsector (a_backsector: like backsector)
		do
			backsector := a_backsector
		end
	
feature 

	curline: SEG_T assign set_curline

	set_curline (a_curline: like curline)
		do
			curline := a_curline
		end

	sidedef: SIDE_T assign set_sidedef

	set_sidedef (a_sidedef: like sidedef)
		do
			sidedef := a_sidedef
		end

	linedef: LINE_T assign set_linedef

	set_linedef (a_linedef: like linedef)
		do
			linedef := a_linedef
		end
	
feature 

	r_clearclipsegs
		do
			solidsegs [0].first := -2147483647
			solidsegs [0].last := -1
			solidsegs [1].first := i_main.R_draw.viewwidth
			solidsegs [1].last := 2147483647
			newend := 2
		end

	r_cleardrawsegs
		do
			ds_p := 0
		end

	r_renderbspnode (bspnum: INTEGER_32)
			-- Renders all subsectors below a given node,
			-- traversing subtree recursively.
			-- Just call with BSP root
		local
			bsp: NODE_T
			side: INTEGER_32
			side_bool: BOOLEAN
		do
			if bspnum & {DOOMDATA_H}.nf_subsector /= 0 then
				if bspnum = -1 then
					r_subsector (0)
				else
					r_subsector (bspnum & ({DOOMDATA_H}.nf_subsector.bit_not))
				end
			else
				bsp := i_main.P_setup.nodes [bspnum]
				side_bool := i_main.R_main.r_pointonside (i_main.R_main.viewx, i_main.R_main.viewy, bsp)
				if side_bool then
					side := 1
				else
					side := 0
				end
				r_renderbspnode (bsp.children [side].to_integer_32)
				if r_checkbbox (bsp.bbox [side.bit_xor (1)]) then
					r_renderbspnode (bsp.children [side.bit_xor (1)].to_integer_32)
				end
			end
		end

	r_subsector (num: INTEGER_32)
			-- Determine floor/ceiling planes.
			-- Add sprites of things in sector.
			-- Draw one or more line segments.
		require
				i_main.P_setup.subsectors.valid_index (num)
		local
			count: INTEGER_32
			line: INTEGER_32
			sub: SUBSECTOR_T
		do
			i_main.R_main.sscount := i_main.R_main.sscount + 1
			sub := i_main.P_setup.subsectors [num]
			check
					attached sub.sector as ss
			then
				frontsector := ss
			end
			count := sub.numlines.to_integer_32
			line := sub.firstline.to_integer_32
			if frontsector.floorheight < i_main.R_main.viewz then
				i_main.R_plane.floorplane := i_main.R_plane.r_findplane (frontsector.floorheight, frontsector.floorpic.to_integer_32, frontsector.lightlevel.to_integer_32)
			else
				i_main.R_plane.floorplane := Void
			end
			if frontsector.ceilingheight > i_main.R_main.viewz or frontsector.ceilingpic.to_integer_32 = i_main.R_sky.skyflatnum then
				i_main.R_plane.ceilingplane := i_main.R_plane.r_findplane (frontsector.ceilingheight, frontsector.ceilingpic.to_integer_32, frontsector.lightlevel.to_integer_32)
			else
				i_main.R_plane.ceilingplane := Void
			end
			i_main.R_things.r_addsprites (frontsector)
			from
			until
				count = 0
			loop
				count := count - 1
				r_addline (i_main.P_setup.segs [line])
				line := line + 1
			end
		end

	r_addline (line: SEG_T)
			-- Clips the given segment
			-- and adds any visible pieces to the line list.
		local
			x1: INTEGER_32
			x2: INTEGER_32
			angle1: ANGLE_T
			angle2: ANGLE_T
			span: ANGLE_T
			tspan: ANGLE_T
			returned: BOOLEAN
			goto_clipsolid: BOOLEAN
			goto_clippass: BOOLEAN
			bs: detachable SECTOR_T
		do
			curline := line
			angle1 := i_main.R_main.r_pointtoangle (line.v1.x, line.v1.y)
			angle2 := i_main.R_main.r_pointtoangle (line.v2.x, line.v2.y)
			span := angle1 - angle2
			if span >= {R_MAIN}.ang180 then
			else
				i_main.R_segs.rw_angle1 := angle1
				angle1 := angle1 - i_main.R_main.viewangle
				angle2 := angle2 - i_main.R_main.viewangle
				tspan := angle1 + i_main.R_main.clipangle
				if tspan > create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle then
					tspan := tspan - create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle
					if tspan >= span then
						returned := True
					else
						angle1 := i_main.R_main.clipangle
					end
				end
				if not returned then
					tspan := i_main.R_main.clipangle - angle2
					if tspan > create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle then
						tspan := tspan - create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle
						if tspan >= span then
							returned := True
						else
							angle2 := - i_main.R_main.clipangle
						end
					end
				end
				if not returned then
					angle1 := (angle1 + {R_MAIN}.ang90) |>> {R_MAIN}.angletofineshift
					angle2 := (angle2 + {R_MAIN}.ang90) |>> {R_MAIN}.angletofineshift
					x1 := i_main.R_main.viewangletox [angle1.as_integer_32]
					x2 := i_main.R_main.viewangletox [angle2.as_integer_32]
					if x1 = x2 then
						returned := True
					end
				end
				if not returned then
					backsector := line.backsector
					bs := backsector
					if bs = Void then
						goto_clipsolid := True
					elseif bs.ceilingheight <= frontsector.floorheight or bs.floorheight >= frontsector.ceilingheight then
						goto_clipsolid := True
					elseif bs.ceilingheight /= frontsector.ceilingheight or bs.floorheight /= frontsector.floorheight then
						goto_clippass := True
					elseif bs.ceilingpic = frontsector.ceilingpic and bs.floorpic = frontsector.floorpic and bs.lightlevel = frontsector.lightlevel and curline.sidedef.midtexture = 0 then
						returned := True
					end
				end
				if not returned then
					if not goto_clipsolid then
						r_clippasswallsegment (x1, x2 - 1)
					else
						r_clipsolidwallsegment (x1, x2 - 1)
					end
				end
			end
		end

	r_clippasswallsegment (first, last: INTEGER_32)
			-- Clips the given range of columns,
			-- but does not includes it in the clip list.
			-- Does handle windows,
			-- e.g. LineDefs with upper and lower texture.
		local
			start: INTEGER_32
			returned: BOOLEAN
		do
			start := solidsegs.lower
			from
			until
				solidsegs [start].last >= first - 1
			loop
				start := start + 1
			end
			if first < solidsegs [start].first then
				if last < solidsegs [start].first - 1 then
					i_main.R_segs.r_storewallrange (first, last)
					returned := True
				else
					i_main.R_segs.r_storewallrange (first, solidsegs [start].first - 1)
				end
			end
			if not returned then
				if last <= solidsegs [start].last then
					returned := True
				end
			end
			if not returned then
				from
				until
					returned or last < solidsegs [start + 1].first - 1
				loop
					i_main.R_segs.r_storewallrange (solidsegs [start].last + 1, solidsegs [start + 1].first - 1)
					start := start + 1
					if last <= solidsegs [start].last then
						returned := True
					end
				end
			end
			if not returned then
				i_main.R_segs.r_storewallrange (solidsegs [start].last + 1, last)
			end
		end

	r_clipsolidwallsegment (first, last: INTEGER_32)
			-- Does handle solid walls ,
			-- e.g. single sided LineDefs (middle texture)
			-- that entirely block the view.
		local
			next: INTEGER_32
			start: INTEGER_32
			done: BOOLEAN
			goto_crunch: BOOLEAN
		do
			from
				start := solidsegs.lower
			until
				solidsegs [start].last >= first - 1
			loop
				start := start + 1
			end
			if first < solidsegs [start].first then
				if last < solidsegs [start].first - 1 then
					i_main.R_segs.r_storewallrange (first, last)
					next := newend
					newend := newend + 1
					from
					until
						next = start
					loop
						solidsegs [next] := solidsegs [next - 1].twin
						next := next - 1
					end
					solidsegs [next].first := first
					solidsegs [next].last := last
					done := True
				else
					i_main.R_segs.r_storewallrange (first, solidsegs [start].first - 1)
					solidsegs [start].first := first
				end
			end
			if not done then
				if last <= solidsegs [start].last then
					done := True
				end
			end
			if not done then
				next := start
				from
				until
					goto_crunch or last < solidsegs [next + 1].first - 1
				loop
					i_main.R_segs.r_storewallrange (solidsegs [next].last + 1, solidsegs [next + 1].first - 1)
					next := next + 1
					if last <= solidsegs [next].last then
						solidsegs [start].last := solidsegs [next].last
						goto_crunch := True
					end
				end
			end
			if not done and not goto_crunch then
				i_main.R_segs.r_storewallrange (solidsegs [next].last + 1, last)
				solidsegs [start].last := last
			end
			if not done then
				if next = start then
					done := True
				end
			end
			if not done then
				from
				until
					next = newend
				loop
					next := next + 1
					start := start + 1
					solidsegs [start] := solidsegs [next].twin
				end
				newend := start + 1
			end
		end
	
feature -- R_CheckBBox

	Checkcoord: ARRAY [ARRAY [INTEGER_32]]
		once
			create Result.make_filled (create {ARRAY [INTEGER_32]}.make_empty, 0, 11)
			Result [0] := <<3, 0, 2, 1>>
			Result [1] := <<3, 0, 2, 0>>
			Result [2] := <<3, 1, 2, 0>>
			Result [3] := <<0, 0, 0, 0>>
			Result [4] := <<2, 0, 2, 1>>
			Result [5] := <<0, 0, 0, 0>>
			Result [6] := <<3, 1, 3, 0>>
			Result [7] := <<0, 0, 0, 0>>
			Result [8] := <<2, 0, 3, 1>>
			Result [9] := <<2, 1, 3, 1>>
			Result [10] := <<2, 1, 3, 0>>
			Result [11] := <<0, 0, 0, 0>>
		ensure
				Result.lower = 0
				Result.count = 12
				across
					Result as r
				all
					r.item.lower = 1 and r.item.count = 4
				end
		end

	r_checkbbox (bspcoord: ARRAY [FIXED_T]): BOOLEAN
		require
				bspcoord.valid_index ({M_BBOX}.boxleft)
				bspcoord.valid_index ({M_BBOX}.boxright)
				bspcoord.valid_index ({M_BBOX}.boxtop)
				bspcoord.valid_index ({M_BBOX}.boxbottom)
		local
			boxx: INTEGER_32
			boxy: INTEGER_32
			boxpos: INTEGER_32
			x1, y1: FIXED_T
			x2, y2: FIXED_T
			angle1, angle2: ANGLE_T
			span, tspan: ANGLE_T
			start: INTEGER_32
			sx1, sx2: INTEGER_32
			returned: BOOLEAN
		do
			if i_main.R_main.viewx <= bspcoord [{M_BBOX}.boxleft] then
				boxx := 0
			elseif i_main.R_main.viewx < bspcoord [{M_BBOX}.boxright] then
				boxx := 1
			else
				boxx := 2
			end
			if i_main.R_main.viewy >= bspcoord [{M_BBOX}.boxtop] then
				boxy := 0
			elseif i_main.R_main.viewy > bspcoord [{M_BBOX}.boxbottom] then
				boxy := 1
			else
				boxy := 2
			end
			boxpos := (boxy |<< 2) + boxx
			if boxpos = 5 then
				Result := True
			else
				x1 := bspcoord [Checkcoord [boxpos] [1]]
				y1 := bspcoord [Checkcoord [boxpos] [2]]
				x2 := bspcoord [Checkcoord [boxpos] [3]]
				y2 := bspcoord [Checkcoord [boxpos] [4]]
				angle1 := i_main.R_main.r_pointtoangle (x1, y1) - i_main.R_main.viewangle
				angle2 := i_main.R_main.r_pointtoangle (x2, y2) - i_main.R_main.viewangle
				span := angle1 - angle2
				if span >= {R_MAIN}.ang180 then
					Result := True
				else
					tspan := angle1 + i_main.R_main.clipangle
					if tspan > create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle then
						tspan := tspan - create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle
						if tspan >= span then
							Result := False
							returned := True
						else
							angle1 := i_main.R_main.clipangle
						end
					end
					if not returned then
						tspan := i_main.R_main.clipangle - angle2
						if tspan > create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle then
							tspan := tspan - create {ANGLE_T}.from_natural ((2).as_natural_32) * i_main.R_main.clipangle
							if tspan >= span then
								Result := False
								returned := True
							else
								angle2 := - i_main.R_main.clipangle
							end
						end
					end
					if not returned then
						angle1 := (angle1 + {R_MAIN}.ang90) |>> {R_MAIN}.angletofineshift
						angle2 := (angle2 + {R_MAIN}.ang90) |>> {R_MAIN}.angletofineshift
						sx1 := i_main.R_main.viewangletox [angle1.as_integer_32]
						sx2 := i_main.R_main.viewangletox [angle2.as_integer_32]
						if sx1 = sx2 then
							Result := False
							returned := True
						end
						if not returned then
							sx2 := sx2 - 1
							start := 0
							from
							until
								solidsegs [start].last >= sx2
							loop
								start := start + 1
							end
							if sx1 >= solidsegs [start].first and sx2 <= solidsegs [start].last then
								Result := False
							else
								Result := True
							end
						end
					end
				end
			end
		end
	
invariant
		solidsegs.count = Maxsegs

end -- class R_BSP

Generated by ISE EiffelStudio