ref: d75ec8b2381cd6f8e61bb8fbbad8ea41246fd8ee
dir: /nano_bsp.c/
//----------------------------------------------------------------------------
//
// Copyright (c) 2023 Andrew Apted
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
// SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
//----------------------------------------------------------------------------
#include "i_system.h"
#include <stdlib.h>
#include <assert.h>
#include "doomtype.h"
#include "doomstat.h"
#include "d_ticcmd.h"
#include "d_event.h"
#include "m_fixed.h"
#include "m_bbox.h"
#include "m_misc.h"
#include "m_random.h"
#include "z_zone.h"
#include "p_local.h"
#include "p_mobj.h"
#include "nano_bsp.h"
#define DIST_EPSILON (FRACUNIT / 64)
#define FAST_THRESHOLD 128
#undef MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#undef MIN
#define MIN(a, b) ((a) < (b) ? (a) : (b))
vertex_t * BSP_NewVertex (fixed_t x, fixed_t y)
{
vertex_t * vert = Z_Malloc(sizeof(vertex_t), PU_LEVEL, NULL);
vert->x = x;
vert->y = y;
return vert;
}
seg_t * BSP_NewSeg (void)
{
seg_t * seg = Z_Malloc (sizeof(seg_t), PU_LEVEL, NULL);
memset (seg, 0, sizeof(*seg));
return seg;
}
subsector_t * BSP_NewSubsector (void)
{
subsector_t * sub = Z_Malloc (sizeof(subsector_t), PU_LEVEL, NULL);
memset (sub, 0, sizeof(*sub));
return sub;
}
node_t * BSP_NewNode (void)
{
node_t * node = Z_Malloc (sizeof(node_t), PU_LEVEL, NULL);
memset (node, 0, sizeof(*node));
return node;
}
/* DEBUG:
void DumpNode (node_t * N, int lev)
{
char spaces[256];
if (lev > 100) lev = 100;
int i;
for (i = 0 ; i < lev*2 ; i++)
spaces[i] = ' ';
spaces[lev*2] = 0;
printf ("%snode %p\n", spaces, N);
printf ("%sbbox (%d %d) .. (%d %d)\n", spaces,
N->bbox[BOXLEFT] >> 16, N->bbox[BOXBOTTOM] >> 16,
N->bbox[BOXRIGHT] >> 16, N->bbox[BOXTOP] >> 16);
if (N->sub == NULL)
{
printf ("%spartition (%d %d) --> (%d %d)\n", spaces,
N->x >> 16, N->y >> 16,
(N->x + N->dx) >> 16, (N->y + N->dy) >> 16);
printf ("%sright\n", spaces);
printf ("%s{\n", spaces);
DumpNode (N->right, lev + 1);
printf ("%s}\n", spaces);
printf ("%sleft\n", spaces);
printf ("%s{\n", spaces);
DumpNode (N->left, lev + 1);
printf ("%s}\n", spaces);
}
else
{
subsector_t * sub = N->sub;
printf ("%ssector #%d\n", spaces, (int)(sub->sector - sectors));
seg_t * S;
for (S = sub->segs ; S != NULL ; S = S->next)
{
printf ("%s line #%d, side %d : (%d %d) --> (%d %d)\n", spaces,
(int) (S->linedef - lines), S->side,
S->v1->x >> 16, S->v1->y >> 16,
S->v2->x >> 16, S->v2->y >> 16);
}
}
}
*/
//----------------------------------------------------------------------------
void BSP_CalcOffset (seg_t * seg)
{
line_t * ld = seg->linedef;
viewx = seg->side ? ld->v2->x : ld->v1->x;
viewy = seg->side ? ld->v2->y : ld->v1->y;
seg->offset = R_PointToDist (seg->v1->x, seg->v1->y);
}
void BSP_BoundingBox (seg_t * soup, fixed_t * bbox)
{
// Note: not using M_AddToBox() here, because it is broken!
bbox[BOXLEFT ] = INT_MAX; bbox[BOXRIGHT ] = INT_MIN;
bbox[BOXBOTTOM] = INT_MAX; bbox[BOXTOP ] = INT_MIN;
seg_t * S;
for (S = soup ; S != NULL ; S = S->next)
{
bbox[BOXLEFT ] = MIN (bbox[BOXLEFT ], S->v1->x);
bbox[BOXLEFT ] = MIN (bbox[BOXLEFT ], S->v2->x);
bbox[BOXBOTTOM] = MIN (bbox[BOXBOTTOM], S->v1->y);
bbox[BOXBOTTOM] = MIN (bbox[BOXBOTTOM], S->v2->y);
bbox[BOXRIGHT ] = MAX (bbox[BOXRIGHT ], S->v1->x);
bbox[BOXRIGHT ] = MAX (bbox[BOXRIGHT ], S->v2->x);
bbox[BOXTOP ] = MAX (bbox[BOXTOP ], S->v1->y);
bbox[BOXTOP ] = MAX (bbox[BOXTOP ], 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];
if (ld->sidenum[side] < 0)
return;
// create the seg
seg_t * seg = BSP_NewSeg ();
seg->v1 = side ? ld->v2 : ld->v1;
seg->v2 = side ? ld->v1 : ld->v2;
seg->sidedef = &sides[ld->sidenum[side]];
seg->linedef = ld;
seg->side = side;
seg->angle = R_PointToAngle2 (seg->v1->x, seg->v1->y, seg->v2->x, seg->v2->y);
seg->frontsector = side ? ld->backsector : ld->frontsector;
seg->backsector = side ? ld->frontsector : ld->backsector;
BSP_CalcOffset (seg);
// link into the list
seg->next = (*list_var);
(*list_var) = seg;
}
seg_t * BSP_CreateSegs (void)
{
seg_t * list = NULL;
int i;
for (i = 0 ; i < numlines ; i++)
{
BSP_SegForLineSide (i, 0, &list);
BSP_SegForLineSide (i, 1, &list);
}
return list;
}
node_t * BSP_CreateLeaf (seg_t * soup)
{
subsector_t * sub = BSP_NewSubsector ();
node_t * node = BSP_NewNode ();
sub->segs = soup;
// TODO: better method, try to avoid self-ref lines
sub->sector = soup->frontsector;
node->sub = sub;
BSP_BoundingBox (soup, node->bbox);
return node;
}
//----------------------------------------------------------------------------
struct NodeEval
{
int left, right, split;
};
int BSP_PointOnSide (seg_t * part, fixed_t x, fixed_t y)
{
x -= part->v1->x;
y -= part->v1->y;
fixed_t dx = part->v2->x - part->v1->x;
fixed_t dy = part->v2->y - part->v1->y;
if (dx == 0)
{
if (x < - DIST_EPSILON)
return (dy < 0) ? +1 : -1;
if (x > + DIST_EPSILON)
return (dy > 0) ? +1 : -1;
return 0;
}
if (dy == 0)
{
if (y < - DIST_EPSILON)
return (dx > 0) ? +1 : -1;
if (y > + DIST_EPSILON)
return (dx < 0) ? +1 : -1;
return 0;
}
// note that we compute the distance to the partition along an axis
// (rather than perpendicular to it), which can give values smaller
// than the true distance. for our purposes, that is okay.
if (abs (dx) >= abs (dy))
{
fixed_t slope = FixedDiv (dy, dx);
y -= FixedMul (x, slope);
if (y < - DIST_EPSILON)
return (dx > 0) ? +1 : -1;
if (y > + DIST_EPSILON)
return (dx < 0) ? +1 : -1;
}
else
{
fixed_t slope = FixedDiv (dx, dy);
x -= FixedMul (y, slope);
if (x < - DIST_EPSILON)
return (dy < 0) ? +1 : -1;
if (x > + DIST_EPSILON)
return (dy > 0) ? +1 : -1;
}
return 0;
}
boolean BSP_SameDirection (seg_t * part, seg_t * seg)
{
fixed_t pdx = part->v2->x - part->v1->x;
fixed_t pdy = part->v2->y - part->v1->y;
fixed_t sdx = seg->v2->x - seg->v1->x;
fixed_t sdy = seg->v2->y - seg->v1->y;
int64_t n = (int64_t)sdx * (int64_t)pdx + (int64_t)sdy * (int64_t)pdy;
return (n > 0);
}
int BSP_SegOnSide (seg_t * part, seg_t * seg)
{
if (seg == part)
return +1;
int side1 = BSP_PointOnSide (part, seg->v1->x, seg->v1->y);
int side2 = BSP_PointOnSide (part, seg->v2->x, seg->v2->y);
// colinear?
if (side1 == 0 && side2 == 0)
return BSP_SameDirection (part, seg) ? +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.
//
boolean BSP_EvalPartition (seg_t * part, seg_t * soup, struct NodeEval * eval)
{
eval->left = 0;
eval->right = 0;
eval->split = 0;
// do not create tiny partitions
if (abs (part->v2->x - part->v1->x) < 4*DIST_EPSILON &&
abs (part->v2->y - part->v1->y) < 4*DIST_EPSILON)
return false;
seg_t * S;
for (S = soup ; S != NULL ; S = S->next)
{
int side = BSP_SegOnSide (part, S);
switch (side)
{
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;
}
//
// 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)
{
// use slower method when number of segs is below a threshold
int count = 0;
seg_t * S;
for (S = soup ; S != NULL ; S = S->next)
count += 1;
if (count < FAST_THRESHOLD)
return NULL;
// determine bounding box of segs
fixed_t bbox[4];
BSP_BoundingBox (soup, bbox);
fixed_t mid_x = bbox[BOXLEFT] / 2 + bbox[BOXRIGHT] / 2;
fixed_t mid_y = bbox[BOXBOTTOM] / 2 + bbox[BOXTOP] / 2;
seg_t * vert_part = NULL;
fixed_t vert_dist = (1 << 30);
seg_t * horiz_part = NULL;
fixed_t horiz_dist = (1 << 30);
// find the segs closest to middle of bbox
seg_t * part;
for (part = soup ; part != NULL ; part = part->next)
{
if (part->v1->x == part->v2->x)
{
fixed_t dist = abs (part->v1->x - mid_x);
if (dist < vert_dist)
{
vert_part = part;
vert_dist = dist;
}
}
else if (part->v1->y == part->v2->y)
{
fixed_t dist = abs (part->v1->y - mid_y);
if (dist < horiz_dist)
{
horiz_part = part;
horiz_dist = dist;
}
}
}
// check that each partition is viable
struct NodeEval v_eval;
struct NodeEval h_eval;
boolean vert_ok = (vert_part != NULL) && BSP_EvalPartition (vert_part, soup, &v_eval);
boolean horiz_ok = (horiz_part != NULL) && BSP_EvalPartition (horiz_part, soup, &h_eval);
if (vert_ok && horiz_ok)
{
int vert_cost = abs (v_eval.left - v_eval.right) * 2 + v_eval.split * 11;
int horiz_cost = abs (h_eval.left - h_eval.right) * 2 + h_eval.split * 11;
return (horiz_cost < vert_cost) ? horiz_part : vert_part;
}
if (vert_ok) return vert_part;
if (horiz_ok) return horiz_part;
return NULL;
}
//
// Evaluate *every* seg in the list as a partition candidate,
// returning the best one, or NULL if none found (which means
// the remaining segs form a subsector).
//
seg_t * BSP_PickNode_Slow (seg_t * soup)
{
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) * 2 + eval.split * 11;
if (cost < best_cost)
{
best = part;
best_cost = cost;
}
}
}
return best;
}
//----------------------------------------------------------------------------
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;
}
fixed_t dx = part->v2->x - part->v1->x;
fixed_t dy = part->v2->y - part->v1->y;
// compute seg coords relative to partition start
fixed_t x1 = seg->v1->x - part->v1->x;
fixed_t y1 = seg->v1->y - part->v1->y;
fixed_t x2 = seg->v2->x - part->v2->x;
fixed_t y2 = seg->v2->y - part->v2->y;
fixed_t a, b;
if (abs (dx) >= abs(dy))
{
fixed_t slope = FixedDiv (dy, dx);
a = abs (y1 - FixedMul (x1, slope));
b = abs (y2 - FixedMul (x2, slope));
}
else
{
fixed_t slope = FixedDiv (dx, dy);
a = abs (x1 - FixedMul (y1, slope));
b = abs (x2 - FixedMul (y2, slope));
}
fixed_t along = FixedDiv (a, a + b);
if (seg->v1->x == seg->v2->x)
*x = seg->v1->x;
else
*x = seg->v1->x + FixedMul (seg->v2->x - seg->v1->x, along);
if (seg->v1->y == seg->v2->y)
*y = seg->v1->y;
else
*y = seg->v1->y + FixedMul (seg->v2->y - seg->v1->y, along);
}
//
// For segs not intersecting the partition, just move them into the
// correct output list (`lefts` or `rights`). otherwise split the seg
// at the intersection point, one pieces goes left, the other right.
//
void BSP_SplitSegs (seg_t * part, seg_t * soup, seg_t ** lefts, seg_t ** rights)
{
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);
vertex_t * iv = BSP_NewVertex (ix, iy);
seg_t * T = BSP_NewSeg ();
T->v2 = S->v2;
T->v1 = iv;
S->v2 = iv;
T->side = S->side;
T->angle = S->angle;
T->sidedef = S->sidedef;
T->linedef = S->linedef;
T->frontsector = S->frontsector;
T->backsector = S->backsector;
// compute offset for new seg, maybe old one too
BSP_CalcOffset (T);
if (S->side)
BSP_CalcOffset (S);
if (BSP_PointOnSide (part, S->v1->x, S->v1->y) < 0)
{
S->next = (*lefts);
(*lefts) = S;
T->next = (*rights);
(*rights) = T;
}
else
{
S->next = (*rights);
(*rights) = S;
T->next = (*lefts);
(*lefts) = T;
}
}
}
node_t * BSP_SubdivideSegs (seg_t * soup)
{
seg_t * part = BSP_PickNode_Fast (soup);
if (part == NULL)
part = BSP_PickNode_Slow (soup);
if (part == NULL)
return BSP_CreateLeaf (soup);
node_t * N = BSP_NewNode ();
N->x = part->v1->x;
N->y = part->v1->y;
N->dx = part->v2->x - N->x;
N->dy = part->v2->y - N->y;
// ensure partitions are a minimum length, since the engine's
// R_PointOnSide() functions have very poor accuracy when the
// delta is too small, and that WILL BREAK a map.
fixed_t min_size = 64 * FRACUNIT;
while (abs (N->dx) < min_size && abs (N->dy) < min_size)
{
N->dx *= 2;
N->dy *= 2;
}
// these are the new lists (after splitting)
seg_t * lefts = NULL;
seg_t * rights = NULL;
BSP_SplitSegs (part, soup, &lefts, &rights);
N->right = BSP_SubdivideSegs (rights);
N->left = BSP_SubdivideSegs (lefts);
BSP_MergeBounds (N);
return N;
}
//----------------------------------------------------------------------------
void Nano_BuildBSP (void)
{
seg_t * list = BSP_CreateSegs ();
root_node = BSP_SubdivideSegs (list);
/* DEBUG:
DumpNode (root_node, 0);
*/
}