# Input

Two solid boxes with movement defined by a transformation matrix – which consists of a 4x4 quadratic functions of a parameter "t".

# Output

The first "t" in which the collision occurs, providing there is one.

# Algorithm

We define a new coordinate system S, where one box is static and aligned with the axes. Given the two transformation matrices M1(t), M2(t), the relative movement of the moving box is then defined by M1(t)M2(t)-1.

The two boxes will collide if and only if there exists t0 where the boundary of the Minkowsky sum (BMS) of B1 and –B2(t) contains the origin -  , for that t0 there exists . We shall find this t0 analytically.

1. Since we are seeking the time of collision, we only need to calculate when the origin is contained in the BMS. Therefore, we avoid from calculating elements inside the boundary. The boundary faces are created by matching pairs of elements (vertices, edges, faces) from each box. The BMS is created using only a subset of all possible pairs. This subset consists of pairs of compatible orientation, which we will find using their spherical orientation representation.

1. We extract the spherical orientation representation of B1, and B2(t). Every face, edge and vertex on the box, has its matching vertex, edge and spherical octant on the normal (Gaussian) sphere respectively, according to their orientation.

1. The compatible pairs of the two boxes will be found by comparing the orientation spheres.

1. The BMS is constructed using the compatible pairs of the boxes, which are derived from the boxes' relative orientation. Hence, the topology of the BMS is derived from the set of compatible pairs. The set of compatible pairs (topology of the boundary) will not change as long as no spherical vertex switches octants. Therefore we divide B2's route into homogeneous paths, paths where no vertex moves between octants.

1. The compatible components define the BMS' planes. For each homogenous part of the route, which defines a different Minkowsky sum topology, if there is a t0 such that one of those planes contains the origin and further, the origin is inside the boundary defined by the other planes, this t0 indicates a collision.

## Extraction of Spherical Orientation Representation (SOR)

### Sphere Representation

We denote the box's faces and vertices as follows: For the initial notation, we assume the box is aligned with the axes, so it can be described by its two corners: (MinX, MinY, MinZ) and (MaxX, MaxY, MaxZ) or (X, Y, Z) and (X', Y', Z') respectively. Each vertex v is conveniently denoted by its simplified coordinates . According to the same method we can describe a face, using its containing plane (e.g. X for the face contained in X = MinX plane, Y' for the face contained in Y = MaxY plane). We denote a box edge by its two adjacent faces (e.g. X-Y, Y'-Z etc.)

It is possible to conclude a face given three vertices, by finding the common component of the three coordinates. Given three faces, the common vertex is, as defined above, the one denoted by the faces' symbols (X, Y, Z, X', Y', Z'), assuming all three are orthogonal. Define F' to be the opposite face to F, and v'=(x',y',z') be the opposite corner of v=(x,y,z). Moreover <symbol>'' = <symbol> (opposite of the opposite).

We can now match the box's faces and vertices to their spherical representation. Each of the box's faces is conceptually represented as a vertex on the normal sphere, and each of the box's vertices is conceptually represented as an octant on the sphere. This way we represent the fact that a box's face is directed to one direction (its normal), and a vertex is "directed" to all directions in between its adjacent three faces' normals. After extracting the SOR: "vertex" denotes a sphere vertex (face of the box) and "octant" denotes a sphere octant (vertex of the box).

The compatible components between the two boxes that form a face in the BMS can be one of the pairs: (face, vertex), (vertex, face), (edge, edge), in which one's normal is in the range of the other's normal.

### Dividing the Route

To divide the route we need to check when any vertex of the moving box's SOR has switched to another spherical octant. We find these instances by solving the equations: , for any three box's orthogonal normals. Each t satisfying one of the nine equations above is an instance of an octant switch. The case of a normal component which equals 0 for a continuous period of time does not represent a change in topology and therefore can be ignored. Sorting all the "t"s above (ignoring duplicates) gives us all points in time where some vertex switches an octant.

### Finding Relative Topology

In each homogenous section i ( ) of the route we want to extract the set of BMS planes equations. Since the topology of the boundary remains the same along the section, we choose a middle point t0 such that ti < t0 < ti+ in which we shall sample the topology, and create a set of plane equations, that are functions of t, and are valid throughout the section ( ).

We shall now describe how to identify the topology at t0. We will use the following notation:

xm – element x of the moving sphere.

xs – element x of the static sphere.

v – a vertex on the normal sphere (X, Y, Z, X', Y', Z').

o – an octant on the normal sphere (e.g. XYZ, X'YZ' etc.).

e – an edge on the normal sphere (e.g. X-Y,X-Z etc.).

S – The full set of compatible pairs defining the BMS.

- VO pair – vertex-octant, both on the normal sphere.

- OV pair – octant-vertex, both on the normal sphere.

#### Computing VO, OV pairs:

1)      We sample the position of three orthogonal moving vertices at t0 (i.e. in which static octant they reside in), and receive three pairs – (vertex,octant): [So far we have 3 vertex-octant (VO) pairs]

2)      From the three pairs  we receive the three antipodal vertices and octants, hence . [So far we have 6 vertex-octant (VO) pairs]

3)      From every 3 moving vertices defining an octant, we can conclude the static vertex residing in it (OV instance), providing there is such.

, the function Vert might return that there is no suitable vertex. i.e. there is no vertex in this octant. Since there are 8 octants and only 6 vertices, and from geometric reasons there can not be two vertices in the same octant, there will be exactly two antipodal (spherical symmetry) vertex-free octants.  Using this method repeatedly for all 8 triplets, we shall get 6 OV instances + 2 antipodal vertex-free octants. [So far we have 6 VO pairs and 6 OV pairs]

#### Computing EE instances (edge-edge):

4)      We traverse through all static edges es:

a.       We extract adjacent octants (o1­, o2).

b.      For each octant we extract the contained moving vertex (if it has one).

c.       For each edge, whose adjacent octants (o1­, o2) contain a moving vertex (v1, v2) – compute the moving edge (em = v1-v2) intersecting es (see illustration below – left side). We receive the EE instance: es-em.

[6 EE instances – 6 edges not surrounding vertex-free octants, each having 1 intersection]

5)      For one of the vertex-free static octant os (we have 2 of those):

a.       Extract border static edges e1, e2, e3.

b.      For each :

i.      Find adjacent octant oi  os.

ii.      Find moving vertex contained in oi: vi (there must be one because the other vertex-free octant is antipodal, thus not adjacent).

c.       For each :

i.      Denote EE instances:

[6 EE instances – the octant has 3 border edges, each having 2 intersections. as shown in illustration below – right side]

6)      From the 6 EE instances found on step 5, we receive the 6 antipodal instances.

We now have a total of 6 OsVm instances, 6 VsOm, and 18 EE instances, giving us altogether 30 plane equations.

 Home | Algorithm | Results | References | Downloads | Contact Us  Written by Danny Albocher & Uzi Sarel Last Update: 21/08/05.