Skip to content

Min, Max under negation and an AABB trick

January 14, 2013

The two obvious identities:

min(a,b) = -max(-a, -b)
max(a,b) = -min(-a, -b)

can be used to rewrite algorithms using mixed min/max expressions in terms of just min (or just max). This can sometimes be useful when working with data that is intended to be processed with SIMD instructions, because it can be used to make the dataflow more regular. Let me give you a simple example to show what I mean: computing the axis-aligned bounding box (or AABB for short) of the union of several 2D AABBs.

AABB of the union of N 2D AABBs

A common representation for a 2D AABB just stores the extrema in both X and Y:

union AlignedBox2 {
  struct {
    float min_x, min_y;
    float max_x, max_y;
  };
  Vec4 simd;
};

The AABB for the union of N such AABBs can then be computed by computing the min/max over all bounds in the array, as follows:

AlignedBox2 union_bounds(const AlignedBox2 *boxes, int N) // N >= 1
{
  AlignedBox2 r = boxes[0];
  for (int i=1; i < N; i++) {
    r.min_x = min(r.min_x, boxes[i].min_x);
    r.min_y = min(r.min_y, boxes[i].min_y);
    r.max_x = max(r.max_x, boxes[i].max_x);
    r.max_y = max(r.max_y, boxes[i].max_y);
  }
  return r;
}

A typical 4-wide SIMD implementation can apply the operations to multiple fields at the same time, but ends up wasting half the SIMD lanes on fields it doesn’t care about, and does some extra work at the end to merge the results back together:

AlignedBox2 union_bounds_simd(const AlignedBox2 *boxes, int N)
{
  Vec4 mins = boxes[0].simd;
  Vec4 maxs = boxes[0].simd;
  for (int i=1; i < N; i++) {
    mins = min(mins, boxes[i].simd);
    maxs = max(maxs, boxes[i].simd);
  }

  AlignedBox2 r;
  r.minx = mins[0]; // or equivalent shuffle...
  r.miny = mins[1];
  r.maxx = maxs[2];
  r.maxy = maxs[3];
  return r;
}

But the identities above suggest that it might help to use a different (and admittedly somewhat weird) representation for 2D boxes instead, where we store the negative of max_x and max_y:

union AlignedBox2b {
  struct {
    float min_x, min_y;
    float neg_max_x, neg_max_y;
  };
  Vec4 simd;
};

If we write the computation of the union bounding box of two AABBs A and B in this form, we get (the interesting part only):

  r.min_x = min(a.min_x, b.min_x);
  r.min_y = min(a.min_y, b.min_y);
  r.neg_max_x = min(a.neg_max_x, b.neg_max_x);
  r.neg_max_y = min(a.neg_max_y, b.neg_max_y);

where the last two lines are just the result of applying the identity above to the original computation of max_x / max_y (with all the sign flips thrown in). Which means the SIMD version in turn becomes much easier (and doesn’t waste any work anymore):

AlignedBox2b union_bounds_simd(const AlignedBox2b *boxes, int N)
{
  AlignedBox2b r = boxes[0];
  for (int i=1; i < N; i++)
    r.simd = min(r.simd, boxes[i]);

  return r;
}

And the same approach works for intersection too – in fact, all you need to do to get a box intersection function is to turn the min into a max.

Now, this is just a toy example, but it shows the point nicely – sometimes a little sign flip can go a long way. In particular, this trick can come in handy when dealing with 3D AABBs and the like, because groups of 3 don’t fit nicely in typical SIMD vector sizes, and you don’t always have another float-sized value to sandwich in between; even if you don’t store the negative of the max, it’s usually much easier to sign-flip individual lanes than it is to rearrange them.

About these ads

From → Coding, Maths

2 Comments
  1. What is representation of Vec4? just four int’s? or this can be any primitive type?

    • Any primitive type will do, as long as there’s corresponding min and max operations.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 195 other followers

%d bloggers like this: