neurodoom 0.6.7

// BSP traversal on the hot path — see rationale in src/render/mod.rs.
#![allow(clippy::indexing_slicing)]

use crate::map::{MapData, NF_SUBSECTOR};
use crate::math::*;
use crate::texture::TextureData;

use super::{ClipRange, Renderer, MAXSEGS};

impl Renderer {
    /// Traverse the BSP tree front-to-back and render visible walls.
    pub fn render_bsp_node(&mut self, map: &MapData, textures: &TextureData, node_id: u16) {
        // Check if this is a subsector
        if node_id & NF_SUBSECTOR != 0 {
            let ssect_id = if node_id == 0xFFFF {
                0
            } else {
                (node_id & !NF_SUBSECTOR) as usize
            };
            self.render_subsector(map, textures, ssect_id);
            return;
        }

        let node = &map.nodes[node_id as usize];

        // Determine which side of the partition the viewer is on
        let side = point_on_side(self.view_x, self.view_y, node.x, node.y, node.dx, node.dy);

        // Render front child first (closer to viewer)
        self.render_bsp_node(map, textures, node.children[side]);

        // Check if back child's bounding box is visible
        let back = side ^ 1;
        if self.check_bbox(&node.bbox[back]) {
            self.render_bsp_node(map, textures, node.children[back]);
        }
    }

    /// Render a subsector: process all segs in it.
    fn render_subsector(&mut self, map: &MapData, textures: &TextureData, ssect_id: usize) {
        if ssect_id >= map.subsectors.len() {
            return;
        }
        let ss = &map.subsectors[ssect_id];

        // Set up floor and ceiling visplanes for this subsector
        let sector = &map.sectors[ss.sector as usize];
        let floor_height = sector.floor_height;
        let ceiling_height = sector.ceiling_height;
        let floor_pic = sector.floor_pic;
        let ceiling_pic = sector.ceiling_pic;
        let light_level = sector.light_level;

        if floor_height < self.view_z {
            let pl = self.find_plane(floor_height, floor_pic, light_level);
            self.cur_floor_plane = Some(pl);
        } else {
            self.cur_floor_plane = None;
        }

        if ceiling_height > self.view_z || ceiling_pic == self.sky_flat_num {
            let pl = self.find_plane(ceiling_height, ceiling_pic, light_level);
            self.cur_ceiling_plane = Some(pl);
        } else {
            self.cur_ceiling_plane = None;
        }

        for i in 0..ss.num_lines as usize {
            let seg_idx = ss.first_line as usize + i;
            if seg_idx < map.segs.len() {
                self.add_line(map, textures, seg_idx);
            }
        }
    }

    /// Process a seg: clip to screen, determine if solid or pass-through.
    fn add_line(&mut self, map: &MapData, textures: &TextureData, seg_idx: usize) {
        let seg = &map.segs[seg_idx];
        let v1 = &map.vertexes[seg.v1 as usize];
        let v2 = &map.vertexes[seg.v2 as usize];

        // Compute angles from viewer to seg endpoints
        let angle1 = point_to_angle_2(self.view_x, self.view_y, v1.x, v1.y);
        let angle2 = point_to_angle_2(self.view_x, self.view_y, v2.x, v2.y);

        // Backface culling
        let span = angle1.wrapping_sub(angle2);
        if span >= ANG180 {
            return;
        }

        let rw_angle1 = angle1;

        // Clip to view frustum
        let mut a1 = angle1.wrapping_sub(self.view_angle);
        let mut a2 = angle2.wrapping_sub(self.view_angle);
        let clip = self.clip_angle;
        let double_clip = clip.wrapping_mul(2);

        let tspan1 = a1.wrapping_add(clip);
        if tspan1 > double_clip {
            let excess = tspan1.wrapping_sub(double_clip);
            if excess >= span {
                return;
            }
            a1 = clip;
        }

        let tspan2 = clip.wrapping_sub(a2);
        if tspan2 > double_clip {
            let excess = tspan2.wrapping_sub(double_clip);
            if excess >= span {
                return;
            }
            a2 = 0u32.wrapping_sub(clip);
        }

        // Convert to screen X
        let fine1 = a1.wrapping_add(ANG90) >> ANGLETOFINESHIFT;
        let fine2 = a2.wrapping_add(ANG90) >> ANGLETOFINESHIFT;
        let x1 = self.viewangletox[fine1 as usize % (FINEANGLES / 2)];
        let x2 = self.viewangletox[fine2 as usize % (FINEANGLES / 2)];

        if x1 >= x2 {
            return;
        }

        if let Some(back_id) = seg.back_sector {
            let front = &map.sectors[seg.front_sector as usize];
            let back = &map.sectors[back_id as usize];

            // Check if effectively solid (closed door, matching heights)
            let is_solid = back.ceiling_height <= front.floor_height
                || back.floor_height >= front.ceiling_height;

            if is_solid {
                self.clip_solid_wall(map, textures, seg_idx, rw_angle1, x1, x2 - 1);
            } else {
                self.clip_pass_wall(map, textures, seg_idx, rw_angle1, x1, x2 - 1);
            }
        } else {
            // Solid (single-sided) wall
            self.clip_solid_wall(map, textures, seg_idx, rw_angle1, x1, x2 - 1);
        }
    }

    /// Clip and render a solid wall (fills solidsegs).
    fn clip_solid_wall(
        &mut self,
        map: &MapData,
        textures: &TextureData,
        seg_idx: usize,
        rw_angle1: Angle,
        first: i32,
        last: i32,
    ) {
        // Find first solidsegs entry that might overlap
        let mut start_idx = 0;
        while start_idx < self.solidsegs_end && self.solidsegs[start_idx].last < first - 1 {
            start_idx += 1;
        }

        if first < self.solidsegs[start_idx].first {
            if last < self.solidsegs[start_idx].first - 1 {
                // Completely visible — render and insert
                self.store_wall_range(map, textures, seg_idx, rw_angle1, first, last);
                // Insert new range
                if self.solidsegs_end < MAXSEGS {
                    let end = self.solidsegs_end;
                    let mut j = end;
                    while j > start_idx {
                        self.solidsegs[j] = self.solidsegs[j - 1];
                        j -= 1;
                    }
                    self.solidsegs[start_idx] = ClipRange { first, last };
                    self.solidsegs_end += 1;
                }
                return;
            }
            // Render visible fragment
            self.store_wall_range(
                map,
                textures,
                seg_idx,
                rw_angle1,
                first,
                self.solidsegs[start_idx].first - 1,
            );
            self.solidsegs[start_idx].first = first;
        }

        if last <= self.solidsegs[start_idx].last {
            return; // Fully clipped
        }

        // Process overlapping ranges
        let mut next_idx = start_idx;
        while next_idx + 1 < self.solidsegs_end
            && last >= self.solidsegs[next_idx + 1].first - 1
        {
            self.store_wall_range(
                map,
                textures,
                seg_idx,
                rw_angle1,
                self.solidsegs[next_idx].last + 1,
                self.solidsegs[next_idx + 1].first - 1,
            );
            next_idx += 1;
            if last <= self.solidsegs[next_idx].last {
                self.solidsegs[start_idx].last = self.solidsegs[next_idx].last;
                // Compact
                self.compact_solidsegs(start_idx, next_idx);
                return;
            }
        }

        // Fragment after last overlapping range
        self.store_wall_range(
            map,
            textures,
            seg_idx,
            rw_angle1,
            self.solidsegs[next_idx].last + 1,
            last,
        );
        self.solidsegs[start_idx].last = last;
        if next_idx != start_idx {
            self.compact_solidsegs(start_idx, next_idx);
        }
    }

    /// Clip and render a pass-through wall (does NOT fill solidsegs).
    fn clip_pass_wall(
        &mut self,
        map: &MapData,
        textures: &TextureData,
        seg_idx: usize,
        rw_angle1: Angle,
        first: i32,
        last: i32,
    ) {
        let mut start_idx = 0;
        while start_idx < self.solidsegs_end && self.solidsegs[start_idx].last < first - 1 {
            start_idx += 1;
        }

        if first < self.solidsegs[start_idx].first {
            if last < self.solidsegs[start_idx].first - 1 {
                self.store_wall_range(map, textures, seg_idx, rw_angle1, first, last);
                return;
            }
            self.store_wall_range(
                map,
                textures,
                seg_idx,
                rw_angle1,
                first,
                self.solidsegs[start_idx].first - 1,
            );
        }

        if last <= self.solidsegs[start_idx].last {
            return;
        }

        while start_idx + 1 < self.solidsegs_end
            && last >= self.solidsegs[start_idx + 1].first - 1
        {
            self.store_wall_range(
                map,
                textures,
                seg_idx,
                rw_angle1,
                self.solidsegs[start_idx].last + 1,
                self.solidsegs[start_idx + 1].first - 1,
            );
            start_idx += 1;
            if last <= self.solidsegs[start_idx].last {
                return;
            }
        }

        self.store_wall_range(
            map,
            textures,
            seg_idx,
            rw_angle1,
            self.solidsegs[start_idx].last + 1,
            last,
        );
    }

    /// Compact solidsegs after merging overlapping ranges.
    fn compact_solidsegs(&mut self, start: usize, next: usize) {
        if next == start {
            return;
        }
        let remove_count = next - start;
        let mut dst = start + 1;
        let mut src = next + 1;
        while src < self.solidsegs_end {
            self.solidsegs[dst] = self.solidsegs[src];
            dst += 1;
            src += 1;
        }
        self.solidsegs_end -= remove_count;
    }

    /// Check if a bounding box is potentially visible (Doom's R_CheckBBox).
    fn check_bbox(&self, bbox: &[Fixed; 4]) -> bool {
        // bbox: [top, bottom, left, right]
        // checkcoord[boxpos] selects which two corners to test based on
        // viewer position relative to the box (3x3 grid = 9 cases, center=inside)
        #[rustfmt::skip]
        static CHECKCOORD: [[usize; 4]; 12] = [
            [3,0,2,1], [3,0,2,0], [3,1,2,0],
            [0,0,0,0], [2,0,2,1], [0,0,0,0], [3,1,3,0],
            [0,0,0,0], [2,0,3,1], [2,1,3,1], [2,1,3,0],
            [0,0,0,0],
        ];

        let boxx = if self.view_x <= bbox[2] {
            0
        } else if self.view_x < bbox[3] {
            1
        } else {
            2
        };

        let boxy = if self.view_y >= bbox[0] {
            0
        } else if self.view_y > bbox[1] {
            1
        } else {
            2
        };

        let boxpos = (boxy << 2) + boxx;
        if boxpos == 5 {
            return true; // viewer inside box
        }

        let cc = &CHECKCOORD[boxpos];
        let x1 = bbox[cc[0]];
        let y1 = bbox[cc[1]];
        let x2 = bbox[cc[2]];
        let y2 = bbox[cc[3]];

        let angle1 = point_to_angle_2(self.view_x, self.view_y, x1, y1)
            .wrapping_sub(self.view_angle);
        let angle2 = point_to_angle_2(self.view_x, self.view_y, x2, y2)
            .wrapping_sub(self.view_angle);

        let span = angle1.wrapping_sub(angle2);
        if span >= ANG180 {
            return true;
        }

        let mut a1 = angle1;
        let mut a2 = angle2;
        let clip2 = self.clip_angle.wrapping_mul(2);

        let tspan = a1.wrapping_add(self.clip_angle);
        if tspan > clip2 {
            let excess = tspan.wrapping_sub(clip2);
            if excess >= span {
                return false;
            }
            a1 = self.clip_angle;
        }

        let tspan = self.clip_angle.wrapping_sub(a2);
        if tspan > clip2 {
            let excess = tspan.wrapping_sub(clip2);
            if excess >= span {
                return false;
            }
            a2 = 0u32.wrapping_sub(self.clip_angle);
        }

        // Convert to screen X and check against solidsegs
        let fine1 = a1.wrapping_add(ANG90) >> ANGLETOFINESHIFT;
        let fine2 = a2.wrapping_add(ANG90) >> ANGLETOFINESHIFT;
        let sx1 = self.viewangletox[fine1 as usize % (FINEANGLES / 2)];
        let sx2 = self.viewangletox[fine2 as usize % (FINEANGLES / 2)];

        if sx1 == sx2 {
            return false;
        }
        let sx2 = sx2 - 1;

        // Check if the range is fully covered by a single solidsegs entry
        for i in 0..self.solidsegs_end {
            if self.solidsegs[i].last >= sx2 {
                return !(sx1 >= self.solidsegs[i].first && sx2 <= self.solidsegs[i].last);
            }
        }

        true
    }
}

/// Determine which side of a partition line a point is on.
/// Returns 0 (front) or 1 (back).
#[inline]
pub fn point_on_side(
    x: Fixed,
    y: Fixed,
    node_x: Fixed,
    node_y: Fixed,
    node_dx: Fixed,
    node_dy: Fixed,
) -> usize {
    if node_dx == 0 {
        return if x <= node_x {
            if node_dy > 0 { 1 } else { 0 }
        } else if node_dy < 0 {
            1
        } else {
            0
        };
    }
    if node_dy == 0 {
        return if y <= node_y {
            if node_dx < 0 { 1 } else { 0 }
        } else if node_dx > 0 {
            1
        } else {
            0
        };
    }

    let dx = x - node_x;
    let dy = y - node_y;

    // Quick sign check
    if (node_dy ^ node_dx ^ dx ^ dy) & (1 << 31) != 0 {
        return if (node_dy ^ dx) & (1 << 31) != 0 { 1 } else { 0 };
    }

    let left = fixed_mul(node_dy >> FRACBITS, dx);
    let right = fixed_mul(dy, node_dx >> FRACBITS);

    if right < left { 0 } else { 1 }
}

/// Compute angle from (x1,y1) to (x2,y2).
pub fn point_to_angle_2(x1: Fixed, y1: Fixed, x2: Fixed, y2: Fixed) -> Angle {
    let dx = x2 - x1;
    let dy = y2 - y1;
    crate::map::point_to_angle(dx, dy)
}