I'm trying to work out the implementation of a separating axis theorem for oriented bounding boxes based on a paper by David Eberly et al.. And it's got some uses of the sigma notation which I don't quite understand. It's probably very rudimentary but it's used throughout the paper and I feel like understanding this well will make it much easier to read the rest of it. I will post a picture of the section I'm having difficulty with (please scroll down to the bottom of the post) and my questions will be based on it, so please take a look at it.

What I'm not seeing is how will that formula get me 8 vertices of a box if there are only 2 iterations on top of the sigma?

For example if I solve the iterations it comes out as this

center + xExtent*xAxis + yExtent*yAxis + zExtent*zAxis

Doesn't that only give me one point? 

Don't I have to repeat the whole thing 8 times with different signs to get all 8 points?

Also what is the |σi| variable in there? The paper says 

Quote

where |σi | = 1 for all i.

What is the purpose of including that if it's always 1. 

Anyways, I feel like I'm missing some detail or just not understanding the proper way a sigma notation is used, this is how I would write the code for that equation

vector center;
float sigmatotal = 0;
for(int i = 0; i <= 2; i++)
  sigmatotal += gamma[i]*extent[i]*axis[i];

center += sigmatotal;

I'm not used to reading math papers, so this might be wrong, but my interpretation is:

0...2 --> 3 iterations (0, 1, 2).

An extent goes in both directions. If a line is 100 meters long, the extents from center is 50 meters.

For ease of writing, some simplification is made. Assume center C is at x = 12, y = 20, z = 100

An axis + an extent = 2 vertices. Imagine a horizontal axis, positive to the right (x: 1, y: 0, z: 0), with extents 5.

The two vertices for that axis-extent tuple would then be at local coordinates (before Center is applied):

min: x = -5, y = 0, z = 0

max: x = 5, y = 0, z = 0

And final coordinates (after adjusting for Center):

min: x = 7, y = 20, z = 100

max: x = 17, y = 20, z = 100

I think the |σ| = 1 just means that the length of the direction axis is of unit length, allowing just multiplying direction axis with extents to get offset from center, without any need to normalize/scale the axis before use.

1 hour ago, Lactose said:

An extent goes in both directions.

Yes, I just wanted to understand how that is represented in the formula.

Because as far as I understand an extent is just a positive number, which you either add or subtract to get both points. The way I see it is if an object has a center of 0 and the extent is 5, then to get both points you must do (0-5), (0+5). But the equation just has the form of

center + extent

Is it just a simplified formula?

Or is it somehow signified by this phrase, the absolute value of the xi should be less than or equal to each extent, which I'm not really sure the purpose of.

Quote

: |xi | ≤ |ai | for all i

I'm not so confused by the implementation but I just want to understand how things are expressed in this paper, because even though I understand how to properly get all the 8 points, there are equations introduced later on which I have hardly any idea for the rational of, and they all use a similar sigma notation with extents and axii, so I must be able to understand what the actual equation is saying in a very strict sense. For example if I had to transcribe this particular formula I would transcribe it as 

vector center;
float sigmatotal = 0;
for(int i = 0; i <= 2; i++)
  sigmatotal += gamma[i]*extent[i]*axis[i];

center += sigmatotal;

which is obviously wrong. So I just want to get some grip on the mathematical nomenclature and symbols used before I start writing code.

I think 

5 hours ago, Lactose said:

I think the |σ| = 1 just means that the length of the direction axis is of unit length, allowing just multiplying direction axis with extents to get offset from center, without any need to normalize/scale the axis before use.

I've been looking at this symbol for a while now, and it's used in other formulas down the page as well. Could it be the sign?

He says an absolute value of this variable is always one. So that means that the variable is always either 1 or -1. So in the formula 

Quote

c + sigma(0 to 2) σ*extent*Axis 

If we pass in the sign vector we can get all the points.

To get point <right upper point> we just pass in a [1, 1, 1] vector for the signs so we get

1*extentX*AxisX + 1*extentY*AxisY + 1*extentZ*AxisZ

To get point <left lower point> we just pass in a [-1, -1, -1] vector for the signs so we get

-1*extentX*AxisX  -1*extentY*AxisY - 1*extentZ*AxisZ

To get point <right lower point> we just pass in a [1, -1, 1] vector for the signs so we get

1*extentX*AxisX  -1*extentY*AxisY + 1*extentZ*AxisZ

and so on and so forth

Could this be it? This would explain how to get all the points using that equation at least.

The bottom formula can be expanded as 

C + sigma_0 a_0 A_0 + sigma_1 a_1 A_1 + sigma_2 a_2 A_2.

They tell you that |sigma_i| = 1, which means that each of the sigma_i values can be -1 or +1. There are 8 ways to make those choices, and that's how to get your 8 vertices.

21 minutes ago, alvaro said:

The bottom formula can be expanded as 

C + sigma_0 a_0 A_0 + sigma_1 a_1 A_1 + sigma_2 a_2 A_2.

They tell you that |sigma_i| = 1, which means that each of the sigma_i values can be -1 or +1. There are 8 ways to make those choices, and that's how to get your 8 vertices.

Ok, that makes sense. I just pass in the sign vector for the sigma_i to get all the points. But what about this use of the formula (see picture)

Should r0 be calculated for each vertex or should it somehow be the combination of all the vertices? 

It seems like he's calculating r0 for each vertex since it's just a restatement of the first formula, but it makes no sense to me because the inscription above the second equation reads "The minimum length interval containing all 8 projection distances"

And here the word "Sign" is just meant to signify σ?

I know this isn't the answer to your question, but you really should be looking at Dirk's GDC lectures on SAT and not Eberly's stuff. Eberly's docs are typically robust and mathematically rich, but his example code is convoluted and overengineered, and ultimately Dirk's resources document better algorithms for the most part in a simpler way.

https://box2d.org/downloads/

On 6/11/2019 at 6:37 AM, VanillaSnake21 said:

Ok, that makes sense. I just pass in the sign vector for the sigma_i to get all the points. But what about this use of the formula (see picture)

Should r0 be calculated for each vertex or should it somehow be the combination of all the vertices? 

It seems like he's calculating r0 for each vertex since it's just a restatement of the first formula, but it makes no sense to me because the inscription above the second equation reads "The minimum length interval containing all 8 projection distances"

And here the word "Sign" is just meant to signify σ?

Does he describe what L and a_i in the formula means (I assume A_i are 3 axis directions, and a_i could be their magnitude/length - but without knowing what L is I can't help you much)?

Anyways - if he uses common notation - Sign should be a signum function defined as (in pseudo code):

signum(x): y = (x < 0 ? -1 : 1);

The upper part is obviously (inside sum) calculating length of projected vector L on basis of the OBB. But without knowing what L is, I can't help you much. For this - do you have a link to Eberly's paper (your post doesn't link to it).

23 minutes ago, Vilem Otte said:

For this - do you have a link to Eberly's paper (your post doesn't link to it).

Sorry, I thought I linked it but for some reason the link is not clickable, this is it here, but the definitions are as follows:

This is how he defines Ai and ai

Quote

In the following discussion, all vectors are in IR3. An oriented bounding box is dened by a center C, a set
of right-handed orthonormal axes A0, A1, and A2, and a set of extents a0 > 0, a1 > 0, and a2 > 0. As a
solid box, the OBB is represented by

They are just axes of the box,small a's are the extents

The definition of L is as follows

Quote

where
L is one of Ai, Bj , or Ai x Bj for i = 0; 1; 2 and j = 0; 1; 2.

I took it to be a projection axis

24 minutes ago, Vilem Otte said:

 

 Anyways - if he uses common notation - Sign should be a signum function defined as (in pseudo code):

signum(x): y = (x < 0 ? -1 : 1);

 

Just want to make sure I understand the signum function on a vector would just return the signs of each element?

For example vector {-2.0f, 3.0, -2.0f}, signum(vector) = {-1, 1, -1} ?

8 hours ago, VanillaSnake21 said:

The definition of L is as follows

Quote

 where
L is one of Ai, Bj , or Ai x Bj for i = 0; 1; 2 and j = 0; 1; 2.

I took it to be a projection axis

Therefore L is a vector in separating plane of 2 OBBs (i.e. separating axis). There is only 15 of them possible.

So to explain geometrically what you want to do - you want to project both OBB and the line between their centres to the plane whose normal is separating axis (i.e. L). Now for each of the OBBs, calculate minimum radius from its center that holds all the points (on the plane defined by L). This is used to find axis where the boxes can intersect (which happens - when the radius is smaller than distance between 2 OBBs).

To illustrate:

Advanced GIMP graphics - representing projection of 2 OBBs on plane defined by separating axis. Notice the r0 and r1 radiuses and yellow (barely visible) line R representing distance.

This is for one of the axis only (a0 - suppose that left OBB is A, right OBB is B). But clearly there is no intersection on axis A0. You need to test all 15 ti properly reject collision, if you find any that has smaller distance than sum of radiuses, you can terminate the search (as if there is an intersection, you can find it there). EDIT: And therefore there is no intersection at all. You need to find one separating axis (i.e. one where there is no collision) to reject the collision.

For that I believe you need to test all planes of both boxes against each other (there may be some optimization - testing just the planes in direction to the 2nd OBB?), each plane-plane test gives you intersection result - 2 3D planes either:

1. don't intersect (simple to handle - either no collision or penetrating distance is distance of planes and intersection points are on both plane connected by line in direction of plane normal)
2. intersection is a line
3. intersection is a plane (when they are equivalent - which is simple to handle - penetrating distance is 0, collision point is any on the given OBB face))

if intersection is line, and it crosses through any face of any of OBBs (which is 2D test) - then you have collision (otherwise, no collision).

If I remember correctly then you need to find point of first time intersection - and then how much boxes penetrated each other (which is just distance of original and transformed 1st time intersection point by constant speed of OBBs).

Note. @Randy Gaul feel free to correct me if I'm wrong in any of the points here, I know that you know a lot more in collisions and physics area than me.

EDIT: Reading the paper... and the notation is somewhat confusing in some parts indeed. His Sign function is actually signum in this case, but later in the paper he defines it for purpose of always getting positive result (few lines down - he already denotes it mathematically properly with absolute value).