I'm insane, please help me add to your engine

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

I'm insane, please help me add to your engine

Post by mcmonkey »

Sorry for the ridiculous titles.

SO.

I've been working on making a custom physics static collidable in BEPU that will allow me to properly and cleanly trace objects into my creation's voxel grid.

... I'm not doing so well.

Rather than dump my code upon you, I've modified the BEPU physics official 'character playground' demo to contain a really simplistic sample of my progress so far.
It's... very low quality, I admit, but... I'm trying and I'm sure with a bit of help I can get it working!

In place of a Voxel grid, I've placed a gigantic cube from Y=0 and down, extending well beyond the limits of the playground.
It should from here be reasonably easy for someone experienced with BEPU to patch this code so it works. By learning from the patches, I should be able to re-apply this knowledge to my actual code and then have a magically working static object.

So, here's my code, in the form of the entire CharacterPlaygroundDemo file with random other stuff dumped at the top. All edits are marked with prefix 'MCMONKEY'.
http://pastebin.com/8PJ02mdX

So what happens when this is run?

The character is stuck in place, beyond jumping, and can be felt to slowly 'sink' downward before hitting solid ground. This sinking is not representative of my original issue as far as I'm aware, but it's possible. The non-movement is representative.
Additionally, all non-static objects are seen to bounce/slide/spin/etc. around arbitrarily when in contact with the new surface. This is relatively representative of the original issue.

So, how might I go about patching this code up to work?

... Sorry again for my failings to accomplish simple tasks.




OH AND there a few "// note"s in that code that might be of interest/relevance.


EDIT: Helps if I keep my variables in order (Updated pastebin link)
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: I'm insane, please help me add to your engine

Post by Norbo »

The main issue is that no real collision detection takes place. A sweep test is performed and creates a contact, but the contact's data isn't actually representative of the collision. There might be some other minor bookkeeping issues too, but this is the biggest problem.

I would recommend creating a subtype of the GroupPairHandler and creating sub-pairs for the various collisions. Check out the CompoundConvexPairHandler and its parent CompoundGroupPairHandler for an example implementation of a GroupPairHandler.
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: I'm insane, please help me add to your engine

Post by mcmonkey »

Norbo wrote:The main issue is that no real collision detection takes place. A sweep test is performed and creates a contact, but the contact's data isn't actually representative of the collision. There might be some other minor bookkeeping issues too, but this is the biggest problem.
What is it missing then? I created the contact with the information available. What more needs adding to represent the collision more accurately?
I would recommend creating a subtype of the GroupPairHandler and creating sub-pairs for the various collisions. Check out the CompoundConvexPairHandler and its parent CompoundGroupPairHandler for an example implementation of a GroupPairHandler.
There's not /actually/ sub-objects in the real implementation, the sample with a Box at the core is just for simplicities sake. GroupPairHandler is rather unfit for non-group objects. (I played with it a bit and all the code assumes from the core that there are sub-objects involved, and it will definitely not play nice for a singular primary pair.)
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: I'm insane, please help me add to your engine

Post by Norbo »

What is it missing then? I created the contact with the information available. What more needs adding to represent the collision more accurately?
At a glance the penetration depths were negative, sweep tests can't generally be relied on for handling intersecting cases in a meaningful way for contact generation, and there may have been some normal calibration issues. I didn't look too deeply.

Creating 'good' contact manifolds is a much harder problem. Even if the above problems were fixed, everything would still jitter around a bunch, except for maybe things with locked orientation like the character.
There's not /actually/ sub-objects in the real implementation, the sample with a Box at the core is just for simplicities sake. GroupPairHandler is rather unfit for non-group objects. (I played with it a bit and all the code assumes from the core that there are sub-objects involved, and it will definitely not play nice for a singular primary pair.)
If you don't plan on having individually accessible collidable data and events, then it would end up looking more like the StaticMeshConvexPairHandler. The main difference is that its StaticMeshContactManifold and its parent TriangleMeshConvexContactManifold are responsible for generating the sub-pairs, rather than the StaticMeshConvexPairHandler. The sub-pairs it manages, TrianglePairTesters, are not full CollidablePairHandlers, but rather low level persistent collision detection data caches. (Be warned, the TriangleMeshConvexContactManifold is complicated, but the vast majority of it is related to boundary smoothing. The parts related to subpair management are pretty simple.)

That said, the existence of CollidablePairHandler subpairs in the GroupPairHandler does not imply there are multiple entities involved, just that there are collidables with uniquely accessible information for the purposes of events and such. Say there's a big voxel-based spaceship built using a CompoundCollidable- a user might want to hook events to certain voxels for gameplay purposes or something. Triangle meshes just treat the triangles and dumb data, so there's no similar features. (Not that it would be impossible, just less natural and the API would look different.)
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: I'm insane, please help me add to your engine

Post by mcmonkey »

I've updated the Update() code to the follow:

Code: Select all


        public override void Update(float dt)
        {
            RigidTransform rt = convex.Entity == null ? convex.WorldTransform : new RigidTransform(convex.Entity.Position, convex.Entity.Orientation);
            if (IsNaNOrInf(ref rt.Position))
            {
                for (int i = contacts.Count - 1; i >= 0; i--)
                {
                    Remove(i);
                }
                return;
            }
            Vector3 sw = new Vector3(0, 0, 1f); // Note: ???
            if (convex.Entity != null)
            {
                sw = convex.Entity.LinearVelocity;
            }
            sw *= dt; // TODO: neeeded?
            RayHit rh;
            bool hit = vwo.ConvexCast(convex.Shape, ref rt, ref sw, out rh);
            if (!hit || IsNaNOrInfOrZero(ref rh.Normal))
            {
                for (int i = contacts.Count - 1; i >= 0; i--)
                {
                    Remove(i);
                }
                return;
            }
            Plane plane = new Plane(new Vector3(0, 1, 0), 0);
            Ray ray = new Ray(rt.Position, sw);
            float t;
            Vector3 pos = rh.Location;
            if (ray.Intersects(plane, out t))
            {
                ray.GetPointOnRay(t, out pos);
            }
            float pendef = Math.Abs(sw.Length() - t);
            Vector3 norm;
            RigidTransform rtx = new RigidTransform(Vector3.Zero, rt.Orientation);
            RigidTransform.Transform(ref plane.Normal, ref rtx, out norm);
           // norm = plane.Normal;
            norm = -norm; // TODO: Why must we negate here?
            norm.Normalize();
            if (convex.Entity is Cylinder)
            {
                Console.WriteLine(pendef + "=pendef, normal=" + norm);
            }
            for (int i = contacts.Count - 1; i >= 0; i--)
            {
                contacts[i].Normal = norm;
                contacts[i].Position = pos;
                contacts[i].PenetrationDepth = pendef;
            }
            if (Contacts.Count == 0)
            {
                ContactData cd = new ContactData();
                cd.Normal = norm;
                cd.Position = pos;
                cd.PenetrationDepth = pendef;
                cd.Id = contacts.Count;
                Add(ref cd);
            }
        }
ALongside some other changes and... it almost begins to work. It keeps things separated as exepcted... however, it pushes too strongly now. It forces the character to bounce into the air, and still bounces non-character entities around.
At a glance the penetration depths were negative
Fixed.
sweep tests can't generally be relied on for handling intersecting cases in a meaningful way for contact generation
You're right here, for multiple reasons. They key one to me is that it doesn't give a contact point... so I added extraneous code to calculate that. It also doesn't properly react to full-on containment (as opposed to partial intersection) but that's allowed to bug, as that should never happen (and if it does, consider behavior undefined, though it's nice to handle it as gently as possible).
and there may have been some normal calibration issues. I didn't look too deeply.
Normals in the above code should be accurate in this test case.


I'm sorry for largely ignoring your main suggestions, as they are very complicated and I'm sure this code can be made to work with a bit of effort and knowledge. And if not, I'm going to need way more detailed help than "Go look at <really complex code> for overcomplicated examples hidden amongst complicated unrelated code" >.>

Worst case scenario if we can't get this figured out... my budget is small currently, but perhaps I could pay you a fair amount to take like half an hour or so to specifically work on my case, and get everything working? I wouldn't expect anything perfect or fancy, just enough to get a solid low-resource-consumption (relatively) method of working together BEPUphysics and static Voxel grids... (Ideally one I can keep powered by convex traces at its core, as that's the least complicated route at the moment, due to some special circumstances), and accurate handling of collision between convex objects and the Voxel grid. Throwing in non-convex objects is a secondary goal that can be dealt with later if it's not feasible to work that in at the same time.

Either way, once I've got everything working I very much intend to send some portion of proceeds from the project your way, as a thank-you for both the very helpful support and the physics engine itself.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: I'm insane, please help me add to your engine

Post by Norbo »

Worst case scenario if we can't get this figured out... my budget is small currently, but perhaps I could pay you a fair amount to take like half an hour or so to specifically work on my case, and get everything working? I wouldn't expect anything perfect or fancy, just enough to get a solid low-resource-consumption (relatively) method of working together BEPUphysics and static Voxel grids... , and accurate handling of collision between convex objects and the Voxel grid. Throwing in non-convex objects is a secondary goal that can be dealt with later if it's not feasible to work that in at the same time.
Unfortunately, this would not be a 30 minute job. Even a fairly simple convex case would take quite a few hours, long enough to make the price outside of most indie-indie budgets.

Fortunately, I went ahead and did it anyway.

Unfortunately, I just blew weeks worth of my free-helpy-time budget. :P

The new SimpleVoxelCollidableDemo only works for convexes, doesn't use any high performance special case logic (e.g. for boxes and spheres), uses a highly inefficient brute force memory structure, makes no attempt at boundary smoothing, leaves queries as stubs, and may still have some bugs in it. But it works reasonably well otherwise. The debug renderer is not set up to handle this, so visualizations are pretty limited- going above 16x16x16 tanks render performance, but the physics run totally fine.

Adding compound body support would be pretty easy. It would be a relatively straightforward CompoundGroupPairHandler implementation- see CompoundInstancedMeshPairHandler for an example. Just replace InstancedMesh with VoxelGrid and register the handler with the narrow phase helper.
(Ideally one I can keep powered by convex traces at its core, as that's the least complicated route at the moment, due to some special circumstances)
Getting stable contact manifold generation using nothing but convex casts would be a large research project at best, and slow and unstable at worst. I'd strongly recommend going with the standard built in contact generation.
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: I'm insane, please help me add to your engine

Post by mcmonkey »

You are absolutely amazing! Thank you so much! Like I can't even express how thankful I am. After we get this fully working, I am fully willing to repay you however I can. (I'm skilled with using OpenGL through OpenTK and could help rewrite the demos to that or something since I believe you said you wanted to rewrite the demos to non-XNA, for example)

This works perfectly for all non-continuous cases.

... It doesn't for continuous, and I'm struggling to fix that. I need continuous support for CharacterController to work.

I've made a variety of attempts in the area of adding an UpdateTimeOfImpact.

here's the very low quality 'convex cast' method:

Code: Select all

            if (convex.Entity != null && convex.Entity.ActivityInformation.IsActive && convex.Entity.PositionUpdateMode == PositionUpdateMode.Continuous)
            {
                timeOfImpact = 1;
                RigidTransform rt = new RigidTransform(convex.Entity.Position, convex.Entity.Orientation);
                Vector3 sweep = convex.Entity.LinearVelocity;
                sweep *= dt;
                float len = sweep.Length();
                RayHit rh;
                if (mesh.ConvexCast(convex.Shape, ref rt, ref sweep, out rh))
                {
                    timeOfImpact = rh.T / len; // Also tried without " / len"
                }
                if (TimeOfImpact < 0)
                {
                    timeOfImpact = 0;
                }
            }
This will stuck objects in their tracks... and also the character can't move. (Also it sinks down clientside, though not serverside which is what matters for now)

This code is based off InstancedMesh code using the existing contact list as well.

Code: Select all

            if (convex != null && convex.Entity != null && convex.Entity.ActivityInformation != null && convex.Entity.ActivityInformation.IsActive && convex.Entity.PositionUpdateMode == PositionUpdateMode.Continuous)
            {
                Vector3 velocity;
                Vector3 lvel = convex.Entity.LinearVelocity;
                Vector3.Multiply(ref lvel, dt, out velocity);
                float velocitySquared = velocity.LengthSquared();
                float minimumRadius = convex.Shape.MinimumRadius * MotionSettings.CoreShapeScaling;
                timeOfImpact = 1;
                if (minimumRadius * minimumRadius < velocitySquared)
                {
                    BoxShape bs = new BoxShape(1, 1, 1);
                    for (int i = 0; i < contactManifold.ctcts.Count; i++) // ctcts = direct access to 'contacts' as a rawlist
                    {
                        Contact ct = contactManifold.ctcts.Elements[i];
                        Vector3 pos = convex.Entity.Position - (ct.Position + new Vector3(0.5f, 0.5f, 0.5f));
                        RayHit rayHit;
                        if (GJKToolbox.CCDSphereCast(new Ray(pos, velocity), minimumRadius, bs, ref Toolbox.RigidIdentity, timeOfImpact, out rayHit) && rayHit.T > Toolbox.BigEpsilon)
                        {
                            timeOfImpact = rayHit.T;
                        }
                    }
                }
            }
it never registers any impacts, ever. Continuous things simply fall through (IE, the character).
(Other non-ccd objects get stopped in their tracks by non-continuous checks which seem to also run, luckily)

(Pretend here is the mid-point between the above code and the below, which I didn't save a copy of but had the same results of the two give-or-take)

This next code block is after a variety of playing around... and features multiple changes from the previous code set, including: manual overlap list grabbing from an attempt to get the max bounds of the movement, tracing the full shape rather than part of it, ...

Code: Select all

            if (convex != null && convex.Entity != null && convex.Entity.ActivityInformation != null && convex.Entity.ActivityInformation.IsActive && convex.Entity.PositionUpdateMode == PositionUpdateMode.Continuous)
            {
                Vector3 velocity;
                Vector3 lvel = convex.Entity.LinearVelocity;
                Vector3.Multiply(ref lvel, dt, out velocity);
                float velocitySquared = velocity.LengthSquared();
                Vector3 veldir = velocity;
                veldir.Normalize(); // TODO: Neccessary?
                //float minimumRadius = convex.Shape.MinimumRadius * MotionSettings.CoreShapeScaling;
                timeOfImpact = 1;
                //if (minimumRadius * minimumRadius < velocitySquared)
                {
                    BoxShape bs = new BoxShape(1, 1, 1);
                    contactManifold.Update(dt); // just in case
                    convex.UpdateBoundingBox();
                    BoundingBox bb = convex.BoundingBox;
                    if (velocity.X < 0) { bb.Min.X += velocity.X; } else { bb.Max.X += velocity.X; }
                    if (velocity.Y < 0) { bb.Min.Y += velocity.Y; } else { bb.Max.Y += velocity.Y; }
                    if (velocity.Z < 0) { bb.Min.Z += velocity.Z; } else { bb.Max.Z += velocity.Z; }
                    var overlaps = new QuickList<Vector3i>(BufferPools<Vector3i>.Thread);
                    mesh.ChunkShape.GetOverlaps(mesh.Position, bb, ref overlaps);
                    SysConsole.Output(OutputType.INFO, "got " + overlaps.Count + " for " + convex.Shape);
                    for (int i = 0; i < overlaps.Count; i++)
                    {
                        Vector3i posi = overlaps[i];
                        Vector3 pos = convex.Entity.Position - (mesh.Position + posi.ToVector3() + new Vector3(0.5f, 0.5f, 0.5f));
                        RayHit rayHit;
                        if (GJKToolbox.CCDSphereCast(new Ray(pos, veldir), convex.Shape.MaximumRadius, bs, ref Toolbox.RigidIdentity, timeOfImpact, out rayHit) && rayHit.T > Toolbox.BigEpsilon)
                        //if (GJKToolbox.CCDSphereCast(new Ray(pos, velocity), minimumRadius, bs, ref Toolbox.RigidIdentity, timeOfImpact, out rayHit) && rayHit.T > Toolbox.BigEpsilon)
                        {
                            timeOfImpact = rayHit.T;
                            SysConsole.Output(OutputType.INFO, "TOI now: " + timeOfImpact + " for " + convex.Shape);
                        }
                        else
                        {
                            SysConsole.Output(OutputType.INFO, "Failed a cast for " + convex.Shape);
                        }
                    }
                    overlaps.Dispose();
                }
            }
This code results in: the character falls through the ground, sometimes getting caught against the inside of a voxel grid if you're lucky. Also tons of outputs saying that the cast failed, with occasional "TOI now:" outputs when caught.



I of course can't possibly ask you to do this all yourself as well, but if you can, I could benefit from some guidance: Which attempt of the 3 is the closest to the correct direction, and from there, what should I look into to improve the attempts?

EDIT: In the demos, the character seems to move just fine with half-accurate discrete checking (After remove the NotImplementedException). I don't know what the demos do different, but... yeah that's happening. I can't even test my code in the demos because it's colliding perfectly fine via discrete collision. And by just fine I mean rather weirdly but it's staying roughly where it belongs is the point. I don't know why, but in my setup, the character seems to be not counting discrete collision at all. Other objects, I note, still collide just fine... just not the character. So I'd also like to know if there's any way to fix the character's discrete tracing, assuming that's something I set differently from the demos.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: I'm insane, please help me add to your engine

Post by Norbo »

I'm not sure what behavior you're experiencing with the character, so I'm not sure how to address it. If you can replicate the behavior in the demos, I could take a look.

Continuous collision detection should be completely irrelevant for speeds that characters usually move at. With the character size and default CCD configuration at 60hz, it shouldn't have any effect at all unless the character's speed is above ~13. In fact, it won't even activate at low relative speeds. Even without CCD, full tunneling shouldn't happen until the character has a speed of at least ~42, and that's assuming the obstacle is infinitely thin and the collision is along the character's thinnest axis.

That said, I found and fixed a bug with subcollidable positioning that was messing with discrete collision, and while I was at it I added in a proper time of impact calculation. The remaining behavior issues in the demos are caused by a lack of boundary smoothing and the lack of voxel grid raycasting support that the character would otherwise use to stick on the ground after hitting a bump, but I can't address those right now.
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: I'm insane, please help me add to your engine

Post by mcmonkey »

Aha! I figured out my issue with the character interacting wrong...

I, er, replaced a ">=" with a ">" on a line. Funny how the tiniest changes create the biggest, most confusing errors.

Now it works near perfectly :D

As far as mathematical accuracy et al, it's just about perfect. I've got my own ray/convex cast code... it's pretty far from perfect but it works for my needs.

I once again cannot thank you enough for doing all that you have to help me. I am infinitely glad I chose BEPU over alternative physics engines.

(Also, I only now realized what TimeOfImpact actually does (as in, how it functions and why it functions that way). Thanks to your sample code + passing explanation, I have that much figured out now).
(I thought it was a more major part of general collision, but really it's just a backup to ensure no penetration happens when CCD is on)


EDIT: I fixed the thing that originally occupied this space, so... yup! AMAZINGNESS IT ALL WORKS!

(I had induced lag for little apparent reason - turns out my old code to respawn the mesh was still at play, and it was duplicating the voxel grid object every time I block was edited, which is bad)


And remember, need any help with OpenTK/OpenGL modern, I'm available!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: I'm insane, please help me add to your engine

Post by Norbo »

And remember, need any help with OpenTK/OpenGL modern, I'm available!
Thanks for the offer :)
Post Reply