clip.cpp 97.1 KB
Newer Older
1
2
3
4
5
6
7
8
// "Build Engine & Tools" Copyright (c) 1993-1997 Ken Silverman
// Ken Silverman's official web site: "http://www.advsys.net/ken"
// See the included license file "BUILDLIC.TXT" for license info.
//
// This file has been modified from Ken Silverman's original release
// by Jonathon Fowler (jf@jonof.id.au)
// by the EDuke32 team (development@voidpoint.com)

9
#include "a.h"
10
#include "build.h"
Evan Ramos's avatar
Evan Ramos committed
11
#include "baselayer.h"
12
#include "clip.h"
13
14
#include "engine_priv.h"

15
16
17
18
19
static int16_t clipnum;
static linetype clipit[MAXCLIPNUM];
static int32_t clipsectnum, origclipsectnum, clipspritenum;
int16_t clipsectorlist[MAXCLIPSECTORS];
static int16_t origclipsectorlist[MAXCLIPSECTORS];
20
21
static uint8_t clipsectormap[(MAXSECTORS+7)>>3];
static uint8_t origclipsectormap[(MAXSECTORS+7)>>3];
22
#ifdef HAVE_CLIPSHAPE_FEATURE
23
static int16_t clipspritelist[MAXCLIPNUM];  // sector-like sprite clipping
24
#endif
Richard Gobeille's avatar
Richard Gobeille committed
25
static int16_t clipobjectval[MAXCLIPNUM];
26
static uint8_t clipignore[(MAXCLIPNUM+7)>>3];
27

28
29
////// sector-like clipping for sprites //////
#ifdef HAVE_CLIPSHAPE_FEATURE
Richard Gobeille's avatar
Richard Gobeille committed
30
void engineSetClipMap(mapinfo_t *bak, mapinfo_t *newmap)
31
32
33
34
35
{
    if (bak)
    {
        bak->numsectors = numsectors;
        bak->numwalls = numwalls;
Richard Gobeille's avatar
Richard Gobeille committed
36
37
        bak->sector = (usectortype *) sector;
        bak->wall = (uwalltype *) wall;
38
39
40
41
42
43
    }

    if (newmap)
    {
        numsectors = newmap->numsectors;
        numwalls = newmap->numwalls;
44
45
        sector = const_cast<sectortype *>((sectortype const *)newmap->sector);
        wall = const_cast<walltype *>((walltype const *)newmap->wall);
46
47
48
    }
}

49
static mapinfo_t origmapinfo, clipmapinfo;
50
51
int32_t quickloadboard=0;

52
static clipinfo_t clipinfo[CM_MAX];
53
54
55
56
static int32_t numclipmaps;

static int32_t numclipsects;  // number in sectq[]
static int16_t *sectoidx;
57
58
static int16_t *sectq;  // [numsectors]
static int16_t pictoidx[MAXTILES];  // maps tile num to clipinfo[] index
59
60
static int16_t *tempictoidx;

Richard Gobeille's avatar
Richard Gobeille committed
61
62
63
static usectortype *loadsector;
static uwalltype *loadwall, *loadwallinv;
static uspritetype *loadsprite;
64

Evan Ramos's avatar
Evan Ramos committed
65
vec2_t hitscangoal = { (1<<29)-1, (1<<29)-1 };
66
67
68
#ifdef USE_OPENGL
int32_t hitallsprites = 0;
#endif
69

Richard Gobeille's avatar
Richard Gobeille committed
70
void engineInitClipMaps()
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
{
    numclipmaps = 0;
    numclipsects = 0;

    DO_FREE_AND_NULL(sectq);
    DO_FREE_AND_NULL(sectoidx);
    DO_FREE_AND_NULL(tempictoidx);
    DO_FREE_AND_NULL(loadsector);
    DO_FREE_AND_NULL(loadwall);
    DO_FREE_AND_NULL(loadwallinv);
    DO_FREE_AND_NULL(loadsprite);

    // two's complement trick, -1 = 0xff
    Bmemset(&pictoidx, -1, sizeof(pictoidx));
    Bmemset(&clipmapinfo, 0, sizeof(mapinfo_t));

    numsectors = 0;
    numwalls = 0;
}

// loads the clip maps.
// this should be called before any real map is loaded.
Richard Gobeille's avatar
Richard Gobeille committed
93
int32_t engineLoadClipMaps(void)
94
95
96
97
{
    int32_t i, k, w;

    int32_t lwcp = 0;
98
99
    size_t fi;
    size_t const g_clipMapFilesNum = g_clipMapFiles.size();
100
101
102
103
104
105

    int32_t *fisec = NULL;
    int32_t *fispr = NULL;

    int32_t ournumsectors=0, ournumwalls=0, ournumsprites=0;

Richard Gobeille's avatar
Richard Gobeille committed
106
    engineInitClipMaps();
107

Richard Gobeille's avatar
Richard Gobeille committed
108
109
110
    loadsector = (usectortype *) Xmalloc(MAXSECTORS * sizeof(sectortype));
    loadwall = (uwalltype *) Xmalloc(MAXWALLS * sizeof(walltype));
    loadsprite = (uspritetype *) Xmalloc(MAXSPRITES * sizeof(spritetype));
111
112

    if (g_clipMapFilesNum)
113
    {
114
115
        fisec = (int32_t *) Xcalloc(g_clipMapFilesNum, sizeof(int32_t));
        fispr = (int32_t *) Xcalloc(g_clipMapFilesNum, sizeof(int32_t));
116
    }
117
118
119
120
121
122
123
124
125
126

    quickloadboard = 1;
    for (fi = 0; fi < g_clipMapFilesNum; ++fi)
    {
        int16_t ang, cs;
        vec3_t tmppos;

        fisec[fi] = ournumsectors;
        fispr[fi] = ournumsprites;

Richard Gobeille's avatar
Richard Gobeille committed
127
        i = engineLoadBoard(g_clipMapFiles[fi], 8, &tmppos, &ang, &cs);
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
        if (i<0)
            continue;
        // Numsprites will now be set!

        initprintf("Loading clip map: %s\n", g_clipMapFiles[fi]);

        if (ournumsectors+numsectors>MAXSECTORS ||
            ournumwalls+numwalls>MAXWALLS ||
            ournumsprites+Numsprites>MAXSPRITES)
        {
            initprintf("clip map: warning: exceeded limits when loading %s, aborting.\n", g_clipMapFiles[fi]);
            break;
        }

        Bmemcpy(loadsector+ournumsectors, sector, numsectors*sizeof(sectortype));
        Bmemcpy(loadwall+ournumwalls, wall, numwalls*sizeof(walltype));
        Bmemcpy(loadsprite+ournumsprites, sprite, Numsprites*sizeof(spritetype));
        for (i=ournumsectors; i<ournumsectors+numsectors; i++)
            loadsector[i].wallptr += ournumwalls;
        for (i=ournumwalls; i<ournumwalls+numwalls; i++)
        {
            if (loadwall[i].point2>=0)
                loadwall[i].point2 += ournumwalls;
            if (loadwall[i].nextwall>=0)
            {
                loadwall[i].nextwall += ournumwalls;
                loadwall[i].nextsector += ournumsectors;
            }
        }
        for (i=ournumsprites; i<ournumsprites+Numsprites; i++)
            if (loadsprite[i].sectnum>=0)
                loadsprite[i].sectnum += ournumsectors;
        ournumsectors += numsectors;
        ournumwalls += numwalls;
        ournumsprites += Numsprites;

        ++lwcp;
    }
    quickloadboard = 0;

    if (ournumsectors==0 || ournumwalls==0 || ournumsprites==0)  // nothing loaded
    {
Richard Gobeille's avatar
Richard Gobeille committed
170
        engineInitClipMaps();
171

172
173
        Xfree(fisec);
        Xfree(fispr);
174
175
176
177
178

        return -1;
    }

    // shrink
Richard Gobeille's avatar
Richard Gobeille committed
179
180
    loadsector = (usectortype *) Xrealloc(loadsector, ournumsectors*sizeof(sectortype));
    loadwall = (uwalltype *) Xrealloc(loadwall, ournumwalls*sizeof(walltype));
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255

    Bmemcpy(sector, loadsector, ournumsectors*sizeof(sectortype));
    Bmemcpy(wall, loadwall, ournumwalls*sizeof(walltype));
    Bmemcpy(sprite, loadsprite, ournumsprites*sizeof(spritetype));
    numsectors = ournumsectors;
    numwalls = ournumwalls;

    //  vvvv    don't use headsprite[sect,stat]!   vvvv

    sectoidx = (int16_t *) Xmalloc(numsectors*sizeof(sectoidx[0]));

    for (i=0; i<numsectors; i++)
        sectoidx[i] = CM_NONE;

    // determine outer sectors
    for (i=0; i<numsectors; i++)
    {
        for (w=sector[i].wallptr; w<sector[i].wallptr+sector[i].wallnum; w++)
            if (wall[w].nextsector<0)
            {
                sectoidx[i] = CM_OUTER;
                break;
            }
    }
    // break connections between outer sectors
    for (i=0; i<numsectors; i++)
    {
        if (sectoidx[i] == CM_OUTER)
            for (w=sector[i].wallptr; w<sector[i].wallptr+sector[i].wallnum; w++)
            {
                k = wall[w].nextwall;
                if (k>=0 && sectoidx[wall[w].nextsector]==CM_OUTER)
                {
                    wall[k].nextwall = wall[k].nextsector = -1;
                    wall[w].nextwall = wall[w].nextsector = -1;
                }
            }
    }

    {
        int16_t ns, outersect;
        int32_t pn, scnt, x, y, z, maxdist;

        sectq = (int16_t *) Xmalloc(numsectors*sizeof(sectq[0]));
        tempictoidx = (int16_t *) Xmalloc(MAXTILES*sizeof(tempictoidx[0]));

        for (i=0; i<MAXTILES; i++)
            tempictoidx[i]=-1;

        // collect sprite picnums
        for (i=0; i<MAXSPRITES && sprite[i].statnum<MAXSTATUS; i++)
        {
            pn = sprite[i].picnum;
            k = sprite[i].sectnum;
            //    -v-  note the <=                         ignore sprites in outer sectors
            if (pn<=0 || pn>=MAXTILES || k<0 || k>=numsectors || (sectoidx[k]&CM_OUTER))
                continue;

            if (numclipmaps >= CM_MAX)
            {
                initprintf("warning: reached max clip map number %d, not processing any more\n", CM_MAX);
                break;
            }

            // chain
            if (pictoidx[pn]>=0)
            {
                if (sectoidx[k]&CM_SOME)
                {
                    for (fi = 0; fi < g_clipMapFilesNum; ++fi)
                        if (k>=fisec[fi])
                            break;
                    initprintf("clip map \"%s\": error: tried to chain picnum %d (sprite %d) in sector %d which"
                        " already belongs to picnum %d.\n", g_clipMapFiles[fi], pn, i-fispr[fi], k-fisec[fi],
                        clipinfo[sectoidx[k]].picnum);
Richard Gobeille's avatar
Richard Gobeille committed
256
                    engineInitClipMaps();
257

258
259
                    Xfree(fisec);
                    Xfree(fispr);
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319

                    return 2;
                }

                // new one is front
                clipinfo[numclipmaps].next = pictoidx[pn];
                pictoidx[pn] = numclipmaps;
            }
            else
            {
                clipinfo[numclipmaps].next = -1;
                pictoidx[pn] = numclipmaps;
            }

            if (!CM_NOROT(i))
            {
                if (sprite[i].ang!=1536 && sprite[i].ang!=512)
                {
                    for (fi = 0; fi < g_clipMapFilesNum; ++fi)
                        if (i>=fispr[fi])
                            break;
                    initprintf("clip map \"%s\": warning: sprite %d pointing neither northward nor southward. %s will be wrong.\n",
                        g_clipMapFiles[fi], i-fispr[fi], (sprite[i].cstat&48)==32 ? "Scaling and flipping" : "X-flipping");
                }
            }

            clipinfo[numclipmaps].picnum = pn;

            // collect sectors
            scnt = numclipsects;
            sectq[numclipsects++] = k;
            sectoidx[k] = numclipmaps;

            clipinfo[numclipmaps].qbeg = scnt;

            outersect = -1;

            do
            {
                k = sectq[scnt];

                for (w=sector[k].wallptr; w<sector[k].wallptr+sector[k].wallnum; w++)
                {
                    ns = wall[w].nextsector;
                    if (ns>=0)
                    {
                        if (sectoidx[ns]==CM_NONE)
                        {
                            sectoidx[ns] = numclipmaps;
                            sectq[numclipsects++] = ns;
                        }
                        else if (sectoidx[ns]&CM_OUTER)
                        {
                            if (outersect>=0 && ns!=outersect)
                            {
                                for (fi = 0; fi < g_clipMapFilesNum; ++fi)
                                    if (ns>=fisec[fi])
                                        break;
                                initprintf("clip map \"%s\": error: encountered more than one outer sector (%d and %d)"
                                    " for sprite %d.\n", g_clipMapFiles[fi], outersect-fisec[fi], ns-fisec[fi], i-fispr[fi]);
Richard Gobeille's avatar
Richard Gobeille committed
320
                                engineInitClipMaps();
321

322
323
                                Xfree(fisec);
                                Xfree(fispr);
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338

                                return 3;
                            }

                            outersect = ns;
                            sectoidx[outersect] |= numclipmaps;
                        }
                        else if (sectoidx[ns]!=numclipmaps)
                        {
                            for (fi = 0; fi < g_clipMapFilesNum; ++fi)
                                if (ns>=fisec[fi])
                                    break;
                            initprintf("clip map \"%s\": error: encountered sector %d belonging to index %d"
                                " while collecting sectors for sprite %d (index %d).\n",
                                g_clipMapFiles[fi], ns-fisec[fi], sectoidx[ns], i-fispr[fi], numclipmaps);
Richard Gobeille's avatar
Richard Gobeille committed
339
                            engineInitClipMaps();
340

341
342
                            Xfree(fisec);
                            Xfree(fispr);
343
344
345
346
347
348
349
350
351
352

                            return 4;
                        }
                    }
                }
            } while (++scnt < numclipsects);

            if (outersect==-1)
            {
                initprintf("clip map: INTERNAL ERROR: outersect==-1!\n");
Richard Gobeille's avatar
Richard Gobeille committed
353
                engineInitClipMaps();
354

355
356
                Xfree(fisec);
                Xfree(fispr);
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384

                return 5;
            }

            sectq[numclipsects++] = outersect;  // last is outer
            clipinfo[numclipmaps].qend = numclipsects-1;

            // normalize
            maxdist = 0;

            for (scnt=clipinfo[numclipmaps].qbeg; scnt<=clipinfo[numclipmaps].qend; scnt++)
            {
                k = sectq[scnt];

                x = sprite[i].x;
                y = sprite[i].y;
                z = sprite[i].z;

                sector[k].floorz -= z;
                sector[k].ceilingz -= z;

                if (scnt==clipinfo[numclipmaps].qbeg)
                {
                    // backup sprite tags since we'll discard sprites later
                    sector[k].CM_XREPEAT = sprite[i].xrepeat;
                    sector[k].CM_YREPEAT = sprite[i].yrepeat;
                    sector[k].CM_XOFFSET = sprite[i].xoffset;
                    sector[k].CM_YOFFSET = sprite[i].yoffset;
Richard Gobeille's avatar
Richard Gobeille committed
385
386
                    sector[k].CM_CSTAT   = sprite[i].cstat;
                    sector[k].CM_ANG     = sprite[i].ang;
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
                }

                // backup floor and ceiling z
                CM_FLOORZ(k) = sector[k].floorz;
                CM_CEILINGZ(k) = sector[k].ceilingz;

                for (w=sector[k].wallptr; w<sector[k].wallptr+sector[k].wallnum; w++)
                {
                    wall[w].x -= x;
                    wall[w].y -= y;

                    if (scnt!=clipinfo[numclipmaps].qend)
                    {
                        if (CM_NOROT(i))
                        {
                            if (klabs(wall[w].x) > maxdist)
                                maxdist = klabs(wall[w].x);
                            if (klabs(wall[w].y) > maxdist)
                                maxdist = klabs(wall[w].y);
                        }
                        else
                        {
                            int32_t tmp = ksqrt(uhypsq(wall[w].x, wall[w].y));
                            if (tmp > maxdist)
                                maxdist = tmp;
                        }
                    }

                    // aliasing
                    if (wall[w].lotag>0 || wall[w].hitag>0)
                    {
                        int32_t ii;

                        if (wall[w].lotag>0 && wall[w].hitag>0)
                        {
                            if (wall[w].lotag > wall[w].hitag)
                                swapshort(&wall[w].lotag, &wall[w].hitag);

                            for (ii=wall[w].lotag; ii<wall[w].hitag; ii++)
                                tempictoidx[ii] = numclipmaps;
                        }
                        else if (wall[w].lotag>0)
                        {
                            if (wall[w].lotag<MAXTILES)
                                tempictoidx[wall[w].lotag] = numclipmaps;
                        }
                        else
                        {
                            if (wall[w].hitag<MAXTILES)
                                tempictoidx[wall[w].hitag] = numclipmaps;
                        }
                    }

                    CM_WALL_X(w) = wall[w].x;
                    CM_WALL_Y(w) = wall[w].y;
                }
            }

            clipinfo[numclipmaps].maxdist = maxdist;
            numclipmaps++;
        }
    }

    // yes, too much copying, but better than ugly code
    Bmemcpy(loadsector, sector, ournumsectors*sizeof(sectortype));
    Bmemcpy(loadwall, wall, ournumwalls*sizeof(walltype));

    // loadwallinv will contain all walls with inverted orientation for x/y-flip handling
Richard Gobeille's avatar
Richard Gobeille committed
455
    loadwallinv = (uwalltype *) Xmalloc(ournumwalls*sizeof(walltype));
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520

    {
        int32_t j, loopstart, loopend, numloopwalls;

        // invert walls!
        loopstart = 0;
        for (j=0; j<ournumwalls; j++)
        {
            wall[j].nextsector = wall[j].nextwall = -1;

            if (wall[j].point2 < j)
            {
                loopend = j+1;
                numloopwalls = loopend-loopstart;

                if (numloopwalls<3)
                {
                    loopstart = loopend;
                    continue;
                }

                for (k=0; k<numloopwalls; k++)
                {
                    wall[loopstart+k].x = loadwall[loopstart + (numloopwalls+1-k)%numloopwalls].x;
                    wall[loopstart+k].y = loadwall[loopstart + (numloopwalls+1-k)%numloopwalls].y;

                    CM_WALL_X(loopstart+k) = wall[loopstart+k].x;
                    CM_WALL_Y(loopstart+k) = wall[loopstart+k].y;
                }

                loopstart = loopend;
            }
        }

        // reconstruct wall connections
        for (i=0; i<ournumsectors; i++)
        {
            for (j=sector[i].wallptr; j<sector[i].wallptr+sector[i].wallnum; j++)
                checksectorpointer(j, i);
        }
    }
    Bmemcpy(loadwallinv, wall, ournumwalls*sizeof(walltype));

    clipmapinfo.numsectors = numsectors;
    clipmapinfo.sector = loadsector;
    clipmapinfo.numwalls = numwalls;
    clipmapinfo.wall = loadwall;

    for (i=0; i<MAXTILES; i++)
    {
        if (pictoidx[i]==-1 && tempictoidx[i]>=0)
            pictoidx[i]=tempictoidx[i];
    }

    DO_FREE_AND_NULL(loadsprite);
    DO_FREE_AND_NULL(tempictoidx);

    // don't let other code be distracted by the temporary map we constructed
    numsectors = 0;
    numwalls = 0;
    initspritelists();

    if (lwcp > 0)
        initprintf("Loaded clip map%s.\n", lwcp==1 ? "" : "s");

521
522
    Xfree(fisec);
    Xfree(fispr);
523
524
525
526
527

    return 0;
}


528
int clipshape_idx_for_sprite(uspriteptr_t const curspr, int curidx)
529
{
Richard Gobeille's avatar
Richard Gobeille committed
530
531
     // per-sprite init
     curidx = (curidx < 0) ? pictoidx[curspr->picnum] : clipinfo[curidx].next;
532

Richard Gobeille's avatar
Richard Gobeille committed
533
534
     while (curidx >= 0 && (curspr->cstat & 32) != (sector[sectq[clipinfo[curidx].qbeg]].CM_CSTAT & 32))
         curidx = clipinfo[curidx].next;
535

Richard Gobeille's avatar
Richard Gobeille committed
536
     return curidx;
537
538
}
#else
539
int32_t clipshape_idx_for_sprite(uspriteptr_t const curspr, int32_t curidx)
540
{
541
    (void)curspr;
542
543
544
545
546
547
548
549
550
551
552
553
554
    UNREFERENCED_PARAMETER(curidx);
    return -1;
}
#endif  // HAVE_CLIPSHAPE_FEATURE
////// //////

////////// CLIPMOVE //////////

int32_t clipmoveboxtracenum = 3;

//
// clipinsidebox
//
555
int clipinsidebox(vec2_t const * const vect, int const wallnum, int const walldist)
556
{
557
558
559
560
561
562
563
    int const r = walldist << 1;

    auto const wal1 = (uwallptr_t)&wall[wallnum];
    auto const wal2 = (uwallptr_t)&wall[wal1->point2];

    vec2_t const v1 = { wal1->x + walldist - vect->x, wal1->y + walldist - vect->y };
    vec2_t       v2 = { wal2->x + walldist - vect->x, wal2->y + walldist - vect->y };
Richard Gobeille's avatar
Richard Gobeille committed
564
565

    if (((v1.x < 0) && (v2.x < 0)) || ((v1.y < 0) && (v2.y < 0)) || ((v1.x >= r) && (v2.x >= r)) || ((v1.y >= r) && (v2.y >= r)))
566
        return 0;
567
568
569

    v2.x -= v1.x; v2.y -= v1.y;

Richard Gobeille's avatar
Richard Gobeille committed
570
    if (v2.x * (walldist - v1.y) >= v2.y * (walldist - v1.x))  // Front
571
572
    {
        v2.x *= ((v2.x > 0) ? (0 - v1.y) : (r - v1.y));
Richard Gobeille's avatar
Richard Gobeille committed
573
        v2.y *= ((v2.y > 0) ? (r - v1.x) : (0 - v1.x));
574
575
576
        return v2.x < v2.y;
    }

Richard Gobeille's avatar
Richard Gobeille committed
577
578
579
    v2.x *= ((v2.x > 0) ? (r - v1.y) : (0 - v1.y));
    v2.y *= ((v2.y > 0) ? (0 - v1.x) : (r - v1.x));
    return (v2.x >= v2.y) << 1;
580
581
582
583
584
585
}


//
// clipinsideboxline
//
Richard Gobeille's avatar
Richard Gobeille committed
586
int clipinsideboxline(int x, int y, int x1, int y1, int x2, int y2, int walldist)
587
{
Richard Gobeille's avatar
Richard Gobeille committed
588
    int const r = walldist << 1;
589

Richard Gobeille's avatar
Richard Gobeille committed
590
591
    x1 += walldist - x;
    x2 += walldist - x;
592
593

    if (((x1 < 0) && (x2 < 0)) || ((x1 >= r) && (x2 >= r)))
594
        return 0;
595

Richard Gobeille's avatar
Richard Gobeille committed
596
597
    y1 += walldist - y;
    y2 += walldist - y;
598
599

    if (((y1 < 0) && (y2 < 0)) || ((y1 >= r) && (y2 >= r)))
600
        return 0;
601

Richard Gobeille's avatar
Richard Gobeille committed
602
603
    x2 -= x1;
    y2 -= y1;
604

Richard Gobeille's avatar
Richard Gobeille committed
605
    if (x2 * (walldist - y1) >= y2 * (walldist - x1))  // Front
606
    {
Richard Gobeille's avatar
Richard Gobeille committed
607
608
        x2 *= ((x2 > 0) ? (0 - y1) : (r - y1));
        y2 *= ((y2 > 0) ? (r - x1) : (0 - x1));
609
610
611
        return x2 < y2;
    }

Richard Gobeille's avatar
Richard Gobeille committed
612
613
614
    x2 *= ((x2 > 0) ? (r - y1) : (0 - y1));
    y2 *= ((y2 > 0) ? (0 - x1) : (r - x1));
    return (x2 >= y2) << 1;
615
616
}

617
618
619
620
static int32_t clipmove_warned;

static inline void addclipsect(int const sectnum)
{
621
    if (clipsectnum < MAXCLIPSECTORS)
622
623
624
625
626
627
628
    {
        bitmap_set(clipsectormap, sectnum);
        clipsectorlist[clipsectnum++] = sectnum;
    }
    else
        clipmove_warned |= 1;
}
629
630

#ifdef HAVE_CLIPSHAPE_FEATURE
631
int32_t clipsprite_try(uspriteptr_t const spr, int32_t xmin, int32_t ymin, int32_t xmax, int32_t ymax)
632
633
634
635
636
637
638
639
640
641
642
643
{
    // try and see whether this sprite's picnum has sector-like clipping data
    int32_t i = pictoidx[spr->picnum];
    // handle sector-like floor sprites separately
    while (i>=0 && (spr->cstat&32) != (clipmapinfo.sector[sectq[clipinfo[i].qbeg]].CM_CSTAT&32))
        i = clipinfo[i].next;

    if (i>=0)
    {
        int32_t maxcorrection = clipinfo[i].maxdist;
        const int32_t k = sectq[clipinfo[i].qbeg];

644
        if ((spr->cstat&CSTAT_SPRITE_ALIGNMENT)!=CSTAT_SPRITE_ALIGNMENT_FLOOR)
645
        {
646
            int32_t const tempint1 = clipmapinfo.sector[k].CM_XREPEAT;
647
648
            maxcorrection = divideu32_noinline(maxcorrection * (int32_t) spr->xrepeat, tempint1);
        }
649
        else
650
        {
651
652
            int32_t const tempint1 = clipmapinfo.sector[k].CM_XREPEAT;
            int32_t const tempint2 = clipmapinfo.sector[k].CM_YREPEAT;
653
654
655
656
657
658
            maxcorrection = max(divideu32_noinline(maxcorrection * (int32_t) spr->xrepeat, tempint1),
                divideu32_noinline(maxcorrection * (int32_t) spr->yrepeat, tempint2));
        }

        maxcorrection -= MAXCLIPDIST;

659
660
661
        if ((spr->x < xmin - maxcorrection) || (spr->y < ymin - maxcorrection) ||
            (spr->x > xmax + maxcorrection) || (spr->y > ymax + maxcorrection))
            return 1;
662

663
        if (clipspritenum < MAXCLIPNUM)
664
            clipspritelist[clipspritenum++] = spr-(uspritetype *)sprite;
665
666
667
668
669
670
671
672
        //initprintf("%d: clip sprite[%d]\n",clipspritenum,j);
        return 1;
    }

    return 0;
}

// return: -1 if curspr has x-flip xor y-flip (in the horizontal map plane!), 1 else
673
int32_t clipsprite_initindex(int32_t curidx, uspriteptr_t const curspr, int32_t *clipsectcnt, const vec3_t *vect)
674
675
676
677
678
679
680
681
682
683
684
685
{
    int32_t k, daz = curspr->z;
    int32_t scalex, scaley, scalez, flipx, flipy;
    int32_t flipmul=1;

    const int32_t j = sectq[clipinfo[curidx].qbeg];
    const int32_t tempint1 = sector[j].CM_XREPEAT;
    const int32_t tempint2 = sector[j].CM_YREPEAT;

    const int32_t rotang = (curspr->ang - sector[j].CM_ANG)&2047;
    const int32_t dorot = !CM_NOROTS(j);

686
    if ((curspr->cstat&CSTAT_SPRITE_ALIGNMENT)!=CSTAT_SPRITE_ALIGNMENT_FLOOR)  // face/wall sprite
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
    {
        scalex = scaley = divscale22(curspr->xrepeat, tempint1);
        scalez = divscale22(curspr->yrepeat, tempint2);

        flipx = 1-((curspr->cstat&4)>>1);
        flipy = 1;
    }
    else
    {
        scalex = divscale22(curspr->xrepeat, tempint1);
        scaley = divscale22(curspr->yrepeat, tempint2);
        scalez = scalex;

        flipx = 1-((curspr->cstat&4)>>1);
        flipy = 1-((curspr->cstat&8)>>2);
    }

    if (dorot)
    {
        flipmul = flipx*flipy;
        if (flipmul==-1)
            wall = (walltype *) loadwallinv;
    }

    if ((curspr->cstat&128) != (sector[j].CM_CSTAT&128))
        daz += (((curspr->cstat&128)>>6)-1)*((tilesiz[curspr->picnum].y*curspr->yrepeat)<<1);

    *clipsectcnt = clipsectnum = 0;
    // init sectors for this index
    for (k=clipinfo[curidx].qbeg; k<=clipinfo[curidx].qend; k++)
    {
718
        int32_t const j   = sectq[k];
719
        auto const    sec = &sector[j];
720

721
        int32_t const startwall = sec->wallptr, endwall = startwall+sec->wallnum;
722
723
724
725
726

        sec->floorz = daz + mulscale22(scalez, CM_FLOORZ(j));
        sec->ceilingz = daz + mulscale22(scalez, CM_CEILINGZ(j));
        //initprintf("sec %d: f=%d, c=%d\n", j, sec->floorz, sec->ceilingz);

727
        for (int w=startwall; w<endwall; w++)
728
        {
Evan Ramos's avatar
Evan Ramos committed
729
            auto wal = (uwalltype *)(wall + w);
730
731
732
733
734
735
736
            wal->x = mulscale22(scalex, CM_WALL_X(w));
            wal->y = mulscale22(scaley, CM_WALL_Y(w));

            if (dorot)
            {
                wal->x *= flipx;
                wal->y *= flipy;
737
                rotatepoint(zerovec, wal->pos, rotang, &wal->pos);
738
739
740
741
742
743
744
            }

            wal->x += curspr->x;
            wal->y += curspr->y;
        }

        if (inside(vect->x, vect->y, j)==1)
745
            addclipsect(j);
746
747
748
749
    }

    // add outer sector if not inside inner ones
    if (clipsectnum==0)
750
        addclipsect(sectq[k-1]);
751
752
753

    return flipmul;
}
754

755
756
#endif

757
static void addclipline(int32_t dax1, int32_t day1, int32_t dax2, int32_t day2, int16_t daoval, int nofix)
758
{
759
    if (clipnum >= MAXCLIPNUM)
760
    {
761
762
        clipmove_warned |= 2;
        return;
763
    }
764
765
766

    clipit[clipnum].x1 = dax1; clipit[clipnum].y1 = day1;
    clipit[clipnum].x2 = dax2; clipit[clipnum].y2 = day2;
Richard Gobeille's avatar
Richard Gobeille committed
767
    clipobjectval[clipnum] = daoval;
768

769
770
    uint32_t const mask = pow2char[clipnum&7];
    uint8_t &value = clipignore[clipnum>>3];
Richard Gobeille's avatar
Richard Gobeille committed
771
    value = (value & ~mask) | (-nofix & mask);
772
773

    clipnum++;
774
775
}

776
static FORCE_INLINE void clipmove_tweak_pos(const vec3_t *pos, int32_t gx, int32_t gy, int32_t x1, int32_t y1, int32_t x2,
777
                                      int32_t y2, int32_t *daxptr, int32_t *dayptr)
778
779
780
{
    int32_t daz;

781
    if (enginecompatibilitymode == ENGINE_19950829 ||
782
        rintersect(pos->x, pos->y, 0, gx, gy, 0, x1, y1, x2, y2, daxptr, dayptr, &daz) == -1)
783
784
785
786
787
788
    {
        *daxptr = pos->x;
        *dayptr = pos->y;
    }
}

789
int32_t getceilzofslope_19950829(int32_t sectnum, int32_t dax, int32_t day)
790
791
{
    if (!(sector[sectnum].ceilingstat&2)) return sector[sectnum].ceilingz;
792
793
794
795
    int32_t const j = sector[sectnum].wallptr;
    int32_t dx = wall[wall[j].point2].x-wall[j].x;
    int32_t dy = wall[wall[j].point2].y-wall[j].y;
    int32_t i = (ksqrtasm_old(dx*dx+dy*dy)); if (i == 0) return(sector[sectnum].ceilingz);
796
797
798
799
800
    i = divscale15(sector[sectnum].ceilingheinum,i);
    dx *= i; dy *= i;
    return(sector[sectnum].ceilingz+dmulscale23(dx,day-wall[j].y,-dy,dax-wall[j].x));
}

801
int32_t getflorzofslope_19950829(int32_t sectnum, int32_t dax, int32_t day)
802
803
{
    if (!(sector[sectnum].floorstat&2)) return sector[sectnum].floorz;
804
805
806
807
    int32_t const j = sector[sectnum].wallptr;
    int32_t dx = wall[wall[j].point2].x-wall[j].x;
    int32_t dy = wall[wall[j].point2].y-wall[j].y;
    int32_t i = (ksqrtasm_old(dx*dx+dy*dy)); if (i == 0) return sector[sectnum].floorz;
808
809
810
811
812
    i = divscale15(sector[sectnum].floorheinum,i);
    dx *= i; dy *= i;
    return(sector[sectnum].floorz+dmulscale23(dx,day-wall[j].y,-dy,dax-wall[j].x));
}

813
// Returns: should clip?
Richard Gobeille's avatar
Richard Gobeille committed
814
static int cliptestsector(int const dasect, int const nextsect, int32_t const flordist, int32_t const ceildist, vec2_t const pos, int32_t const posz)
815
{
Evan Ramos's avatar
Evan Ramos committed
816
    Bassert((unsigned)dasect < (unsigned)numsectors && (unsigned)nextsect < (unsigned)numsectors);
Richard Gobeille's avatar
Richard Gobeille committed
817

Richard Gobeille's avatar
Richard Gobeille committed
818
    auto const sec2 = (usectorptr_t)&sector[nextsect];
Richard Gobeille's avatar
Richard Gobeille committed
819

820
    switch (enginecompatibilitymode)
821
    {
822
    case ENGINE_EDUKE32:
823
    {
824
825
826
827
        int32_t daz2  = sec2->floorz;
        int32_t dacz2 = sec2->ceilingz;

        if ((sec2->floorstat|sec2->ceilingstat) & 2)
828
829
830
#ifdef YAX_ENABLE
            yax_getzsofslope(nextsect, pos.x, pos.y, &dacz2, &daz2);
#else
831
            getcorrectzsofslope(nextsect, pos.x, pos.y, &dacz2, &daz2);
832
#endif
833
834
835
836
837
838
839
840
841
842

        if (daz2 <= dacz2)
            return 1;

        auto const sec = (usectorptr_t)&sector[dasect];

        int32_t daz  = sec->floorz;
        int32_t dacz = sec->ceilingz;

        if ((sec->floorstat|sec->ceilingstat) & 2)
843
844
845
#ifdef YAX_ENABLE
            yax_getzsofslope(dasect, pos.x, pos.y, &dacz, &daz);
#else
846
            getcorrectzsofslope(dasect, pos.x, pos.y, &dacz, &daz);
847
#endif
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865

        int32_t const sec2height = klabs(daz2-dacz2);

        return ((klabs(daz-dacz) > sec2height &&       // clip if the current sector is taller and the next is too small
                sec2height < (ceildist+(CLIPCURBHEIGHT<<1))) ||

                ((sec2->floorstat&1) == 0 &&    // parallaxed floor curbs don't clip
                posz >= daz2-(flordist-1) &&    // also account for desired z distance tolerance
                daz2 < daz-CLIPCURBHEIGHT) ||   // curbs less tall than 256 z units don't clip

                ((sec2->ceilingstat&1) == 0 && 
                posz <= dacz2+(ceildist-1) &&
                dacz2 > dacz+CLIPCURBHEIGHT));  // ceilings check the same conditions ^^^^^
    }
    case ENGINE_19950829:
    {
        int32_t daz = getflorzofslope_19950829(dasect, pos.x, pos.y);
        int32_t daz2 = getflorzofslope_19950829(nextsect, pos.x, pos.y);
866
867
868

        if (daz2 < daz && (sec2->floorstat&1) == 0)
            if (posz >= daz2-(flordist-1)) return 1;
869
870
        daz = getceilzofslope_19950829(dasect, pos.x, pos.y);
        daz2 = getceilzofslope_19950829(nextsect, pos.x, pos.y);
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
        if (daz2 > daz && (sec2->ceilingstat&1) == 0)
            if (posz <= daz2+(ceildist-1)) return 1;

        return 0;
    }
    default:
    {
        int32_t daz = getflorzofslope(dasect, pos.x, pos.y);
        int32_t daz2 = getflorzofslope(nextsect, pos.x, pos.y);

        if (daz2 < daz-(1<<8) && (sec2->floorstat&1) == 0)
            if (posz >= daz2-(flordist-1)) return 1;
        daz = getceilzofslope(dasect, pos.x, pos.y);
        daz2 = getceilzofslope(nextsect, pos.x, pos.y);
        if (daz2 > daz+(1<<8) && (sec2->ceilingstat&1) == 0)
            if (posz <= daz2+(ceildist-1)) return 1;

        return 0;
    }
    }
891
892
893
}

int32_t clipmovex(vec3_t *pos, int16_t *sectnum,
894
                  int32_t xvect, int32_t yvect,
895
896
                  int32_t const walldist, int32_t const ceildist, int32_t const flordist, uint32_t const cliptype,
                  uint8_t const noslidep)
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
{
    const int32_t oboxtracenum = clipmoveboxtracenum;

    if (noslidep)
        clipmoveboxtracenum = 1;
    int32_t ret = clipmove(pos, sectnum, xvect, yvect,
        walldist, ceildist, flordist, cliptype);
    clipmoveboxtracenum = oboxtracenum;

    return ret;
}

//
// raytrace (internal)
//
Richard Gobeille's avatar
Richard Gobeille committed
912
static inline int32_t cliptrace(vec2_t const pos, vec2_t * const goal)
913
914
915
{
    int32_t hitwall = -1;

916
    for (native_t z=clipnum-1; z>=0; z--)
917
    {
918
919
920
        vec2_t const p1   = { clipit[z].x1, clipit[z].y1 };
        vec2_t const p2   = { clipit[z].x2, clipit[z].y2 };
        vec2_t const area = { p2.x-p1.x, p2.y-p1.y };
921

922
        int32_t topu = area.x*(pos.y-p1.y) - (pos.x-p1.x)*area.y;
923

924
        if (topu <= 0 || area.x*(goal->y-p1.y) > (goal->x-p1.x)*area.y)
925
926
            continue;

927
        vec2_t const diff = { goal->x-pos.x, goal->y-pos.y };
928

929
        if (diff.x*(p1.y-pos.y) > (p1.x-pos.x)*diff.y || diff.x*(p2.y-pos.y) <= (p2.x-pos.x)*diff.y)
930
931
            continue;

932
933
        int32_t const bot = diff.x*area.y - area.x*diff.y;
        native_t cnt = 256;
934

935
        if (!bot)
936
937
            continue;

938
        vec2_t n;
939
940
941

        do
        {
942
943
944
945
946
947
948
            if (--cnt < 0)
            {
                *goal = pos;
                return z;
            }

            n = { pos.x+scale(diff.x, topu, bot), pos.y+scale(diff.y, topu, bot) };
949
            topu--;
950
        } while (area.x*(n.y-p1.y) <= (n.x-p1.x)*area.y);
951

952
        if (klabs(pos.x-n.x)+klabs(pos.y-n.y) < klabs(pos.x-goal->x)+klabs(pos.y-goal->y))
953
        {
954
955
            *goal = n;
            hitwall = z;
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
        }
    }

    return hitwall;
}

//
// keepaway (internal)
//
static inline void keepaway(int32_t *x, int32_t *y, int32_t w)
{
    const int32_t x1 = clipit[w].x1, dx = clipit[w].x2-x1;
    const int32_t y1 = clipit[w].y1, dy = clipit[w].y2-y1;
    const int32_t ox = ksgn(-dy), oy = ksgn(dx);
    char first = (klabs(dx) <= klabs(dy));

Richard Gobeille's avatar
Richard Gobeille committed
972
    do
973
974
975
976
977
978
979
980
981
982
983
    {
        if (dx*(*y-y1) > (*x-x1)*dy)
            return;

        if (first == 0)
            *x += ox;
        else
            *y += oy;

        first ^= 1;
    }
Richard Gobeille's avatar
Richard Gobeille committed
984
    while (1);
985
986
}

Richard Gobeille's avatar
Richard Gobeille committed
987
static int get_floorspr_clipyou(vec2_t const v1, vec2_t const v2, vec2_t const v3, vec2_t const v4)
988
{
Richard Gobeille's avatar
Richard Gobeille committed
989
    int clipyou = 0;
990

Richard Gobeille's avatar
Richard Gobeille committed
991
    if ((v1.y^v2.y) < 0)
992
    {
Richard Gobeille's avatar
Richard Gobeille committed
993
994
        if ((v1.x^v2.x) < 0) clipyou ^= (v1.x*v2.y < v2.x*v1.y)^(v1.y<v2.y);
        else if (v1.x >= 0) clipyou ^= 1;
995
    }
Richard Gobeille's avatar
Richard Gobeille committed
996
    if ((v2.y^v3.y) < 0)
997
    {
Richard Gobeille's avatar
Richard Gobeille committed
998
999
        if ((v2.x^v3.x) < 0) clipyou ^= (v2.x*v3.y < v3.x*v2.y)^(v2.y<v3.y);
        else if (v2.x >= 0) clipyou ^= 1;
1000
    }