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