1 //**************************************************************************
2 //**
3 //** ## ## ## ## ## #### #### ### ###
4 //** ## ## ## ## ## ## ## ## ## ## #### ####
5 //** ## ## ## ## ## ## ## ## ## ## ## ## ## ##
6 //** ## ## ######## ## ## ## ## ## ## ## ### ##
7 //** ### ## ## ### ## ## ## ## ## ##
8 //** # ## ## # #### #### ## ##
9 //**
10 //** $Id: p_nodebuild.cpp 4297 2010-06-03 22:49:00Z firebrand_kh $
11 //**
12 //** Copyright (C) 1999-2006 Jānis Legzdiņš
13 //**
14 //** This program is free software; you can redistribute it and/or
15 //** modify it under the terms of the GNU General Public License
16 //** as published by the Free Software Foundation; either version 2
17 //** of the License, or (at your option) any later version.
18 //**
19 //** This program is distributed in the hope that it will be useful,
20 //** but WITHOUT ANY WARRANTY; without even the implied warranty of
21 //** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 //** GNU General Public License for more details.
23 //**
24 //**************************************************************************
25 //**
26 //** Build nodes using glBSP.
27 //**
28 //**************************************************************************
29
30 // HEADER FILES ------------------------------------------------------------
31
32 #include "gamedefs.h"
33 #include "fwaddefs.h"
34 extern "C" {
35 #define vertex_t glbsp_vertex_t
36 #define sector_t glbsp_sector_t
37 #define seg_t glbsp_seg_t
38 #define node_t glbsp_node_t
39 #include "../utils/glbsp/level.h"
40 #include "../utils/glbsp/blockmap.h"
41 #include "../utils/glbsp/node.h"
42 #include "../utils/glbsp/seg.h"
43 #include "../utils/glbsp/analyze.h"
44 #undef vertex_t
45 #undef sector_t
46 #undef seg_t
47 #undef node_t
48 extern boolean_g lev_doing_normal;
49 extern boolean_g lev_doing_hexen;
50 };
51
52 // MACROS ------------------------------------------------------------------
53
54 // TYPES -------------------------------------------------------------------
55
56 // Lump order in a map WAD: each map needs a couple of lumps
57 // to provide a complete scene geometry description.
58 enum
59 {
60 ML_LABEL, // A separator, name, ExMx or MAPxx
61 ML_THINGS, // Monsters, items..
62 ML_LINEDEFS, // LineDefs, from editing
63 ML_SIDEDEFS, // SideDefs, from editing
64 ML_VERTEXES, // Vertices, edited and BSP splits generated
65 ML_SEGS, // LineSegs, from LineDefs split by BSP
66 ML_SSECTORS, // SubSectors, list of LineSegs
67 ML_NODES, // BSP nodes
68 ML_SECTORS, // Sectors, from editing
69 ML_REJECT, // LUT, sector-sector visibility
70 ML_BLOCKMAP, // LUT, motion clipping, walls/grid element
71 ML_BEHAVIOR // ACS scripts
72 };
73
74 // EXTERNAL FUNCTION PROTOTYPES --------------------------------------------
75
76 // PUBLIC FUNCTION PROTOTYPES ----------------------------------------------
77
78 // PRIVATE FUNCTION PROTOTYPES ---------------------------------------------
79
80 // EXTERNAL DATA DECLARATIONS ----------------------------------------------
81
82 // PUBLIC DATA DEFINITIONS -------------------------------------------------
83
84 // PRIVATE DATA DEFINITIONS ------------------------------------------------
85
86 // CODE --------------------------------------------------------------------
87
88 //==========================================================================
89 //
90 // GLBSP_PrintMsg
91 //
92 //==========================================================================
93
GLBSP_PrintMsg(const char * str,...)94 static void GLBSP_PrintMsg(const char *str, ...)
95 {
96 char message_buf[1024];
97 va_list args;
98
99 va_start(args, str);
100 vsprintf(message_buf, str, args);
101 va_end(args);
102
103 GCon->Logf("GB: %s", message_buf);
104 }
105
106 //==========================================================================
107 //
108 // GLBSP_FatalError
109 //
110 // Terminates the program reporting an error.
111 //
112 //==========================================================================
113
GLBSP_FatalError(const char * str,...)114 static void GLBSP_FatalError(const char *str, ...)
115 {
116 char message_buf[1024];
117 va_list args;
118
119 va_start(args, str);
120 vsprintf(message_buf, str, args);
121 va_end(args);
122
123 Sys_Error("Builing nodes failed: %s\n", message_buf);
124 }
125
GLBSP_Ticker()126 static void GLBSP_Ticker()
127 {
128 }
129
GLBSP_DisplayOpen(displaytype_e)130 static boolean_g GLBSP_DisplayOpen(displaytype_e)
131 {
132 return true;
133 }
134
GLBSP_DisplaySetTitle(const char *)135 static void GLBSP_DisplaySetTitle(const char *)
136 {
137 }
138
GLBSP_DisplaySetBarText(int,const char *)139 static void GLBSP_DisplaySetBarText(int, const char*)
140 {
141 }
142
GLBSP_DisplaySetBarLimit(int,int)143 static void GLBSP_DisplaySetBarLimit(int, int)
144 {
145 }
146
GLBSP_DisplaySetBar(int,int)147 static void GLBSP_DisplaySetBar(int, int)
148 {
149 }
150
GLBSP_DisplayClose()151 static void GLBSP_DisplayClose()
152 {
153 }
154
155 static const nodebuildfuncs_t build_funcs =
156 {
157 GLBSP_FatalError,
158 GLBSP_PrintMsg,
159 GLBSP_Ticker,
160
161 GLBSP_DisplayOpen,
162 GLBSP_DisplaySetTitle,
163 GLBSP_DisplaySetBar,
164 GLBSP_DisplaySetBarLimit,
165 GLBSP_DisplaySetBarText,
166 GLBSP_DisplayClose
167 };
168
169 //==========================================================================
170 //
171 // SetUpVertices
172 //
173 //==========================================================================
174
SetUpVertices(VLevel * Level)175 static void SetUpVertices(VLevel* Level)
176 {
177 guard(SetUpVertices);
178 vertex_t* pSrc = Level->Vertexes;
179 for (int i = 0; i < Level->NumVertexes; i++, pSrc++)
180 {
181 glbsp_vertex_t* Vert = NewVertex();
182 Vert->x = pSrc->x;
183 Vert->y = pSrc->y;
184 Vert->index = i;
185 }
186
187 num_normal_vert = num_vertices;
188 num_gl_vert = 0;
189 num_complete_seg = 0;
190 unguard;
191 }
192
193 //==========================================================================
194 //
195 // SetUpSectors
196 //
197 //==========================================================================
198
SetUpSectors(VLevel * Level)199 static void SetUpSectors(VLevel* Level)
200 {
201 guard(SetUpSectors);
202 sector_t* pSrc = Level->Sectors;
203 for (int i = 0; i < Level->NumSectors; i++, pSrc++)
204 {
205 glbsp_sector_t* Sector = NewSector();
206 Sector->coalesce = (pSrc->tag >= 900 && pSrc->tag < 1000) ?
207 TRUE : FALSE;
208 Sector->index = i;
209 Sector->warned_facing = -1;
210 }
211 unguard;
212 }
213
214 //==========================================================================
215 //
216 // SetUpSidedefs
217 //
218 //==========================================================================
219
SetUpSidedefs(VLevel * Level)220 static void SetUpSidedefs(VLevel* Level)
221 {
222 guard(SetUpSidedefs);
223 side_t* pSrc = Level->Sides;
224 for (int i = 0; i < Level->NumSides; i++, pSrc++)
225 {
226 sidedef_t* Side = NewSidedef();
227 Side->sector = !pSrc->Sector ? NULL :
228 LookupSector(pSrc->Sector - Level->Sectors);
229 if (Side->sector)
230 {
231 Side->sector->ref_count++;
232 }
233 Side->index = i;
234 }
235 unguard;
236 }
237
238 //==========================================================================
239 //
240 // SetUpLinedefs
241 //
242 //==========================================================================
243
SetUpLinedefs(VLevel * Level)244 static void SetUpLinedefs(VLevel* Level)
245 {
246 guard(SetUpLinedefs);
247 line_t* pSrc = Level->Lines;
248 for (int i = 0; i < Level->NumLines; i++, pSrc++)
249 {
250 linedef_t* Line = NewLinedef();
251 Line->start = LookupVertex(pSrc->v1 - Level->Vertexes);
252 Line->end = LookupVertex(pSrc->v2 - Level->Vertexes);
253 Line->start->ref_count++;
254 Line->end->ref_count++;
255 Line->zero_len = (fabs(Line->start->x - Line->end->x) < DIST_EPSILON) &&
256 (fabs(Line->start->y - Line->end->y) < DIST_EPSILON);
257 Line->flags = pSrc->flags;
258 Line->type = pSrc->special;
259 Line->two_sided = (Line->flags & LINEFLAG_TWO_SIDED) ? TRUE : FALSE;
260 Line->right = pSrc->sidenum[0] < 0 ? NULL : LookupSidedef(pSrc->sidenum[0]);
261 Line->left = pSrc->sidenum[1] < 0 ? NULL : LookupSidedef(pSrc->sidenum[1]);
262 if (Line->right)
263 {
264 Line->right->ref_count++;
265 Line->right->on_special |= (Line->type > 0) ? 1 : 0;
266 }
267 if (Line->left)
268 {
269 Line->left->ref_count++;
270 Line->left->on_special |= (Line->type > 0) ? 1 : 0;
271 }
272 Line->self_ref = (Line->left && Line->right &&
273 (Line->left->sector == Line->right->sector));
274 Line->index = i;
275 }
276 unguard;
277 }
278
279 //==========================================================================
280 //
281 // SetUpThings
282 //
283 //==========================================================================
284
SetUpThings(VLevel * Level)285 static void SetUpThings(VLevel* Level)
286 {
287 guard(SetUpThings);
288 mthing_t* pSrc = Level->Things;
289 for (int i = 0; i < Level->NumThings; i++, pSrc++)
290 {
291 thing_t* Thing = NewThing();
292 Thing->x = (int)pSrc->x;
293 Thing->y = (int)pSrc->y;
294 Thing->type = pSrc->type;
295 Thing->options = pSrc->options;
296 Thing->index = i;
297 }
298 unguard;
299 }
300
301 //==========================================================================
302 //
303 // CopyGLVerts
304 //
305 //==========================================================================
306
CopyGLVerts(VLevel * Level,vertex_t * & GLVertexes)307 static void CopyGLVerts(VLevel* Level, vertex_t*& GLVertexes)
308 {
309 guard(CopyGLVerts);
310 int NumBaseVerts = Level->NumVertexes;
311 vertex_t* OldVertexes = Level->Vertexes;
312 Level->NumVertexes = NumBaseVerts + num_gl_vert;
313 Level->Vertexes = new vertex_t[Level->NumVertexes];
314 GLVertexes = Level->Vertexes + NumBaseVerts;
315 memcpy(Level->Vertexes, OldVertexes, NumBaseVerts * sizeof(vertex_t));
316 vertex_t* pDst = GLVertexes;
317 for (int i = 0; i < num_vertices; i++)
318 {
319 glbsp_vertex_t* vert = LookupVertex(i);
320 if (!(vert->index & IS_GL_VERTEX))
321 continue;
322 *pDst = TVec(vert->x, vert->y, 0);
323 pDst++;
324 }
325
326 // Update pointers to vertexes in lines.
327 for (int i = 0; i < Level->NumLines; i++)
328 {
329 line_t* ld = &Level->Lines[i];
330 ld->v1 = &Level->Vertexes[ld->v1 - OldVertexes];
331 ld->v2 = &Level->Vertexes[ld->v2 - OldVertexes];
332 }
333 delete[] OldVertexes;
334 OldVertexes = NULL;
335 unguard;
336 }
337
338 //==========================================================================
339 //
340 // CopySegs
341 //
342 //==========================================================================
343
CopySegs(VLevel * Level,vertex_t * GLVertexes)344 static void CopySegs(VLevel* Level, vertex_t* GLVertexes)
345 {
346 guard(CopySegs);
347 // Build ordered list of source segs.
348 glbsp_seg_t** SrcSegs = new glbsp_seg_t*[num_complete_seg];
349 for (int i = 0; i < num_segs; i++)
350 {
351 glbsp_seg_t* Seg = LookupSeg(i);
352 // ignore degenerate segs
353 if (Seg->degenerate)
354 continue;
355 SrcSegs[Seg->index] = Seg;
356 }
357
358 Level->NumSegs = num_complete_seg;
359 Level->Segs = new seg_t[Level->NumSegs];
360 memset(Level->Segs, 0, sizeof(seg_t) * Level->NumSegs);
361 seg_t* li = Level->Segs;
362 for (int i = 0; i < Level->NumSegs; i++, li++)
363 {
364 glbsp_seg_t* SrcSeg = SrcSegs[i];
365
366 if (SrcSeg->start->index & IS_GL_VERTEX)
367 {
368 li->v1 = &GLVertexes[SrcSeg->start->index & ~IS_GL_VERTEX];
369 }
370 else
371 {
372 li->v1 = &Level->Vertexes[SrcSeg->start->index];
373 }
374 if (SrcSeg->end->index & IS_GL_VERTEX)
375 {
376 li->v2 = &GLVertexes[SrcSeg->end->index & ~IS_GL_VERTEX];
377 }
378 else
379 {
380 li->v2 = &Level->Vertexes[SrcSeg->end->index];
381 }
382
383 if (SrcSeg->linedef)
384 {
385 line_t* ldef = &Level->Lines[SrcSeg->linedef->index];
386 li->linedef = ldef;
387 li->sidedef = &Level->Sides[ldef->sidenum[SrcSeg->side]];
388 li->frontsector = Level->Sides[ldef->sidenum[SrcSeg->side]].Sector;
389
390 if (ldef->flags & ML_TWOSIDED)
391 {
392 li->backsector = Level->Sides[ldef->sidenum[SrcSeg->side ^ 1]].Sector;
393 }
394
395 if (SrcSeg->side)
396 {
397 li->offset = Length(*li->v1 - *ldef->v2);
398 }
399 else
400 {
401 li->offset = Length(*li->v1 - *ldef->v1);
402 }
403 li->length = Length(*li->v2 - *li->v1);
404 li->side = SrcSeg->side;
405 }
406
407 // Calc seg's plane params
408 CalcSeg(li);
409 }
410
411 delete[] SrcSegs;
412 SrcSegs = NULL;
413 unguard;
414 }
415
416 //==========================================================================
417 //
418 // CopySubsectors
419 //
420 //==========================================================================
421
CopySubsectors(VLevel * Level)422 static void CopySubsectors(VLevel* Level)
423 {
424 guard(CopySubsectors);
425 Level->NumSubsectors = num_subsecs;
426 Level->Subsectors = new subsector_t[Level->NumSubsectors];
427 memset(Level->Subsectors, 0, sizeof(subsector_t) * Level->NumSubsectors);
428 subsector_t* ss = Level->Subsectors;
429 for (int i = 0; i < Level->NumSubsectors; i++, ss++)
430 {
431 subsec_t* SrcSub = LookupSubsec(i);
432 ss->numlines = SrcSub->seg_count;
433 ss->firstline = SrcSub->seg_list->index;
434
435 // Look up sector number for each subsector
436 seg_t* seg = &Level->Segs[ss->firstline];
437 for (int j = 0; j < ss->numlines; j++)
438 {
439 if (seg[j].linedef)
440 {
441 ss->sector = seg[j].sidedef->Sector;
442 ss->seclink = ss->sector->subsectors;
443 ss->sector->subsectors = ss;
444 break;
445 }
446 }
447 if (!ss->sector)
448 {
449 Host_Error("Subsector %d without sector", i);
450 }
451 }
452 unguard;
453 }
454
455 //==========================================================================
456 //
457 // CopyNode
458 //
459 //==========================================================================
460
CopyNode(int & NodeIndex,glbsp_node_t * SrcNode,node_t * Nodes)461 static void CopyNode(int& NodeIndex, glbsp_node_t* SrcNode, node_t* Nodes)
462 {
463 if (SrcNode->r.node)
464 {
465 CopyNode(NodeIndex, SrcNode->r.node, Nodes);
466 }
467
468 if (SrcNode->l.node)
469 {
470 CopyNode(NodeIndex, SrcNode->l.node, Nodes);
471 }
472
473 SrcNode->index = NodeIndex;
474
475 node_t* Node = &Nodes[NodeIndex];
476 Node->SetPointDir(TVec(SrcNode->x, SrcNode->y, 0),
477 TVec(SrcNode->dx, SrcNode->dy, 0));
478
479 Node->bbox[0][0] = SrcNode->r.bounds.minx;
480 Node->bbox[0][1] = SrcNode->r.bounds.miny;
481 Node->bbox[0][2] = -32768.0;
482 Node->bbox[0][3] = SrcNode->r.bounds.maxx;
483 Node->bbox[0][4] = SrcNode->r.bounds.maxy;
484 Node->bbox[0][5] = 32768.0;
485
486 Node->bbox[1][0] = SrcNode->l.bounds.minx;
487 Node->bbox[1][1] = SrcNode->l.bounds.miny;
488 Node->bbox[1][2] = -32768.0;
489 Node->bbox[1][3] = SrcNode->l.bounds.maxx;
490 Node->bbox[1][4] = SrcNode->l.bounds.maxy;
491 Node->bbox[1][5] = 32768.0;
492
493 if (SrcNode->r.node)
494 {
495 Node->children[0] = SrcNode->r.node->index;
496 }
497 else if (SrcNode->r.subsec)
498 {
499 Node->children[0] = SrcNode->r.subsec->index | NF_SUBSECTOR;
500 }
501
502 if (SrcNode->l.node)
503 {
504 Node->children[1] = SrcNode->l.node->index;
505 }
506 else if (SrcNode->l.subsec)
507 {
508 Node->children[1] = SrcNode->l.subsec->index | NF_SUBSECTOR;
509 }
510
511 NodeIndex++;
512 }
513
514 //==========================================================================
515 //
516 // CopyNodes
517 //
518 //==========================================================================
519
CopyNodes(VLevel * Level,glbsp_node_t * root_node)520 static void CopyNodes(VLevel* Level, glbsp_node_t* root_node)
521 {
522 guard(CopyNodes);
523 // Copy nodes.
524 Level->NumNodes = num_nodes;
525 Level->Nodes = new node_t[Level->NumNodes];
526 memset(Level->Nodes, 0, sizeof(node_t) * Level->NumNodes);
527 if (root_node)
528 {
529 int NodeIndex = 0;
530 CopyNode(NodeIndex, root_node, Level->Nodes);
531 }
532 unguard;
533 }
534
535 //==========================================================================
536 //
537 // VLevel::BuildNodes
538 //
539 //==========================================================================
540
BuildNodes()541 void VLevel::BuildNodes()
542 {
543 guard(VLevel::BuildNodes);
544 // Set up glBSP build globals.
545 nodebuildinfo_t nb_info = default_buildinfo;
546 nodebuildcomms_t nb_comms = default_buildcomms;
547 nb_info.quiet = false;
548 nb_info.gwa_mode = true;
549
550 cur_info = &nb_info;
551 cur_funcs = &build_funcs;
552 cur_comms = &nb_comms;
553
554 lev_doing_normal = false;
555 lev_doing_hexen = !!(LevelFlags & LF_Extended);
556
557 // Set up map data from loaded data.
558 SetUpVertices(this);
559 SetUpSectors(this);
560 SetUpSidedefs(this);
561 SetUpLinedefs(this);
562 SetUpThings(this);
563
564 // Other data initialisation.
565 CalculateWallTips();
566 if (lev_doing_hexen)
567 {
568 DetectPolyobjSectors();
569 }
570 DetectOverlappingLines();
571 if (cur_info->window_fx)
572 {
573 DetectWindowEffects();
574 }
575 InitBlockmap();
576
577 // Build nodes.
578 superblock_t* SegList = CreateSegs();
579 glbsp_node_t* root_node;
580 subsec_t* root_sub;
581 glbsp_ret_e ret = ::BuildNodes(SegList, &root_node, &root_sub, 0, NULL);
582 FreeSuper(SegList);
583
584 if (ret == GLBSP_E_OK)
585 {
586 ClockwiseBspTree(root_node);
587
588 // Copy nodes into internal structures.
589 vertex_t* GLVertexes;
590
591 CopyGLVerts(this, GLVertexes);
592 CopySegs(this, GLVertexes);
593 CopySubsectors(this);
594 CopyNodes(this, root_node);
595 }
596
597 // Free any memory used by glBSP.
598 FreeLevel();
599 FreeQuickAllocCuts();
600 FreeQuickAllocSupers();
601
602 cur_info = NULL;
603 cur_comms = NULL;
604 cur_funcs = NULL;
605
606 if (ret != GLBSP_E_OK)
607 {
608 Host_Error("Node build failed");
609 }
610
611 // Create dummy VIS data.
612 VisData = NULL;
613 NoVis = new vuint8[(NumSubsectors + 7) / 8];
614 memset(NoVis, 0xff, (NumSubsectors + 7) / 8);
615 unguard;
616 }
617