shithub: nanobsp

Download patch

ref: 3df8a2a60275255339785dfc0b874a5c38be595f
parent: 7596c0ec610b22d95cc12737133a1e20c8f5d805
author: Andrew Apted <ajapted@gmail.com>
date: Sat Dec 9 12:10:36 EST 2023 

determine bounding box of each `node_t`, check in rendering code.


--- a/nano_bsp.c
+++ b/nano_bsp.c
@@ -88,6 +88,32 @@
 	seg->offset = R_PointToDist (seg->v1->x, seg->v1->y);
 }
 
+void BSP_BoundingBox (seg_t * soup, fixed_t * bbox)
+{
+	bbox[BOXLEFT]   = INT_MAX;
+	bbox[BOXBOTTOM] = INT_MAX;
+	bbox[BOXRIGHT]  = INT_MIN;
+	bbox[BOXTOP]    = INT_MIN;
+
+	seg_t * S;
+	for (S = soup ; S != NULL ; S = S->next)
+	{
+		M_AddToBox (bbox, S->v1->x, S->v1->y);
+		M_AddToBox (bbox, S->v2->x, S->v2->y);
+	}
+}
+
+void BSP_MergeBounds (node_t * node)
+{
+	fixed_t * L_bbox = node->left ->bbox;
+	fixed_t * R_bbox = node->right->bbox;
+
+	node->bbox[BOXLEFT  ] = MIN (L_bbox[BOXLEFT  ], R_bbox[BOXLEFT  ]);
+	node->bbox[BOXBOTTOM] = MIN (L_bbox[BOXBOTTOM], R_bbox[BOXBOTTOM]);
+	node->bbox[BOXRIGHT ] = MAX (L_bbox[BOXRIGHT ], R_bbox[BOXRIGHT ]);
+	node->bbox[BOXTOP   ] = MAX (L_bbox[BOXTOP   ], R_bbox[BOXTOP   ]);
+}
+
 void BSP_SegForLineSide (int i, int side, seg_t ** list_var)
 {
 	line_t * ld = &lines[i];
@@ -142,6 +168,8 @@
 	sub->sector = soup->frontsector;
 
 	node->sub = sub;
+	BSP_BoundingBox (soup, node->bbox);
+
 	return node;
 }
 
@@ -243,21 +271,6 @@
 	return (side1 >= 0 && side2 >= 0) ? +1 : -1;
 }
 
-void BSP_BoundingBox (seg_t * soup, fixed_t * bbox)
-{
-	bbox[BOXLEFT]   = INT_MAX;
-	bbox[BOXBOTTOM] = INT_MAX;
-	bbox[BOXRIGHT]  = INT_MIN;
-	bbox[BOXTOP]    = INT_MIN;
-
-	seg_t * S;
-	for (S = soup ; S != NULL ; S = S->next)
-	{
-		M_AddToBox (bbox, S->v1->x, S->v1->y);
-		M_AddToBox (bbox, S->v2->x, S->v2->y);
-	}
-}
-
 //
 // Evaluate a seg as a partition candidate, storing the results in `eval`.
 // returns true if the partition is viable, false otherwise.
@@ -588,6 +601,8 @@
 
 	N->right = BSP_SubdivideSegs (rights);
 	N->left  = BSP_SubdivideSegs (lefts);
+
+	BSP_MergeBounds (N);
 
 	return N;
 }
--- a/r_bsp.c
+++ b/r_bsp.c
@@ -549,7 +549,7 @@
 
     // Possibly divide back space.
     bsp = side ? bsp->right : bsp->left;
-    if (true) //FIXME  R_CheckBBox (bsp->bbox))
+    if (R_CheckBBox (bsp->bbox))
         goto loop;
 }
 
--- a/r_defs.h
+++ b/r_defs.h
@@ -262,6 +262,9 @@
     // partition line (start coord, delta to end)
     fixed_t  x, y, dx, dy;
 
+    // bounding box for this node / leaf
+    fixed_t  bbox[4];
+
     // right and left children
     struct node_s * right;
     struct node_s * left;
-- 
⑨