1 //----------------------------------------------------------------------------
2 // EDGE OpenGL Rendering (Occlusion testing)
3 //----------------------------------------------------------------------------
4 //
5 // Copyright (c) 1999-2009 The EDGE Team.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 //
17 //----------------------------------------------------------------------------
18
19 #include "i_defs.h"
20
21 #include "ddf/types.h"
22
23 #include "r_occlude.h"
24
25
26 // #define DEBUG_OCC 1
27
28
29 typedef struct angle_range_s
30 {
31 angle_t low, high;
32
33 struct angle_range_s *next;
34 struct angle_range_s *prev;
35 }
36 angle_range_t;
37
38
39 static angle_range_t *occbuf_head = NULL;
40 static angle_range_t *occbuf_tail = NULL;
41
42 static angle_range_t *free_range_chickens = NULL;
43
44
45 #ifdef DEBUG_OCC
ValidateBuffer(void)46 static void ValidateBuffer(void)
47 {
48 if (! occbuf_head)
49 {
50 SYS_ASSERT(! occbuf_tail);
51 return;
52 }
53
54 for (angle_range_t *AR = occbuf_head; AR; AR = AR->next)
55 {
56 SYS_ASSERT(AR->low <= AR->high);
57
58 if (AR->next)
59 {
60 SYS_ASSERT(AR->next->prev == AR);
61 SYS_ASSERT(AR->next->low > AR->high);
62 }
63 else
64 {
65 SYS_ASSERT(AR == occbuf_tail);
66 }
67
68 if (AR->prev)
69 {
70 SYS_ASSERT(AR->prev->next == AR);
71 }
72 else
73 {
74 SYS_ASSERT(AR == occbuf_head);
75 }
76 }
77 }
78 #endif // DEBUG_OCC
79
80
RGL_1DOcclusionClear(void)81 void RGL_1DOcclusionClear(void)
82 {
83 // Clear all angles in the whole buffer
84 // )i.e. mark them as open / non-blocking).
85
86 if (occbuf_head)
87 {
88 occbuf_tail->next = free_range_chickens;
89
90 free_range_chickens = occbuf_head;
91
92 occbuf_head = NULL;
93 occbuf_tail = NULL;
94 }
95
96 #ifdef DEBUG_OCC
97 ValidateBuffer();
98 #endif
99 }
100
GetNewRange(angle_t low,angle_t high)101 static inline angle_range_t *GetNewRange(angle_t low, angle_t high)
102 {
103 angle_range_t *R;
104
105 if (free_range_chickens)
106 {
107 R = free_range_chickens;
108
109 free_range_chickens = R->next;
110 }
111 else
112 R = new angle_range_t;
113
114 R->low = low;
115 R->high = high;
116
117 return R;
118 }
119
LinkBefore(angle_range_t * X,angle_range_t * N)120 static inline void LinkBefore(angle_range_t *X, angle_range_t *N)
121 {
122 // X = eXisting range
123 // N = New range
124
125 N->next = X;
126 N->prev = X->prev;
127
128 X->prev = N;
129
130 if (N->prev)
131 N->prev->next = N;
132 else
133 occbuf_head = N;
134 }
135
LinkInTail(angle_range_t * N)136 static inline void LinkInTail(angle_range_t *N)
137 {
138 N->next = NULL;
139 N->prev = occbuf_tail;
140
141 if (occbuf_tail)
142 occbuf_tail->next = N;
143 else
144 occbuf_head = N;
145
146 occbuf_tail = N;
147 }
148
RemoveRange(angle_range_t * R)149 static inline void RemoveRange(angle_range_t *R)
150 {
151 if (R->next)
152 R->next->prev = R->prev;
153 else
154 occbuf_tail = R->prev;
155
156 if (R->prev)
157 R->prev->next = R->next;
158 else
159 occbuf_head = R->next;
160
161 // add it to the quick-alloc list
162 R->next = free_range_chickens;
163 R->prev = NULL;
164
165 free_range_chickens = R;
166 }
167
DoSet(angle_t low,angle_t high)168 static void DoSet(angle_t low, angle_t high)
169 {
170 for (angle_range_t *AR = occbuf_head; AR; AR = AR->next)
171 {
172 if (high < AR->low)
173 {
174 LinkBefore(AR, GetNewRange(low, high));
175 return;
176 }
177
178 if (low > AR->high)
179 continue;
180
181 // the new range overlaps the old range.
182 //
183 // The above test (i.e. low > AR->high) guarantees that if
184 // we reduce AR->low, it cannot touch the previous range.
185 //
186 // However by increasing AR->high we may touch or overlap
187 // some subsequent ranges in the list. When that happens,
188 // we must remove them (and adjust the current range).
189
190 AR->low = MIN(AR->low, low);
191 AR->high = MAX(AR->high, high);
192
193 #ifdef DEBUG_OCC
194 if (AR->prev)
195 {
196 SYS_ASSERT(AR->low > AR->prev->high);
197 }
198 #endif
199 while (AR->next && AR->high >= AR->next->low)
200 {
201 AR->high = MAX(AR->high, AR->next->high);
202
203 RemoveRange(AR->next);
204 }
205
206 return;
207 }
208
209 // the new range is greater than all existing ranges
210
211 LinkInTail(GetNewRange(low, high));
212 }
213
RGL_1DOcclusionSet(angle_t low,angle_t high)214 void RGL_1DOcclusionSet(angle_t low, angle_t high)
215 {
216 // Set all angles in the given range, i.e. mark them as blocking.
217 // The angles are relative to the VIEW angle.
218
219 SYS_ASSERT((angle_t)(high - low) < ANG180);
220
221 if (low <= high)
222 DoSet(low, high);
223 else
224 { DoSet(low, ANG_MAX); DoSet(0, high); }
225
226 #ifdef DEBUG_OCC
227 ValidateBuffer();
228 #endif
229 }
230
DoTest(angle_t low,angle_t high)231 static inline bool DoTest(angle_t low, angle_t high)
232 {
233 for (angle_range_t *AR = occbuf_head; AR; AR = AR->next)
234 {
235 if (AR->low <= low && high <= AR->high)
236 return true;
237
238 if (AR->high > low)
239 break;
240 }
241
242 return false;
243 }
244
RGL_1DOcclusionTest(angle_t low,angle_t high)245 bool RGL_1DOcclusionTest(angle_t low, angle_t high)
246 {
247 // Check whether all angles in the given range are set (i.e. blocked).
248 // Returns true if the entire range is blocked, false otherwise.
249 // Angles are relative to the VIEW angle.
250
251 SYS_ASSERT((angle_t)(high - low) < ANG180);
252
253 if (low <= high)
254 return DoTest(low, high);
255 else
256 return DoTest(low, ANG_MAX) && DoTest(0, high);
257 }
258
259
260 #if 0 // OLD CODE
261
262 //----------------------------------------------------------------------------
263 //
264 // SPECIAL 1D OCCLUSION BUFFER
265 //
266
267 #define ONED_POWER 12 // 4096 angles
268 #define ONED_SIZE (1 << ONED_POWER)
269 #define ONED_TOTAL (ONED_SIZE / 32)
270
271 // 1 bit per angle, packed into 32 bit values.
272 // (NOTE: for speed reasons, 1 is "clear", and 0 is "blocked")
273 //
274 static u32_t oned_oculus_buffer[ONED_TOTAL];
275
276 // -AJA- these values could be computed (rather than looked-up)
277 // without too much trouble. For now I want to get the logic correct.
278 //
279 static u32_t oned_low_masks[32] =
280 {
281 0xFFFFFFFF, 0x7FFFFFFF, 0x3FFFFFFF, 0x1FFFFFFF,
282 0x0FFFFFFF, 0x07FFFFFF, 0x03FFFFFF, 0x01FFFFFF,
283 0x00FFFFFF, 0x007FFFFF, 0x003FFFFF, 0x001FFFFF,
284 0x000FFFFF, 0x0007FFFF, 0x0003FFFF, 0x0001FFFF,
285 0x0000FFFF, 0x00007FFF, 0x00003FFF, 0x00001FFF,
286 0x00000FFF, 0x000007FF, 0x000003FF, 0x000001FF,
287 0x000000FF, 0x0000007F, 0x0000003F, 0x0000001F,
288 0x0000000F, 0x00000007, 0x00000003, 0x00000001
289 };
290
291 static u32_t oned_high_masks[32] =
292 {
293 0x80000000, 0xC0000000, 0xE0000000, 0xF0000000,
294 0xF8000000, 0xFC000000, 0xFE000000, 0xFF000000,
295 0xFF800000, 0xFFC00000, 0xFFE00000, 0xFFF00000,
296 0xFFF80000, 0xFFFC0000, 0xFFFE0000, 0xFFFF0000,
297 0xFFFF8000, 0xFFFFC000, 0xFFFFE000, 0xFFFFF000,
298 0xFFFFF800, 0xFFFFFC00, 0xFFFFFE00, 0xFFFFFF00,
299 0xFFFFFF80, 0xFFFFFFC0, 0xFFFFFFE0, 0xFFFFFFF0,
300 0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE, 0xFFFFFFFF
301 };
302
303 #define LOW_MASK(L) oned_low_masks[L]
304 #define HIGH_MASK(H) oned_high_masks[H]
305
306
307 //
308 // RGL_1DOcclusionClear
309 //
310 // Clear all angles in the given range. (Clear means open, i.e. not
311 // blocked). The angles are relative to the VIEW angle.
312 //
313 void RGL_1DOcclusionClear(void)
314 {
315 int i;
316
317 for (i = 0; i < ONED_TOTAL; i++)
318 oned_oculus_buffer[i] = 0xFFFFFFFF;
319 }
320
321 //
322 // RGL_1DOcclusionSet
323 //
324 // Set all angles in the given range, i.e. mark them as blocking. The
325 // angles are relative to the VIEW angle.
326 //
327 void RGL_1DOcclusionSet(angle_t low, angle_t high)
328 {
329 SYS_ASSERT((angle_t)(high - low) < ANG180);
330
331 unsigned int low_b, high_b;
332
333 low >>= (ANGLEBITS - ONED_POWER);
334 high >>= (ANGLEBITS - ONED_POWER);
335
336 low_b = low & 0x1F; low >>= 5;
337 high_b = high & 0x1F; high >>= 5;
338
339 if (low == high)
340 {
341 oned_oculus_buffer[low] &= ~(LOW_MASK(low_b) & HIGH_MASK(high_b));
342 }
343 else
344 {
345 oned_oculus_buffer[low] &= ~LOW_MASK(low_b);
346 oned_oculus_buffer[high] &= ~HIGH_MASK(high_b);
347
348 low = (low+1) % ONED_TOTAL;
349
350 for (; low != high; low = (low+1) % ONED_TOTAL)
351 oned_oculus_buffer[low] = 0x00000000;
352 }
353 }
354
355 //
356 // RGL_1DOcclusionTest
357 //
358 // Check whether all angles in the given range are set (i.e. blocked).
359 // Returns true if the entire range is blocked, false otherwise.
360 // Angles are relative to the VIEW angle.
361 //
362 bool RGL_1DOcclusionTest(angle_t low, angle_t high)
363 {
364 SYS_ASSERT((angle_t)(high - low) < ANG180);
365
366 unsigned int low_b, high_b;
367
368 low >>= (ANGLEBITS - ONED_POWER);
369 high >>= (ANGLEBITS - ONED_POWER);
370
371 low_b = low & 0x1F; low >>= 5;
372 high_b = high & 0x1F; high >>= 5;
373
374 if (low == high)
375 return ! (oned_oculus_buffer[low] & (LOW_MASK(low_b) & HIGH_MASK(high_b)));
376
377 if (oned_oculus_buffer[low] & LOW_MASK(low_b))
378 return false;
379
380 if (oned_oculus_buffer[high] & HIGH_MASK(high_b))
381 return false;
382
383 low = (low+1) % ONED_TOTAL;
384
385 for (; low != high; low = (low+1) % ONED_TOTAL)
386 if (oned_oculus_buffer[low])
387 return false;
388
389 return true;
390 }
391
392 #endif // OLD CODE
393
394 //--- editor settings ---
395 // vi:ts=4:sw=4:noexpandtab
396