511 lines
8.8 KiB
C
511 lines
8.8 KiB
C
// region.h
|
|
|
|
#include "bsp5.h"
|
|
|
|
/*
|
|
|
|
input
|
|
-----
|
|
vertexes
|
|
edges
|
|
faces
|
|
|
|
output
|
|
------
|
|
smaller set of vertexes
|
|
smaller set of edges
|
|
regions
|
|
? triangulated regions
|
|
face to region mapping numbers
|
|
|
|
*/
|
|
|
|
#define max_edges_in_region 32
|
|
|
|
int firstedge;
|
|
|
|
vec3_t region_mins, region_maxs;
|
|
|
|
void addpointtoregion (vec3_t p)
|
|
{
|
|
int i;
|
|
|
|
for (i=0 ; i<3 ; i++)
|
|
{
|
|
if (p[i] < region_mins[i])
|
|
region_mins[i] = p[i];
|
|
if (p[i] > region_maxs[i])
|
|
region_maxs[i] = p[i];
|
|
}
|
|
}
|
|
|
|
void clearregionsize (void)
|
|
{
|
|
region_mins[0] = region_mins[1] = region_mins[2] = 9999;
|
|
region_maxs[0] = region_maxs[1] = region_maxs[2] = -9999;
|
|
}
|
|
|
|
void addfacetoregionsize (face_t *f)
|
|
{
|
|
int i;
|
|
|
|
for (i=0 ; i<f->numpoints ; i++)
|
|
addpointtoregion (f->pts[i]);
|
|
}
|
|
|
|
/*
|
|
==============
|
|
canjoinfaces
|
|
==============
|
|
*/
|
|
qboolean canjoinfaces (face_t *f, face_t *f2)
|
|
{
|
|
vec3_t oldmins, oldmaxs;
|
|
int i;
|
|
|
|
if (f2->planenum != f->planenum
|
|
|| f2->planeside != f->planeside
|
|
|| f2->texturenum != f->texturenum)
|
|
return false;
|
|
if (f2->outputnumber != -1)
|
|
return false;
|
|
if (f2->contents[0] != f->contents[0])
|
|
{ // does this ever happen? theyy shouldn't share.
|
|
printf ("canjoinfaces: edge with different contents");
|
|
return false;
|
|
}
|
|
|
|
// check size constraints
|
|
if ( ! (texinfo[f->texturenum].flags & tex_special) )
|
|
{
|
|
vectorcopy (region_mins, oldmins);
|
|
vectorcopy (region_maxs, oldmaxs);
|
|
addfacetoregionsize (f2);
|
|
for (i=0 ; i<3 ; i++)
|
|
{
|
|
if (region_maxs[i] - region_mins[i] > 240)
|
|
{
|
|
vectorcopy (oldmins, region_mins);
|
|
vectorcopy (oldmaxs, region_maxs);
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (numsurfedges - firstedge + f2->numpoints > max_edges_in_region)
|
|
return false; // a huge water or sky polygon
|
|
}
|
|
|
|
// check edge count constraints
|
|
return true;
|
|
}
|
|
|
|
|
|
/*
|
|
==============
|
|
recursivegrowregion
|
|
==============
|
|
*/
|
|
void recursivegrowregion (dface_t *r, face_t *f)
|
|
{
|
|
int e;
|
|
face_t *f2;
|
|
int i;
|
|
|
|
if (f->outputnumber == numfaces)
|
|
return;
|
|
|
|
if (f->outputnumber != -1)
|
|
error ("recursivegrowregion: region collision");
|
|
f->outputnumber = numfaces;
|
|
|
|
// add edges
|
|
for (i=0 ; i<f->numpoints ; i++)
|
|
{
|
|
e = f->edges[i];
|
|
if (!edgefaces[abs(e)][0])
|
|
continue; // edge has allready been removed
|
|
if (e > 0)
|
|
f2 = edgefaces[e][1];
|
|
else
|
|
f2 = edgefaces[-e][0];
|
|
if (f2 && f2->outputnumber == numfaces)
|
|
{
|
|
edgefaces[abs(e)][0] = null;
|
|
edgefaces[abs(e)][1] = null;
|
|
continue; // allready merged
|
|
}
|
|
if (f2 && canjoinfaces (f, f2))
|
|
{ // remove the edge and merge the faces
|
|
edgefaces[abs(e)][0] = null;
|
|
edgefaces[abs(e)][1] = null;
|
|
recursivegrowregion (r, f2);
|
|
}
|
|
else
|
|
{
|
|
// emit a surfedge
|
|
if (numsurfedges == max_map_surfedges)
|
|
error ("numsurfedges == max_map_surfedges");
|
|
dsurfedges[numsurfedges] = e;
|
|
numsurfedges++;
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
void printdface (int f)
|
|
{ // for debugging
|
|
dface_t *df;
|
|
dedge_t *e;
|
|
int i, n;
|
|
|
|
df = &dfaces[f];
|
|
for (i=0 ; i<df->numedges ; i++)
|
|
{
|
|
n = dsurfedges[df->firstedge+i];
|
|
e = &dedges[abs(n)];
|
|
if (n < 0)
|
|
printf ("%5i = %5i : %5i\n", n, e->v[1], e->v[0]);
|
|
else
|
|
printf ("%5i = %5i : %5i\n", n, e->v[0], e->v[1]);
|
|
}
|
|
}
|
|
|
|
void findvertexuse (int v)
|
|
{ // for debugging
|
|
int i, j, n;
|
|
dface_t *df;
|
|
dedge_t *e;
|
|
|
|
for (i=firstmodelface ; i<numfaces ; i++)
|
|
{
|
|
df = &dfaces[i];
|
|
for (j=0 ; j<df->numedges ; j++)
|
|
{
|
|
n = dsurfedges[df->firstedge+j];
|
|
e = &dedges[abs(n)];
|
|
if (e->v[0] == v || e->v[1] == v)
|
|
{
|
|
printf ("on face %i\n", i);
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void findedgeuse (int v)
|
|
{ // for debugging
|
|
int i, j, n;
|
|
dface_t *df;
|
|
|
|
for (i=firstmodelface ; i<numfaces ; i++)
|
|
{
|
|
df = &dfaces[i];
|
|
for (j=0 ; j<df->numedges ; j++)
|
|
{
|
|
n = dsurfedges[df->firstedge+j];
|
|
if (n == v || -n == v)
|
|
{
|
|
printf ("on face %i\n", i);
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
================
|
|
healedges
|
|
|
|
extends e1 so that it goes all the way to e2, and removes all references
|
|
to e2
|
|
================
|
|
*/
|
|
int edgemapping[max_map_edges];
|
|
void healedges (int e1, int e2)
|
|
{
|
|
int i, j, n, saved;
|
|
dface_t *df;
|
|
dedge_t *ed, *ed2;
|
|
vec3_t v1, v2;
|
|
dface_t *found[2];
|
|
int foundj[2];
|
|
|
|
return;
|
|
e1 = edgemapping[e1];
|
|
e2 = edgemapping[e2];
|
|
|
|
// extend e1 to e2
|
|
ed = &dedges[e1];
|
|
ed2 = &dedges[e2];
|
|
vectorsubtract (dvertexes[ed->v[1]].point, dvertexes[ed->v[0]].point, v1);
|
|
vectornormalize (v1);
|
|
|
|
if (ed->v[0] == ed2->v[0])
|
|
ed->v[0] = ed2->v[1];
|
|
else if (ed->v[0] == ed2->v[1])
|
|
ed->v[0] = ed2->v[0];
|
|
else if (ed->v[1] == ed2->v[0])
|
|
ed->v[1] = ed2->v[1];
|
|
else if (ed->v[1] == ed2->v[1])
|
|
ed->v[1] = ed2->v[0];
|
|
else
|
|
error ("healedges: edges don't meet");
|
|
|
|
vectorsubtract (dvertexes[ed->v[1]].point, dvertexes[ed->v[0]].point, v2);
|
|
vectornormalize (v2);
|
|
|
|
if (!vectorcompare (v1, v2))
|
|
error ("healedges: edges not colinear");
|
|
|
|
edgemapping[e2] = e1;
|
|
saved = 0;
|
|
|
|
// remove all uses of e2
|
|
for (i=firstmodelface ; i<numfaces ; i++)
|
|
{
|
|
df = &dfaces[i];
|
|
for (j=0 ; j<df->numedges ; j++)
|
|
{
|
|
n = dsurfedges[df->firstedge+j];
|
|
if (n == e2 || n == -e2)
|
|
{
|
|
found[saved] = df;
|
|
foundj[saved] = j;
|
|
saved++;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (saved != 2)
|
|
printf ("warning: didn't find both faces for a saved edge\n");
|
|
else
|
|
{
|
|
for (i=0 ; i<2 ; i++)
|
|
{ // remove this edge
|
|
df = found[i];
|
|
j = foundj[i];
|
|
for (j++ ; j<df->numedges ; j++)
|
|
dsurfedges[df->firstedge+j-1] =
|
|
dsurfedges[df->firstedge+j];
|
|
dsurfedges[df->firstedge+j-1] = 0;
|
|
df->numedges--;
|
|
}
|
|
|
|
|
|
edgefaces[e2][0] = edgefaces[e2][1] = null;
|
|
}
|
|
}
|
|
|
|
typedef struct
|
|
{
|
|
int numedges;
|
|
int edges[2];
|
|
} checkpoint_t;
|
|
|
|
checkpoint_t checkpoints[max_map_verts];
|
|
|
|
/*
|
|
==============
|
|
removecolinearedges
|
|
==============
|
|
*/
|
|
void removecolinearedges (void)
|
|
{
|
|
int i,j, v;
|
|
int c0, c1, c2, c3;
|
|
checkpoint_t *cp;
|
|
|
|
// no edges remapped yet
|
|
for (i=0 ; i<numedges ; i++)
|
|
edgemapping[i] = i;
|
|
|
|
// find vertexes that only have two edges
|
|
memset (checkpoints, 0, sizeof(checkpoints));
|
|
|
|
for (i=firstmodeledge ; i<numedges ; i++)
|
|
{
|
|
if (!edgefaces[i][0])
|
|
continue; // removed
|
|
for (j=0 ; j<2 ; j++)
|
|
{
|
|
v = dedges[i].v[j];
|
|
cp = &checkpoints[v];
|
|
if (cp->numedges<2)
|
|
cp->edges[cp->numedges] = i;
|
|
cp->numedges++;
|
|
}
|
|
}
|
|
|
|
// if a vertex only has two edges and they are colinear, it can be removed
|
|
c0 = c1 = c2 = c3 = 0;
|
|
|
|
for (i=0 ; i<numvertexes ; i++)
|
|
{
|
|
cp = &checkpoints[i];
|
|
switch (cp->numedges)
|
|
{
|
|
case 0:
|
|
c0++;
|
|
break;
|
|
case 1:
|
|
c1++;
|
|
break;
|
|
case 2:
|
|
c2++;
|
|
healedges (cp->edges[0], cp->edges[1]);
|
|
break;
|
|
default:
|
|
c3++;
|
|
break;
|
|
}
|
|
}
|
|
|
|
// qprintf ("%5i c0\n", c0);
|
|
// qprintf ("%5i c1\n", c1);
|
|
// qprintf ("%5i c2\n", c2);
|
|
// qprintf ("%5i c3+\n", c3);
|
|
qprintf ("%5i deges removed by tjunction healing\n", c2);
|
|
}
|
|
|
|
/*
|
|
==============
|
|
countrealnumbers
|
|
==============
|
|
*/
|
|
void countrealnumbers (void)
|
|
{
|
|
int i;
|
|
int c;
|
|
|
|
qprintf ("%5i regions\n", numfaces-firstmodelface);
|
|
|
|
c = 0;
|
|
for (i=firstmodelface ; i<numfaces ; i++)
|
|
c += dfaces[i].numedges;
|
|
qprintf ("%5i real marksurfaces\n", c);
|
|
|
|
c = 0;
|
|
for (i=firstmodeledge ; i<numedges ; i++)
|
|
if (edgefaces[i][0])
|
|
c++; // not removed
|
|
|
|
qprintf ("%5i real edges\n", c);
|
|
}
|
|
|
|
//=============================================================================
|
|
|
|
/*
|
|
==============
|
|
grownoderegion_r
|
|
==============
|
|
*/
|
|
void grownoderegion_r (node_t *node)
|
|
{
|
|
dface_t *r;
|
|
face_t *f;
|
|
int i;
|
|
|
|
if (node->planenum == planenum_leaf)
|
|
return;
|
|
|
|
node->firstface = numfaces;
|
|
|
|
for (f=node->faces ; f ; f=f->next)
|
|
{
|
|
// if (f->outputnumber != -1)
|
|
// continue; // allready grown into an earlier region
|
|
|
|
// emit a region
|
|
|
|
if (numfaces == max_map_faces)
|
|
error ("max_map_faces");
|
|
f->outputnumber = numfaces;
|
|
r = &dfaces[numfaces];
|
|
|
|
r->planenum = node->outputplanenum;
|
|
r->side = f->planeside;
|
|
r->texinfo = f->texturenum;
|
|
for (i=0 ; i<maxlightmaps ; i++)
|
|
r->styles[i] = 255;
|
|
r->lightofs = -1;
|
|
|
|
// add the face and mergable neighbors to it
|
|
|
|
#if 0
|
|
clearregionsize ();
|
|
addfacetoregionsize (f);
|
|
recursivegrowregion (r, f);
|
|
#endif
|
|
r->firstedge = firstedge = numsurfedges;
|
|
for (i=0 ; i<f->numpoints ; i++)
|
|
{
|
|
if (numsurfedges == max_map_surfedges)
|
|
error ("numsurfedges == max_map_surfedges");
|
|
dsurfedges[numsurfedges] = f->edges[i];
|
|
numsurfedges++;
|
|
}
|
|
|
|
r->numedges = numsurfedges - r->firstedge;
|
|
|
|
numfaces++;
|
|
}
|
|
|
|
node->numfaces = numfaces - node->firstface;
|
|
|
|
grownoderegion_r (node->children[0]);
|
|
grownoderegion_r (node->children[1]);
|
|
}
|
|
|
|
|
|
/*
|
|
==============
|
|
grownoderegions
|
|
==============
|
|
*/
|
|
void grownoderegions (node_t *headnode)
|
|
{
|
|
qprintf ("---- growregions ----\n");
|
|
|
|
grownoderegion_r (headnode);
|
|
|
|
//removecolinearedges ();
|
|
countrealnumbers ();
|
|
}
|
|
|
|
/*
|
|
===============================================================================
|
|
|
|
turn the faces on a plane into optimal non-convex regions
|
|
the edges may still be split later as a result of tjunctions
|
|
|
|
typedef struct
|
|
{
|
|
vec3_t dir;
|
|
vec3_t origin;
|
|
vec3_t p[2];
|
|
}
|
|
for all faces
|
|
for all edges
|
|
for all edges so far
|
|
if overlap
|
|
split
|
|
|
|
|
|
===============================================================================
|
|
*/
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|