+ trace->skipsupercontentsmask = skipsupercontentsmask;
+ trace->skipmaterialflagsmask = skipmaterialflagsmask;
+
+ // calculate tracebox-like parameters for efficient culling
+ VectorMAM(0.5f, thisbrush_start->mins, 0.5f, thisbrush_start->maxs, start);
+ VectorMAM(0.5f, thisbrush_end->mins, 0.5f, thisbrush_end->maxs, end);
+ VectorSubtract(thisbrush_start->mins, start, startmins);
+ VectorSubtract(thisbrush_start->maxs, start, startmaxs);
+ VectorSubtract(thisbrush_end->mins, end, endmins);
+ VectorSubtract(thisbrush_end->maxs, end, endmaxs);
+ mins[0] = min(startmins[0], endmins[0]);
+ mins[1] = min(startmins[1], endmins[1]);
+ mins[2] = min(startmins[2], endmins[2]);
+ maxs[0] = max(startmaxs[0], endmaxs[0]);
+ maxs[1] = max(startmaxs[1], endmaxs[1]);
+ maxs[2] = max(startmaxs[2], endmaxs[2]);
+
+ // push first node
+ nodestackline[nodestackpos][0] = start[0];
+ nodestackline[nodestackpos][1] = start[1];
+ nodestackline[nodestackpos][2] = start[2];
+ nodestackline[nodestackpos][3] = end[0];
+ nodestackline[nodestackpos][4] = end[1];
+ nodestackline[nodestackpos][5] = end[2];
+ nodestack[nodestackpos++] = nodenum;
+ while (nodestackpos)
+ {
+ nodenum = nodestack[--nodestackpos];
+ node = bih->nodes + nodenum;
+ VectorCopy(nodestackline[nodestackpos], nodestart);
+ VectorCopy(nodestackline[nodestackpos] + 3, nodeend);
+ sweepnodemins[0] = min(nodestart[0], nodeend[0]) + mins[0] - 1;
+ sweepnodemins[1] = min(nodestart[1], nodeend[1]) + mins[1] - 1;
+ sweepnodemins[2] = min(nodestart[2], nodeend[2]) + mins[2] - 1;
+ sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + maxs[0] + 1;
+ sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + maxs[1] + 1;
+ sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + maxs[2] + 1;
+ if (!BoxesOverlap(sweepnodemins, sweepnodemaxs, node->mins, node->maxs))
+ continue;
+ if (node->type <= BIH_SPLITZ && nodestackpos+2 <= 1024)
+ {
+ // recurse children of the split
+ axis = node->type - BIH_SPLITX;
+ d1 = node->backmax - nodestart[axis] - mins[axis];
+ d2 = node->backmax - nodeend[axis] - mins[axis];
+ d3 = nodestart[axis] - node->frontmin + maxs[axis];
+ d4 = nodeend[axis] - node->frontmin + maxs[axis];
+ switch((d1 < 0) | ((d2 < 0) << 1) | ((d3 < 0) << 2) | ((d4 < 0) << 3))
+ {
+ case 0: /* >>>> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 1: /* <>>> */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 2: /* ><>> */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 3: /* <<>> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 4: /* >><> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 5: /* <><> */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 6: /* ><<> */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 7: /* <<<> */ f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 8: /* >>>< */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 9: /* <>>< */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 10: /* ><>< */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 11: /* <<>< */ f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 12: /* >><< */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 13: /* <><< */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 14: /* ><<< */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 15: /* <<<< */ break;
+ }
+ }
+ else if (node->type == BIH_UNORDERED)
+ {
+ // calculate sweep bounds for this node
+ // copy node bounds into local variables and expand to get Minkowski Sum of the two shapes
+ VectorSubtract(node->mins, maxs, nodebigmins);
+ VectorSubtract(node->maxs, mins, nodebigmaxs);
+ // clip line to this node bounds
+ axis = 0; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ axis = 1; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ axis = 2; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ // some of the line intersected the enlarged node box
+ // calculate sweep bounds for this node
+ sweepnodemins[0] = min(nodestart[0], nodeend[0]) + mins[0] - 1;
+ sweepnodemins[1] = min(nodestart[1], nodeend[1]) + mins[1] - 1;
+ sweepnodemins[2] = min(nodestart[2], nodeend[2]) + mins[2] - 1;
+ sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + maxs[0] + 1;
+ sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + maxs[1] + 1;
+ sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + maxs[2] + 1;
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = bih->leafs + node->children[axis];
+ if (!BoxesOverlap(sweepnodemins, sweepnodemaxs, leaf->mins, leaf->maxs))
+ continue;
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, brush, brush);
+ break;
+ case BIH_COLLISIONTRIANGLE:
+ if (!mod_q3bsp_curves_collisions.integer)
+ continue;
+ e = model->brush.data_collisionelement3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->brush.data_collisionvertex3f + e[0] * 3, model->brush.data_collisionvertex3f + e[1] * 3, model->brush.data_collisionvertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ case BIH_RENDERTRIANGLE:
+ e = model->surfmesh.data_element3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->surfmesh.data_vertex3f + e[0] * 3, model->surfmesh.data_vertex3f + e[1] * 3, model->surfmesh.data_vertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ }
+ }
+ }