Sign in to follow this  
Spa8nky

What would be a sensible method to return collision info in this recursive algorithm?

Recommended Posts

Spa8nky    230
When inserting a ray in an octree I have an algorithm that finds the nodes that the ray intersects. I then test the ray against each object located inside each node found. I would like to return the collision information for the closest object the ray intersected. I therefore compare each confirmed intersection against the current minimum time of collision (tColl) which is initialised to float.MaxValue.
            if (tMin < tMax)
            {
                // Initialise time of ray collision to maximum value
                float tColl = float.MaxValue;

                // Check this node and then its children
                Subtree(node, ray, t0.X, t0.Y, t0.Z, t1.X, t1.Y, t1.Z, a, ref tColl);
            }
I am having difficulty in returning the collision information due to the recursive nature of the method involved:
        private void Subtree(Node_Octree node, CD_Ray ray, float t0x, float t0y, float t0z, float t1x, float t1y, float t1z, int a, ref float tColl)
        {
            if (node == null || t1x < 0f || t1y < 0f || t1z < 0f)
            {
                return;
            }

            // Test any objects in this node for intersection with the ray
            TestNodeObjectsRay(node, ray, ref tColl);

            node.DrawNode = true;

            float tMx = 0.5f * (t0x + t1x);
            float tMy = 0.5f * (t0y + t1y);
            float tMz = 0.5f * (t0z + t1z);

            // Find the index of the first child node (octant) crossed by the ray 
            int index = 0;
            float max = Math_Util.Max3(t0x, t0y, t0z);

            // |= bit  (Turns bit on)
            // &= ~bit (Turns bit off)

            if (t0x == max)
            {
                // YZ entry plane 
                if (tMy < t0x) index |= 2; // Bit 1 affected (2^1)
                if (tMz < t0x) index |= 1; // Bit 0 affected (2^0)
            }
            if (t0y == max)
            {
                // XZ entry plane
                if (tMx < t0y) index |= 4; // Bit 2 affected (2^2)
                if (tMz < t0y) index |= 1; // Bit 0 affected (2^0)
            }
            if (t0z == max)
            {
                // XY entry plane
                if (tMx < t0z) index |= 4; // Bit 2 affected (2^2)
                if (tMy < t0z) index |= 2; // Bit 1 affected (2^1)
            }

            // [Child Node Indices]
            //            z
            //           /
            //          /
            //        __________
            //       / 3  / 7  /|
            // y    /____/____/ |
            // |   /  2 / 6  /|7|
            // |  /____/____/ |/|                   [Original Paper]
            //    |  2 | 6  |6|5/
            //    |____|____|/|/
            //    |  0 | 4  |4/
            //    |____|____|/   --- x 

            while (index != 8)
            {
                switch (index)
                {
                    case 0:
                        {
                            Subtree(node.child[a], ray, t0x, t0y, t0z, tMx, tMy, tMz, a, ref tColl);
                            index = NextSubNode(tMx, 4, tMy, 2, tMz, 1);
                            break;
                        }
                    case 1:
                        {
                            Subtree(node.child[1 ^ a], ray, t0x, t0y, tMz, tMx, tMy, t1z, a, ref tColl);
                            index = NextSubNode(tMx, 5, tMy, 3, t1z, 8);
                            break;
                        }
                    case 2:
                        {
                            Subtree(node.child[2 ^ a], ray, t0x, tMy, t0z, tMx, t1y, tMz, a, ref tColl);
                            index = NextSubNode(tMx, 6, t1y, 8, tMz, 3);
                            break;
                        }
                    case 3:
                        {
                            Subtree(node.child[3 ^ a], ray, t0x, tMy, tMz, tMx, t1y, t1z, a, ref tColl);
                            index = NextSubNode(tMx, 7, t1y, 8, t1z, 8);
                            break;
                        }
                    case 4:
                        {
                            Subtree(node.child[4 ^ a], ray, tMx, t0y, t0z, t1x, tMy, tMz, a, ref tColl);
                            index = NextSubNode(t1x, 8, tMy, 6, tMz, 5);
                            break;
                        }
                    case 5:
                        {
                            Subtree(node.child[5 ^ a], ray, tMx, t0y, tMz, t1x, tMy, t1z, a, ref tColl);
                            index = NextSubNode(t1x, 8, tMy, 7, t1z, 8);
                            break;
                        }
                    case 6:
                        {
                            Subtree(node.child[6 ^ a], ray, tMx, tMy, t0z, t1x, t1y, tMz, a, ref tColl);
                            index = NextSubNode(t1x, 8, t1y, 8, tMz, 7);
                            break;
                        }
                    case 7:
                        {
                            Subtree(node.child[7 ^ a], ray, tMx, tMy, tMz, t1x, t1y, t1z, a, ref tColl);
                            index = 8;
                            break;
                        }
                }
            }
        }

This is the method which checks for intersection:
        private void TestNodeObjectsRay(Node_Octree node, CD_Ray ray, ref float tColl)
        {           
            for (int i = 0; i < node.objects.Count; ++i)
            {
                collisionTests++;
                Contact3D contact_Current = new Contact3D();
                if (Detection3D.TestShapeShape(ray, node.objects[i].shape, ref contact_Current))
                {
                    if (contact_Current.t_Enter < tColl)
                    {

                    }
                }
            }
        }

How would you guys suggest returning the collision information associated with the closest object intersected? I believe that if the node has no children (therefore next sub node == null) and an object has already been intersected by the ray, then there is no need to check further nodes. How could I factor that in also? Thanks.

Share this post


Link to post
Share on other sites
Zeraan    317
I noticed that your recursive function is not returning anything. Maybe if you return the node that is intersected, and have the function check to see if the return value is not null, then proceed with recursion. If the returned value is a node, then halt and return that node.

Same concept for current node being intersected, just return that node and don't check the subnodes.

Hope this helps!

Edit: By returning a node I mean this way:

private Node_Octreee SubTree(...)
{
if(!TestNodeObjectsRay(...))
{
//check all child nodes here
foreach(node in list of nodes)
node = SubTree(...);
if(node != null)
return node;
}
else
return current node;
}

private bool TestNodeObjectsRay(...)
{
if(intersected)
return true;
else
return false;
}




[Edited by - Zeraan on March 17, 2010 12:48:07 PM]

Share this post


Link to post
Share on other sites
Spa8nky    230
I've been looking at this and I still don't follow how I can apply this to my method?

My method starts with the root and then checks child nodes based on indices. There would be no need to check all child nodes of a node for ray intersection as your code suggests.

I need some way of escaping the recursion should the node == null (i.e. it is a terminal node) and an object has been found to be intersecting.

I apologise, but I can't understand how your example works in this case:


private void Subtree(Node_Octree node, CD_Ray ray, float t0x, float t0y, float t0z, float t1x, float t1y, float t1z, int a, ref float tColl)
{
if (t1x < 0f || t1y < 0f || t1z < 0f)
{
return;
}

// Terminal node
if (node == null)
{
// Return closest object intersected if one has been found in the terminal node

// Else continue with method
}

// Test any objects in this node for intersection with the ray
TestNodeObjectsRay(node, ray, ref tColl);






EDIT:

Something of this ilk:


case 0:
{
if (node.child[a] != null)
{
// Test any objects in this node for intersection with the ray
// Replace the closest object if a closer one has been found
TestNodeObjectsRay(node, ray, ref tColl);
Subtree(node.child[a], ray, t0x, t0y, t0z, tMx, tMy, tMz, a, ref tColl);
}
else
{
// This is a terminal node
if (TestNodeObjectsRay(node, ray, ref tColl))
{
// If a closer has been found in this node, exit the method and return that object

}
}
index = NextSubNode(tMx, 4, tMy, 2, tMz, 1);
break;
}




Can someone tell me how I can directly exit the algorithm for the terminal node case?

[Edited by - Spa8nky on March 18, 2010 8:54:12 AM]

Share this post


Link to post
Share on other sites
haegarr    7372
I (using C++) represent a single hit by a SurfaceInfo instance. That class refers to the Surface instance (maybe a Mesh or an ImplicitAlgebraicSurface), stores the point of intersection, the distance on the ray's track, and later on more (e.g. the surface normal vector).

However, is this intersection for a ray-tracer or just for some test? I ask because a featured ray-tracer typially needs more informations than the closest hit. E.g. it must detect whether the closest hit is entering or leaving a shape's volume (i.e. whether the camera is inside a volume). It may further need to deal with Boolean operations on objects, in which case it not only needs to know the closest entree/exit into a shape volume but all ones. For such case I use a SpanList what is a list of, well, Span instances. Each Span denotes an entree and its exit into/out the Shape it points to. The SpanList sorts the Spans accordingly to the distance of the entrees. Then Boolean operation are done on SpanLists.

Share this post


Link to post
Share on other sites
Spa8nky    230
When a smaller tColl value is found, the parameters are stored in the following class:


public class Contact3D
{
public IOctree_Object[] body; // Two rigid bodies involved in the collision pair
public Vector3 normal; // Contact normal
public float penetration; // Penetration depth (at the contact point)
public Vector3 point; // Contact point [World Coordinates]
public float t_Enter; // Time of first collision (point of entry)
public float t_Exit; // Time of last collision (point of exit)

public Contact3D()
{
body = new IOctree_Object[2];
normal = Vector3.Zero;
penetration = 0.0f;
point = Vector3.Zero;
t_Enter = 0.0f;
t_Exit = 1.0f;
}
}



I would be returning that class if possible, but I can't figure out how to do so in an efficient manner. Only one body will need to be stored in this case.

In terms of context, this algorithm will be used for selecting objects in 3D space with a mouse pointer ray and for creating decals on the nearest object when a gun is fired.

Share this post


Link to post
Share on other sites
haegarr    7372
Does the programming language in use allow to pass-by-reference? If so, then why not allocate a Contact3D inside the invoking client and pass it by reference instead of tColl to each TestNodeObjectsRay(...)? The structure may be filled in several times, but at the end the fill-in computed from the closest hit will remain.

Share this post


Link to post
Share on other sites
Zeraan    317
Quote:
Original post by Spa8nky
I've been looking at this and I still don't follow how I can apply this to my method?

My method starts with the root and then checks child nodes based on indices. There would be no need to check all child nodes of a node for ray intersection as your code suggests.

I need some way of escaping the recursion should the node == null (i.e. it is a terminal node) and an object has been found to be intersecting.

I apologise, but I can't understand how your example works in this case:

*** Source Snippet Removed ***

EDIT:

Something of this ilk:

*** Source Snippet Removed ***

Can someone tell me how I can directly exit the algorithm for the terminal node case?


My bad. You don't have to check all of the child nodes. What I'm trying to say is that you first check the current node to see if it's intersected, as seen in "if(!TestNodeObjectsRay(...)". If it returns true, it means current node is intersected, and you go to "else" which returns current node without going into any of the child nodes. Otherwise check the child node, and if it returns null, you return null from that. If it doesn't return null, then you've found a node that's intersected by the ray. If there's no child nodes, and the node isn't intersected, just return null.

Does that help?

Edit: After looking at your code a bit, it looks like it only goes into one child node. So if it all returns null, then you know that none of your nodes got intersected.

2nd Edit: You could return tColl class instead of Node class. But if you need both, create a container class that stores both and you can return that class instead.

Share this post


Link to post
Share on other sites
Spa8nky    230
Quote:
Original post by haegarr
Does the programming language in use allow to pass-by-reference? If so, then why not allocate a Contact3D inside the invoking client and pass it by reference instead of tColl to each TestNodeObjectsRay(...)? The structure may be filled in several times, but at the end the fill-in computed from the closest hit will remain.


Yes it does :)

So I can pass the Contact3D around by reference and then compare the t_Enter parameter with the current Contact3D's parameter. If lower, then it becomes the new reference Contact3D.

How do I exit the recursive SubTree() method immediately if the referenced Contact3D has been replaced in a terminal node?

Thanks for the help guys.

Share this post


Link to post
Share on other sites
Zeraan    317
Quote:
Original post by Spa8nky

Yes it does :)

So I can pass the Contact3D around by reference and then compare the t_Enter parameter with the current Contact3D's parameter. If lower, then it becomes the new reference Contact3D.

How do I exit the recursive SubTree() method immediately if the referenced Contact3D has been replaced in a terminal node?

Thanks for the help guys.


You could add a variable to function arguments, "out isChanged", and when that function call ends, you check to see if "isChanged" is true, if so, then return, and return isChanged to parent function that called the current function. That's one way that I can think of.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this