Repository navigation
Expand file tree
/
Copy pathbounding_volumes.html
More file actions
1334 lines (1215 loc) · 61.6 KB
/
Copy pathbounding_volumes.html
File metadata and controls
1334 lines (1215 loc) · 61.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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
170
171
172
173
174
175
176
177
178
179
180
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
256
257
258
259
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
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
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
385
386
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
455
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
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
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
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!doctype html>
<html class="no-js" lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" href="https://interactivecomputergraphics.github.io/physics-simulation/examples/style.css">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true
},
"HTML-CSS": { fonts: ["TeX"] }
});
</script>
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.4/MathJax.js"></script>
<title>Bounding Volumes</title>
<style>
#compareTable { width: 100%; border-collapse: collapse; font-size: 0.85rem; margin-top: 8px; }
#compareTable th, #compareTable td { padding: 5px 8px; border-bottom: 1px solid #e5e7eb; text-align: right; }
#compareTable th:first-child, #compareTable td:first-child { text-align: left; }
#compareTable th { color: #4b5563; font-weight: 600; background: #f5f7ff; }
#compareTable tbody tr { cursor: pointer; }
#compareTable tbody tr:hover { background: #f3f4f6; }
#compareTable tbody tr.selected { background: #e8eefc; font-weight: 600; }
.swatch { display: inline-block; width: 12px; height: 12px; border-radius: 3px; vertical-align: middle; margin-right: 6px; }
.theory table.costs { border-collapse: collapse; margin: 10px 0; font-size: 0.92rem; }
.theory table.costs th, .theory table.costs td { border: 1px solid #d1d5db; padding: 5px 10px; text-align: left; vertical-align: top; }
.theory table.costs th { background: #f5f7ff; }
</style>
</head>
<body>
<header class="page-header">
<h1>Bounding Volumes</h1>
</header>
<main>
<!-- Simulation panel: canvas + controls -->
<table style="align_center;border-radius: 20px;padding: 20px;margin:auto">
<col width="70%">
<col width="30%">
<tr>
<td>
<div class="card sim-panel">
<div class="sim-canvas-wrap">
<canvas id="simCanvas" width="1024" height="640" style="border:2px solid #000000;border-radius: 20px;background-color:#FFFFFF">Your browser does not support the HTML5 canvas tag.</canvas>
</div>
<p class="canvas-hint">Drag an object to move it. Shift + drag (or right-drag, or the mouse wheel over an object) rotates it.</p>
<div class="sim-canvas-wrap" style="margin-top:6px">
<canvas id="testCanvas" width="1024" height="300" style="border:2px solid #000000;border-radius: 20px;background-color:#FFFFFF"></canvas>
</div>
<p class="canvas-hint">
<b>Overlap test</b> — every row is one test that the selected bounding volume type needs, evaluated top to bottom.
Each row compares the intervals of <span style="color:#4673e5"><b>A</b></span> and <span style="color:#10b981"><b>B</b></span> on one axis.
The first axis on which the intervals are disjoint is a <em>separating axis</em>: the test stops there (early exit) and the remaining rows are skipped.
Hover a row to see that axis, the projected intervals and their slabs in the scene.
</p>
<table id="compareTable">
<thead>
<tr>
<th>Bounding volume</th>
<th>Area BV / object A</th>
<th>Area BV / object B</th>
<th>BVs overlap?</th>
<th>Tests evaluated</th>
<th>Max. tests 2D</th>
<th>Max. tests 3D</th>
</tr>
</thead>
<tbody></tbody>
</table>
<p class="canvas-hint">All four types are evaluated live for the current configuration. Click a row to select that type. An area ratio of 1.00 would be a perfect fit.</p>
</div>
</td>
<td>
<div class="controls-panel">
<h3>Controls</h3>
<div class="controls-grid">
<label>BV test</label>
<span class="stat-value"><span id="bvStatus">-</span></span>
<label>Exact test (objects)</label>
<span class="stat-value"><span id="exactStatus">-</span></span>
<label>Result</label>
<span class="stat-value"><span id="classification">-</span></span>
<label>Tests evaluated</label>
<span class="stat-value"><span id="testsEvaluated">-</span></span>
<label>Storage per BV (2D / 3D)</label>
<span class="stat-value"><span id="storage">-</span></span>
<label>Update when rotating</label>
<span class="stat-value" style="font-size:0.8rem"><span id="updateCost">-</span></span>
<label for="typeInput">Bounding volume</label>
<select onchange="gui.setType(this.value)" id="typeInput">
<option value="sphere">Bounding sphere</option>
<option value="aabb" selected="selected">AABB</option>
<option value="obb">OBB</option>
<option value="kdop">k-DOP</option>
</select>
<label for="kInput">k (k-DOP)</label>
<select onchange="gui.k = parseInt(this.value)" id="kInput">
<option value="4">4 (= AABB)</option>
<option value="6">6</option>
<option value="8" selected="selected">8</option>
<option value="12">12</option>
<option value="16">16</option>
</select>
<label for="obbFitInput">OBB fitting</label>
<select onchange="gui.obbFit = this.value" id="obbFitInput">
<option value="min" selected="selected">Minimal area</option>
<option value="pca">PCA (covariance)</option>
</select>
<label for="shapeInput">Objects</label>
<select onchange="gui.restart()" id="shapeInput">
<option value="mixed" selected="selected">Stick + random</option>
<option value="random">Random convex</option>
<option value="elongated">Elongated</option>
<option value="triangle">Triangles</option>
<option value="round">Round</option>
</select>
<label for="rotateInput">Auto-rotate</label>
<input onchange="gui.autoRotate = this.checked" id="rotateInput" type="checkbox">
<label for="overlayInput">Overlay all BV types</label>
<input onchange="gui.overlay = this.checked" id="overlayInput" type="checkbox">
<div class="full-width">
<button onclick="gui.restart()" id="restart">▶ New objects</button>
</div>
</div>
</div>
</td>
</tr>
</table>
<!-- Theory section -->
<div class="card theory">
<h2>Bounding volumes</h2>
<p>
Testing two complex objects for intersection exactly is expensive. A <b>bounding volume (BV)</b> is a simple shape that completely encloses an object. If the bounding volumes of two objects do not overlap, the objects cannot overlap either, and the expensive exact test can be skipped. Collision detection therefore becomes a two-stage process:
</p>
<ol>
<li><b>BV test:</b> do the bounding volumes overlap? This test is cheap and <em>conservative</em>. It never misses a real collision (no false negatives), but it may report an overlap although the objects are apart (a <em>false positive</em>).</li>
<li><b>Exact test:</b> only if the BVs overlap, test the actual geometry (here: two convex polygons with the separating axis theorem; in 3D, typically triangle–triangle tests, often organized in a bounding volume hierarchy).</li>
</ol>
<p>
A good bounding volume should (i) fit the object <b>tightly</b>, so that false positives are rare, (ii) have a <b>cheap overlap test</b>, (iii) be <b>cheap to update</b> when the object moves or rotates, and (iv) need <b>little memory</b>. These goals contradict each other; the four types below are different trade-offs between them. The example works in 2D, so spheres become circles. The 3D numbers are given alongside.
</p>
<h3>Bounding sphere</h3>
<p>
A sphere is stored as center $\mathbf c$ and radius $r$. Two spheres overlap if and only if
$$\|\mathbf c_A - \mathbf c_B\|^2 \le (r_A + r_B)^2,$$
which is a <b>single test</b> and needs no square root. A sphere is rotation invariant: when the object rotates, only the center has to be transformed. It fits elongated or flat objects badly, though (try the "Elongated" objects and compare the area ratios). The example computes the minimal enclosing circle with Welzl's randomized algorithm [Wel91]. Ritter's fast approximation [Rit90] is a common alternative in practice.
</p>
<h3>Axis-aligned bounding box (AABB)</h3>
<p>
An AABB is stored as minimum and maximum coordinate per world axis. Two AABBs overlap if and only if their intervals overlap on <em>every</em> coordinate axis:
$$\min{}_A^i \le \max{}_B^i \;\wedge\; \min{}_B^i \le \max{}_A^i \qquad \text{for } i = x, y\,(,z).$$
That is <b>2 interval tests in 2D, 3 in 3D</b>, and the test can stop as soon as one axis separates the boxes. The test is very cheap, but the box must stay aligned with the world axes. When the object rotates, the AABB has to be recomputed (here from all vertices) and its size changes with the orientation. Switch on "Auto-rotate" to watch the area ratio of the AABB change while those of the sphere and the OBB stay constant.
</p>
<h3>Oriented bounding box (OBB)</h3>
<p>
An OBB is stored as center $\mathbf c$, an orthonormal frame $\mathbf u_1, \mathbf u_2\,(,\mathbf u_3)$ and half extents $h_i$. It rotates with the object, so its fit does not depend on the orientation. Its overlap test uses the <b>separating axis theorem (SAT)</b>: two convex objects are disjoint if and only if there is an axis $\mathbf L$ on which their projections are disjoint. Let box $A$ have center $\mathbf c_A$, axes $\mathbf u^A_i$ and half extents $h^A_i$, and box $B$ correspondingly $\mathbf c_B$, $\mathbf u^B_i$, $h^B_i$. The projection of box $A$ onto $\mathbf L$ is the interval $[\mathbf c_A \cdot \mathbf L - r_A,\ \mathbf c_A \cdot \mathbf L + r_A]$ with the <em>projected radius</em>
$$r_A = \sum_i h^A_i \,|\mathbf u^A_i \cdot \mathbf L|,$$
i.e. half the length of the box's shadow on $\mathbf L$ (each half extent contributes according to how much its axis points along $\mathbf L$). The radius $r_B = \sum_i h^B_i \,|\mathbf u^B_i \cdot \mathbf L|$ of box $B$ is defined in the same way. The two intervals are disjoint, i.e. the boxes are separated on $\mathbf L$, if the distance of the projected centers exceeds the sum of the projected radii:
$$|(\mathbf c_B - \mathbf c_A)\cdot \mathbf L| > r_A + r_B.$$
For unit-length $\mathbf L$ these are true distances; for an arbitrary $\mathbf L$ both sides scale by $\|\mathbf L\|$, so the test result is the same and no normalization is needed. For boxes it suffices to test the following candidate axes:
</p>
<ul>
<li><b>2D:</b> the 2 axes of $A$ and the 2 axes of $B$ — <b>4 tests</b>.</li>
<li><b>3D:</b> the 3 face normals of $A$, the 3 face normals of $B$ and the 9 cross products $\mathbf u^A_i \times \mathbf u^B_j$ of their edge directions — <b>15 tests</b> [GLM96].</li>
</ul>
<p>
So the OBB fits much tighter than the AABB, but its test is more expensive. Fitting is harder too: the example offers the minimal-area rectangle (in 2D, one side is always collinear with a convex hull edge) and the common PCA fit. The PCA fit aligns the box with the eigenvectors of the covariance matrix of the vertices. It is fast but not optimal and depends on how the vertices are distributed; compare both fits with the "Random convex" objects.
</p>
<h3>Discrete oriented polytope (k-DOP)</h3>
<p>
A k-DOP generalizes the AABB to $k/2$ <b>fixed</b> directions $\mathbf n_1, \dots, \mathbf n_{k/2}$ that are the same for all objects. It stores the interval $[\min_{\mathbf p} \mathbf p\cdot\mathbf n_i,\ \max_{\mathbf p} \mathbf p\cdot\mathbf n_i]$ of the object for each direction, i.e. $k$ numbers. The BV itself is the intersection of the $k$ resulting half-spaces (slabs). Because the directions are shared, the overlap test is just a comparison of $k/2$ interval pairs, with no projection at query time:
$$\text{overlap} \iff \min{}_A^i \le \max{}_B^i \;\wedge\; \min{}_B^i \le \max{}_A^i \qquad \text{for } i = 1,\dots,k/2.$$
An AABB is the 4-DOP in 2D (6-DOP in 3D). Typical 3D choices are 6-, 14- (adds the 4 cube diagonals), 18- (adds the 6 edge diagonals) and 26-DOPs [KHM98]. A larger $k$ fits tighter but costs more memory and more interval tests. Like the AABB, a k-DOP must be recomputed when the object rotates.
</p>
<p>
In 2D, comparing the $k/2$ intervals is an exact test for the two k-DOPs, since their edge normals are exactly the fixed directions. In 3D, the cross products of edge directions would also be needed, so the $k/2$ interval comparisons are only <em>conservative</em>. They can report overlap for two disjoint k-DOPs, which is acceptable for a BV test.
</p>
<h3>Comparison (3D)</h3>
<table class="costs">
<tr><th>BV</th><th>Storage</th><th>Overlap test</th><th>Fit</th><th>Update under rotation</th></tr>
<tr><td>Sphere</td><td>4 floats</td><td>1 distance test</td><td>poor for elongated objects</td><td>transform center</td></tr>
<tr><td>AABB</td><td>6 floats</td><td>3 interval tests</td><td>depends on orientation</td><td>recompute (or enlarge conservatively)</td></tr>
<tr><td>OBB</td><td>15 floats (center, 3×3 rotation, half extents)</td><td>up to 15 SAT axes</td><td>tight, orientation independent</td><td>rotate frame with object</td></tr>
<tr><td>k-DOP</td><td>$k$ floats</td><td>$k/2$ interval tests</td><td>tighter with larger $k$</td><td>recompute (or approximate)</td></tr>
</table>
<p>
A tighter BV means fewer false positives and thus fewer expensive exact tests, but each BV test costs more. Which type pays off depends on the application. In bounding volume hierarchies, the same trade-off appears at every node: AABB trees are cheap to refit for deforming meshes [vdB97], while OBB trees prune very effectively for rigid objects in close proximity [GLM96].
</p>
<h3>References</h3>
<ul>
<li>[GLM96] Stefan Gottschalk, Ming C. Lin, Dinesh Manocha. OBBTree: A Hierarchical Structure for Rapid Interference Detection. In Proceedings of SIGGRAPH, 1996.</li>
<li>[KHM98] James T. Klosowski, Martin Held, Joseph S. B. Mitchell, Henry Sowizral, Karel Zikan. Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics, 1998.</li>
<li>[vdB97] Gino van den Bergen. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools, 1997.</li>
<li>[Wel91] Emo Welzl. Smallest Enclosing Disks (Balls and Ellipsoids). In New Results and New Trends in Computer Science, LNCS 555, 1991.</li>
<li>[Rit90] Jack Ritter. An Efficient Bounding Sphere. In Graphics Gems, 1990.</li>
<li>[Eri04] Christer Ericson. Real-Time Collision Detection. Morgan Kaufmann, 2004.</li>
</ul>
</div>
</main>
<script id="simulation_code" type="text/javascript">
// =====================================================================================
// Overview
// --------
// The example consists of three parts:
// 1. Geometry helpers (vectors, convex polygons, the exact polygon-polygon test).
// 2. Bounding volume code: fitting a BV to an object (done once in local coordinates),
// transforming it to world space, and the overlap test of two BVs (bvTest).
// 3. The GUI class: drawing, user interaction and the main loop.
//
// Coordinates: we work directly in canvas pixels, i.e. x points right and y points DOWN.
// A 2D vector is a plain object { x, y }.
// =====================================================================================
// ---- small vector helpers ----
function add(a, b) { return { x: a.x + b.x, y: a.y + b.y }; }
function sub(a, b) { return { x: a.x - b.x, y: a.y - b.y }; }
function mul(a, s) { return { x: a.x * s, y: a.y * s }; } // scale a vector by a scalar s
function dot(a, b) { return a.x * b.x + a.y * b.y; }
function len(a) { return Math.sqrt(dot(a, a)); }
function perp(a) { return { x: -a.y, y: a.x }; } // a rotated by 90 degrees (perpendicular vector)
function normalize(a) { let l = len(a); return { x: a.x / l, y: a.y / l }; }
// rotate p by the angle ang (radians) around the origin: R(ang) * p
function rotate(p, ang) { let c = Math.cos(ang), s = Math.sin(ang); return { x: c * p.x - s * p.y, y: s * p.x + c * p.y }; }
// ---- polygon helpers ----
// Convex hull of a point set (Andrew's monotone chain algorithm).
// The points are sorted by x; then the lower and the upper part of the hull are built
// separately. A point is removed again as soon as it would create a "right turn"
// (cross product <= 0), since then it cannot lie on the convex hull.
// The result is a convex polygon in counter-clockwise order.
function convexHull(points)
{
let p = points.slice().sort((a, b) => a.x - b.x || a.y - b.y);
// z-component of (a - o) x (b - o): > 0 for a left turn o -> a -> b
let cross = (o, a, b) => (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
let lower = [], upper = [];
for (let q of p)
{
while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], q) <= 0) lower.pop();
lower.push(q);
}
for (let i = p.length - 1; i >= 0; i--)
{
while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], p[i]) <= 0) upper.pop();
upper.push(p[i]);
}
// the last point of each chain is the first point of the other one
upper.pop(); lower.pop();
return lower.concat(upper);
}
// Area of a polygon with the shoelace formula: A = 1/2 |sum_i (x_i y_{i+1} - x_{i+1} y_i)|
function polygonArea(poly)
{
let a = 0;
for (let i = 0; i < poly.length; i++)
{
let p = poly[i], q = poly[(i + 1) % poly.length];
a += p.x * q.y - q.x * p.y;
}
return Math.abs(a) / 2;
}
// Center of mass of a polygon (area-weighted, also derived from the shoelace formula).
// The objects are defined relative to their centroid, so they rotate around it.
function polygonCentroid(poly)
{
let a = 0, cx = 0, cy = 0;
for (let i = 0; i < poly.length; i++)
{
let p = poly[i], q = poly[(i + 1) % poly.length];
let w = p.x * q.y - q.x * p.y;
a += w; cx += (p.x + q.x) * w; cy += (p.y + q.y) * w;
}
return { x: cx / (3 * a), y: cy / (3 * a) };
}
// Clip a convex polygon against the half-plane dot(p, n) <= d and return the remaining part
// (one step of the Sutherland-Hodgman algorithm). Used only to construct the k-DOP polygon
// for drawing it - the k-DOP overlap test itself never needs this polygon.
function clipHalfPlane(poly, n, d)
{
let out = [];
for (let i = 0; i < poly.length; i++)
{
let p = poly[i], q = poly[(i + 1) % poly.length];
let dp = dot(p, n) - d, dq = dot(q, n) - d; // signed distances (scaled by |n|) to the boundary line
if (dp <= 0) out.push(p); // p is inside -> keep it
if ((dp < 0 && dq > 0) || (dp > 0 && dq < 0)) // edge p-q crosses the line -> add the intersection point
out.push(add(p, mul(sub(q, p), dp / (dp - dq))));
}
return out;
}
// Project a point set onto an axis and return the covered interval [min, max] of dot(p, axis).
// This is THE basic operation of all interval / separating axis tests in this example.
// (If the axis is not normalized, the interval is scaled by its length - which does not
// change whether two intervals overlap.)
function projectPoints(pts, axis)
{
let lo = Infinity, hi = -Infinity;
for (let p of pts) { let t = dot(p, axis); lo = Math.min(lo, t); hi = Math.max(hi, t); }
return [lo, hi];
}
// p is inside a counter-clockwise convex polygon if it lies to the left of every edge.
// (Only used for picking objects with the mouse.)
function pointInConvexPolygon(p, poly)
{
for (let i = 0; i < poly.length; i++)
{
let a = poly[i], b = poly[(i + 1) % poly.length];
if ((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x) < 0) return false; // right of edge a-b -> outside
}
return true;
}
// EXACT test of two convex polygons with the separating axis theorem (SAT):
// two convex polygons are disjoint if and only if one of the edge normals of P or Q is a
// separating axis, i.e. the projections of P and Q onto that axis do not overlap.
// This is the expensive "narrow phase" test that the bounding volumes are supposed to avoid:
// it needs (#edges of P + #edges of Q) axes, and each projection touches all vertices.
function polygonsIntersect(P, Q)
{
for (let poly of [P, Q])
for (let i = 0; i < poly.length; i++)
{
let axis = perp(sub(poly[(i + 1) % poly.length], poly[i])); // edge normal
let [a0, a1] = projectPoints(P, axis), [b0, b1] = projectPoints(Q, axis);
if (a1 < b0 || b1 < a0) return false; // intervals disjoint -> separated
}
return true; // no separating axis found -> the polygons intersect
}
// ---- object shapes (convex polygons in local coordinates, centered at their centroid) ----
// uniformly distributed random point in an ellipse with radii rx, ry
// (sqrt makes the distribution uniform in area instead of clustering at the center)
function randomInDisc(rx, ry)
{
let a = Math.random() * 2 * Math.PI, r = Math.sqrt(Math.random());
return { x: Math.cos(a) * r * rx, y: Math.sin(a) * r * ry };
}
// Create a random convex polygon of the given kind: generate some points and take their
// convex hull. The shapes are chosen to show the strengths and weaknesses of the BV types,
// e.g. elongated objects are a bad case for spheres (and for AABBs when rotated).
function makeShape(kind)
{
let pts = [];
if (kind === 'elongated')
for (let i = 0; i < 10; i++) pts.push(randomInDisc(140, 26));
else if (kind === 'triangle')
{
// three points on a distorted circle, roughly 120 degrees apart
let a0 = Math.random() * 2 * Math.PI;
for (let i = 0; i < 3; i++)
{
let a = a0 + i * 2 * Math.PI / 3 + (Math.random() - 0.5) * 1.2;
let r = 60 + Math.random() * 50;
pts.push({ x: Math.cos(a) * r, y: Math.sin(a) * r });
}
}
else if (kind === 'round')
// slightly jittered regular 14-gon -> a good case for bounding spheres
for (let i = 0; i < 14; i++)
{
let a = i * 2 * Math.PI / 14, r = 62 + (Math.random() - 0.5) * 8;
pts.push({ x: Math.cos(a) * r, y: Math.sin(a) * r });
}
else // random convex
for (let i = 0; i < 9; i++) pts.push(randomInDisc(95, 75));
let hull = convexHull(pts);
if (hull.length < 3 || polygonArea(hull) < 400) return makeShape(kind); // degenerate -> try again
// move the polygon so that its centroid is the origin of the local coordinate system
let c = polygonCentroid(hull);
return hull.map(p => sub(p, c));
}
// ---- bounding volume fitting (in local coordinates, done once per object) ----
//
// Sphere and OBB are rigidly attached to the object: they are fitted ONCE in the object's
// local coordinate system and later only transformed with the object.
// AABB and k-DOP are defined w.r.t. fixed world directions, so they have to be recomputed
// from the world-space vertices whenever the object rotates (see Body.kdopW).
// Minimal enclosing circle with Welzl's randomized incremental algorithm (expected O(n)).
// Idea: process the points in random order. If a point lies outside the current circle,
// it must lie ON the boundary of the new minimal circle. Then the circle is rebuilt with
// this point (and possibly a second and third point) fixed on its boundary.
// A circle is stored as { c: center, r: radius }.
function minEnclosingCircle(points)
{
// random shuffle (Fisher-Yates) -> guarantees the expected linear running time
let p = points.slice();
for (let i = p.length - 1; i > 0; i--) { let j = Math.floor(Math.random() * (i + 1)); [p[i], p[j]] = [p[j], p[i]]; }
const eps = 1e-7;
let inside = (q, c) => len(sub(q, c.c)) <= c.r + eps;
// smallest circle through two points: the segment a-b is its diameter
let circle2 = (a, b) => ({ c: mul(add(a, b), 0.5), r: len(sub(a, b)) / 2 });
// circle through three points (circumcircle of the triangle a, b, c)
let circle3 = (a, b, c) =>
{
let bx = b.x - a.x, by = b.y - a.y, cx = c.x - a.x, cy = c.y - a.y;
let d = 2 * (bx * cy - by * cx);
if (Math.abs(d) < 1e-12) // collinear: use the widest pair
{
let cands = [circle2(a, b), circle2(a, c), circle2(b, c)];
return cands.reduce((m, x) => x.r > m.r ? x : m);
}
// circumcenter relative to a (solution of a 2x2 linear system)
let ux = (cy * (bx * bx + by * by) - by * (cx * cx + cy * cy)) / d;
let uy = (bx * (cx * cx + cy * cy) - cx * (bx * bx + by * by)) / d;
return { c: { x: a.x + ux, y: a.y + uy }, r: Math.sqrt(ux * ux + uy * uy) };
};
let c = { c: p[0], r: 0 };
for (let i = 1; i < p.length; i++)
{
if (inside(p[i], c)) continue;
c = { c: p[i], r: 0 }; // p[i] must be on the boundary
for (let j = 0; j < i; j++)
{
if (inside(p[j], c)) continue;
c = circle2(p[i], p[j]); // p[i] and p[j] on the boundary
for (let k = 0; k < j; k++)
if (!inside(p[k], c)) c = circle3(p[i], p[j], p[k]); // three boundary points define the circle
}
}
return c;
}
// Fit a box with the given (unit) axis u (and v = perp(u)) to the points:
// project all points onto u and v; the projected intervals give the box extents.
// A box is stored as { c: center, u, v: unit axes, hx, hy: half extents along u and v }.
function boxForAxis(points, u)
{
let v = perp(u);
let [u0, u1] = projectPoints(points, u), [v0, v1] = projectPoints(points, v);
return { c: add(mul(u, (u0 + u1) / 2), mul(v, (v0 + v1) / 2)), u, v, hx: (u1 - u0) / 2, hy: (v1 - v0) / 2 };
}
// OBB fit 1: minimal-area rectangle.
// In 2D, one side of the minimal-area enclosing rectangle is always collinear with an edge
// of the convex hull (this is the basis of the "rotating calipers" algorithm). So we simply
// try every hull edge direction as box axis and keep the box with the smallest area.
// (In 3D, the exact minimal-volume OBB is much more expensive to compute.)
function obbMinArea(hull)
{
let best = null;
for (let i = 0; i < hull.length; i++)
{
let b = boxForAxis(hull, normalize(sub(hull[(i + 1) % hull.length], hull[i])));
if (!best || b.hx * b.hy < best.hx * best.hy) best = b;
}
return best;
}
// OBB fit 2: principal component analysis (PCA).
// The box axes are the eigenvectors of the covariance matrix
// C = 1/n sum_i (p_i - m)(p_i - m)^T (m = mean of the points),
// i.e. the directions of largest and smallest spread of the points. This is fast and common
// in practice (e.g. OBBTree), but not optimal, and the result depends on how the vertices
// are distributed over the object.
function obbPCA(points)
{
let m = { x: 0, y: 0 };
for (let p of points) m = add(m, p);
m = mul(m, 1 / points.length);
// entries of the symmetric 2x2 covariance matrix (the factor 1/n does not change the eigenvectors)
let cxx = 0, cyy = 0, cxy = 0;
for (let p of points)
{
let d = sub(p, m);
cxx += d.x * d.x; cyy += d.y * d.y; cxy += d.x * d.y;
}
// for a symmetric 2x2 matrix, the angle of the first eigenvector has a closed form
let ang = 0.5 * Math.atan2(2 * cxy, cxx - cyy);
return boxForAxis(points, { x: Math.cos(ang), y: Math.sin(ang) });
}
// The k/2 fixed directions of a 2D k-DOP, evenly spaced over 180 degrees.
// Each direction n_i bounds the object from both sides (min and max), which gives k
// half-planes in total. k = 4 gives the directions (1,0) and (0,1), i.e. an AABB.
function kdopDirections(k)
{
let m = k / 2, dirs = [];
for (let i = 0; i < m; i++) dirs.push({ x: Math.cos(i * Math.PI / m), y: Math.sin(i * Math.PI / m) });
return dirs;
}
// A rigid object: a convex polygon given in local coordinates plus a position (center)
// and a rotation angle. Its bounding volumes are fitted once in local coordinates.
class Body
{
constructor(local, center, angle)
{
this.local = local; // vertices in local coordinates (centroid = origin)
this.center = center; // world position of the local origin
this.angle = angle; // rotation angle in radians
this.area = polygonArea(local);
// fitted once - both are rigidly attached to the object
this.sphere = minEnclosingCircle(local);
this.obb = { min: obbMinArea(local), pca: obbPCA(local) };
this.update();
}
// local -> world: x_world = R(angle) * x_local + center
toWorld(p) { return add(this.center, rotate(p, this.angle)); }
// world-space vertices (needed for drawing, for the exact test and for AABB / k-DOP)
update() { this.world = this.local.map(p => this.toWorld(p)); }
// ---- world-space bounding volumes ----
// Sphere: only the center has to be transformed, the radius is rotation invariant.
sphereW() { return { c: this.toWorld(this.sphere.c), r: this.sphere.r }; }
// OBB: transform the center and rotate the box axes with the object;
// the half extents stay the same. Cost: independent of the number of vertices.
obbW(fit)
{
let o = this.obb[fit];
return { c: this.toWorld(o.c), u: rotate(o.u, this.angle), v: rotate(o.v, this.angle), hx: o.hx, hy: o.hy };
}
// k-DOP (and AABB = 4-DOP): for each fixed world direction, the interval [min, max] of
// the projected world vertices. Since the directions do not rotate with the object,
// this has to be recomputed from ALL vertices after every rotation.
kdopW(dirs) { return dirs.map(d => projectPoints(this.world, d)); }
}
// the four corners of an OBB: c +- hx*u +- hy*v
function obbCorners(o)
{
let U = mul(o.u, o.hx), V = mul(o.v, o.hy);
return [sub(sub(o.c, U), V), sub(add(o.c, U), V), add(add(o.c, U), V), add(sub(o.c, U), V)];
}
// The k-DOP as a polygon (only needed for drawing and for computing its area):
// the intersection of the k half-planes min_i <= dot(p, n_i) <= max_i.
// Start with a huge square and clip it against every half-plane.
function kdopPolygon(dirs, intervals)
{
let poly = [{ x: -1e5, y: -1e5 }, { x: 1e5, y: -1e5 }, { x: 1e5, y: 1e5 }, { x: -1e5, y: 1e5 }];
dirs.forEach((d, i) =>
{
poly = clipHalfPlane(poly, d, intervals[i][1]); // dot(p, n_i) <= max_i
poly = clipHalfPlane(poly, mul(d, -1), -intervals[i][0]); // dot(p, n_i) >= min_i
});
return poly;
}
// Static information about the BV types, shown in the GUI (colors, storage, number of tests).
// Storage in 2D / 3D: sphere: center + radius; AABB: min + max corner;
// OBB: center + rotation (2D: 1 angle, 3D: 3x3 matrix) + half extents; k-DOP: k interval bounds.
const BV_INFO = {
sphere: { name: "Bounding sphere", color: "#8b5cf6", storage: () => "3 / 4 floats",
max2D: () => "1", max3D: () => "1",
update: "transform the center only (rotation invariant)" },
aabb: { name: "AABB", color: "#f97316", storage: () => "4 / 6 floats",
max2D: () => "2", max3D: () => "3",
update: "recompute from all vertices" },
obb: { name: "OBB", color: "#0891b2", storage: () => "5 / 15 floats",
max2D: () => "4", max3D: () => "15",
update: "rotate the box axes with the object" },
kdop: { name: "k-DOP", color: "#db2777", storage: k => `${k} / ${k} floats`,
max2D: k => `${k / 2}`, max3D: k => `${k / 2}`,
update: "recompute from all vertices (k/2 projections each)" }
};
// World-space geometry of a bounding volume, for drawing and area computation:
// either a circle { circle: true, c, r } or a convex polygon { pts }.
function bvGeometry(type, body, opts)
{
if (type === 'sphere') { let s = body.sphereW(); return { circle: true, c: s.c, r: s.r }; }
if (type === 'obb') return { pts: obbCorners(body.obbW(opts.obbFit)) };
let dirs = kdopDirections(type === 'aabb' ? 4 : opts.k); // an AABB is the 4-DOP
return { pts: kdopPolygon(dirs, body.kdopW(dirs)) };
}
// area of a BV - used to measure how tightly it fits (BV area / object area)
function bvArea(g) { return g.circle ? Math.PI * g.r * g.r : polygonArea(g.pts); }
// =====================================================================================
// The overlap test of two bounding volumes
// =====================================================================================
// The test is returned as a list of individual tests ("rows") so that the GUI can show
// each of them. All BV types except the sphere use interval tests:
// - project both BVs onto an axis -> two intervals [a0, a1] and [b0, b1]
// - the intervals are disjoint if a1 < b0 or b1 < a0 -> the axis separates the BVs
// The BVs overlap only if the intervals overlap on ALL tested axes. Therefore the test can
// stop at the first separating axis ("early exit"); the remaining rows are then skipped.
//
// Returns { rows, overlap, evaluated }:
// rows[i] = { name, axis, a: interval of A, b: interval of B, separated, evaluated, decisive }
// overlap = true if the BVs overlap
// evaluated = number of tests that were actually performed (up to the early exit)
function bvTest(type, A, B, opts)
{
let rows = [];
if (type === 'sphere')
{
// Spheres: a single test. The spheres are disjoint if the distance of the centers is
// larger than the sum of the radii. (In practice one compares squared values,
// |c_B - c_A|^2 > (r_A + r_B)^2, to avoid the square root; here we need d for display.)
let sa = A.sphereW(), sb = B.sphereW();
let d = len(sub(sb.c, sa.c));
rows.push({ sphere: true, name: "center distance", cA: sa.c, cB: sb.c, rA: sa.r, rB: sb.r, d, separated: d > sa.r + sb.r });
}
else if (type === 'obb')
{
// OBBs: separating axis theorem. In 2D, the candidate axes are the two box axes of A
// and the two box axes of B (in 3D: 3 + 3 face normals + 9 edge-edge cross products).
let oa = A.obbW(opts.obbFit), ob = B.obbW(opts.obbFit);
// Interval of an OBB on axis L: centered at dot(c, L) with the projected radius
// r = hx * |dot(u, L)| + hy * |dot(v, L)|
// (each half extent contributes as much as its axis points along L).
let interval = (o, L) =>
{
let c = dot(o.c, L), r = o.hx * Math.abs(dot(o.u, L)) + o.hy * Math.abs(dot(o.v, L));
return [c - r, c + r];
};
for (let [name, L] of [["u_A (axis 1 of A)", oa.u], ["v_A (axis 2 of A)", oa.v], ["u_B (axis 1 of B)", ob.u], ["v_B (axis 2 of B)", ob.v]])
rows.push({ name, axis: L, a: interval(oa, L), b: interval(ob, L) });
}
else
{
// AABB and k-DOP: the axes are the FIXED directions, and the intervals are exactly the
// stored BV data (min/max per direction) - no projection is needed at test time.
// The AABB test is the k-DOP test with k = 4 (directions x and y).
let k = type === 'aabb' ? 4 : opts.k;
let dirs = kdopDirections(k);
let ia = A.kdopW(dirs), ib = B.kdopW(dirs);
dirs.forEach((d, i) =>
{
let deg = Math.round(i * 180 / (k / 2));
let name = type === 'aabb' ? (i === 0 ? "x-axis" : "y-axis") : `n${i + 1} (${deg}°)`;
rows.push({ name, axis: d, a: ia[i], b: ib[i] });
});
}
// Evaluate the tests in order with early exit.
// (For visualization, the intervals of the skipped rows were computed above as well;
// a real implementation would of course stop computing at the first separating axis.)
let overlap = true, evaluated = 0;
for (let r of rows)
{
if (!r.sphere) r.separated = r.a[1] < r.b[0] || r.b[1] < r.a[0]; // interval test
r.evaluated = overlap; // rows after a separating axis are skipped
if (overlap) evaluated++;
if (overlap && r.separated) { overlap = false; r.decisive = true; } // first separating axis -> stop
}
return { rows, overlap, evaluated };
}
// =====================================================================================
// GUI: user interaction, drawing and the main loop.
// The collision detection itself happens in mainLoop() (bvTest + polygonsIntersect);
// everything else in this class only visualizes the results.
// =====================================================================================
class GUI
{
constructor()
{
// two canvases: the scene (objects + BVs) and the panel listing the individual tests
this.canvas = document.getElementById("simCanvas");
this.c = this.canvas.getContext("2d");
this.testCanvas = document.getElementById("testCanvas");
this.tc = this.testCanvas.getContext("2d");
// current settings (read from the HTML controls)
this.type = document.getElementById("typeInput").value;
this.k = parseInt(document.getElementById("kInput").value);
this.obbFit = document.getElementById("obbFitInput").value;
this.autoRotate = document.getElementById("rotateInput").checked;
this.overlay = document.getElementById("overlayInput").checked;
this.hoverRow = null; // index of the test row under the mouse (or null)
this.drag = null; // current drag operation (moving or rotating an object)
// mouse / touch handling: drag to move, shift/right-drag or wheel to rotate
this.canvas.addEventListener("mousedown", this.mouseDown.bind(this), false);
window.addEventListener("mousemove", this.mouseMove.bind(this), false);
window.addEventListener("mouseup", () => { this.drag = null; }, false);
this.canvas.addEventListener("contextmenu", e => e.preventDefault(), false);
this.canvas.addEventListener("wheel", this.wheel.bind(this), { passive: false });
this.canvas.addEventListener("touchstart", this.touchStart.bind(this), { passive: false });
this.canvas.addEventListener("touchmove", this.touchMove.bind(this), { passive: false });
this.canvas.addEventListener("touchend", () => { this.drag = null; }, { passive: false });
this.testCanvas.addEventListener("mousemove", this.testMouseMove.bind(this), false);
this.testCanvas.addEventListener("mouseleave", () => { this.hoverRow = null; }, false);
this.buildCompareTable();
this.setType(this.type);
this.restart();
this.mainLoop();
}
// options needed by the BV functions: k of the k-DOP and the OBB fitting method
get opts() { return { k: this.k, obbFit: this.obbFit }; }
// create two new random objects A and B (their BVs are fitted in the Body constructor)
restart()
{
let kind = document.getElementById("shapeInput").value;
let W = this.canvas.width, H = this.canvas.height;
let shapeA = makeShape(kind === 'mixed' ? 'elongated' : kind);
let shapeB = makeShape(kind === 'mixed' ? 'random' : kind);
this.A = new Body(shapeA, { x: W * 0.36, y: H * 0.5 }, Math.PI / 5);
this.B = new Body(shapeB, { x: W * 0.64, y: H * 0.5 }, Math.random() * Math.PI);
}
// select the BV type to show ('sphere', 'aabb', 'obb' or 'kdop')
setType(type)
{
this.type = type;
document.getElementById("typeInput").value = type;
document.getElementById("kInput").disabled = type !== 'kdop';
document.getElementById("obbFitInput").disabled = type !== 'obb';
this.hoverRow = null;
}
// create the rows of the comparison table once; updateStats() only fills in the values
buildCompareTable()
{
let body = document.querySelector("#compareTable tbody");
for (let t of ['sphere', 'aabb', 'obb', 'kdop'])
{
let tr = document.createElement("tr");
tr.id = "cmp_" + t;
tr.innerHTML = `<td><span class="swatch" style="background:${BV_INFO[t].color}"></span><span class="nm"></span></td>` +
`<td class="ra"></td><td class="rb"></td><td class="ov"></td><td class="ev"></td><td class="m2"></td><td class="m3"></td>`;
tr.addEventListener("click", () => this.setType(t));
body.appendChild(tr);
}
}
// ---- main loop ----
// Called once per frame:
// 1. move the objects (auto-rotation; dragging changes center/angle directly)
// 2. BV test (cheap, conservative)
// 3. exact test of the objects (expensive). In a real collision detection, this test is
// ONLY performed if the BVs overlap. We always run it here, so that the GUI can show
// whether a BV overlap is a real collision or a false positive.
// 4. draw everything
mainLoop()
{
if (this.autoRotate)
{
this.A.angle += 0.004;
this.B.angle -= 0.0065;
}
this.A.update();
this.B.update();
let opts = this.opts;
this.result = bvTest(this.type, this.A, this.B, opts); // stage 1: BV test
this.exact = polygonsIntersect(this.A.world, this.B.world); // stage 2: exact test
this.drawScene();
this.drawTests();
this.updateStats();
window.requestAnimationFrame(this.mainLoop.bind(this));
}
// Update the HTML statistics and the comparison table.
// Classification of the result:
// BVs disjoint -> no collision, exact test not needed (early out)
// BVs overlap, objects collide -> collision
// BVs overlap, objects do not -> false positive (the BV was not tight enough)
// A false negative (BVs disjoint, but objects collide) is impossible, since every BV
// completely contains its object.
updateStats()
{
let r = this.result, info = BV_INFO[this.type];
let set = (id, text, color) => { let e = document.getElementById(id); e.textContent = text; e.style.color = color || ""; };
set("bvStatus", r.overlap ? "BVs overlap" : "BVs disjoint", r.overlap ? "#d97706" : "#059669");
if (r.overlap)
set("exactStatus", this.exact ? "Collision" : "No collision", this.exact ? "#e61e1e" : "#059669");
else
set("exactStatus", "not needed", "#6b7280");
let cls = !r.overlap ? "No collision (early out)" : this.exact ? "Collision" : "False positive";
set("classification", cls, !r.overlap ? "#059669" : this.exact ? "#e61e1e" : "#d97706");
set("testsEvaluated", `${r.evaluated} of ${r.rows.length}`);
set("storage", info.storage(this.k));
set("updateCost", info.update);
// live comparison of all types: run the BV test of every type on the current configuration
// and measure the tightness as (area of the BV) / (area of the object) >= 1
let opts = this.opts;
for (let t of ['sphere', 'aabb', 'obb', 'kdop'])
{
let tr = document.getElementById("cmp_" + t);
let res = t === this.type ? r : bvTest(t, this.A, this.B, opts);
let ratioA = bvArea(bvGeometry(t, this.A, opts)) / this.A.area;
let ratioB = bvArea(bvGeometry(t, this.B, opts)) / this.B.area;
tr.className = t === this.type ? "selected" : "";
tr.querySelector(".nm").textContent = t === 'kdop' ? `${this.k}-DOP` : t === 'obb' ? `OBB (${this.obbFit === 'min' ? 'min. area' : 'PCA'})` : BV_INFO[t].name;
tr.querySelector(".ra").textContent = ratioA.toFixed(2);
tr.querySelector(".rb").textContent = ratioB.toFixed(2);
let ov = tr.querySelector(".ov");
ov.textContent = res.overlap ? (this.exact ? "yes" : "yes (false positive)") : "no";
ov.style.color = res.overlap ? (this.exact ? "#e61e1e" : "#d97706") : "#059669";
tr.querySelector(".ev").textContent = res.evaluated;
tr.querySelector(".m2").textContent = BV_INFO[t].max2D(this.k);
tr.querySelector(".m3").textContent = BV_INFO[t].max3D(this.k);
}
}
// ---- scene ----
// Draw the scene: grid, (optionally) the other BV types, the selected BVs, the objects,
// the visualization of one test (axis + intervals or sphere distance) and a status header.
drawScene()
{
let c = this.c, W = this.canvas.width, H = this.canvas.height;
let opts = this.opts, info = BV_INFO[this.type];
c.clearRect(0, 0, W, H);
c.fillStyle = "#ffffff";
c.fillRect(0, 0, W, H);
// light grid + world frame (the axes AABBs are aligned with)
c.strokeStyle = "#f1f3f7";
c.lineWidth = 1;
for (let x = 0; x <= W; x += 40) { c.beginPath(); c.moveTo(x, 0); c.lineTo(x, H); c.stroke(); }
for (let y = 0; y <= H; y += 40) { c.beginPath(); c.moveTo(0, y); c.lineTo(W, y); c.stroke(); }
// (canvas coordinates: y points down)
this.drawArrow(c, { x: 22, y: H - 72 }, { x: 72, y: H - 72 }, "#6b7280", "x");
this.drawArrow(c, { x: 22, y: H - 72 }, { x: 22, y: H - 22 }, "#6b7280", "y");
// other BV types (faint, dashed) for comparison
if (this.overlay)
for (let t of ['sphere', 'aabb', 'obb', 'kdop'])
{
if (t === this.type) continue;
c.save();
c.strokeStyle = BV_INFO[t].color;
c.globalAlpha = 0.6;
c.lineWidth = 1.2;
c.setLineDash([5, 4]);
for (let b of [this.A, this.B]) { this.pathGeometry(c, bvGeometry(t, b, opts)); c.stroke(); }
c.restore();
}
// selected BVs: fill
let geoms = [bvGeometry(this.type, this.A, opts), bvGeometry(this.type, this.B, opts)];
for (let g of geoms)
{
this.pathGeometry(c, g);
c.fillStyle = this.result.overlap ? "rgba(245,158,11,0.16)" : this.hexAlpha(info.color, 0.10);
c.fill();
}
// the objects themselves
[[this.A, "rgba(70,115,229,0.45)", "#4673e5", "A"], [this.B, "rgba(16,185,129,0.45)", "#10b981", "B"]].forEach(([b, fill, stroke, label]) =>
{
c.beginPath();
b.world.forEach((p, i) => i === 0 ? c.moveTo(p.x, p.y) : c.lineTo(p.x, p.y));
c.closePath();
c.fillStyle = this.exact ? "rgba(230,30,30,0.45)" : fill;
c.fill();
c.strokeStyle = this.exact ? "#e61e1e" : stroke;
c.lineWidth = 2;
c.stroke();
c.fillStyle = "#111827";
c.font = "bold 19px Inter, sans-serif";
c.textAlign = "center";
c.fillText(label, b.center.x, b.center.y + 5);
c.textAlign = "left";
});
// selected BVs: outline
for (let g of geoms)
{
this.pathGeometry(c, g);
c.strokeStyle = info.color;
c.lineWidth = 2.5;
c.stroke();
}
if (this.type === 'obb') // draw the box axes u, v
for (let b of [this.A, this.B])
{
let o = b.obbW(this.obbFit);
this.drawArrow(c, o.c, add(o.c, mul(o.u, Math.max(o.hx, 25))), info.color, "u");
this.drawArrow(c, o.c, add(o.c, mul(o.v, Math.max(o.hy, 25))), info.color, "v");
}
// visualize one test: the hovered row, otherwise the separating axis that ended the test
let rows = this.result.rows;
let row = this.hoverRow !== null && rows[this.hoverRow] ? rows[this.hoverRow] : rows.find(r => r.decisive || r.sphere);
if (row)
{
if (row.sphere) this.drawSphereTest(row);
else this.drawAxisTest(row);
}
// header
c.font = "bold 19px Inter, sans-serif";
c.fillStyle = info.color;
c.fillText(this.type === 'kdop' ? `${this.k}-DOP` : info.name, 12, 26);
c.font = "17px Inter, sans-serif";
let r = this.result;
c.fillStyle = r.overlap ? "#d97706" : "#059669";
c.fillText(r.overlap ? `1. BV test: overlap on all ${r.rows.length} test(s) → exact test required`
: `1. BV test: separated by test ${r.evaluated} of ${r.rows.length} → stop, objects cannot collide`, 12, 50);
if (r.overlap)
{
c.fillStyle = this.exact ? "#e61e1e" : "#d97706";
c.fillText(this.exact ? "2. Exact test: objects collide" : "2. Exact test: objects do NOT collide → the BV test was a false positive", 12, 72);
}
else
{
c.fillStyle = "#9ca3af";
c.fillText("2. Exact test: skipped", 12, 72);
}
c.strokeStyle = "#999999";
c.lineWidth = 1;
c.strokeRect(0, 0, W, H);
}
// create a canvas path for a BV geometry (circle or polygon, see bvGeometry)
pathGeometry(c, g)
{
c.beginPath();
if (g.circle) c.arc(g.c.x, g.c.y, g.r, 0, 2 * Math.PI);
else { g.pts.forEach((p, i) => i === 0 ? c.moveTo(p.x, p.y) : c.lineTo(p.x, p.y)); c.closePath(); }
}
// "#rrggbb" -> "rgba(r,g,b,a)"
hexAlpha(hex, a)
{
let n = parseInt(hex.slice(1), 16);
return `rgba(${n >> 16},${(n >> 8) & 255},${n & 255},${a})`;
}
// arrow from 'from' to 'to' with an optional label at its tip
drawArrow(c, from, to, color, label)
{
let d = normalize(sub(to, from)), n = perp(d);
c.save();
c.strokeStyle = color; c.fillStyle = color; c.lineWidth = 1.8;
c.beginPath(); c.moveTo(from.x, from.y); c.lineTo(to.x, to.y); c.stroke();
let h1 = add(sub(to, mul(d, 8)), mul(n, 4)), h2 = sub(sub(to, mul(d, 8)), mul(n, 4));
c.beginPath(); c.moveTo(to.x, to.y); c.lineTo(h1.x, h1.y); c.lineTo(h2.x, h2.y); c.closePath(); c.fill();
if (label)
{
c.font = "italic 16px Inter, sans-serif";
let p = add(to, mul(d, 9));
c.textAlign = "center";
c.fillText(label, p.x, p.y + 4);
c.textAlign = "left";
}
c.restore();
}
// Visualize the sphere test in the scene: the line between the centers (length d),
// the radius r_A measured from c_A towards B and r_B measured from c_B towards A.
// If the two radius segments do not meet (d > r_A + r_B), the remaining gap is drawn in red.
drawSphereTest(row)
{
let c = this.c;
let d = normalize(sub(row.cB, row.cA)); // unit direction from c_A to c_B
let endA = add(row.cA, mul(d, row.rA)), endB = sub(row.cB, mul(d, row.rB));
c.save();
c.setLineDash([4, 4]);
c.strokeStyle = "#374151"; c.lineWidth = 1.5;
c.beginPath(); c.moveTo(row.cA.x, row.cA.y); c.lineTo(row.cB.x, row.cB.y); c.stroke();