doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tr_trace.cpp
Go to the documentation of this file.
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 #include "../idlib/precompiled.h"
30 #pragma hdrstop
31 
32 #include "tr_local.h"
33 
34 //#define TEST_TRACE
35 
36 /*
37 =================
38 R_LocalTrace
39 
40 If we resort the vertexes so all silverts come first, we can save some work here.
41 =================
42 */
43 localTrace_t R_LocalTrace( const idVec3 &start, const idVec3 &end, const float radius, const srfTriangles_t *tri ) {
44  int i, j;
45  byte * cullBits;
46  idPlane planes[4];
47  localTrace_t hit;
48  int c_testEdges, c_testPlanes, c_intersect;
49  idVec3 startDir;
50  byte totalOr;
51  float radiusSqr;
52 
53 #ifdef TEST_TRACE
54  idTimer trace_timer;
55  trace_timer.Start();
56 #endif
57 
58  hit.fraction = 1.0f;
59 
60  // create two planes orthogonal to each other that intersect along the trace
61  startDir = end - start;
62  startDir.Normalize();
63  startDir.NormalVectors( planes[0].Normal(), planes[1].Normal() );
64  planes[0][3] = - start * planes[0].Normal();
65  planes[1][3] = - start * planes[1].Normal();
66 
67  // create front and end planes so the trace is on the positive sides of both
68  planes[2] = startDir;
69  planes[2][3] = - start * planes[2].Normal();
70  planes[3] = -startDir;
71  planes[3][3] = - end * planes[3].Normal();
72 
73  // catagorize each point against the four planes
74  cullBits = (byte *) _alloca16( tri->numVerts );
75  SIMDProcessor->TracePointCull( cullBits, totalOr, radius, planes, tri->verts, tri->numVerts );
76 
77  // if we don't have points on both sides of both the ray planes, no intersection
78  if ( ( totalOr ^ ( totalOr >> 4 ) ) & 3 ) {
79  //common->Printf( "nothing crossed the trace planes\n" );
80  return hit;
81  }
82 
83  // if we don't have any points between front and end, no intersection
84  if ( ( totalOr ^ ( totalOr >> 1 ) ) & 4 ) {
85  //common->Printf( "trace didn't reach any triangles\n" );
86  return hit;
87  }
88 
89  // scan for triangles that cross both planes
90  c_testPlanes = 0;
91  c_testEdges = 0;
92  c_intersect = 0;
93 
94  radiusSqr = Square( radius );
95  startDir = end - start;
96 
97  if ( !tri->facePlanes || !tri->facePlanesCalculated ) {
98  R_DeriveFacePlanes( const_cast<srfTriangles_t *>( tri ) );
99  }
100 
101  for ( i = 0, j = 0; i < tri->numIndexes; i += 3, j++ ) {
102  float d1, d2, f, d;
103  float edgeLengthSqr;
104  idPlane * plane;
105  idVec3 point;
106  idVec3 dir[3];
107  idVec3 cross;
108  idVec3 edge;
109  byte triOr;
110 
111  // get sidedness info for the triangle
112  triOr = cullBits[ tri->indexes[i+0] ];
113  triOr |= cullBits[ tri->indexes[i+1] ];
114  triOr |= cullBits[ tri->indexes[i+2] ];
115 
116  // if we don't have points on both sides of both the ray planes, no intersection
117  if ( ( triOr ^ ( triOr >> 4 ) ) & 3 ) {
118  continue;
119  }
120 
121  // if we don't have any points between front and end, no intersection
122  if ( ( triOr ^ ( triOr >> 1 ) ) & 4 ) {
123  continue;
124  }
125 
126  c_testPlanes++;
127 
128  plane = &tri->facePlanes[j];
129  d1 = plane->Distance( start );
130  d2 = plane->Distance( end );
131 
132  if ( d1 <= d2 ) {
133  continue; // comning at it from behind or parallel
134  }
135 
136  if ( d1 < 0.0f ) {
137  continue; // starts past it
138  }
139 
140  if ( d2 > 0.0f ) {
141  continue; // finishes in front of it
142  }
143 
144  f = d1 / ( d1 - d2 );
145 
146  if ( f < 0.0f ) {
147  continue; // shouldn't happen
148  }
149 
150  if ( f >= hit.fraction ) {
151  continue; // have already hit something closer
152  }
153 
154  c_testEdges++;
155 
156  // find the exact point of impact with the plane
157  point = start + f * startDir;
158 
159  // see if the point is within the three edges
160  // if radius > 0 the triangle is expanded with a circle in the triangle plane
161 
162  dir[0] = tri->verts[ tri->indexes[i+0] ].xyz - point;
163  dir[1] = tri->verts[ tri->indexes[i+1] ].xyz - point;
164 
165  cross = dir[0].Cross( dir[1] );
166  d = plane->Normal() * cross;
167  if ( d > 0.0f ) {
168  if ( radiusSqr <= 0.0f ) {
169  continue;
170  }
171  edge = tri->verts[ tri->indexes[i+0] ].xyz - tri->verts[ tri->indexes[i+1] ].xyz;
172  edgeLengthSqr = edge.LengthSqr();
173  if ( cross.LengthSqr() > edgeLengthSqr * radiusSqr ) {
174  continue;
175  }
176  d = edge * dir[0];
177  if ( d < 0.0f ) {
178  edge = tri->verts[ tri->indexes[i+0] ].xyz - tri->verts[ tri->indexes[i+2] ].xyz;
179  d = edge * dir[0];
180  if ( d < 0.0f ) {
181  if ( dir[0].LengthSqr() > radiusSqr ) {
182  continue;
183  }
184  }
185  } else if ( d > edgeLengthSqr ) {
186  edge = tri->verts[ tri->indexes[i+1] ].xyz - tri->verts[ tri->indexes[i+2] ].xyz;
187  d = edge * dir[1];
188  if ( d < 0.0f ) {
189  if ( dir[1].LengthSqr() > radiusSqr ) {
190  continue;
191  }
192  }
193  }
194  }
195 
196  dir[2] = tri->verts[ tri->indexes[i+2] ].xyz - point;
197 
198  cross = dir[1].Cross( dir[2] );
199  d = plane->Normal() * cross;
200  if ( d > 0.0f ) {
201  if ( radiusSqr <= 0.0f ) {
202  continue;
203  }
204  edge = tri->verts[ tri->indexes[i+1] ].xyz - tri->verts[ tri->indexes[i+2] ].xyz;
205  edgeLengthSqr = edge.LengthSqr();
206  if ( cross.LengthSqr() > edgeLengthSqr * radiusSqr ) {
207  continue;
208  }
209  d = edge * dir[1];
210  if ( d < 0.0f ) {
211  edge = tri->verts[ tri->indexes[i+1] ].xyz - tri->verts[ tri->indexes[i+0] ].xyz;
212  d = edge * dir[1];
213  if ( d < 0.0f ) {
214  if ( dir[1].LengthSqr() > radiusSqr ) {
215  continue;
216  }
217  }
218  } else if ( d > edgeLengthSqr ) {
219  edge = tri->verts[ tri->indexes[i+2] ].xyz - tri->verts[ tri->indexes[i+0] ].xyz;
220  d = edge * dir[2];
221  if ( d < 0.0f ) {
222  if ( dir[2].LengthSqr() > radiusSqr ) {
223  continue;
224  }
225  }
226  }
227  }
228 
229  cross = dir[2].Cross( dir[0] );
230  d = plane->Normal() * cross;
231  if ( d > 0.0f ) {
232  if ( radiusSqr <= 0.0f ) {
233  continue;
234  }
235  edge = tri->verts[ tri->indexes[i+2] ].xyz - tri->verts[ tri->indexes[i+0] ].xyz;
236  edgeLengthSqr = edge.LengthSqr();
237  if ( cross.LengthSqr() > edgeLengthSqr * radiusSqr ) {
238  continue;
239  }
240  d = edge * dir[2];
241  if ( d < 0.0f ) {
242  edge = tri->verts[ tri->indexes[i+2] ].xyz - tri->verts[ tri->indexes[i+1] ].xyz;
243  d = edge * dir[2];
244  if ( d < 0.0f ) {
245  if ( dir[2].LengthSqr() > radiusSqr ) {
246  continue;
247  }
248  }
249  } else if ( d > edgeLengthSqr ) {
250  edge = tri->verts[ tri->indexes[i+0] ].xyz - tri->verts[ tri->indexes[i+1] ].xyz;
251  d = edge * dir[0];
252  if ( d < 0.0f ) {
253  if ( dir[0].LengthSqr() > radiusSqr ) {
254  continue;
255  }
256  }
257  }
258  }
259 
260  // we hit it
261  c_intersect++;
262 
263  hit.fraction = f;
264  hit.normal = plane->Normal();
265  hit.point = point;
266  hit.indexes[0] = tri->indexes[i];
267  hit.indexes[1] = tri->indexes[i+1];
268  hit.indexes[2] = tri->indexes[i+2];
269  }
270 
271 
272 #ifdef TEST_TRACE
273  trace_timer.Stop();
274  common->Printf( "testVerts:%i c_testPlanes:%i c_testEdges:%i c_intersect:%i msec:%1.4f\n",
275  tri->numVerts, c_testPlanes, c_testEdges, c_intersect, trace_timer.Milliseconds() );
276 #endif
277 
278  return hit;
279 }
280 
281 /*
282 =================
283 RB_DrawExpandedTriangles
284 =================
285 */
286 void RB_DrawExpandedTriangles( const srfTriangles_t *tri, const float radius, const idVec3 &vieworg ) {
287  int i, j, k;
288  idVec3 dir[6], normal, point;
289 
290  for ( i = 0; i < tri->numIndexes; i += 3 ) {
291 
292  idVec3 p[3] = { tri->verts[ tri->indexes[ i + 0 ] ].xyz, tri->verts[ tri->indexes[ i + 1 ] ].xyz, tri->verts[ tri->indexes[ i + 2 ] ].xyz };
293 
294  dir[0] = p[0] - p[1];
295  dir[1] = p[1] - p[2];
296  dir[2] = p[2] - p[0];
297 
298  normal = dir[0].Cross( dir[1] );
299 
300  if ( normal * p[0] < normal * vieworg ) {
301  continue;
302  }
303 
304  dir[0] = normal.Cross( dir[0] );
305  dir[1] = normal.Cross( dir[1] );
306  dir[2] = normal.Cross( dir[2] );
307 
308  dir[0].Normalize();
309  dir[1].Normalize();
310  dir[2].Normalize();
311 
312  qglBegin( GL_LINE_LOOP );
313 
314  for ( j = 0; j < 3; j++ ) {
315  k = ( j + 1 ) % 3;
316 
317  dir[4] = ( dir[j] + dir[k] ) * 0.5f;
318  dir[4].Normalize();
319 
320  dir[3] = ( dir[j] + dir[4] ) * 0.5f;
321  dir[3].Normalize();
322 
323  dir[5] = ( dir[4] + dir[k] ) * 0.5f;
324  dir[5].Normalize();
325 
326  point = p[k] + dir[j] * radius;
327  qglVertex3f( point[0], point[1], point[2] );
328 
329  point = p[k] + dir[3] * radius;
330  qglVertex3f( point[0], point[1], point[2] );
331 
332  point = p[k] + dir[4] * radius;
333  qglVertex3f( point[0], point[1], point[2] );
334 
335  point = p[k] + dir[5] * radius;
336  qglVertex3f( point[0], point[1], point[2] );
337 
338  point = p[k] + dir[k] * radius;
339  qglVertex3f( point[0], point[1], point[2] );
340  }
341 
342  qglEnd();
343  }
344 }
345 
346 /*
347 ================
348 RB_ShowTrace
349 
350 Debug visualization
351 ================
352 */
353 void RB_ShowTrace( drawSurf_t **drawSurfs, int numDrawSurfs ) {
354  int i;
355  const srfTriangles_t *tri;
356  const drawSurf_t *surf;
357  idVec3 start, end;
358  idVec3 localStart, localEnd;
359  localTrace_t hit;
360  float radius;
361 
362  if ( r_showTrace.GetInteger() == 0 ) {
363  return;
364  }
365 
366  if ( r_showTrace.GetInteger() == 2 ) {
367  radius = 5.0f;
368  } else {
369  radius = 0.0f;
370  }
371 
372  // determine the points of the trace
374  end = start + 4000 * backEnd.viewDef->renderView.viewaxis[0];
375 
376  // check and draw the surfaces
377  qglDisableClientState( GL_TEXTURE_COORD_ARRAY );
378  GL_TexEnv( GL_MODULATE );
379 
381 
382  // find how many are ambient
383  for ( i = 0 ; i < numDrawSurfs ; i++ ) {
384  surf = drawSurfs[i];
385  tri = surf->geo;
386 
387  if ( tri == NULL || tri->verts == NULL ) {
388  continue;
389  }
390 
391  // transform the points into local space
392  R_GlobalPointToLocal( surf->space->modelMatrix, start, localStart );
393  R_GlobalPointToLocal( surf->space->modelMatrix, end, localEnd );
394 
395  // check the bounding box
396  if ( !tri->bounds.Expand( radius ).LineIntersection( localStart, localEnd ) ) {
397  continue;
398  }
399 
401 
402  // highlight the surface
404 
405  qglColor4f( 1, 0, 0, 0.25 );
407 
408  // draw the bounding box
410 
411  qglColor4f( 1, 1, 1, 1 );
412  RB_DrawBounds( tri->bounds );
413 
414  if ( radius != 0.0f ) {
415  // draw the expanded triangles
416  qglColor4f( 0.5f, 0.5f, 1.0f, 1.0f );
417  RB_DrawExpandedTriangles( tri, radius, localStart );
418  }
419 
420  // check the exact surfaces
421  hit = R_LocalTrace( localStart, localEnd, radius, tri );
422  if ( hit.fraction < 1.0 ) {
423  qglColor4f( 1, 1, 1, 1 );
424  RB_DrawBounds( idBounds( hit.point ).Expand( 1 ) );
425  }
426  }
427 }
int indexes[3]
Definition: tr_local.h:1664
#define qglLoadMatrixf
Definition: qgl_linked.h:188
const srfTriangles_t * geo
Definition: tr_local.h:112
float Normalize(void)
Definition: Vector.h:646
void cross(float a[], float b[], float c[])
Definition: Model_lwo.cpp:3889
const idVec3 & Normal(void) const
Definition: Plane.h:239
#define qglDisableClientState
Definition: qgl_linked.h:93
int numVerts
Definition: Model.h:98
Definition: Timer.h:40
const int GLS_SRCBLEND_SRC_ALPHA
Definition: tr_local.h:1009
float Distance(const idVec3 &v) const
Definition: Plane.h:324
idVec3 xyz
Definition: DrawVert.h:42
idVec3 normal
Definition: tr_local.h:1663
#define qglBegin
Definition: qgl_linked.h:33
Definition: Vector.h:316
bool facePlanesCalculated
Definition: Model.h:93
const int GLS_DEPTHFUNC_ALWAYS
Definition: tr_local.h:1038
ID_INLINE T Square(T x)
Definition: Math.h:104
idPlane * facePlanes
Definition: Model.h:115
void Start(void)
Definition: Timer.h:144
double Milliseconds(void) const
Definition: Timer.h:191
idVec3 Cross(const idVec3 &a) const
Definition: Vector.h:619
const struct viewEntity_s * space
Definition: tr_local.h:113
int i
Definition: process.py:33
backEndState_t backEnd
Definition: tr_backend.cpp:35
idCVar r_showTrace("r_showTrace","0", CVAR_RENDERER|CVAR_INTEGER,"show the intersection of an eye trace with the world", idCmdSystem::ArgCompletion_Integer< 0, 2 >)
void RB_ShowTrace(drawSurf_t **drawSurfs, int numDrawSurfs)
Definition: tr_trace.cpp:353
void RB_DrawElementsImmediate(const srfTriangles_t *tri)
Definition: tr_render.cpp:49
GLuint GLuint end
Definition: glext.h:2845
idBounds bounds
Definition: Model.h:87
renderView_t renderView
Definition: tr_local.h:370
idCommon * common
Definition: Common.cpp:206
#define NULL
Definition: Lib.h:88
float fraction
Definition: tr_local.h:1660
void R_DeriveFacePlanes(srfTriangles_t *tri)
Definition: tr_trisurf.cpp:827
int GetInteger(void) const
Definition: CVarSystem.h:143
#define qglEnd
Definition: qgl_linked.h:103
idImageManager * globalImages
Definition: Image_init.cpp:74
idImage * whiteImage
Definition: Image.h:398
Definition: Plane.h:71
float LengthSqr(void) const
Definition: Vector.h:635
virtual void Printf(const char *fmt,...) id_attribute((format(printf
idBounds Expand(const float d) const
Definition: Bounds.h:317
float modelMatrix[16]
Definition: tr_local.h:360
idVec3 point
Definition: tr_local.h:1662
void Stop(void)
Definition: Timer.h:155
void R_GlobalPointToLocal(const float modelMatrix[16], const idVec3 &in, idVec3 &out)
Definition: tr_main.cpp:522
idVec3 vieworg
Definition: RenderWorld.h:215
virtual void VPCALL TracePointCull(byte *cullBits, byte &totalOr, const float radius, const idPlane *planes, const idDrawVert *verts, const int numVerts)=0
void RB_DrawExpandedTriangles(const srfTriangles_t *tri, const float radius, const idVec3 &vieworg)
Definition: tr_trace.cpp:286
const int GLS_DSTBLEND_ONE_MINUS_SRC_ALPHA
Definition: tr_local.h:1021
bool LineIntersection(const idVec3 &start, const idVec3 &end) const
Definition: Bounds.cpp:135
tuple f
Definition: idal.py:89
unsigned char byte
Definition: Lib.h:75
#define qglColor4f
Definition: qgl_linked.h:66
float modelViewMatrix[16]
Definition: tr_local.h:361
glIndex_t * indexes
Definition: Model.h:102
#define qglVertex3f
Definition: qgl_linked.h:349
void GL_State(int stateBits)
Definition: tr_backend.cpp:239
GLint j
Definition: qgl.h:264
int numIndexes
Definition: Model.h:101
localTrace_t R_LocalTrace(const idVec3 &start, const idVec3 &end, const float radius, const srfTriangles_t *tri)
Definition: tr_trace.cpp:43
GLfloat GLfloat p
Definition: glext.h:4674
idMat3 viewaxis
Definition: RenderWorld.h:216
void RB_DrawBounds(const idBounds &bounds)
void Bind()
void GL_TexEnv(int env)
Definition: tr_backend.cpp:196
void NormalVectors(idVec3 &left, idVec3 &down) const
Definition: Vector.h:727
GLuint start
Definition: glext.h:2845
idDrawVert * verts
Definition: Model.h:99
idSIMDProcessor * SIMDProcessor
Definition: Simd.cpp:43
const viewDef_t * viewDef
Definition: tr_local.h:641