sbylib.collision.broad.aabbset source code

1 module sbylib.collision.broad.aabbset;
2 
3 import sbylib.collision.bounds.aabb;
4 import sbylib.collision.shape.shape;
5 import sbylib.collision.narrow.detect : CollisionResult;
6 import std.typecons : Nullable;
7 import std.variant : Algebraic, visit;
8 
9 class AABBSet {
10 
11     auto collisionDetected(MyType : CollisionShape, YourType : CollisionShape)(YourType shape) {
12         return CollisionDetectNotification!(MyType, YourType)(this, shape);
13     }
14 
15     private alias Tree = Algebraic!(Node, Leaf);
16     private AABB visitAABB(Tree tree) {
17         return tree.visit!(
18                 (Node node) => node.getAABB(),
19                 (Leaf leaf) => leaf.getAABB());
20     }
21 
22     private Tree root; 
23     private this(ShapePair[] shapeList) {
24         this.root = buildTree(shapeList);
25     }
26 
27     private Tree buildTree(ShapePair[] shapeList) 
28         in (shapeList.length > 0)
29     {
30         import std.algorithm : map, reduce, sort, minElement, maxElement;
31         import std.array : array;
32         import std.typecons : tuple;
33         import std.range : enumerate;
34         import sbylib.math : mostDispersionBasis, dot, vec3;
35 
36         if (shapeList.length is 1)
37             return Tree(new Leaf(shapeList[0]));
38 
39         auto shapeAABBList = shapeList.map!(s => tuple(s, s.getAABB())).array;
40         auto centerList = shapeAABBList.map!(s => s[1].center).array;
41         auto basisList = mostDispersionBasis(centerList);
42         auto lengthList = basisList.array.map!(basis =>
43                 centerList.map!(c => dot(c, basis)).maxElement
44               - centerList.map!(c => dot(c, basis)).minElement).array;
45         vec3 basis = basisList[lengthList.enumerate.reduce!((a,b) => a.value > b.value ? a : b).index];
46         shapeList = shapeAABBList
47             .sort!((a,b) => dot(a[1].center, basis) < dot(b[1].center, basis))
48             .map!(s => s[0])
49             .array;
50         return Tree(new Node([buildTree(shapeList[0..$/2]), buildTree(shapeList[$/2..$])]));
51     }
52 
53     void detect
54         (MyType : CollisionShape, YourType : CollisionShape)
55         (YourType shape, CollisionDetectCallback!(MyType, YourType) callback) 
56     {
57         root.visit!(
58             (Node node) => node.detect!(MyType, YourType)(shape, callback),
59             (Leaf leaf) => leaf.detect!(MyType, YourType)(shape, callback));
60     }
61 
62     private alias CollisionDetectCallback(MyType, YourType)
63         = void delegate(MyType, YourType, CollisionResult!(MyType, YourType));
64 
65     private struct ShapePair {
66         import std.variant : Variant;
67 
68         CollisionShape shape;
69         Variant variant;
70         alias shape this;
71 
72         this(Shape : CollisionShape)(Shape shape) {
73             this.shape = shape;
74             this.variant = shape;
75         }
76     }
77 
78     struct Builder {
79         ShapePair[] shapeList;
80 
81         void add(Shape : CollisionShape)(Shape shape) {
82             this.shapeList ~= ShapePair(shape); 
83         }
84 
85         auto build() {
86             return new AABBSet(shapeList);
87         }
88     }
89 
90     private class Node {
91         Tree[2] children;
92         Nullable!AABB aabb;
93         this(Tree[2] children) { this.children = children; }
94         AABB getAABB() { 
95             if(aabb.isNull)
96                 aabb = AABB.unite(visitAABB(children[0]), visitAABB(children[1])); 
97             return aabb.get();
98         }
99         
100         void detect(MyType : CollisionShape, YourType : CollisionShape)
101             (YourType shape, CollisionDetectCallback!(MyType, YourType) callback) {
102             if (intersect(this.getAABB(), shape.getAABB()) is false) return;
103             static foreach (i; 0..2) {
104                 children[i].visit!(
105                     (Node node) => node.detect!(MyType, YourType)(shape, callback),
106                     (Leaf leaf) => leaf.detect!(MyType, YourType)(shape, callback));
107             }
108         }
109     }
110 
111     private class Leaf {
112         ShapePair shape;
113         this(ShapePair shape) { this.shape = shape; }
114         AABB getAABB() { return shape.getAABB(); }
115 
116         void detect(MyType : CollisionShape, YourType : CollisionShape)
117             (YourType shape, CollisionDetectCallback!(MyType, YourType) callback) {
118             import sbylib.collision.narrow : detect;
119 
120             if (this.shape is shape) return;
121             if (intersect(this.getAABB(), shape.getAABB()) is false) return;
122 
123             if (auto s1 = this.shape.variant.peek!MyType) {
124                 auto info = detect(*s1, shape);
125                 if (info.isNull) return;
126                 callback(*s1, shape, info.get());
127             }
128         }
129     }
130 }
131 
132 private struct CollisionDetectNotification(MyType : CollisionShape, YourType : CollisionShape) {
133     AABBSet set;
134     YourType shape;
135 }
136 
137 auto when(MyType : CollisionShape, YourType : CollisionShape)(CollisionDetectNotification!(MyType, YourType) notification) {
138     import sbylib.graphics : Event, when, Frame, then, until;
139     import std.meta : AliasSeq;
140 
141     alias Args = AliasSeq!(MyType, YourType, CollisionResult!(MyType, YourType));
142 
143     auto result = new Event!(Args);
144 
145     when(Frame).then({
146         notification.set.detect!(MyType, YourType)(notification.shape, (Args args) => result.fire(args));
147     });
148     return result;
149 }