shithub: nanobsp

ref: d8c7c055604b45a5d883f7d32e49e11487dca7ae
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  (1.0 / 256.0)


// 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 = &sectors[0];  // FIXME

	N->sub = sub;
	return N;
}

//----------------------------------------------------------------------------

struct NodeEval
{
	int left, right, split;
};

//
// 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)
{
	// TODO

	return false;
}

//
// 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)
{
	// TODO
	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)
{
	// TODO
	return NULL;
}

//----------------------------------------------------------------------------

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
}