-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-*/\r
-// trace.c\r
-/*\r
-#include "cmdlib.h"\r
-#include "mathlib.h"\r
-#include "bspfile.h"\r
-*/\r
-\r
-#include "qrad.h"\r
-\r
-#define ON_EPSILON 0.1\r
-\r
-typedef struct tnode_s\r
-{\r
- int type;\r
- vec3_t normal;\r
- float dist;\r
- int children[2];\r
- int pad;\r
-} tnode_t;\r
-\r
-tnode_t *tnodes, *tnode_p;\r
-\r
-/*\r
-==============\r
-MakeTnode\r
-\r
-Converts the disk node structure into the efficient tracing structure\r
-==============\r
-*/\r
-void MakeTnode (int nodenum)\r
-{\r
- tnode_t *t;\r
- dplane_t *plane;\r
- int i;\r
- dnode_t *node;\r
- \r
- t = tnode_p++;\r
-\r
- node = dnodes + nodenum;\r
- plane = dplanes + node->planenum;\r
-\r
- t->type = plane->type;\r
- VectorCopy (plane->normal, t->normal);\r
- t->dist = plane->dist;\r
- \r
- for (i=0 ; i<2 ; i++)\r
- {\r
- if (node->children[i] < 0)\r
- t->children[i] = (dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID) | (1<<31);\r
- else\r
- {\r
- t->children[i] = tnode_p - tnodes;\r
- MakeTnode (node->children[i]);\r
- }\r
- }\r
- \r
-}\r
-\r
-\r
-/*\r
-=============\r
-MakeTnodes\r
-\r
-Loads the node structure out of a .bsp file to be used for light occlusion\r
-=============\r
-*/\r
-void MakeTnodes (dmodel_t *bm)\r
-{\r
- // 32 byte align the structs\r
- tnodes = malloc( (numnodes+1) * sizeof(tnode_t));\r
- tnodes = (tnode_t *)(((int)tnodes + 31)&~31);\r
- tnode_p = tnodes;\r
-\r
- MakeTnode (0);\r
-}\r
-\r
-\r
-//==========================================================\r
-\r
-\r
-int TestLine_r (int node, vec3_t start, vec3_t stop)\r
-{\r
- tnode_t *tnode;\r
- float front, back;\r
- vec3_t mid;\r
- float frac;\r
- int side;\r
- int r;\r
-\r
- if (node & (1<<31))\r
- return node & ~(1<<31); // leaf node\r
-\r
- tnode = &tnodes[node];\r
- switch (tnode->type)\r
- {\r
- case PLANE_X:\r
- front = start[0] - tnode->dist;\r
- back = stop[0] - tnode->dist;\r
- break;\r
- case PLANE_Y:\r
- front = start[1] - tnode->dist;\r
- back = stop[1] - tnode->dist;\r
- break;\r
- case PLANE_Z:\r
- front = start[2] - tnode->dist;\r
- back = stop[2] - tnode->dist;\r
- break;\r
- default:\r
- front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;\r
- back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;\r
- break;\r
- }\r
-\r
- if (front >= -ON_EPSILON && back >= -ON_EPSILON)\r
- return TestLine_r (tnode->children[0], start, stop);\r
- \r
- if (front < ON_EPSILON && back < ON_EPSILON)\r
- return TestLine_r (tnode->children[1], start, stop);\r
-\r
- side = front < 0;\r
- \r
- frac = front / (front-back);\r
-\r
- mid[0] = start[0] + (stop[0] - start[0])*frac;\r
- mid[1] = start[1] + (stop[1] - start[1])*frac;\r
- mid[2] = start[2] + (stop[2] - start[2])*frac;\r
-\r
- r = TestLine_r (tnode->children[side], start, mid);\r
- if (r)\r
- return r;\r
- return TestLine_r (tnode->children[!side], mid, stop);\r
-}\r
-\r
-int TestLine (vec3_t start, vec3_t stop)\r
-{\r
- return TestLine_r (0, start, stop);\r
-}\r
-\r
-/*\r
-==============================================================================\r
-\r
-LINE TRACING\r
-\r
-The major lighting operation is a point to point visibility test, performed\r
-by recursive subdivision of the line by the BSP tree.\r
-\r
-==============================================================================\r
-*/\r
-\r
-typedef struct\r
-{\r
- vec3_t backpt;\r
- int side;\r
- int node;\r
-} tracestack_t;\r
-\r
-\r
-/*\r
-==============\r
-TestLine\r
-==============\r
-*/\r
-qboolean _TestLine (vec3_t start, vec3_t stop)\r
-{\r
- int node;\r
- float front, back;\r
- tracestack_t *tstack_p;\r
- int side;\r
- float frontx,fronty, frontz, backx, backy, backz;\r
- tracestack_t tracestack[64];\r
- tnode_t *tnode;\r
- \r
- frontx = start[0];\r
- fronty = start[1];\r
- frontz = start[2];\r
- backx = stop[0];\r
- backy = stop[1];\r
- backz = stop[2];\r
- \r
- tstack_p = tracestack;\r
- node = 0;\r
- \r
- while (1)\r
- {\r
- if (node == CONTENTS_SOLID)\r
- {\r
-#if 0\r
- float d1, d2, d3;\r
-\r
- d1 = backx - frontx;\r
- d2 = backy - fronty;\r
- d3 = backz - frontz;\r
-\r
- if (d1*d1 + d2*d2 + d3*d3 > 1)\r
-#endif\r
- return false; // DONE!\r
- }\r
- \r
- while (node < 0)\r
- {\r
- // pop up the stack for a back side\r
- tstack_p--;\r
- if (tstack_p < tracestack)\r
- return true;\r
- node = tstack_p->node;\r
- \r
- // set the hit point for this plane\r
- \r
- frontx = backx;\r
- fronty = backy;\r
- frontz = backz;\r
- \r
- // go down the back side\r
-\r
- backx = tstack_p->backpt[0];\r
- backy = tstack_p->backpt[1];\r
- backz = tstack_p->backpt[2];\r
- \r
- node = tnodes[tstack_p->node].children[!tstack_p->side];\r
- }\r
-\r
- tnode = &tnodes[node];\r
- \r
- switch (tnode->type)\r
- {\r
- case PLANE_X:\r
- front = frontx - tnode->dist;\r
- back = backx - tnode->dist;\r
- break;\r
- case PLANE_Y:\r
- front = fronty - tnode->dist;\r
- back = backy - tnode->dist;\r
- break;\r
- case PLANE_Z:\r
- front = frontz - tnode->dist;\r
- back = backz - tnode->dist;\r
- break;\r
- default:\r
- front = (frontx*tnode->normal[0] + fronty*tnode->normal[1] + frontz*tnode->normal[2]) - tnode->dist;\r
- back = (backx*tnode->normal[0] + backy*tnode->normal[1] + backz*tnode->normal[2]) - tnode->dist;\r
- break;\r
- }\r
-\r
- if (front > -ON_EPSILON && back > -ON_EPSILON)\r
-// if (front > 0 && back > 0)\r
- {\r
- node = tnode->children[0];\r
- continue;\r
- }\r
- \r
- if (front < ON_EPSILON && back < ON_EPSILON)\r
-// if (front <= 0 && back <= 0)\r
- {\r
- node = tnode->children[1];\r
- continue;\r
- }\r
-\r
- side = front < 0;\r
- \r
- front = front / (front-back);\r
- \r
- tstack_p->node = node;\r
- tstack_p->side = side;\r
- tstack_p->backpt[0] = backx;\r
- tstack_p->backpt[1] = backy;\r
- tstack_p->backpt[2] = backz;\r
- \r
- tstack_p++;\r
- \r
- backx = frontx + front*(backx-frontx);\r
- backy = fronty + front*(backy-fronty);\r
- backz = frontz + front*(backz-frontz);\r
- \r
- node = tnode->children[side]; \r
- } \r
-}\r
-\r
-\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant 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.
+
+GtkRadiant 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.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+*/
+// trace.c
+/*
+#include "cmdlib.h"
+#include "mathlib.h"
+#include "bspfile.h"
+*/
+
+#include "qrad.h"
+
+#define ON_EPSILON 0.1
+
+typedef struct tnode_s
+{
+ int type;
+ vec3_t normal;
+ float dist;
+ int children[2];
+ int pad;
+} tnode_t;
+
+tnode_t *tnodes, *tnode_p;
+
+/*
+==============
+MakeTnode
+
+Converts the disk node structure into the efficient tracing structure
+==============
+*/
+void MakeTnode (int nodenum)
+{
+ tnode_t *t;
+ dplane_t *plane;
+ int i;
+ dnode_t *node;
+
+ t = tnode_p++;
+
+ node = dnodes + nodenum;
+ plane = dplanes + node->planenum;
+
+ t->type = plane->type;
+ VectorCopy (plane->normal, t->normal);
+ t->dist = plane->dist;
+
+ for (i=0 ; i<2 ; i++)
+ {
+ if (node->children[i] < 0)
+ t->children[i] = (dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID) | (1<<31);
+ else
+ {
+ t->children[i] = tnode_p - tnodes;
+ MakeTnode (node->children[i]);
+ }
+ }
+
+}
+
+
+/*
+=============
+MakeTnodes
+
+Loads the node structure out of a .bsp file to be used for light occlusion
+=============
+*/
+void MakeTnodes (dmodel_t *bm)
+{
+ // 32 byte align the structs
+ tnodes = malloc( (numnodes+1) * sizeof(tnode_t));
+ tnodes = (tnode_t *)(((int)tnodes + 31)&~31);
+ tnode_p = tnodes;
+
+ MakeTnode (0);
+}
+
+
+//==========================================================
+
+
+int TestLine_r (int node, vec3_t start, vec3_t stop)
+{
+ tnode_t *tnode;
+ float front, back;
+ vec3_t mid;
+ float frac;
+ int side;
+ int r;
+
+ if (node & (1<<31))
+ return node & ~(1<<31); // leaf node
+
+ tnode = &tnodes[node];
+ switch (tnode->type)
+ {
+ case PLANE_X:
+ front = start[0] - tnode->dist;
+ back = stop[0] - tnode->dist;
+ break;
+ case PLANE_Y:
+ front = start[1] - tnode->dist;
+ back = stop[1] - tnode->dist;
+ break;
+ case PLANE_Z:
+ front = start[2] - tnode->dist;
+ back = stop[2] - tnode->dist;
+ break;
+ default:
+ front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
+ back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;
+ break;
+ }
+
+ if (front >= -ON_EPSILON && back >= -ON_EPSILON)
+ return TestLine_r (tnode->children[0], start, stop);
+
+ if (front < ON_EPSILON && back < ON_EPSILON)
+ return TestLine_r (tnode->children[1], start, stop);
+
+ side = front < 0;
+
+ frac = front / (front-back);
+
+ mid[0] = start[0] + (stop[0] - start[0])*frac;
+ mid[1] = start[1] + (stop[1] - start[1])*frac;
+ mid[2] = start[2] + (stop[2] - start[2])*frac;
+
+ r = TestLine_r (tnode->children[side], start, mid);
+ if (r)
+ return r;
+ return TestLine_r (tnode->children[!side], mid, stop);
+}
+
+int TestLine (vec3_t start, vec3_t stop)
+{
+ return TestLine_r (0, start, stop);
+}
+
+/*
+==============================================================================
+
+LINE TRACING
+
+The major lighting operation is a point to point visibility test, performed
+by recursive subdivision of the line by the BSP tree.
+
+==============================================================================
+*/
+
+typedef struct
+{
+ vec3_t backpt;
+ int side;
+ int node;
+} tracestack_t;
+
+
+/*
+==============
+TestLine
+==============
+*/
+qboolean _TestLine (vec3_t start, vec3_t stop)
+{
+ int node;
+ float front, back;
+ tracestack_t *tstack_p;
+ int side;
+ float frontx,fronty, frontz, backx, backy, backz;
+ tracestack_t tracestack[64];
+ tnode_t *tnode;
+
+ frontx = start[0];
+ fronty = start[1];
+ frontz = start[2];
+ backx = stop[0];
+ backy = stop[1];
+ backz = stop[2];
+
+ tstack_p = tracestack;
+ node = 0;
+
+ while (1)
+ {
+ if (node == CONTENTS_SOLID)
+ {
+#if 0
+ float d1, d2, d3;
+
+ d1 = backx - frontx;
+ d2 = backy - fronty;
+ d3 = backz - frontz;
+
+ if (d1*d1 + d2*d2 + d3*d3 > 1)
+#endif
+ return false; // DONE!
+ }
+
+ while (node < 0)
+ {
+ // pop up the stack for a back side
+ tstack_p--;
+ if (tstack_p < tracestack)
+ return true;
+ node = tstack_p->node;
+
+ // set the hit point for this plane
+
+ frontx = backx;
+ fronty = backy;
+ frontz = backz;
+
+ // go down the back side
+
+ backx = tstack_p->backpt[0];
+ backy = tstack_p->backpt[1];
+ backz = tstack_p->backpt[2];
+
+ node = tnodes[tstack_p->node].children[!tstack_p->side];
+ }
+
+ tnode = &tnodes[node];
+
+ switch (tnode->type)
+ {
+ case PLANE_X:
+ front = frontx - tnode->dist;
+ back = backx - tnode->dist;
+ break;
+ case PLANE_Y:
+ front = fronty - tnode->dist;
+ back = backy - tnode->dist;
+ break;
+ case PLANE_Z:
+ front = frontz - tnode->dist;
+ back = backz - tnode->dist;
+ break;
+ default:
+ front = (frontx*tnode->normal[0] + fronty*tnode->normal[1] + frontz*tnode->normal[2]) - tnode->dist;
+ back = (backx*tnode->normal[0] + backy*tnode->normal[1] + backz*tnode->normal[2]) - tnode->dist;
+ break;
+ }
+
+ if (front > -ON_EPSILON && back > -ON_EPSILON)
+// if (front > 0 && back > 0)
+ {
+ node = tnode->children[0];
+ continue;
+ }
+
+ if (front < ON_EPSILON && back < ON_EPSILON)
+// if (front <= 0 && back <= 0)
+ {
+ node = tnode->children[1];
+ continue;
+ }
+
+ side = front < 0;
+
+ front = front / (front-back);
+
+ tstack_p->node = node;
+ tstack_p->side = side;
+ tstack_p->backpt[0] = backx;
+ tstack_p->backpt[1] = backy;
+ tstack_p->backpt[2] = backz;
+
+ tstack_p++;
+
+ backx = frontx + front*(backx-frontx);
+ backy = fronty + front*(backy-fronty);
+ backz = frontz + front*(backz-frontz);
+
+ node = tnode->children[side];
+ }
+}
+
+