forked from RandyGaul/cute_headers
-
Notifications
You must be signed in to change notification settings - Fork 0
/
tinyc2.h
1708 lines (1507 loc) · 45.7 KB
/
tinyc2.h
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
/*
------------------------------------------------------------------------------
Licensing information can be found at the end of the file.
------------------------------------------------------------------------------
tinyc2.h - v1.04
To create implementation (the function definitions)
#define TINYC2_IMPLEMENTATION
in *one* C/CPP file (translation unit) that includes this file
SUMMARY:
tinyc2 is a single-file header that implements 2D collision detection routines
that test for overlap, and optionally can find the collision manifold. The
manifold contains all necessary information to prevent shapes from inter-
penetrating, which is useful for character controllers, general physics
simulation, and user-interface programming.
This header implements a group of "immediate mode" functions that should be
very easily adapted into pre-existing projects.
Revision history:
1.0 (02/13/2017) initial release
1.01 (02/13/2017) const crusade, minor optimizations, capsule degen
1.02 (03/21/2017) compile fixes for c on more compilers
1.03 (09/15/2017) various bugfixes and quality of life changes to manifolds
1.04 (03/25/2018) fixed manifold bug in c2CircletoAABBManifold
*/
/*
Contributors:
Plastburk 1.01 - const pointers pull request
mmozeiko 1.02 - 3 compile bugfixes
felipefs 1.02 - 3 compile bugfixes
seemk 1.02 - fix branching bug in c2Collide
sro5h 1.02 - bug reports for multiple manifold funcs
sro5h 1.03 - work involving quality of life fixes for manifolds
*/
/*
THE IMPORTANT PARTS:
Most of the math types in this header are for internal use. Users care about
the shape types and the collision functions.
SHAPE TYPES:
* c2Circle
* c2Capsule
* c2AABB
* c2Ray
* c2Poly
COLLISION FUNCTIONS (*** is a shape name from the above list):
* c2***to*** - boolean YES/NO hittest
* c2***to***Manifold - construct manifold to describe how shapes hit
* c2GJK - runs GJK algorithm to find closest point pair
between two shapes
* c2MakePoly - Runs convex hull algorithm and computes normals on input point-set
* c2Collided - generic version of c2***to*** funcs
* c2Collide - generic version of c2***to***Manifold funcs
* c2CastRay - generic version of c2Rayto*** funcs
The rest of the header is more or less for internal use. Here is an example of
making some shapes and testing for collision:
c2Circle c;
c.p = position;
c.r = radius;
c2Capsule cap;
cap.a = first_endpoint;
cap.b = second_endpoint;
cap.r = radius;
int hit = c2CircletoCapsule(c, cap);
if (hit)
{
handle collision here...
}
For more code examples and tests please see:
https://github.com/RandyGaul/tinyheaders/tree/master/examples_tinygl_and_tinyc2
Here is a past discussion thread on this header:
https://www.reddit.com/r/gamedev/comments/5tqyey/tinyc2_2d_collision_detection_library_in_c/
Here is a very nice repo containing various tests and examples using SFML for rendering:
https://github.com/sro5h/tinyc2-tests
*/
/*
DETAILS/ADVICE:
This header does not implement a broad-phase, and instead concerns itself with
the narrow-phase. This means this header just checks to see if two individual
shapes are touching, and can give information about how they are touching.
Very common 2D broad-phases are tree and grid approaches. Quad trees are good
for static geometry that does not move much if at all. Dynamic AABB trees are
good for general purpose use, and can handle moving objects very well. Grids
are great and are similar to quad trees.
If implementing a grid it can be wise to have each collideable grid cell hold
an integer. This integer refers to a 2D shape that can be passed into the
various functions in this header. The shape can be transformed from "model"
space to "world" space using c2x -- a transform struct. In this way a grid
can be implemented that holds any kind of convex shape (that this header
supports) while conserving memory with shape instancing.
Please email at my address with any questions or comments at:
author's last name followed by 1748 at gmail
*/
/*
Features:
* Circles, capsules, AABBs, rays and convex polygons are supported
* Fast boolean only result functions (hit yes/no)
* Slghtly slower manifold generation for collision normals + depths +points
* GJK implementation (finds closest points for disjoint pairs of shapes)
* Robust 2D convex hull generator
* Lots of correctly implemented and tested 2D math routines
* Implemented in portable C, and is readily portable to other languages
* Generic c2Collide, c2Collided and c2CastRay function (can pass in any shape type)
* Extensive examples at: https://github.com/RandyGaul/tinyheaders/tree/master/examples_tinygl_and_tinyc2
*/
#if !defined(TINYC2_H)
// this can be adjusted as necessary, but is highly recommended to be kept at 8.
// higher numbers will incur quite a bit of memory overhead, and convex shapes
// over 8 verts start to just look like spheres, which can be implicitly rep-
// resented as a point + radius. usually tools that generate polygons should be
// constructed so they do not output polygons with too many verts.
// Note: polygons in tinyc2 are all *convex*.
#define C2_MAX_POLYGON_VERTS 8
// 2d vector
typedef struct
{
float x;
float y;
} c2v;
// 2d rotation composed of cos/sin pair
typedef struct
{
float c;
float s;
} c2r;
// 2d rotation matrix
typedef struct
{
c2v x;
c2v y;
} c2m;
// 2d transformation "x"
// These are used especially for c2Poly when a c2Poly is passed to a function.
// Since polygons are prime for "instancing" a c2x transform can be used to
// transform a polygon from local space to world space. In functions that take
// a c2x pointer (like c2PolytoPoly), these pointers can be NULL, which represents
// an identity transformation and assumes the verts inside of c2Poly are already
// in world space.
typedef struct
{
c2v p;
c2r r;
} c2x;
// 2d halfspace (aka plane, aka line)
typedef struct
{
c2v n; // normal, normalized
float d; // distance to origin from plane, or ax + by = d
} c2h;
typedef struct
{
c2v p;
float r;
} c2Circle;
typedef struct
{
c2v min;
c2v max;
} c2AABB;
// a capsule is defined as a line segment (from a to b) and radius r
typedef struct
{
c2v a;
c2v b;
float r;
} c2Capsule;
typedef struct
{
int count;
c2v verts[C2_MAX_POLYGON_VERTS];
c2v norms[C2_MAX_POLYGON_VERTS];
} c2Poly;
// IMPORTANT:
// Many algorithms in this file are sensitive to the magnitude of the
// ray direction (c2Ray::d). It is highly recommended to normalize the
// ray direction and use t to specify a distance. Please see this link
// for an in-depth explanation: https://github.com/RandyGaul/tinyheaders/issues/30
typedef struct
{
c2v p; // position
c2v d; // direction (normalized)
float t; // distance along d from position p to find endpoint of ray
} c2Ray;
typedef struct
{
float t; // time of impact
c2v n; // normal of surface at impact (unit length)
} c2Raycast;
// position of impact p = ray.p + ray.d * raycast.t
#define c2Impact(ray, t) c2Add(ray.p, c2Mulvs(ray.d, t))
// contains all information necessary to resolve a collision, or in other words
// this is the information needed to separate shapes that are colliding. Doing
// the resolution step is *not* included in tinyc2. tinyc2 does not include
// "feature information" that describes which topological features collided.
// However, modifying the exist ***Manifold funcs can be done to output any
// needed feature information. Feature info is sometimes needed for certain kinds
// of simulations that cache information over multiple game-ticks, of which are
// associated to the collision of specific features. An example implementation
// is in the qu3e 3D physics engine library: https://github.com/RandyGaul/qu3e
typedef struct
{
int count;
float depths[2];
c2v contact_points[2];
// always points from shape A to shape B (first and second shapes passed into
// any of the c2***to***Manifold functions)
c2v n;
} c2Manifold;
// boolean collision detection
// these versions are faster than the manifold versions, but only give a YES/NO
// result
int c2CircletoCircle(c2Circle A, c2Circle B);
int c2CircletoAABB(c2Circle A, c2AABB B);
int c2CircletoCapsule(c2Circle A, c2Capsule B);
int c2AABBtoAABB(c2AABB A, c2AABB B);
int c2AABBtoCapsule(c2AABB A, c2Capsule B);
int c2CapsuletoCapsule(c2Capsule A, c2Capsule B);
int c2CircletoPoly(c2Circle A, const c2Poly* B, const c2x* bx);
int c2AABBtoPoly(c2AABB A, const c2Poly* B, const c2x* bx);
int c2CapsuletoPoly(c2Capsule A, const c2Poly* B, const c2x* bx);
int c2PolytoPoly(const c2Poly* A, const c2x* ax, const c2Poly* B, const c2x* bx);
// ray operations
// output is placed into the c2Raycast struct, which represents the hit location
// of the ray. the out param contains no meaningful information if these funcs
// return 0
int c2RaytoCircle(c2Ray A, c2Circle B, c2Raycast* out);
int c2RaytoAABB(c2Ray A, c2AABB B, c2Raycast* out);
int c2RaytoCapsule(c2Ray A, c2Capsule B, c2Raycast* out);
int c2RaytoPoly(c2Ray A, const c2Poly* B, const c2x* bx_ptr, c2Raycast* out);
// manifold generation
// these functions are slower than the boolean versions, but will compute one
// or two points that represent the plane of contact. This information is
// is usually needed to resolve and prevent shapes from colliding. If no coll
// ision occured the count member of the manifold struct is set to 0.
void c2CircletoCircleManifold(c2Circle A, c2Circle B, c2Manifold* m);
void c2CircletoAABBManifold(c2Circle A, c2AABB B, c2Manifold* m);
void c2CircletoCapsuleManifold(c2Circle A, c2Capsule B, c2Manifold* m);
void c2AABBtoAABBManifold(c2AABB A, c2AABB B, c2Manifold* m);
void c2AABBtoCapsuleManifold(c2AABB A, c2Capsule B, c2Manifold* m);
void c2CapsuletoCapsuleManifold(c2Capsule A, c2Capsule B, c2Manifold* m);
void c2CircletoPolyManifold(c2Circle A, const c2Poly* B, const c2x* bx, c2Manifold* m);
void c2AABBtoPolyManifold(c2AABB A, const c2Poly* B, const c2x* bx, c2Manifold* m);
void c2CapsuletoPolyManifold(c2Capsule A, const c2Poly* B, const c2x* bx, c2Manifold* m);
void c2PolytoPolyManifold(const c2Poly* A, const c2x* ax, const c2Poly* B, const c2x* bx, c2Manifold* m);
typedef enum
{
C2_CIRCLE,
C2_AABB,
C2_CAPSULE,
C2_POLY
} C2_TYPE;
// Runs the GJK algorithm to find closest points, returns distance between closest points.
// outA and outB can be NULL, in this case only distance is returned. ax_ptr and bx_ptr
// can be NULL, and represent local to world transformations for shapes A and B respectively.
// use_radius will apply radii for capsules and circles (if set to false, spheres are
// treated as points and capsules are treated as line segments i.e. rays).
float c2GJK(const void* A, C2_TYPE typeA, const c2x* ax_ptr, const void* B, C2_TYPE typeB, const c2x* bx_ptr, c2v* outA, c2v* outB, int use_radius);
// Computes 2D convex hull. Will not do anything if less than two verts supplied. If
// more than C2_MAX_POLYGON_VERTS are supplied extras are ignored.
int c2Hull(c2v* verts, int count);
void c2Norms(c2v* verts, c2v* norms, int count);
// runs c2Hull and c2Norms, assumes p->verts and p->count are both set to valid values
void c2MakePoly(c2Poly* p);
// Generic collision detection routines, useful for games that want to use some poly-
// morphism to write more generic-styled code. Internally calls various above functions.
// For AABBs/Circles/Capsules ax and bx are ignored. For polys ax and bx can define
// model to world transformations, or be NULL for identity transforms.
int c2Collided(const void* A, const c2x* ax, C2_TYPE typeA, const void* B, const c2x* bx, C2_TYPE typeB);
void c2Collide(const void* A, const c2x* ax, C2_TYPE typeA, const void* B, const c2x* bx, C2_TYPE typeB, c2Manifold* m);
int c2CastRay(c2Ray A, const void* B, const c2x* bx, C2_TYPE typeB, c2Raycast* out);
#ifdef _MSC_VER
#define C2_INLINE __forceinline
#else
#define C2_INLINE inline __attribute__((always_inline))
#endif
// adjust these primitives as seen fit
#include <string.h> // memcpy
#include <math.h>
#define c2Sin(radians) sinf(radians)
#define c2Cos(radians) cosf(radians)
#define c2Sqrt(a) sqrtf(a)
#define c2Min(a, b) ((a) < (b) ? (a) : (b))
#define c2Max(a, b) ((a) > (b) ? (a) : (b))
#define c2Abs(a) ((a) < 0 ? -(a) : (a))
#define c2Clamp(a, lo, hi) c2Max(lo, c2Min(a, hi))
C2_INLINE void c2SinCos(float radians, float* s, float* c) { *c = c2Cos(radians); *s = c2Sin(radians); }
#define c2Sign(a) (a < 0 ? -1.0f : 1.0f)
// The rest of the functions in the header-only portion are all for internal use
// and use the author's personal naming conventions. It is recommended to use one's
// own math library instead of the one embedded here in tinyc2, but for those
// curious or interested in trying it out here's the details:
// The Mul functions are used to perform multiplication. x stands for transform,
// v stands for vector, s stands for scalar, r stands for rotation, h stands for
// halfspace and T stands for transpose.For example c2MulxvT stands for "multiply
// a transform with a vector, and transpose the transform".
// vector ops
C2_INLINE c2v c2V(float x, float y) { c2v a; a.x = x; a.y = y; return a; }
C2_INLINE c2v c2Add(c2v a, c2v b) { a.x += b.x; a.y += b.y; return a; }
C2_INLINE c2v c2Sub(c2v a, c2v b) { a.x -= b.x; a.y -= b.y; return a; }
C2_INLINE float c2Dot(c2v a, c2v b) { return a.x * b.x + a.y * b.y; }
C2_INLINE c2v c2Mulvs(c2v a, float b) { a.x *= b; a.y *= b; return a; }
C2_INLINE c2v c2Mulvv(c2v a, c2v b) { a.x *= b.x; a.y *= b.y; return a; }
C2_INLINE c2v c2Div(c2v a, float b) { return c2Mulvs(a, 1.0f / b); }
C2_INLINE c2v c2Skew(c2v a) { c2v b; b.x = -a.y; b.y = a.x; return b; }
C2_INLINE c2v c2CCW90(c2v a) { c2v b; b.x = a.y; b.y = -a.x; return b; }
C2_INLINE float c2Det2(c2v a, c2v b) { return a.x * b.y - a.y * b.x; }
C2_INLINE c2v c2Minv(c2v a, c2v b) { return c2V(c2Min(a.x, b.x), c2Min(a.y, b.y)); }
C2_INLINE c2v c2Maxv(c2v a, c2v b) { return c2V(c2Max(a.x, b.x), c2Max(a.y, b.y)); }
C2_INLINE c2v c2Clampv(c2v a, c2v lo, c2v hi) { return c2Maxv(lo, c2Minv(a, hi)); }
C2_INLINE c2v c2Absv(c2v a) { return c2V(c2Abs(a.x), c2Abs(a.y)); }
C2_INLINE float c2Hmin(c2v a) { return c2Min(a.x, a.y); }
C2_INLINE float c2Hmax(c2v a) { return c2Max(a.x, a.y); }
C2_INLINE float c2Len(c2v a) { return c2Sqrt(c2Dot(a, a)); }
C2_INLINE c2v c2Norm(c2v a) { return c2Div(a, c2Len(a)); }
C2_INLINE c2v c2Neg(c2v a) { return c2V(-a.x, -a.y); }
C2_INLINE c2v c2Lerp(c2v a, c2v b, float t) { return c2Add(a, c2Mulvs(c2Sub(b, a), t)); }
C2_INLINE int c2Parallel(c2v a, c2v b, float kTol)
{
float k = c2Len(a) / c2Len(b);
b = c2Mulvs(b, k);
if (c2Abs(a.x - b.x) < kTol && c2Abs(a.y - b.y) < kTol) return 1;
return 0;
}
// rotation ops
C2_INLINE c2r c2Rot(float radians) { c2r r; c2SinCos(radians, &r.s, &r.c); return r; }
C2_INLINE c2r c2RotIdentity() { c2r r; r.c = 1.0f; r.s = 0; return r; }
C2_INLINE c2v c2RotX(c2r r) { return c2V(r.c, r.s); }
C2_INLINE c2v c2RotY(c2r r) { return c2V(-r.s, r.c); }
C2_INLINE c2v c2Mulrv(c2r a, c2v b) { return c2V(a.c * b.x - a.s * b.y, a.s * b.x + a.c * b.y); }
C2_INLINE c2v c2MulrvT(c2r a, c2v b) { return c2V(a.c * b.x + a.s * b.y, -a.s * b.x + a.c * b.y); }
C2_INLINE c2r c2Mulrr(c2r a, c2r b) { c2r c; c.c = a.c * b.c - a.s * b.s; c.s = a.s * b.c + a.c * b.s; return c; }
C2_INLINE c2r c2MulrrT(c2r a, c2r b) { c2r c; c.c = a.c * b.c + a.s * b.s; c.s = a.c * b.s - a.s * b.c; return c; }
C2_INLINE c2v c2Mulmv(c2m a, c2v b) { c2v c; c.x = a.x.x * b.x + a.y.x * b.y; c.y = a.x.y * b.x + a.y.y * b.y; return c; }
C2_INLINE c2v c2MulmvT(c2m a, c2v b) { c2v c; c.x = a.x.x * b.x + a.x.y * b.y; c.y = a.y.x * b.x + a.y.y * b.y; return c; }
C2_INLINE c2m c2Mulmm(c2m a, c2m b) { c2m c; c.x = c2Mulmv(a, b.x); c.y = c2Mulmv(a, b.y); return c; }
C2_INLINE c2m c2MulmmT(c2m a, c2m b) { c2m c; c.x = c2MulmvT(a, b.x); c.y = c2MulmvT(a, b.y); return c; }
// transform ops
C2_INLINE c2x c2xIdentity() { c2x x; x.p = c2V(0, 0); x.r = c2RotIdentity(); return x; }
C2_INLINE c2v c2Mulxv(c2x a, c2v b) { return c2Add(c2Mulrv(a.r, b), a.p); }
C2_INLINE c2v c2MulxvT(c2x a, c2v b) { return c2MulrvT(a.r, c2Sub(b, a.p)); }
C2_INLINE c2x c2Mulxx(c2x a, c2x b) { c2x c; c.r = c2Mulrr(a.r, b.r); c.p = c2Add(c2Mulrv(a.r, b.p), a.p); return c; }
C2_INLINE c2x c2MulxxT(c2x a, c2x b) { c2x c; c.r = c2MulrrT(a.r, b.r); c.p = c2MulrvT(a.r, c2Sub(b.p, a.p)); return c; }
C2_INLINE c2x c2Transform(c2v p, float radians) { c2x x; x.r = c2Rot(radians); x.p = p; return x; }
// halfspace ops
C2_INLINE c2v c2Origin(c2h h) { return c2Mulvs(h.n, h.d); }
C2_INLINE float c2Dist(c2h h, c2v p) { return c2Dot(h.n, p) - h.d; }
C2_INLINE c2v c2Project(c2h h, c2v p) { return c2Sub(p, c2Mulvs(h.n, c2Dist(h, p))); }
C2_INLINE c2h c2Mulxh(c2x a, c2h b) { c2h c; c.n = c2Mulrv(a.r, b.n); c.d = c2Dot(c2Mulxv(a, c2Origin(b)), c.n); return c; }
C2_INLINE c2h c2MulxhT(c2x a, c2h b) { c2h c; c.n = c2MulrvT(a.r, b.n); c.d = c2Dot(c2MulxvT(a, c2Origin(b)), c.n); return c; }
C2_INLINE c2v c2Intersect(c2v a, c2v b, float da, float db) { return c2Add(a, c2Mulvs(c2Sub(b, a), (da / (da - db)))); }
C2_INLINE void c2BBVerts(c2v* out, c2AABB* bb)
{
out[0] = bb->min;
out[1] = c2V(bb->max.x, bb->min.y);
out[2] = bb->max;
out[3] = c2V(bb->min.x, bb->max.y);
}
#define TINYC2_H
#endif
#ifdef TINYC2_IMPLEMENTATION
#ifndef TINYC2_IMPLEMENTATION_ONCE
#define TINYC2_IMPLEMENTATION_ONCE
int c2Collided(const void* A, const c2x* ax, C2_TYPE typeA, const void* B, const c2x* bx, C2_TYPE typeB)
{
switch (typeA)
{
case C2_CIRCLE:
switch (typeB)
{
case C2_CIRCLE: return c2CircletoCircle(*(c2Circle*)A, *(c2Circle*)B);
case C2_AABB: return c2CircletoAABB(*(c2Circle*)A, *(c2AABB*)B);
case C2_CAPSULE: return c2CircletoCapsule(*(c2Circle*)A, *(c2Capsule*)B);
case C2_POLY: return c2CircletoPoly(*(c2Circle*)A, (const c2Poly*)B, bx);
default: return 0;
}
break;
case C2_AABB:
switch (typeB)
{
case C2_CIRCLE: return c2CircletoAABB(*(c2Circle*)B, *(c2AABB*)A);
case C2_AABB: return c2AABBtoAABB(*(c2AABB*)A, *(c2AABB*)B);
case C2_CAPSULE: return c2AABBtoCapsule(*(c2AABB*)A, *(c2Capsule*)B);
case C2_POLY: return c2AABBtoPoly(*(c2AABB*)A, (const c2Poly*)B, bx);
default: return 0;
}
break;
case C2_CAPSULE:
switch (typeB)
{
case C2_CIRCLE: return c2CircletoCapsule(*(c2Circle*)B, *(c2Capsule*)A);
case C2_AABB: return c2AABBtoCapsule(*(c2AABB*)B, *(c2Capsule*)A);
case C2_CAPSULE: return c2CapsuletoCapsule(*(c2Capsule*)A, *(c2Capsule*)B);
case C2_POLY: return c2CapsuletoPoly(*(c2Capsule*)A, (const c2Poly*)B, bx);
default: return 0;
}
break;
case C2_POLY:
switch (typeB)
{
case C2_CIRCLE: return c2CircletoPoly(*(c2Circle*)B, (const c2Poly*)A, ax);
case C2_AABB: return c2AABBtoPoly(*(c2AABB*)B, (const c2Poly*)A, ax);
case C2_CAPSULE: return c2CapsuletoPoly(*(c2Capsule*)B, (const c2Poly*)A, ax);
case C2_POLY: return c2PolytoPoly((const c2Poly*)A, ax, (const c2Poly*)B, bx);
default: return 0;
}
break;
default:
return 0;
}
}
void c2Collide(const void* A, const c2x* ax, C2_TYPE typeA, const void* B, const c2x* bx, C2_TYPE typeB, c2Manifold* m)
{
m->count = 0;
switch (typeA)
{
case C2_CIRCLE:
switch (typeB)
{
case C2_CIRCLE: return c2CircletoCircleManifold(*(c2Circle*)A, *(c2Circle*)B, m);
case C2_AABB: return c2CircletoAABBManifold(*(c2Circle*)A, *(c2AABB*)B, m);
case C2_CAPSULE: return c2CircletoCapsuleManifold(*(c2Circle*)A, *(c2Capsule*)B, m);
case C2_POLY: return c2CircletoPolyManifold(*(c2Circle*)A, (const c2Poly*)B, bx, m);
}
break;
case C2_AABB:
switch (typeB)
{
case C2_CIRCLE: c2CircletoAABBManifold(*(c2Circle*)B, *(c2AABB*)A, m); m->n = c2Neg(m->n); return;
case C2_AABB: return c2AABBtoAABBManifold(*(c2AABB*)A, *(c2AABB*)B, m);
case C2_CAPSULE: return c2AABBtoCapsuleManifold(*(c2AABB*)A, *(c2Capsule*)B, m);
case C2_POLY: return c2AABBtoPolyManifold(*(c2AABB*)A, (const c2Poly*)B, bx, m);
}
break;
case C2_CAPSULE:
switch (typeB)
{
case C2_CIRCLE: c2CircletoCapsuleManifold(*(c2Circle*)B, *(c2Capsule*)A, m); m->n = c2Neg(m->n); return;
case C2_AABB: c2AABBtoCapsuleManifold(*(c2AABB*)B, *(c2Capsule*)A, m); m->n = c2Neg(m->n); return;
case C2_CAPSULE: return c2CapsuletoCapsuleManifold(*(c2Capsule*)A, *(c2Capsule*)B, m);
case C2_POLY: return c2CapsuletoPolyManifold(*(c2Capsule*)A, (const c2Poly*)B, bx, m);
}
break;
case C2_POLY:
switch (typeB)
{
case C2_CIRCLE: c2CircletoPolyManifold(*(c2Circle*)B, (const c2Poly*)A, ax, m); m->n = c2Neg(m->n); return;
case C2_AABB: c2AABBtoPolyManifold(*(c2AABB*)B, (const c2Poly*)A, ax, m); m->n = c2Neg(m->n); return;
case C2_CAPSULE: c2CapsuletoPolyManifold(*(c2Capsule*)B, (const c2Poly*)A, ax, m); m->n = c2Neg(m->n); return;
case C2_POLY: return c2PolytoPolyManifold((const c2Poly*)A, ax, (const c2Poly*)B, bx, m);
}
break;
}
}
int c2CastRay(c2Ray A, const void* B, const c2x* bx, C2_TYPE typeB, c2Raycast* out)
{
switch (typeB)
{
case C2_CIRCLE: return c2RaytoCircle(A, *(c2Circle*)B, out);
case C2_AABB: return c2RaytoAABB(A, *(c2AABB*)B, out);
case C2_CAPSULE: return c2RaytoCapsule(A, *(c2Capsule*)B, out);
case C2_POLY: return c2RaytoPoly(A, (const c2Poly*)B, bx, out);
}
return 0;
}
#define C2_GJK_ITERS 20
typedef struct
{
float radius;
int count;
c2v verts[C2_MAX_POLYGON_VERTS];
} c2Proxy;
typedef struct
{
c2v sA;
c2v sB;
c2v p;
float u;
int iA;
int iB;
} c2sv;
typedef struct
{
c2sv a, b, c, d;
float div;
int count;
} c2Simplex;
static C2_INLINE void c2MakeProxy(const void* shape, C2_TYPE type, c2Proxy* p)
{
switch (type)
{
case C2_CIRCLE:
{
c2Circle* c = (c2Circle*)shape;
p->radius = c->r;
p->count = 1;
p->verts[0] = c->p;
} break;
case C2_AABB:
{
c2AABB* bb = (c2AABB*)shape;
p->radius = 0;
p->count = 4;
c2BBVerts(p->verts, bb);
} break;
case C2_CAPSULE:
{
c2Capsule* c = (c2Capsule*)shape;
p->radius = c->r;
p->count = 2;
p->verts[0] = c->a;
p->verts[1] = c->b;
} break;
case C2_POLY:
{
c2Poly* poly = (c2Poly*)shape;
p->radius = 0;
p->count = poly->count;
for (int i = 0; i < p->count; ++i) p->verts[i] = poly->verts[i];
} break;
}
}
static C2_INLINE int c2Support(const c2v* verts, int count, c2v d)
{
int imax = 0;
float dmax = c2Dot(verts[0], d);
for (int i = 1; i < count; ++i)
{
float dot = c2Dot(verts[i], d);
if (dot > dmax)
{
imax = i;
dmax = dot;
}
}
return imax;
}
#define C2_BARY(n, x) c2Mulvs(s->n.x, (den * s->n.u))
#define C2_BARY2(x) c2Add(C2_BARY(a, x), C2_BARY(b, x))
#define C2_BARY3(x) c2Add(c2Add(C2_BARY(a, x), C2_BARY(b, x)), C2_BARY(c, x))
static C2_INLINE c2v c2L(c2Simplex* s)
{
float den = 1.0f / s->div;
switch (s->count)
{
case 1: return s->a.p;
case 2: return C2_BARY2(p);
case 3: return C2_BARY3(p);
default: return c2V(0, 0);
}
}
static C2_INLINE void c2Witness(c2Simplex* s, c2v* a, c2v* b)
{
float den = 1.0f / s->div;
switch (s->count)
{
case 1: *a = s->a.sA; *b = s->a.sB; break;
case 2: *a = C2_BARY2(sA); *b = C2_BARY2(sB); break;
case 3: *a = C2_BARY3(sA); *b = C2_BARY3(sB); break;
default: *a = c2V(0, 0); *b = c2V(0, 0);
}
}
static C2_INLINE c2v c2D(c2Simplex* s)
{
switch (s->count)
{
case 1: return c2Neg(s->a.p);
case 2:
{
c2v ab = c2Sub(s->b.p, s->a.p);
if (c2Det2(ab, c2Neg(s->a.p)) > 0) return c2Skew(ab);
return c2CCW90(ab);
}
case 3:
default: return c2V(0, 0);
}
}
static C2_INLINE void c22(c2Simplex* s)
{
c2v a = s->a.p;
c2v b = s->b.p;
float u = c2Dot(b, c2Norm(c2Sub(b, a)));
float v = c2Dot(a, c2Norm(c2Sub(a, b)));
if (v <= 0)
{
s->a.u = 1.0f;
s->div = 1.0f;
s->count = 1;
}
else if (u <= 0)
{
s->a = s->b;
s->a.u = 1.0f;
s->div = 1.0f;
s->count = 1;
}
else
{
s->a.u = u;
s->b.u = v;
s->div = u + v;
s->count = 2;
}
}
static C2_INLINE void c23(c2Simplex* s)
{
c2v a = s->a.p;
c2v b = s->b.p;
c2v c = s->c.p;
float uAB = c2Dot(b, c2Norm(c2Sub(b, a)));
float vAB = c2Dot(a, c2Norm(c2Sub(a, b)));
float uBC = c2Dot(c, c2Norm(c2Sub(c, b)));
float vBC = c2Dot(b, c2Norm(c2Sub(b, c)));
float uCA = c2Dot(a, c2Norm(c2Sub(a, c)));
float vCA = c2Dot(c, c2Norm(c2Sub(c, a)));
float area = c2Det2(c2Norm(c2Sub(b, a)), c2Norm(c2Sub(c, a)));
float uABC = c2Det2(b, c) * area;
float vABC = c2Det2(c, a) * area;
float wABC = c2Det2(a, b) * area;
if (vAB <= 0 && uCA <= 0)
{
s->a.u = 1.0f;
s->div = 1.0f;
s->count = 1;
}
else if (uAB <= 0 && vBC <= 0)
{
s->a = s->b;
s->a.u = 1.0f;
s->div = 1.0f;
s->count = 1;
}
else if (uBC <= 0 && vCA <= 0)
{
s->a = s->c;
s->a.u = 1.0f;
s->div = 1.0f;
s->count = 1;
}
else if (uAB > 0 && vAB > 0 && wABC <= 0)
{
s->a.u = uAB;
s->b.u = vAB;
s->div = uAB + vAB;
s->count = 2;
}
else if (uBC > 0 && vBC > 0 && uABC <= 0)
{
s->a = s->b;
s->b = s->c;
s->a.u = uBC;
s->b.u = vBC;
s->div = uBC + vBC;
s->count = 2;
}
else if (uCA > 0 && vCA > 0 && vABC <= 0)
{
s->b = s->a;
s->a = s->c;
s->a.u = uCA;
s->b.u = vCA;
s->div = uCA + vCA;
s->count = 2;
}
else
{
s->a.u = uABC;
s->b.u = vABC;
s->c.u = wABC;
s->div = uABC + vABC + wABC;
s->count = 3;
}
}
#include <float.h>
// Please see http://box2d.org/downloads/ under GDC 2010 for Erin's demo code
// and PDF slides for documentation on the GJK algorithm.
float c2GJK(const void* A, C2_TYPE typeA, const c2x* ax_ptr, const void* B, C2_TYPE typeB, const c2x* bx_ptr, c2v* outA, c2v* outB, int use_radius)
{
c2x ax;
c2x bx;
if (typeA != C2_POLY || !ax_ptr) ax = c2xIdentity();
else ax = *ax_ptr;
if (typeB != C2_POLY || !bx_ptr) bx = c2xIdentity();
else bx = *bx_ptr;
c2Proxy pA;
c2Proxy pB;
c2MakeProxy(A, typeA, &pA);
c2MakeProxy(B, typeB, &pB);
c2Simplex s;
s.a.iA = 0;
s.a.iB = 0;
s.a.sA = c2Mulxv(ax, pA.verts[0]);
s.a.sB = c2Mulxv(bx, pB.verts[0]);
s.a.p = c2Sub(s.a.sB, s.a.sA);
s.a.u = 1.0f;
s.count = 1;
c2sv* verts = &s.a;
int saveA[3], saveB[3];
int save_count = 0;
float d0 = FLT_MAX;
float d1 = FLT_MAX;
int iter = 0;
int hit = 0;
while (iter < C2_GJK_ITERS)
{
save_count = s.count;
for (int i = 0; i < save_count; ++i)
{
saveA[i] = verts[i].iA;
saveB[i] = verts[i].iB;
}
switch (s.count)
{
case 1: break;
case 2: c22(&s); break;
case 3: c23(&s); break;
}
if (s.count == 3)
{
hit = 1;
break;
}
c2v p = c2L(&s);
d1 = c2Dot(p, p);
if (d1 > d0) break;
d0 = d1;
c2v d = c2D(&s);
if (c2Dot(d, d) < FLT_EPSILON * FLT_EPSILON) break;
int iA = c2Support(pA.verts, pA.count, c2MulrvT(ax.r, c2Neg(d)));
c2v sA = c2Mulxv(ax, pA.verts[iA]);
int iB = c2Support(pB.verts, pB.count, c2MulrvT(bx.r, d));
c2v sB = c2Mulxv(bx, pB.verts[iB]);
++iter;
int dup = 0;
for (int i = 0; i < save_count; ++i)
{
if (iA == saveA[i] && iB == saveB[i])
{
dup = 1;
break;
}
}
if (dup) break;
c2sv* v = verts + s.count;
v->iA = iA;
v->sA = sA;
v->iB = iB;
v->sB = sB;
v->p = c2Sub(v->sB, v->sA);
++s.count;
}
c2v a, b;
c2Witness(&s, &a, &b);
float dist = c2Len(c2Sub(a, b));
if (hit)
{
a = b;
dist = 0;
}
else if (use_radius)
{
float rA = pA.radius;
float rB = pB.radius;
if (dist > rA + rB && dist > FLT_EPSILON)
{
dist -= rA + rB;
c2v n = c2Norm(c2Sub(b, a));
a = c2Add(a, c2Mulvs(n, rA));
b = c2Sub(b, c2Mulvs(n, rB));
}
else
{
c2v p = c2Mulvs(c2Add(a, b), 0.5f);
a = p;
b = p;
dist = 0;
}
}
if (outA) *outA = a;
if (outB) *outB = b;
return dist;
}
int c2Hull(c2v* verts, int count)
{
if (count <= 2) return 0;
count = c2Min(C2_MAX_POLYGON_VERTS, count);
int right = 0;
float xmax = verts[0].x;
for (int i = 1; i < count; ++i)
{
float x = verts[i].x;
if (x > xmax)
{
xmax = x;
right = i;
}
else if (x == xmax)
if (verts[i].y < verts[right].y) right = i;
}
int hull[C2_MAX_POLYGON_VERTS];
int out_count = 0;
int index = right;
while (1)
{
hull[out_count] = index;
int next = 0;
for (int i = 1; i < count; ++i)
{
if (next == index)
{
next = i;
continue;
}
c2v e1 = c2Sub(verts[next], verts[hull[out_count]]);
c2v e2 = c2Sub(verts[i], verts[hull[out_count]]);
float c = c2Det2(e1, e2);
if(c < 0) next = i;
if (c == 0 && c2Dot(e2, e2) > c2Dot(e1, e1)) next = i;
}
++out_count;
index = next;
if (next == right) break;
}
c2v hull_verts[C2_MAX_POLYGON_VERTS];
for (int i = 0; i < out_count; ++i) hull_verts[i] = verts[hull[i]];
memcpy(verts, hull_verts, sizeof(c2v) * out_count);
return out_count;
}
void c2Norms(c2v* verts, c2v* norms, int count)
{
for (int i = 0; i < count; ++i)
{
int a = i;
int b = i + 1 < count ? i + 1 : 0;
c2v e = c2Sub(verts[b], verts[a]);
norms[i] = c2Norm(c2CCW90(e));
}
}
void c2MakePoly(c2Poly* p)
{
p->count = c2Hull(p->verts, p->count);
c2Norms(p->verts, p->norms, p->count);
}
int c2CircletoCircle(c2Circle A, c2Circle B)
{
c2v c = c2Sub(B.p, A.p);
float d2 = c2Dot(c, c);
float r2 = A.r + B.r;
r2 = r2 * r2;
return d2 < r2;
}
int c2CircletoAABB(c2Circle A, c2AABB B)
{
c2v L = c2Clampv(A.p, B.min, B.max);
c2v ab = c2Sub(A.p, L);
float d2 = c2Dot(ab, ab);
float r2 = A.r * A.r;
return d2 < r2;
}
int c2AABBtoAABB(c2AABB A, c2AABB B)
{
int d0 = B.max.x < A.min.x;
int d1 = A.max.x < B.min.x;
int d2 = B.max.y < A.min.y;
int d3 = A.max.y < B.min.y;
return !(d0 | d1 | d2 | d3);
}
// see: http://www.randygaul.net/2014/07/23/distance-point-to-line-segment/
int c2CircletoCapsule(c2Circle A, c2Capsule B)
{
c2v n = c2Sub(B.b, B.a);
c2v ap = c2Sub(A.p, B.a);