Line Segments
Heim kommt man nie. Aber wo befreundete Wege zusammenlaufen, da sieht die ganze Welt für eine Stunde wie Heimat aus.
– Hermann Hesse, Demian
The Intersection Problem
In this tutorial, we want to improve on the collision detection algorithm used in the Kicker-demo from previous tutorials. The issue can easily be restated as a line, or segment, intersection problem: As an object moves with a certain velocity, the velocity vector, with origin at the current position of the moving object, leads the way to wherever the object is going to.
Once we know that two line segments actually intersect, computing the intersection point
Parametric Representation
To facilitate working with line segments, we will use the parametric representation of lines and segments. Basically, you can imagine a segment as the way between two points. Let
Intersection
To figure out whether two segments
In matrix notation, this reads as follows:
Colinearity
Now if
If the determinant of the matrix
Linear Independence
Now if the two directional vectors are linearly independent, the matrix
Example
Let
In this example, we have
thus
Plugging
as desired, which tells us that if we run three quarters of the length of the segment from
Implementation
To define line segments in C++, we use a small class:
class LineSegment2D{private: Vector2F startPoint, endPoint; // the start and ending point of the line segment Vector2F directionVector; // the vector joining those two points Vector2F normalVector; // the normal vector of the line segment
public: LineSegment2D(); LineSegment2D(Vector2F startPoint, Vector2F endPoint); LineSegment2D(Vector2F startPoint, Vector2F endPoint, Vector2F normalVector); ~LineSegment2D() {};
void setStartingPoint(Vector2F vector) { startPoint = vector; }; void setEndPoint(Vector2F vector) { endPoint = vector; }; void projectToVector(const Vector2F& vectorToProjectOn); void recomputeDirectionalVector(float radius = 1.0f);
const Vector2F getDirectionalVector() const { return directionVector; }; const Vector2F getNormalVector() const { return normalVector; }; const Vector2F getStartPoint() const { return startPoint; };
friend class Geometry;};
Both constructors compute the directional vector and the first constructor computes the normal vector (clockwise) as well:
LineSegment2D::LineSegment2D(Vector2F startPoint, Vector2F endPoint, Vector2F normalVector) : startPoint(startPoint), endPoint(endPoint), normalVector(normalVector){ this->directionVector = endPoint - startPoint;
// normal vector: (-dy,dx) this->normalVector = Vector2F(-directionVector.y, directionVector.x); this->normalVector.normalize();}
LineSegment2D::LineSegment2D(Vector2F startPoint, Vector2F endPoint) : startPoint(startPoint), endPoint(endPoint){ this->directionVector = endPoint - startPoint;
// normal vector: (-dy,dx) this->normalVector = Vector2F(-directionVector.y, directionVector.x); this->normalVector.normalize();}
The recomputeDirectionalVector method is used to get the direction vector from the centre of a ball to the edge of its radius:
void LineSegment2D::recomputeDirectionalVector(float radius){ this->directionVector = this->endPoint - this->startPoint; if (this->directionVector.x == 0 && this->directionVector.y == 0) return; this->directionVector.normalize(); this->directionVector *= -1.0f*radius;}
Note the negative sign in the normalization of the vector. This is due to the base change between standard coordinates and screen coordinates.
The actual test for intersecting between two segments follows the mathematics explained above:
bool Geometry::segmentIntersection2D(const LineSegment2D& segment1, const LineSegment2D& segment2, Vector2F* t){ // compute the determinant of the 2x2 matrix float det = segment1.directionVector.x * segment2.directionVector.y - segment1.directionVector.y * segment2.directionVector.x;
// if det is 0, the directional vectors are colinear if (det == 0) return false;
// compute directional vector between the two starting points Vector2F directionalVector = Vector2F(segment2.startPoint.x - segment1.startPoint.x, segment2.startPoint.y - segment1.startPoint.y);
// compute t1 float t1 = segment2.directionVector.y * directionalVector.x - segment2.directionVector.x * directionalVector.y; t1 /= det;
// if t1 is not between 0 and 1, the segments can't intersect if (0 > t1 || t1 > 1) return false;
// compute t2 float t2 = -segment1.directionVector.y * directionalVector.x + segment1.directionVector.x * directionalVector.y; t2 /= det;
// if t2 is not between 0 and 1, the segments can't intersect if (0 > t2 || t2 > 1) return false;
// else return true if (t != NULL) { t->x = t1; t->y = t2; } return true;
}
And all of this greatly simplifies the collision detection test of the Kicker-demo:
util::Expected<void> PlayState::update(const double deltaTime){ if (isPaused) return { };
// update the ball and table ball->update(deltaTime, table->frictionCoeffK);
// check wall intersections int i = -1; for (auto wall : table->walls) { i++; if (i != collision) { if (mathematics::Geometry::segmentIntersection2D(*wall, *ball->direction)) { mathematics::reflectionVector(ball->velocity, wall->getNormalVector()); collision = i; break; } } }
...
// return success return { };}
While these new ideas greatly improved on the previous algorithms, this is far from being the entire story. In a later series of tutorials about Computational Geometry, we will explore topics such as this in greater mathematical detail.
References
- Geogebra
- Tricks of the Windows Programming Gurus, by A. LaMothe
- Wikipedia