1 /*
2  * Copyright (c) 2007-2013 Scott Lembcke and Howling Moon Software
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20  * SOFTWARE.
21  */
22 module dchip.cpShape;
23 
24 import std..string;
25 
26 import dchip.cpBB;
27 import dchip.cpBody;
28 import dchip.chipmunk;
29 import dchip.chipmunk_private;
30 import dchip.chipmunk_types;
31 import dchip.cpSpace;
32 import dchip.util;
33 import dchip.cpVect;
34 
35 /// The cpShape struct defines the shape of a rigid body_.
36 
37 /// Nearest point query info struct.
38 struct cpNearestPointQueryInfo
39 {
40     /// The nearest shape, null if no shape was within range.
41     cpShape* shape;
42 
43     /// The closest point on the shape's surface. (in world space coordinates)
44     cpVect p;
45 
46     /// The distance to the point. The distance is negative if the point is inside the shape.
47     cpFloat d = 0;
48 
49     /// The gradient of the signed distance function.
50     /// The same as info.p/info.d, but accurate even for very small values of info.d.
51     cpVect g;
52 }
53 
54 /// Segment query info struct.
55 struct cpSegmentQueryInfo
56 {
57     /// The shape that was hit, null if no collision occured.
58     cpShape* shape;
59 
60     /// The normalized distance along the query segment in the range [0, 1].
61     cpFloat t = 0;
62 
63     /// The normal of the surface hit.
64     cpVect n;
65 }
66 
67 /// @private
68 enum cpShapeType
69 {
70     CP_CIRCLE_SHAPE,
71     CP_SEGMENT_SHAPE,
72     CP_POLY_SHAPE,
73     CP_NUM_SHAPES
74 }
75 
76 ///
77 mixin _ExportEnumMembers!cpShapeType;
78 
79 alias cpShapeCacheDataImpl = cpBB function(cpShape* shape, cpVect p, cpVect rot);
80 alias cpShapeDestroyImpl = void function(cpShape* shape);
81 alias cpShapeNearestPointQueryImpl = void function(cpShape* shape, cpVect p, cpNearestPointQueryInfo* info);
82 alias cpShapeSegmentQueryImpl = void function(cpShape* shape, cpVect a, cpVect b, cpSegmentQueryInfo* info);
83 
84 /// @private
85 struct cpShapeClass
86 {
87     cpShapeType type;
88 
89     cpShapeCacheDataImpl cacheData;
90     cpShapeDestroyImpl destroy;
91     cpShapeNearestPointQueryImpl nearestPointQuery;
92     cpShapeSegmentQueryImpl segmentQuery;
93 }
94 
95 /// Opaque collision shape struct.
96 struct cpShape
97 {
98     version (CHIP_ALLOW_PRIVATE_ACCESS)
99         /* const */ cpShapeClass * klass;
100     else
101         package /* const */ cpShapeClass * klass;
102 
103     /// The rigid body_ this collision shape is attached to.
104     cpBody* body_;
105 
106     /// The current bounding box of the shape.
107     cpBB bb;
108 
109     /// Sensor flag.
110     /// Sensor shapes call collision callbacks but don't produce collisions.
111     cpBool sensor;
112 
113     /// Coefficient of restitution. (elasticity)
114     cpFloat e = 0;
115 
116     /// Coefficient of friction.
117     cpFloat u = 0;
118 
119     /// Surface velocity used when solving for friction.
120     cpVect surface_v;
121 
122     /// User definable data pointer.
123     /// Generally this points to your the game object class so you can access it
124     /// when given a cpShape reference in a callback.
125     cpDataPointer data;
126 
127     /// Collision type of this shape used when picking collision handlers.
128     cpCollisionType collision_type;
129 
130     /// Group of this shape. Shapes in the same group don't collide.
131     cpGroup group;
132 
133     // Layer bitmask for this shape. Shapes only collide if the bitwise and of their layers is non-zero.
134     cpLayers layers;
135 
136     version (CHIP_ALLOW_PRIVATE_ACCESS)
137         cpSpace * space;
138     else
139         package cpSpace * space;
140 
141     version (CHIP_ALLOW_PRIVATE_ACCESS)
142         cpShape * next;
143     else
144         package cpShape * next;
145 
146     version (CHIP_ALLOW_PRIVATE_ACCESS)
147         cpShape * prev;
148     else
149         package cpShape * prev;
150 
151     version (CHIP_ALLOW_PRIVATE_ACCESS)
152         cpHashValue hashid;
153     else
154         package cpHashValue hashid;
155 }
156 
157 /// Get the hit point for a segment query.
158 cpVect cpSegmentQueryHitPoint(const cpVect start, const cpVect end, const cpSegmentQueryInfo info)
159 {
160     return cpvlerp(start, end, info.t);
161 }
162 
163 /// Get the hit distance for a segment query.
164 cpFloat cpSegmentQueryHitDist(const cpVect start, const cpVect end, const cpSegmentQueryInfo info)
165 {
166     return cpvdist(start, end) * info.t;
167 }
168 
169 mixin template CP_DefineShapeStructGetter(type, string member, string name)
170 {
171     mixin(q{
172         type cpShapeGet%s(const cpShape * shape) { return cast(typeof(return))shape.%s; }
173     }.format(name, member));
174 }
175 
176 mixin template CP_DefineShapeStructSetter(type, string member, string name, bool activates)
177 {
178     mixin(q{
179         void cpShapeSet%s(cpShape * shape, type value)
180         {
181             %s
182 
183             shape.%s = value;
184         }
185     }.format(name, activates ? "if (shape.body_) cpBodyActivate(shape.body_);" : "", member));
186 }
187 
188 mixin template CP_DefineShapeStructProperty(type, string member, string name, bool activates)
189 {
190     mixin CP_DefineShapeStructGetter!(type, member, name);
191     mixin CP_DefineShapeStructSetter!(type, member, name, activates);
192 }
193 
194 mixin CP_DefineShapeStructGetter!(cpSpace*, "space", "Space");
195 
196 mixin CP_DefineShapeStructGetter!(cpBody*, "body_", "Body");
197 
198 mixin CP_DefineShapeStructGetter!(cpBB, "bb", "BB");
199 mixin CP_DefineShapeStructProperty!(cpBool, "sensor", "Sensor", cpTrue);
200 mixin CP_DefineShapeStructProperty!(cpFloat, "e", "Elasticity", cpFalse);
201 mixin CP_DefineShapeStructProperty!(cpFloat, "u", "Friction", cpTrue);
202 mixin CP_DefineShapeStructProperty!(cpVect, "surface_v", "SurfaceVelocity", cpTrue);
203 mixin CP_DefineShapeStructProperty!(cpDataPointer, "data", "UserData", cpFalse);
204 mixin CP_DefineShapeStructProperty!(cpCollisionType, "collision_type", "CollisionType", cpTrue);
205 mixin CP_DefineShapeStructProperty!(cpGroup, "group", "Group", cpTrue);
206 mixin CP_DefineShapeStructProperty!(cpLayers, "layers", "Layers", cpTrue);
207 
208 mixin template CP_DeclareShapeGetter(type, string struct_, string member, string name)
209 {
210     mixin(q{
211         type %sGet%s(const cpShape * shape)
212     }.format(struct_, name, member));
213 }
214 
215 /// @private
216 struct cpCircleShape
217 {
218     cpShape shape;
219 
220     cpVect c, tc;
221     cpFloat r = 0;
222 }
223 
224 /// @private
225 struct cpSegmentShape
226 {
227     cpShape shape;
228 
229     cpVect a, b, n;
230     cpVect ta, tb, tn;
231     cpFloat r = 0;
232 
233     cpVect a_tangent, b_tangent;
234 }
235 
236 __gshared cpHashValue cpShapeIDCounter = 0;
237 
238 void cpResetShapeIdCounter()
239 {
240     cpShapeIDCounter = 0;
241 }
242 
243 cpShape* cpShapeInit(cpShape* shape, const cpShapeClass* klass, cpBody* body_)
244 {
245     shape.klass = cast(typeof(shape.klass))klass;
246 
247     shape.hashid = cpShapeIDCounter;
248     cpShapeIDCounter++;
249 
250     shape.body_   = body_;
251     shape.sensor = 0;
252 
253     shape.e         = 0.0f;
254     shape.u         = 0.0f;
255     shape.surface_v = cpvzero;
256 
257     shape.collision_type = 0;
258     shape.group  = CP_NO_GROUP;
259     shape.layers = CP_ALL_LAYERS;
260 
261     shape.data = null;
262 
263     shape.space = null;
264 
265     shape.next = null;
266     shape.prev = null;
267 
268     return shape;
269 }
270 
271 void cpShapeDestroy(cpShape* shape)
272 {
273     if (shape.klass && shape.klass.destroy)
274         shape.klass.destroy(shape);
275 }
276 
277 void cpShapeFree(cpShape* shape)
278 {
279     if (shape)
280     {
281         cpShapeDestroy(shape);
282         cpfree(shape);
283     }
284 }
285 
286 void cpShapeSetBody(cpShape* shape, cpBody* body_)
287 {
288     cpAssertHard(!cpShapeActive(shape), "You cannot change the body_ on an active shape. You must remove the shape from the space before changing the body_.");
289     shape.body_ = body_;
290 }
291 
292 cpBB cpShapeCacheBB(cpShape* shape)
293 {
294     cpBody* body_ = shape.body_;
295     return cpShapeUpdate(shape, body_.p, body_.rot);
296 }
297 
298 cpBB cpShapeUpdate(cpShape* shape, cpVect pos, cpVect rot)
299 {
300     return (shape.bb = shape.klass.cacheData(shape, pos, rot));
301 }
302 
303 cpBool cpShapePointQuery(cpShape* shape, cpVect p)
304 {
305     cpNearestPointQueryInfo info = { null, cpvzero, INFINITY, cpvzero };
306     cpShapeNearestPointQuery(shape, p, &info);
307 
308     return (info.d < 0.0f);
309 }
310 
311 cpFloat cpShapeNearestPointQuery(cpShape* shape, cpVect p, cpNearestPointQueryInfo* info)
312 {
313     cpNearestPointQueryInfo blank = { null, cpvzero, INFINITY, cpvzero };
314 
315     if (info)
316     {
317         (*info) = blank;
318     }
319     else
320     {
321         info = &blank;
322     }
323 
324     shape.klass.nearestPointQuery(shape, p, info);
325     return info.d;
326 }
327 
328 cpBool cpShapeSegmentQuery(cpShape* shape, cpVect a, cpVect b, cpSegmentQueryInfo* info)
329 {
330     cpSegmentQueryInfo blank = { null, 1.0f, cpvzero };
331 
332     if (info)
333     {
334         (*info) = blank;
335     }
336     else
337     {
338         info = &blank;
339     }
340 
341     cpNearestPointQueryInfo nearest;
342     shape.klass.nearestPointQuery(shape, a, &nearest);
343 
344     if (nearest.d <= 0.0)
345     {
346         info.shape = shape;
347         info.t     = 0.0;
348         info.n     = cpvnormalize(cpvsub(a, nearest.p));
349     }
350     else
351     {
352         shape.klass.segmentQuery(shape, a, b, info);
353     }
354 
355     return (info.shape != null);
356 }
357 
358 cpCircleShape* cpCircleShapeAlloc()
359 {
360     return cast(cpCircleShape*)cpcalloc(1, cpCircleShape.sizeof);
361 }
362 
363 cpBB cpCircleShapeCacheData(cpCircleShape* circle, cpVect p, cpVect rot)
364 {
365     cpVect c = circle.tc = cpvadd(p, cpvrotate(circle.c, rot));
366     return cpBBNewForCircle(c, circle.r);
367 }
368 
369 void cpCicleShapeNearestPointQuery(cpCircleShape* circle, cpVect p, cpNearestPointQueryInfo* info)
370 {
371     cpVect  delta = cpvsub(p, circle.tc);
372     cpFloat d     = cpvlength(delta);
373     cpFloat r     = circle.r;
374 
375     info.shape = cast(cpShape*)circle;
376     info.p     = cpvadd(circle.tc, cpvmult(delta, r / d)); // TODO div/0
377     info.d     = d - r;
378 
379     // Use up for the gradient if the distance is very small.
380     info.g = (d > MAGIC_EPSILON ? cpvmult(delta, 1.0f / d) : cpv(0.0f, 1.0f));
381 }
382 
383 void cpCircleShapeSegmentQuery(cpCircleShape* circle, cpVect a, cpVect b, cpSegmentQueryInfo* info)
384 {
385     CircleSegmentQuery(cast(cpShape*)circle, circle.tc, circle.r, a, b, info);
386 }
387 
388 cpCircleShape* cpCircleShapeInit(cpCircleShape* circle, cpBody* body_, cpFloat radius, cpVect offset)
389 {
390     circle.c = offset;
391     circle.r = radius;
392 
393     cpShapeInit(cast(cpShape*)circle, &cpCircleShapeClass, body_);
394 
395     return circle;
396 }
397 
398 cpShape* cpCircleShapeNew(cpBody* body_, cpFloat radius, cpVect offset)
399 {
400     return cast(cpShape*)cpCircleShapeInit(cpCircleShapeAlloc(), body_, radius, offset);
401 }
402 
403 cpSegmentShape *
404 cpSegmentShapeAlloc()
405 {
406     return cast(cpSegmentShape*)cpcalloc(1, cpSegmentShape.sizeof);
407 }
408 
409 cpBB cpSegmentShapeCacheData(cpSegmentShape* seg, cpVect p, cpVect rot)
410 {
411     seg.ta = cpvadd(p, cpvrotate(seg.a, rot));
412     seg.tb = cpvadd(p, cpvrotate(seg.b, rot));
413     seg.tn = cpvrotate(seg.n, rot);
414 
415     cpFloat l = 0, r = 0, b = 0, t = 0;
416 
417     if (seg.ta.x < seg.tb.x)
418     {
419         l = seg.ta.x;
420         r = seg.tb.x;
421     }
422     else
423     {
424         l = seg.tb.x;
425         r = seg.ta.x;
426     }
427 
428     if (seg.ta.y < seg.tb.y)
429     {
430         b = seg.ta.y;
431         t = seg.tb.y;
432     }
433     else
434     {
435         b = seg.tb.y;
436         t = seg.ta.y;
437     }
438 
439     cpFloat rad = seg.r;
440     return cpBBNew(l - rad, b - rad, r + rad, t + rad);
441 }
442 
443 void cpSegmentShapeNearestPointQuery(cpSegmentShape* seg, cpVect p, cpNearestPointQueryInfo* info)
444 {
445     cpVect closest = cpClosetPointOnSegment(p, seg.ta, seg.tb);
446 
447     cpVect  delta = cpvsub(p, closest);
448     cpFloat d     = cpvlength(delta);
449     cpFloat r     = seg.r;
450     cpVect  g     = cpvmult(delta, 1.0f / d);
451 
452     info.shape = cast(cpShape*)seg;
453     info.p     = (d ? cpvadd(closest, cpvmult(g, r)) : closest);
454     info.d     = d - r;
455 
456     // Use the segment's normal if the distance is very small.
457     info.g = (d > MAGIC_EPSILON ? g : seg.n);
458 }
459 
460 void cpSegmentShapeSegmentQuery(cpSegmentShape* seg, cpVect a, cpVect b, cpSegmentQueryInfo* info)
461 {
462     cpVect  n = seg.tn;
463     cpFloat d = cpvdot(cpvsub(seg.ta, a), n);
464     cpFloat r = seg.r;
465 
466     cpVect flipped_n  = (d > 0.0f ? cpvneg(n) : n);
467     cpVect seg_offset = cpvsub(cpvmult(flipped_n, r), a);
468 
469     // Make the endpoints relative to 'a' and move them by the thickness of the segment.
470     cpVect seg_a = cpvadd(seg.ta, seg_offset);
471     cpVect seg_b = cpvadd(seg.tb, seg_offset);
472     cpVect delta = cpvsub(b, a);
473 
474     if (cpvcross(delta, seg_a) * cpvcross(delta, seg_b) <= 0.0f)
475     {
476         cpFloat d_offset = d + (d > 0.0f ? -r : r);
477         cpFloat ad       = -d_offset;
478         cpFloat bd       = cpvdot(delta, n) - d_offset;
479 
480         if (ad * bd < 0.0f)
481         {
482             info.shape = cast(cpShape*)seg;
483             info.t     = ad / (ad - bd);
484             info.n     = flipped_n;
485         }
486     }
487     else if (r != 0.0f)
488     {
489         cpSegmentQueryInfo info1 = { null, 1.0f, cpvzero };
490         cpSegmentQueryInfo info2 = { null, 1.0f, cpvzero };
491         CircleSegmentQuery(cast(cpShape*)seg, seg.ta, seg.r, a, b, &info1);
492         CircleSegmentQuery(cast(cpShape*)seg, seg.tb, seg.r, a, b, &info2);
493 
494         if (info1.t < info2.t)
495         {
496             (*info) = info1;
497         }
498         else
499         {
500             (*info) = info2;
501         }
502     }
503 }
504 
505 __gshared cpShapeClass cpSegmentShapeClass;
506 __gshared cpShapeClass cpCircleShapeClass;
507 
508 void _initModuleCtor_cpShape()
509 {
510     cpSegmentShapeClass = cpShapeClass(
511         CP_SEGMENT_SHAPE,
512         cast(cpShapeCacheDataImpl)&cpSegmentShapeCacheData,
513         null,
514         cast(cpShapeNearestPointQueryImpl)&cpSegmentShapeNearestPointQuery,
515         cast(cpShapeSegmentQueryImpl)&cpSegmentShapeSegmentQuery,
516     );
517 
518     cpCircleShapeClass = cpShapeClass(
519         CP_CIRCLE_SHAPE,
520         cast(cpShapeCacheDataImpl)&cpCircleShapeCacheData,
521         null,
522         cast(cpShapeNearestPointQueryImpl)&cpCicleShapeNearestPointQuery,
523         cast(cpShapeSegmentQueryImpl)&cpCircleShapeSegmentQuery,
524     );
525 }
526 
527 cpSegmentShape* cpSegmentShapeInit(cpSegmentShape* seg, cpBody* body_, cpVect a, cpVect b, cpFloat r)
528 {
529     seg.a = a;
530     seg.b = b;
531     seg.n = cpvperp(cpvnormalize(cpvsub(b, a)));
532 
533     seg.r = r;
534 
535     seg.a_tangent = cpvzero;
536     seg.b_tangent = cpvzero;
537 
538     cpShapeInit(cast(cpShape*)seg, &cpSegmentShapeClass, body_);
539 
540     return seg;
541 }
542 
543 cpShape* cpSegmentShapeNew(cpBody* body_, cpVect a, cpVect b, cpFloat r)
544 {
545     return cast(cpShape*)cpSegmentShapeInit(cpSegmentShapeAlloc(), body_, a, b, r);
546 }
547 
548 void cpSegmentShapeSetNeighbors(cpShape* shape, cpVect prev, cpVect next)
549 {
550     cpAssertHard(shape.klass == &cpSegmentShapeClass, "Shape is not a segment shape.");
551     cpSegmentShape* seg = cast(cpSegmentShape*)shape;
552 
553     seg.a_tangent = cpvsub(prev, seg.a);
554     seg.b_tangent = cpvsub(next, seg.b);
555 }
556 
557 // Unsafe API (chipmunk_unsafe.h)
558 
559 void cpCircleShapeSetRadius(cpShape* shape, cpFloat radius)
560 {
561     cpAssertHard(shape.klass == &cpCircleShapeClass, "Shape is not a circle shape.");
562     cpCircleShape* circle = cast(cpCircleShape*)shape;
563 
564     circle.r = radius;
565 }
566 
567 void cpCircleShapeSetOffset(cpShape* shape, cpVect offset)
568 {
569     cpAssertHard(shape.klass == &cpCircleShapeClass, "Shape is not a circle shape.");
570     cpCircleShape* circle = cast(cpCircleShape*)shape;
571 
572     circle.c = offset;
573 }
574 
575 void cpSegmentShapeSetEndpoints(cpShape* shape, cpVect a, cpVect b)
576 {
577     cpAssertHard(shape.klass == &cpSegmentShapeClass, "Shape is not a segment shape.");
578     cpSegmentShape* seg = cast(cpSegmentShape*)shape;
579 
580     seg.a = a;
581     seg.b = b;
582     seg.n = cpvperp(cpvnormalize(cpvsub(b, a)));
583 }
584 
585 void cpSegmentShapeSetRadius(cpShape* shape, cpFloat radius)
586 {
587     cpAssertHard(shape.klass == &cpSegmentShapeClass, "Shape is not a segment shape.");
588     cpSegmentShape* seg = cast(cpSegmentShape*)shape;
589 
590     seg.r = radius;
591 }