Im trying to test whether a point lies within a 3d volume defined by 8 points. I know I can use the plane equation to check that the signed distance is always -1 for all 6 sides, but does anyone know of a faster way or could point me to some code?

I should add that ideally the test would produce 3 linear interpolation parameters which would lie in the range 0..1 to indicate that the point is within the volume for each axis (since I will have to calculate these later if the point is found to be in the volume)

  • 3
    \$\begingroup\$ Is the cube axis aligned?, are its faces parallel? \$\endgroup\$ – Zhen Oct 28 '12 at 17:15
  • \$\begingroup\$ I was just about to add- no, sadly theyre not! makes the plane equation approach rather complicated! \$\endgroup\$ – aadster Oct 28 '12 at 17:50
  • 2
    \$\begingroup\$ Striving after "faster" is a form of procrastination. Until this intersection test shows up in profiling results (ie: until you have measured numbers which show that it's a problem), you're just wasting your time trying to find a faster way to do it. \$\endgroup\$ – Trevor Powell Dec 28 '12 at 23:14
  • \$\begingroup\$ Are you going to test many points against the same cuboid, or one point against many cuboids? (If you only have one point and one cuboid, it’s not worth worrying about speed.) \$\endgroup\$ – sam hocevar Jun 27 '13 at 0:29
  • \$\begingroup\$ Use point to AABB, but first transform your point into the reference from of your OBB. Nick Wiggill's answer is correct. \$\endgroup\$ – RandyGaul Aug 26 '13 at 1:30

Fast ray-box intersection (Andrew Woo)

Graphics Gems (volume I) page 395.

source code

There used to be a full version of his original paper online, not not anymore it seems. In future, you can use this reference when you need any intersection test algo's.

FYI, this algorithm is derived from Amanatides & Woo's seminal paper on 3D-DDA, if you want some insight into how the diff logic operates.

| improve this answer | |
  • \$\begingroup\$ many thanks, sadly the points are not axis aligned nor parallel (sorry the question title is misleading!) \$\endgroup\$ – aadster Oct 28 '12 at 17:53
  • \$\begingroup\$ @user1130477 Not a problem... Did you read the reference I gave you there? That should sort you out. \$\endgroup\$ – Engineer Oct 28 '12 at 17:53
  • \$\begingroup\$ yes, thanks, Im looking at the convex polyhedron solution now.. I guess the scenario is similar to a clipping frustum (Edit, actually, the faces arent parallel, so no its not! hehe) \$\endgroup\$ – aadster Oct 28 '12 at 17:55
  • \$\begingroup\$ @user1130477 Not going for ray-plane then? I guess that it might be a little faster if all eight points of the cuboid are rapidly transformed into an axis aligned space, with the ray, then calculated that way? I think because polyhedra are more generalised, that even non-axis-aligned cuboid tests may be faster than ray-polyhedra tests. \$\endgroup\$ – Engineer Oct 28 '12 at 17:58
  • \$\begingroup\$ the problem is that faces arent planar, let alone axis aligned. I could effectively tessellate the test volume to 12 triangles and perform the test on that, but I still need to generate 3 parameters which I will later use for tri-linear interpolation. I was wondering whether I could use a barycentric approach of vertex weightings as starting point \$\endgroup\$ – aadster Oct 28 '12 at 18:04

Generate BSP (Binary Space Partioning) using the Cuboid. Each face of the cuboid is the partioning plane, and define the inside volume to be the volume that is always on the same subspace of all the faces. E.g:

  1. Get next face. Calculate if point is in front or behind the plane

    1. A: If it is behind, point is outside.
    2. B: If it is in front, goto 1
  2. If you pass all the tests, point is inside

| improve this answer | |
  • \$\begingroup\$ thanks, that approach will certainly work and is what Im implementing for now.. Ive not been very clear about what I need the test to perform- essentially this is a search for a UVW coordinate somewhere in a voxel grid. The UVW coordinates are propagated using navier stokes so can be highly twisted. After Ive found a voxel which contains the UVW coord I need to tri-linearly interpolate to an exact location, so its essential that I get the 3 0..1 tri-lin interpolants. Ideally, Id find a transform which would put my test point in the space of the volume. i.e. 0..1 indicates inside the volume \$\endgroup\$ – aadster Oct 28 '12 at 19:57
  • \$\begingroup\$ wondering if its possible to generate a matrix that would describe the transformation from a unit cube to 8 arbitrary points in space? \$\endgroup\$ – aadster Oct 28 '12 at 20:00
  • \$\begingroup\$ to explain how complex the scenario is likely to be, here's an image... sites.google.com/site/adamvanner/home/voxelUVWsample.JPG ... I have highlighted the top and bottom faces of the "cube" of samples in green for clarity. I wanted to show how the samples can be twisted. the image on the right shows the same samples, but Ive radially tessellated each quad into 4 triangles, so actually, a plane test wont work as the normal to a side could be reversed... maybe this is all just impossible? \$\endgroup\$ – aadster Oct 28 '12 at 20:20
  • \$\begingroup\$ @aadster, Ok, i read the new question \$\endgroup\$ – Zhen Oct 28 '12 at 22:10

I think the solution to this problem in the scenarios Im certain to encounter (twisted sample points which dont maintain an "inside" and "outside" to the form) with this is to approach this as a transform to move a unit cube to the "cube" described by the 8 (most likely twisted & incoherent) sample points.

If it is possible to create such a transform, it means I can both test whether a point lies within this volume as well as generating the interpolation parameters needed for tri-linear and tri-cubic interpolation

To make this all clearer, Ive asked a more specific question!

matrix to transform unit cube to space defined by 8 arbitrary points


| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.