home *** CD-ROM | disk | FTP | other *** search
/ Enter 2005 March / ENTER.ISO / files / fwp-0.0.6-win32-installer.exe / intersection.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2005-01-21  |  44.8 KB  |  1,412 lines
  1. /*!
  2. \file intersection.cpp
  3. \author Karsten Schwenk
  4.  
  5. See header for description (intersection.h).
  6. */
  7.  
  8.  
  9. #include "intersection.h"
  10.  
  11. #include <math.h>
  12. //#include <stdio.h>
  13.  
  14. #define INTERSECTION_EPSILON    0.001
  15.  
  16. bool pointIntersectsPlane(vec3_t point, vec4_t plane){
  17.     return fabs(vectorDotP3d(point, plane)-plane[3]) < INTERSECTION_EPSILON;
  18. }
  19.  
  20. bool pointIntersectsTriangle(vec3_t point, vec3_t p1, vec3_t p2, vec3_t p3){
  21.     vec4_t plane;
  22.     vec3_t p1p2, p1p3, p2p3;
  23.     vec3_t p1point, p2point;//, p3point;
  24.     vec3_t c1,c2;
  25.  
  26.     vectorSub3d(p2, p1, p1p2);
  27.     vectorSub3d(p3, p1, p1p3);
  28.     vectorSub3d(p3, p2, p2p3);
  29.  
  30.     vectorCrossP3d(p1p2, p1p3, plane);
  31.     vectorNormalize3d(plane, plane);
  32.     plane[3]=vectorDotP3d(p1, plane);
  33.  
  34.     if(fabs(vectorDotP3d(point, plane)-plane[3]) > INTERSECTION_EPSILON)
  35.         return false;
  36.  
  37.     vectorSub3d(point, p1, p1point);
  38.     vectorCrossP3d(p1p2, p1p3, c1);
  39.     vectorCrossP3d(p1p2, p1point, c2);
  40.     if(vectorDotP3d(c1,c2) < 0.0)
  41.         return false;
  42.  
  43. //    vectorSub3d(point, p1, p1point);
  44.     vectorCrossP3d(p1p3, p1p2, c1);
  45.     vectorCrossP3d(p1p3, p1point, c2);
  46.     if(vectorDotP3d(c1,c2) < 0.0)
  47.         return false;
  48.  
  49.  
  50.     vectorScale3d(-1.0f, p1p2, p1p2);
  51.     vectorSub3d(point, p2, p2point);
  52.     vectorCrossP3d(p2p3, p1p2, c1);
  53.     vectorCrossP3d(p2p3, p2point, c2);
  54.     if(vectorDotP3d(c1,c2) < 0.0)
  55.         return false;
  56.  
  57.     return true;
  58. }
  59.  
  60. bool pointIntersectsSphere(vec3_t point, vec3_t center, float radius){
  61.     return vectorPointDistance3d(point, center) <= radius;
  62. }
  63.  
  64. bool pointIntersectsCube(vec3_t point, vec3_t center, float edgelength){
  65.     double l=edgelength*0.5;
  66.  
  67.     return (point[0]>center[0]-l && point[0]<center[0]+l
  68.         && point[1]>center[1]-l && point[1]<center[1]+l
  69.         && point[2]>center[2]-l && point[2]<center[2]+l);
  70. }
  71. bool pointIntersectsBox(vec3_t point, vec3_t center, vec3_t edgelengths){
  72.     double l0=edgelengths[0]*0.5;
  73.     double l1=edgelengths[1]*0.5;
  74.     double l2=edgelengths[2]*0.5;
  75.  
  76.     return (point[0]>center[0]-l0 && point[0]<center[0]+l0
  77.         && point[1]>center[1]-l1 && point[1]<center[1]+l1
  78.         && point[2]>center[2]-l2 && point[2]<center[2]+l2);
  79. }
  80. bool pointIntersectsAABB(vec3_t point, vec3_t min, vec3_t max){
  81.  
  82.     return (point[0]>=min[0] && point[0]<=max[0]
  83.         && point[1]>=min[1] && point[1]<=max[1]
  84.         && point[2]>=min[2] && point[2]<=max[2]);
  85. }
  86.  
  87. bool lineIntersectsPlane(vec3_t pos, vec3_t dir, vec4_t plane){
  88.     double xd=vectorDotP3d(plane, dir);
  89.  
  90.     return (xd!=0.0);
  91. }
  92.  
  93. bool lineIntersectsPlane(vec3_t pos, vec3_t dir, vec4_t plane, float* distance, vec3_t hitpoint){
  94.     double xd=vectorDotP3d(plane, dir);
  95.  
  96.     if(xd==0.0)
  97.         return false;
  98.  
  99.     *distance=(float)( (plane[3]-vectorDotP3d(plane, pos))/xd );
  100.     vectorMA3d(pos, *distance, dir, hitpoint);
  101.  
  102.     return true;
  103. }
  104.  
  105. bool lineIntersectsTriangle(vec3_t pos, vec3_t dir, vec3_t p1, vec3_t p2, vec3_t p3){
  106.     vec4_t plane;
  107.     vec3_t p1p2, p1p3, p2p3;
  108.     vec3_t p1point, p2point;
  109.     vec3_t c1,c2;
  110.     vec3_t hitpoint;
  111.  
  112.     vectorSub3d(p2, p1, p1p2);
  113.     vectorSub3d(p3, p1, p1p3);
  114.     vectorSub3d(p3, p2, p2p3);
  115.  
  116.     vectorCrossP3d(p1p2, p1p3, plane);
  117.     vectorNormalize3d(plane, plane);
  118.     plane[3]=vectorDotP3d(p1, plane);
  119.  
  120.     double xd=vectorDotP3d(plane, dir);
  121.  
  122.     if(xd==0.0)
  123.         return false;
  124.  
  125.     float distance=(float)( (plane[3]-vectorDotP3d(plane, pos))/xd );
  126.     vectorMA3d(pos, distance, dir, hitpoint);
  127.  
  128.     // check if hitpoint is in triangle
  129.     vectorSub3d(hitpoint, p1, p1point);
  130.     vectorCrossP3d(p1p2, p1p3, c1);
  131.     vectorCrossP3d(p1p2, p1point, c2);
  132.     if(vectorDotP3d(c1,c2) < 0.0)
  133.         return false;
  134.  
  135. //    vectorSub3d(point, p1, p1point);
  136.     vectorCrossP3d(p1p3, p1p2, c1);
  137.     vectorCrossP3d(p1p3, p1point, c2);
  138.     if(vectorDotP3d(c1,c2) < 0.0)
  139.         return false;
  140.  
  141.     vectorScale3d(-1.0f, p1p2, p1p2);
  142.     vectorSub3d(hitpoint, p2, p2point);
  143.     vectorCrossP3d(p2p3, p1p2, c1);
  144.     vectorCrossP3d(p2p3, p2point, c2);
  145.     if(vectorDotP3d(c1,c2) < 0.0)
  146.         return false;
  147.  
  148.     return true;
  149. }
  150.  
  151. bool lineIntersectsTriangle(vec3_t pos, vec3_t dir, vec3_t p1, vec3_t p2, vec3_t p3, float* distance, vec3_t hitpoint){
  152.     vec4_t plane;
  153.     vec3_t p1p2, p1p3, p2p3;
  154.     vec3_t p1point, p2point;
  155.     vec3_t c1,c2;
  156.  
  157.     vectorSub3d(p2, p1, p1p2);
  158.     vectorSub3d(p3, p1, p1p3);
  159.     vectorSub3d(p3, p2, p2p3);
  160.  
  161.     vectorCrossP3d(p1p2, p1p3, plane);
  162.     vectorNormalize3d(plane, plane);
  163.     plane[3]=vectorDotP3d(p1, plane);
  164.  
  165.     double xd=vectorDotP3d(plane, dir);
  166.  
  167.     if(xd==0.0)
  168.         return false;
  169.  
  170.     *distance=(float)( (plane[3]-vectorDotP3d(plane, pos))/xd );
  171.     vectorMA3d(pos, *distance, dir, hitpoint);
  172.  
  173.     // check if hitpoint is in triangle
  174.     vectorSub3d(hitpoint, p1, p1point);
  175.     vectorCrossP3d(p1p2, p1p3, c1);
  176.     vectorCrossP3d(p1p2, p1point, c2);
  177.     if(vectorDotP3d(c1,c2) < 0.0)
  178.         return false;
  179.  
  180. //    vectorSub3d(point, p1, p1point);
  181.     vectorCrossP3d(p1p3, p1p2, c1);
  182.     vectorCrossP3d(p1p3, p1point, c2);
  183.     if(vectorDotP3d(c1,c2) < 0.0)
  184.         return false;
  185.  
  186.     vectorScale3d(-1.0f, p1p2, p1p2);
  187.     vectorSub3d(hitpoint, p2, p2point);
  188.     vectorCrossP3d(p2p3, p1p2, c1);
  189.     vectorCrossP3d(p2p3, p2point, c2);
  190.     if(vectorDotP3d(c1,c2) < 0.0)
  191.         return false;
  192.  
  193.     return true;
  194. }
  195.  
  196. bool lineIntersectsSphere(vec3_t pos, vec3_t dir, vec3_t center, float radius){
  197.     vec3_t h;
  198.     vectorSub3d(pos, center, h);
  199.     double a=vectorDotP3d(dir, dir);
  200.     double b=2.0f*vectorDotP3d(dir, h);
  201.     double c=radius+vectorDotP3d(h, h);
  202.  
  203.     double d=b*b - 4*a*c;
  204.  
  205.     return (d>=0.0);
  206. }
  207.  
  208. bool lineIntersectsSphere(vec3_t pos, vec3_t dir, vec3_t center, float radius, float* distance, vec3_t hitpoint){
  209.     vec3_t h;
  210.     vectorSub3d(pos, center, h);
  211.     double a=vectorDotP3d(dir, dir);
  212.     double b=2.0f*vectorDotP3d(dir, h);
  213.     double c=radius+vectorDotP3d(h, h);
  214.  
  215.     double d=b*b - 4*a*c;
  216.  
  217.     if(d<0.0)
  218.         return false;
  219.  
  220.     double x1=(-b+sqrt(d))/(2*a);
  221.     double x2=(-b-sqrt(d))/(2*a);
  222.  
  223.     *distance=(float)( x1<x2 ? x1 : x2 );
  224.     vectorMA3d(pos, *distance, dir, hitpoint);
  225.  
  226.     return true;
  227. }
  228.  
  229. bool lineIntersectsCube(vec3_t pos, vec3_t dir, vec3_t center, float edgelength){
  230.     vec3_t min, max;
  231.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  232.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  233.  
  234.     return lineIntersectsAABB(pos, dir, min, max);
  235. }
  236.  
  237. bool lineIntersectsCube(vec3_t pos, vec3_t dir, vec3_t center, float edgelength, float* distance, vec3_t hitpoint){
  238.     vec3_t min, max;
  239.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  240.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  241.  
  242.     return lineIntersectsAABB(pos, dir, min, max, distance, hitpoint);
  243. }
  244.  
  245. bool lineIntersectsBox(vec3_t pos, vec3_t dir, vec3_t center, vec3_t edgelengths){
  246.     vec3_t min, max;
  247.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  248.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  249.  
  250.     return lineIntersectsAABB(pos, dir, min, max);
  251. }
  252.  
  253. bool lineIntersectsBox(vec3_t pos, vec3_t dir, vec3_t center, vec3_t edgelengths, float* distance, vec3_t hitpoint){
  254.     vec3_t min, max;
  255.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  256.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  257.  
  258.     return lineIntersectsAABB(pos, dir, min, max, distance, hitpoint);
  259. }
  260.  
  261. bool lineIntersectsAABB(vec3_t pos, vec3_t dir, vec3_t min, vec3_t max){
  262.     vec4_t plane;
  263.     vec3_t hitpoint;
  264.     float distance;
  265.  
  266.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  267.     plane[3]=vectorDotP3d(max, plane);
  268.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  269.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  270.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  271.             return true;
  272.         }
  273.     }
  274.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  275.     plane[3]=vectorDotP3d(min, plane);
  276.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  277.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  278.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  279.             return true;
  280.         }
  281.     }
  282.  
  283.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  284.     plane[3]=vectorDotP3d(max, plane);
  285.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  286.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  287.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  288.             return true;
  289.         }
  290.     }
  291.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  292.     plane[3]=vectorDotP3d(min, plane);
  293.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  294.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  295.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  296.             return true;
  297.         }
  298.     }
  299.  
  300.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  301.     plane[3]=vectorDotP3d(max, plane);
  302.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  303.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  304.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  305.             return true;
  306.         }
  307.     }
  308.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  309.     plane[3]=vectorDotP3d(min, plane);
  310.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  311.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  312.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  313.             return true;
  314.         }
  315.     }
  316.  
  317.     return false;
  318. }
  319.  
  320. bool lineIntersectsAABB(vec3_t pos, vec3_t dir, vec3_t min, vec3_t max, float* distance, vec3_t hitpoint){
  321.     vec4_t plane;
  322.     vec3_t hp;
  323.     float d;
  324.     *distance=FLT_MAX;
  325.  
  326.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  327.     plane[3]=vectorDotP3d(max, plane);
  328.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  329.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  330.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON){
  331.             *distance = d < *distance ? d : *distance;
  332.         }
  333.     }
  334.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  335.     plane[3]=vectorDotP3d(min, plane);
  336.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  337.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  338.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON){
  339.             *distance = d < *distance ? d : *distance;
  340.         }
  341.     }
  342.  
  343.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  344.     plane[3]=vectorDotP3d(max, plane);
  345.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  346.         if(hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  347.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON){
  348.             *distance = d < *distance ? d : *distance;
  349.         }
  350.     }
  351.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  352.     plane[3]=vectorDotP3d(min, plane);
  353.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  354.         if(hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  355.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON){
  356.             *distance = d < *distance ? d : *distance;
  357.         }
  358.     }
  359.  
  360.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  361.     plane[3]=vectorDotP3d(max, plane);
  362.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  363.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  364.             && hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON){
  365.             *distance = d < *distance ? d : *distance;
  366.         }
  367.     }
  368.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  369.     plane[3]=vectorDotP3d(min, plane);
  370.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  371.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  372.             && hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON){
  373.             *distance = d < *distance ? d : *distance;
  374.         }
  375.     }
  376.  
  377.     if(*distance < FLT_MAX){
  378.         vectorMA3d(pos, *distance, dir, hitpoint);
  379.         return true;
  380.     }else{
  381.         return false;
  382.     }
  383. }
  384.  
  385.  
  386.  
  387.  
  388. bool linesegmentIntersectsPlane(vec3_t pos1, vec3_t pos2, vec4_t plane){
  389.     vec3_t dir;
  390.     vectorSub3d(pos2, pos1, dir);
  391.     
  392.     double xd=vectorDotP3d(plane, dir);
  393.  
  394.     if(xd==0.0)
  395.         return false;
  396.  
  397.     double distance= (plane[3]-vectorDotP3d(plane, pos1))/xd;
  398.  
  399.     return (distance>=0.0 && distance<=1.0);
  400. }
  401.  
  402. bool linesegmentIntersectsPlane(vec3_t pos1, vec3_t pos2, vec4_t plane, float* distance, vec3_t hitpoint){
  403.     vec3_t dir;
  404.     vectorSub3d(pos2, pos1, dir);
  405.     
  406.     double xd=vectorDotP3d(plane, dir);
  407.  
  408.     if(xd==0.0)
  409.         return false;
  410.  
  411.     *distance=(float)( (plane[3]-vectorDotP3d(plane, pos1))/xd );
  412.     if(*distance>=0.0 && *distance<=1.0){
  413.         vectorMA3d(pos1, *distance, dir, hitpoint);
  414.         return true;
  415.     }else{
  416.         return false;
  417.     }
  418. }
  419.  
  420. bool linesegmentIntersectsTriangle(vec3_t pos1, vec3_t pos2, vec3_t p1, vec3_t p2, vec3_t p3){
  421.     vec3_t dir;
  422.     vec4_t plane;
  423.     vec3_t p1p2, p1p3, p2p3;
  424.     vec3_t p1point, p2point;
  425.     vec3_t c1,c2;
  426.     vec3_t hitpoint;
  427.  
  428.     vectorSub3d(pos2, pos1, dir);
  429.  
  430.     vectorSub3d(p2, p1, p1p2);
  431.     vectorSub3d(p3, p1, p1p3);
  432.     vectorSub3d(p3, p2, p2p3);
  433.  
  434.     vectorCrossP3d(p1p2, p1p3, plane);
  435.     vectorNormalize3d(plane, plane);
  436.     plane[3]=vectorDotP3d(p1, plane);
  437.  
  438.     double xd=vectorDotP3d(plane, dir);
  439.  
  440.     if(xd==0.0)
  441.         return false;
  442.  
  443.     float distance=(float)( (plane[3]-vectorDotP3d(plane, pos1))/xd );
  444.     if(distance<0.0 || distance>1.0)
  445.         return false;
  446.  
  447.     vectorMA3d(pos1, distance, dir, hitpoint);
  448.  
  449.     // check if hitpoint is in triangle
  450.     vectorSub3d(hitpoint, p1, p1point);
  451.     vectorCrossP3d(p1p2, p1p3, c1);
  452.     vectorCrossP3d(p1p2, p1point, c2);
  453.     if(vectorDotP3d(c1,c2) < 0.0)
  454.         return false;
  455.  
  456. //    vectorSub3d(point, p1, p1point);
  457.     vectorCrossP3d(p1p3, p1p2, c1);
  458.     vectorCrossP3d(p1p3, p1point, c2);
  459.     if(vectorDotP3d(c1,c2) < 0.0)
  460.         return false;
  461.  
  462.     vectorScale3d(-1.0f, p1p2, p1p2);
  463.     vectorSub3d(hitpoint, p2, p2point);
  464.     vectorCrossP3d(p2p3, p1p2, c1);
  465.     vectorCrossP3d(p2p3, p2point, c2);
  466.     if(vectorDotP3d(c1,c2) < 0.0)
  467.         return false;
  468.  
  469.     return true;
  470. }
  471.  
  472. bool linesegmentIntersectsTriangle(vec3_t pos1, vec3_t pos2, vec3_t p1, vec3_t p2, vec3_t p3, float* distance, vec3_t hitpoint){
  473.     vec3_t dir;
  474.     vec4_t plane;
  475.     vec3_t p1p2, p1p3, p2p3;
  476.     vec3_t p1point, p2point;
  477.     vec3_t c1,c2;
  478.  
  479.     vectorSub3d(pos2, pos1, dir);
  480.  
  481.     vectorSub3d(p2, p1, p1p2);
  482.     vectorSub3d(p3, p1, p1p3);
  483.     vectorSub3d(p3, p2, p2p3);
  484.  
  485.     vectorCrossP3d(p1p2, p1p3, plane);
  486.     vectorNormalize3d(plane, plane);
  487.     plane[3]=vectorDotP3d(p1, plane);
  488.  
  489.     double xd=vectorDotP3d(plane, dir);
  490.  
  491.     if(xd==0.0)
  492.         return false;
  493.  
  494.     *distance=(float)( (plane[3]-vectorDotP3d(plane, pos1))/xd );
  495.     if(*distance<0.0 || *distance>1.0)
  496.         return false;
  497.  
  498.     vectorMA3d(pos1, *distance, dir, hitpoint);
  499.  
  500.     // check if hitpoint is in triangle
  501.     vectorSub3d(hitpoint, p1, p1point);
  502.     vectorCrossP3d(p1p2, p1p3, c1);
  503.     vectorCrossP3d(p1p2, p1point, c2);
  504.     if(vectorDotP3d(c1,c2) < 0.0)
  505.         return false;
  506.  
  507. //    vectorSub3d(point, p1, p1point);
  508.     vectorCrossP3d(p1p3, p1p2, c1);
  509.     vectorCrossP3d(p1p3, p1point, c2);
  510.     if(vectorDotP3d(c1,c2) < 0.0)
  511.         return false;
  512.  
  513.     vectorScale3d(-1.0f, p1p2, p1p2);
  514.     vectorSub3d(hitpoint, p2, p2point);
  515.     vectorCrossP3d(p2p3, p1p2, c1);
  516.     vectorCrossP3d(p2p3, p2point, c2);
  517.     if(vectorDotP3d(c1,c2) < 0.0)
  518.         return false;
  519.  
  520.     return true;
  521. }
  522.  
  523. bool linesegmentIntersectsSphere(vec3_t pos1, vec3_t pos2, vec3_t center, float radius){
  524.     if(vectorPointDistance3d(pos1, center) <= radius || vectorPointDistance3d(pos1, center) <= radius)
  525.         return true;
  526.  
  527.     vec3_t dir;
  528.     vectorSub3d(pos2, pos1, dir);
  529.  
  530.     vec3_t h;
  531.     vectorSub3d(pos1, center, h);
  532.     double a=vectorDotP3d(dir, dir);
  533.     double b=2.0f*vectorDotP3d(dir, h);
  534.     double c=radius+vectorDotP3d(h, h);
  535.  
  536.     double d=b*b - 4*a*c;
  537.  
  538.     if(d<0.0)
  539.         return false;
  540.  
  541.     double x1=(-b+sqrt(d))/(2*a);
  542.     double x2=(-b-sqrt(d))/(2*a);
  543.  
  544.     return ( (x1>=0.0 && x1<=1.0) || ( x2>=0.0 && x2<=1.0) );
  545.  
  546. }
  547.  
  548. bool linesegmentIntersectsSphere(vec3_t pos1, vec3_t pos2, vec3_t center, float radius, float* distance, vec3_t hitpoint){
  549.     vec3_t dir;
  550.     vectorSub3d(pos2, pos1, dir);
  551.  
  552.     vec3_t h;
  553.     vectorSub3d(pos1, center, h);
  554.     double a=vectorDotP3d(dir, dir);
  555.     double b=2.0f*vectorDotP3d(dir, h);
  556.     double c=radius+vectorDotP3d(h, h);
  557.  
  558.     double d=b*b - 4*a*c;
  559.  
  560.     if(d<0.0)
  561.         return false;
  562.  
  563.     double x1=(-b+sqrt(d))/(2*a);
  564.     double x2=(-b-sqrt(d))/(2*a);
  565.  
  566.     if(x1>=0.0 && x1<=1.0 && x2>=0.0 && x2<=1.0){
  567.         *distance=(float)( x1 < x2 ? x1 : x2 );
  568.     }else if(x1>=0.0 && x1<=1.0){
  569.         *distance=(float)( x1 );
  570.     }else if(x2>=0.0 && x2<=1.0){
  571.         *distance=(float)( x2 );
  572.     }else{
  573.         // check if both points are inside the sphere
  574.         if(vectorPointDistance3d(pos1, center) <= radius && vectorPointDistance3d(pos1, center) <= radius){
  575.             return true;    // THINKABOUTME: besonderer Rⁿckgabewert?? - z.B. distance=0.0??
  576.         }else{
  577.             return false;
  578.         }
  579.     }
  580.  
  581.     vectorMA3d(pos1, *distance, dir, hitpoint);
  582.     return true;
  583.  
  584. }
  585.  
  586. bool linesegmentIntersectsCube(vec3_t pos1, vec3_t pos2, vec3_t center, float edgelength){
  587.     vec3_t min, max;
  588.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  589.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  590.  
  591.     return linesegmentIntersectsAABB(pos1, pos2, min, max);
  592. }
  593.  
  594. bool linesegmentIntersectsCube(vec3_t pos1, vec3_t pos2, vec3_t center, float edgelength, float* distance, vec3_t hitpoint){
  595.     vec3_t min, max;
  596.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  597.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  598.  
  599.     return linesegmentIntersectsAABB(pos1, pos2, min, max, distance, hitpoint);
  600. }
  601.  
  602. bool linesegmentIntersectsBox(vec3_t pos1, vec3_t pos2, vec3_t center, vec3_t edgelengths){
  603.     vec3_t min, max;
  604.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  605.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  606.  
  607.     return linesegmentIntersectsAABB(pos1, pos2, min, max);
  608. }
  609.  
  610. bool linesegmentIntersectsBox(vec3_t pos1, vec3_t pos2, vec3_t center, vec3_t edgelengths, float* distance, vec3_t hitpoint){
  611.     vec3_t min, max;
  612.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  613.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  614.  
  615.     return linesegmentIntersectsAABB(pos1, pos2, min, max, distance, hitpoint);
  616. }
  617.  
  618. bool linesegmentIntersectsAABB(vec3_t pos1, vec3_t pos2, vec3_t min, vec3_t max){
  619.     vec4_t plane;
  620.     vec3_t hitpoint;
  621.     float distance;
  622.     vec3_t dir;
  623.     vectorSub3d(pos2, pos1, dir);
  624.  
  625.     if(pointIntersectsAABB(pos1, min, max) || pointIntersectsAABB(pos2, min, max))    // one point in AABB
  626.         return true;
  627.  
  628.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  629.     plane[3]=vectorDotP3d(max, plane);
  630.     if(lineIntersectsPlane(pos1, dir, plane, &distance, hitpoint)){
  631.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  632.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  633.             && distance>=0.0 && distance<=1.0){
  634.             return true;
  635.         }
  636.     }
  637.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  638.     plane[3]=vectorDotP3d(min, plane);
  639.     if(lineIntersectsPlane(pos1, dir, plane, &distance, hitpoint)){
  640.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  641.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  642.             && distance>=0.0 && distance<=1.0){
  643.             return true;
  644.         }
  645.     }
  646.  
  647.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  648.     plane[3]=vectorDotP3d(max, plane);
  649.     if(lineIntersectsPlane(pos1, dir, plane, &distance, hitpoint)){
  650.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  651.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  652.             && distance>=0.0 && distance<=1.0){
  653.             return true;
  654.         }
  655.     }
  656.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  657.     plane[3]=vectorDotP3d(min, plane);
  658.     if(lineIntersectsPlane(pos1, dir, plane, &distance, hitpoint)){
  659.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  660.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  661.             && distance>=0.0 && distance<=1.0){
  662.             return true;
  663.         }
  664.     }
  665.  
  666.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  667.     plane[3]=vectorDotP3d(max, plane);
  668.     if(lineIntersectsPlane(pos1, dir, plane, &distance, hitpoint)){
  669.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  670.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  671.             && distance>=0.0 && distance<=1.0){
  672.             return true;
  673.         }
  674.     }
  675.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  676.     plane[3]=vectorDotP3d(min, plane);
  677.     if(lineIntersectsPlane(pos1, dir, plane, &distance, hitpoint)){
  678.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  679.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  680.             && distance>=0.0 && distance<=1.0){
  681.             return true;
  682.         }
  683.     }
  684.  
  685.     return false;
  686. }
  687.  
  688. bool linesegmentIntersectsAABB(vec3_t pos1, vec3_t pos2, vec3_t min, vec3_t max, float* distance, vec3_t hitpoint){
  689.     vec4_t plane;
  690.     vec3_t hp;
  691.     float d;
  692.     vec3_t dir;
  693.     vectorSub3d(pos2, pos1, dir);
  694.  
  695.     if(pointIntersectsAABB(pos1, min, max)){    // startPoint in AABB -> instant intersection
  696.         *distance=0.0f;
  697.         vectorCopy3d(pos1, hitpoint);
  698.         return true;
  699.     }
  700.  
  701.     *distance=FLT_MAX;
  702.  
  703.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  704.     plane[3]=vectorDotP3d(max, plane);
  705.     if(lineIntersectsPlane(pos1, dir, plane, &d, hp)){
  706.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  707.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  708.             && d>=0.0 && d<=1.0){
  709.             *distance = d < *distance ? d : *distance;
  710.         }
  711.     }
  712.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  713.     plane[3]=vectorDotP3d(min, plane);
  714.     if(lineIntersectsPlane(pos1, dir, plane, &d, hp)){
  715.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  716.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  717.             && d>=0.0 && d<=1.0){
  718.             *distance = d < *distance ? d : *distance;
  719.         }
  720.     }
  721.  
  722.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  723.     plane[3]=vectorDotP3d(max, plane);
  724.     if(lineIntersectsPlane(pos1, dir, plane, &d, hp)){
  725.         if(hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  726.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  727.             && d>=0.0 && d<=1.0){
  728.             *distance = d < *distance ? d : *distance;
  729.         }
  730.     }
  731.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  732.     plane[3]=vectorDotP3d(min, plane);
  733.     if(lineIntersectsPlane(pos1, dir, plane, &d, hp)){
  734.         if(hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  735.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  736.             && d>=0.0 && d<=1.0){
  737.             *distance = d < *distance ? d : *distance;
  738.         }
  739.     }
  740.  
  741.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  742.     plane[3]=vectorDotP3d(max, plane);
  743.     if(lineIntersectsPlane(pos1, dir, plane, &d, hp)){
  744.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  745.             && hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  746.             && d>=0.0 && d<=1.0){
  747.             *distance = d < *distance ? d : *distance;
  748.         }
  749.     }
  750.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  751.     plane[3]=vectorDotP3d(min, plane);
  752.     if(lineIntersectsPlane(pos1, dir, plane, &d, hp)){
  753.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  754.             && hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  755.             && d>=0.0 && d<=1.0){
  756.             *distance = d < *distance ? d : *distance;
  757.         }
  758.     }
  759.  
  760.     if(*distance < FLT_MAX){
  761.         vectorMA3d(pos1, *distance, dir, hitpoint);
  762.         return true;
  763.     }else{
  764.         return false;
  765.     }
  766. }
  767.  
  768.  
  769.  
  770.  
  771. bool rayIntersectsPlane(vec3_t pos, vec3_t dir, vec4_t plane){
  772.     double xd=vectorDotP3d(plane, dir);
  773.  
  774.     if(xd==0.0)
  775.         return false;
  776.  
  777.     return (plane[3]-vectorDotP3d(plane, pos))/xd >= 0.0;
  778. }
  779.  
  780. bool rayIntersectsPlane(vec3_t pos, vec3_t dir, vec4_t plane, float* distance, vec3_t hitpoint){
  781.     double xd=vectorDotP3d(plane, dir);
  782.  
  783.     if(xd==0.0)
  784.         return false;
  785.  
  786.     *distance=(float)( (plane[3]-vectorDotP3d(plane, pos))/xd );
  787.     if(*distance>=0.0){
  788.         vectorMA3d(pos, *distance, dir, hitpoint);
  789.         return true;
  790.     }else{
  791.         return false;
  792.     }
  793. }
  794.  
  795. bool rayIntersectsTriangle(vec3_t pos, vec3_t dir, vec3_t p1, vec3_t p2, vec3_t p3){
  796.     vec4_t plane;
  797.     vec3_t p1p2, p1p3, p2p3;
  798.     vec3_t p1point, p2point;
  799.     vec3_t c1,c2;
  800.     vec3_t hitpoint;
  801.  
  802.     vectorSub3d(p2, p1, p1p2);
  803.     vectorSub3d(p3, p1, p1p3);
  804.     vectorSub3d(p3, p2, p2p3);
  805.  
  806.     vectorCrossP3d(p1p2, p1p3, plane);
  807.     vectorNormalize3d(plane, plane);
  808.     plane[3]=vectorDotP3d(p1, plane);
  809.  
  810.     double xd=vectorDotP3d(plane, dir);
  811.  
  812.     if(xd==0.0)
  813.         return false;
  814.  
  815.     float distance=(float)( (plane[3]-vectorDotP3d(plane, pos))/xd );
  816.     if(distance<0.0)
  817.         return false;
  818.  
  819.     vectorMA3d(pos, distance, dir, hitpoint);
  820.  
  821.     // check if hitpoint is in triangle
  822.     vectorSub3d(hitpoint, p1, p1point);
  823.     vectorCrossP3d(p1p2, p1p3, c1);
  824.     vectorCrossP3d(p1p2, p1point, c2);
  825.     if(vectorDotP3d(c1,c2) < 0.0)
  826.         return false;
  827.  
  828. //    vectorSub3d(point, p1, p1point);
  829.     vectorCrossP3d(p1p3, p1p2, c1);
  830.     vectorCrossP3d(p1p3, p1point, c2);
  831.     if(vectorDotP3d(c1,c2) < 0.0)
  832.         return false;
  833.  
  834.     vectorScale3d(-1.0f, p1p2, p1p2);
  835.     vectorSub3d(hitpoint, p2, p2point);
  836.     vectorCrossP3d(p2p3, p1p2, c1);
  837.     vectorCrossP3d(p2p3, p2point, c2);
  838.     if(vectorDotP3d(c1,c2) < 0.0)
  839.         return false;
  840.  
  841.     return true;
  842. }
  843.  
  844. bool rayIntersectsTriangle(vec3_t pos, vec3_t dir, vec3_t p1, vec3_t p2, vec3_t p3, float* distance, vec3_t hitpoint){
  845.     vec4_t plane;
  846.     vec3_t p1p2, p1p3, p2p3;
  847.     vec3_t p1point, p2point;
  848.     vec3_t c1,c2;
  849.  
  850.     vectorSub3d(p2, p1, p1p2);
  851.     vectorSub3d(p3, p1, p1p3);
  852.     vectorSub3d(p3, p2, p2p3);
  853.  
  854.     vectorCrossP3d(p1p2, p1p3, plane);
  855.     vectorNormalize3d(plane, plane);
  856.     plane[3]=vectorDotP3d(p1, plane);
  857.  
  858.     double xd=vectorDotP3d(plane, dir);
  859.  
  860.     if(xd==0.0)
  861.         return false;
  862.  
  863.     *distance=(float)( (plane[3]-vectorDotP3d(plane, pos))/xd );
  864.     if(*distance<0.0)
  865.         return false;
  866.  
  867.     vectorMA3d(pos, *distance, dir, hitpoint);
  868.  
  869.     // check if hitpoint is in triangle
  870.     vectorSub3d(hitpoint, p1, p1point);
  871.     vectorCrossP3d(p1p2, p1p3, c1);
  872.     vectorCrossP3d(p1p2, p1point, c2);
  873.     if(vectorDotP3d(c1,c2) < 0.0)
  874.         return false;
  875.  
  876. //    vectorSub3d(point, p1, p1point);
  877.     vectorCrossP3d(p1p3, p1p2, c1);
  878.     vectorCrossP3d(p1p3, p1point, c2);
  879.     if(vectorDotP3d(c1,c2) < 0.0)
  880.         return false;
  881.  
  882.     vectorScale3d(-1.0f, p1p2, p1p2);
  883.     vectorSub3d(hitpoint, p2, p2point);
  884.     vectorCrossP3d(p2p3, p1p2, c1);
  885.     vectorCrossP3d(p2p3, p2point, c2);
  886.     if(vectorDotP3d(c1,c2) < 0.0)
  887.         return false;
  888.  
  889.     return true;
  890.  
  891. }
  892.  
  893. bool rayIntersectsSphere(vec3_t pos, vec3_t dir, vec3_t center, float radius){
  894.  
  895.     vec3_t h;
  896.     vectorSub3d(pos, center, h);
  897.     double a=vectorDotP3d(dir, dir);
  898.     double b=2.0f*vectorDotP3d(dir, h);
  899.     double c=radius+vectorDotP3d(h, h);
  900.  
  901.     double d=b*b - 4*a*c;
  902.  
  903.     if(d<0.0)
  904.         return false;
  905.  
  906.     double x1=(-b+sqrt(d))/(2*a);
  907.     double x2=(-b-sqrt(d))/(2*a);
  908.  
  909.     return ( (x1>=0.0) || ( x2>=0.0) );
  910. }
  911.  
  912. bool rayIntersectsSphere(vec3_t pos, vec3_t dir, vec3_t center, float radius, float* distance, vec3_t hitpoint){
  913.     vec3_t h;
  914.     vectorSub3d(pos, center, h);
  915.     double a=vectorDotP3d(dir, dir);
  916.     double b=2.0f*vectorDotP3d(dir, h);
  917.     double c=radius+vectorDotP3d(h, h);
  918.  
  919.     double d=b*b - 4*a*c;
  920.  
  921.     if(d<0.0)
  922.         return false;
  923.  
  924.     double x1=(-b+sqrt(d))/(2*a);
  925.     double x2=(-b-sqrt(d))/(2*a);
  926.  
  927.     if(x1>=0.0 && x2>=0.0){    // THINKABOUTME: besser machen
  928.         *distance=(float)( x1 < x2 ? x1 : x2 );
  929.     }else if(x1>=0.0){
  930.         *distance=(float)( x1 );
  931.     }else if(x2>=0.0){
  932.         *distance=(float)( x2 );
  933.     }else{
  934.         return false;
  935.     }
  936.  
  937.     vectorMA3d(pos, *distance, dir, hitpoint);
  938.     return true;
  939. }
  940.  
  941. bool rayIntersectsCube(vec3_t pos, vec3_t dir, vec3_t center, float edgelength){
  942.     vec3_t min, max;
  943.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  944.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  945.  
  946.     return rayIntersectsAABB(pos, dir, min, max);
  947. }
  948.  
  949. bool rayIntersectsCube(vec3_t pos, vec3_t dir, vec3_t center, float edgelength, float* distance, vec3_t hitpoint){
  950.     vec3_t min, max;
  951.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  952.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  953.  
  954.     return rayIntersectsAABB(pos, dir, min, max, distance, hitpoint);
  955. }
  956.  
  957. bool rayIntersectsBox(vec3_t pos, vec3_t dir, vec3_t center, vec3_t edgelengths){
  958.     vec3_t min, max;
  959.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  960.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  961.  
  962.     return rayIntersectsAABB(pos, dir, min, max);
  963. }
  964.  
  965. bool rayIntersectsBox(vec3_t pos, vec3_t dir, vec3_t center, vec3_t edgelengths, float* distance, vec3_t hitpoint){
  966.     vec3_t min, max;
  967.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  968.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  969.  
  970.     return rayIntersectsAABB(pos, dir, min, max, distance, hitpoint);
  971. }
  972.  
  973. bool rayIntersectsAABB(vec3_t pos, vec3_t dir, vec3_t min, vec3_t max){
  974.     vec4_t plane;
  975.     vec3_t hitpoint;
  976.     float distance;
  977.  
  978.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  979.     plane[3]=vectorDotP3d(max, plane);
  980.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  981.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  982.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  983.             && distance>=0.0){
  984.             return true;
  985.         }
  986.     }
  987.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  988.     plane[3]=vectorDotP3d(min, plane);
  989.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  990.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  991.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  992.             && distance>=0.0){
  993.             return true;
  994.         }
  995.     }
  996.  
  997.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  998.     plane[3]=vectorDotP3d(max, plane);
  999.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  1000.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1001.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  1002.             && distance>=0.0){
  1003.             return true;
  1004.         }
  1005.     }
  1006.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  1007.     plane[3]=vectorDotP3d(min, plane);
  1008.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  1009.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1010.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON
  1011.             && distance>=0.0){
  1012.             return true;
  1013.         }
  1014.     }
  1015.  
  1016.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  1017.     plane[3]=vectorDotP3d(max, plane);
  1018.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  1019.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1020.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1021.             && distance>=0.0){
  1022.             return true;
  1023.         }
  1024.     }
  1025.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  1026.     plane[3]=vectorDotP3d(min, plane);
  1027.     if(lineIntersectsPlane(pos, dir, plane, &distance, hitpoint)){
  1028.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1029.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1030.             && distance>=0.0){
  1031.             return true;
  1032.         }
  1033.     }
  1034.  
  1035.     return false;
  1036. }
  1037.  
  1038. bool rayIntersectsAABB(vec3_t pos, vec3_t dir, vec3_t min, vec3_t max, float* distance, vec3_t hitpoint){
  1039.     vec4_t plane;
  1040.     vec3_t hp;
  1041.     float d;
  1042.  
  1043.     *distance=FLT_MAX;
  1044.  
  1045.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  1046.     plane[3]=vectorDotP3d(max, plane);
  1047.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  1048.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  1049.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  1050.             && d>=0.0){
  1051.             *distance = d < *distance ? d : *distance;
  1052.         }
  1053.     }
  1054.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  1055.     plane[3]=vectorDotP3d(min, plane);
  1056.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  1057.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  1058.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  1059.             && d>=0.0){
  1060.             *distance = d < *distance ? d : *distance;
  1061.         }
  1062.     }
  1063.  
  1064.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  1065.     plane[3]=vectorDotP3d(max, plane);
  1066.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  1067.         if(hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  1068.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  1069.             && d>=0.0){
  1070.             *distance = d < *distance ? d : *distance;
  1071.         }
  1072.     }
  1073.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  1074.     plane[3]=vectorDotP3d(min, plane);
  1075.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  1076.         if(hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  1077.             && hp[2]>min[2]-INTERSECTION_EPSILON && hp[2]<max[2]+INTERSECTION_EPSILON
  1078.             && d>=0.0){
  1079.             *distance = d < *distance ? d : *distance;
  1080.         }
  1081.     }
  1082.  
  1083.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  1084.     plane[3]=vectorDotP3d(max, plane);
  1085.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  1086.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  1087.             && hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  1088.             && d>=0.0){
  1089.             *distance = d < *distance ? d : *distance;
  1090.         }
  1091.     }
  1092.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  1093.     plane[3]=vectorDotP3d(min, plane);
  1094.     if(lineIntersectsPlane(pos, dir, plane, &d, hp)){
  1095.         if(hp[1]>min[1]-INTERSECTION_EPSILON && hp[1]<max[1]+INTERSECTION_EPSILON
  1096.             && hp[0]>min[0]-INTERSECTION_EPSILON && hp[0]<max[0]+INTERSECTION_EPSILON
  1097.             && d>=0.0){
  1098.             *distance = d < *distance ? d : *distance;
  1099.         }
  1100.     }
  1101.  
  1102.     if(*distance < FLT_MAX){
  1103.         vectorMA3d(pos, *distance, dir, hitpoint);
  1104.         return true;
  1105.     }else{
  1106.         return false;
  1107.     }
  1108. }
  1109.  
  1110.  
  1111. bool triangleIntersectsTriangle(vec3_t p1_1, vec3_t p1_2, vec3_t p1_3, vec3_t p2_1, vec3_t p2_2, vec3_t p2_3){
  1112.     return false;
  1113. }
  1114.  
  1115. bool triangleIntersectsSphere(vec3_t p1, vec3_t p2, vec3_t p3, vec3_t center, float radius){
  1116.     if(vectorPointDistance3d(p1, center) <= radius)
  1117.         return true;
  1118.     if(vectorPointDistance3d(p2, center) <= radius)
  1119.         return true;
  1120.     if(vectorPointDistance3d(p3, center) <= radius)
  1121.         return true;
  1122.  
  1123.     if(linesegmentIntersectsSphere(p1, p2, center, radius))
  1124.         return true;
  1125.     if(linesegmentIntersectsSphere(p2, p3, center, radius))
  1126.         return true;
  1127.     if(linesegmentIntersectsSphere(p3, p1, center, radius))
  1128.         return true;
  1129.  
  1130.     // FIXME: dreieck umgibt kugel!
  1131.     return false;
  1132. }
  1133.  
  1134. bool triangleIntersectsCube(vec3_t p1, vec3_t p2, vec3_t p3, vec3_t center, float edgelength){
  1135.     vec3_t min, max;
  1136.  
  1137.     vectorInit3d(center[0]-edgelength, center[1]-edgelength, center[2]-edgelength, min);
  1138.     vectorInit3d(center[0]+edgelength, center[1]+edgelength, center[2]+edgelength, max);
  1139.  
  1140.     return triangleIntersectsAABB(p1, p2, p3, min, max);
  1141. }
  1142.  
  1143. bool triangleIntersectsBox(vec3_t p1, vec3_t p2, vec3_t p3, vec3_t center, vec3_t edgelengths){
  1144.     vec3_t min, max;
  1145.  
  1146.     vectorInit3d(center[0]-edgelengths[0], center[1]-edgelengths[1], center[2]-edgelengths[2], min);
  1147.     vectorInit3d(center[0]+edgelengths[0], center[1]+edgelengths[1], center[2]+edgelengths[2], max);
  1148.  
  1149.     return triangleIntersectsAABB(p1, p2, p3, min, max);
  1150. }
  1151.  
  1152. bool triangleIntersectsAABB(vec3_t p1, vec3_t p2, vec3_t p3, vec3_t min, vec3_t max){
  1153.  
  1154.     if(p1[0]>max[0] && p2[0]>max[0] && p3[0]>max[0])    // all points right of AABB
  1155.         return false;
  1156.     if(p1[0]<min[0] && p2[0]<min[0] && p3[0]<min[0])    // all points left of AABB
  1157.         return false;
  1158.     if(p1[1]>max[1] && p2[1]>max[1] && p3[1]>max[1])    // all points above AABB
  1159.         return false;
  1160.     if(p1[1]<min[1] && p2[1]<min[1] && p3[1]<min[1])    // all points below AABB
  1161.         return false;
  1162.     if(p1[2]>max[2] && p2[2]>max[2] && p3[2]>max[2])    // all points in front of AABB
  1163.         return false;
  1164.     if(p1[2]<min[2] && p2[2]<min[2] && p3[2]<min[2])    // all points behind AABB
  1165.         return false;
  1166.     
  1167.     if(pointIntersectsAABB(p1, min, max) || pointIntersectsAABB(p2, min, max) || pointIntersectsAABB(p3, min, max))    // point in AABB
  1168.         return true;
  1169.  
  1170.     // check edges of triangle against AABB faces
  1171.     vec4_t plane;
  1172.     float distance;
  1173.     vec3_t hitpoint;
  1174.  
  1175.     // right side
  1176.     vectorInit3d(1.0f, 0.0f, 0.0f, plane);
  1177.     plane[3]=vectorDotP3d(max, plane);
  1178.     if(linesegmentIntersectsPlane(p1, p2, plane, &distance, hitpoint)){
  1179.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON    // THINKABOUTME: geht auch ohne EPSILON
  1180.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1181.             return true;
  1182.         }
  1183.     }
  1184.     if(linesegmentIntersectsPlane(p2, p3, plane, &distance, hitpoint)){
  1185.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1186.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1187.             return true;
  1188.         }
  1189.     }
  1190.     if(linesegmentIntersectsPlane(p3, p1, plane, &distance, hitpoint)){
  1191.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1192.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1193.             return true;
  1194.         }
  1195.     }
  1196.  
  1197.     // left side
  1198.     vectorInit3d(-1.0f, 0.0f, 0.0f, plane);
  1199.     plane[3]=vectorDotP3d(min, plane);
  1200.     if(linesegmentIntersectsPlane(p1, p2, plane, &distance, hitpoint)){
  1201.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1202.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1203.             return true;
  1204.         }
  1205.     }
  1206.     if(linesegmentIntersectsPlane(p2, p3, plane, &distance, hitpoint)){
  1207.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1208.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1209.             return true;
  1210.         }
  1211.     }
  1212.     if(linesegmentIntersectsPlane(p3, p1, plane, &distance, hitpoint)){
  1213.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1214.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1215.             return true;
  1216.         }
  1217.     }
  1218.  
  1219.     // top side
  1220.     vectorInit3d(0.0f, 1.0f, 0.0f, plane);
  1221.     plane[3]=vectorDotP3d(max, plane);
  1222.     if(linesegmentIntersectsPlane(p1, p2, plane, &distance, hitpoint)){
  1223.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1224.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1225.             return true;
  1226.         }
  1227.     }
  1228.     if(linesegmentIntersectsPlane(p2, p3, plane, &distance, hitpoint)){
  1229.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1230.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1231.             return true;
  1232.         }
  1233.     }
  1234.     if(linesegmentIntersectsPlane(p3, p1, plane, &distance, hitpoint)){
  1235.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1236.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1237.             return true;
  1238.         }
  1239.     }
  1240.  
  1241.     // bottom side
  1242.     vectorInit3d(0.0f, -1.0f, 0.0f, plane);
  1243.     plane[3]=vectorDotP3d(min, plane);
  1244.     if(linesegmentIntersectsPlane(p1, p2, plane, &distance, hitpoint)){
  1245.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1246.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1247.             return true;
  1248.         }
  1249.     }
  1250.     if(linesegmentIntersectsPlane(p2, p3, plane, &distance, hitpoint)){
  1251.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1252.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1253.             return true;
  1254.         }
  1255.     }
  1256.     if(linesegmentIntersectsPlane(p3, p1, plane, &distance, hitpoint)){
  1257.         if(hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON
  1258.             && hitpoint[2]>min[2]-INTERSECTION_EPSILON && hitpoint[2]<max[2]+INTERSECTION_EPSILON){
  1259.             return true;
  1260.         }
  1261.     }
  1262.     
  1263.     // front side
  1264.     vectorInit3d(0.0f, 0.0f, 1.0f, plane);
  1265.     plane[3]=vectorDotP3d(max, plane);
  1266.     if(linesegmentIntersectsPlane(p1, p2, plane, &distance, hitpoint)){
  1267.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1268.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  1269.             return true;
  1270.         }
  1271.     }
  1272.     if(linesegmentIntersectsPlane(p2, p3, plane, &distance, hitpoint)){
  1273.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1274.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  1275.             return true;
  1276.         }
  1277.     }
  1278.     if(linesegmentIntersectsPlane(p3, p1, plane, &distance, hitpoint)){
  1279.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1280.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  1281.             return true;
  1282.         }
  1283.     }
  1284.  
  1285.     // back side
  1286.     vectorInit3d(0.0f, 0.0f, -1.0f, plane);
  1287.     plane[3]=vectorDotP3d(min, plane);
  1288.     if(linesegmentIntersectsPlane(p1, p2, plane, &distance, hitpoint)){
  1289.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1290.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  1291.             return true;
  1292.         }
  1293.     }
  1294.     if(linesegmentIntersectsPlane(p2, p3, plane, &distance, hitpoint)){
  1295.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1296.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  1297.             return true;
  1298.         }
  1299.     }
  1300.     if(linesegmentIntersectsPlane(p3, p1, plane, &distance, hitpoint)){
  1301.         if(hitpoint[1]>min[1]-INTERSECTION_EPSILON && hitpoint[1]<max[1]+INTERSECTION_EPSILON
  1302.             && hitpoint[0]>min[0]-INTERSECTION_EPSILON && hitpoint[0]<max[0]+INTERSECTION_EPSILON){
  1303.             return true;
  1304.         }
  1305.     }
  1306.  
  1307.  
  1308.     // check edges of AABB against triangle
  1309.     // THINKABOUTME: geht auch schneller
  1310.  
  1311.     // bottom to top
  1312.     vec3_t point1, point2;
  1313.     vectorInit3d(min[0], min[1], min[2], point1);
  1314.     vectorInit3d(min[0], max[1], min[2], point2);
  1315.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1316.         return true;
  1317.  
  1318.     vectorInit3d(max[0], min[1], min[2], point1);
  1319.     vectorInit3d(max[0], max[1], min[2], point2);
  1320.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1321.         return true;
  1322.  
  1323.     vectorInit3d(max[0], min[1], max[2], point1);
  1324.     vectorInit3d(max[0], max[1], max[2], point2);
  1325.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1326.         return true;
  1327.  
  1328.     vectorInit3d(min[0], min[1], max[2], point1);
  1329.     vectorInit3d(min[0], max[1], max[2], point2);
  1330.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1331.         return true;
  1332.  
  1333.     // back to front
  1334.     vectorInit3d(min[0], min[1], min[2], point1);
  1335.     vectorInit3d(min[0], min[1], max[2], point2);
  1336.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1337.         return true;
  1338.  
  1339.     vectorInit3d(min[0], max[1], min[2], point1);
  1340.     vectorInit3d(min[0], max[1], max[2], point2);
  1341.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1342.         return true;
  1343.  
  1344.     vectorInit3d(max[0], max[1], min[2], point1);
  1345.     vectorInit3d(max[0], max[1], max[2], point2);
  1346.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1347.         return true;
  1348.  
  1349.     vectorInit3d(max[0], min[1], min[2], point1);
  1350.     vectorInit3d(max[0], min[1], max[2], point2);
  1351.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1352.         return true;
  1353.  
  1354.     // left to right
  1355.     vectorInit3d(min[0], min[1], min[2], point1);
  1356.     vectorInit3d(max[0], min[1], min[2], point2);
  1357.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1358.         return true;
  1359.  
  1360.     vectorInit3d(min[0], max[1], min[2], point1);
  1361.     vectorInit3d(max[0], max[1], min[2], point2);
  1362.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1363.         return true;
  1364.  
  1365.     vectorInit3d(min[0], max[1], max[2], point1);
  1366.     vectorInit3d(max[0], max[1], max[2], point2);
  1367.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1368.         return true;
  1369.  
  1370.     vectorInit3d(min[0], min[1], max[2], point1);
  1371.     vectorInit3d(max[0], min[1], max[2], point2);
  1372.     if(linesegmentIntersectsTriangle(point1, point2, p1, p2, p3))
  1373.         return true;
  1374.  
  1375.     return false;
  1376. }
  1377.  
  1378. bool triangleIntersectsCylinder(vec3_t p1, vec3_t p2, vec3_t p3, vec3_t center, float radius, float height){
  1379.     return false;
  1380. }
  1381.  
  1382. bool sphereIntersectsSphere(vec3_t center1, float radius1, vec3_t center2, float radius2){
  1383.     return vectorPointDistance3d(center1, center2) <= radius1+radius2;
  1384. }
  1385.  
  1386. bool cylinderIntersectsCylinder(vec3_t center1, float radius1, float height1, vec3_t center2, float radius2, float height2){
  1387.     vec2_t center1_xz, center2_xz;
  1388.  
  1389.     // check if base caps overlap
  1390.     vectorInit2d(center1[0], center1[2], center1_xz);
  1391.     vectorInit2d(center2[0], center2[2], center2_xz);
  1392.     if(vectorPointDistance2d(center2_xz, center1_xz) > radius1+radius2)
  1393.         return false;
  1394.  
  1395.     // check height intervalls
  1396.     if(center1[1]+height1<center2[1] || center2[1]+height2<center1[1])
  1397.         return false;
  1398.  
  1399.     return true;
  1400. }
  1401.  
  1402. bool AABBIntersectsAABB(vec3_t min1, vec3_t max1, vec3_t min2, vec3_t max2){
  1403.     if(min2[0]>max1[0] || max2[0]<min1[0])    // THINKABOUTME: wegen shorteval alles zusammen??
  1404.         return false;
  1405.     if(min2[1]>max1[1] || max2[1]<min1[1])
  1406.         return false;
  1407.     if(min2[2]>max1[2] || max2[2]<min1[2])
  1408.         return false;
  1409.  
  1410.     return true;
  1411. }
  1412.