Solvespace

1
//-----------------------------------------------------------------------------
2
// Binary space partitioning tree, used to represent a volume in 3-space
3
// bounded by a triangle mesh. These are used to compute Boolean operations
4
// on meshes. These aren't used for anything relating to an SShell of
5
// ratpoly surfaces.
6
//
7
// Copyright 2008-2013 Jonathan Westhues.
8
//-----------------------------------------------------------------------------
9
#include "solvespace.h"
10

11
SBsp2 *SBsp2::Alloc() { return (SBsp2 *)AllocTemporary(sizeof(SBsp2)); }
12
SBsp3 *SBsp3::Alloc() { return (SBsp3 *)AllocTemporary(sizeof(SBsp3)); }
13

14
SBsp3 *SBsp3::FromMesh(const SMesh *m) {
15
    SMesh mc = {};
16
    for(auto const &elt : m->l) { mc.AddTriangle(&elt); }
17

18
    srand(0); // Let's be deterministic, at least!
19
    int n = mc.l.n;
20
    while(n > 1) {
21
        int k = rand() % n;
22
        n--;
23
        swap(mc.l[k], mc.l[n]);
24
    }
25

26
    SBsp3 *bsp3 = NULL;
27
    for(auto &elt : mc.l) { bsp3 = InsertOrCreate(bsp3, &elt, NULL); }
28
    mc.Clear();
29
    return bsp3;
30
}
31

32
Vector SBsp3::IntersectionWith(Vector a, Vector b) const {
33
    double da = a.Dot(n) - d;
34
    double db = b.Dot(n) - d;
35
    ssassert(da*db < 0, "Expected segment to intersect BSP node");
36

37
    double dab = (db - da);
38
    return (a.ScaledBy(db/dab)).Plus(b.ScaledBy(-da/dab));
39
}
40

41
void SBsp3::InsertInPlane(bool pos2, STriangle *tr, SMesh *m) {
42
    Vector tc = ((tr->a).Plus(tr->b).Plus(tr->c)).ScaledBy(1.0/3);
43

44
    bool onFace = false;
45
    bool sameNormal = false;
46
    double maxNormalMag = -1;
47

48
    Vector lln, trn = tr->Normal();
49

50
    SBsp3 *ll = this;
51
    while(ll) {
52
        if((ll->tri).ContainsPoint(tc)) {
53
            onFace = true;
54
            // If the mesh contains almost-zero-area triangles, and we're
55
            // just on the edge of one of those, then don't trust its normal.
56
            lln = (ll->tri).Normal();
57
            if(lln.Magnitude() > maxNormalMag) {
58
                sameNormal = trn.Dot(lln) > 0;
59
                maxNormalMag = lln.Magnitude();
60
            }
61
        }
62
        ll = ll->more;
63
    }
64

65
    if((!onFace && ((m->keepInsideOtherShell && !pos2) ||
66
                    (!m->keepInsideOtherShell && pos2))) ||
67
       (onFace && ((m->keepCoplanar && m->flipNormal && !sameNormal) ||
68
                   (m->keepCoplanar && !m->flipNormal && sameNormal)))) {
69
        // We have decided that we need to keep a triangle either inside,
70
        // outside or on the other shell. So add it and flip it if requested.
71
        if(!(m->flipNormal)) {
72
            m->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
73
        } else {
74
            m->AddTriangle(tr->meta, tr->c, tr->b, tr->a);
75
        }
76
    } else {
77
        m->atLeastOneDiscarded = true;
78
    }
79
}
80

81
void SBsp3::InsertHow(BspClass how, STriangle *tr, SMesh *instead) {
82
    switch(how) {
83
        case BspClass::POS:
84
            if(instead && !pos) goto alt;
85
            pos = InsertOrCreate(pos, tr, instead);
86
            break;
87

88
        case BspClass::NEG:
89
            if(instead && !neg) goto alt;
90
            neg = InsertOrCreate(neg, tr, instead);
91
            break;
92

93
        case BspClass::COPLANAR: {
94
            if(instead) goto alt;
95
            SBsp3 *m = Alloc();
96
            m->n = n;
97
            m->d = d;
98
            m->tri = *tr;
99
            m->more = more;
100
            more = m;
101
            break;
102
        }
103
    }
104
    return;
105

106
alt:
107
    if(((BspClass::POS == how) && !instead->keepInsideOtherShell) ||
108
       ((BspClass::NEG == how) && instead->keepInsideOtherShell)) {
109
        // We have decided that we need to keep a triangle (either inside or
110
        // outside the other shell. So add it and flip it if requested.
111
        if(!(instead->flipNormal)) {
112
            instead->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
113
        } else {
114
            instead->AddTriangle(tr->meta, tr->c, tr->b, tr->a);
115
        }
116
    } else if(how == BspClass::COPLANAR) {
117
        if(edges) {
118
            edges->InsertTriangle(tr, instead, this);
119
        } else {
120
            // I suppose this actually is allowed to happen, if the coplanar
121
            // face is the leaf, and all of its neighbors are earlier in tree?
122
            InsertInPlane(/*pos2=*/false, tr, instead);
123
        }
124
    } else {
125
        instead->atLeastOneDiscarded = true;
126
    }
127
}
128

129
class BspUtil {
130
public:
131
    SBsp3      *bsp;
132

133
    size_t      onc;
134
    size_t      posc;
135
    size_t      negc;
136
    bool       *isPos;
137
    bool       *isNeg;
138
    bool       *isOn;
139

140
    // triangle operations
141
    STriangle  *tr;
142
    STriangle  *btri; // also as alone
143
    STriangle  *ctri;
144

145
    // convex operations
146
    Vector     *on;
147
    size_t      npos;
148
    size_t      nneg;
149
    Vector     *vpos; // also as quad
150
    Vector     *vneg;
151

152
    static BspUtil *Alloc() {
153
        return (BspUtil *)AllocTemporary(sizeof(BspUtil));
154
    }
155

156
    void AllocOn() {
157
        on = (Vector *)AllocTemporary(sizeof(Vector) * 2);
158
    }
159

160
    void AllocTriangle() {
161
        btri = (STriangle *)AllocTemporary(sizeof(STriangle));
162
    }
163

164
    void AllocTriangles() {
165
        btri = (STriangle *)AllocTemporary(sizeof(STriangle) * 2);
166
        ctri = &btri[1];
167
    }
168

169
    void AllocQuad() {
170
        vpos = (Vector *)AllocTemporary(sizeof(Vector) * 4);
171
    }
172

173
    void AllocClassify(size_t size) {
174
        // Allocate a one big piece is faster than a small ones.
175
        isPos = (bool *)AllocTemporary(sizeof(bool) * size * 3);
176
        isNeg = &isPos[size];
177
        isOn  = &isNeg[size];
178
    }
179

180
    void AllocVertices(size_t size) {
181
        vpos = (Vector *)AllocTemporary(sizeof(Vector) * size * 2);
182
        vneg = &vpos[size];
183
    }
184

185
    void ClassifyTriangle(STriangle *tri, SBsp3 *node) {
186
        tr   = tri;
187
        bsp  = node;
188
        onc  = 0;
189
        posc = 0;
190
        negc = 0;
191

192
        AllocClassify(3);
193

194
        double dt[3] = { (tr->a).Dot(bsp->n), (tr->b).Dot(bsp->n), (tr->c).Dot(bsp->n) };
195
        double d = bsp->d;
196
        // Count vertices in the plane
197
        for(int i = 0; i < 3; i++) {
198
            if(dt[i] > d + LENGTH_EPS) {
199
                posc++;
200
                isPos[i] = true;
201
            } else if(dt[i] < d - LENGTH_EPS) {
202
                negc++;
203
                isNeg[i] = true;
204
            } else {
205
                onc++;
206
                isOn[i] = true;
207
            }
208
        }
209
    }
210

211
    bool ClassifyConvex(Vector *vertex, size_t cnt, SBsp3 *node, bool insertEdge) {
212
        bsp  = node;
213
        onc  = 0;
214
        posc = 0;
215
        negc = 0;
216

217
        AllocClassify(cnt);
218
        AllocOn();
219

220
        for(size_t i = 0; i < cnt; i++) {
221
            double dt = bsp->n.Dot(vertex[i]);
222
            isPos[i] = isNeg[i] = isOn[i] = false;
223
            if(fabs(dt - bsp->d) < LENGTH_EPS) {
224
                isOn[i] = true;
225
                if(onc < 2) {
226
                    on[onc] = vertex[i];
227
                }
228
                onc++;
229
            } else if(dt > bsp->d) {
230
                isPos[i] = true;
231
                posc++;
232
            } else {
233
                isNeg[i] = true;
234
                negc++;
235
            }
236
        }
237

238
        if(onc != 2 && onc != 1 && onc != 0) return false;
239
        if(onc == 2) {
240
            if(insertEdge) {
241
                Vector e01 = (vertex[1]).Minus(vertex[0]);
242
                Vector e12 = (vertex[2]).Minus(vertex[1]);
243
                Vector out = e01.Cross(e12);
244
                SEdge se = SEdge::From(on[0], on[1]);
245
                bsp->edges = SBsp2::InsertOrCreateEdge(bsp->edges, &se, bsp->n, out);
246
            }
247
        }
248
        return true;
249
    }
250

251
    bool ClassifyConvexVertices(Vector *vertex, size_t cnt, bool insertEdges) {
252
        Vector inter[2];
253
        int inters = 0;
254

255
        npos = 0;
256
        nneg = 0;
257

258
        // Enlarge vertices list to consider two intersections
259
        AllocVertices(cnt + 4);
260

261
        for(size_t i = 0; i < cnt; i++) {
262
            size_t ip = WRAP((i + 1), cnt);
263

264
            if(isPos[i]) {
265
                vpos[npos++] = vertex[i];
266
            }
267
            if(isNeg[i]) {
268
                vneg[nneg++] = vertex[i];
269
            }
270
            if(isOn[i]) {
271
                vneg[nneg++] = vertex[i];
272
                vpos[npos++] = vertex[i];
273
            }
274
            if((isPos[i] && isNeg[ip]) || (isNeg[i] && isPos[ip])) {
275
                Vector vi = bsp->IntersectionWith(vertex[i], vertex[ip]);
276
                vpos[npos++] = vi;
277
                vneg[nneg++] = vi;
278

279
                if(inters >= 2) return false; // triangulate: XXX shouldn't happen but does
280
                inter[inters++] = vi;
281
            }
282
        }
283
        ssassert(npos <= cnt + 1 && nneg <= cnt + 1, "Impossible");
284

285
        if(insertEdges) {
286
            Vector e01 = (vertex[1]).Minus(vertex[0]);
287
            Vector e12 = (vertex[2]).Minus(vertex[1]);
288
            Vector out = e01.Cross(e12);
289
            if(inters == 2) {
290
                SEdge se = SEdge::From(inter[0], inter[1]);
291
                bsp->edges = SBsp2::InsertOrCreateEdge(bsp->edges, &se, bsp->n, out);
292
            } else if(inters == 1 && onc == 1) {
293
                SEdge se = SEdge::From(inter[0], on[0]);
294
                bsp->edges = SBsp2::InsertOrCreateEdge(bsp->edges, &se, bsp->n, out);
295
            } else if(inters == 0 && onc == 2) {
296
                // We already handled this on-plane existing edge
297
            } else {
298
                return false; //triangulate;
299
            }
300
        }
301
        if(nneg < 3 || npos < 3) return false; // triangulate; // XXX
302

303
        return true;
304
    }
305

306
    void ProcessEdgeInsert() {
307
        ssassert(onc == 2, "Impossible");
308

309
        Vector a, b;
310
        if     (!isOn[0]) { a = tr->b; b = tr->c; }
311
        else if(!isOn[1]) { a = tr->c; b = tr->a; }
312
        else if(!isOn[2]) { a = tr->a; b = tr->b; }
313
        else ssassert(false, "Impossible");
314

315
        SEdge se = SEdge::From(a, b);
316
        bsp->edges = SBsp2::InsertOrCreateEdge(bsp->edges, &se, bsp->n, tr->Normal());
317
    }
318

319
    bool SplitIntoTwoTriangles(bool insertEdge) {
320
        ssassert(posc == 1 && negc == 1 && onc == 1, "Impossible");
321

322
        bool bpos;
323
        Vector a, b, c;
324

325
        // Standardize so that a is on the plane
326
        if       (isOn[0]) { a = tr->a; b = tr->b; c = tr->c; bpos = isPos[1];
327
        } else if(isOn[1]) { a = tr->b; b = tr->c; c = tr->a; bpos = isPos[2];
328
        } else if(isOn[2]) { a = tr->c; b = tr->a; c = tr->b; bpos = isPos[0];
329
        } else ssassert(false, "Impossible");
330

331
        AllocTriangles();
332
        Vector bPc = bsp->IntersectionWith(b, c);
333
        *btri = STriangle::From(tr->meta, a, b, bPc);
334
        *ctri = STriangle::From(tr->meta, c, a, bPc);
335

336
        if(insertEdge) {
337
            SEdge se = SEdge::From(a, bPc);
338
            bsp->edges = SBsp2::InsertOrCreateEdge(bsp->edges, &se, bsp->n, tr->Normal());
339
        }
340

341
        return bpos;
342
    }
343

344
    bool SplitIntoTwoPieces(bool insertEdge) {
345
        Vector a, b, c;
346
        if(posc == 2 && negc == 1) {
347
            // Standardize so that a is on one side, and b and c are on the other.
348
            if       (isNeg[0]) {   a = tr->a; b = tr->b; c = tr->c;
349
            } else if(isNeg[1]) {   a = tr->b; b = tr->c; c = tr->a;
350
            } else if(isNeg[2]) {   a = tr->c; b = tr->a; c = tr->b;
351
            } else ssassert(false, "Impossible");
352
        } else if(posc == 1 && negc == 2) {
353
            if       (isPos[0]) {   a = tr->a; b = tr->b; c = tr->c;
354
            } else if(isPos[1]) {   a = tr->b; b = tr->c; c = tr->a;
355
            } else if(isPos[2]) {   a = tr->c; b = tr->a; c = tr->b;
356
            } else ssassert(false, "Impossible");
357
        } else ssassert(false, "Impossible");
358

359
        Vector aPb = bsp->IntersectionWith(a, b);
360
        Vector cPa = bsp->IntersectionWith(c, a);
361
        AllocTriangle();
362
        AllocQuad();
363

364
        *btri = STriangle::From(tr->meta, a, aPb, cPa);
365

366
        vpos[0] = aPb;
367
        vpos[1] = b;
368
        vpos[2] = c;
369
        vpos[3] = cPa;
370

371
        if(insertEdge) {
372
            SEdge se = SEdge::From(aPb, cPa);
373
            bsp->edges = SBsp2::InsertOrCreateEdge(bsp->edges, &se, bsp->n, btri->Normal());
374
        }
375

376
        return posc == 2 && negc == 1;
377
    }
378

379
    static SBsp3 *Triangulate(SBsp3 *bsp, const STriMeta &meta, Vector *vertex,
380
                              size_t cnt, SMesh *instead) {
381
        for(size_t i = 0; i < cnt - 2; i++) {
382
            STriangle tr = STriangle::From(meta, vertex[0], vertex[i + 1], vertex[i + 2]);
383
            bsp = SBsp3::InsertOrCreate(bsp, &tr, instead);
384
        }
385
        return bsp;
386
    }
387
};
388

389
void SBsp3::InsertConvexHow(BspClass how, STriMeta meta, Vector *vertex, size_t n,
390
                            SMesh *instead) {
391
    switch(how) {
392
        case BspClass::POS:
393
            if(pos) {
394
                pos = pos->InsertConvex(meta, vertex, n, instead);
395
                return;
396
            }
397
            break;
398

399
        case BspClass::NEG:
400
            if(neg) {
401
                neg = neg->InsertConvex(meta, vertex, n, instead);
402
                return;
403
            }
404
            break;
405

406
        default: ssassert(false, "Unexpected BSP insert type");
407
    }
408

409
    for(size_t i = 0; i < n - 2; i++) {
410
        STriangle tr = STriangle::From(meta,
411
                                       vertex[0], vertex[i+1], vertex[i+2]);
412
        InsertHow(how, &tr, instead);
413
    }
414
}
415

416
SBsp3 *SBsp3::InsertConvex(STriMeta meta, Vector *vertex, size_t cnt, SMesh *instead) {
417
    BspUtil *u = BspUtil::Alloc();
418
    if(u->ClassifyConvex(vertex, cnt, this, !instead)) {
419
        if(u->posc == 0) {
420
            InsertConvexHow(BspClass::NEG, meta, vertex, cnt, instead);
421
            return this;
422
        }
423
        if(u->negc == 0) {
424
            InsertConvexHow(BspClass::POS, meta, vertex, cnt, instead);
425
            return this;
426
        }
427

428
        if(u->ClassifyConvexVertices(vertex, cnt, !instead)) {
429
            InsertConvexHow(BspClass::NEG, meta, u->vneg, u->nneg, instead);
430
            InsertConvexHow(BspClass::POS, meta, u->vpos, u->npos, instead);
431
            return this;
432
        }
433
    }
434

435
    // We don't handle the special case for this; do it as triangles
436
    return BspUtil::Triangulate(this, meta, vertex, cnt, instead);
437
}
438

439
SBsp3 *SBsp3::InsertOrCreate(SBsp3 *where, STriangle *tr, SMesh *instead) {
440
    if(where == NULL) {
441
        if(instead) {
442
            // ruevs: I do not think this code is reachable, but in
443
            // principle should we use instead->keepInsideOtherShell
444
            // in place of instead->flipNormal ?
445
            if(instead->flipNormal) {
446
                instead->atLeastOneDiscarded = true;
447
            } else {
448
                instead->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
449
            }
450
            return NULL;
451
        }
452

453
        // Brand new node; so allocate for it, and fill us in.
454
        SBsp3 *r = Alloc();
455
        r->n = (tr->Normal()).WithMagnitude(1);
456
        r->d = (tr->a).Dot(r->n);
457
        r->tri = *tr;
458
        return r;
459
    }
460
    where->Insert(tr, instead);
461
    return where;
462
}
463

464
void SBsp3::Insert(STriangle *tr, SMesh *instead) {
465
    BspUtil *u = BspUtil::Alloc();
466
    u->ClassifyTriangle(tr, this);
467

468
    // All vertices in-plane
469
    if(u->onc == 3) {
470
        InsertHow(BspClass::COPLANAR, tr, instead);
471
        return;
472
    }
473

474
    // No split required
475
    if(u->posc == 0 || u->negc == 0) {
476
        if(!instead && u->onc == 2) {
477
            u->ProcessEdgeInsert();
478
        }
479

480
        if(u->posc > 0) {
481
            InsertHow(BspClass::POS, tr, instead);
482
        } else {
483
            InsertHow(BspClass::NEG, tr, instead);
484
        }
485
        return;
486
    }
487

488
    // The polygon must be split into two triangles, one above, one below.
489
    if(u->posc == 1 && u->negc == 1 && u->onc == 1) {
490
        if(u->SplitIntoTwoTriangles(!instead)) {
491
            InsertHow(BspClass::POS, u->btri, instead);
492
            InsertHow(BspClass::NEG, u->ctri, instead);
493
        } else {
494
            InsertHow(BspClass::POS, u->ctri, instead);
495
            InsertHow(BspClass::NEG, u->btri, instead);
496
        }
497
        return;
498
    }
499

500
    // The polygon must be split into two pieces: a triangle and a quad.
501
    if(u->SplitIntoTwoPieces(!instead)) {
502
        InsertConvexHow(BspClass::POS, tr->meta, u->vpos, 4, instead);
503
        InsertHow(BspClass::NEG, u->btri, instead);
504
    } else {
505
        InsertConvexHow(BspClass::NEG, tr->meta, u->vpos, 4, instead);
506
        InsertHow(BspClass::POS, u->btri, instead);
507
    }
508
}
509

510
void SBsp3::GenerateInPaintOrder(SMesh *m) const {
511
    // Doesn't matter which branch we take if the normal has zero z
512
    // component, so don't need a separate case for that.
513
    if(n.z < 0) {
514
        if(pos) pos->GenerateInPaintOrder(m);
515
    } else {
516
        if(neg) neg->GenerateInPaintOrder(m);
517
    }
518

519
    const SBsp3 *flip = this;
520
    while(flip) {
521
        m->AddTriangle(&(flip->tri));
522
        flip = flip->more;
523
    }
524

525
    if(n.z < 0) {
526
        if(neg) neg->GenerateInPaintOrder(m);
527
    } else {
528
        if(pos) pos->GenerateInPaintOrder(m);
529
    }
530
}
531

532
/////////////////////////////////
533

534
Vector SBsp2::IntersectionWith(Vector a, Vector b) const {
535
    double da = a.Dot(no) - d;
536
    double db = b.Dot(no) - d;
537
    ssassert(da*db < 0, "Expected segment to intersect BSP node");
538

539
    double dab = (db - da);
540
    return (a.ScaledBy(db/dab)).Plus(b.ScaledBy(-da/dab));
541
}
542

543
SBsp2 *SBsp2::InsertOrCreateEdge(SBsp2 *where, SEdge *nedge, Vector nnp, Vector out) {
544
    if(where == NULL) {
545
        // Brand new node; so allocate for it, and fill us in.
546
        SBsp2 *r = Alloc();
547
        r->np = nnp;
548
        r->no = ((r->np).Cross((nedge->b).Minus(nedge->a))).WithMagnitude(1);
549
        if(out.Dot(r->no) < 0) {
550
            r->no = (r->no).ScaledBy(-1);
551
        }
552
        r->d = (nedge->a).Dot(r->no);
553
        r->edge = *nedge;
554
        return r;
555
    }
556
    where->InsertEdge(nedge, nnp, out);
557
    return where;
558
}
559

560
void SBsp2::InsertEdge(SEdge *nedge, Vector nnp, Vector out) {
561

562
    double dt[2] = { (nedge->a).Dot(no), (nedge->b).Dot(no) };
563

564
    bool isPos[2] = {}, isNeg[2] = {}, isOn[2] = {};
565
    for(int i = 0; i < 2; i++) {
566
        if(fabs(dt[i] - d) < LENGTH_EPS) {
567
            isOn[i] = true;
568
        } else if(dt[i] > d) {
569
            isPos[i] = true;
570
        } else {
571
            isNeg[i] = true;
572
        }
573
    }
574

575
    if((isPos[0] && isPos[1])||(isPos[0] && isOn[1])||(isOn[0] && isPos[1])) {
576
        pos = InsertOrCreateEdge(pos, nedge, nnp, out);
577
        return;
578
    }
579
    if((isNeg[0] && isNeg[1])||(isNeg[0] && isOn[1])||(isOn[0] && isNeg[1])) {
580
        neg = InsertOrCreateEdge(neg, nedge, nnp, out);
581
        return;
582
    }
583
    if(isOn[0] && isOn[1]) {
584
        SBsp2 *m = Alloc();
585

586
        m->np = nnp;
587
        m->no = ((m->np).Cross((nedge->b).Minus(nedge->a))).WithMagnitude(1);
588
        if(out.Dot(m->no) < 0) {
589
            m->no = (m->no).ScaledBy(-1);
590
        }
591
        m->d = (nedge->a).Dot(m->no);
592
        m->edge = *nedge;
593

594
        m->more = more;
595
        more = m;
596
        return;
597
    }
598
    if((isPos[0] && isNeg[1]) || (isNeg[0] && isPos[1])) {
599
        Vector aPb = IntersectionWith(nedge->a, nedge->b);
600

601
        SEdge ea = SEdge::From(nedge->a, aPb);
602
        SEdge eb = SEdge::From(aPb, nedge->b);
603

604
        if(isPos[0]) {
605
            pos = InsertOrCreateEdge(pos, &ea, nnp, out);
606
            neg = InsertOrCreateEdge(neg, &eb, nnp, out);
607
        } else {
608
            neg = InsertOrCreateEdge(neg, &ea, nnp, out);
609
            pos = InsertOrCreateEdge(pos, &eb, nnp, out);
610
        }
611
        return;
612
    }
613
    ssassert(false, "Impossible");
614
}
615

616
void SBsp2::InsertTriangleHow(BspClass how, STriangle *tr, SMesh *m, SBsp3 *bsp3) {
617
    switch(how) {
618
        case BspClass::POS:
619
            if(pos) {
620
                pos->InsertTriangle(tr, m, bsp3);
621
            } else {
622
                bsp3->InsertInPlane(/*pos2=*/true, tr, m);
623
            }
624
            break;
625

626
        case BspClass::NEG:
627
            if(neg) {
628
                neg->InsertTriangle(tr, m, bsp3);
629
            } else {
630
                bsp3->InsertInPlane(/*pos2=*/false, tr, m);
631
            }
632
            break;
633

634
        default: ssassert(false, "Unexpected BSP insert type");
635
    }
636
}
637

638
void SBsp2::InsertTriangle(STriangle *tr, SMesh *m, SBsp3 *bsp3) {
639
    double dt[3] = { (tr->a).Dot(no), (tr->b).Dot(no), (tr->c).Dot(no) };
640

641
    bool isPos[3] = {}, isNeg[3] = {}, isOn[3] = {};
642
    int inc = 0, posc = 0, negc = 0;
643
    for(int i = 0; i < 3; i++) {
644
        if(fabs(dt[i] - d) < LENGTH_EPS) {
645
            isOn[i] = true;
646
            inc++;
647
        } else if(dt[i] > d) {
648
            isPos[i] = true;
649
            posc++;
650
        } else {
651
            isNeg[i] = true;
652
            negc++;
653
        }
654
    }
655

656
    if(inc == 3) {
657
        // All vertices on-line; so it's a degenerate triangle, to ignore.
658
        return;
659
    }
660

661
    // No split required
662
    if(posc == 0 || negc == 0) {
663
        if(posc > 0) {
664
            InsertTriangleHow(BspClass::POS, tr, m, bsp3);
665
        } else {
666
            InsertTriangleHow(BspClass::NEG, tr, m, bsp3);
667
        }
668
        return;
669
    }
670

671
    // The polygon must be split into two pieces, one above, one below.
672
    Vector a, b, c;
673

674
    if(posc == 1 && negc == 1 && inc == 1) {
675
        bool bpos;
676
        // Standardize so that a is on the plane
677
        if       (isOn[0]) { a = tr->a; b = tr->b; c = tr->c; bpos = isPos[1];
678
        } else if(isOn[1]) { a = tr->b; b = tr->c; c = tr->a; bpos = isPos[2];
679
        } else if(isOn[2]) { a = tr->c; b = tr->a; c = tr->b; bpos = isPos[0];
680
        } else ssassert(false, "Impossible");
681

682
        Vector bPc = IntersectionWith(b, c);
683
        STriangle btri = STriangle::From(tr->meta, a, b, bPc);
684
        STriangle ctri = STriangle::From(tr->meta, c, a, bPc);
685

686
        if(bpos) {
687
            InsertTriangleHow(BspClass::POS, &btri, m, bsp3);
688
            InsertTriangleHow(BspClass::NEG, &ctri, m, bsp3);
689
        } else {
690
            InsertTriangleHow(BspClass::POS, &ctri, m, bsp3);
691
            InsertTriangleHow(BspClass::NEG, &btri, m, bsp3);
692
        }
693

694
        return;
695
    }
696

697
    if(posc == 2 && negc == 1) {
698
        // Standardize so that a is on one side, and b and c are on the other.
699
        if       (isNeg[0]) {   a = tr->a; b = tr->b; c = tr->c;
700
        } else if(isNeg[1]) {   a = tr->b; b = tr->c; c = tr->a;
701
        } else if(isNeg[2]) {   a = tr->c; b = tr->a; c = tr->b;
702
        } else ssassert(false, "Impossible");
703

704
    } else if(posc == 1 && negc == 2) {
705
        if       (isPos[0]) {   a = tr->a; b = tr->b; c = tr->c;
706
        } else if(isPos[1]) {   a = tr->b; b = tr->c; c = tr->a;
707
        } else if(isPos[2]) {   a = tr->c; b = tr->a; c = tr->b;
708
        } else ssassert(false, "Impossible");
709
    } else ssassert(false, "Impossible");
710

711
    Vector aPb = IntersectionWith(a, b);
712
    Vector cPa = IntersectionWith(c, a);
713

714
    STriangle alone = STriangle::From(tr->meta, a,   aPb, cPa);
715
    STriangle quad1 = STriangle::From(tr->meta, aPb, b,   c  );
716
    STriangle quad2 = STriangle::From(tr->meta, aPb, c,   cPa);
717

718
    if(posc == 2 && negc == 1) {
719
        InsertTriangleHow(BspClass::POS, &quad1, m, bsp3);
720
        InsertTriangleHow(BspClass::POS, &quad2, m, bsp3);
721
        InsertTriangleHow(BspClass::NEG, &alone, m, bsp3);
722
    } else {
723
        InsertTriangleHow(BspClass::NEG, &quad1, m, bsp3);
724
        InsertTriangleHow(BspClass::NEG, &quad2, m, bsp3);
725
        InsertTriangleHow(BspClass::POS, &alone, m, bsp3);
726
    }
727

728
    return;
729
}
730