if (model == NULL)
return NULL;
- Mod_CheckLoaded(model);
-
// LordHavoc: modified to start at first clip node,
// in other words: first node of the (sub)model
node = model->brush.data_nodes + model->brushq1.hulls[0].firstclipnode;
memset(out, 0, outsize);
}
+static int Mod_Q1BSP_FindBoxClusters(model_t *model, const vec3_t mins, const vec3_t maxs, int maxclusters, int *clusterlist)
+{
+ int numclusters = 0;
+ int nodestackindex = 0;
+ mnode_t *node, *nodestack[1024];
+ if (!model->brush.num_pvsclusters)
+ return -1;
+ node = model->brush.data_nodes;
+ for (;;)
+ {
+#if 1
+ if (node->plane)
+ {
+ // node - recurse down the BSP tree
+ int side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
+ if (side < 2)
+ {
+ // box is on one side of plane, take that path
+ node = node->children[side];
+ }
+ else
+ {
+ // box crosses plane, take one path and remember the other
+ if (nodestackindex < 1024)
+ nodestack[nodestackindex++] = node->children[0];
+ node = node->children[1];
+ }
+ continue;
+ }
+ else
+ {
+ // leaf - add clusterindex to list
+ if (numclusters < maxclusters)
+ clusterlist[numclusters] = ((mleaf_t *)node)->clusterindex;
+ numclusters++;
+ }
+#else
+ if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
+ {
+ if (node->plane)
+ {
+ if (nodestackindex < 1024)
+ nodestack[nodestackindex++] = node->children[0];
+ node = node->children[1];
+ continue;
+ }
+ else
+ {
+ // leaf - add clusterindex to list
+ if (numclusters < maxclusters)
+ clusterlist[numclusters] = ((mleaf_t *)node)->clusterindex;
+ numclusters++;
+ }
+ }
+#endif
+ // try another path we didn't take earlier
+ if (nodestackindex == 0)
+ break;
+ node = nodestack[--nodestackindex];
+ }
+ // return number of clusters found (even if more than the maxclusters)
+ return numclusters;
+}
+
static int Mod_Q1BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
{
- int clusterindex, side, nodestackindex = 0;
+ int nodestackindex = 0;
mnode_t *node, *nodestack[1024];
if (!model->brush.num_pvsclusters)
return true;
node = model->brush.data_nodes;
for (;;)
{
+#if 1
if (node->plane)
{
// node - recurse down the BSP tree
- side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
+ int side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
if (side < 2)
{
// box is on one side of plane, take that path
nodestack[nodestackindex++] = node->children[0];
node = node->children[1];
}
+ continue;
}
else
{
// leaf - check cluster bit
- clusterindex = ((mleaf_t *)node)->clusterindex;
+ int clusterindex = ((mleaf_t *)node)->clusterindex;
if (CHECKPVSBIT(pvs, clusterindex))
{
// it is visible, return immediately with the news
return true;
}
+ }
+#else
+ if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
+ {
+ if (node->plane)
+ {
+ if (nodestackindex < 1024)
+ nodestack[nodestackindex++] = node->children[0];
+ node = node->children[1];
+ continue;
+ }
else
{
- // nothing to see here, try another path we didn't take earlier
- if (nodestackindex == 0)
- break;
- node = nodestack[--nodestackindex];
+ // leaf - check cluster bit
+ int clusterindex = ((mleaf_t *)node)->clusterindex;
+ if (CHECKPVSBIT(pvs, clusterindex))
+ {
+ // it is visible, return immediately with the news
+ return true;
+ }
}
}
+#endif
+ // nothing to see here, try another path we didn't take earlier
+ if (nodestackindex == 0)
+ break;
+ node = nodestack[--nodestackindex];
}
// it is not visible
return false;
static int Mod_Q1BSP_BoxTouchingLeafPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
{
- int clusterindex, side, nodestackindex = 0;
+ int nodestackindex = 0;
mnode_t *node, *nodestack[1024];
if (!model->brush.num_leafs)
return true;
node = model->brush.data_nodes;
for (;;)
{
+#if 1
if (node->plane)
{
// node - recurse down the BSP tree
- side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
+ int side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
if (side < 2)
{
// box is on one side of plane, take that path
nodestack[nodestackindex++] = node->children[0];
node = node->children[1];
}
+ continue;
}
else
{
// leaf - check cluster bit
- clusterindex = ((mleaf_t *)node) - model->brush.data_leafs;
+ int clusterindex = ((mleaf_t *)node) - model->brush.data_leafs;
if (CHECKPVSBIT(pvs, clusterindex))
{
// it is visible, return immediately with the news
return true;
}
+ }
+#else
+ if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
+ {
+ if (node->plane)
+ {
+ if (nodestackindex < 1024)
+ nodestack[nodestackindex++] = node->children[0];
+ node = node->children[1];
+ continue;
+ }
else
{
- // nothing to see here, try another path we didn't take earlier
- if (nodestackindex == 0)
- break;
- node = nodestack[--nodestackindex];
+ // leaf - check cluster bit
+ int clusterindex = ((mleaf_t *)node) - model->brush.data_leafs;
+ if (CHECKPVSBIT(pvs, clusterindex))
+ {
+ // it is visible, return immediately with the news
+ return true;
+ }
}
}
+#endif
+ // nothing to see here, try another path we didn't take earlier
+ if (nodestackindex == 0)
+ break;
+ node = nodestack[--nodestackindex];
}
// it is not visible
return false;
static int Mod_Q1BSP_BoxTouchingVisibleLeafs(model_t *model, const qbyte *visibleleafs, const vec3_t mins, const vec3_t maxs)
{
- int side, nodestackindex = 0;
+ int nodestackindex = 0;
mnode_t *node, *nodestack[1024];
+ if (!model->brush.num_leafs)
+ return true;
node = model->brush.data_nodes;
for (;;)
{
+#if 1
if (node->plane)
{
// node - recurse down the BSP tree
- side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
+ int side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
if (side < 2)
{
// box is on one side of plane, take that path
nodestack[nodestackindex++] = node->children[0];
node = node->children[1];
}
+ continue;
}
else
{
// it is visible, return immediately with the news
return true;
}
+ }
+#else
+ if (BoxesOverlap(mins, maxs, node->mins, node->maxs))
+ {
+ if (node->plane)
+ {
+ if (nodestackindex < 1024)
+ nodestack[nodestackindex++] = node->children[0];
+ node = node->children[1];
+ continue;
+ }
else
{
- // nothing to see here, try another path we didn't take earlier
- if (nodestackindex == 0)
- break;
- node = nodestack[--nodestackindex];
+ // leaf - check if it is visible
+ if (visibleleafs[(mleaf_t *)node - model->brush.data_leafs])
+ {
+ // it is visible, return immediately with the news
+ return true;
+ }
}
}
+#endif
+ // nothing to see here, try another path we didn't take earlier
+ if (nodestackindex == 0)
+ break;
+ node = nodestack[--nodestackindex];
}
// it is not visible
return false;
for (maps = 0;maps < MAXLIGHTMAPS && surface->lightmapinfo->styles[maps] != 255;maps++)
{
- scale = d_lightstylevalue[surface->lightmapinfo->styles[maps]];
+ scale = r_refdef.lightstylevalue[surface->lightmapinfo->styles[maps]];
r00 += lightmap[ 0] * scale;g00 += lightmap[ 1] * scale;b00 += lightmap[ 2] * scale;
r01 += lightmap[ 3] * scale;g01 += lightmap[ 4] * scale;b01 += lightmap[ 5] * scale;
r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
mvertex_t *point;
mleaf_t *leaf, *endleaf;
- // recalculate bounding boxes for all leafs(because qbsp is very sloppy)
+ // tally up portal and point counts and recalculate bounding boxes for all
+ // leafs (because qbsp is very sloppy)
leaf = loadmodel->brush.data_leafs;
endleaf = leaf + loadmodel->brush.num_leafs;
for (;leaf < endleaf;leaf++)
VectorSet(leaf->maxs, -2000000000, -2000000000, -2000000000);
}
p = portalchain;
- while (p)
- {
- if (p->numpoints >= 3)
- {
- for (i = 0;i < 2;i++)
- {
- leaf = (mleaf_t *)p->nodes[i];
- for (j = 0;j < p->numpoints;j++)
- {
- if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
- if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
- if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
- if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
- if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
- if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
- }
- }
- }
- p = p->chain;
- }
-
- Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brush.data_nodes);
-
- // tally up portal and point counts
- p = portalchain;
numportals = 0;
numpoints = 0;
while (p)
{
pnext = p->chain;
- // note: this check must match the one above or it will usually corrupt memory
- // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
- if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1] && ((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
+ if (p->numpoints >= 3 && p->nodes[0] != p->nodes[1])
{
- // first make the back to front portal(forward portal)
- portal->points = point;
- portal->numpoints = p->numpoints;
- portal->plane.dist = p->plane.dist;
- VectorCopy(p->plane.normal, portal->plane.normal);
- portal->here = (mleaf_t *)p->nodes[1];
- portal->past = (mleaf_t *)p->nodes[0];
- // copy points
- for (j = 0;j < portal->numpoints;j++)
+ // note: this check must match the one above or it will usually corrupt memory
+ // the nodes[0] != nodes[1] check is because leaf 0 is the shared solid leaf, it can have many portals inside with leaf 0 on both sides
+ if (((mleaf_t *)p->nodes[0])->clusterindex >= 0 && ((mleaf_t *)p->nodes[1])->clusterindex >= 0)
{
- VectorCopy(p->points + j*3, point->position);
- point++;
+ // first make the back to front portal(forward portal)
+ portal->points = point;
+ portal->numpoints = p->numpoints;
+ portal->plane.dist = p->plane.dist;
+ VectorCopy(p->plane.normal, portal->plane.normal);
+ portal->here = (mleaf_t *)p->nodes[1];
+ portal->past = (mleaf_t *)p->nodes[0];
+ // copy points
+ for (j = 0;j < portal->numpoints;j++)
+ {
+ VectorCopy(p->points + j*3, point->position);
+ point++;
+ }
+ BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
+ PlaneClassify(&portal->plane);
+
+ // link into leaf's portal chain
+ portal->next = portal->here->portals;
+ portal->here->portals = portal;
+
+ // advance to next portal
+ portal++;
+
+ // then make the front to back portal(backward portal)
+ portal->points = point;
+ portal->numpoints = p->numpoints;
+ portal->plane.dist = -p->plane.dist;
+ VectorNegate(p->plane.normal, portal->plane.normal);
+ portal->here = (mleaf_t *)p->nodes[0];
+ portal->past = (mleaf_t *)p->nodes[1];
+ // copy points
+ for (j = portal->numpoints - 1;j >= 0;j--)
+ {
+ VectorCopy(p->points + j*3, point->position);
+ point++;
+ }
+ BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
+ PlaneClassify(&portal->plane);
+
+ // link into leaf's portal chain
+ portal->next = portal->here->portals;
+ portal->here->portals = portal;
+
+ // advance to next portal
+ portal++;
}
- BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
- PlaneClassify(&portal->plane);
-
- // link into leaf's portal chain
- portal->next = portal->here->portals;
- portal->here->portals = portal;
-
- // advance to next portal
- portal++;
-
- // then make the front to back portal(backward portal)
- portal->points = point;
- portal->numpoints = p->numpoints;
- portal->plane.dist = -p->plane.dist;
- VectorNegate(p->plane.normal, portal->plane.normal);
- portal->here = (mleaf_t *)p->nodes[0];
- portal->past = (mleaf_t *)p->nodes[1];
- // copy points
- for (j = portal->numpoints - 1;j >= 0;j--)
+ // add the portal's polygon points to the leaf bounding boxes
+ for (i = 0;i < 2;i++)
{
- VectorCopy(p->points + j*3, point->position);
- point++;
+ leaf = (mleaf_t *)p->nodes[i];
+ for (j = 0;j < p->numpoints;j++)
+ {
+ if (leaf->mins[0] > p->points[j*3+0]) leaf->mins[0] = p->points[j*3+0];
+ if (leaf->mins[1] > p->points[j*3+1]) leaf->mins[1] = p->points[j*3+1];
+ if (leaf->mins[2] > p->points[j*3+2]) leaf->mins[2] = p->points[j*3+2];
+ if (leaf->maxs[0] < p->points[j*3+0]) leaf->maxs[0] = p->points[j*3+0];
+ if (leaf->maxs[1] < p->points[j*3+1]) leaf->maxs[1] = p->points[j*3+1];
+ if (leaf->maxs[2] < p->points[j*3+2]) leaf->maxs[2] = p->points[j*3+2];
+ }
}
- BoxFromPoints(portal->mins, portal->maxs, portal->numpoints, portal->points->position);
- PlaneClassify(&portal->plane);
-
- // link into leaf's portal chain
- portal->next = portal->here->portals;
- portal->here->portals = portal;
-
- // advance to next portal
- portal++;
}
FreePortal(p);
p = pnext;
}
+ // now recalculate the node bounding boxes from the leafs
+ Mod_Q1BSP_RecursiveRecalcNodeBBox(loadmodel->brush.data_nodes);
}
/*
static qbyte *Mod_Q1BSP_GetPVS(model_t *model, const vec3_t p)
{
mnode_t *node;
- Mod_CheckLoaded(model);
node = model->brush.data_nodes;
while (node->plane)
node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
mod->brush.BoxTouchingLeafPVS = Mod_Q1BSP_BoxTouchingLeafPVS;
mod->brush.BoxTouchingVisibleLeafs = Mod_Q1BSP_BoxTouchingVisibleLeafs;
+ mod->brush.FindBoxClusters = Mod_Q1BSP_FindBoxClusters;
mod->brush.LightPoint = Mod_Q1BSP_LightPoint;
mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
mod->brush.AmbientSoundLevelsForPoint = Mod_Q1BSP_AmbientSoundLevelsForPoint;
mod->brush.BoxTouchingPVS = NULL;
mod->brush.BoxTouchingLeafPVS = NULL;
mod->brush.BoxTouchingVisibleLeafs = NULL;
+ mod->brush.FindBoxClusters = NULL;
mod->brush.LightPoint = NULL;
mod->brush.AmbientSoundLevelsForPoint = NULL;
}
static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, model_t *model, mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
{
int i;
- //int sides;
+ int sides;
float nodesegmentmins[3], nodesegmentmaxs[3];
mleaf_t *leaf;
colbrushf_t *brush;
}
*/
#if 1
+ for (;;)
+ {
+ mplane_t *plane = node->plane;
+ if (!plane)
+ break;
+ // axial planes are much more common than non-axial, so an optimized
+ // axial case pays off here
+ if (plane->type < 3)
+ {
+ // this is an axial plane, compare bounding box directly to it and
+ // recurse sides accordingly
+ // recurse down node sides
+ // use an inlined axial BoxOnPlaneSide to slightly reduce overhead
+ //sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, plane);
+ sides = ((segmentmaxs[plane->type] >= plane->dist) | ((segmentmins[plane->type] < plane->dist) << 1));
+ if (sides == 3)
+ {
+ // segment box crosses plane
+ Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+ sides = 2;
+ }
+ }
+ else
+ {
+ // this is a non-axial plane, entire trace bounding box
+ // comparisons against it are likely to be very sloppy, so in if
+ // the whole box is split by the plane we then test the start/end
+ // boxes against it to be sure
+ sides = BoxOnPlaneSide(segmentmins, segmentmaxs, plane);
+ if (sides == 3)
+ {
+ // segment box crosses plane
+ // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
+ sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, plane);
+ if (sides == 3)
+ {
+ Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+ sides = 2;
+ }
+ }
+ }
+ // take whichever side the segment box is on
+ node = node->children[sides - 1];
+ }
+ nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
+ nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
+ nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
+ nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
+ nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
+ nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
+#elif 1
for (;;)
{
nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
mod->brush.BoxTouchingPVS = Mod_Q1BSP_BoxTouchingPVS;
mod->brush.BoxTouchingLeafPVS = Mod_Q1BSP_BoxTouchingLeafPVS;
mod->brush.BoxTouchingVisibleLeafs = Mod_Q1BSP_BoxTouchingVisibleLeafs;
+ mod->brush.FindBoxClusters = Mod_Q1BSP_FindBoxClusters;
mod->brush.LightPoint = Mod_Q3BSP_LightPoint;
mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
mod->brush.PointInLeaf = Mod_Q1BSP_PointInLeaf;
mod->brush.BoxTouchingPVS = NULL;
mod->brush.BoxTouchingLeafPVS = NULL;
mod->brush.BoxTouchingVisibleLeafs = NULL;
+ mod->brush.FindBoxClusters = NULL;
mod->brush.LightPoint = NULL;
mod->brush.FindNonSolidLocation = Mod_Q1BSP_FindNonSolidLocation;
}
projects / xonotic / darkplaces.git / blobdiff