1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
18 See file, 'COPYING', for details.
19 */
20 #ifdef HAVE_CONFIG_H
21 # include "config.h"
22 #endif
23
24 #ifdef HAVE_STRING_H
25 # include <string.h>
26 #endif
27
28 #include "QF/sys.h"
29
30 #include "brush.h"
31 #include "bsp5.h"
32 #include "csg4.h"
33 #include "draw.h"
34 #include "merge.h"
35 #include "solidbsp.h"
36 #include "surfaces.h"
37
38 /** \addtogroup qfbsp_csg4
39 */
40 //@{
41
42 /*
43 NOTES
44
45 Brushes that touch still need to be split at the cut point to make a
46 tjunction
47 */
48
49 face_t *validfaces[MAX_MAP_PLANES];
50 face_t *inside, *outside;
51 int brushfaces;
52 int csgfaces;
53 int csgmergefaces;
54
55 face_t *
NewFaceFromFace(const face_t * in)56 NewFaceFromFace (const face_t *in)
57 {
58 face_t *newf;
59
60 newf = AllocFace ();
61
62 newf->planenum = in->planenum;
63 newf->texturenum = in->texturenum;
64 newf->planeside = in->planeside;
65 newf->original = in->original;
66 newf->contents[0] = in->contents[0];
67 newf->contents[1] = in->contents[1];
68 newf->detail = in->detail;
69
70 return newf;
71 }
72
73 void
SplitFace(face_t * in,plane_t * split,face_t ** front,face_t ** back)74 SplitFace (face_t *in, plane_t *split, face_t **front, face_t **back)
75 {
76 int i;
77 int counts[3];
78 plane_t plane;
79 vec_t dot;
80 winding_t *tmp;
81
82 if (in->points->numpoints < 0)
83 Sys_Error ("SplitFace: freed face");
84 counts[0] = counts[1] = counts[2] = 0;
85
86 // determine sides for each point
87 for (i = 0; i < in->points->numpoints; i++) {
88 dot = DotProduct (in->points->points[i], split->normal) - split->dist;
89 if (dot > ON_EPSILON)
90 counts[SIDE_FRONT]++;
91 else if (dot < -ON_EPSILON)
92 counts[SIDE_BACK]++;
93 }
94
95 if (!counts[SIDE_FRONT]) {
96 *front = NULL;
97 *back = in;
98 return;
99 }
100 if (!counts[SIDE_BACK]) {
101 *front = in;
102 *back = NULL;
103 return;
104 }
105
106 *back = NewFaceFromFace (in);
107 *front = NewFaceFromFace (in);
108
109 tmp = CopyWinding (in->points);
110 (*front)->points = ClipWinding (tmp, split, 0);
111
112 plane.dist = -split->dist;
113 VectorNegate (split->normal, plane.normal);
114 (*back)->points = ClipWinding (in->points, &plane, 0);
115
116 in->points = 0; // freed by ClipWinding
117 FreeFace (in);
118 }
119
120 /** Clips all of the faces in the ::inside list.
121
122 Faces will be moved to the ::outside list or split into a piece in each
123 list. Faces exactly on the plane will stay inside unless overdrawn by
124 a later brush
125
126 \param splitplane Index of the plane by which faces will be clipped.
127 \param frontside The side of the plane that holds the outside list.
128 \param precedence XXX
129 */
130 static void
ClipInside(int splitplane,int frontside,qboolean precedence)131 ClipInside (int splitplane, int frontside, qboolean precedence)
132 {
133 face_t *insidelist, *next, *f;
134 face_t *frags[2];
135 plane_t *split;
136
137 split = &planes[splitplane];
138
139 insidelist = NULL;
140 for (f = inside; f; f = next) {
141 next = f->next; // f->next will get mashed by SplitFace
142
143 if (f->planenum == splitplane) {
144 // exactly on, handle special
145
146 // always clip off opposite facing
147 if (frontside != f->planeside || precedence) {
148 frags[frontside] = NULL;
149 frags[!frontside] = f;
150 } else {
151 // leave it on the outside
152 frags[frontside] = f;
153 frags[!frontside] = NULL;
154 }
155 } else {
156 // proper split
157 SplitFace (f, split, &frags[0], &frags[1]);
158 }
159
160 if (frags[frontside]) {
161 frags[frontside]->next = outside;
162 outside = frags[frontside];
163 }
164 if (frags[!frontside]) {
165 frags[!frontside]->next = insidelist;
166 insidelist = frags[!frontside];
167 }
168 }
169
170 inside = insidelist;
171 }
172
173 /** Saves all of the faces in the ::outside list to the bsp plane list
174 (::validfaces).
175
176 \param mirror If true, add extra faces that face the opposite direction.
177 */
178 static void
SaveOutside(qboolean mirror)179 SaveOutside (qboolean mirror)
180 {
181 face_t *f, *next, *newf;
182 int planenum;
183
184 for (f = outside; f; f = next) {
185 next = f->next;
186 csgfaces++;
187 Draw_DrawFace (f);
188 planenum = f->planenum;
189
190 if (mirror) {
191 newf = NewFaceFromFace (f);
192
193 newf->points = CopyWindingReverse (f->points);
194 newf->planeside = f->planeside ^ 1; // reverse side
195 newf->contents[0] = f->contents[1];
196 newf->contents[1] = f->contents[0];
197
198 validfaces[planenum] = MergeFaceToList (newf,
199 validfaces[planenum]);
200 }
201
202 validfaces[planenum] = MergeFaceToList (f, validfaces[planenum]);
203 validfaces[planenum] = FreeMergeListScraps (validfaces[planenum]);
204 }
205 }
206
207 /** Free the faces that are inside the clipping brush.
208
209 If the clipping brush is non-solid, then the faces will be moved to
210 ::outside rather than being freed, thus allowing the faces to continue
211 to exist.
212
213 \param contents The contents of the clipping brush.
214 */
215 static void
FreeInside(int contents)216 FreeInside (int contents)
217 {
218 face_t *next, *f;
219
220 for (f = inside; f; f = next) {
221 next = f->next;
222
223 if (contents != CONTENTS_SOLID) {
224 f->contents[0] = contents;
225 f->next = outside;
226 outside = f;
227 } else
228 FreeFace (f);
229 }
230 }
231
232 surface_t *
BuildSurfaces(void)233 BuildSurfaces (void)
234 {
235 face_t *count;
236 face_t **f;
237 int i;
238 surface_t *surfhead, *s;
239
240 surfhead = NULL;
241
242 f = validfaces;
243 for (i = 0; i < numbrushplanes; i++, f++) {
244 if (!*f)
245 continue; // nothing left on this plane
246
247 // create a new surface to hold the faces on this plane
248 s = AllocSurface ();
249 s->planenum = i;
250 s->next = surfhead;
251 surfhead = s;
252 s->faces = *f;
253 for (count = s->faces; count; count = count->next) {
254 csgmergefaces++;
255 if (count->detail)
256 s->has_detail = 1;
257 else
258 s->has_struct = 1;
259 }
260 CalcSurfaceInfo (s); // bounding box and flags
261 }
262
263 return surfhead;
264 }
265
266 /** Create faces using the faces of the provided brush.
267
268 The ::outside list will be set to the list of created faces. The faces
269 will be such that their front is empty and their back is the contents of
270 the brush.
271
272 \param b The brush from which to create the faces.
273 */
274 static void
CopyFacesToOutside(brush_t * b)275 CopyFacesToOutside (brush_t *b)
276 {
277 face_t *newf, *f;
278
279 outside = NULL;
280
281 for (f = b->faces; f; f = f->next) {
282 if (f->texturenum == TEX_SKIP)
283 continue;
284
285 brushfaces++;
286 newf = AllocFace ();
287 *newf = *f;
288 newf->points = CopyWinding (f->points);
289 newf->next = outside;
290 newf->contents[0] = CONTENTS_EMPTY;
291 newf->contents[1] = b->contents;
292 outside = newf;
293 }
294 }
295
296 surface_t *
CSGFaces(brushset_t * bs)297 CSGFaces (brushset_t *bs)
298 {
299 brush_t *b1, *b2;
300 face_t *f;
301 int i;
302 qboolean overwrite;
303 surface_t *surfhead;
304
305 qprintf ("---- CSGFaces ----\n");
306
307 memset (validfaces, 0, sizeof (validfaces));
308
309 csgfaces = brushfaces = csgmergefaces = 0;
310
311 Draw_ClearWindow ();
312
313 // do the solid faces
314 for (b1 = bs->brushes; b1; b1 = b1->next) {
315 // set outside to a copy of the brush's faces
316 CopyFacesToOutside (b1);
317
318 if (b1->faces->texturenum < 0) {
319 // Don't split HINT and SKIP brushes.
320 SaveOutside (false);
321 continue;
322 }
323
324 // earlier brushes do NOT overwrite
325 overwrite = false;
326
327 for (b2 = bs->brushes; b2; b2 = b2->next) {
328 // see if b2 needs to clip a chunk out of b1
329 if (b2->faces->texturenum < 0)
330 continue;
331
332 if (b1 == b2) {
333 // later brushes DO overwrite
334 overwrite = true;
335 continue;
336 }
337 // check bounding box first
338 for (i = 0; i < 3; i++)
339 if (b1->mins[i] > b2->maxs[i] || b1->maxs[i] < b2->mins[i])
340 break;
341 if (i < 3)
342 continue;
343
344 // divide faces by the planes of the new brush
345
346 inside = outside;
347 outside = NULL;
348
349 for (f = b2->faces; f; f = f->next)
350 ClipInside (f->planenum, f->planeside, overwrite);
351
352 // these faces are contained in another brush, so get rid of them
353 if (b1->contents == CONTENTS_SOLID
354 && b2->contents <= CONTENTS_WATER) {
355 // Faces from a solid brush are allowed to exist inside a
356 // non-solid brush. This forms an intrusion into the clipping
357 // brush.
358 FreeInside (b2->contents);
359 } else {
360 // Unconditionally treat the clipping brush as solid to force
361 // contents merging, or to make an empty clipping brush clip
362 // away parts of other brushes.
363 FreeInside (CONTENTS_SOLID);
364 }
365 }
366
367 // all of the faces left in outside are real surface faces
368 // if the brush is not solid, mirror the faces for the inside view
369 SaveOutside (b1->contents != CONTENTS_SOLID);
370 }
371
372 #if 0
373 if (!csgfaces)
374 Sys_Error ("No faces");
375 #endif
376
377 surfhead = BuildSurfaces ();
378
379 qprintf ("%5i brushfaces\n", brushfaces);
380 qprintf ("%5i csgfaces\n", csgfaces);
381 qprintf ("%5i mergedfaces\n", csgmergefaces);
382
383 return surfhead;
384 }
385
386 //@}
387