CODEWITHSUNDEEP
c++performance3dgeometry
Slight
Slight

Reputation: 1582

Fastest way to determine if a 3D point is within an axis aligned cube?

Assume you are given a single 3D point to be tested and another two 3D points representing the maximum and minimum of a cube.

The obvious solution using, at worst, 6 conditional statements is as follows:

if (point.x < cubemin.x || point.y < cubemin.y || point.z < cubemin.z
 || point.x > cubemax.x || point.y > cubemax.y || point.z > cubemax.z)
    return false; //is not within cube
return true; //is within cube

Conditional statements are some of the most computationally expensive instructions to execute. Is there any way to reduce the number of checks required? Performance in this case is crucial above all else.

Upvotes: 2

Views: 2196

Answers (2)

user3146587
user3146587

Reputation: 4320

There is this trick to reduce the number of tests (I am not advising using it...):

Assuming all coordinates are unsigned integers, then xmin <= x && x <= xmax can be reduced to x - xmin <= xmax - xmin.

  1. If xmin <= x && x <= xmax, this returns true as expected.
  2. If xmax < x, then x - xmin > xmax - xmin, so this returns false as expected.
  3. If x < xmin, then x - xmin wraps around (giving MAX_UINT + 1 + x - xmin), and xmax - xmin < MAX_UINT + 1 + x - xmin, so this returns false as expected.

Upvotes: 2

Robin Hsu
Robin Hsu

Reputation: 4484

Mathematically, there is no other way to work around maximum of 6 comparisons.

However, in the aspect of computer architecture, it is possible to do it all in parallel. A vector computer can do lots of similar things (such as your comparisons of max and min, etc.) in parallel.

So, that depends on what platform your program will be implemented on, and if that platform provide some vector instructions.

Or extremely, if your work is so critical, you may try to fabricate your own ASIC CPU chip.

Upvotes: 2

Related Questions