ref: fabfd02b9487fadcc21b1dc46585a52aac2987d4
parent: d8c7c055604b45a5d883f7d32e49e11487dca7ae
author: Andrew Apted <ajapted@gmail.com>
date: Fri Dec 8 20:03:59 EST 2023
worked on EvalPartition and PickNode funcs.
--- a/nano_bsp.c
+++ b/nano_bsp.c
@@ -41,7 +41,7 @@
#undef MIN
#define MIN(a, b) ((a) < (b) ? (a) : (b))
-// #define DIST_EPSILON (1.0 / 256.0)
+#define DIST_EPSILON (FRACUNIT / 64)
// TODO: probably make these global
@@ -154,6 +154,58 @@
int left, right, split;
};
+int BSP_PointOnSide (seg_t * part, fixed_t x, fixed_t y)
+{+ fixed_t dx = part->v2->x - part->v1->x;
+ fixed_t dy = part->v2->y - part->v1->y;
+
+ if (dx == 0)
+ {+ if (x < part->v1->x - DIST_EPSILON)
+ return (dy > 0) ? +1 : -1;
+
+ if (x > part->v1->x + DIST_EPSILON)
+ return (dy > 0) ? +1 : -1;
+
+ return 0;
+ }
+
+ if (dy == 0)
+ {+ if (y < part->v1->y - DIST_EPSILON)
+ return (dx > 0) ? +1 : -1;
+
+ if (y > part->v1->y + DIST_EPSILON)
+ return (dx > 0) ? +1 : -1;
+
+ return 0;
+ }
+
+ // TODO !!
+
+ return 0;
+}
+
+int BSP_SegOnSide (seg_t * part, seg_t * seg)
+{+ int side1 = BSP_PointOnSide (part, seg->v1->x, seg->v1->y);
+ int side2 = BSP_PointOnSide (part, seg->v2->x, seg->v2->y);
+
+ if (side1 == 0 && side2 == 0)
+ {+ // FIXME
+ boolean on_right = false;
+
+ return on_right ? +1 : -1;
+ }
+
+ // splits the seg?
+ if ((side1 *= side2) < 0)
+ return 0;
+
+ return (side1 >= 0 && side2 >= 0) ? +1 : -1;
+}
+
//
// Evaluate a seg as a partition candidate, storing the results in `eval`.
// returns true if the partition is viable, false otherwise.
@@ -160,9 +212,31 @@
//
boolean BSP_EvalPartition (seg_t * part, seg_t * soup, struct NodeEval * eval)
{- // TODO
+ eval->left = 0;
+ eval->right = 0;
+ eval->split = 0;
- return false;
+ seg_t * S;
+ for (S = soup ; S != NULL ; S = S->next)
+ {+ if (S == part)
+ continue;
+
+ switch (BSP_SegOnSide (part, S))
+ {+ case 0: eval->split += 1; break;
+ case -1: eval->left += 1; break;
+ case +1: eval->right += 1; break;
+ }
+ }
+
+ // a viable partition either splits something, or has other segs
+ // lying on both the left and right sides.
+
+ if (eval->split == 0 && (eval->left == 0 || eval->right == 0))
+ return false;
+
+ return true;
}
//
@@ -171,8 +245,28 @@
//
seg_t * BSP_PickNode_Fast (seg_t * soup)
{- // TODO
- return NULL;
+ seg_t * part;
+ seg_t * best = NULL;
+ int best_score = -1;
+
+ for (part = soup ; part != NULL ; part = part->next)
+ {+ 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;
+ }
+ }
+ }
+ }
+
+ return best;
}
//
@@ -182,8 +276,27 @@
//
seg_t * BSP_PickNode_Slow (seg_t * soup)
{- // TODO
- return NULL;
+ seg_t * part;
+ seg_t * best = NULL;
+ int best_cost = (1 << 30);
+
+ for (part = soup ; part != NULL ; part = part->next)
+ {+ struct NodeEval eval;
+
+ if (BSP_EvalPartition (part, soup, &eval))
+ {+ int cost = abs (eval.left - eval.right)
+
+ if (cost < best_cost)
+ {+ best = part;
+ best_cost = cost;
+ }
+ }
+ }
+
+ return best;
}
//----------------------------------------------------------------------------
--
⑨