naev 0.10.4
collision.c
Go to the documentation of this file.
1/*
2 * See Licensing and Copyright notice in naev.h
3 */
11#include "naev.h"
14#include "collision.h"
15
16#include "log.h"
17
18/*
19 * Prototypes
20 */
21static int pointInPolygon( const CollPoly* at, const vec2* ap,
22 float x, float y );
23static int LineOnPolygon( const CollPoly* at, const vec2* ap,
24 float x1, float y1, float x2, float y2, vec2* crash );
25
32void LoadPolygon( CollPoly* polygon, xmlNodePtr node )
33{
34 xmlNodePtr cur = node->children;
35 do {
36 if (xml_isNode(cur,"x")) {
37 char *list = xml_get(cur);
38 int i = 0;
39 /* split the list of coordiantes */
40 char *ch = strtok(list, ",");
41 polygon->x = malloc( sizeof(float) );
42 polygon->xmin = 0;
43 polygon->xmax = 0;
44 while (ch != NULL) {
45 float d;
46 i++;
47 polygon->x = realloc( polygon->x, sizeof(float) * i );
48 d = atof(ch);
49 polygon->x[i-1] = d;
50 polygon->xmin = MIN( polygon->xmin, d );
51 polygon->xmax = MAX( polygon->xmax, d );
52 ch = strtok(NULL, ",");
53 }
54 }
55 else if (xml_isNode(cur,"y")) {
56 char *list = xml_get(cur);
57 int i = 0;
58 /* split the list of coordiantes */
59 char *ch = strtok(list, ",");
60 polygon->y = malloc( sizeof(float) );
61 polygon->ymin = 0;
62 polygon->ymax = 0;
63 while (ch != NULL) {
64 float d;
65 i++;
66 polygon->y = realloc( polygon->y, sizeof(float) * i );
67 d = atof(ch);
68 polygon->y[i-1] = d;
69 polygon->ymin = MIN( polygon->ymin, d );
70 polygon->ymax = MAX( polygon->ymax, d );
71 ch = strtok(NULL, ",");
72 }
73 polygon->npt = i;
74 }
75 } while (xml_nextNode(cur));
76
77 return;
78}
79
97int CollideSprite( const glTexture* at, const int asx, const int asy, const vec2* ap,
98 const glTexture* bt, const int bsx, const int bsy, const vec2* bp,
99 vec2* crash )
100{
101 int x,y;
102 int ax1,ax2, ay1,ay2;
103 int bx1,bx2, by1,by2;
104 int inter_x0, inter_x1, inter_y0, inter_y1;
105 int rasy, rbsy;
106 int abx,aby, bbx, bby;
107
108#if DEBUGGING
109 /* Make sure the surfaces have transparency maps. */
110 if (at->trans == NULL) {
111 WARN(_("Texture '%s' has no transparency map"), at->name);
112 return 0;
113 }
114 if (bt->trans == NULL) {
115 WARN(_("Texture '%s' has no transparency map"), bt->name);
116 return 0;
117 }
118#endif /* DEBUGGING */
119
120 /* a - cube coordinates */
121 ax1 = (int)VX(*ap) - (int)(at->sw)/2;
122 ay1 = (int)VY(*ap) - (int)(at->sh)/2;
123 ax2 = ax1 + (int)(at->sw) - 1;
124 ay2 = ay1 + (int)(at->sh) - 1;
125
126 /* b - cube coordinates */
127 bx1 = (int)VX(*bp) - (int)(bt->sw)/2;
128 by1 = (int)VY(*bp) - (int)(bt->sh)/2;
129 bx2 = bx1 + bt->sw - 1;
130 by2 = by1 + bt->sh - 1;
131
132 /* check if bounding boxes intersect */
133 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
134 if ((by2 < ay1) || (ay2 < by1)) return 0;
135
136 /* define the remaining binding box */
137 inter_x0 = MAX( ax1, bx1 );
138 inter_x1 = MIN( ax2, bx2 );
139 inter_y0 = MAX( ay1, by1 );
140 inter_y1 = MIN( ay2, by2 );
141
142 /* real vertical sprite value (flipped) */
143 rasy = at->sy - asy - 1;
144 rbsy = bt->sy - bsy - 1;
145
146 /* set up the base points */
147 abx = asx*(int)(at->sw) - ax1;
148 aby = rasy*(int)(at->sh) - ay1;
149 bbx = bsx*(int)(bt->sw) - bx1;
150 bby = rbsy*(int)(bt->sh) - by1;
151
152 for (y=inter_y0; y<=inter_y1; y++)
153 for (x=inter_x0; x<=inter_x1; x++)
154 /* compute offsets for surface before pass to TransparentPixel test */
155 if ((!gl_isTrans(at, abx + x, aby + y)) &&
156 (!gl_isTrans(bt, bbx + x, bby + y))) {
157
158 /* Set the crash position. */
159 crash->x = x;
160 crash->y = y;
161 return 1;
162 }
163
164 return 0;
165}
166
179int CollideSpritePolygon( const CollPoly* at, const vec2* ap,
180 const glTexture* bt, const int bsx, const int bsy, const vec2* bp,
181 vec2* crash )
182{
183 int x,y;
184 int ax1,ax2, ay1,ay2;
185 int bx1,bx2, by1,by2;
186 int inter_x0, inter_x1, inter_y0, inter_y1;
187 int rbsy;
188 int bbx, bby;
189
190#if DEBUGGING
191 /* Make sure the surfaces have transparency maps. */
192 if (bt->trans == NULL) {
193 WARN(_("Texture '%s' has no transparency map"), bt->name);
194 return 0;
195 }
196#endif /* DEBUGGING */
197
198 /* a - cube coordinates */
199 ax1 = (int)VX(*ap) + (int)(at->xmin);
200 ay1 = (int)VY(*ap) + (int)(at->ymin);
201 ax2 = (int)VX(*ap) + (int)(at->xmax);
202 ay2 = (int)VY(*ap) + (int)(at->ymax);
203
204 /* b - cube coordinates */
205 bx1 = (int)VX(*bp) - (int)(bt->sw)/2;
206 by1 = (int)VY(*bp) - (int)(bt->sh)/2;
207 bx2 = bx1 + bt->sw - 1;
208 by2 = by1 + bt->sh - 1;
209
210 /* check if bounding boxes intersect */
211 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
212 if ((by2 < ay1) || (ay2 < by1)) return 0;
213
214 /* define the remaining binding box */
215 inter_x0 = MAX( ax1, bx1 );
216 inter_x1 = MIN( ax2, bx2 );
217 inter_y0 = MAX( ay1, by1 );
218 inter_y1 = MIN( ay2, by2 );
219
220 /* real vertical sprite value (flipped) */
221 rbsy = bt->sy - bsy - 1;
222
223 /* set up the base points */
224 bbx = bsx*(int)(bt->sw) - bx1;
225 bby = rbsy*(int)(bt->sh) - by1;
226 for (y=inter_y0; y<=inter_y1; y++) {
227 for (x=inter_x0; x<=inter_x1; x++) {
228 /* compute offsets for surface before pass to TransparentPixel test */
229 if ((!gl_isTrans(bt, bbx + x, bby + y))) {
230 if (pointInPolygon( at, ap, (float)x, (float)y )) {
231 crash->x = x;
232 crash->y = y;
233 return 1;
234 }
235 }
236 }
237 }
238
239 return 0;
240}
241
254int CollidePolygon( const CollPoly* at, const vec2* ap,
255 const CollPoly* bt, const vec2* bp, vec2* crash )
256{
257 int ax1,ax2, ay1,ay2;
258 int bx1,bx2, by1,by2;
259 int inter_x0, inter_x1, inter_y0, inter_y1;
260 float xabs, yabs, x1, y1, x2, y2;
261
262 /* a - cube coordinates */
263 ax1 = (int)VX(*ap) + (int)(at->xmin);
264 ay1 = (int)VY(*ap) + (int)(at->ymin);
265 ax2 = (int)VX(*ap) + (int)(at->xmax);
266 ay2 = (int)VY(*ap) + (int)(at->ymax);
267
268 /* b - cube coordinates */
269 bx1 = (int)VX(*bp) + (int)(bt->xmin);
270 by1 = (int)VY(*bp) + (int)(bt->ymin);
271 bx2 = (int)VX(*bp) + (int)(bt->xmax);
272 by2 = (int)VY(*bp) + (int)(bt->ymax);
273
274 /* check if bounding boxes intersect */
275 if ((bx2 < ax1) || (ax2 < bx1)) return 0;
276 if ((by2 < ay1) || (ay2 < by1)) return 0;
277
278 /* define the remaining binding box */
279 inter_x0 = MAX( ax1, bx1 );
280 inter_x1 = MIN( ax2, bx2 );
281 inter_y0 = MAX( ay1, by1 );
282 inter_y1 = MIN( ay2, by2 );
283
284 /* loop on the points of bt to see if one of them is in polygon at. */
285 for (int i=0; i<=bt->npt-1; i++) {
286 xabs = bt->x[i] + VX(*bp);
287 yabs = bt->y[i] + VY(*bp);
288
289 if ((xabs<inter_x0) || (xabs>inter_x1) ||
290 (yabs<inter_y0) || (yabs>inter_y1)) {
291 if (pointInPolygon( at, ap, xabs, yabs )) {
292 crash->x = (int)xabs;
293 crash->y = (int)yabs;
294 return 1;
295 }
296 }
297 }
298
299 /* loop on the lines of bt to see if one of them intersects a line of at. */
300 x1 = bt->x[0] + VX(*bp);
301 y1 = bt->y[0] + VY(*bp);
302 x2 = bt->x[bt->npt-1] + VX(*bp);
303 y2 = bt->y[bt->npt-1] + VY(*bp);
304 if (LineOnPolygon( at, ap, x1, y1, x2, y2, crash ))
305 return 1;
306 for (int i=0; i<=bt->npt-2; i++) {
307 x1 = bt->x[i] + VX(*bp);
308 y1 = bt->y[i] + VY(*bp);
309 x2 = bt->x[i+1] + VX(*bp);
310 y2 = bt->y[i+1] + VY(*bp);
311 if ( LineOnPolygon( at, ap, x1, y1, x2, y2, crash ) )
312 return 1;
313 }
314
315 return 0;
316}
317
325void RotatePolygon( CollPoly* rpolygon, CollPoly* ipolygon, float theta )
326{
327 float ct, st, d;
328
329 rpolygon->npt = ipolygon->npt;
330 rpolygon->x = malloc( ipolygon->npt*sizeof(float) );
331 rpolygon->y = malloc( ipolygon->npt*sizeof(float) );
332 rpolygon->xmin = 0;
333 rpolygon->xmax = 0;
334 rpolygon->ymin = 0;
335 rpolygon->ymax = 0;
336
337 ct = cos( theta );
338 st = sin( theta );
339
340 for (int i=0; i<=rpolygon->npt-1; i++) {
341 d = ipolygon->x[i] * ct - ipolygon->y[i] * st;
342 rpolygon->x[i] = d;
343 rpolygon->xmin = MIN( rpolygon->xmin, d );
344 rpolygon->xmax = MAX( rpolygon->xmax, d );
345
346 d = ipolygon->x[i] * st + ipolygon->y[i] * ct ;
347 rpolygon->y[i] = d;
348 rpolygon->ymin = MIN( rpolygon->ymin, d );
349 rpolygon->ymax = MAX( rpolygon->ymax, d );
350 }
351}
352
362int pointInPolygon( const CollPoly* at, const vec2* ap,
363 float x, float y )
364{
365 float vprod, sprod, angle;
366 float dxi, dxip, dyi, dyip;
367
368 /* See if the pixel is inside the polygon:
369 We increment the angle when doing a loop along all the points
370 If the final angle is 0, we are outside the polygon
371 Otherwise, the angle should be +/- 2pi*/
372 angle = 0.0;
373 for (int i=0; i<=at->npt-2; i++) {
374 dxi = at->x[i] +VX(*ap)-x;
375 dxip = at->x[i+1]+VX(*ap)-x;
376 dyi = at->y[i] +VY(*ap)-y;
377 dyip = at->y[i+1]+VY(*ap)-y;
378 sprod = dxi * dxip + dyi * dyip;
379 vprod = dxi * dyip - dyi * dxip;
380 angle += atan2(vprod, sprod);
381 }
382 dxi = at->x[at->npt-1] + VX(*ap) - x;
383 dxip = at->x[0] + VX(*ap) - x;
384 dyi = at->y[at->npt-1] + VY(*ap)- y;
385 dyip = at->y[0] + VY(*ap) - y;
386 sprod = dxi * dxip + dyi * dyip;
387 vprod = dxi * dyip - dyi * dxip;
388 angle += atan2(vprod, sprod);
389
390 if (FABS(angle) < 1e-5)
391 return 0;
392
393 return 1;
394}
395
408int LineOnPolygon( const CollPoly* at, const vec2* ap,
409 float x1, float y1, float x2, float y2, vec2* crash )
410{
411 float xi, xip, yi, yip;
412
413 /* In this function, we are only looking for one collision point. */
414
415 xi = at->x[at->npt-1] + ap->x;
416 xip = at->x[0] + ap->x;
417 yi = at->y[at->npt-1] + ap->y;
418 yip = at->y[0] + ap->y;
419 if ( CollideLineLine(x1, y1, x2, y2, xi, yi, xip, yip, crash) == 1 )
420 return 1;
421 for (int i=0; i<=at->npt-2; i++) {
422 xi = at->x[i] + ap->x;
423 xip = at->x[i+1] + ap->x;
424 yi = at->y[i] + ap->y;
425 yip = at->y[i+1] + ap->y;
426 if ( CollideLineLine(x1, y1, x2, y2, xi, yi, xip, yip, crash) == 1 )
427 return 1;
428 }
429
430 return 0;
431}
432
448int CollideLineLine( double s1x, double s1y, double e1x, double e1y,
449 double s2x, double s2y, double e2x, double e2y, vec2* crash )
450{
451 double ua_t, ub_t, u_b;
452 double ua, ub;
453
454 ua_t = (e2x - s2x) * (s1y - s2y) - (e2y - s2y) * (s1x - s2x);
455 ub_t = (e1x - s1x) * (s1y - s2y) - (e1y - s1y) * (s1x - s2x);
456 u_b = (e2y - s2y) * (e1x - s1x) - (e2x - s2x) * (e1y - s1y);
457
458 if (u_b != 0.) {
459 ua = ua_t / u_b;
460 ub = ub_t / u_b;
461
462 /* Intersection at a point. */
463 if ((0. <= ua) && (ua <= 1.) && (0. <= ub) && (ub <= 1.)) {
464 crash->x = s1x + ua * (e1x - s1x);
465 crash->y = s1y + ua * (e1y - s1y);
466 return 1;
467 }
468 /* No intersection. */
469 else
470 return 0;
471 }
472 else {
473 /* Coincident. */
474 if ((ua_t == 0.) || (ub_t == 0.))
475 return 3;
476 /* Parallel. */
477 else
478 return 2;
479 }
480}
481
501int CollideLineSprite( const vec2* ap, double ad, double al,
502 const glTexture* bt, const int bsx, const int bsy, const vec2* bp,
503 vec2 crash[2] )
504{
505 int x,y, rbsy, bbx,bby;
506 double ep[2], bl[2], tr[2], v[2], mod;
507 int hits, real_hits;
508 vec2 tmp_crash, border[2];
509
510 /* Make sure texture has transparency map. */
511 if (bt->trans == NULL) {
512 WARN(_("Texture '%s' has no transparency map"), bt->name);
513 return 0;
514 }
515
516 /* Set up end point of line. */
517 ep[0] = ap->x + al*cos(ad);
518 ep[1] = ap->y + al*sin(ad);
519
520 /* Set up top right corner of the rectangle. */
521 tr[0] = bp->x + bt->sw/2.;
522 tr[1] = bp->y + bt->sh/2.;
523 /* Set up bottom left corner of the rectangle. */
524 bl[0] = bp->x - bt->sw/2.;
525 bl[1] = bp->y - bt->sh/2.;
526
527 /*
528 * Start check for rectangular collisions.
529 */
530 hits = 0;
531 /* Left border. */
532 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
533 bl[0], bl[1], bl[0], tr[1], &tmp_crash) == 1) {
534 border[hits].x = tmp_crash.x;
535 border[hits].y = tmp_crash.y;
536 hits++;
537 }
538 /* Top border. */
539 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
540 bl[0], tr[1], tr[0], tr[1], &tmp_crash) == 1) {
541 border[hits].x = tmp_crash.x;
542 border[hits].y = tmp_crash.y;
543 hits++;
544 }
545 /* Now we have to make sure hits isn't 2. */
546 /* Right border. */
547 if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
548 tr[0], tr[1], tr[0], bl[1], &tmp_crash) == 1) {
549 border[hits].x = tmp_crash.x;
550 border[hits].y = tmp_crash.y;
551 hits++;
552 }
553 /* Bottom border. */
554 if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
555 tr[0], bl[1], bl[0], bl[1], &tmp_crash) == 1) {
556 border[hits].x = tmp_crash.x;
557 border[hits].y = tmp_crash.y;
558 hits++;
559 }
560
561 /* No hits - missed. */
562 if (hits == 0)
563 return 0;
564
565 /* Beam must die in the rectangle. */
566 if (hits == 1) {
567 border[1].x = ep[0];
568 border[1].y = ep[1];
569 }
570
571 /*
572 * Now we do a pixel perfect approach.
573 */
574 real_hits = 0;
575 /* Directionality vector (normalized). */
576 v[0] = border[1].x - border[0].x;
577 v[1] = border[1].y - border[0].y;
578 /* Normalize. */
579 mod = MOD(v[0],v[1])/2.; /* Multiply by two to reduce check amount. */
580 v[0] /= mod;
581 v[1] /= mod;
582
583 /* real vertical sprite value (flipped) */
584 rbsy = bt->sy - bsy - 1;
585 /* set up the base points */
586 bbx = bsx*(int)(bt->sw);
587 bby = rbsy*(int)(bt->sh);
588
589 /* We start checking first border until we find collision. */
590 x = border[0].x - bl[0] + v[0];
591 y = border[0].y - bl[1] + v[1];
592 while ((x > 0.) && (x < bt->sw) && (y > 0.) && (y < bt->sh)) {
593 /* Is non-transparent. */
594 if (!gl_isTrans(bt, bbx+(int)x, bby+(int)y)) {
595 crash[real_hits].x = x + bl[0];
596 crash[real_hits].y = y + bl[1];
597 real_hits++;
598 break;
599 }
600 x += v[0];
601 y += v[1];
602 }
603
604 /* Now we check the second border. */
605 x = border[1].x - bl[0] - v[0];
606 y = border[1].y - bl[1] - v[1];
607 while ((x > 0.) && (x < bt->sw) && (y > 0.) && (y < bt->sh)) {
608 /* Is non-transparent. */
609 if (!gl_isTrans(bt, bbx+(int)x, bby+(int)y)) {
610 crash[real_hits].x = x + bl[0];
611 crash[real_hits].y = y + bl[1];
612 real_hits++;
613 break;
614 }
615 x -= v[0];
616 y -= v[1];
617 }
618
619 /* Actually missed. */
620 if (real_hits == 0)
621 return 0;
622
623 /* Strange situation, should never happen but just in case we duplicate
624 * the hit. */
625 if (real_hits == 1) {
626 crash[1].x = crash[0].x;
627 crash[1].y = crash[0].y;
628 }
629
630 /* We hit. */
631 return 1;
632}
633
650int CollideLinePolygon( const vec2* ap, double ad, double al,
651 const CollPoly* bt, const vec2* bp, vec2 crash[2] )
652{
653 double ep[2], bl[2], tr[2];
654 double xi, yi, xip, yip;
655 int hits, real_hits;
656 vec2 tmp_crash;
657
658 /* Set up end point of line. */
659 ep[0] = ap->x + al*cos(ad);
660 ep[1] = ap->y + al*sin(ad);
661
662 real_hits = 0;
663 vectnull( &tmp_crash );
664
665 /* Check if the beginning point is inside polygon */
666 if (pointInPolygon( bt, bp, (float) ap->x, (float) ap->y )) {
667 crash[real_hits].x = ap->x;
668 crash[real_hits].y = ap->y;
669 real_hits++;
670 }
671
672 /* same thing for end point */
673 if (pointInPolygon( bt, bp, (float) ep[0], (float) ep[1] )) {
674 crash[real_hits].x = ep[0];
675 crash[real_hits].y = ep[1];
676 real_hits++;
677 }
678
679 /* If both are inside, we got the two collision points. */
680 if (real_hits == 2)
681 return 1;
682
683 /* None is inside, check if there is a chance of intersection */
684 if (real_hits == 0) {
685 /* Set up top right corner of the rectangle. */
686 tr[0] = bp->x + (double)bt->xmax;
687 tr[1] = bp->y + (double)bt->ymax;
688 /* Set up bottom left corner of the rectangle. */
689 bl[0] = bp->x + (double)bt->xmin;
690 bl[1] = bp->y + (double)bt->ymin;
691
692 /*
693 * Start check for rectangular collisions.
694 */
695 hits = 0;
696 /* Left border. */
697 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
698 bl[0], bl[1], bl[0], tr[1], &tmp_crash) == 1)
699 hits++;
700
701 /* Top border. */
702 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
703 bl[0], tr[1], tr[0], tr[1], &tmp_crash) == 1)
704 hits++;
705
706 /* Right border. */
707 if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
708 tr[0], tr[1], tr[0], bl[1], &tmp_crash) == 1)
709 hits++;
710
711 /* Bottom border. */
712 if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
713 tr[0], bl[1], bl[0], bl[1], &tmp_crash) == 1)
714 hits++;
715
716 /* No hits - missed. No need to go further */
717 if (hits == 0)
718 return 0;
719 }
720
721 /*
722 * Now we check any line of the polygon
723 */
724 xi = (double)bt->x[bt->npt-1] + bp->x;
725 xip = (double)bt->x[0] + bp->x;
726 yi = (double)bt->y[bt->npt-1] + bp->y;
727 yip = (double)bt->y[0] + bp->y;
728 if ( CollideLineLine(ap->x, ap->y, ep[0], ep[1],
729 xi, yi, xip, yip, &tmp_crash) ) {
730 crash[real_hits].x = tmp_crash.x;
731 crash[real_hits].y = tmp_crash.y;
732 real_hits++;
733 if (real_hits == 2)
734 return 1;
735 }
736 for (int i=0; i<=bt->npt-2; i++) {
737 xi = (double)bt->x[i] + bp->x;
738 xip = (double)bt->x[i+1] + bp->x;
739 yi = (double)bt->y[i] + bp->y;
740 yip = (double)bt->y[i+1] + bp->y;
741 if ( CollideLineLine(ap->x, ap->y, ep[0], ep[1],
742 xi, yi, xip, yip, &tmp_crash) ) {
743 crash[real_hits].x = tmp_crash.x;
744 crash[real_hits].y = tmp_crash.y;
745 real_hits++;
746 if (real_hits == 2)
747 return 1;
748 }
749 }
750
751 /* Actually missed. */
752 if (real_hits == 0)
753 return 0;
754
755 /* Strange situation, should never happen but just in case we duplicate
756 * the hit. */
757 if (real_hits == 1) {
758 crash[1].x = crash[0].x;
759 crash[1].y = crash[0].y;
760 }
761
762 /* We hit. */
763 return 1;
764}
765
766static int linePointOnSegment( double d1, double x1, double y1, double x2, double y2, double x, double y )
767{
768 //double d1 = hypot( x2-x1, y2-y1 ); /* Distance between end-points. */
769 double d2 = hypot( x-x1, y-y1 ); /* Distance from point to one end. */
770 double d3 = hypot( x2-x, y2-y ); /* Distance to the other end. */
771 return fabs(d1 - d2 - d3) < 1e-8; /* True if smaller than some tolerance. */
772}
773
774#define FX( A, B, C, x ) (-(A * x + C) / B)
775#define FY( A, B, C , y ) (-(B * y + C) / A)
786int CollideLineCircle( const vec2* p1, const vec2* p2,
787 const vec2 *cc, double cr, vec2 crash[2] )
788{
789 double x0 = cc->x;
790 double y0 = cc->y;
791 double x1 = p1->x;
792 double y1 = p1->y;
793 double x2 = p2->x;
794 double y2 = p2->y;
795
796 double A = y2 - y1;
797 double B = x1 - x2;
798 double C = x2 * y1 - x1 * y2;
799
800 double a = pow2(A) + pow2(B);
801 double b, c, d;
802
803 int bnz, cnt;
804
805 double x, y, d1;
806
807 /* Non-vertical case. */
808 if (fabs(B) >= 1e-8) {
809 b = 2. * (A * C + A * B * y0 - pow2(B) * x0);
810 c = pow2(C) + 2. * B * C * y0 - pow2(B) * (pow2(cr) - pow2(x0) - pow2(y0));
811 bnz = 1;
812 }
813 /* Have to have special care when line is vertical. */
814 else {
815 b = 2. * (B * C + A * B * x0 - pow2(A) * y0);
816 c = pow2(C) + 2. * A * C * x0 - pow2(A) * (pow2(cr) - pow2(x0) - pow2(y0));
817 bnz = 0;
818 }
819 d = pow2(b) - 4. * a * c; /* Discriminant. */
820 if (d < 0.)
821 return 0;
822
823 cnt = 0;
824 d1 = hypot( x2-x1, y2-y1 );
825 /* Line is tangent, so only one intersection. */
826 if (d == 0.) {
827 if (bnz) {
828 x = -b / (2. * a);
829 y = FX(A, B, C, x);
830 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
831 crash[cnt].x = x;
832 crash[cnt].y = y;
833 cnt++;
834 }
835 } else {
836 y = -b / (2. * a);
837 x = FY(A, B, C, y);
838 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
839 crash[cnt].x = x;
840 crash[cnt].y = y;
841 cnt++;
842 }
843 }
844 }
845 /* Two intersections. */
846 else {
847 d = sqrt(d);
848 if (bnz) {
849 x = (-b + d) / (2. * a);
850 y = FX(A, B, C, x);
851 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
852 crash[cnt].x = x;
853 crash[cnt].y = y;
854 cnt++;
855 }
856 x = (-b - d) / (2. * a);
857 y = FX(A, B, C, x);
858 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
859 crash[cnt].x = x;
860 crash[cnt].y = y;
861 cnt++;
862 }
863 } else {
864 y = (-b + d) / (2. * a);
865 x = FY(A, B, C, y);
866 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
867 crash[cnt].x = x;
868 crash[cnt].y = y;
869 cnt++;
870 }
871 y = (-b - d) / (2. * a);
872 x = FY(A, B, C, y);
873 if (linePointOnSegment( d1, x1, y1, x2, y2, x, y )) {
874 crash[cnt].x = x;
875 crash[cnt].y = y;
876 cnt++;
877 }
878 }
879 }
880 return cnt;
881}
882#undef FX
883#undef FY
884
887double CollideCircleIntersection( const vec2 *p1, double r1,
888 const vec2 *p2, double r2 )
889{
890 double dist2 = vec2_dist2( p1, p2 );
891
892 /* No intersection. */
893 if (dist2 > pow2(r1+r2))
894 return 0.;
895
896 /* One inside the other. */
897 if (dist2 <= pow2(fabs(r1-r2)))
898 return M_PI * pow2( MIN(r1, r2) );
899
900#if 0
901 /* Case exactly the same. */
902 if ((dist2==0.) && (r1==r2))
903 return M_PI * pow2(r1);
904#endif
905
906 /* Distances. */
907 double dist = sqrt( dist2 );
908 double distc1 = (pow2(r1) - pow2(r2) + dist2) / (2. * dist); /* First center point to middle line. */
909 double distc2 = dist - distc1; /* Second center point to middle line. */
910 double height = sqrt( pow2(r1) - pow2(distc1) ); /* Half of middle line. */
911 /* Angles. */
912 double ang1 = fmod( atan2( height, distc1 ) * 2. + 2.*M_PI, 2.*M_PI ); /* Center angle for first circle. */
913 double ang2 = fmod( atan2( height, distc2 ) * 2. + 2.*M_PI, 2.*M_PI ); /*< Center angle for second circle. */
914 /* Areas. */
915 double A1 = pow2(r1) / 2.0 * (ang1 - sin(ang1)); /* Area of first circula segment. */
916 double A2 = pow2(r2) / 2.0 * (ang2 - sin(ang2)); /* Area of second circula segment. */
917
918 return A1+A2;
919}
RotatePolygon
void RotatePolygon(CollPoly *rpolygon, CollPoly *ipolygon, float theta)
Rotates a polygon.
Definition: collision.c:325
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:786
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:650
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:501
LoadPolygon
void LoadPolygon(CollPoly *polygon, xmlNodePtr node)
Loads a polygon from an xml node.
Definition: collision.c:32
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:448
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:97
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:408
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:179
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:254
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:362
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:838
c
static const double c[]
Definition: rng.c:264
a
static const double a[]
Definition: rng.c:247
d
static const double d[]
Definition: rng.c:273
b
static const double b[]
Definition: rng.c:256
C
static cholmod_common C
Definition: safelanes.c:92
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:34
glTexture::sw
double sw
Definition: opengl_tex.h:44
glTexture::trans
uint8_t * trans
Definition: opengl_tex.h:51
glTexture::sh
double sh
Definition: opengl_tex.h:45
glTexture::name
char * name
Definition: opengl_tex.h:35
glTexture::sy
double sy
Definition: opengl_tex.h:43
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.9.3