Finding out if a point is inside a "distorted cube"
Author
I'm working on a 3d engine which will feature cubic surfaces, whose detail level will be adjusted to the speed of the computer. The problem is that I need a way to perform hit tests between objects which will be independent of the current detailo level, and therefore I've come up with a simple-in-theory method.
Divide the world and all objects into "distorted cubes". By distorted cubes I mean volumes which have got the same number of points and manner of connecting them as a cube, though each point can have any position. Then I could simply check if one point in a cube is inside another cube, and here comes the problems. How do I do that?
I tried using a tri-linear formula and getting the x, y and z coords from it, to check if they are in range. However, after messing with it for a week, I sent it to some maths teacher, who told me that the equation had six solutions!
So, do anyone know how to do this, or is it plain impossible?
Regards, Alexander Toresson
Hey, you have invented the Descent engine, 9 years too late :) Its entire worlds were made out of distorted cubes, with their sides used as portals.
I'm not exactly sure about this, but this should be right:
If you want to know if a point is within a cube, or any convex volume for that matter, you can do a simple test. Each of the cube faces is a polygon. Each polygon lies on a plane. This plane has a normal that faces the outside of the cube. Now, if your point is on the back side (opposed to the normal) of all the faces of your convex volume, that means the point is inside the convex volume. If the point is in front of any of the planes, that means the point is not in the cube. This test will tell you if any point is inside the cube or not. Whatever the orientation of the cube is, it will work.
You just have to calculate the parameters for the 6 surface planes of the cube and then you can easily perform the test.
Good luck marine! :)
If you want to know if a point is within a cube, or any convex volume for that matter, you can do a simple test. Each of the cube faces is a polygon. Each polygon lies on a plane. This plane has a normal that faces the outside of the cube. Now, if your point is on the back side (opposed to the normal) of all the faces of your convex volume, that means the point is inside the convex volume. If the point is in front of any of the planes, that means the point is not in the cube. This test will tell you if any point is inside the cube or not. Whatever the orientation of the cube is, it will work.
You just have to calculate the parameters for the 6 surface planes of the cube and then you can easily perform the test.
Good luck marine! :)
You could break your cubes into tetrahedrons (4-point solids) and use barycentric coordinate concepts to test whether a point is inside each of the tetrahedrons?
Depending on how distorted Mr. Cube becomes, this may be the easiest option(?)
Depending on how distorted Mr. Cube becomes, this may be the easiest option(?)
Here's another way:
If your 'distorted cube' can be represented as a matrix transformation of a 'unit cube' (a cube of length 1 on each axis centred around the origin) this method will work.
Transform your point by the inverse of the matrix and then do a check as follows:
if ((transpoint.x >= -0.5f) && (transpoint.x <= 0.5f) && (transpoint.y >= -0.5f) && (transpoint.y <= 0.5f) &&
(transpoint.z >= -0.5f) && (transpoint.z <= 0.5f))
{
// point is inside the cube.
}
Obviously, you can precalculate your inverse matrix and attach it to each cube before your main loop begins.
But that's assuming your 'distorted' cube *can* actually be represented as a transformation of a unit cube :D
If your 'distorted cube' can be represented as a matrix transformation of a 'unit cube' (a cube of length 1 on each axis centred around the origin) this method will work.
Transform your point by the inverse of the matrix and then do a check as follows:
if ((transpoint.x >= -0.5f) && (transpoint.x <= 0.5f) && (transpoint.y >= -0.5f) && (transpoint.y <= 0.5f) &&
(transpoint.z >= -0.5f) && (transpoint.z <= 0.5f))
{
// point is inside the cube.
}
Obviously, you can precalculate your inverse matrix and attach it to each cube before your main loop begins.
But that's assuming your 'distorted' cube *can* actually be represented as a transformation of a unit cube :D
Using the equations of the 6 planes bounding it is probably the distorted cube is probably the easiest way; search for any tutorial on frustum culling, and you can probably adapt it to work with your cube's corners as vertices.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
