1 /*
2 ===========================================================================
3
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
8
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29 /*
30 ===============================================================================
31
32 Trace model vs. polygonal model collision detection.
33
34 ===============================================================================
35 */
36
37 #include "sys/platform.h"
38
39 #include "cm/CollisionModel_local.h"
40
41 /*
42 ===============================================================================
43
44 Trace through the spatial subdivision
45
46 ===============================================================================
47 */
48
49 /*
50 ================
51 idCollisionModelManagerLocal::TraceTrmThroughNode
52 ================
53 */
TraceTrmThroughNode(cm_traceWork_t * tw,cm_node_t * node)54 void idCollisionModelManagerLocal::TraceTrmThroughNode( cm_traceWork_t *tw, cm_node_t *node ) {
55 cm_polygonRef_t *pref;
56 cm_brushRef_t *bref;
57
58 // position test
59 if ( tw->positionTest ) {
60 // if already stuck in solid
61 if ( tw->trace.fraction == 0.0f ) {
62 return;
63 }
64 // test if any of the trm vertices is inside a brush
65 for ( bref = node->brushes; bref; bref = bref->next ) {
66 if ( idCollisionModelManagerLocal::TestTrmVertsInBrush( tw, bref->b ) ) {
67 return;
68 }
69 }
70 // if just testing a point we're done
71 if ( tw->pointTrace ) {
72 return;
73 }
74 // test if the trm is stuck in any polygons
75 for ( pref = node->polygons; pref; pref = pref->next ) {
76 if ( idCollisionModelManagerLocal::TestTrmInPolygon( tw, pref->p ) ) {
77 return;
78 }
79 }
80 }
81 else if ( tw->rotation ) {
82 // rotate through all polygons in this leaf
83 for ( pref = node->polygons; pref; pref = pref->next ) {
84 if ( idCollisionModelManagerLocal::RotateTrmThroughPolygon( tw, pref->p ) ) {
85 return;
86 }
87 }
88 }
89 else {
90 // trace through all polygons in this leaf
91 for ( pref = node->polygons; pref; pref = pref->next ) {
92 if ( idCollisionModelManagerLocal::TranslateTrmThroughPolygon( tw, pref->p ) ) {
93 return;
94 }
95 }
96 }
97 }
98
99 /*
100 ================
101 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r
102 ================
103 */
104 //#define NO_SPATIAL_SUBDIVISION
105
TraceThroughAxialBSPTree_r(cm_traceWork_t * tw,cm_node_t * node,float p1f,float p2f,idVec3 & p1,idVec3 & p2)106 void idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( cm_traceWork_t *tw, cm_node_t *node, float p1f, float p2f, idVec3 &p1, idVec3 &p2) {
107 float t1, t2, offset;
108 float frac, frac2;
109 float idist;
110 idVec3 mid;
111 int side;
112 float midf;
113
114 if ( !node ) {
115 return;
116 }
117
118 if ( tw->quickExit ) {
119 return; // stop immediately
120 }
121
122 if ( tw->trace.fraction <= p1f ) {
123 return; // already hit something nearer
124 }
125
126 // if we need to test this node for collisions
127 if ( node->polygons || (tw->positionTest && node->brushes) ) {
128 // trace through node with collision data
129 idCollisionModelManagerLocal::TraceTrmThroughNode( tw, node );
130 }
131 // if already stuck in solid
132 if ( tw->positionTest && tw->trace.fraction == 0.0f ) {
133 return;
134 }
135 // if this is a leaf node
136 if ( node->planeType == -1 ) {
137 return;
138 }
139 #ifdef NO_SPATIAL_SUBDIVISION
140 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[0], p1f, p2f, p1, p2 );
141 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[1], p1f, p2f, p1, p2 );
142 return;
143 #endif
144 // distance from plane for trace start and end
145 t1 = p1[node->planeType] - node->planeDist;
146 t2 = p2[node->planeType] - node->planeDist;
147 // adjust the plane distance appropriately for mins/maxs
148 offset = tw->extents[node->planeType];
149 // see which sides we need to consider
150 if ( t1 >= offset && t2 >= offset ) {
151 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[0], p1f, p2f, p1, p2 );
152 return;
153 }
154
155 if ( t1 < -offset && t2 < -offset ) {
156 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[1], p1f, p2f, p1, p2 );
157 return;
158 }
159
160 if ( t1 < t2 ) {
161 idist = 1.0f / (t1-t2);
162 side = 1;
163 frac2 = (t1 + offset) * idist;
164 frac = (t1 - offset) * idist;
165 } else if (t1 > t2) {
166 idist = 1.0f / (t1-t2);
167 side = 0;
168 frac2 = (t1 - offset) * idist;
169 frac = (t1 + offset) * idist;
170 } else {
171 side = 0;
172 frac = 1.0f;
173 frac2 = 0.0f;
174 }
175
176 // move up to the node
177 if ( frac < 0.0f ) {
178 frac = 0.0f;
179 }
180 else if ( frac > 1.0f ) {
181 frac = 1.0f;
182 }
183
184 midf = p1f + (p2f - p1f)*frac;
185
186 mid[0] = p1[0] + frac*(p2[0] - p1[0]);
187 mid[1] = p1[1] + frac*(p2[1] - p1[1]);
188 mid[2] = p1[2] + frac*(p2[2] - p1[2]);
189
190 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[side], p1f, midf, p1, mid );
191
192
193 // go past the node
194 if ( frac2 < 0.0f ) {
195 frac2 = 0.0f;
196 }
197 else if ( frac2 > 1.0f ) {
198 frac2 = 1.0f;
199 }
200
201 midf = p1f + (p2f - p1f)*frac2;
202
203 mid[0] = p1[0] + frac2*(p2[0] - p1[0]);
204 mid[1] = p1[1] + frac2*(p2[1] - p1[1]);
205 mid[2] = p1[2] + frac2*(p2[2] - p1[2]);
206
207 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[side^1], midf, p2f, mid, p2 );
208 }
209
210 /*
211 ================
212 idCollisionModelManagerLocal::TraceThroughModel
213 ================
214 */
TraceThroughModel(cm_traceWork_t * tw)215 void idCollisionModelManagerLocal::TraceThroughModel( cm_traceWork_t *tw ) {
216 float d;
217 int i, numSteps;
218 idVec3 start, end;
219 idRotation rot;
220
221 if ( !tw->rotation ) {
222 // trace through spatial subdivision and then through leafs
223 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, tw->model->node, 0, 1, tw->start, tw->end );
224 }
225 else {
226 // approximate the rotation with a series of straight line movements
227 // total length covered along circle
228 d = tw->radius * DEG2RAD( tw->angle );
229 // if more than one step
230 if ( d > CIRCLE_APPROXIMATION_LENGTH ) {
231 // number of steps for the approximation
232 numSteps = (int) (CIRCLE_APPROXIMATION_LENGTH / d);
233 // start of approximation
234 start = tw->start;
235 // trace circle approximation steps through the BSP tree
236 for ( i = 0; i < numSteps; i++ ) {
237 // calculate next point on approximated circle
238 rot.Set( tw->origin, tw->axis, tw->angle * ((float) (i+1) / numSteps) );
239 end = start * rot;
240 // trace through spatial subdivision and then through leafs
241 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, tw->model->node, 0, 1, start, end );
242 // no need to continue if something was hit already
243 if ( tw->trace.fraction < 1.0f ) {
244 return;
245 }
246 start = end;
247 }
248 }
249 else {
250 start = tw->start;
251 }
252 // last step of the approximation
253 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, tw->model->node, 0, 1, start, tw->end );
254 }
255 }
256