naev 0.11.5
collision.c
Go to the documentation of this file.
1/*
2 * See Licensing and Copyright notice in naev.h
3 */
11#include "naev.h"
12
13#include "SDL.h"
16#include "collision.h"
17
18#include "log.h"
19#include "array.h"
20
21/*
22 * Prototypes
23 */
24static int PointInPolygon( const CollPoly* at, const vec2* ap,
25 float x, float y );
26static int LineOnPolygon( const CollPoly* at, const vec2* ap,
27 float x1, float y1, float x2, float y2, vec2* crash );
28
35void LoadPolygon( CollPoly* polygon, xmlNodePtr node )
36{
37 xmlNodePtr cur = node->children;
38 do {
39 if (xml_isNode(cur,"x")) {
40 char *saveptr;
41 char *list = xml_get(cur);
42 /* split the list of coordiantes */
43 char *ch = SDL_strtokr(list, ",", &saveptr);
44 polygon->x = array_create_size(float, 32);
45 polygon->xmin = 0;
46 polygon->xmax = 0;
47 while (ch != NULL) {
48 float d = atof(ch);
49 array_push_back( &polygon->x, d );
50 polygon->xmin = MIN( polygon->xmin, d );
51 polygon->xmax = MAX( polygon->xmax, d );
52 ch = SDL_strtokr(NULL, ",", &saveptr);
53 }
54 }
55 else if (xml_isNode(cur,"y")) {
56 char *saveptr;
57 char *list = xml_get(cur);
58 /* split the list of coordiantes */
59 char *ch = SDL_strtokr(list, ",", &saveptr);
60 polygon->y = array_create_size(float, 32);
61 polygon->ymin = 0;
62 polygon->ymax = 0;
63 while (ch != NULL) {
64 float d = atof(ch);
65 array_push_back( &polygon->y, d );
66 polygon->ymin = MIN( polygon->ymin, d );
67 polygon->ymax = MAX( polygon->ymax, d );
68 ch = SDL_strtokr(NULL, ",", &saveptr);
69 }
70 }
71 } while (xml_nextNode(cur));
72
73 polygon->npt = array_size(polygon->x);
74 if (array_size(polygon->y) != polygon->npt)
75 WARN(_("Polygon with mismatch of number of |x|=%d and |y|=%d coordinates detected!"), polygon->npt, array_size(polygon->y) );
76
77 return;
78}
79
80void FreePolygon( CollPoly *polygon )
81{
82 array_free( polygon->x );
83 array_free( polygon->y );
84}
85
103int CollideSprite( const glTexture* at, const int asx, const int asy, const vec2* ap,
104 const glTexture* bt, const int bsx, const int bsy, const vec2* bp,
105 vec2* crash )
106{
107 int x,y;
108 int ax1,ax2, ay1,ay2;
109 int bx1,bx2, by1,by2;
110 int inter_x0, inter_x1, inter_y0, inter_y1;
111 int rasy, rbsy;
112 int abx,aby, bbx, bby;
113
114#if DEBUGGING
115 /* Make sure the surfaces have transparency maps. */
116 if (at->trans == NULL) {
117 WARN(_("Texture '%s' has no transparency map"), at->name);
118 return 0;
119 }
120 if (bt->trans == NULL) {
121 WARN(_("Texture '%s' has no transparency map"), bt->name);
122 return 0;
123 }
124#endif /* DEBUGGING */
125
126 /* a - cube coordinates */
127 ax1 = (int)VX(*ap) - (int)(at->sw)/2;
128 ay1 = (int)VY(*ap) - (int)(at->sh)/2;
129 ax2 = ax1 + (int)(at->sw) - 1;
130 ay2 = ay1 + (int)(at->sh) - 1;
131
132 /* b - cube coordinates */
133 bx1 = (int)VX(*bp) - (int)(bt->sw)/2;
134 by1 = (int)VY(*bp) - (int)(bt->sh)/2;
135 bx2 = bx1 + bt->sw - 1;
136 by2 = by1 + bt->sh - 1;
137
138 /* check if bounding boxes intersect */
139 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
140 if ((by2 < ay1) || (ay2 < by1)) return 0;
141
142 /* define the remaining binding box */
143 inter_x0 = MAX( ax1, bx1 );
144 inter_x1 = MIN( ax2, bx2 );
145 inter_y0 = MAX( ay1, by1 );
146 inter_y1 = MIN( ay2, by2 );
147
148 /* real vertical sprite value (flipped) */
149 rasy = at->sy - asy - 1;
150 rbsy = bt->sy - bsy - 1;
151
152 /* set up the base points */
153 abx = asx*(int)(at->sw) - ax1;
154 aby = rasy*(int)(at->sh) - ay1;
155 bbx = bsx*(int)(bt->sw) - bx1;
156 bby = rbsy*(int)(bt->sh) - by1;
157
158 for (y=inter_y0; y<=inter_y1; y++)
159 for (x=inter_x0; x<=inter_x1; x++)
160 /* compute offsets for surface before pass to TransparentPixel test */
161 if ((!gl_isTrans(at, abx + x, aby + y)) &&
162 (!gl_isTrans(bt, bbx + x, bby + y))) {
163
164 /* Set the crash position. */
165 crash->x = x;
166 crash->y = y;
167 return 1;
168 }
169
170 return 0;
171}
172
185int CollideSpritePolygon( const CollPoly* at, const vec2* ap,
186 const glTexture* bt, const int bsx, const int bsy, const vec2* bp,
187 vec2* crash )
188{
189 int x,y;
190 int ax1,ax2, ay1,ay2;
191 int bx1,bx2, by1,by2;
192 int inter_x0, inter_x1, inter_y0, inter_y1;
193 int rbsy;
194 int bbx, bby;
195
196#if DEBUGGING
197 /* Make sure the surfaces have transparency maps. */
198 if (bt->trans == NULL) {
199 WARN(_("Texture '%s' has no transparency map"), bt->name);
200 return 0;
201 }
202#endif /* DEBUGGING */
203
204 /* a - cube coordinates */
205 ax1 = (int)VX(*ap) + (int)(at->xmin);
206 ay1 = (int)VY(*ap) + (int)(at->ymin);
207 ax2 = (int)VX(*ap) + (int)(at->xmax);
208 ay2 = (int)VY(*ap) + (int)(at->ymax);
209
210 /* b - cube coordinates */
211 bx1 = (int)VX(*bp) - (int)(bt->sw)/2;
212 by1 = (int)VY(*bp) - (int)(bt->sh)/2;
213 bx2 = bx1 + bt->sw - 1;
214 by2 = by1 + bt->sh - 1;
215
216 /* check if bounding boxes intersect */
217 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
218 if ((by2 < ay1) || (ay2 < by1)) return 0;
219
220 /* define the remaining binding box */
221 inter_x0 = MAX( ax1, bx1 );
222 inter_x1 = MIN( ax2, bx2 );
223 inter_y0 = MAX( ay1, by1 );
224 inter_y1 = MIN( ay2, by2 );
225
226 /* real vertical sprite value (flipped) */
227 rbsy = bt->sy - bsy - 1;
228
229 /* set up the base points */
230 bbx = bsx*(int)(bt->sw) - bx1;
231 bby = rbsy*(int)(bt->sh) - by1;
232 for (y=inter_y0; y<=inter_y1; y++) {
233 for (x=inter_x0; x<=inter_x1; x++) {
234 /* compute offsets for surface before pass to TransparentPixel test */
235 if ((!gl_isTrans(bt, bbx + x, bby + y))) {
236 if (PointInPolygon( at, ap, (float)x, (float)y )) {
237 crash->x = x;
238 crash->y = y;
239 return 1;
240 }
241 }
242 }
243 }
244
245 return 0;
246}
247
260int CollidePolygon( const CollPoly* at, const vec2* ap,
261 const CollPoly* bt, const vec2* bp, vec2* crash )
262{
263 int ax1,ax2, ay1,ay2;
264 int bx1,bx2, by1,by2;
265 int inter_x0, inter_x1, inter_y0, inter_y1;
266 float x1, y1, x2, y2;
267
268 /* a - cube coordinates */
269 ax1 = (int)VX(*ap) + (int)(at->xmin);
270 ay1 = (int)VY(*ap) + (int)(at->ymin);
271 ax2 = (int)VX(*ap) + (int)(at->xmax);
272 ay2 = (int)VY(*ap) + (int)(at->ymax);
273
274 /* b - cube coordinates */
275 bx1 = (int)VX(*bp) + (int)(bt->xmin);
276 by1 = (int)VY(*bp) + (int)(bt->ymin);
277 bx2 = (int)VX(*bp) + (int)(bt->xmax);
278 by2 = (int)VY(*bp) + (int)(bt->ymax);
279
280 /* check if bounding boxes intersect */
281 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
282 if ((by2 < ay1) || (ay2 < by1)) return 0;
283
284 /* define the remaining binding box */
285 inter_x0 = MAX( ax1, bx1 );
286 inter_x1 = MIN( ax2, bx2 );
287 inter_y0 = MAX( ay1, by1 );
288 inter_y1 = MIN( ay2, by2 );
289
290 /* loop on the points of bt to see if one of them is in polygon at. */
291 for (int i=0; i<=bt->npt-1; i++) {
292 float xabs, yabs;
293 xabs = bt->x[i] + VX(*bp);
294 yabs = bt->y[i] + VY(*bp);
295
296 if ((xabs<inter_x0) || (xabs>inter_x1) ||
297 (yabs<inter_y0) || (yabs>inter_y1)) {
298 if (PointInPolygon( at, ap, xabs, yabs )) {
299 crash->x = (int)xabs;
300 crash->y = (int)yabs;
301 return 1;
302 }
303 }
304 }
305
306 /* loop on the lines of bt to see if one of them intersects a line of at. */
307 x1 = bt->x[0] + VX(*bp);
308 y1 = bt->y[0] + VY(*bp);
309 x2 = bt->x[bt->npt-1] + VX(*bp);
310 y2 = bt->y[bt->npt-1] + VY(*bp);
311 if (LineOnPolygon( at, ap, x1, y1, x2, y2, crash ))
312 return 1;
313 for (int i=0; i<=bt->npt-2; i++) {
314 x1 = bt->x[i] + VX(*bp);
315 y1 = bt->y[i] + VY(*bp);
316 x2 = bt->x[i+1] + VX(*bp);
317 y2 = bt->y[i+1] + VY(*bp);
318 if ( LineOnPolygon( at, ap, x1, y1, x2, y2, crash ) )
319 return 1;
320 }
321
322 return 0;
323}
324
332void RotatePolygon( CollPoly* rpolygon, CollPoly* ipolygon, float theta )
333{
334 float ct, st;
335
336 rpolygon->npt = ipolygon->npt;
337 rpolygon->x = malloc( ipolygon->npt*sizeof(float) );
338 rpolygon->y = malloc( ipolygon->npt*sizeof(float) );
339 rpolygon->xmin = 0;
340 rpolygon->xmax = 0;
341 rpolygon->ymin = 0;
342 rpolygon->ymax = 0;
343
344 ct = cos( theta );
345 st = sin( theta );
346
347 for (int i=0; i<=rpolygon->npt-1; i++) {
348 float d = ipolygon->x[i] * ct - ipolygon->y[i] * st;
349 rpolygon->x[i] = d;
350 rpolygon->xmin = MIN( rpolygon->xmin, d );
351 rpolygon->xmax = MAX( rpolygon->xmax, d );
352
353 d = ipolygon->x[i] * st + ipolygon->y[i] * ct ;
354 rpolygon->y[i] = d;
355 rpolygon->ymin = MIN( rpolygon->ymin, d );
356 rpolygon->ymax = MAX( rpolygon->ymax, d );
357 }
358}
359
369static int PointInPolygon( const CollPoly* at, const vec2* ap,
370 float x, float y )
371{
372 float vprod, sprod, angle;
373 float dxi, dxip, dyi, dyip;
374
375 /* See if the pixel is inside the polygon:
376 We increment the angle when doing a loop along all the points
377 If the final angle is 0, we are outside the polygon
378 Otherwise, the angle should be +/- 2pi*/
379 angle = 0.0;
380 for (int i=0; i<=at->npt-2; i++) {
381 dxi = at->x[i] +VX(*ap)-x;
382 dxip = at->x[i+1]+VX(*ap)-x;
383 dyi = at->y[i] +VY(*ap)-y;
384 dyip = at->y[i+1]+VY(*ap)-y;
385 sprod = dxi * dxip + dyi * dyip;
386 vprod = dxi * dyip - dyi * dxip;
387 angle += atan2(vprod, sprod);
388 }
389 dxi = at->x[at->npt-1] + VX(*ap) - x;
390 dxip = at->x[0] + VX(*ap) - x;
391 dyi = at->y[at->npt-1] + VY(*ap)- y;
392 dyip = at->y[0] + VY(*ap) - y;
393 sprod = dxi * dxip + dyi * dyip;
394 vprod = dxi * dyip - dyi * dxip;
395 angle += atan2(vprod, sprod);
396
397 if (FABS(angle) < 1e-5)
398 return 0;
399
400 return 1;
401}
402
415static int LineOnPolygon( const CollPoly* at, const vec2* ap,
416 float x1, float y1, float x2, float y2, vec2* crash )
417{
418 float xi, xip, yi, yip;
419
420 /* In this function, we are only looking for one collision point. */
421
422 xi = at->x[at->npt-1] + ap->x;
423 xip = at->x[0] + ap->x;
424 yi = at->y[at->npt-1] + ap->y;
425 yip = at->y[0] + ap->y;
426 if ( CollideLineLine(x1, y1, x2, y2, xi, yi, xip, yip, crash) == 1 )
427 return 1;
428 for (int i=0; i<=at->npt-2; i++) {
429 xi = at->x[i] + ap->x;
430 xip = at->x[i+1] + ap->x;
431 yi = at->y[i] + ap->y;
432 yip = at->y[i+1] + ap->y;
433 if ( CollideLineLine(x1, y1, x2, y2, xi, yi, xip, yip, crash) == 1 )
434 return 1;
435 }
436
437 return 0;
438}
439
455int CollideLineLine( double s1x, double s1y, double e1x, double e1y,
456 double s2x, double s2y, double e2x, double e2y, vec2* crash )
457{
458 double ua_t, ub_t, u_b;
459
460 ua_t = (e2x - s2x) * (s1y - s2y) - (e2y - s2y) * (s1x - s2x);
461 ub_t = (e1x - s1x) * (s1y - s2y) - (e1y - s1y) * (s1x - s2x);
462 u_b = (e2y - s2y) * (e1x - s1x) - (e2x - s2x) * (e1y - s1y);
463
464 if (u_b != 0.) {
465 double ua, ub;
466 ua = ua_t / u_b;
467 ub = ub_t / u_b;
468
469 /* Intersection at a point. */
470 if ((0. <= ua) && (ua <= 1.) && (0. <= ub) && (ub <= 1.)) {
471 crash->x = s1x + ua * (e1x - s1x);
472 crash->y = s1y + ua * (e1y - s1y);
473 return 1;
474 }
475 /* No intersection. */
476 else
477 return 0;
478 }
479 else {
480 /* Coincident. */
481 if ((ua_t == 0.) || (ub_t == 0.))
482 return 3;
483 /* Parallel. */
484 else
485 return 2;
486 }
487}
488
508int CollideLineSprite( const vec2* ap, double ad, double al,
509 const glTexture* bt, const int bsx, const int bsy, const vec2* bp,
510 vec2 crash[2] )
511{
512 int x,y, rbsy, bbx,bby;
513 double ep[2], bl[2], tr[2], v[2], mod;
514 int hits, real_hits;
515 vec2 tmp_crash, border[2];
516
517 /* Make sure texture has transparency map. */
518 if (bt->trans == NULL) {
519 WARN(_("Texture '%s' has no transparency map"), bt->name);
520 return 0;
521 }
522
523 /* Set up end point of line. */
524 ep[0] = ap->x + al*cos(ad);
525 ep[1] = ap->y + al*sin(ad);
526
527 /* Set up top right corner of the rectangle. */
528 tr[0] = bp->x + bt->sw/2.;
529 tr[1] = bp->y + bt->sh/2.;
530 /* Set up bottom left corner of the rectangle. */
531 bl[0] = bp->x - bt->sw/2.;
532 bl[1] = bp->y - bt->sh/2.;
533
534 /*
535 * Start check for rectangular collisions.
536 */
537 hits = 0;
538 /* Left border. */
539 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
540 bl[0], bl[1], bl[0], tr[1], &tmp_crash) == 1) {
541 border[hits].x = tmp_crash.x;
542 border[hits].y = tmp_crash.y;
543 hits++;
544 }
545 /* Top border. */
546 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
547 bl[0], tr[1], tr[0], tr[1], &tmp_crash) == 1) {
548 border[hits].x = tmp_crash.x;
549 border[hits].y = tmp_crash.y;
550 hits++;
551 }
552 /* Now we have to make sure hits isn't 2. */
553 /* Right border. */
554 if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
555 tr[0], tr[1], tr[0], bl[1], &tmp_crash) == 1) {
556 border[hits].x = tmp_crash.x;
557 border[hits].y = tmp_crash.y;
558 hits++;
559 }
560 /* Bottom border. */
561 if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
562 tr[0], bl[1], bl[0], bl[1], &tmp_crash) == 1) {
563 border[hits].x = tmp_crash.x;
564 border[hits].y = tmp_crash.y;
565 hits++;
566 }
567
568 /* No hits - missed. */
569 if (hits == 0)
570 return 0;
571
572 /* Beam must die in the rectangle. */
573 if (hits == 1) {
574 border[1].x = ep[0];
575 border[1].y = ep[1];
576 }
577
578 /*
579 * Now we do a pixel perfect approach.
580 */
581 real_hits = 0;
582 /* Directionality vector (normalized). */
583 v[0] = border[1].x - border[0].x;
584 v[1] = border[1].y - border[0].y;
585 /* Normalize. */
586 mod = MOD(v[0],v[1])/2.; /* Multiply by two to reduce check amount. */
587 v[0] /= mod;
588 v[1] /= mod;
589
590 /* real vertical sprite value (flipped) */
591 rbsy = bt->sy - bsy - 1;
592 /* set up the base points */
593 bbx = bsx*(int)(bt->sw);
594 bby = rbsy*(int)(bt->sh);
595
596 /* We start checking first border until we find collision. */
597 x = border[0].x - bl[0] + v[0];
598 y = border[0].y - bl[1] + v[1];
599 while ((x > 0.) && (x < bt->sw) && (y > 0.) && (y < bt->sh)) {
600 /* Is non-transparent. */
601 if (!gl_isTrans(bt, bbx+(int)x, bby+(int)y)) {
602 crash[real_hits].x = x + bl[0];
603 crash[real_hits].y = y + bl[1];
604 real_hits++;
605 break;
606 }
607 x += v[0];
608 y += v[1];
609 }
610
611 /* Now we check the second border. */
612 x = border[1].x - bl[0] - v[0];
613 y = border[1].y - bl[1] - v[1];
614 while ((x > 0.) && (x < bt->sw) && (y > 0.) && (y < bt->sh)) {
615 /* Is non-transparent. */
616 if (!gl_isTrans(bt, bbx+(int)x, bby+(int)y)) {
617 crash[real_hits].x = x + bl[0];
618 crash[real_hits].y = y + bl[1];
619 real_hits++;
620 break;
621 }
622 x -= v[0];
623 y -= v[1];
624 }
625
626 /* Actually missed. */
627 if (real_hits == 0)
628 return 0;
629
630 /* Strange situation, should never happen but just in case we duplicate
631 * the hit. */
632 if (real_hits == 1) {
633 crash[1].x = crash[0].x;
634 crash[1].y = crash[0].y;
635 }
636
637 /* We hit. */
638 return 1;
639}
640
657int CollideLinePolygon( const vec2* ap, double ad, double al,
658 const CollPoly* bt, const vec2* bp, vec2 crash[2] )
659{
660 double ep[2];
661 double xi, yi, xip, yip;
662 int real_hits;
663 vec2 tmp_crash;
664
665 /* Set up end point of line. */
666 ep[0] = ap->x + al*cos(ad);
667 ep[1] = ap->y + al*sin(ad);
668
669 real_hits = 0;
670 vectnull( &tmp_crash );
671
672 /* Check if the beginning point is inside polygon */
673 if (PointInPolygon( bt, bp, (float) ap->x, (float) ap->y )) {
674 crash[real_hits].x = ap->x;
675 crash[real_hits].y = ap->y;
676 real_hits++;
677 }
678
679 /* same thing for end point */
680 if (PointInPolygon( bt, bp, (float) ep[0], (float) ep[1] )) {
681 crash[real_hits].x = ep[0];
682 crash[real_hits].y = ep[1];
683 real_hits++;
684 }
685
686 /* If both are inside, we got the two collision points. */
687 if (real_hits == 2)
688 return 1;
689
690 /* None is inside, check if there is a chance of intersection */
691 if (real_hits == 0) {
692 int hits;
693 double bl[2], tr[2];
694 /* Set up top right corner of the rectangle. */
695 tr[0] = bp->x + (double)bt->xmax;
696 tr[1] = bp->y + (double)bt->ymax;
697 /* Set up bottom left corner of the rectangle. */
698 bl[0] = bp->x + (double)bt->xmin;
699 bl[1] = bp->y + (double)bt->ymin;
700
701 /*
702 * Start check for rectangular collisions.
703 */
704 hits = 0;
705 /* Left border. */
706 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
707 bl[0], bl[1], bl[0], tr[1], &tmp_crash) == 1)
708 hits++;
709
710 /* Top border. */
711 if (!hits && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
712 bl[0], tr[1], tr[0], tr[1], &tmp_crash) == 1)
713 hits++;
714
715 /* Right border. */
716 if (!hits && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
717 tr[0], tr[1], tr[0], bl[1], &tmp_crash) == 1)
718 hits++;
719
720 /* Bottom border. */
721 if (!hits && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
722 tr[0], bl[1], bl[0], bl[1], &tmp_crash) == 1)
723 hits++;
724
725 /* No hits - missed. No need to go further */
726 if (hits == 0)
727 return 0;
728 }
729
730 /*
731 * Now we check any line of the polygon
732 */
733 xi = (double)bt->x[bt->npt-1] + bp->x;
734 xip = (double)bt->x[0] + bp->x;
735 yi = (double)bt->y[bt->npt-1] + bp->y;
736 yip = (double)bt->y[0] + bp->y;
737 if ( CollideLineLine(ap->x, ap->y, ep[0], ep[1],
738 xi, yi, xip, yip, &tmp_crash) ) {
739 crash[real_hits].x = tmp_crash.x;
740 crash[real_hits].y = tmp_crash.y;
741 real_hits++;
742 if (real_hits == 2)
743 return 1;
744 }
745 for (int i=0; i<=bt->npt-2; i++) {
746 xi = (double)bt->x[i] + bp->x;
747 xip = (double)bt->x[i+1] + bp->x;
748 yi = (double)bt->y[i] + bp->y;
749 yip = (double)bt->y[i+1] + bp->y;
750 if ( CollideLineLine(ap->x, ap->y, ep[0], ep[1],
751 xi, yi, xip, yip, &tmp_crash) ) {
752 crash[real_hits].x = tmp_crash.x;
753 crash[real_hits].y = tmp_crash.y;
754 real_hits++;
755 if (real_hits == 2)
756 return 1;
757 }
758 }
759
760 /* Actually missed. */
761 if (real_hits == 0)
762 return 0;
763
764 /* Strange situation, should never happen but just in case we duplicate
765 * the hit. */
766 if (real_hits == 1) {
767 crash[1].x = crash[0].x;
768 crash[1].y = crash[0].y;
769 }
770
771 /* We hit. */
772 return 1;
773}
774
790int CollideCirclePolygon( const vec2* ap, double ar,
791 const CollPoly* bt, const vec2* bp, vec2 crash[2] )
792{
793 vec2 p1, p2;
794 int real_hits;
795 vec2 tmp_crash[2];
796
797 real_hits = 0;
798 vectnull( &tmp_crash[0] );
799 vectnull( &tmp_crash[1] );
800
801 /* Set up top right corner of the rectangle. */
802 p1.x = bp->x + (double)bt->xmax;
803 p1.y = bp->y + (double)bt->ymax;
804 /* Set up bottom left corner of the rectangle. */
805 p2.x = bp->x + (double)bt->xmin;
806 p2.y = bp->y + (double)bt->ymin;
807
808 /* Start check for rectangular collisions. */
809 if ((ap->x-ar > p1.x) && (ap->x+ar < p2.x) &&
810 (ap->y-ar > p1.y) && (ap->y+ar < p2.y))
811 return 0;
812
813 /*
814 * Now we check any line of the polygon
815 */
816 p1.x = (double)bt->x[bt->npt-1] + bp->x;
817 p2.x = (double)bt->x[0] + bp->x;
818 p1.y = (double)bt->y[bt->npt-1] + bp->y;
819 p2.y = (double)bt->y[0] + bp->y;
820 if (CollideLineCircle( &p1, &p2, ap, ar, tmp_crash )) {
821 crash[real_hits].x = tmp_crash[0].x;
822 crash[real_hits].y = tmp_crash[0].y;
823 real_hits++;
824 if (real_hits == 2)
825 return 1;
826 }
827 for (int i=0; i<=bt->npt-2; i++) {
828 p1.x = (double)bt->x[i] + bp->x;
829 p2.x = (double)bt->x[i+1] + bp->x;
830 p1.y = (double)bt->y[i] + bp->y;
831 p2.y = (double)bt->y[i+1] + bp->y;
832 if (CollideLineCircle( &p1, &p2, ap, ar, tmp_crash )) {
833 crash[real_hits].x = tmp_crash[0].x;
834 crash[real_hits].y = tmp_crash[0].y;
835 real_hits++;
836 if (real_hits == 2)
837 return 1;
838 }
839 }
840
841 /* Actually missed. */
842 if (real_hits == 0)
843 return 0;
844
845 /* Strange situation, should never happen but just in case we duplicate
846 * the hit. */
847 if (real_hits == 1) {
848 crash[1].x = crash[0].x;
849 crash[1].y = crash[0].y;
850 }
851
852 /* We hit. */
853 return 1;
854}
855
868int CollideCircleSprite( const vec2 *ap, double ar, const glTexture* bt,
869 const int bsx, const int bsy, const vec2* bp,vec2* crash )
870{
871 int r, acx,acy, ax1,ax2, ay1,ay2;
872 int bx1,bx2, by1,by2;
873 int inter_x0, inter_x1, inter_y0, inter_y1;
874 int rbsy;
875 int bbx, bby;
876
877#if DEBUGGING
878 /* Make sure the surfaces have transparency maps. */
879 if (bt->trans == NULL) {
880 WARN(_("Texture '%s' has no transparency map"), bt->name);
881 return 0;
882 }
883#endif /* DEBUGGING */
884
885 /* a - cube coordinates */
886 r = ceil(ar);
887 acx = (int) VX(*ap);
888 acy = (int) VY(*ap);
889 ax1 = acx - r;
890 ay1 = acy - r;
891 ax2 = acx + r;
892 ay2 = acy + r;
893
894 /* b - cube coordinates */
895 bx1 = (int)VX(*bp) - (int)(bt->sw)/2;
896 by1 = (int)VY(*bp) - (int)(bt->sh)/2;
897 bx2 = bx1 + bt->sw - 1;
898 by2 = by1 + bt->sh - 1;
899
900 /* check if bounding boxes intersect */
901 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
902 if ((by2 < ay1) || (ay2 < by1)) return 0;
903
904 /* define the remaining binding box */
905 inter_x0 = MAX( ax1, bx1 );
906 inter_x1 = MIN( ax2, bx2 );
907 inter_y0 = MAX( ay1, by1 );
908 inter_y1 = MIN( ay2, by2 );
909
910 /* real vertical sprite value (flipped) */
911 rbsy = bt->sy - bsy - 1;
912
913 /* set up the base points */
914 bbx = bsx*(int)(bt->sw) - bx1;
915 bby = rbsy*(int)(bt->sh) - by1;
916 for (int y=inter_y0; y<=inter_y1; y++) {
917 for (int x=inter_x0; x<=inter_x1; x++) {
918 /* compute offsets for surface before pass to TransparentPixel test */
919 if ((!gl_isTrans(bt, bbx + x, bby + y))) {
920 if (pow2(x-acx)+pow2(y-acy) <= r*r) {
921 crash->x = x;
922 crash->y = y;
923 return 1;
924 }
925 }
926 }
927 }
928
929 return 0;
930}
931
932static int linePointOnSegment( double d1, double x1, double y1, double x2, double y2, double x, double y )
933{
934 //double d1 = hypot( x2-x1, y2-y1 ); /* Distance between end-points. */
935 double d2 = hypot( x-x1, y-y1 ); /* Distance from point to one end. */
936 double d3 = hypot( x2-x, y2-y ); /* Distance to the other end. */
937 return fabs(d1 - d2 - d3) < 1e-8; /* True if smaller than some tolerance. */
938}
939
940#define FX( A, B, C, x ) (-(A * x + C) / B)
941#define FY( A, B, C , y ) (-(B * y + C) / A)
952int CollideLineCircle( const vec2* p1, const vec2* p2,
953 const vec2 *cc, double cr, vec2 crash[2] )
954{
955 double x0 = cc->x;
956 double y0 = cc->y;
957 double x1 = p1->x;
958 double y1 = p1->y;
959 double x2 = p2->x;
960 double y2 = p2->y;
961
962 double A = y2 - y1;
963 double B = x1 - x2;
964 double C = x2 * y1 - x1 * y2;
965
966 double a = pow2(A) + pow2(B);
967 double b, c, d;
968
969 int bnz, cnt;
970
971 double x, y, d1;
972
973 /* Non-vertical case. */
974 if (fabs(B) >= 1e-8) {
975 b = 2. * (A * C + A * B * y0 - pow2(B) * x0);
976 c = pow2(C) + 2. * B * C * y0 - pow2(B) * (pow2(cr) - pow2(x0) - pow2(y0));
977 bnz = 1;
978 }
979 /* Have to have special care when line is vertical. */
980 else {
981 b = 2. * (B * C + A * B * x0 - pow2(A) * y0);
982 c = pow2(C) + 2. * A * C * x0 - pow2(A) * (pow2(cr) - pow2(x0) - pow2(y0));
983 bnz = 0;
984 }
985 d = pow2(b) - 4. * a * c; /* Discriminant. */
986 if (d < 0.)
987 return 0;
988
989 cnt = 0;
990 d1 = hypot( x2-x1, y2-y1 );
991 /* Line is tangent, so only one intersection. */
992 if (d == 0.) {
993 if (bnz) {
994 x = -b / (2. * a);
995 y = FX(A, B, C, x);
996 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
997 crash[cnt].x = x;
998 crash[cnt].y = y;
999 cnt++;
1000 }
1001 } else {
1002 y = -b / (2. * a);
1003 x = FY(A, B, C, y);
1004 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
1005 crash[cnt].x = x;
1006 crash[cnt].y = y;
1007 cnt++;
1008 }
1009 }
1010 }
1011 /* Two intersections. */
1012 else {
1013 d = sqrt(d);
1014 if (bnz) {
1015 x = (-b + d) / (2. * a);
1016 y = FX(A, B, C, x);
1017 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
1018 crash[cnt].x = x;
1019 crash[cnt].y = y;
1020 cnt++;
1021 }
1022 x = (-b - d) / (2. * a);
1023 y = FX(A, B, C, x);
1024 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
1025 crash[cnt].x = x;
1026 crash[cnt].y = y;
1027 cnt++;
1028 }
1029 } else {
1030 y = (-b + d) / (2. * a);
1031 x = FY(A, B, C, y);
1032 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
1033 crash[cnt].x = x;
1034 crash[cnt].y = y;
1035 cnt++;
1036 }
1037 y = (-b - d) / (2. * a);
1038 x = FY(A, B, C, y);
1039 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
1040 crash[cnt].x = x;
1041 crash[cnt].y = y;
1042 cnt++;
1043 }
1044 }
1045 }
1046 return cnt;
1047}
1048#undef FX
1049#undef FY
1050
1054int CollideCircleCircle( const vec2 *p1, double r1,
1055 const vec2 *p2, double r2, vec2 crash[2] )
1056{
1057 double dist2 = vec2_dist2( p1, p2 );
1058
1059 /* No intersection. */
1060 if (dist2 > pow2(r1+r2))
1061 return 0;
1062
1063 crash->x = (p1->x * r1 + p2->x * r2) / (r1+r2);
1064 crash->y = (p1->y * r1 + p2->y * r2) / (r1+r2);
1065 return 1;
1066}
1067
1071double CollideCircleIntersection( const vec2 *p1, double r1,
1072 const vec2 *p2, double r2 )
1073{
1074 double dist2 = vec2_dist2( p1, p2 );
1075
1076 /* No intersection. */
1077 if (dist2 > pow2(r1+r2))
1078 return 0.;
1079
1080 /* One inside the other. */
1081 if (dist2 <= pow2(fabs(r1-r2)))
1082 return M_PI * pow2( MIN(r1, r2) );
1083
1084#if 0
1085 /* Case exactly the same. */
1086 if ((dist2==0.) && (r1==r2))
1087 return M_PI * pow2(r1);
1088#endif
1089
1090 /* Distances. */
1091 double dist = sqrt( dist2 );
1092 double distc1 = (pow2(r1) - pow2(r2) + dist2) / (2. * dist); /* First center point to middle line. */
1093 double distc2 = dist - distc1; /* Second center point to middle line. */
1094 double height = sqrt( pow2(r1) - pow2(distc1) ); /* Half of middle line. */
1095 /* Angles. */
1096 double ang1 = fmod( atan2( height, distc1 ) * 2. + 2.*M_PI, 2.*M_PI ); /* Center angle for first circle. */
1097 double ang2 = fmod( atan2( height, distc2 ) * 2. + 2.*M_PI, 2.*M_PI ); /*< Center angle for second circle. */
1098 /* Areas. */
1099 double A1 = pow2(r1) / 2.0 * (ang1 - sin(ang1)); /* Area of first circula segment. */
1100 double A2 = pow2(r2) / 2.0 * (ang2 - sin(ang2)); /* Area of second circula segment. */
1101
1102 return A1+A2;
1103}
array.h
Provides macros to work with dynamic arrays.
array_free
#define array_free(ptr_array)
Frees memory allocated and sets array to NULL.
Definition array.h:158
array_create_size
#define array_create_size(basic_type, capacity)
Creates a new dynamic array of ‘basic_type’ with an initial capacity.
Definition array.h:102
array_size
static ALWAYS_INLINE int array_size(const void *array)
Returns number of elements in the array.
Definition array.h:168
array_push_back
#define array_push_back(ptr_array, element)
Adds a new element at the end of the array.
Definition array.h:129
CollideCircleCircle
int CollideCircleCircle(const vec2 *p1, double r1, const vec2 *p2, double r2, vec2 crash[2])
Computes the collision between two circles.
Definition collision.c:1054
RotatePolygon
void RotatePolygon(CollPoly *rpolygon, CollPoly *ipolygon, float theta)
Rotates a polygon.
Definition collision.c:332
LineOnPolygon
static int LineOnPolygon(const CollPoly *at, const vec2 *ap, float x1, float y1, float x2, float y2, vec2 *crash)
Checks whether or not a line intersects a polygon.
Definition collision.c:415
CollideLineCircle
int CollideLineCircle(const vec2 *p1, const vec2 *p2, const vec2 *cc, double cr, vec2 crash[2])
Checks to see if a line collides with a circle.
Definition collision.c:952
CollideLinePolygon
int CollideLinePolygon(const vec2 *ap, double ad, double al, const CollPoly *bt, const vec2 *bp, vec2 crash[2])
Checks to see if a line collides with a polygon.
Definition collision.c:657
PointInPolygon
static int PointInPolygon(const CollPoly *at, const vec2 *ap, float x, float y)
Checks whether or not a point is inside a polygon.
Definition collision.c:369
CollideLineSprite
int CollideLineSprite(const vec2 *ap, double ad, double al, const glTexture *bt, const int bsx, const int bsy, const vec2 *bp, vec2 crash[2])
Checks to see if a line collides with a sprite.
Definition collision.c:508
CollideCircleSprite
int CollideCircleSprite(const vec2 *ap, double ar, const glTexture *bt, const int bsx, const int bsy, const vec2 *bp, vec2 *crash)
Checks whether or not a sprite collides with a polygon.
Definition collision.c:868
LoadPolygon
void LoadPolygon(CollPoly *polygon, xmlNodePtr node)
Loads a polygon from an xml node.
Definition collision.c:35
CollideLineLine
int CollideLineLine(double s1x, double s1y, double e1x, double e1y, double s2x, double s2y, double e2x, double e2y, vec2 *crash)
Checks to see if two lines collide.
Definition collision.c:455
CollideSprite
int CollideSprite(const glTexture *at, const int asx, const int asy, const vec2 *ap, const glTexture *bt, const int bsx, const int bsy, const vec2 *bp, vec2 *crash)
Checks whether or not two sprites collide.
Definition collision.c:103
CollideCirclePolygon
int CollideCirclePolygon(const vec2 *ap, double ar, const CollPoly *bt, const vec2 *bp, vec2 crash[2])
Checks to see if a circle collides with a polygon.
Definition collision.c:790
CollideSpritePolygon
int CollideSpritePolygon(const CollPoly *at, const vec2 *ap, const glTexture *bt, const int bsx, const int bsy, const vec2 *bp, vec2 *crash)
Checks whether or not a sprite collides with a polygon.
Definition collision.c:185
CollidePolygon
int CollidePolygon(const CollPoly *at, const vec2 *ap, const CollPoly *bt, const vec2 *bp, vec2 *crash)
Checks whether or not two polygons collide. /!\ The function is not symmetric: the points of polygon ...
Definition collision.c:260
CollideCircleIntersection
double CollideCircleIntersection(const vec2 *p1, double r1, const vec2 *p2, double r2)
Calculates the area of intersection between two circles.
Definition collision.c:1071
naev.h
Header file with generic functions and naev-specifics.
MIN
#define MIN(x, y)
Definition naev.h:40
pow2
#define pow2(x)
Definition naev.h:46
FABS
#define FABS(x)
Definition naev.h:37
MAX
#define MAX(x, y)
Definition naev.h:39
gl_isTrans
int gl_isTrans(const glTexture *t, const int x, const int y)
Checks to see if a pixel is transparent in a texture.
Definition opengl_tex.c:948
c
static const double c[]
Definition rng.c:264
d
static const double d[]
Definition rng.c:273
C
static cholmod_common C
Definition safelanes.c:95
CollPoly
Represents a polygon used for collision detection.
Definition collision.h:13
CollPoly::ymin
float ymin
Definition collision.h:18
CollPoly::ymax
float ymax
Definition collision.h:19
CollPoly::xmax
float xmax
Definition collision.h:17
CollPoly::xmin
float xmin
Definition collision.h:16
CollPoly::x
float * x
Definition collision.h:14
CollPoly::y
float * y
Definition collision.h:15
CollPoly::npt
int npt
Definition collision.h:20
glTexture
Abstraction for rendering sprite sheets.
Definition opengl_tex.h:36
glTexture::sw
double sw
Definition opengl_tex.h:46
glTexture::trans
uint8_t * trans
Definition opengl_tex.h:53
glTexture::sh
double sh
Definition opengl_tex.h:47
glTexture::name
char * name
Definition opengl_tex.h:37
glTexture::sy
double sy
Definition opengl_tex.h:45
st
Definition msgcat.c:199
vec2
Represents a 2d vector.
Definition vec2.h:32
vec2::y
double y
Definition vec2.h:34
vec2::x
double x
Definition vec2.h:33
Generated by doxygen 1.12.0