|
![](/i/fill.gif) |
As promised in my previous post, here is my intersection routine. You
cannot use it directly as it's a C++-ified version, but i think you'll
get the general idea behind it. It's *much* faster than the original
version.
//============================================================================
// CSG_INTERSECTION::AllObjectIntersections:
//
// Author: POV-Ray Team
/* AKA:
To get an intersection for a CSG-Intersection object, it must be
contained within all objects (TODO: if the given objects don't
overlap anywhere, detect it during the parsing stage.)
So the original algorithm loops twice over all objects:
The outer loop retrieves all intersection points for each of the
objects.
The inner loop checks, whether any of these intersections is
inside of all other objects (which would lead to a hit).
It's short and simple, bot not very effective.
Imagine i.e. the following difference object,
difference
{
union { ...} // A complex union
object { small_sphere1 }
...
object { small_sphere1000 }
... // texture etc.
}
to create a sponge. Assume a ray that results in 1000 intersection
points from the union, but no hit for the inverted small spheres.
The latter means: No hit but the ray's origin is inside of each of
the inverted spheres, so the entire ray is inside of each of the
spheres.
==> It's not necessary do any sphere-inside-test for any of the
intersection points.
I changed it to three independend steps:
1. Retrieve all intersections of the not-inverted children:
If a child is not intersected:
if ray's origin is outside of this child, the whole CSG isn't
intersected, else the entire ray is inside of this child, so
it can be ignored completely in 3.
Else, the intersections and the child are stored for step 3.
2. Same as 1. for all inverted children.
They are handled seperately because of a BBOX tree effectively
speeds up calculations:
If a finite node isn't hit, we can ignore any of it's leaf
objects as the entire ray must be inside of each leaf object.
This saves a lot of intersection tests.
3. Each intersection, that is inside of each of the children
retrieved above, is a valid CSG intersection.
It doesn't make sense to use the not-inverted children in a BBOX
tree. The CSG's BBOX is computed as the intersection of all
not-inverted children bounding boxes.
If a ray hit's the CSG's BBOX, it will also hit each BBOX of each
not-inverted child.
*/
bool CSG_INTERSECTION::AllObjectIntersections(RAY &Ray, ISTACK
*Depth_Stack, DBL BestDepth) const
{
bool maybeFound(false), found(false), escape(false),
rayFlagsTest(false);
OBJECT *o;
int childIdx;
void *IntersectionCSG = GetFlagMultiTextured() ? (void*) this :
NULL;
Increase_Counter(stats[Ray_CSG_Intersection_Tests]);
OBJECTLIST *hitQueue = ObjectListPool.Request();
ISTACK *localStack = IstackPool.Request();
// First stage:
// Test all not-inverted objects, try to escape as early as
possible.
for (childIdx = 0; !escape && (childIdx < m_notInvChildren.size());
++childIdx)
{
o = m_notInvChildren[childIdx];
if (o->AllIntersections(Ray, localStack, BOUND_HUGE))
hitQueue->push_back(o);
else
{
if (!o->Inside(Ray.Initial))
{
// The entire ray is outside of >o<, we can escape now.
// SetAsFirstSib(childIdx);
escape = true;
}
// else the ray starts from within >o< never hitting any
// boundary, it can be ignored completely.
}
}
// Second stage: Get all intersections of the inverted objects
if (!escape)
{
if (BBox_Tree != NULL)
escape = IntersectCsgIntersectionTree(BBox_Tree, hitQueue, Ray,
localStack);
else
{
// No BBox Tree of inverted siblings, step through children
list.
for (childIdx = 0; !escape && (childIdx < Children.size());
++childIdx)
{
o = Children[childIdx];
// Test objects AABB before intersection test
if (!o->BBoxTestPassed(Ray, BOUND_HUGE))
{
// no AABB hit
if (!o->Inside(Ray.Initial)) // entire ray is outside of
>o<
escape = true;
continue; // with next object or escape
}
if (o->AllIntersections(Ray, localStack, BOUND_HUGE))
hitQueue->push_back(o);
else
{
if (!o->Inside(Ray.Initial))
{
escape = true;
break;
}
}
}
}
}
// Third stage: Now we have a list of intersections in 'localStack'
and a
// list of intersected objects in 'hitQueue'.
// Get all intersections, that are inside of all objects.
if (!escape)
{
for (int i = 0; i < localStack->size(); ++i)
{
maybeFound = true; // new intersection to be checked
INTERSECTION &locIsec = (*localStack)[i];
const OBJECT *obj = locIsec.Object;
VECTOR &iPoint = locIsec.IPoint;
if ((locIsec.Depth < BestDepth) && PointInClip(iPoint))
{
for (int j = 0; j < hitQueue->size(); ++j)
{
const OBJECT *hitObject = (*hitQueue)[j];
if ((hitObject != obj) && !hitObject->Inside(iPoint))
{
maybeFound = false; // missed object '(*hitQueue)[j]'
break; // try the next intersection
}
}
if (maybeFound)
{
found = true;
INTERSECTION &isec = push_copy(Depth_Stack, locIsec);
isec.Object = this;
if (NULL != locIsec.Csg) // the child is a CSG itself
isec.Csg = locIsec.Csg;
else // it was a simple child
isec.Csg = locIsec.Object;
}
}
}
}
IstackPool.Release(localStack);
ObjectListPool.Release(hitQueue);
if (found)
Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
return(found);
}
Post a reply to this message
|
![](/i/fill.gif) |