Test if ray AABB overlaps node
If no {return false}
If yes
{
Check if current node is split
If yes{recall itself but pointing to the 8 subnodes}
If no
{
For(i = 0; i < node's polycount; i++)
{
Construct AABB of node's polygon
Test ray's AABB against polygon's AABB
If overlap
{
Add to an array of polygons*
}
}
}
}
Creating list of polygons during AABB-Octree test
Author
Hi guys. I have a ray in 3d space and an octree, and I want to test which polygons the ray intersects. I create an aabb around the ray and test this against the octree, however how would you guys suggest I keep the list of polygons to test if it intersects against?
For the octree traversal function I'll test if there's an overlap between the ray's AABB and the node, then I'll test each polygon's AABB against the ray's AABB to reduce the amount of intensive calculations (i.e. actually calculating where the ray hits each polygon's plane e.t.c.).
At the moment I have a collision function which will test an array of polygons against a ray, so before testing I want to produce a complete array which I can use (can have repeating polygons since I may use a timestamp idea for polygons). I'm planning to write the traversal function called testAABB_OctreePolys(6 f32s for the max and min coords of the AABB, pointer to an octree node initially the octree head) which will do the following:
You might want to consider writing the routine to use ray-box intersection tests to traverse the octtree instead of box-box tests. The ray-box test will be more expensive but it will intersect less leaf nodes when the ray is at an angle with respect to the octtree axes.
For building the list of polygons, you can pass the list as an argument to the recursive function (or use a single globally visible list).
For building the list of polygons, you can pass the list as an argument to the recursive function (or use a single globally visible list).
Author
Cheers for the idea. I may implement a Ray-AABB test instead of an AABB-AABB test, although I'm using fairly small rays which are significantly smaller than the smallest size of an octree node so I'll compare each method during runtime.
For creating the list of polygons, I'm hesitant to use a global array as I'm not sure how many polygons will be needed for each frame and I'd have to declare the array to be fairly large so I don't run out of space in the array. Althought I'm not sure what other ideas to use, so I may just do this (unless I traverse the list once, count how many polygons I have to test, create an array of this size and then re-traverse the octree to actually get the polygons into the array - a waste of time though).
For creating the list of polygons, I'm hesitant to use a global array as I'm not sure how many polygons will be needed for each frame and I'd have to declare the array to be fairly large so I don't run out of space in the array. Althought I'm not sure what other ideas to use, so I may just do this (unless I traverse the list once, count how many polygons I have to test, create an array of this size and then re-traverse the octree to actually get the polygons into the array - a waste of time though).
I second the ray AABB, for a start. Especially with octrees. You can pre-compute the expensive part of the ray-AABB intersection test, the divisions.
That's the first step anyway.
the '... / (ray_direction)', that can be pre-computed (for each axis, x, y and z) prior to testing the octree, because that will never change (the box axes will always be along the global x, y and z axis). Then you save quite a few divisions.
Secondly, there are loads more you can deduce when using an octree. You can save the parent's enter and exit point (t_enter and t_exit), and only calculate the intersection of the ray and the planes originating from the parent's centre position.
Then you can deduce which of the child boxes actually intersects the ray (given the order of the intersection params). So you don't actually end up doing a ray-AABox intersect in the end, more like a slimlined, specific test.
So in the end, a LOT faster than building a box around the ray and culling, if your rays are long (short rays, the bounding box should be sufficent).
Also, you do not necesseraly need to store all triangles intersected by the ray. Most of the time, you want to stop at the first intersection anyway.
That will bring a lot of optimisations. First of all, depending on the direction of the ray, you want to test the child boxes in a specific order, to have a greater chance of catching that first intersection early. That's easy to precompute as well (it's a factor of the sign of the ray direction).
Also, the t_enter, t_exit values can be modified 'on the go', as you start intersecting triangles. Then everything with a intersection param > than your smallest t_exit can be rejected. All you need to store is just one triangle, the first intersected.
If you have more quirky features, such as semi transparent polygons, or you want only the first 10 triangles intersected, then you can adapt the algo accordingly. But tracing through the whole ray length is very often wasteful.
bool RayIntersectInterval(float interval_min, float interval_max, float ray_origin, float ray_direction, float& t_enter, float &t_exit){ // ray is aligned with that interval direction if (fabs(d) < 0.000001f) return true; // compute the intersection params float u0, u1; u0 = (interval_min - ray_origin) / (ray_direction); u1 = (interval_max - ray_origin) / (ray_direction); // sort them (t1 must be >= t0) if (u0 > u1) swapf(u0, u1); // check if the intersection is within the ray range if (u1 < t_enter || u0 > t_exit) return false; // Update the ray range t_enter = max(u0, t_enter); t_exit = min(u1, t_exit); // Ah. we missed the interval return (t_exit >= t_enter);}bool RayIntersectAxisAlignedBox(Vector& BoxMin, Vector& BoxMax, Vector& RayOrigin, Vector& RayDirection, float& t_enter/*=0.0f*/, float& t_exit/*=ray_length*/){ // x axis if(!RayIntersectInterval(BoxMin.x, BoxMax.x, RayOrigin.x, RayDirection.x, t_enter, t_exit)) return false; // y axis if(!RayIntersectInterval(BoxMin.y, BoxMax.y, RayOrigin.y, RayDirection.y, t_enter, t_exit)) return false; // z axis if(!RayIntersectInterval(BoxMin.z, BoxMax.z, RayOrigin.z, RayDirection.z, t_enter, t_exit)) return false; return true;}That's the first step anyway.
the '... / (ray_direction)', that can be pre-computed (for each axis, x, y and z) prior to testing the octree, because that will never change (the box axes will always be along the global x, y and z axis). Then you save quite a few divisions.
Secondly, there are loads more you can deduce when using an octree. You can save the parent's enter and exit point (t_enter and t_exit), and only calculate the intersection of the ray and the planes originating from the parent's centre position.
Then you can deduce which of the child boxes actually intersects the ray (given the order of the intersection params). So you don't actually end up doing a ray-AABox intersect in the end, more like a slimlined, specific test.
So in the end, a LOT faster than building a box around the ray and culling, if your rays are long (short rays, the bounding box should be sufficent).
Also, you do not necesseraly need to store all triangles intersected by the ray. Most of the time, you want to stop at the first intersection anyway.
That will bring a lot of optimisations. First of all, depending on the direction of the ray, you want to test the child boxes in a specific order, to have a greater chance of catching that first intersection early. That's easy to precompute as well (it's a factor of the sign of the ray direction).
Also, the t_enter, t_exit values can be modified 'on the go', as you start intersecting triangles. Then everything with a intersection param > than your smallest t_exit can be rejected. All you need to store is just one triangle, the first intersected.
If you have more quirky features, such as semi transparent polygons, or you want only the first 10 triangles intersected, then you can adapt the algo accordingly. But tracing through the whole ray length is very often wasteful.
This ray-octree think is mostly valid for long rays, like AI, visibility tests, bullets, things like that. for short rays, the box culling is very fast, and you will not get any benefits from doing a proper ray-octree test.
Short rays? I think we might be talking about line segments here. A ray has infinite length, so as far as I know there's no such thing as a short ray. The optimizations are similiar either way.
For building the list of polygons, a resizable array might be appropriate. If you're using C++ then just use a vector. C++'s std::vector works by allocating a new block of memory twice as large as the old one and copying all the elements over if you try to push_back an element when all the capacity has been used. You can reuse the same vector between calls so this reallocating and copying will not happen frequently (unless the number of intersections is constantly rising). You can also reserve space which will prevent the allocating and copying unless the number of collisions is greater than the value you reserved.
Another possibility is to use a fixed size array and also return information if there are possibly more intersections that weren't found and the data necessary to perform another check to find more intersections (the point where this run of the algorithm ran out of memory). Then if it ran out of memory you just process those intersections and then run the algorithm again, starting from where the previous run left off. Continue until it returns that it found all intersections (did not run out of space). For efficiency, you can separate any precomputations from the main algorithm (you'd have at least two functions, one for precomputing things and another that takes the precomputed data and uses it to run the actual algorithm).
For building the list of polygons, a resizable array might be appropriate. If you're using C++ then just use a vector. C++'s std::vector works by allocating a new block of memory twice as large as the old one and copying all the elements over if you try to push_back an element when all the capacity has been used. You can reuse the same vector between calls so this reallocating and copying will not happen frequently (unless the number of intersections is constantly rising). You can also reserve space which will prevent the allocating and copying unless the number of collisions is greater than the value you reserved.
Another possibility is to use a fixed size array and also return information if there are possibly more intersections that weren't found and the data necessary to perform another check to find more intersections (the point where this run of the algorithm ran out of memory). Then if it ran out of memory you just process those intersections and then run the algorithm again, starting from where the previous run left off. Continue until it returns that it found all intersections (did not run out of space). For efficiency, you can separate any precomputations from the main algorithm (you'd have at least two functions, one for precomputing things and another that takes the precomputed data and uses it to run the actual algorithm).
Author
Cheers for the replies guys!
I think since I'll only be using small segments for this test, I'll stick to testing an AABB versus the octree nodes. However thanks for all that info oliii, I'll be sure to make use of it when I implement traversing the octree with longer segments/rays for things like A.I. later on!
I've been thinking about what oliii said, how I don't need to create an array as when I've found an intersection, that's it. So I'm thinking of testing the segment against polygons accurately within the traversal function and using a timestamp to stop duplicate tests, something like:
Would this seem ok? Any improvements? (Must be some I'm inexperienced!)
I think since I'll only be using small segments for this test, I'll stick to testing an AABB versus the octree nodes. However thanks for all that info oliii, I'll be sure to make use of it when I implement traversing the octree with longer segments/rays for things like A.I. later on!
I've been thinking about what oliii said, how I don't need to create an array as when I've found an intersection, that's it. So I'm thinking of testing the segment against polygons accurately within the traversal function and using a timestamp to stop duplicate tests, something like:
COLLISION FUNCTION:{ timestamp++; intersectedPoly = testRayOctree(...); do what else I have to do;}testRayOctree(...){ Test if ray AABB overlaps node If no {return false} If yes { Check if current node is split If yes{recall itself but pointing to the 8 subnodes, return value obtained} If no { For(i = 0; i < node's polycount; i++) { if(polygon.timestamp != timestamp) { polygon.timestamp = timestamp Test the ray against the polygon If there is an intersection and its within the segment size { return i } } } } }}Would this seem ok? Any improvements? (Must be some I'm inexperienced!)
Segments -> [StartPoint, EndPoint].
Ray -> [Origin, Direction (Normalised, preferably), Length].
To do that, if you are only interested in the first triangle intersected, you would need to 'sort' the intersections but intersection time (or distance), from the segment origin. Then you can reject polygons behind that distance / time.
this is my take on it.
Ray -> [Origin, Direction (Normalised, preferably), Length].
To do that, if you are only interested in the first triangle intersected, you would need to 'sort' the intersections but intersection time (or distance), from the segment origin. Then you can reject polygons behind that distance / time.
this is my take on it.
C_Triangle* C_Octree::FirstIntersect(const C_Segment& segment, float& tcoll) const{ if (!GetRootNode()) return false; // watermark the triangles being tested with a unique number. PushTestCounter(); tcoll = 1.0f; return GetRootNode()->FindFirstIntersection(segment, tcoll); }C_Triangle* C_OctreeNode::FirstIntersect(const C_Segment& segment, float& tcoll) const{ C_TrianglePtr* trianglePtr = NULL; // segment not actually intersecting our node. if (!segment.BoundingBox().Intersect(this->BoundingBox())) return false; // leaf node. The node stores a list of triangles intersecting the box around that leaf. if (this->IsLeaf()) { for(int i = 0; i < this->NumTriangles(); i++) { // our triangle const C_Triangle* ptri = this->GetTrianglePtr(i); // already tested that triangle if(ptri->TestCounter() == m_pParentOctree->TestCounter()) continue; // set test counter to our current count ptri->SetTestCounter(m_pParentOctree->TestCounter()); // test intersection with segment, in range [0, tcoll]. if(ptri->Intersect(segment.StartPoint, (segment.EndPoint - segment.StartPoint), tcoll)) { // intersecion found trianglePtr = ptri; } } } // branch node. The node splits into a list of sub branches or leaves. else { for(int i = 0; i < this->NumChildNodes(); i++) { const C_OctreeNode* pchild = this->GetChildNodePtr(i); // get the triangle (if any) intersected in that child node C_Triangle* ptri = pchild->FirstIntersection(segment, tcoll); // yay we got one, intersecting the segment, and is the earliest. if (ptri) trianglePtr = ptri; } } return trianglePtr;}
Author
Cheers oliii, I've implemented the method with your idea of rejecting polygons behind the nearest t_coll and it works well!
Thanks for all the help again! :)
Thanks for all the help again! :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
