shithub: nanobsp

Download patch

ref: cc2d1303a4e49882bf961779e06e53297b67467e
parent: fabfd02b9487fadcc21b1dc46585a52aac2987d4
author: Andrew Apted <ajapted@gmail.com>
date: Fri Dec 8 20:23:40 EST 2023 

finished BSP_PickNode_Fast() and BSP_PickNode_Slow() funcs.


--- a/nano_bsp.c
+++ b/nano_bsp.c
@@ -161,6 +161,7 @@
 
 	if (dx == 0)
 	{
+		// FIXME: review these
 		if (x < part->v1->x - DIST_EPSILON)
 			return (dy > 0) ? +1 : -1;
 
@@ -240,28 +241,51 @@
 }
 
 //
-// Look for an axis-aligned seg which can divide the other segs in a
-// "nice" way.  returns NULL if none found.
+// Look for an axis-aligned seg which can divide the other segs
+// in a "nice" way.  returns NULL if none found.
 //
 seg_t * BSP_PickNode_Fast (seg_t * soup)
 {
+	// determine bounds of segs
+	fixed_t bbox[4];
+
+	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);
+	}
+
+	fixed_t mid_x = bbox[BOXLEFT]   / 2 + bbox[BOXRIGHT] / 2;
+	fixed_t mid_y = bbox[BOXBOTTOM] / 2 + bbox[BOXTOP]   / 2;
+
 	seg_t * part;
-	seg_t * best   = NULL;
-	int best_score = -1;
+	seg_t * best = NULL;
+	fixed_t best_score = -1;
 
 	for (part = soup ; part != NULL ; part = part->next)
 	{
+		boolean vert  = (part->v1->x == part->v2->x);
+		boolean horiz = (part->v1->y == part->v2->y);
+
+		if (! (vert || horiz))
+			continue;
+
+		fixed_t score = abs (vert ? (part->v1->x - mid_x) : (part->v1->y - mid_y));
+
+		if (score > best_score)
+		{
 			struct NodeEval eval;
 
 			if (BSP_EvalPartition (part, soup, &eval))
 			{
-				int score = 500000 - abs (eval.left - eval.right) * 100 - eval.split;
-
-				if (score > best_score)
-				{
-					best = part;
-					best_score = score;
-				}
+				best = part;
+				best_score = score;
 			}
 		}
 	}
@@ -286,7 +310,7 @@
 
 		if (BSP_EvalPartition (part, soup, &eval))
 		{
-			int cost = abs (eval.left - eval.right)
+			int cost = abs (eval.left - eval.right) * 100 + eval.split * 17;
 
 			if (cost < best_cost)
 			{
-- 
⑨