衝突判定
So if its vertices have Cartesian coordinates ( x 1 , y 1 , z 1 ) {\displaystyle (x_{1},y_{1},z_{1})} , ( x 2 , y 2 , z 2 ) {\displaystyle (x_{2},y_{2},z_{2})} and ( x 3 , y 3 , z 3 ) {\displaystyle (x_{3},y_{3},z_{3})} then the centroid is ( ( x 1 + x 2 + x 3 ) 3 , ( y 1 + y 2 + y 3 ) 3 , ( z 1 + z 2 + z 3 ) 3 ) {\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)} .
有向境界ボックス(Oriented Bounding Box)。
We suppose that, from one time step to the next, I k {\displaystyle I_{k}} and J k {\displaystyle J_{k}} intersect, then it is very likely that at the next time step, they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to.
So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length n {\displaystyle n} , the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list.
Early work by Ming C. Lin used a variation on the simplex algorithm from linear programming. The Gilbert-Johnson-Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.
The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.
Here is the function for a line segment distance between two 3D points. d i s t a n c e = ( z 2 − z 1 ) 2 + ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 {\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}
Here the length/distance of the segment is an adjustable "hit" criteria size of segment. As the objects approach the length decreases to the threshold value. A triangle sphere becomes the effective geometry test. A sphere centered at the centroid can be sized to encompass all the triangle's vertices.