1 //------------------------------------------------------------------------
2 // REJECT : Generate the reject table
3 //------------------------------------------------------------------------
4 //
5 // GL-Friendly Node Builder (C) 2000-2007 Andrew Apted
6 //
7 // Based on 'BSP 2.3' by Colin Reed, Lee Killough and others.
8 //
9 // This program is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU General Public License
11 // as published by the Free Software Foundation; either version 2
12 // of the License, or (at your option) any later version.
13 //
14 // This program 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 //------------------------------------------------------------------------
20
21 #include "system.h"
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <stdarg.h>
27 #include <ctype.h>
28 #include <math.h>
29 #include <limits.h>
30 #include <assert.h>
31
32 #include "reject.h"
33 #include "level.h"
34 #include "node.h"
35 #include "seg.h"
36 #include "structs.h"
37 #include "util.h"
38 #include "wad.h"
39
40
41 #define DEBUG_REJECT 0
42
43
44 //
45 // InitReject
46 //
47 // Puts each sector into individual groups.
48 //
InitReject(void)49 static void InitReject(void)
50 {
51 int i;
52
53 for (i=0; i < num_sectors; i++)
54 {
55 sector_t *sec = LookupSector(i);
56
57 sec->rej_group = i;
58 sec->rej_next = sec->rej_prev = sec;
59 }
60 }
61
62 //
63 // GroupSectors
64 //
65 // Algorithm: Initially all sectors are in individual groups. Now we
66 // scan the linedef list. For each 2-sectored line, merge the two
67 // sector groups into one. That's it !
68 //
GroupSectors(void)69 static void GroupSectors(void)
70 {
71 int i;
72
73 for (i=0; i < num_linedefs; i++)
74 {
75 linedef_t *line = LookupLinedef(i);
76 sector_t *sec1, *sec2, *tmp;
77
78 if (! line->right || ! line->left)
79 continue;
80
81 // the standard DOOM engine will not allow sight past lines
82 // lacking the TWOSIDED flag, so we can skip them here too.
83 if (! line->two_sided)
84 continue;
85
86 sec1 = line->right->sector;
87 sec2 = line->left->sector;
88
89 if (! sec1 || ! sec2 || sec1 == sec2)
90 continue;
91
92 // already in the same group ?
93 if (sec1->rej_group == sec2->rej_group)
94 continue;
95
96 // swap sectors so that the smallest group is added to the biggest
97 // group. This is based on the assumption that sector numbers in
98 // wads will generally increase over the set of linedefs, and so
99 // (by swapping) we'll tend to add small groups into larger
100 // groups, thereby minimising the updates to 'rej_group' fields
101 // that is required when merging.
102
103 if (sec1->rej_group > sec2->rej_group)
104 {
105 tmp = sec1; sec1 = sec2; sec2 = tmp;
106 }
107
108 // update the group numbers in the second group
109
110 sec2->rej_group = sec1->rej_group;
111
112 for (tmp=sec2->rej_next; tmp != sec2; tmp=tmp->rej_next)
113 tmp->rej_group = sec1->rej_group;
114
115 // merge 'em baby...
116
117 sec1->rej_next->rej_prev = sec2;
118 sec2->rej_next->rej_prev = sec1;
119
120 tmp = sec1->rej_next;
121 sec1->rej_next = sec2->rej_next;
122 sec2->rej_next = tmp;
123 }
124 }
125
126 #if DEBUG_REJECT
CountGroups(void)127 static void CountGroups(void)
128 {
129 // Note: this routine is destructive to the group numbers
130
131 int i;
132
133 for (i=0; i < num_sectors; i++)
134 {
135 sector_t *sec = LookupSector(i);
136 sector_t *tmp;
137
138 int group = sec->rej_group;
139 int num = 0;
140
141 if (group < 0)
142 continue;
143
144 sec->rej_group = -1;
145 num++;
146
147 for (tmp=sec->rej_next; tmp != sec; tmp=tmp->rej_next)
148 {
149 tmp->rej_group = -1;
150 num++;
151 }
152
153 PrintDebug("Group %d Sectors %d\n", group, num);
154 }
155 }
156 #endif
157
158 //
159 // CreateReject
160 //
CreateReject(uint8_g * matrix)161 static void CreateReject(uint8_g *matrix)
162 {
163 int view, target;
164
165 for (view=0; view < num_sectors; view++)
166 for (target=0; target < view; target++)
167 {
168 sector_t *view_sec = LookupSector(view);
169 sector_t *targ_sec = LookupSector(target);
170
171 int p1, p2;
172
173 if (view_sec->rej_group == targ_sec->rej_group)
174 continue;
175
176 // for symmetry, do two bits at a time
177
178 p1 = view * num_sectors + target;
179 p2 = target * num_sectors + view;
180
181 matrix[p1 >> 3] |= (1 << (p1 & 7));
182 matrix[p2 >> 3] |= (1 << (p2 & 7));
183 }
184 }
185
186 //
187 // PutReject
188 //
189 // For now we only do very basic reject processing, limited to
190 // determining all isolated groups of sectors (islands that are
191 // surrounded by void space).
192 //
PutReject(void)193 void PutReject(void)
194 {
195 int reject_size;
196 uint8_g *matrix;
197 lump_t *lump;
198
199 DisplayTicker();
200
201 InitReject();
202 GroupSectors();
203
204 reject_size = (num_sectors * num_sectors + 7) / 8;
205 matrix = UtilCalloc(reject_size);
206
207 CreateReject(matrix);
208
209 # if DEBUG_REJECT
210 CountGroups();
211 # endif
212
213 lump = CreateLevelLump("REJECT");
214
215 AppendLevelLump(lump, matrix, reject_size);
216
217 PrintVerbose("Added simple reject lump\n");
218
219 UtilFree(matrix);
220 }
221
222