Geometry of lines in game development

When I started developing Raildale, I didn’t think that lines would be a problem. I, however, did not manage to find any good articles suitable for game developers about this theme. I was trying to solve the collision detection task, and I had to find the intersection of lines. I found many articles for amateurs, but there were many numbers and no good formulas. That’s why I had to solve this task myself.

I thought it would not be very difficult, but I realized that I had forgotten mathematics and solving of a simple system of equations was a problem for me. I was surprised since I was strong in math and geometry during my time at university. However you lose control over some skills if you don’t practice them.

I will rely on vectors in this article. So if you are not familiar with the concept of vectors, I would advise you to read this great article first.

Definition of line

First of all, we should define a class or a structure of a line, so we must first determine how we would define a line. I tried some different forms, but I settled on vector form, where you define a line with one point belonging to this line (p⃗) and with a direction vector (u⃗). In this case line equation takes the following form:

r⃗(t) = p⃗ + tu⃗, t is number

image

This method has some advantages:

  • You can use the same definition for 2D and 3D;
  • You can use the same definition for line segment, because u⃗ can be of any length.
case class Vec2(x : Float, y : Float) 
case class Vec3(x : Float, y : Float, z : Float) 
case class Line2(p : Vec2, u : Vec2) 
case class Line3(p : Vec3, u : Vec3) 

I used the Scala syntax, because this language has a very minimalistic and clear syntax.

Line and plane

The conventional method of defining a plane is by one point (p⃗) and a normal (n⃗). The same method defines a line in 2D. So vector (r⃗) belongs to the line or the plane if:

(r⃗ - p⃗)·n⃗ = 0

image

The vector (r⃗ - p⃗) should be perpendicular to the normal if it belongs to this line or plane and the dot product has a great property: it equals zero for perpendicular vectors.

For 2D line we can calculate the normal very simply:

def n : Vec2 = Vec2(-u.y, u.x)

And we can define the class of a plane:

case class Plane(p : Vec3, n : Vec3)

For our purpose we would not normalize vector n⃗ as we need a perpendicular vector with any length.

Intersection of a line with another line or a plane

The thing I love most about vectors is that they have the same solution for different dimensions (2D, 3D). The intersection point between two lines or a line and a plane must satisfy both the equations:

⎧r⃗ = p⃗₁ + tu⃗₁
⎨ 
⎩(r⃗ - p⃗₂)·n⃗₂ = 0

⎧n⃗₂·r⃗ = n⃗₂·p⃗₁ + t(n⃗₂·u⃗₁)
⎨ 
⎩n⃗₂·r⃗ = n⃗₂·p⃗₂
⇒ n⃗₂·p⃗ = n⃗₂·p⃗₁ + t(n⃗₂·u⃗₁) ⇒t = n⃗₂·(p⃗₂ - p⃗₁)/(n⃗₂·u⃗₁) ⇒
r⃗ =  p⃗₁ + [n⃗₂·(p⃗₂ - p⃗₁)/(n⃗₂·u⃗₁)]*u⃗₁

It is a formula for both intersection of lines in 2D and intersection of a line and a plane in 3D.

Projection of a point on a line

This can be very useful, for example, for limiting an area where a character or a camera can move. If the point is outside of the area you can replace it by projecting it on one of the borders of the area.

If we have a point (P) and a line (L), then we can simply find it as an intersection of L and the other line with P, as the start point and with the normal to L as the direction vector.

image

def projection(point : Vec2) : Vec2 = 
    intersection(Line2(point, this.n))

Segment of a line

We can use the same line class for a segment. It’s very simple to check whether the point belongs to a segment or not. The point must belong to the line and to the bounding rectangle of the segment.

image

If you need to define intersections between many segments, it  can be very time consuming. But first of all you can calculate intersections only between segments having an intersection between their bounding rectangles. Also you can use Bentley–Ottmann algorithm which does it fast.

Sources

package com.antonzherdev.line

case class Vec2(x : Float, y : Float) {
  def +(v : Vec2) = Vec2(x + v.x, y + v.y)
  def -(v : Vec2) = Vec2(x - v.x, y - v.y)
  def *(f : Float) = Vec2(x*f, y*f)
  def dot(v : Vec2) : Float = x*v.x + y*v.y
}
case class Vec3(x : Float, y : Float, z : Float) {
  def +(v : Vec3) = Vec3(x + v.x, y + v.y, z + v.z)
  def -(v : Vec3) = Vec3(x - v.x, y - v.y, z - v.z)
  def *(f : Float) = Vec3(x*f, y*f, z*f)
  def dot(v : Vec3) : Float = x*v.x + y*v.y
}

case class Line2(p : Vec2, u : Vec2) {
  def n : Vec2 = Vec2(-u.y, u.x)
  def intersection(line : Line2) : Vec2 = p + (u*(line.n.dot(line.p - p)/ line.n.dot(u)))
  def projection(point : Vec2) : Vec2 = intersection(Line2(point, this.n))

  def segmentBoundingRect : Rect2 = Rect2(p, u)
  def projectionToSegment(point : Vec2) : Option[Vec2] = {
    val proj = intersection(Line2(point, this.n))
    if(segmentBoundingRect.contains(proj)) Some(proj)
    else None
  }
}
case class Line3(p : Vec3, u : Vec3) {
  def intersection(plane : Plane) : Vec3 = p + (u*(plane.n.dot(plane.p - p)/ plane.n.dot(u)))
}
case class Plane(p : Vec3, n : Vec3)
case class Rect2(p : Vec2, size : Vec2) {
  def contains(point : Vec2) : Boolean =
    (p.x <= point.x) && point.x <= p.x + size.x && p.y <= point.y && point.y <= p.y + size.y
}

object Test {
  def main(args: Array[String]) {
    assert(Vec2(0, 2) == (Line2(Vec2(1, 1), Vec2(1, -1)) intersection Line2(Vec2(-1, 1), Vec2(-1, -1))))
    assert(Vec3(-1, -1, -1) == (Line3(Vec3(0, 0, 0), Vec3(1, 1, 1)) intersection Plane(Vec3(-1, 0, 0), Vec3(1, 0, 0))))
    assert(Vec2(2, 0) == (Line2(Vec2(1, 1), Vec2(1, -1)) projection Vec2(3, 1)))
  }
}