Andrew Aye

Andrew Aye - Talina Gaming System
Collision System - Linear

Linear

TgS Collision - Linear.h

TgS Collision - Line.inl	TgS Collision - Linear-Linear.inl
TgS Collision - Linear-Point.inl	TgS Collision - Ray.inl
TgS Collision - Segment.inl

TgS Collision - Linear-Linear.cpp	TgS Collision - Linear-Point.cpp
TgS Collision - Linear.cpp

Derivation of Algorithm

Segment Definition: G0(α) = P0 + α•D0 | α ε [ 0, 1]
Segment Definition: G1(β) = P1 + β•D1 | β ε [ 0, 1]

Let the points of closest contact be Q0 = P0+γ•D0 and Q1 = P1+Φ•D1, and v = Q1-Q0
Geometrically we know that the vector connecting the two closest points of contact ( or the minimal distance vector ) must be perpindicular to both lines. Thus, D0•v=0, D1•v=0, DS=P1-P0, v=(P1+Φ•D1)-(P0+γ•D0)

v = (P1+Φ•D1) - (P0+γ•D0)
v = P1 + Φ•D1 - P0 - γ•D0
v = P1 - P0 + Φ•D1 - γ•D0
v = DS + Φ•D1 - γ•D0

0 = D0•(DS + Φ•D1 - γ•D0)
0 = (DS•D0) + Φ•(D0•D1) - γ•(D0•D0)
γ = (DS•D0)/(D0•D0) + Φ•(D0•D1)/(D0•D0)
Φ = γ•(D0•D0)/(D0•D1) - (DS•D0)/(D0•D1)

0 = D1•(DS + Φ•D1 - γ•D0)
0 = (DS•D1) + Φ•(D1•D1) - γ•(D0•D1)
γ = (DS•D1)/(D0•D1) + Φ•(D1•D1)/(D0•D1)
Φ = γ•(D0•D1)/(D1•D1) - (DS•D1)/(D1•D1)

Two equations, two unknowns - solving for the gamma and theta yields:

0 = γ•(D0•D0)•(D1•D1) - (DS•D0)•(D1•D1) - γ•(D0•D1)•(D0•D1) + (DS•D1)•(D0•D1)
0 = γ•((D0•D0)•(D1•D1) - (D0•D1)•(D0•D1)) + (DS•D1)•(D0•D1) - (DS•D0)•(D1•D1)
γ = ((DS•D0)•(D1•D1) - (DS•D1)•(D0•D1)) / ((D0•D0)•(D1•D1) - (D0•D1)•(D0•D1))

0 = Φ•(D1•D1)•(D0•D0) + (DS•D1)•(D0•D0) - Φ•(D0•D1)•(D0•D1) - (DS•D0)•(D0•D1)
0 = Φ•((D1•D1)•(D0•D0) - (D0•D1)•(D0•D1)) + (DS•D1)•(D0•D0) - (DS•D0)•(D0•D1)
Φ = ((DS•D0)•(D0•D1) - (DS•D1)•(D0•D0)) / ((D0•D0)•(D1•D1) - (D0•D1)•(D0•D1))

If ((D0•D0)•(D1•D1) - (D0•D1)•(D0•D1)) < ε, the lines are parallel

However, we know that γ ε [ 0, 1], Φ ε [ 0, 1], generating nine cases:

[1] γ ε (-∞, 0) | Φ ε (-∞, 0)

[A] DS•D0 ε ( 0, D0•D0) || γ = DS•D0 / D0•D0 | Φ = 0

= (P1 - P0 - γ•D0)•(P1 - P0 - γ•D0)
= (DS - γ•D0)•(DS - γ•D0)
= (DS•DS) - 2•γ•(DS•D0) + γ•γ•(D0•D0)
= (DS•DS) + 2•(DS•D0 / D0•D0)•(DS•D0) + (DS•D0 / D0•D0)•(DS•D0 / D0•D0)•(D0•D0)
= (DS•DS) - (DS•D0)•(DS•D0) / (D0•D0)
= (DS•DS) - γ•(DS•D0)

[B] DS•D0 ε ( D0•D0, ∞) || γ = 1 | Φ = 0

= (P1 - P0 - D0)•(P1 - P0 - D0)
= (DS - D0)•(DS - D0)
= (DS•DS) - 2•(DS•D0) + (D0•D0)

[C] DS•D0 ε (-∞, 0), DS•D1 ε [ 0, ∞) || γ = 0 | Φ = 0

= (P1 - P0)•(P1 - P0)
= (DS•DS)

[D] DS•D0 ε (-∞, 0), DS•D1 ε (-DS•D1, 0) || γ = 0 | Φ = -DS•D1 / D1•D1

= (P1 + Φ•D1 - P0)•(P1 + Φ•D1 - P0)
= (DS + Φ•D1)•(DS + Φ•D1)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•(-DS•D1 / D1•D1)•(D1•D1)
= (DS•DS) + Φ•(DS•D1)

[E] DS•D0 ε (-∞, 0), DS•D1 ε (-∞,-D1•D1] || γ = 0 | Φ = 1

= (P1 + D1 - P0)•(P1 + D1 - P0)
= (DS + D1)•(DS + D1)
= (DS•DS) + 2•(DS•D1) + (D1•D1)

[2] γ ε (-∞, 0) | Φ ε [ 0, 1]

[A] DS•D1 ε [ 0, ∞) || γ = 0 | Φ = 0

Same as [1C]

[B] DS•D1 ε (-D1•D1, 0) || γ = 0 | Φ = -DS•D1 / D1•D1

Same as [1D]

[C] DS•D1 ε (-∞,-D1•D1) || γ = 0 | Φ = 1

Same as [1E]

[3] γ ε (-∞, 0) | Φ ε ( 1, ∞)

[A] DS•D0 ε [D0•D0 - D0•D1, ∞) || γ = 1 | Φ = 1

= (P1 + D1 - P0 - D0)•(P1 + D1 - P0 - D0)
= (DS + D1 - D0)•(DS + D1 - D0)
= (DS•DS) + (DS•D1) - (DS•D0) + (DS•D1) + (D1•D1) - (D0•D1) - (DS•D0) - (D0•D1) + (D0•D0)
= (DS•DS) + 2•(DS•D1) - 2•(D0•D1) - 2•(DS•D0) + (D0•D0) + (D1•D1)

[B] DS•D0 ε (-D0•D1, D0•D0 - D0•D1) || γ = ((D0•D1) + (DS•D0)) / (D0•D0) | Φ = 1

= (P1 + D1 - P0 - γ•D0)•(P1 + D1 - P0 - γ•D0)
= (DS + D1 - γ•D0)•(DS + D1 - γ•D0)
= (DS•DS) + 2•(DS•D1) + (D1•D1) - 2•γ•(D0•D1) - 2•γ•(DS•D0) + γ•γ•(D0•D0)
= (DS•DS) + 2•(DS•D1) + (D1•D1) - γ•(2•(D0•D1) + 2•(DS•D0) - γ•(D0•D0))
= (DS•DS) + 2•(DS•D1) + (D1•D1) - γ•(2•(D0•D1) + 2•(DS•D0) - (D0•D1) - (DS•D0))
= (DS•DS) + 2•(DS•D1) + (D1•D1) - γ•((D0•D1) + (DS•D0))
= (DS•DS) + 2•(DS•D1) + (D1•D1) - γ•γ•(D0•D0)

[C] DS•D0 ε (-∞,-D0•D1) | DS•D1 ε ( 0, ∞) || γ = 0 | Φ = 0

Same as [1C]

[D] DS•D0 ε (-∞,-D0•D1) | DS•D1 ε (-D1•D1, 0) || γ = 0 | Φ = -DS•D1 / D1•D1

Same as [1D]

[E] DS•D0 ε (-∞,-D0•D1) | DS•D1 ε (-∞,-D1•D1) || γ = 0 | Φ = 1

Same as [1E]

[4] γ ε [ 0, 1] | Φ ε (-∞, 0)

[A] DS•D0 ε (-∞, 0) || γ = 0 | Φ = 0

Same as [1C]

[B] DS•D0 ε [ 0, D0•D0] || γ = DS•D0 / D0•D0 | Φ = 0

Same as [1A]

[C] DS•D0 ε ( D0•D0, ∞) || γ = 1 | Φ = 0

Same as [1B]

[5] γ ε [ 0, 1] | Φ ε [ 0, 1]

Distance: The distance value would be || v ||.
= || v || = v•v = (P1 + Φ•D1 - P0 - γ•D0)•(P1 + Φ•D1 - P0 - γ•D0)
= (DS + Φ•D1 - γ•D0)•(DS + Φ•D1 - γ•D0)
= (DS•DS) + 2•Φ•(DS•D1) - 2•γ•(DS•D0) + Φ•Φ•(D1•D1) - 2•γ•Φ•(D0•D1) + γ•γ•(D0•D0)
= (DS•DS) + Φ•(Φ•(D1•D1) + 2•(DS•D1)) + γ•(γ•(D0•D0) - 2•(DS•D0)) - 2•γ•Φ•(D0•D1)

[6] γ ε [ 0, 1] | Φ ε ( 1, ∞)

[A] DS•D0 ε [D0•D0 - D0•D1, ∞) || γ = 1 | Φ = 1

Same as [3A]

[B] DS•D0 ε (-D0•D1, D0•D0 - D0•D1) || γ = ((D0•D1) + (DS•D0)) / (D0•D0) | Φ = 1

Same as [3B]

[C] DS•D0 ε (-∞,-D0•D1) || γ = 0 | Φ = 1

Same as [1E]

[7] γ ε ( 1, ∞) | Φ ε (-∞, 0)

[A] DS•D0 ε (-∞, 0) || γ = 0 | Φ = 0

Same as [1C]

[B] DS•D0 ε [ 0, D0•D0) || γ = DS•D0 / D0•D0 | Φ = 0

Same as [1A]

[C] DS•D0 ε ( D0•D0, ∞), DS•D1 ε ( D0•D1, ∞) || γ = 1 | Φ = 0

Same as [1B]

[D] DS•D0 ε ( D0•D0, ∞), DS•D1 ε ( D0•D1 - D1•D1, D0•D1) || γ = 1 | Φ = ((D0•D1) - (DS•D1)) / (D1•D1)

= (P1 + Φ•D1 - P0 - D0)•(P1 + Φ•D1 - P0 - D0)
= (DS + Φ•D1 - D0)•(DS + Φ•D1 - D0)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1) - 2•Φ•(D0•D1) - 2•(DS•D0) + (D0•D0)
= (DS•DS) + Φ•(2•(DS•D1) - 2•(D0•D1) + Φ•(D1•D1)) - 2•(DS•D0) + (D0•D0)
= (DS•DS) + Φ•((DS•D1) - (D0•D1)) - 2•(DS•D0) + (D0•D0)
= (DS•DS) - Φ•Φ•(D1•D1) - 2•(DS•D0) + (D0•D0)

[E] DS•D0 ε ( D0•D0, ∞), DS•D1 ε (-∞, D0•D1 - D1•D1) || γ = 1 | Φ = 1

Same as [3A]

[8] γ ε ( 1, ∞) | Φ ε [ 0, 1]

[A] DS•D1 ε ( D0•D1, ∞) || γ = 1 | Φ = 0

Same as [1B]

[B] DS•D1 ε ( D0•D1 - D1•D1, D0•D1) || γ = 1 | Φ = ((D0•D1) - (DS•D1)) / (D1•D1)

Same as [7D]

[C] DS•D1 ε (-∞, D0•D1 - D1•D1) || γ = 1 | Φ = 1

Same as [3A]

[9] γ ε ( 1, ∞) | Φ ε ( 1, ∞)

[A] DS•D0 ε [-D0•D1, D0•D0-D0•D1] || γ = ((D0•D1) + (DS•D0)) / (D0•D0) | Φ = 1

Same as [3B]

[B] DS•D0 ε (-∞,-D0•D1) || γ = 0 | Φ = 1

Same as [1E]

[C] DS•D0 ε ( D0•D0-D0•D1, ∞), DS•D1 ε ( D0•D1, ∞) || γ = 1 | Φ = 0

Same as [1B]

[D] DS•D0 ε ( D0•D0-D0•D1, ∞), DS•D1 ε ( D0•D1 - D1•D1, D0•D1) || γ = 1 | Φ = ((D0•D1) - (DS•D1)) / (D1•D1)

Same as [7D]

[E] DS•D0 ε ( D0•D0-D0•D1, ∞), DS•D1 ε (-∞, D0•D1 - D1•D1) || γ = 1 | Φ = 1

Same as [3A]

-- Parallel Segments --

[1] D0•D1 ε (-∞, 0)

[A] DS•D0 ε ( D0•D0-D0•D1, ∞) || γ = 1 | Φ = 1

Same as [3A]

[B] DS•D0 ε ( D0•D0, D0•D0-D0•D1] || γ = 1 | Φ = ((D0•D0) - (DS•D0)) / (D0•D1)

= (P1 + Φ•D1 - P0 - D0)•(P1 + Φ•D1 - P0 - D0)
= (DS + Φ•D1 - D0)•(DS + Φ•D1 - D0)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1) - 2•Φ•(D0•D1) - 2•(DS•D0) + (D0•D0)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1) - 2•((D0•D0) - (DS•D0)) - 2•(DS•D0) + (D0•D0)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1) - 2•(D0•D0) + 2•(DS•D0) - 2•(DS•D0) + (D0•D0)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1) - (D0•D0)

[C] DS•D0 ε ( 0, D0•D0] || γ = DS•D0 / D0•D0 | Φ = 0

Same as [1A]

[D] DS•D0 ε (-∞, 0) || γ = 0 | Φ = 0

Same as [1C]

[2] D0•D1 ε [ 0, ∞)

[A] DS•D0 ε [ D0•D0, ∞) || γ = 1 | Φ = 0

Same as [1B]

[C] DS•D0 ε (-D0•D1, D0•D0) || γ = 0 | Φ = -DS•D0 / D0•D1

= (P1 + Φ•D1 - P0)•(P1 + Φ•D1 - P0)
= (DS + Φ•D1)•(DS + Φ•D1)
= (DS•DS) + 2•Φ•(DS•D1) + Φ•Φ•(D1•D1)

[D] DS•D0 ε (-∞,-D0•D1] || γ = 0 | Φ = 1

Same as [1E]