From 27760ec1ca7a93877b2b015a0a2e9db87de4204c Mon Sep 17 00:00:00 2001
From: tcmal <me@aria.rip>
Date: Sun, 25 Aug 2024 17:44:21 +0100
Subject: feat(render): proper bsp tree walking

---
 stockton-render/src/culling.rs | 32 ++++++++++++++++++++++++++------
 1 file changed, 26 insertions(+), 6 deletions(-)

diff --git a/stockton-render/src/culling.rs b/stockton-render/src/culling.rs
index 7ae9958..8240701 100644
--- a/stockton-render/src/culling.rs
+++ b/stockton-render/src/culling.rs
@@ -17,26 +17,46 @@
 #![allow(dead_code)]
 
 use stockton_levels::prelude::*;
-use stockton_levels::traits::tree::BSPNodeValue;
+use stockton_levels::traits::tree::{BSPNode, BSPNodeValue};
 use stockton_types::Vector3;
 
 
 /// Get the visible faces according to visdata and frustum culling
 // TODO: Write this. For now, just render all faces
-pub fn get_visible_faces<X: CoordSystem, T: MinBSPFeatures<X>>(_pos: Vector3, file: &T) -> Vec<u32> {
-	let mut visible = Vec::with_capacity(file.faces_len() as usize);
-	for x in 0..file.faces_len() {
-		visible.push(x as u32);
+pub fn get_visible_faces<X: CoordSystem, T: MinBSPFeatures<X>>(pos: Vector3, file: &T) -> Vec<u32> {
+	let vis_cluster = get_cluster_id(pos, file);
+	
+	if (vis_cluster & 0x80000000) != 0 { // Negative = Invalid camera position
+		return vec![];
 	}
 
+	let mut visible = Vec::with_capacity(file.faces_len() as usize);
+	walk_bsp_tree(file.get_bsp_root(), vis_cluster, &mut visible, file);
+
 	return visible;
 }
 
+pub fn walk_bsp_tree<X: CoordSystem, T: MinBSPFeatures<X>>(node: &BSPNode, vis_cluster: u32, visible_faces: &mut Vec<u32>, file: &T) -> () {
+	if let BSPNodeValue::Children(front, back) = &node.value {
+		walk_bsp_tree(back, vis_cluster, visible_faces, file);
+		walk_bsp_tree(front, vis_cluster, visible_faces, file);
+	} else if let BSPNodeValue::Leaf(leaf) = &node.value {
+		if (leaf.cluster_id & 0x80000000) != 0 { // Negative means invalid leaf
+			return;
+		} else if file.cluster_visible_from(vis_cluster, leaf.cluster_id) {
+			for face_idx in leaf.faces_idx.iter() {
+				// TODO: Culling or something
+				visible_faces.push(*face_idx);
+			}
+		}
+	}
+}
+
 /// Get the viscluster pos lies in 
 fn get_cluster_id<X: CoordSystem, T: MinBSPFeatures<X>>(pos: Vector3, file: &T) -> u32 {
 	let mut node = file.get_bsp_root();
 	loop {
-		if let BSPNodeValue::Children(front, back) = &node.value{
+		if let BSPNodeValue::Children(front, back) = &node.value {
 			let plane = file.get_plane(node.plane_idx);
 			let dist = plane.normal.dot(&pos) - plane.dist;
 
-- 
cgit v1.2.3