1 #include "csg.h"
2
3 vec_t g_BrushUnionThreshold = DEFAULT_BRUSH_UNION_THRESHOLD;
4
NewWindingFromPlane(const brushhull_t * const hull,const int planenum)5 static Winding* NewWindingFromPlane(const brushhull_t* const hull, const int planenum)
6 {
7 Winding* winding;
8 Winding* front;
9 Winding* back;
10 bface_t* face;
11 plane_t* plane;
12
13 plane = &g_mapplanes[planenum];
14 winding = new Winding(plane->normal, plane->dist);
15
16 for (face = hull->faces; face; face = face->next)
17 {
18 plane = &g_mapplanes[face->planenum];
19 winding->Clip(plane->normal, plane->dist, &front, &back);
20 delete winding;
21
22 if (front)
23 {
24 delete front;
25 }
26 if (back)
27 {
28 winding = back;
29 }
30 else
31 {
32 Developer(DEVELOPER_LEVEL_ERROR, "NewFaceFromPlane returning NULL");
33 return NULL;
34 }
35 }
36
37 return winding;
38 }
39
AddFaceToList(bface_t ** head,bface_t * newface)40 static void AddFaceToList(bface_t** head, bface_t* newface)
41 {
42 hlassert(newface);
43 hlassert(newface->w);
44 if (!*head)
45 {
46 *head = newface;
47 return;
48 }
49 else
50 {
51 bface_t* node = *head;
52
53 while (node->next)
54 {
55 node = node->next;
56 }
57 node->next = newface;
58 newface->next = NULL;
59 }
60 }
61
NumberOfHullFaces(const brushhull_t * const hull)62 static int NumberOfHullFaces(const brushhull_t* const hull)
63 {
64 int x;
65 bface_t* face;
66
67 if (!hull->faces)
68 {
69 return 0;
70 }
71
72 for (x = 0, face = hull->faces; face; face = face->next, x++)
73 { // counter
74 }
75
76 return x;
77 }
78
79 // Returns false if union of brushes is obviously zero
AddPlaneToUnion(brushhull_t * hull,const int planenum)80 static void AddPlaneToUnion(brushhull_t* hull, const int planenum)
81 {
82 bool need_new_face = false;
83
84 bface_t* new_face_list;
85
86 bface_t* face;
87 bface_t* next;
88
89 plane_t* split;
90 Winding* front;
91 Winding* back;
92
93 new_face_list = NULL;
94
95 next = NULL;
96
97 hlassert(hull);
98
99 if (!hull->faces)
100 {
101 return;
102 }
103 hlassert(hull->faces->w);
104
105 for (face = hull->faces; face; face = next)
106 {
107 hlassert(face->w);
108 next = face->next;
109
110 // Duplicate plane, ignore
111 if (face->planenum == planenum)
112 {
113 AddFaceToList(&new_face_list, CopyFace(face));
114 continue;
115 }
116
117 split = &g_mapplanes[planenum];
118 face->w->Clip(split->normal, split->dist, &front, &back);
119
120 if (front)
121 {
122 delete front;
123 need_new_face = true;
124
125 if (back)
126 { // Intersected the face
127 delete face->w;
128 face->w = back;
129 AddFaceToList(&new_face_list, CopyFace(face));
130 }
131 }
132 else
133 {
134 // Completely missed it, back is identical to face->w so it is destroyed
135 if (back)
136 {
137 delete back;
138 AddFaceToList(&new_face_list, CopyFace(face));
139 }
140 }
141 hlassert(face->w);
142 }
143
144 FreeFaceList(hull->faces);
145 hull->faces = new_face_list;
146
147 if (need_new_face && (NumberOfHullFaces(hull) > 2))
148 {
149 Winding* new_winding = NewWindingFromPlane(hull, planenum);
150
151 if (new_winding)
152 {
153 bface_t* new_face = (bface_t*)Alloc(sizeof(bface_t));
154
155 new_face->planenum = planenum;
156 new_face->w = new_winding;
157
158 new_face->next = hull->faces;
159 hull->faces = new_face;
160 }
161 }
162 }
163
CalculateSolidVolume(const brushhull_t * const hull)164 static vec_t CalculateSolidVolume(const brushhull_t* const hull)
165 {
166 // calculate polyhedron origin
167 // subdivide face winding into triangles
168
169 // for each face
170 // calculate volume of triangle of face to origin
171 // add subidivided volume chunk to total
172
173 int x = 0;
174 vec_t volume = 0.0;
175 vec_t inverse;
176 vec3_t midpoint = { 0.0, 0.0, 0.0 };
177
178 bface_t* face;
179
180 for (face = hull->faces; face; face = face->next, x++)
181 {
182 vec3_t facemid;
183
184 face->w->getCenter(facemid);
185 VectorAdd(midpoint, facemid, midpoint);
186 Developer(DEVELOPER_LEVEL_MESSAGE, "Midpoint for face %d is %f %f %f\n", x, facemid[0], facemid[1], facemid[2]);
187 }
188
189 inverse = 1.0 / x;
190
191 VectorScale(midpoint, inverse, midpoint);
192
193 Developer(DEVELOPER_LEVEL_MESSAGE, "Midpoint for hull is %f %f %f\n", midpoint[0], midpoint[1], midpoint[2]);
194
195 for (face = hull->faces; face; face = face->next, x++)
196 {
197 plane_t* plane = &g_mapplanes[face->planenum];
198 vec_t area = face->w->getArea();
199 vec_t dist = DotProduct(plane->normal, midpoint);
200
201 dist -= plane->dist;
202 dist = fabs(dist);
203
204 volume += area * dist / 3.0;
205 }
206
207 Developer(DEVELOPER_LEVEL_MESSAGE, "Volume for brush is %f\n", volume);
208
209 return volume;
210 }
211
DumpHullWindings(const brushhull_t * const hull)212 static void DumpHullWindings(const brushhull_t* const hull)
213 {
214 int x = 0;
215 bface_t* face;
216
217 for (face = hull->faces; face; face = face->next)
218 {
219 Developer(DEVELOPER_LEVEL_MEGASPAM, "Winding %d\n", x++);
220 face->w->Print();
221 Developer(DEVELOPER_LEVEL_MEGASPAM, "\n");
222 }
223 }
224
isInvalidHull(const brushhull_t * const hull)225 static bool isInvalidHull(const brushhull_t* const hull)
226 {
227 int x = 0;
228 bface_t* face;
229
230 vec3_t mins = { 99999.0, 99999.0, 99999.0 };
231 vec3_t maxs = { -99999.0, -99999.0, -99999.0 };
232
233 for (face = hull->faces; face; face = face->next)
234 {
235 unsigned int y;
236 Winding* winding = face->w;
237
238 for (y = 0; y < winding->m_NumPoints; y++)
239 {
240 VectorCompareMinimum(mins, winding->m_Points[y], mins);
241 VectorCompareMaximum(maxs, winding->m_Points[y], maxs);
242 }
243 }
244
245 for (x = 0; x < 3; x++)
246 {
247 if ((mins[x] < (-BOGUS_RANGE / 2)) || (maxs[x] > (BOGUS_RANGE / 2)))
248 {
249 return true;
250 }
251 }
252 return false;
253 }
254
CalculateBrushUnions(const intptr_t brushnum)255 void CalculateBrushUnions(const intptr_t brushnum)
256 {
257 int bn, hull;
258 brush_t* b1;
259 brush_t* b2;
260 brushhull_t* bh1;
261 brushhull_t* bh2;
262 entity_t* e;
263
264 b1 = &g_mapbrushes[brushnum];
265 e = &g_entities[b1->entitynum];
266
267 for (hull = 0; hull < 1 /* NUM_HULLS */ ; hull++)
268 {
269 bh1 = &b1->hulls[hull];
270 if (!bh1->faces) // Skip it if it is not in this hull
271 {
272 continue;
273 }
274
275 for (bn = brushnum + 1; bn < e->numbrushes; bn++)
276 { // Only compare if b2 > b1, tests are communitive
277 b2 = &g_mapbrushes[e->firstbrush + bn];
278 bh2 = &b2->hulls[hull];
279
280 if (!bh2->faces) // Skip it if it is not in this hull
281 {
282 continue;
283 }
284 if (b1->contents != b2->contents)
285 {
286 continue; // different contents, ignore
287 }
288
289 Developer(DEVELOPER_LEVEL_SPAM, "Processing hull %d brush %d and brush %d\n", hull, brushnum, bn);
290
291 {
292 brushhull_t union_hull;
293 bface_t* face;
294
295 union_hull.bounds = bh1->bounds;
296
297 union_hull.faces = CopyFaceList(bh1->faces);
298
299 for (face = bh2->faces; face; face = face->next)
300 {
301 AddPlaneToUnion(&union_hull, face->planenum);
302 }
303
304 // union was clipped away (no intersection)
305 if (!union_hull.faces)
306 {
307 continue;
308 }
309
310 if (g_developer >= DEVELOPER_LEVEL_MESSAGE)
311 {
312 Log("\nUnion windings\n");
313 DumpHullWindings(&union_hull);
314
315 Log("\nBrush %d windings\n", brushnum);
316 DumpHullWindings(bh1);
317
318 Log("\nBrush %d windings\n", bn);
319 DumpHullWindings(bh2);
320 }
321
322
323 {
324 vec_t volume_brush_1;
325 vec_t volume_brush_2;
326 vec_t volume_brush_union;
327 vec_t volume_ratio_1;
328 vec_t volume_ratio_2;
329
330 if (isInvalidHull(&union_hull))
331 {
332 FreeFaceList(union_hull.faces);
333 continue;
334 }
335
336 volume_brush_union = CalculateSolidVolume(&union_hull);
337 volume_brush_1 = CalculateSolidVolume(bh1);
338 volume_brush_2 = CalculateSolidVolume(bh2);
339
340 volume_ratio_1 = volume_brush_union / volume_brush_1;
341 volume_ratio_2 = volume_brush_union / volume_brush_2;
342
343 if ((volume_ratio_1 > g_BrushUnionThreshold) || (g_developer >= DEVELOPER_LEVEL_MESSAGE))
344 {
345 volume_ratio_1 *= 100.0;
346 Warning("Entity %d : Brush %d intersects with brush %d by %2.3f percent", b1->entitynum,
347 brushnum, bn, volume_ratio_1);
348 }
349 if ((volume_ratio_2 > g_BrushUnionThreshold) || (g_developer >= DEVELOPER_LEVEL_MESSAGE))
350 {
351 volume_ratio_2 *= 100.0;
352 Warning("Entity %d : Brush %d intersects with brush %d by %2.3f percent", b1->entitynum, bn,
353 brushnum, volume_ratio_2);
354 }
355 }
356
357 FreeFaceList(union_hull.faces);
358 }
359 }
360 }
361 }
362