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 #include "idlib/Timer.h"
39 #include "framework/Common.h"
40 #include "framework/Session.h"
41 #include "renderer/Material.h"
42 #include "renderer/RenderWorld.h"
43 #include "sys/sys_public.h"
44
45 #include "cm/CollisionModel_local.h"
46
47 /*
48 ===============================================================================
49
50 Visualisation code
51
52 ===============================================================================
53 */
54
55 const char *cm_contentsNameByIndex[] = {
56 "none", // 0
57 "solid", // 1
58 "opaque", // 2
59 "water", // 3
60 "playerclip", // 4
61 "monsterclip", // 5
62 "moveableclip", // 6
63 "ikclip", // 7
64 "blood", // 8
65 "body", // 9
66 "corpse", // 10
67 "trigger", // 11
68 "aas_solid", // 12
69 "aas_obstacle", // 13
70 "flashlight_trigger", // 14
71 NULL
72 };
73
74 int cm_contentsFlagByIndex[] = {
75 -1, // 0
76 CONTENTS_SOLID, // 1
77 CONTENTS_OPAQUE, // 2
78 CONTENTS_WATER, // 3
79 CONTENTS_PLAYERCLIP, // 4
80 CONTENTS_MONSTERCLIP, // 5
81 CONTENTS_MOVEABLECLIP, // 6
82 CONTENTS_IKCLIP, // 7
83 CONTENTS_BLOOD, // 8
84 CONTENTS_BODY, // 9
85 CONTENTS_CORPSE, // 10
86 CONTENTS_TRIGGER, // 11
87 CONTENTS_AAS_SOLID, // 12
88 CONTENTS_AAS_OBSTACLE, // 13
89 CONTENTS_FLASHLIGHT_TRIGGER, // 14
90 0
91 };
92
93 idCVar cm_drawMask( "cm_drawMask", "none", CVAR_GAME, "collision mask", cm_contentsNameByIndex, idCmdSystem::ArgCompletion_String<cm_contentsNameByIndex> );
94 idCVar cm_drawColor( "cm_drawColor", "1 0 0 .5", CVAR_GAME, "color used to draw the collision models" );
95 idCVar cm_drawFilled( "cm_drawFilled", "0", CVAR_GAME | CVAR_BOOL, "draw filled polygons" );
96 idCVar cm_drawInternal( "cm_drawInternal", "1", CVAR_GAME | CVAR_BOOL, "draw internal edges green" );
97 idCVar cm_drawNormals( "cm_drawNormals", "0", CVAR_GAME | CVAR_BOOL, "draw polygon and edge normals" );
98 idCVar cm_backFaceCull( "cm_backFaceCull", "0", CVAR_GAME | CVAR_BOOL, "cull back facing polygons" );
99 idCVar cm_debugCollision( "cm_debugCollision", "0", CVAR_GAME | CVAR_BOOL, "debug the collision detection" );
100
101 static idVec4 cm_color;
102
103 /*
104 ================
105 idCollisionModelManagerLocal::ContentsFromString
106 ================
107 */
ContentsFromString(const char * string) const108 int idCollisionModelManagerLocal::ContentsFromString( const char *string ) const {
109 int i, contents = 0;
110 idLexer src( string, idStr::Length( string ), "ContentsFromString" );
111 idToken token;
112
113 while( src.ReadToken( &token ) ) {
114 if ( token == "," ) {
115 continue;
116 }
117 for ( i = 1; cm_contentsNameByIndex[i] != NULL; i++ ) {
118 if ( token.Icmp( cm_contentsNameByIndex[i] ) == 0 ) {
119 contents |= cm_contentsFlagByIndex[i];
120 break;
121 }
122 }
123 }
124
125 return contents;
126 }
127
128 /*
129 ================
130 idCollisionModelManagerLocal::StringFromContents
131 ================
132 */
StringFromContents(const int contents) const133 const char *idCollisionModelManagerLocal::StringFromContents( const int contents ) const {
134 int i, length = 0;
135 static char contentsString[MAX_STRING_CHARS];
136
137 contentsString[0] = '\0';
138
139 for ( i = 1; cm_contentsFlagByIndex[i] != 0; i++ ) {
140 if ( contents & cm_contentsFlagByIndex[i] ) {
141 if ( length != 0 ) {
142 length += idStr::snPrintf( contentsString + length, sizeof( contentsString ) - length, "," );
143 }
144 length += idStr::snPrintf( contentsString + length, sizeof( contentsString ) - length, cm_contentsNameByIndex[i] );
145 }
146 }
147
148 return contentsString;
149 }
150
151 /*
152 ================
153 idCollisionModelManagerLocal::DrawEdge
154 ================
155 */
DrawEdge(cm_model_t * model,int edgeNum,const idVec3 & origin,const idMat3 & axis)156 void idCollisionModelManagerLocal::DrawEdge( cm_model_t *model, int edgeNum, const idVec3 &origin, const idMat3 &axis ) {
157 int side;
158 cm_edge_t *edge;
159 idVec3 start, end, mid;
160 bool isRotated;
161
162 isRotated = axis.IsRotated();
163
164 edge = model->edges + abs(edgeNum);
165 side = edgeNum < 0;
166
167 start = model->vertices[edge->vertexNum[side]].p;
168 end = model->vertices[edge->vertexNum[!side]].p;
169 if ( isRotated ) {
170 start *= axis;
171 end *= axis;
172 }
173 start += origin;
174 end += origin;
175
176 if ( edge->internal ) {
177 if ( cm_drawInternal.GetBool() ) {
178 session->rw->DebugArrow( colorGreen, start, end, 1 );
179 }
180 } else {
181 if ( edge->numUsers > 2 ) {
182 session->rw->DebugArrow( colorBlue, start, end, 1 );
183 } else {
184 session->rw->DebugArrow( cm_color, start, end, 1 );
185 }
186 }
187
188 if ( cm_drawNormals.GetBool() ) {
189 mid = (start + end) * 0.5f;
190 if ( isRotated ) {
191 end = mid + 5 * (axis * edge->normal);
192 } else {
193 end = mid + 5 * edge->normal;
194 }
195 session->rw->DebugArrow( colorCyan, mid, end, 1 );
196 }
197 }
198
199 /*
200 ================
201 idCollisionModelManagerLocal::DrawPolygon
202 ================
203 */
DrawPolygon(cm_model_t * model,cm_polygon_t * p,const idVec3 & origin,const idMat3 & axis,const idVec3 & viewOrigin)204 void idCollisionModelManagerLocal::DrawPolygon( cm_model_t *model, cm_polygon_t *p, const idVec3 &origin, const idMat3 &axis, const idVec3 &viewOrigin ) {
205 int i, edgeNum;
206 cm_edge_t *edge;
207 idVec3 center, end, dir;
208
209 if ( cm_backFaceCull.GetBool() ) {
210 edgeNum = p->edges[0];
211 edge = model->edges + abs(edgeNum);
212 dir = model->vertices[edge->vertexNum[0]].p - viewOrigin;
213 if ( dir * p->plane.Normal() > 0.0f ) {
214 return;
215 }
216 }
217
218 if ( cm_drawNormals.GetBool() ) {
219 center = vec3_origin;
220 for ( i = 0; i < p->numEdges; i++ ) {
221 edgeNum = p->edges[i];
222 edge = model->edges + abs(edgeNum);
223 center += model->vertices[edge->vertexNum[edgeNum < 0]].p;
224 }
225 center *= (1.0f / p->numEdges);
226 if ( axis.IsRotated() ) {
227 center = center * axis + origin;
228 end = center + 5 * (axis * p->plane.Normal());
229 } else {
230 center += origin;
231 end = center + 5 * p->plane.Normal();
232 }
233 session->rw->DebugArrow( colorMagenta, center, end, 1 );
234 }
235
236 if ( cm_drawFilled.GetBool() ) {
237 idFixedWinding winding;
238 for ( i = p->numEdges - 1; i >= 0; i-- ) {
239 edgeNum = p->edges[i];
240 edge = model->edges + abs(edgeNum);
241 winding += origin + model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p * axis;
242 }
243 session->rw->DebugPolygon( cm_color, winding );
244 } else {
245 for ( i = 0; i < p->numEdges; i++ ) {
246 edgeNum = p->edges[i];
247 edge = model->edges + abs(edgeNum);
248 if ( edge->checkcount == checkCount ) {
249 continue;
250 }
251 edge->checkcount = checkCount;
252 DrawEdge( model, edgeNum, origin, axis );
253 }
254 }
255 }
256
257 /*
258 ================
259 idCollisionModelManagerLocal::DrawNodePolygons
260 ================
261 */
DrawNodePolygons(cm_model_t * model,cm_node_t * node,const idVec3 & origin,const idMat3 & axis,const idVec3 & viewOrigin,const float radius)262 void idCollisionModelManagerLocal::DrawNodePolygons( cm_model_t *model, cm_node_t *node,
263 const idVec3 &origin, const idMat3 &axis,
264 const idVec3 &viewOrigin, const float radius ) {
265 int i;
266 cm_polygon_t *p;
267 cm_polygonRef_t *pref;
268
269 while (1) {
270 for ( pref = node->polygons; pref; pref = pref->next ) {
271 p = pref->p;
272 if ( radius ) {
273 // polygon bounds should overlap with trace bounds
274 for ( i = 0; i < 3; i++ ) {
275 if ( p->bounds[0][i] > viewOrigin[i] + radius ) {
276 break;
277 }
278 if ( p->bounds[1][i] < viewOrigin[i] - radius ) {
279 break;
280 }
281 }
282 if ( i < 3 ) {
283 continue;
284 }
285 }
286 if ( p->checkcount == checkCount ) {
287 continue;
288 }
289 if ( !( p->contents & cm_contentsFlagByIndex[cm_drawMask.GetInteger()] ) ) {
290 continue;
291 }
292
293 DrawPolygon( model, p, origin, axis, viewOrigin );
294 p->checkcount = checkCount;
295 }
296 if ( node->planeType == -1 ) {
297 break;
298 }
299 if ( radius && viewOrigin[node->planeType] > node->planeDist + radius ) {
300 node = node->children[0];
301 } else if ( radius && viewOrigin[node->planeType] < node->planeDist - radius ) {
302 node = node->children[1];
303 } else {
304 DrawNodePolygons( model, node->children[1], origin, axis, viewOrigin, radius );
305 node = node->children[0];
306 }
307 }
308 }
309
310 /*
311 ================
312 idCollisionModelManagerLocal::DrawModel
313 ================
314 */
DrawModel(cmHandle_t handle,const idVec3 & modelOrigin,const idMat3 & modelAxis,const idVec3 & viewOrigin,const float radius)315 void idCollisionModelManagerLocal::DrawModel( cmHandle_t handle, const idVec3 &modelOrigin, const idMat3 &modelAxis,
316 const idVec3 &viewOrigin, const float radius ) {
317
318 cm_model_t *model;
319 idVec3 viewPos;
320
321 if ( handle < 0 && handle >= numModels ) {
322 return;
323 }
324
325 if ( cm_drawColor.IsModified() ) {
326 sscanf( cm_drawColor.GetString(), "%f %f %f %f", &cm_color.x, &cm_color.y, &cm_color.z, &cm_color.w );
327 cm_drawColor.ClearModified();
328 }
329
330 model = models[ handle ];
331 viewPos = (viewOrigin - modelOrigin) * modelAxis.Transpose();
332 checkCount++;
333 DrawNodePolygons( model, model->node, modelOrigin, modelAxis, viewPos, radius );
334 }
335
336 /*
337 ===============================================================================
338
339 Speed test code
340
341 ===============================================================================
342 */
343
344 static idCVar cm_testCollision( "cm_testCollision", "0", CVAR_GAME | CVAR_BOOL, "" );
345 static idCVar cm_testRotation( "cm_testRotation", "1", CVAR_GAME | CVAR_BOOL, "" );
346 static idCVar cm_testModel( "cm_testModel", "0", CVAR_GAME | CVAR_INTEGER, "" );
347 static idCVar cm_testTimes( "cm_testTimes", "1000", CVAR_GAME | CVAR_INTEGER, "" );
348 static idCVar cm_testRandomMany( "cm_testRandomMany", "0", CVAR_GAME | CVAR_BOOL, "" );
349 static idCVar cm_testOrigin( "cm_testOrigin", "0 0 0", CVAR_GAME, "" );
350 static idCVar cm_testReset( "cm_testReset", "0", CVAR_GAME | CVAR_BOOL, "" );
351 static idCVar cm_testBox( "cm_testBox", "-16 -16 0 16 16 64", CVAR_GAME, "" );
352 static idCVar cm_testBoxRotation( "cm_testBoxRotation", "0 0 0", CVAR_GAME, "" );
353 static idCVar cm_testWalk( "cm_testWalk", "1", CVAR_GAME | CVAR_BOOL, "" );
354 static idCVar cm_testLength( "cm_testLength", "1024", CVAR_GAME | CVAR_FLOAT, "" );
355 static idCVar cm_testRadius( "cm_testRadius", "64", CVAR_GAME | CVAR_FLOAT, "" );
356 static idCVar cm_testAngle( "cm_testAngle", "60", CVAR_GAME | CVAR_FLOAT, "" );
357
358 static unsigned int total_translation;
359 static unsigned int min_translation = 999999;
360 static unsigned int max_translation = 0;
361 static int num_translation = 0;
362 static unsigned int total_rotation;
363 static unsigned int min_rotation = 999999;
364 static unsigned int max_rotation = 0;
365 static int num_rotation = 0;
366 static idVec3 start;
367 static idVec3 *testend;
368
DebugOutput(const idVec3 & origin)369 void idCollisionModelManagerLocal::DebugOutput( const idVec3 &origin ) {
370 int i, k;
371 unsigned int t;
372 char buf[128];
373 idVec3 end;
374 idAngles boxAngles;
375 idMat3 modelAxis, boxAxis;
376 idBounds bounds;
377 trace_t trace;
378
379 if ( !cm_testCollision.GetBool() ) {
380 return;
381 }
382
383 testend = (idVec3 *) Mem_Alloc( cm_testTimes.GetInteger() * sizeof(idVec3) );
384
385 if ( cm_testReset.GetBool() || ( cm_testWalk.GetBool() && !start.Compare( start ) ) ) {
386 total_translation = total_rotation = 0;
387 min_translation = min_rotation = 999999;
388 max_translation = max_rotation = 0;
389 num_translation = num_rotation = 0;
390 cm_testReset.SetBool( false );
391 }
392
393 if ( cm_testWalk.GetBool() ) {
394 start = origin;
395 cm_testOrigin.SetString( va( "%1.2f %1.2f %1.2f", start[0], start[1], start[2] ) );
396 } else {
397 sscanf( cm_testOrigin.GetString(), "%f %f %f", &start[0], &start[1], &start[2] );
398 }
399
400 sscanf( cm_testBox.GetString(), "%f %f %f %f %f %f", &bounds[0][0], &bounds[0][1], &bounds[0][2],
401 &bounds[1][0], &bounds[1][1], &bounds[1][2] );
402 sscanf( cm_testBoxRotation.GetString(), "%f %f %f", &boxAngles[0], &boxAngles[1], &boxAngles[2] );
403 boxAxis = boxAngles.ToMat3();
404 modelAxis.Identity();
405
406 idTraceModel itm( bounds );
407 idRandom random( 0 );
408 idTimer timer;
409
410 if ( cm_testRandomMany.GetBool() ) {
411 // if many traces in one random direction
412 for ( i = 0; i < 3; i++ ) {
413 testend[0][i] = start[i] + random.CRandomFloat() * cm_testLength.GetFloat();
414 }
415 for ( k = 1; k < cm_testTimes.GetInteger(); k++ ) {
416 testend[k] = testend[0];
417 }
418 } else {
419 // many traces each in a different random direction
420 for ( k = 0; k < cm_testTimes.GetInteger(); k++ ) {
421 for ( i = 0; i < 3; i++ ) {
422 testend[k][i] = start[i] + random.CRandomFloat() * cm_testLength.GetFloat();
423 }
424 }
425 }
426
427 // translational collision detection
428 timer.Clear();
429 timer.Start();
430 for ( i = 0; i < cm_testTimes.GetInteger(); i++ ) {
431 Translation( &trace, start, testend[i], &itm, boxAxis, CONTENTS_SOLID|CONTENTS_PLAYERCLIP, cm_testModel.GetInteger(), vec3_origin, modelAxis );
432 }
433 timer.Stop();
434 t = timer.Milliseconds();
435 if ( t < min_translation ) min_translation = t;
436 if ( t > max_translation ) max_translation = t;
437 num_translation++;
438 total_translation += t;
439 if ( cm_testTimes.GetInteger() > 9999 ) {
440 sprintf( buf, "%3dK", (int ) ( cm_testTimes.GetInteger() / 1000 ) );
441 } else {
442 sprintf( buf, "%4d", cm_testTimes.GetInteger() );
443 }
444 common->Printf("%s translations: %4u milliseconds, (min = %u, max = %u, av = %1.1f)\n", buf, t, min_translation, max_translation, (float) total_translation / num_translation );
445
446 if ( cm_testRandomMany.GetBool() ) {
447 // if many traces in one random direction
448 for ( i = 0; i < 3; i++ ) {
449 testend[0][i] = start[i] + random.CRandomFloat() * cm_testRadius.GetFloat();
450 }
451 for ( k = 1; k < cm_testTimes.GetInteger(); k++ ) {
452 testend[k] = testend[0];
453 }
454 } else {
455 // many traces each in a different random direction
456 for ( k = 0; k < cm_testTimes.GetInteger(); k++ ) {
457 for ( i = 0; i < 3; i++ ) {
458 testend[k][i] = start[i] + random.CRandomFloat() * cm_testRadius.GetFloat();
459 }
460 }
461 }
462
463 if ( cm_testRotation.GetBool() ) {
464 // rotational collision detection
465 idVec3 vec( random.CRandomFloat(), random.CRandomFloat(), random.RandomFloat() );
466 vec.Normalize();
467 idRotation rotation( vec3_origin, vec, cm_testAngle.GetFloat() );
468
469 timer.Clear();
470 timer.Start();
471 for ( i = 0; i < cm_testTimes.GetInteger(); i++ ) {
472 rotation.SetOrigin( testend[i] );
473 Rotation( &trace, start, rotation, &itm, boxAxis, CONTENTS_SOLID|CONTENTS_PLAYERCLIP, cm_testModel.GetInteger(), vec3_origin, modelAxis );
474 }
475 timer.Stop();
476 t = timer.Milliseconds();
477 if ( t < min_rotation ) min_rotation = t;
478 if ( t > max_rotation ) max_rotation = t;
479 num_rotation++;
480 total_rotation += t;
481 if ( cm_testTimes.GetInteger() > 9999 ) {
482 sprintf( buf, "%3dK", (int ) ( cm_testTimes.GetInteger() / 1000 ) );
483 } else {
484 sprintf( buf, "%4d", cm_testTimes.GetInteger() );
485 }
486 common->Printf("%s rotation: %4d milliseconds, (min = %d, max = %d, av = %1.1f)\n", buf, t, min_rotation, max_rotation, (float) total_rotation / num_rotation );
487 }
488
489 Mem_Free( testend );
490 testend = NULL;
491 }
492