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