Octrees: Triangle/Cube intersection

Hello all,

I'm implementing octrees which will contain a list of triangles. While the implementation is quite obvious I just keep wondering: what is a good algorithm to test whether a triangle is inside a cube? I've done quite a lot of googling, but every resource skips over this part.
I could probably think of a really crappy way (testing every possible situation on the relative position of the triangle). But there must be a better way.
Another resource said that you could transform the cube into a voxel and then said there was an algorithm to detect the intersection between the two, though it was a reference to a book I don't have.

Thanks in advance

Without knowing more about the context of the box (axis aligned perhaps?), I can't say what's going to be fast within your context.

If, for example, the box were always aligned with the world axis (and aligned bounding box, for example), then you could express the box as a set of maximum extents for each axis. That is, the box left is xL, right is xR, top is yT, bottom is yB, near is zN, far is zF.

Any point is NOT inside the box if any of that point's coordinates exceed these boundaries (that is, can't be more left than xL, can't be more right than xR, etc.).

It reduces the test to a series of 6 comparisons per vertex.

If your box is not axis aligned, then you may need to use a property of the "dot product" to help.

Each side of the box would have a normal. The normal gives you the 'direction' of the plane's perpendicular, which is often used for light calculations. The same calculation used to determine if light should be reflected, or if a face is toward or away from the camera, can tell you if the vertex in question is 'in front of' or 'behind' a face.

The normal used on a visible box would face 'outward'. As such, testing a vertex on the inside of a box would produce a result with the opposite sign - that is, if you used the normal already used for lighting or face culling, you're interested in 'negative' results, not positive ones.

Anyway, if a point is inside the box, it would have to be 'on the same side' of all planes that comprise the box - that is, inside the box. If the vertex were not 'on the same side' of any one plane as all of the others, it couldn't be inside the box.

Code:

       ^
       |
    -------
    |     |
<---|  A  |---->
    |     | B
    -------
       |
       v

Vertex A would be 'behind' each of the normals of the 4 sides depicted. It works the same in 3D, just with two more sides to consider.

Vertex B is "on the same side" of 3 of the 4 sides, just like A. However, B is on the "other" side of the box's right side, so it's not inside the box.

I'll leave it to you to google the dot product in context of various uses, like face culling, light calculations, etc.

Hello JVene,

Thank you for your answer. Sorry for not specifying the fact that the box is axis aligned (do non-axis aligned octrees exist?)
However, I'm not trying to find out if a point is inside the axis aligned cube: I'm trying to find out if any point of a triangle (of which, of course, there are infinite) is inside the cube. If any of the three vertices is inside the cube it's easy to say of course. However the problem cases are when one vertex is on one side of the cube and one vertex is on the other side.

Thanks

The 3 vertices which define the triangle define the extents of the triangle.

The problem circumstance you're indicating would appear if two vertices of the triangle are outside the box, yet the line connecting these two cross into the interior of the box.

This can only happen with respect to the relative position of the triangle's vertices and the planes defining the box.

An adaptation of the cohen-sutherland line clipping algorithm, which is described for 2D, is in the area of what you're looking for.

Originally Posted by JVene

The problem circumstance you're indicating would appear if two vertices of the triangle are outside the box, yet the line connecting these two cross into the interior of the box.

Thanks for your answer.

Well, that is a second case. There is also a case where none of the lines crossing vertices intersect the box. There is one other situation, where for instance the line crossing 2 vertices is somewhere beneath the cube, and the other vertex above the cube. A 2D equivalent would be a triangle with a square inside.
That, I believe, are the only three cases I would have to consider.

Any idea on a good algorithm for this final case?

It is typical to break aligned box problems like this into 2d problems in each of the 3 axis. Cohen-sutherland deals with all the potential line crossings, and you test each of the 3 lines of the triangle. The test is is two phases, you may only need the first phase. The second phase deals with where to clip the line (the intersection of the line and the edge of the rectangle, if it occurs). Cohen-sutherland reduces the problem to determining what 'quadrant' the endpoints are in (including the interior), producing a bitmap of all the possible permutations, then providing a table (usually implemented in a switch) which determine the 'meaning' of a particular pair.

Code:

    p1 |  p2   |
  -----+-------+-----
       |       |
    p3 |       |
       |       |
  -----+-------+-----
       |       |

I forget the details, google reveals several discussions, but you'd skip the clipping step. Simply determining the relative position of p1 to p2, p1 to p3 to the square 'decides' that these two lines don't intersect the square, but the relative position of p2 to p3 indicates it does. If that's as far as you require, you're done (in 2D).

You'd have to test the p2-p3 pair against the other axis, but (I forget exactly where I first read this, probably in one of Eberly's books), if the line doesn't cross in 2d, it doesn't cross in 3d. There's a proof on that somewhere, too - but now I'm reaching back over a decade to recall my source.

Is this part of a contact/collision test, or something else?


Edit:

The general topic you're asking about approaches the tenets of collision/contact (a broad subject about object intersections), and I'd recommend on of the books in the Morgan-Kaufman series. David Eberly gives excellent treatments (he's a PhD in math, and a game developer), but also there's a book devoted to real time collision detection (words to that effect are it's title) from that publisher that go into exquisite detail.

Thank you for your answer. I'm going to look into that algorithm as soon as I have time.

Originally Posted by JVene

Is this part of a contact/collision test, or something else?

No; it's for detecting which nodes in the octree contains which triangles. The scene consists on triangles. I'll use the octree mostly for faster collision detection (so, yes, it's part of a collision test eventually), and not having to render the entire scene (only the nodes of the octree that are visible).

Look for the book "Real Time Collision Detection" by Christer Ericson, published by Morgan-Kaufmann, or one of the texts by David Eberly, same publisher. Eberly covers everything from rendering, culling to physics and special effects regarding his game engine Wild Magic.

Ericson focuses in great detail on the subject of contacts, collisions and all things regarding scene management related to this topic.

Ian Millington (sp), in his book "Game Physics Engine Development", from the same publisher, gives a good, gentle coverage of contact/collision, too.

While these books may currently exceed what you're thinking, the focus is generally on 3D geometry, and the fast methods in game development relative to that, and a huge benefit of experience in commercial grade game engines relative to the need for speed, efficiency, relative accuracy, etc.

What you'll get from any of these texts is that it is an in depth subject, it serves against your interests to focus on small parts of the subject without considering the whole, and unless you are really working on a small subset of the problem for a specific need (that is, you're not making a game - just some illustrative work, or some filter in some editor that doesn't need a generalized solution) you need to consider at least seeing a guided tour of the subject so you know what's been done and the reasoning behind it.