ref: fabfd02b9487fadcc21b1dc46585a52aac2987d4
dir: /nano_bsp.c/
//----------------------------------------------------------------------------
//
// Copyright (c) 2023 Andrew Apted
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
//----------------------------------------------------------------------------
#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"
#undef MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#undef MIN
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define DIST_EPSILON (FRACUNIT / 64)
// TODO: probably make these global
typedef struct nsubsec_s
{
sector_t * sector;
seg_t * segs;
} nsubsec_t;
typedef struct nnode_s
{
// when non-NULL, this is actually a leaf of the BSP tree
nsubsec_t * sub;
// partition line (start coord, delta to end)
fixed_t x, y, dx, dy;
// right and left children
struct nnode_s * right;
struct nnode_s * left;
} nnode_t;
vertex_t * BSP_NewVertex (void)
{
vertex_t * vert = Z_Malloc(sizeof(vertex_t), PU_LEVEL, NULL);
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;
}
nsubsec_t * BSP_NewSubsector (void)
{
nsubsec_t * sub = Z_Malloc (sizeof(nsubsec_t), PU_LEVEL, NULL);
memset (sub, 0, sizeof(*sub));
return sub;
}
nnode_t * BSP_NewNode (void)
{
nnode_t * node = Z_Malloc (sizeof(nnode_t), PU_LEVEL, NULL);
memset (node, 0, sizeof(*node));
return node;
}
//----------------------------------------------------------------------------
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->offset = 0;
seg->angle = R_PointToAngle2 (seg->v1->x, seg->v1->y, seg->v2->x, seg->v2->y);
seg->sidedef = &sides[ld->sidenum[side]];
seg->linedef = ld;
seg->frontsector = side ? ld->backsector : ld->frontsector;
seg->backsector = side ? ld->frontsector : ld->backsector;
// 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;
}
nnode_t * BSP_CreateLeaf (seg_t * soup)
{
nsubsec_t * sub = BSP_NewSubsector ();
nnode_t * N = BSP_NewNode ();
sub->segs = soup;
sub->sector = §ors[0]; // FIXME
N->sub = sub;
return N;
}
//----------------------------------------------------------------------------
struct NodeEval
{
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.
//
boolean BSP_EvalPartition (seg_t * part, seg_t * soup, struct NodeEval * eval)
{
eval->left = 0;
eval->right = 0;
eval->split = 0;
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;
}
//
// 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)
{
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;
}
//
// 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)
if (cost < best_cost)
{
best = part;
best_cost = cost;
}
}
}
return best;
}
//----------------------------------------------------------------------------
void BSP_SplitSegs (seg_t * part, seg_t * soup, seg_t ** lefts, seg_t ** rights)
{
// TODO
}
nnode_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);
nnode_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;
// 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);
return N;
}
//----------------------------------------------------------------------------
void Nano_BuildBSP (void)
{
seg_t * list = BSP_CreateSegs ();
nnode_t * node = BSP_SubdivideSegs (list);
// TODO
}