rscad_csg_bsp/

bsp.rs

use crate::*;
pub struct BspNode<T: Number> {
    plane: Option<Plane<T, 3>>,
    front: Option<Box<BspNode<T>>>,
    back: Option<Box<BspNode<T>>>,
    polygons: Vec<Polygon<T, 3>>,
}

impl<T: Number> Default for BspNode<T> {
    fn default() -> Self {
        Self {
            plane: None,
            front: None,
            back: None,
            polygons: Vec::new(),
        }
    }
}

impl<T: Number> BspNode<T> {
    fn pick_splitting_plane(polygons: &[Polygon<T, 3>]) -> (usize, Vec<PolygonClassification>) {
        let len = polygons.len();
        if len <= 1 {
            let classes = polygons
                .iter()
                .map(|_| PolygonClassification::Coplanar)
                .collect();
            return (0, classes);
        }

        // Evaluate candidate splitting planes. For small sets test every
        // polygon; for larger sets, sample sqrt(n) evenly-spaced candidates
        // (clamped to 16..64). Each candidate is scored against ALL polygons
        // — the O(candidates × n) cost is negligible compared to the downstream
        // polygon splitting, and accuracy here directly reduces cascading splits.
        let num_candidates = if len <= 48 {
            len
        } else {
            ((len as f64).sqrt().ceil() as usize).clamp(16, 64)
        };
        let cand_step = if num_candidates >= len {
            1
        } else {
            len / num_candidates
        };

        let mut best_idx = 0;
        let mut best_score = i64::MAX;
        // Reuse a single buffer for classifications; swap into best on improvement.
        let mut classes = Vec::with_capacity(len);
        let mut best_classes = Vec::with_capacity(len);

        for c in 0..num_candidates {
            let idx = c * cand_step;
            let plane = polygons[idx].plane();
            let mut front = 0i64;
            let mut back = 0i64;
            let mut spanning = 0i64;
            let mut coplanar = 0i64;

            classes.clear();
            classes.extend(polygons.iter().map(|p| {
                let cl = plane.classify_polygon(p);
                match cl {
                    PolygonClassification::Front => front += 1,
                    PolygonClassification::Back => back += 1,
                    PolygonClassification::Spanning => spanning += 1,
                    PolygonClassification::Coplanar => coplanar += 1,
                }
                cl
            }));

            // Each spanning polygon becomes two fragments that cascade through
            // the tree — penalize heavily (×16). Lightly penalize imbalance to
            // prefer shallower trees. Reward coplanar polygons: they stay at
            // this node and shrink both subtrees.
            let imbalance = if front > back {
                front - back
            } else {
                back - front
            };
            let score = spanning * 16 + imbalance - coplanar * 2;

            if score < best_score {
                best_score = score;
                best_idx = idx;
                core::mem::swap(&mut classes, &mut best_classes);
            }
        }

        (best_idx, best_classes)
    }

    pub fn build(polygons: Vec<Polygon<T, 3>>) -> Self {
        if polygons.is_empty() {
            return Self::default();
        }

        let (split_idx, classes) = Self::pick_splitting_plane(&polygons);
        let plane = polygons[split_idx].plane();

        let mut node = Self {
            plane: Some(plane),
            front: None,
            back: None,
            polygons: Vec::new(),
        };

        let mut front_polygons = Vec::new();
        let mut back_polygons = Vec::new();

        for (polygon, class) in polygons.into_iter().zip(classes) {
            match class {
                PolygonClassification::Coplanar => node.polygons.push(polygon),
                PolygonClassification::Front => front_polygons.push(polygon),
                PolygonClassification::Back => back_polygons.push(polygon),
                PolygonClassification::Spanning => {
                    let (front, back) = plane.split_polygon(polygon);
                    front_polygons.push(front);
                    back_polygons.push(back);
                }
            }
        }

        if !front_polygons.is_empty() {
            node.front = Some(Box::new(Self::build(front_polygons)));
        }
        if !back_polygons.is_empty() {
            node.back = Some(Box::new(Self::build(back_polygons)));
        }

        node
    }

    pub fn clip_polygons(&self, polygons: Vec<Polygon<T, 3>>) -> Vec<Polygon<T, 3>> {
        let mut out = Vec::new();
        self.clip_polygons_into(polygons, &mut out);
        out
    }

    fn clip_polygons_into(&self, polygons: Vec<Polygon<T, 3>>, out: &mut Vec<Polygon<T, 3>>) {
        let Some(plane) = self.plane else {
            out.extend(polygons);
            return;
        };

        let mut front = Vec::new();
        let mut back = Vec::new();

        for polygon in polygons {
            match plane.classify_polygon(&polygon) {
                PolygonClassification::Front => front.push(polygon),
                PolygonClassification::Back => back.push(polygon),
                PolygonClassification::Coplanar => {
                    let dot = plane.normal().dot(&polygon.plane().normal());
                    if dot > T::zero() {
                        front.push(polygon);
                    } else {
                        back.push(polygon);
                    }
                }
                PolygonClassification::Spanning => {
                    let (f, b) = plane.split_polygon(polygon);
                    front.push(f);
                    back.push(b);
                }
            }
        }

        match &self.front {
            Some(f) => f.clip_polygons_into(front, out),
            None => out.extend(front),
        };

        if let Some(b) = &self.back {
            b.clip_polygons_into(back, out);
        }
        // else: back polygons clipped away
    }

    pub fn clip_to(&mut self, other: &BspNode<T>) {
        let taken = core::mem::take(&mut self.polygons);
        self.polygons = other.clip_polygons(taken);
        if let Some(ref mut front) = self.front {
            front.clip_to(other);
        }
        if let Some(ref mut back) = self.back {
            back.clip_to(other);
        }
    }

    pub fn invert(&mut self) {
        for polygon in &mut self.polygons {
            polygon.flip_in_place();
        }
        if let Some(ref mut plane) = self.plane {
            *plane = plane.flip();
        }
        core::mem::swap(&mut self.front, &mut self.back);
        if let Some(ref mut front) = self.front {
            front.invert();
        }
        if let Some(ref mut back) = self.back {
            back.invert();
        }
    }

    pub fn polygons(&self) -> Vec<Polygon<T, 3>> {
        let mut result = Vec::new();
        self.collect_polygons_into(&mut result);
        result
    }

    fn collect_polygons_into(&self, out: &mut Vec<Polygon<T, 3>>) {
        out.extend(self.polygons.iter().cloned());
        if let Some(ref front) = self.front {
            front.collect_polygons_into(out);
        }
        if let Some(ref back) = self.back {
            back.collect_polygons_into(out);
        }
    }

    pub fn build_into(&mut self, polygons: Vec<Polygon<T, 3>>) {
        let mut front_polygons = Vec::new();
        let mut back_polygons = Vec::new();

        for polygon in polygons {
            let Some(plane) = self.plane else {
                self.plane = Some(polygon.plane());
                self.polygons.push(polygon);
                continue;
            };
            match plane.classify_polygon(&polygon) {
                PolygonClassification::Coplanar => self.polygons.push(polygon),
                PolygonClassification::Front => front_polygons.push(polygon),
                PolygonClassification::Back => back_polygons.push(polygon),
                PolygonClassification::Spanning => {
                    let (front, back) = plane.split_polygon(polygon);
                    front_polygons.push(front);
                    back_polygons.push(back);
                }
            }
        }

        if !front_polygons.is_empty() {
            match &mut self.front {
                Some(f) => f.build_into(front_polygons),
                None => self.front = Some(Box::new(Self::build(front_polygons))),
            }
        }
        if !back_polygons.is_empty() {
            match &mut self.back {
                Some(b) => b.build_into(back_polygons),
                None => self.back = Some(Box::new(Self::build(back_polygons))),
            }
        }
    }
}