Struct BspTree 

pub struct BspTree { /* private fields */ }

A Binary Space Partitioning tree for 3D polygons.

BSP trees recursively partition space using planes, enabling efficient spatial queries and ordered traversal. Each node contains polygons that are coplanar with its splitting plane, while non-coplanar polygons are stored in front or back subtrees.

Construction

Trees are built from a collection of polygons using a PlaneSelector to choose splitting planes:

use bsp_tree::{BspTree, Polygon, FirstPolygon};

let polygons: Vec<Polygon> = /* ... */;
let tree = BspTree::build(polygons, &FirstPolygon);

Traversal

The tree supports front-to-back and back-to-front traversal relative to a viewpoint, useful for painter’s algorithm rendering:

tree.traverse_back_to_front(eye_position, &mut visitor);
tree.traverse_front_to_back(eye_position, &mut visitor);

Implementations

impl BspTree

pub fn new() -> Self

Creates an empty BSP tree.

pub fn build<S: PlaneSelector>(polygons: Vec<Polygon>, selector: &S) -> Self

Builds a BSP tree from a collection of polygons.

Uses the provided PlaneSelector to choose splitting planes during construction. Polygons that span a splitting plane are automatically split using the Cuttable trait.

Returns an empty tree if the input is empty.

pub fn from_polygons(polygons: Vec<Polygon>) -> Self

Builds a BSP tree using the default plane selector ([FirstPolygon]).

pub fn is_empty(&self) -> bool

Returns true if the tree contains no polygons.

pub fn root(&self) -> Option<&BspNode>

Returns a reference to the root node, if any.

pub fn root_mut(&mut self) -> Option<&mut BspNode>

Returns a mutable reference to the root node, if any.

This is primarily for future insert operations.

pub fn polygon_count(&self) -> usize

Returns the total number of polygons in the tree.

pub fn depth(&self) -> usize

Returns the maximum depth of the tree (0 for empty tree).

pub fn traverse_front_to_back<V: BspVisitor>( &self, eye: Point3<f32>, visitor: &mut V, )

Traverses the tree front-to-back relative to the given viewpoint.

Useful for early-Z occlusion culling in modern renderers with depth buffers, where drawing front objects first allows the GPU to reject occluded fragments.

The visitor’s visit method is called for each group of coplanar polygons, in front-to-back order (nearest first).

pub fn traverse_back_to_front<V: BspVisitor>( &self, eye: Point3<f32>, visitor: &mut V, )

Traverses the tree back-to-front relative to the given viewpoint.

This is the classic painter’s algorithm ordering: far polygons are visited first, then closer polygons, so they can be drawn on top. Also useful for correct alpha blending of transparent surfaces.

pub fn collect_polygons(&self) -> Vec<Polygon>

Collects all polygons in the tree into a vector.

The order of polygons is not guaranteed.

Trait Implementations

impl Clone for BspTree

fn clone(&self) -> BspTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BspTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BspTree

fn default() -> BspTree

Returns the “default value” for a type.