← Back to branch summary

~ubuntu-branches/ubuntu/maverick/glbsp/maverick

« back to all changes in this revision

Viewing changes to src/blockmap.c

  • Committer: Bazaar Package Importer
  • Author(s): Darren Salt
  • Date: 2008-01-30 13:33:49 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20080130133349-kgojg33vyiu8xbvp
Tags: 2.24-1
http://bugs.debian.org/460387
* New upstream release.
* Bumped the lib soname and the library package name due to one silly
  little binary incompatibility caused by changes in an exported struct.
  (Safe; nothing else currently in the archive has ever used libglbsp2.)
* Removed my patches since they're all applied upstream.
* Updated the list of documentation files.
* Build-time changes:
  - Switched from dh_movefiles to dh_install.
  - Updated my makefile to cope with upstream changes.
  - Corrected for debian-rules-ignores-make-clean-error.
  - Corrected for substvar-source-version-is-deprecated.
  - Link libglbsp, rather than glbsp, with libm and libz.
* Fixed shlibdeps. (Closes: #460387)
* Bumped standards version to 3.7.3 (no other changes).

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/blockmap.c
 
1
//------------------------------------------------------------------------
 
2
// BLOCKMAP : Generate the blockmap
 
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 "blockmap.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_BLOCKMAP  0
 
42
 
 
43
 
 
44
static int block_x, block_y;
 
45
static int block_w, block_h;
 
46
static int block_count;
 
47
 
 
48
static int block_mid_x = 0;
 
49
static int block_mid_y = 0;
 
50
 
 
51
static uint16_g ** block_lines;
 
52
 
 
53
static uint16_g *block_ptrs;
 
54
static uint16_g *block_dups;
 
55
 
 
56
static int block_compression;
 
57
static int block_overflowed;
 
58
 
 
59
#define DUMMY_DUP  0xFFFF
 
60
 
 
61
 
 
62
//
 
63
// GetBlockmapBounds
 
64
//
 
65
void GetBlockmapBounds(int *x, int *y, int *w, int *h)
 
66
{
 
67
  *x = block_x; *y = block_y;
 
68
  *w = block_w; *h = block_h;
 
69
}
 
70
 
 
71
//
 
72
// CheckLinedefInsideBox
 
73
//
 
74
int CheckLinedefInsideBox(int xmin, int ymin, int xmax, int ymax,
 
75
    int x1, int y1, int x2, int y2)
 
76
{
 
77
  int count = 2;
 
78
  int tmp;
 
79
 
 
80
  for (;;)
 
81
  {
 
82
    if (y1 > ymax)
 
83
    {
 
84
      if (y2 > ymax)
 
85
        return FALSE;
 
86
        
 
87
      x1 = x1 + (int) ((x2-x1) * (double)(ymax-y1) / (double)(y2-y1));
 
88
      y1 = ymax;
 
89
      
 
90
      count = 2;
 
91
      continue;
 
92
    }
 
93
 
 
94
    if (y1 < ymin)
 
95
    {
 
96
      if (y2 < ymin)
 
97
        return FALSE;
 
98
      
 
99
      x1 = x1 + (int) ((x2-x1) * (double)(ymin-y1) / (double)(y2-y1));
 
100
      y1 = ymin;
 
101
      
 
102
      count = 2;
 
103
      continue;
 
104
    }
 
105
 
 
106
    if (x1 > xmax)
 
107
    {
 
108
      if (x2 > xmax)
 
109
        return FALSE;
 
110
        
 
111
      y1 = y1 + (int) ((y2-y1) * (double)(xmax-x1) / (double)(x2-x1));
 
112
      x1 = xmax;
 
113
 
 
114
      count = 2;
 
115
      continue;
 
116
    }
 
117
 
 
118
    if (x1 < xmin)
 
119
    {
 
120
      if (x2 < xmin)
 
121
        return FALSE;
 
122
        
 
123
      y1 = y1 + (int) ((y2-y1) * (double)(xmin-x1) / (double)(x2-x1));
 
124
      x1 = xmin;
 
125
 
 
126
      count = 2;
 
127
      continue;
 
128
    }
 
129
 
 
130
    count--;
 
131
 
 
132
    if (count == 0)
 
133
      break;
 
134
 
 
135
    /* swap end points */
 
136
    tmp=x1;  x1=x2;  x2=tmp;
 
137
    tmp=y1;  y1=y2;  y2=tmp;
 
138
  }
 
139
 
 
140
  /* linedef touches block */
 
141
  return TRUE;
 
142
}
 
143
 
 
144
 
 
145
/* ----- create blockmap ------------------------------------ */
 
146
 
 
147
#define BK_NUM    0
 
148
#define BK_MAX    1
 
149
#define BK_XOR    2
 
150
#define BK_FIRST  3
 
151
 
 
152
#define BK_QUANTUM  32
 
153
 
 
154
static void BlockAdd(int blk_num, int line_index)
 
155
{
 
156
  uint16_g *cur = block_lines[blk_num];
 
157
 
 
158
# if DEBUG_BLOCKMAP
 
159
  PrintDebug("Block %d has line %d\n", blk_num, line_index);
 
160
# endif
 
161
 
 
162
  if (blk_num < 0 || blk_num >= block_count)
 
163
    InternalError("BlockAdd: bad block number %d", blk_num);
 
164
    
 
165
  if (! cur)
 
166
  {
 
167
    // create empty block
 
168
    block_lines[blk_num] = cur = UtilCalloc(BK_QUANTUM * 
 
169
        sizeof(uint16_g));
 
170
    cur[BK_NUM] = 0;
 
171
    cur[BK_MAX] = BK_QUANTUM;
 
172
    cur[BK_XOR] = 0x1234;
 
173
  }
 
174
 
 
175
  if (BK_FIRST + cur[BK_NUM] == cur[BK_MAX])
 
176
  {
 
177
    // no more room, so allocate some more...
 
178
    cur[BK_MAX] += BK_QUANTUM;
 
179
 
 
180
    block_lines[blk_num] = cur = UtilRealloc(cur, cur[BK_MAX] * 
 
181
        sizeof(uint16_g));
 
182
  }
 
183
 
 
184
  // compute new checksum
 
185
  cur[BK_XOR] = ((cur[BK_XOR] << 4) | (cur[BK_XOR] >> 12)) ^ line_index;
 
186
 
 
187
  cur[BK_FIRST + cur[BK_NUM]] = UINT16(line_index);
 
188
  cur[BK_NUM]++;
 
189
}
 
190
 
 
191
static void BlockAddLine(linedef_t *L)
 
192
{
 
193
  int x1 = (int) L->start->x;
 
194
  int y1 = (int) L->start->y;
 
195
  int x2 = (int) L->end->x;
 
196
  int y2 = (int) L->end->y;
 
197
 
 
198
  int bx1 = (MIN(x1,x2) - block_x) / 128;
 
199
  int by1 = (MIN(y1,y2) - block_y) / 128;
 
200
  int bx2 = (MAX(x1,x2) - block_x) / 128;
 
201
  int by2 = (MAX(y1,y2) - block_y) / 128;
 
202
 
 
203
  int bx, by;
 
204
  int line_index = L->index;
 
205
 
 
206
# if DEBUG_BLOCKMAP
 
207
  PrintDebug("BlockAddLine: %d (%d,%d) -> (%d,%d)\n", line_index, 
 
208
      x1, y1, x2, y2);
 
209
# endif
 
210
 
 
211
  // handle truncated blockmaps
 
212
  if (bx1 < 0) bx1 = 0;
 
213
  if (by1 < 0) by1 = 0;
 
214
  if (bx2 >= block_w) bx2 = block_w - 1;
 
215
  if (by2 >= block_h) by2 = block_h - 1;
 
216
 
 
217
  if (bx2 < bx1 || by2 < by1)
 
218
    return;
 
219
 
 
220
  // handle simple case #1: completely horizontal
 
221
  if (by1 == by2)
 
222
  {
 
223
    for (bx=bx1; bx <= bx2; bx++)
 
224
    {
 
225
      int blk_num = by1 * block_w + bx;
 
226
      BlockAdd(blk_num, line_index);
 
227
    }
 
228
    return;
 
229
  }
 
230
 
 
231
  // handle simple case #2: completely vertical
 
232
  if (bx1 == bx2)
 
233
  {
 
234
    for (by=by1; by <= by2; by++)
 
235
    {
 
236
      int blk_num = by * block_w + bx1;
 
237
      BlockAdd(blk_num, line_index);
 
238
    }
 
239
    return;
 
240
  }
 
241
 
 
242
  // handle the rest (diagonals)
 
243
 
 
244
  for (by=by1; by <= by2; by++)
 
245
  for (bx=bx1; bx <= bx2; bx++)
 
246
  {
 
247
    int blk_num = by * block_w + bx;
 
248
  
 
249
    int minx = block_x + bx * 128;
 
250
    int miny = block_y + by * 128;
 
251
    int maxx = minx + 127;
 
252
    int maxy = miny + 127;
 
253
 
 
254
    if (CheckLinedefInsideBox(minx, miny, maxx, maxy, x1, y1, x2, y2))
 
255
    {
 
256
      BlockAdd(blk_num, line_index);
 
257
    }
 
258
  }
 
259
}
 
260
 
 
261
static void CreateBlockmap(void)
 
262
{
 
263
  int i;
 
264
 
 
265
  block_lines = UtilCalloc(block_count * sizeof(uint16_g *));
 
266
 
 
267
  DisplayTicker();
 
268
 
 
269
  for (i=0; i < num_linedefs; i++)
 
270
  {
 
271
    linedef_t *L = LookupLinedef(i);
 
272
 
 
273
    // ignore zero-length lines
 
274
    if (L->zero_len)
 
275
      continue;
 
276
 
 
277
    BlockAddLine(L);
 
278
  }
 
279
}
 
280
 
 
281
 
 
282
static int BlockCompare(const void *p1, const void *p2)
 
283
{
 
284
  int blk_num1 = ((const uint16_g *) p1)[0];
 
285
  int blk_num2 = ((const uint16_g *) p2)[0];
 
286
 
 
287
  const uint16_g *A = block_lines[blk_num1];
 
288
  const uint16_g *B = block_lines[blk_num2];
 
289
 
 
290
  if (A == B)
 
291
    return 0;
 
292
 
 
293
  if (A == NULL) return -1;
 
294
  if (B == NULL) return +1;
 
295
 
 
296
  if (A[BK_NUM] != B[BK_NUM])
 
297
  {
 
298
    return A[BK_NUM] - B[BK_NUM];
 
299
  }
 
300
 
 
301
  if (A[BK_XOR] != B[BK_XOR])
 
302
  {
 
303
    return A[BK_XOR] - B[BK_XOR];
 
304
  }
 
305
 
 
306
  return memcmp(A+BK_FIRST, B+BK_FIRST, A[BK_NUM] * sizeof(uint16_g));
 
307
}
 
308
 
 
309
static void CompressBlockmap(void)
 
310
{
 
311
  int i;
 
312
  int cur_offset;
 
313
  int dup_count=0;
 
314
 
 
315
  int orig_size, new_size;
 
316
 
 
317
  block_ptrs = UtilCalloc(block_count * sizeof(uint16_g));
 
318
  block_dups = UtilCalloc(block_count * sizeof(uint16_g));
 
319
 
 
320
  DisplayTicker();
 
321
 
 
322
  // sort duplicate-detecting array.  After the sort, all duplicates
 
323
  // will be next to each other.  The duplicate array gives the order
 
324
  // of the blocklists in the BLOCKMAP lump.
 
325
  
 
326
  for (i=0; i < block_count; i++)
 
327
    block_dups[i] = i;
 
328
 
 
329
  qsort(block_dups, block_count, sizeof(uint16_g), BlockCompare);
 
330
 
 
331
  // scan duplicate array and build up offset array
 
332
 
 
333
  cur_offset = 4 + block_count + 2;
 
334
 
 
335
  orig_size = 4 + block_count;
 
336
  new_size  = cur_offset;
 
337
 
 
338
  DisplayTicker();
 
339
 
 
340
  for (i=0; i < block_count; i++)
 
341
  {
 
342
    int blk_num = block_dups[i];
 
343
    int count;
 
344
 
 
345
    // empty block ?
 
346
    if (block_lines[blk_num] == NULL)
 
347
    {
 
348
      block_ptrs[blk_num] = 4 + block_count;
 
349
      block_dups[i] = DUMMY_DUP;
 
350
 
 
351
      orig_size += 2;
 
352
      continue;
 
353
    }
 
354
 
 
355
    count = 2 + block_lines[blk_num][BK_NUM];
 
356
 
 
357
    // duplicate ?  Only the very last one of a sequence of duplicates
 
358
    // will update the current offset value.
 
359
 
 
360
    if (i+1 < block_count && 
 
361
        BlockCompare(block_dups + i, block_dups + i+1) == 0)
 
362
    {
 
363
      block_ptrs[blk_num] = cur_offset;
 
364
      block_dups[i] = DUMMY_DUP;
 
365
 
 
366
      // free the memory of the duplicated block
 
367
      UtilFree(block_lines[blk_num]);
 
368
      block_lines[blk_num] = NULL;
 
369
      
 
370
      dup_count++;
 
371
 
 
372
      orig_size += count;
 
373
      continue;
 
374
    }
 
375
 
 
376
    // OK, this block is either the last of a series of duplicates, or
 
377
    // just a singleton.
 
378
 
 
379
    block_ptrs[blk_num] = cur_offset;
 
380
 
 
381
    cur_offset += count;
 
382
 
 
383
    orig_size += count;
 
384
    new_size  += count;
 
385
  }
 
386
 
 
387
  if (cur_offset > 65535)
 
388
  {
 
389
    MarkSoftFailure(LIMIT_BLOCKMAP);
 
390
    block_overflowed = TRUE;
 
391
    return;
 
392
  }
 
393
 
 
394
# if DEBUG_BLOCKMAP
 
395
  PrintDebug("Blockmap: Last ptr = %d  duplicates = %d\n", 
 
396
      cur_offset, dup_count);
 
397
# endif
 
398
 
 
399
  block_compression = (orig_size - new_size) * 100 / orig_size;
 
400
 
 
401
  // there's a tiny chance of new_size > orig_size
 
402
  if (block_compression < 0)
 
403
    block_compression = 0;
 
404
}
 
405
 
 
406
 
 
407
static void WriteBlockmap(void)
 
408
{
 
409
  int i;
 
410
  
 
411
  raw_blockmap_header_t header;
 
412
 
 
413
  lump_t *lump = CreateLevelLump("BLOCKMAP");
 
414
 
 
415
  uint16_g null_block[2] = { 0x0000, 0xFFFF };
 
416
  uint16_g m_zero = 0x0000;
 
417
  uint16_g m_neg1 = 0xFFFF;
 
418
  
 
419
  // leave empty if the blockmap overflowed
 
420
  if (block_overflowed)
 
421
    return;
 
422
 
 
423
  // fill in header
 
424
  header.x_origin = UINT16(block_x);
 
425
  header.y_origin = UINT16(block_y);
 
426
  header.x_blocks = UINT16(block_w);
 
427
  header.y_blocks = UINT16(block_h);
 
428
  
 
429
  AppendLevelLump(lump, &header, sizeof(header));
 
430
 
 
431
  // handle pointers
 
432
  for (i=0; i < block_count; i++)
 
433
  {
 
434
    uint16_g ptr = UINT16(block_ptrs[i]);
 
435
 
 
436
    if (ptr == 0)
 
437
      InternalError("WriteBlockmap: offset %d not set.", i);
 
438
 
 
439
    AppendLevelLump(lump, &ptr, sizeof(uint16_g));
 
440
  }
 
441
 
 
442
  // add the null block which _all_ empty blocks will use
 
443
  AppendLevelLump(lump, null_block, sizeof(null_block));
 
444
 
 
445
  // handle each block list
 
446
  for (i=0; i < block_count; i++)
 
447
  {
 
448
    int blk_num = block_dups[i];
 
449
    uint16_g *blk;
 
450
 
 
451
    // ignore duplicate or empty blocks
 
452
    if (blk_num == DUMMY_DUP)
 
453
      continue;
 
454
 
 
455
    blk = block_lines[blk_num];
 
456
 
 
457
    if (blk == NULL)
 
458
      InternalError("WriteBlockmap: block %d is NULL !", i);
 
459
 
 
460
    AppendLevelLump(lump, &m_zero, sizeof(uint16_g));
 
461
    AppendLevelLump(lump, blk + BK_FIRST, blk[BK_NUM] * sizeof(uint16_g));
 
462
    AppendLevelLump(lump, &m_neg1, sizeof(uint16_g));
 
463
  }
 
464
}
 
465
 
 
466
 
 
467
static void FreeBlockmap(void)
 
468
{
 
469
  int i;
 
470
 
 
471
  for (i=0; i < block_count; i++)
 
472
  {
 
473
    if (block_lines[i])
 
474
      UtilFree(block_lines[i]);
 
475
  }
 
476
 
 
477
  UtilFree(block_lines);
 
478
  UtilFree(block_ptrs);
 
479
  UtilFree(block_dups);
 
480
}
 
481
 
 
482
 
 
483
/* ----- top level funcs ------------------------------------ */
 
484
 
 
485
static void FindBlockmapLimits(bbox_t *bbox)
 
486
{
 
487
  int i;
 
488
 
 
489
  int mid_x = 0;
 
490
  int mid_y = 0;
 
491
 
 
492
  bbox->minx = bbox->miny = SHRT_MAX;
 
493
  bbox->maxx = bbox->maxy = SHRT_MIN;
 
494
 
 
495
  for (i=0; i < num_linedefs; i++)
 
496
  {
 
497
    linedef_t *L = LookupLinedef(i);
 
498
 
 
499
    if (! L->zero_len)
 
500
    {
 
501
      float_g x1 = L->start->x;
 
502
      float_g y1 = L->start->y;
 
503
      float_g x2 = L->end->x;
 
504
      float_g y2 = L->end->y;
 
505
 
 
506
      int lx = (int)floor(MIN(x1, x2));
 
507
      int ly = (int)floor(MIN(y1, y2));
 
508
      int hx = (int)ceil(MAX(x1, x2));
 
509
      int hy = (int)ceil(MAX(y1, y2));
 
510
 
 
511
      if (lx < bbox->minx) bbox->minx = lx;
 
512
      if (ly < bbox->miny) bbox->miny = ly;
 
513
      if (hx > bbox->maxx) bbox->maxx = hx;
 
514
      if (hy > bbox->maxy) bbox->maxy = hy;
 
515
 
 
516
      // compute middle of cluster (roughly, so we don't overflow)
 
517
      mid_x += (lx + hx) / 32;
 
518
      mid_y += (ly + hy) / 32;
 
519
    }
 
520
  }
 
521
 
 
522
  if (num_linedefs > 0)
 
523
  {
 
524
    block_mid_x = (mid_x / num_linedefs) * 16;
 
525
    block_mid_y = (mid_y / num_linedefs) * 16;
 
526
  }
 
527
 
 
528
# if DEBUG_BLOCKMAP
 
529
  PrintDebug("Blockmap lines centered at (%d,%d)\n", block_mid_x, block_mid_y);
 
530
# endif
 
531
}
 
532
 
 
533
//
 
534
// TruncateBlockmap
 
535
//
 
536
static void TruncateBlockmap(void)
 
537
{
 
538
  while (block_w * block_h > cur_info->block_limit)
 
539
  {
 
540
    block_w -= block_w / 8;
 
541
    block_h -= block_h / 8;
 
542
  }
 
543
 
 
544
  block_count = block_w * block_h;
 
545
 
 
546
  PrintMiniWarn("Blockmap TOO LARGE!  Truncated to %dx%d blocks\n",
 
547
      block_w, block_h);
 
548
 
 
549
  MarkSoftFailure(LIMIT_BMAP_TRUNC);
 
550
 
 
551
  /* center the truncated blockmap */
 
552
  block_x = block_mid_x - block_w * 64;
 
553
  block_y = block_mid_y - block_h * 64;
 
554
 
 
555
# if DEBUG_BLOCKMAP
 
556
  PrintDebug("New blockmap origin: (%d,%d)\n", block_x, block_y);
 
557
# endif
 
558
}
 
559
 
 
560
//
 
561
// InitBlockmap
 
562
//
 
563
void InitBlockmap(void)
 
564
{
 
565
  bbox_t map_bbox;
 
566
 
 
567
  /* find limits of linedefs, and store as map limits */
 
568
  FindBlockmapLimits(&map_bbox);
 
569
 
 
570
  PrintVerbose("Map goes from (%d,%d) to (%d,%d)\n",
 
571
      map_bbox.minx, map_bbox.miny, map_bbox.maxx, map_bbox.maxy);
 
572
 
 
573
  block_x = map_bbox.minx - (map_bbox.minx & 0x7);
 
574
  block_y = map_bbox.miny - (map_bbox.miny & 0x7);
 
575
 
 
576
  block_w = ((map_bbox.maxx - block_x) / 128) + 1;
 
577
  block_h = ((map_bbox.maxy - block_y) / 128) + 1;
 
578
  block_count = block_w * block_h;
 
579
 
 
580
}
 
581
 
 
582
//
 
583
// PutBlockmap
 
584
//
 
585
void PutBlockmap(void)
 
586
{
 
587
  block_overflowed = FALSE;
 
588
 
 
589
  // truncate blockmap if too large.  We're limiting the number of
 
590
  // blocks to around 16000 (user changeable), this leaves about 48K
 
591
  // of shorts for the actual line lists.
 
592
 
 
593
  if (block_count > cur_info->block_limit)
 
594
    TruncateBlockmap();
 
595
 
 
596
  // initial phase: create internal blockmap containing the index of
 
597
  // all lines in each block.
 
598
  
 
599
  CreateBlockmap();
 
600
 
 
601
  // -AJA- second phase: compress the blockmap.  We do this by sorting
 
602
  //       the blocks, which is a typical way to detect duplicates in
 
603
  //       a large list.
 
604
 
 
605
  CompressBlockmap();
 
606
 
 
607
  // final phase: write it out in the correct format
 
608
 
 
609
  WriteBlockmap();
 
610
 
 
611
  if (block_overflowed)
 
612
    PrintVerbose("Blockmap overflowed (lump will be empty)\n");
 
613
  else
 
614
    PrintVerbose("Completed blockmap, size %dx%d (compression: %d%%)\n",
 
615
        block_w, block_h, block_compression);
 
616
 
 
617
  FreeBlockmap();
 
618
}
 
619