ref: 27c69fd7f524572d195bb09613931cffecff56f0
parent: 6aaf1cc828f8aec18649c0ff89b3d32bf00367e4
author: Andrew Apted <ajapted@gmail.com>
date: Sat Dec 9 07:17:45 EST 2023
worked on BSP_ComputeIntersection(), handle axis-aligned partitions.
--- a/nano_bsp.c
+++ b/nano_bsp.c
@@ -385,6 +385,75 @@
//----------------------------------------------------------------------------
+fixed_t BSP_VertIntersection (fixed_t part_x, seg_t * seg)
+{+ // horizontal seg?
+ if (seg->v1->y == seg->v2->y)
+ return seg->v1->y;
+
+ fixed_t a = abs (seg->v1->x - part_x);
+ fixed_t b = abs (seg->v2->x - part_x);
+
+ fixed_t along = FixedDiv (a, a + b);
+
+ return seg->v1->y + FixedMul (seg->v2->y - seg->v1->y, along);
+}
+
+
+fixed_t BSP_HorizIntersection (fixed_t part_y, seg_t * seg)
+{+ // vertical seg?
+ if (seg->v1->x == seg->v2->x)
+ return seg->v1->x;
+
+ fixed_t a = abs (seg->v1->y - part_y);
+ fixed_t b = abs (seg->v2->y - part_y);
+
+ fixed_t along = FixedDiv (a, a + b);
+
+ return seg->v1->x + FixedMul (seg->v2->x - seg->v1->x, along);
+}
+
+
+void BSP_ComputeIntersection (seg_t * part, seg_t * seg, fixed_t * x, fixed_t * y)
+{+ // vertical partition?
+ if (part->v1->x == part->v2->x)
+ {+ *x = part->v1->x;
+ *y = BSP_VertIntersection (*x, seg);
+ return;
+ }
+
+ // horizontal partition?
+ if (part->v1->y == part->v2->y)
+ {+ *y = part->v1->y;
+ *x = BSP_HorizIntersection (*y, seg);
+ return;
+ }
+
+ // TODO
+/*
+ double perp1 = PerpDist (E->x1, E->y1, part->x1, part->y1, part->x2, part->y2);
+ double perp2 = PerpDist (E->x2, E->y2, part->x1, part->y1, part->x2, part->y2);
+
+ // 0 = start, 1 = end
+ double ds = perp1 / (perp1 - perp2);
+
+ if (E->x1 == E->x2)
+ *x = E->x1;
+ else
+ *x = E->x1 + (E->x2 - E->x1) * ds;
+
+ if (E->y1 == E->y2)
+ *y = E->y1;
+ else
+ *y = E->y1 + (E->y2 - E->y1) * ds;
+*/
+}
+
+
//
// For segs not intersecting the partition, just move them into the
// correct output list (`lefts` or `rights`). otherwise split the seg
@@ -392,7 +461,34 @@
//
void BSP_SplitSegs (seg_t * part, seg_t * soup, seg_t ** lefts, seg_t ** rights)
{- // TODO
+ while (soup != NULL)
+ {+ seg_t * S = soup;
+ soup = soup->next;
+
+ int where = BSP_SegOnSide (part, S);
+
+ if (where < 0)
+ {+ S->next = (*lefts);
+ (*lefts) = S;
+ continue;
+ }
+
+ if (where > 0)
+ {+ S->next = (*rights);
+ (*rights) = S;
+ continue;
+ }
+
+ // we must split this seg
+ fixed_t ix, iy;
+
+ BSP_ComputeIntersection (part, S, &ix, &iy);
+
+ // TODO
+ }
}
nnode_t * BSP_SubdivideSegs (seg_t * soup)
--
⑨