I'm now experimenting with replacing my entire hand-grown vector library with Eigen. It's really going well!

Most of the operations I perform are simple Vector3 and 3x3 or 4x4 matrices, and they're benefitting from Eigen's vectorization, both in terms of my code cleanliness and in actual evaluation speed. So thanks to the whole Eigen team!

Here's my simple puzzle which I can't figure out if Eigen's routines can help with.

I have two 3D axis aligned boxes. Each box is defined by 6 numbers giving the X Y and Z bounds for each. I can change the representation any way that's needed.. as a single 6D vector, as two 3D vectors (for bottom left and top right corners) or as a two vectors, one the center point and one the three widths (or half-widths).

The key inner-loop, time limiting, computation with the boxes is to see if two boxes intersect. In my current (pre-Eigen) code, I do the simple set of tests:

Code: Select all

inline bool intersect(const Box &a, const Box &b) {
{
  if (a.x0>=b.x1) return false;
  if (b.x0>=a.x0) return false;
  if (a.y0>=b.y1) return false;
  if (b.y0>=a.y0) return false;
  if (a.z0>=b.z1) return false;
  if (b.z0>=a.z0) return false;
  return true;


In my applications (ray tracing) boxes usually don't intersect, so the early escape (often after the first 1 or 2 tests) is efficient.

My question: what's the efficient way to organize my box data in Eigen to make this test (or an equivalent one) efficient?

I'm thinking that Eigen's SSE vectorization may give a win, perhaps using the storage strategy of maintaining boxes by center and half-widths, and comparing the absolute seperation between the centers to the sum of the half widths. But that seems slower than my old school method.. perhaps because I'm still testing the 3 inequalities one at a time?

There does not seem to be any clean query in Eigen for "return true if ALL of these components are negative", or easy booleans for efficient component wise comparisons followed by an ANY or ALL boolean query.

Luckily this example is very small so it's fun to just try all the variants to see what works best. I just think I'm missing some new approaches using Eigen's own operators that would envoke the SSE optimizations.

Anyway, I'm having fun.
I appreciate any thoughts or suggestions on my puzzle!

hm, there is an error in your code, I think the odd lines should be like this:
if (b.x0>=a.x1) return false;

I guess it's not really the code you used.


In eigen you can do stuff like: (array1>array2).all() though this kind of operations are not vectorized yet.

For your particular case, I doubt there is much to get from SSE vectorization. Perhaps, simply writing it like this:

return (a.x0<b.x1) && (b.x0<a.x1) && ...;

would be easier on the compiler...

ggael wrote:hm, there is an error in your code, I think the odd lines should be like this:
if (b.x0>=a.x1) return false;

I guess it's not really the code you used.

Whups, you're right, I just typed it from memory and didn't switch the last variable.

In eigen you can do stuff like: (array1>array2).all() though this kind of operations are not vectorized yet.

Ah, this was actually a feature I was looking for! I didn't see it in my pass through the docs, but that's because Eigen has so much good stuff in it I guess.

Your suggestion of chaining the tests is actually similar to what I do in my code. Splitting it into individual tests with returns like my example gives identical performance.



Another thought occured to me: would the box test be vectorizable in Eigen if I had an array of boxes to test? I could imagine doing something like making a structure of 6 variable length vectors, one for X0, one for X1, etc, and somehow testing those in a big batch. Hmm, I need to think more about this.

Thanks for the .any() hint!

the main difficultly is that you want to abort the computation as soon as possible, i.e., as soon as a test fails. This makes any kind of SSE vectorization particularly tricky because you will be enforced to preform some useless tests. You have to find the good tradeoff...