Very simple sphere to poly

[Chris]

Hi,

I am using raytracing to find connectable pathnodes in order to build the edges, but I need to do a radius check to keep the paths away from obstacles. I basically want this check to happen instantaneously (like a ray trace), but after lots of fiddling around, I am just not sure how this relatively simple task can be done using Bepu. This is at the editor level, so I don't actually need physics for this task, just a collision check with the 'space'.

Sorry if I am missing something very obvious, I am only asking because my attempts have failed.

P.S. Ideally, I would like to use a cylinder, but I don't believe I need to set up a character for this task, right?

[Norbo]

It sounds like a convex cast would do the trick. It's basically a ray cast, except instead of a point being casted along a ray, it's a whole convex shape. To 'fatten' the ray, use a sphere shape.

All BroadPhaseEntry objects support a ConvexCast method. However, the Space class does not expose a ConvexCast method (typically, convex casts are performed against a specific group of objects rather than a whole simulation). It is still possible to do it against an entire simulation, though; just like the Space.RayCast internally collects all the BroadPhaseEntry objects that overlap the ray using the Space.BroadPhase.QueryAccelerator, a similar query can find all BroadPhaseEntry objects that overlap a bounding box containing the convex cast. Be careful about long convex casts; the bounding box could be large and inefficient.

To create the bounding box, use a convex shape's GetSweptLocalBoundingBox. (Since the cast will be operating in world space instead of in the local space of some other object as the method is usually used, AffineTransform.Identity can be used as the spaceTransform parameter.) Then, get all overlapping BroadPhaseEntry objects from the Space.BroadPhase.QueryAccelerator.GetEntries method. Finally, call ConvexCast on each of the BroadPhaseEntry objects that you want to consider an obstacle.

Another option would be to shotgun-blast a bunch of regular ray casts to approximate the shape. A sufficient number of rays will likely end up being slower than a convex cast.

P.S. Ideally, I would like to use a cylinder, but I don't believe I need to set up a character for this task, right?

If I understand the goal correctly, a character is indeed unnecessary. While a SphereShape would probably be easier to use for a convex cast than a CylinderShape, cylinders can be made and used without characters. Using a long cylinder or capsule could do something similar to a convex cast, except it could generate contact data rather than hit data. If you want to go this route, check out the CharacterController's QueryManager for an example of querying the space with an object to find contacts.

[Chris]

Thanks.

When you mentioned the ConvexShapes I found another thread on this forum which also helped. I have it working with a Convex Sphere. Do you think it may be worth doing a simple ray trace with 'space' to exit early before doing the convex test?

[Norbo]

If the usage of the ray is such that a ray test would usually hit something when a convex cast would, then it might gain a tiny bit of speed. If it ends up falling back to a convex cast frequently, any gains would probably be lost since a ray cast is not that much cheaper than a convex cast (for reasonable convex cast lengths, anyway; huge bounding boxes around long sweeps can cause issues). If the convex cast is functionally necessary anyway, just doing it up front would be simpler. If it turns out to be a performance problem, then extra optimizations might be worth investigating.

[Chris]

OK, i'll ignore the original ray trace as recommended.

This is the implementation, which works quite well (might be helpful to others too).

Code: Select all

public bool ValidateEdgePath(Space space, PathNode nodeA, PathNode nodeB)
        {
            SphereShape convexSphere = new SphereShape(NodeRadius); 
            RigidTransform rigidTransform = new RigidTransform(nodeA.Position, Quaternion.Identity);
            BoundingBox box;
            AffineTransform affine = AffineTransform.Identity;
            List<BroadPhaseEntry> entries = new List<BroadPhaseEntry>();
            Vector3 sweep = nodeB.Position - nodeA.Position;
            ulong nearestID = ulong.MaxValue;
            float nearestDistance = float.MaxValue;

            sweep.Normalize();
            sweep *= Vector3.Distance(nodeA.Position, nodeB.Position);  
            convexSphere.GetSweptLocalBoundingBox(ref rigidTransform, ref affine, ref sweep, out box);
           
            space.BroadPhase.QueryAccelerator.GetEntries(box, entries);

            foreach (BroadPhaseEntry entry in entries)
            {
                if (entry.Tag is ulong)
                {
                    ulong id = (ulong)entry.Tag;

                    if (id != nodeA.ID)
                    {
                        RayHit rayHit;
                        if (entry.ConvexCast(convexSphere, ref rigidTransform, ref sweep, out rayHit))
                        {
                            if (rayHit.T < nearestDistance)
                            {
                                nearestDistance = rayHit.T;
                                nearestID = id;
                            }                            
                        }
                    }
                }
            }

            if (nearestID == nodeB.ID)
            {
                return true;
            }

            return false;
        }

I am setting 'sweep' to as direction and length for both the BB and the test. Sometimes it doesn't connect 2 nodes even though they are unobstructed, but they were a little further apart than the others. You mentioned that large (interpreted as long) BBs could cause problems, and am happy to restrict the distances to cope with this. However, I might have to set up a hierarchical network, where the lesser coursed graphs will have nodes with some distance between them. I could probably create a hybrid system for them, but was wondering if my implementation was incorrect before advancing.

P.S. thanks for your time and for the use of Bepu, which has made XNA so much more fun to work with.

[Norbo]

You mentioned that large (interpreted as long) BBs could cause problems, and am happy to restrict the distances to cope with this.

The primary problem I was referring to was performance due to extra entries to test. A poorly fitting axis aligned bounding box, such as one built around a long diagonal cast, will detect a lot of entries which are distant and obviously not going to hit. But, it is indeed true that the convex cast can also have numerical difficulties with extremely long sweeps or other hard situations. I wouldn't expect to see these very frequently, though. If it does happen, it usually manifests as a bad hit location, but the time of impact is generally still valid (at least as far as I've seen).

If there's a situation which reproducibly fails, making it into a demo for me to debug would be very helpful.

I could probably create a hybrid system for them, but was wondering if my implementation was incorrect before advancing.

It looks functionally correct. The sweep normalization-multiply sequence results in the original value of B - A, though, and the ulong stored in the Tag will cause boxing. Those won't break anything, but if performance is important, it might be worth changing.

P.S. thanks for your time and for the use of Bepu, which has made XNA so much more fun to work with.

Glad to hear it

[Chris]

I removed the normalisation of the sweep value. It was setup like that before when I was altering the distance to exclude the node radius, which isn't needed now. The boxing of the ulong is only on the editor, so at this stage performance isn't the issue. However, I will keep this in mind when exporting/importing the graphs.

The two that didn't connect may of been down to my placement method, in which I try and place a cylinder (represents the node's space) into the map, which checks the poly normal (walkable) and that the node is unobstucted. I have a tiny value to raise the cylinder slightly off the ground, so it doesn't register an initial collision. I applied this tiny offset to the radius of the cylinder and it seems to connect eveything, because the cylinder will always be slightly more fatter than the convex sphere (the sphere is the real radius of character). Since doing this I can't replicate the problem.

All is well, and thanks for the tips.