Raycast with compound sub shapes

[Esharc]

Hello Julio.

I am trying to get the sub shape that a raycast is hitting.

The OnRayPrecastAction works correctly and the sub shape is returned but that is before the actual hit is calculated, and I do not know at that point if the sub shape has a hit yet.

In the OnRayCastAction the parent shape and body is returned, but not the sub shape. So at this point I know that I have hit some body in the compound shape, but I do not know which shape I have hit.

Will it be possible to add the sub shape that was hit to the returned contact in OnRayCastAction say have m_shapeInstance1 be the sub shape that was hit and m_shapeInsance0 be the parent shape?

If you need a test case for this, let me know and I can try and add one.

[Julio Jerez]

I explain why that's a bad idea, and I tell you how to do it in your side.

Essentially:
The OnRayPrecastAction member operates at the object level (coarse granularity).
The RayCast member operates at the shape level (fine granularity).

Imagine a scene with many objects made up of compound shapes, and you want to ray cast against their sub-shapes.
Along the ray path, it may intersect several compound objects before finding the one you’re actually interested in.

If OnRayPrecastAction had to determine which specific sub-shape the ray hit, it would waste a lot of CPU time unnecessarily.
This would increase the ray cast’s time complexity—from being linear in the number of objects along the ray’s path to being proportional to the number of objects times the number of sub-shapes per object.
That’s not ideal for most cases, so there should be a better approach.

The function you should look at is:

Code: Select all

ndFloat32 ndShapeInstance::RayCast(
    ndRayCastNotify& callback,
    const ndVector& localP0,
    const ndVector& localP1,
    const ndBody* const body,
    ndContactPoint& contactOut
) const


If you look at the ndRayCastNotify class, you’ll see it contains a contact member that provides all the necessary hit information, after the shape was casted by RayCast function.
In most cases, this is sufficient, you don’t need OnRayPrecastAction to do the heavy lifting.

solution:
if you need this operation in OnRayPrecastAction because your project specifically requires this functionality, it’s straightforward to implement.

In the OnRayPrecastAction call, you receive the rigid body hit by the ray and the compound shape.
You can inspect its collision shape. and if it one of interest by applying any filter you want.

them, if the check passed, Transform the ray into the compound’s local space.
Call Instance->RayCast() to determine which sub-shape the ray hits.

[Esharc]

Hi Julio.

Thanks for the explanation.

Essentially I would like to use the the contact information returned from the ray cast. As you say the contact member from ndRayCastNotify has the information that I should need.

The problem that I am having is that when ndShapeInstance::RayCast completes, it has the shape that was intersected with when casting into a compound shape, but later that shape is set to the parent shape of the compound shape.

So the contact information that I am receiving contains the parent compound shape, and not the sub shape that was intersected since the shape sets both shapeInstance0 and shapeInstance1 to the parent shape.

I realize that there may be multiple sub shapes that the ray intersects with, but I was thinking that if shapeInstance1 was set to the sub shape that was intersected with and shapeInstance0 to the parent shape then I can check for the sub shape that way?

I have implemented your suggestion and it is working well so far. But as you indicated, this approach is quite slow and I do notice a performance drop.

[Julio Jerez]

Hi Julio.
The problem that I am having is that when ndShapeInstance::RayCast completes, it has the shape that was intersected with when casting into a compound shape, but later that shape is set to the parent shape of the compound shape.

you are 100% correct, the function is overriding the sub shape with the parent shape,
that seem like a legacy from 3.xx

The intension is that the instance reported the sub shape hit, and the bodies has the parent shape.
I think I did verify that, by maybe later I changed, but it is no right.

let me verify it does not have side effects after I fix it.
I suspect that it is because the low level ray cast does not set the out shape because it will keep overriding on subsequent calls.
I have to debug it and see what the reason, but that does no seem right.

[Julio Jerez]

Oh, I verified that my suspicion is correct.
I can’t say exactly how it happened, but there’s a strong indication the issue comes from optimizing legacy C++.

That part of the code is nearly 30 years old. I’ve reused it many times across different projects for various employers back when I was doing that kind of work.

Basically, it’s a result of how C++ used to be. Back then, the language wasn’t as smart or efficient as it is today. We avoided returning objects, minimized object initialization in constructors, and used manual approaches instead.
So, in this case, instead of having the function return a contact object, it takes a pointer and initializes part of it internally. we were all doing C in Cpp.

There’s really no reason to do it that way anymore. Modern compilers are incredibly smart and can optimize parameter passing, especially with inlining and runtime optimizations. And even without that, CPUs today are hundreds of times faster than they were when I wrote that part of the library.

you can see that paternt here

Code: Select all

ndFloat32 ndShapeCompound::RayCast
...
            ndContactPoint tmpContactOut;

            ndShapeInstance* const shape = me->GetShape();
            const ndVector p0 (shape->GetLocalMatrix().UntransformVector (localP0) & ndVector::m_triplexMask);
            const ndVector p1 (shape->GetLocalMatrix().UntransformVector (localP1) & ndVector::m_triplexMask);
            ndFloat32 param = shape->RayCast(callback, p0, p1, body, tmpContactOut);
            if (param < maxT)
            {
...


Ray cast is called with an empty contact point and initialize only part of it.
then if it a hit is found, it initializes the rest.
All of that for saving the function not returning a full contact and that's just bad C++ today.
These functions should return an object instead of writing to the passed in pointer,
If that was the only place contact was used it is easy to fix, but it is not.
So I have to fix it case by case for now.

Newton originally started as a collision engine first, and only later became a full rigid-body simulator after David Baraff’s papers inspired that direction.

Anyway, I’ll do a major overhaul later on, but that will take some time.
For now, I’ll just fix it so it works as intended.

[Julio Jerez]

The solution isn’t pretty — it basically repeats more of the same logic.

here is the fix method:

The Body Raycast assumes the instance shape is the hit shape (bad programming).
Then it performs a ray cast, but the ray cast doesn’t actually set the hit shape.
If the body shape is a single primitive, it just sets the rest of the parameters (also bad).
If the shape is a compound, the compound raycast overrides the hit shape (really bad).

So on exit, if the ray hit anything else, it will report either a single primitive shape or a sub-shape of a compound.
I didn’t see any side effects in my tests, but I wouldn’t be surprised if you find some.

If you do, we’ll scrap this approach and modify the RayCast prototype to return a full contact point instead.
That’s not a small change, since the collision system shares the same functions for both ray casts and convex casts and contact joints.

In the meantime, I’ve applied similar fixes to convex casts, since they had the same issue.

Here’s a thought
have you considered using convex casts instead of ray casts?
You can use a convex cast with a small sphere as a replacement for a ray cast.
The advantage is that it gives you a filtering effect.

For example, imagine ray casting across a grid with small crevices. A ray cast can pass through the gaps and hit something unexpected.
It might sound like a contrived example, but think about a large landscape far from the origin:
if a ray passes exactly between two adjacent faces, floating-point precision might fail.
The ray cast routine is robust, but not immune to rounding errors.
Once in maybe ten million casts, you could get a wrong hit that breaks your game.

There’s also the issue of meshes where faces don’t meet perfectly, even after vertex welding.
A convex cast helps prevent this by giving you adjustable “thickness” via the sphere radius.
I ran into these kinds of bugs when testing fast-moving vehicles on terrain.

just an idea

[Julio Jerez]

ok, if you sync, ray cast and convex cast should report the sub-shape hit.
fixing convex cast took a little more work, but it is working.

I also revamped the find floor function in the demos,
these are just user implementations. you can do it anyway you want.

some demos are now using the convex cast functionality.

one example that always fail before, was placing the L shaped compound mesh,
in that example place one L shape on the floor always work with ray case.
the second failed because the ray pass thought a gap and report deep overlapping position.
with convex cast, the function sees the gap as a hit and report a fixable ground.

you can use those as sample how to go about using convex cast.
it is not all or nothing, it is the proper tool for the job.
I am just let it you know about that option.

if you sync, it should be working.
Thanks.