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 "tools/compilers/aas/AASBuild_local.h"
32
33 /*
34 ============
35 idAASBuild::SetPortalFlags_r
36 ============
37 */
SetPortalFlags_r(idBrushBSPNode * node)38 void idAASBuild::SetPortalFlags_r( idBrushBSPNode *node ) {
39 int s;
40 idBrushBSPPortal *p;
41 idVec3 normal;
42
43 if ( !node ) {
44 return;
45 }
46
47 if ( node->GetContents() & AREACONTENTS_SOLID ) {
48 return;
49 }
50
51 if ( !node->GetChild(0) && !node->GetChild(1) ) {
52 for ( p = node->GetPortals(); p; p = p->Next(s) ) {
53 s = (p->GetNode(1) == node);
54
55 // if solid at the other side of the portal
56 if ( p->GetNode(!s)->GetContents() & AREACONTENTS_SOLID ) {
57 if ( s ) {
58 normal = -p->GetPlane().Normal();
59 }
60 else {
61 normal = p->GetPlane().Normal();
62 }
63 if ( normal * aasSettings->invGravityDir > aasSettings->minFloorCos ) {
64 p->SetFlag( FACE_FLOOR );
65 }
66 else {
67 p->SetFlag( FACE_SOLID );
68 }
69 }
70 }
71 return;
72 }
73
74 SetPortalFlags_r( node->GetChild(0) );
75 SetPortalFlags_r( node->GetChild(1) );
76 }
77
78 /*
79 ============
80 idAASBuild::PortalIsGap
81 ============
82 */
PortalIsGap(idBrushBSPPortal * portal,int side)83 bool idAASBuild::PortalIsGap( idBrushBSPPortal *portal, int side ) {
84 idVec3 normal;
85
86 // if solid at the other side of the portal
87 if ( portal->GetNode(!side)->GetContents() & AREACONTENTS_SOLID ) {
88 return false;
89 }
90
91 if ( side ) {
92 normal = -(portal->GetPlane().Normal());
93 }
94 else {
95 normal = portal->GetPlane().Normal();
96 }
97 if ( normal * aasSettings->invGravityDir > aasSettings->minFloorCos ) {
98 return true;
99 }
100 return false;
101 }
102
103 /*
104 ============
105 idAASBuild::GravSubdivLeafNode
106 ============
107 */
108 #define FACE_CHECKED BIT(31)
109 #define GRAVSUBDIV_EPSILON 0.1f
110
GravSubdivLeafNode(idBrushBSPNode * node)111 void idAASBuild::GravSubdivLeafNode( idBrushBSPNode *node ) {
112 int s1, s2, i, j, k, side1;
113 int numSplits, numSplitters;
114 idBrushBSPPortal *p1, *p2;
115 idWinding *w1, *w2;
116 idVec3 normal;
117 idPlane plane;
118 idPlaneSet planeList;
119 float d, min, max;
120 int *splitterOrder;
121 int *bestNumSplits;
122 int floor, gap, numFloorChecked;
123
124 // if this leaf node is already classified it cannot have a combination of floor and gap portals
125 if ( node->GetFlags() & (AREA_FLOOR|AREA_GAP) ) {
126 return;
127 }
128
129 floor = gap = 0;
130
131 // check if the area has a floor
132 for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
133 s1 = (p1->GetNode(1) == node);
134
135 if ( p1->GetFlags() & FACE_FLOOR ) {
136 floor++;
137 }
138 }
139
140 // find seperating planes between gap and floor portals
141 for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
142 s1 = (p1->GetNode(1) == node);
143
144 // if the portal is a gap seen from this side
145 if ( PortalIsGap( p1, s1 ) ) {
146 gap++;
147 // if the area doesn't have a floor
148 if ( !floor ) {
149 break;
150 }
151 }
152 else {
153 continue;
154 }
155
156 numFloorChecked = 0;
157
158 w1 = p1->GetWinding();
159
160 // test all edges of the gap
161 for ( i = 0; i < w1->GetNumPoints(); i++ ) {
162
163 // create a plane through the edge of the gap parallel to the direction of gravity
164 normal = (*w1)[(i+1)%w1->GetNumPoints()].ToVec3() - (*w1)[i].ToVec3();
165 normal = normal.Cross( aasSettings->invGravityDir );
166 if ( normal.Normalize() < 0.2f ) {
167 continue;
168 }
169 plane.SetNormal( normal );
170 plane.FitThroughPoint( (*w1)[i].ToVec3() );
171
172 // get the side of the plane the gap is on
173 side1 = w1->PlaneSide( plane, GRAVSUBDIV_EPSILON );
174 if ( side1 == SIDE_ON ) {
175 break;
176 }
177
178 // test if the plane through the edge of the gap seperates the gap from a floor portal
179 for ( p2 = node->GetPortals(); p2; p2 = p2->Next(s2) ) {
180 s2 = (p2->GetNode(1) == node);
181
182 if ( !( p2->GetFlags() & FACE_FLOOR ) ) {
183 continue;
184 }
185
186 if ( p2->GetFlags() & FACE_CHECKED ) {
187 continue;
188 }
189
190 w2 = p2->GetWinding();
191
192 min = 2.0f * GRAVSUBDIV_EPSILON;
193 max = GRAVSUBDIV_EPSILON;
194 if ( side1 == SIDE_FRONT ) {
195 for ( j = 0; j < w2->GetNumPoints(); j++ ) {
196 d = plane.Distance( (*w2)[j].ToVec3() );
197 if ( d >= GRAVSUBDIV_EPSILON ) {
198 break; // point at the same side of the plane as the gap
199 }
200 d = idMath::Fabs( d );
201 if ( d < min ) {
202 min = d;
203 }
204 if ( d > max ) {
205 max = d;
206 }
207 }
208 }
209 else {
210 for ( j = 0; j < w2->GetNumPoints(); j++ ) {
211 d = plane.Distance( (*w2)[j].ToVec3() );
212 if ( d <= -GRAVSUBDIV_EPSILON ) {
213 break; // point at the same side of the plane as the gap
214 }
215 d = idMath::Fabs( d );
216 if ( d < min ) {
217 min = d;
218 }
219 if ( d > max ) {
220 max = d;
221 }
222 }
223 }
224
225 // a point of the floor portal was found to be at the same side of the plane as the gap
226 if ( j < w2->GetNumPoints() ) {
227 continue;
228 }
229
230 // if the floor portal touches the plane
231 if ( min < GRAVSUBDIV_EPSILON && max > GRAVSUBDIV_EPSILON ) {
232 planeList.FindPlane( plane, 0.00001f, 0.1f );
233 }
234
235 p2->SetFlag( FACE_CHECKED );
236 numFloorChecked++;
237
238 }
239 if ( numFloorChecked == floor ) {
240 break;
241 }
242 }
243
244 for ( p2 = node->GetPortals(); p2; p2 = p2->Next(s2) ) {
245 s2 = (p2->GetNode(1) == node);
246 p2->RemoveFlag( FACE_CHECKED );
247 }
248 }
249
250 // if the leaf node does not have both floor and gap portals
251 if ( !( gap && floor) ) {
252 if ( floor ) {
253 node->SetFlag( AREA_FLOOR );
254 }
255 else if ( gap ) {
256 node->SetFlag( AREA_GAP );
257 }
258 return;
259 }
260
261 // if no valid seperators found
262 if ( planeList.Num() == 0 ) {
263 // NOTE: this should never happend, if it does the leaf node has degenerate portals
264 return;
265 }
266
267 splitterOrder = (int *) _alloca( planeList.Num() * sizeof( int ) );
268 bestNumSplits = (int *) _alloca( planeList.Num() * sizeof( int ) );
269 numSplitters = 0;
270
271 // test all possible seperators and sort them from best to worst
272 for ( i = 0; i < planeList.Num(); i += 2 ) {
273 numSplits = 0;
274
275 for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
276 s1 = (p1->GetNode(1) == node);
277 if ( p1->GetWinding()->PlaneSide( planeList[i], 0.1f ) == SIDE_CROSS ) {
278 numSplits++;
279 }
280 }
281
282 for ( j = 0; j < numSplitters; j++ ) {
283 if ( numSplits < bestNumSplits[j] ) {
284 for ( k = numSplitters; k > j; k-- ) {
285 bestNumSplits[k] = bestNumSplits[k-1];
286 splitterOrder[k] = splitterOrder[k-1];
287 }
288 bestNumSplits[j] = numSplits;
289 splitterOrder[j] = i;
290 numSplitters++;
291 break;
292 }
293 }
294 if ( j >= numSplitters ) {
295 bestNumSplits[j] = numSplits;
296 splitterOrder[j] = i;
297 numSplitters++;
298 }
299 }
300
301 // try all seperators in order from best to worst
302 for ( i = 0; i < numSplitters; i++ ) {
303 if ( node->Split( planeList[splitterOrder[i]], -1 ) ) {
304 // we found a seperator that works
305 break;
306 }
307 }
308 if ( i >= numSplitters) {
309 return;
310 }
311
312 DisplayRealTimeString( "\r%6d", ++numGravitationalSubdivisions );
313
314 // test children for further splits
315 GravSubdivLeafNode( node->GetChild(0) );
316 GravSubdivLeafNode( node->GetChild(1) );
317 }
318
319 /*
320 ============
321 idAASBuild::GravSubdiv_r
322 ============
323 */
GravSubdiv_r(idBrushBSPNode * node)324 void idAASBuild::GravSubdiv_r( idBrushBSPNode *node ) {
325
326 if ( !node ) {
327 return;
328 }
329
330 if ( node->GetContents() & AREACONTENTS_SOLID ) {
331 return;
332 }
333
334 if ( !node->GetChild(0) && !node->GetChild(1) ) {
335 GravSubdivLeafNode( node );
336 return;
337 }
338
339 GravSubdiv_r( node->GetChild(0) );
340 GravSubdiv_r( node->GetChild(1) );
341 }
342
343 /*
344 ============
345 idAASBuild::GravitationalSubdivision
346 ============
347 */
GravitationalSubdivision(idBrushBSP & bsp)348 void idAASBuild::GravitationalSubdivision( idBrushBSP &bsp ) {
349 numGravitationalSubdivisions = 0;
350
351 common->Printf( "[Gravitational Subdivision]\n" );
352
353 SetPortalFlags_r( bsp.GetRootNode() );
354 GravSubdiv_r( bsp.GetRootNode() );
355
356 common->Printf( "\r%6d subdivisions\n", numGravitationalSubdivisions );
357 }
358