[Aardwolf]

Eh? The PID-based thing already had limits on how much torque it could apply.

And it sucked balls. It kinda worked when all I had was a single limb, not in contact with the ground, with an immobile shoulder. But not at all when I put six of them together in a bug. Instead it's flopping and flailing around and generally failing, when all I asked it to do was to go to and maintain a constant pose.

[z64555]

Ok, so you'll need to tune each leg to be able to hold at least half of the body weight of the 6-legged bug (since it needs a minumum of 3 points of contact to stay standing).

The flopping around bit is most likely from an improper damping ratio (probably too little) resulting in an under damped system of equations. I dunno, you may have to get math program like MatLab, SciLab, or OpenModelica to plot the response curve of your PID system instead of trying to eyeball it in-game.

[Aardwolf]

Hm...

If I do something like the single-limb RobotArm prototype, but instead of a completely immobile shoulder joint I attach it to something that can move but can't rotate, and which has about the mass of the full bug (or half of it?)... maybe that will help.

Another thing that I'm concerned about with this PID thing... maybe some of my issues are arising from the fact that this is a discrete simulation instead of sensors monitoring a continuous real-life phenomenon (even if the sensors were sampling it discretely)... e.g. it may be possible to overshoot the mark in a single tick.

Not sure what you mean by "damping ratio".

[z64555]

Another thing that I'm concerned about with this PID thing... maybe some of my issues are arising from the fact that this is a discrete simulation instead of sensors monitoring a continuous real-life phenomenon (even if the sensors were sampling it discretely)... e.g. it may be possible to overshoot the mark in a single tick.

...Which is why I suggested that you try simulating in a math program suite before trying as a discrete time system (DTS). A DTS can, and will, become very unstable if the input signal operates at a frequency greater than what it is sampled at. In realistic terms, this means you can't have the bug accelerating too fast between iterations. The damping ratio is a complex formula that describes how fast the system decays from an initial impulse... just like a shock absorber on a car.

Simulating a single arm is a start, but try a simulation with three legs for a stationary test and four legs for a movement test before going to 6 or more.
[/quote]

[Aardwolf]

Simulating a single arm is a start, but try a simulation with three legs for a stationary test and four legs for a movement test before going to 6 or more.

D'oh... why did I even try to get a single leg to stand... way to not do your job, brain.

...Which is why I suggested that you try simulating in a math program suite before trying as a discrete time system (DTS). A DTS can, and will, become very unstable if the input signal operates at a frequency greater than what it is sampled at. In realistic terms, this means you can't have the bug accelerating too fast between iterations.

RE: "simulating in a math program suite": You mean using an existing simulator? Or just for the analysis? I am somewhat disinclined to use an existing simulator, because its behavior would invariably be different from that of my physics engine, and ultimately it's my physics engine that I need it to work correctly in. Which isn't to say that my physics engine is physically inaccurate (although it may be), just that the specific of how my constraints behave, how the friction works, etc., would likely not be easily and accurately reproducible in another simulator.

RE: "if the input signal operates at a frequency greater than what it is sampled at": About a month ago I changed how constraint motors are controlled so that it runs a callback immediately before every physics tick... so it should have up-to-date info about the state of the physics world, and the values I set for the motor torques will potentially be changed again as soon as the next tick. And the ticks have a fixed timestep.



Anyway, will try with a tripod soon.

[z64555]

...Which is why I suggested that you try simulating in a math program suite before trying as a discrete time system (DTS). A DTS can, and will, become very unstable if the input signal operates at a frequency greater than what it is sampled at. In realistic terms, this means you can't have the bug accelerating too fast between iterations.

RE: "simulating in a math program suite": You mean using an existing simulator? Or just for the analysis? I am somewhat disinclined to use an existing simulator, because its behavior would invariably be different from that of my physics engine, and ultimately it's my physics engine that I need it to work correctly in. Which isn't to say that my physics engine is physically inaccurate (although it may be), just that the specific of how my constraints behave, how the friction works, etc., would likely not be easily and accurately reproducible in another simulator.

Well, the other simulator would be a "guaranteed simulation of physical stuff," which means that if there's anything in your simulations that is just plain wrong, the game and the simulator will get 2 drastically different responses. The math program suite should allow you to simulate the physical model that you want and it'll plot you a nice curve of the response that you want out of your game. I'm going to try grabbing a copy of SciLab sometime this week to see if I can get some block diagram simulations going on it.

RE: "if the input signal operates at a frequency greater than what it is sampled at": About a month ago I changed how constraint motors are controlled so that it runs a callback immediately before every physics tick... so it should have up-to-date info about the state of the physics world, and the values I set for the motor torques will potentially be changed again as soon as the next tick. And the ticks have a fixed timestep.

In that case, the control system is operating at the same frequency as the system it is controlling. I think this should be ok, but I don't have enough experience with Z-domain modeling and simulation to give you a definitive thumbs up or down... I'll have to mess around with SciLab to see if I can get a better feeling of it.

[Aardwolf]

Made a tripod which uses the PID stuff. It's nowhere near as "rigid" as I want.



Also... physics trouble again

I notice that when the legs of the tripod are touching the ground, the point of contact doesn't stay put... as if it's standing on a slippery surface. I'm not sure if that's because the forces are exceeding the force of friction, or if it's skipping out of contact with the ground every other frame, or what, but it's bad. And I think it's not entirely the PID system's fault, because there are similar problems with the player... e.g. when I try to stand still, my feet jitter and I very slowly inch forward or backward (depending on whether I'm looking up or down). And in the case of the player, it's definitely a case of not being in continuous contact with the ground.

Part of the problem is that when objects collide, they have a 'bounciness' which is a little more than enough to nullify their inward velocity. But gravity acts as a downward impulse applied every tick. Together this means that objects will never settle!

Maybe I need to make it so objects only bounce if the inward velocity is greater than the per-tick inward component of the delta-v from forces acting on the objects. I'll probably try that when I get up tomorrow.


Edit: Did that, but now it seems there's another issue... there's a system that undoes interpenetration between objects by directly modifying their positions, instead of changing their velocities... and if an object has two contact points with similar normal vectors, the displacement gets added and causes the object to move further than it really ought to. Shouldn't be too hard to fix though!

[Tomo]

Both the issues raised generate energy from nowhere, which is obviously unrealistic.

You need damped collisions, that should solve both issues. Look up "inelastic collisions" on Wikipedia.

Perhaps treat interpenetration as the surface deforming under the "impact" and partially restore the surface elastically - like walking on a mattress.
- This will mean that all characters will always sink slightly below the surface, with the distance depending on their weight. The displayed models can take that into account.

Thinking about it, it also looks "right" if something with spiky legs jabs them slightly into the ground, rather than the ground being infinitely hard.

[Aardwolf]

I already have inelastic and partially inelastic collisions, and have had them virtually from the beginning. That's what the "bounciness" variable is for. 0 = totally inelastic collisions. 1 = totally elastic collisions. There is no "energy from nowhere" involved in that aspect of the simulation.

I've removed the anti-penetration thing because it was indeed "energy from nowhere", and was causing problems.



Then I determined that my friction is borked: although I wanted it to only affect the tangential components of the relative local velocity between two objects at the contact point, it is affecting the normal component as well. Not quite sure how to fix.

But I realized something I hadn't realized before! I can represent a cross product as a multiplication by a 3x3 matrix! E.g. if I have a cross product a x b, I can represent that as multiplying vector a by [[0, b.z, -b.y], [-b.z, 0, b.x], [b.y, -b.x, 0]]. And so I determined that I can express the change in the relative local velocity at the contact point as a multiplication of the applied impulse by a 3x3 matrix

But when I tried to implement it it didn't work right

[Tomo]

Ah, so so by "bounciness" you meant coefficient of restitution? That's correct then, sorry.

Not sure what you meant on the friction issue.
Perhaps knocking up something that draws the vectors (velocity, normal, and tangential) onscreen during sim would help you figure out where it's going weird?

[z64555]

Ah, so so by "bounciness" you meant coefficient of restitution? That's correct then, sorry.

Spring coefficient, more likely.

I think that the vector indicators would be helpful, as well as maybe a control panel that will allow you to modify various coefficients in real-time (vs. going back, modifying a value, compiling, and simulating again).

[Aardwolf]

Ah, so so by "bounciness" you meant coefficient of restitution? That's correct then, sorry.

Not sure what you meant on the friction issue.
Perhaps knocking up something that draws the vectors (velocity, normal, and tangential) onscreen during sim would help you figure out where it's going weird?

Ah yes! Coefficient of restitution! I had heard the term before, but didn't realize it was the same as what I was doing.



RE: vectors:

One of the quantities I'm working with is the "relative local velocity" between two objects at the point of contact, i.e. the difference between the local velocities at that point... let's call this L for short. Computed as:

          L = v₂ - v₁ + r₂ x ω₂ - r₁ x ω₁

Where r is the vector from the respective object's CoM to the point of contact, and ω is the angular velocity of the object.



The way these quantities change when an impulse p is applied at the contact point are as follows:

          v₁ += p / m₁
          ω₁ += I₁^-1 (p x r₁)
          v₂ -= p / m₂
          ω₂ -= I₂^-1 (p x r₂)

Where I is the MoI of one of the objects.



Uh... where was I going with this?

Oh right! In theory, after I apply an impulse for "restitution", the component of L along the normal vector of the contact point should be non-negative, i.e. the objects should not still have a velocity that would cause them to go through each other. This much seems to be working.

The problem is that friction should only affect the components of L along the axes orthogonal to the normal vector (i.e. in the plane of the contact point)... but the way I've been computing the friction, I've just been using an impulse that's in the plane of the contact point, and that doesn't guarantee that the resulting ΔL will be in the plane as well.

I was thinking I could represent the conversion from p to the resulting ΔL as a 3x3 matrix multiplication, and then use the inverse matrix to compute an appropriate impulse... but as I said earlier, my implementation didn't work.



Edit:

I figured out why my implementation didn't work! It's because cross products lose information... i.e. if I have a function f(a) = a x b, it is not possible to reconstruct a given f(a). And so when I tried to invert a matrix which depended on the cross product matrices, it didn't turn out right.

So now I know why the thing I tried to do doesn't work, but I'm not really any closer to getting it working.



Edit II:

Turns out I just had the signs wrong in one of my equations (not one I posted though). I reversed the polarity and now it's working awesomely

[Aardwolf]

There are still two "big" problems with my physics that I think I'm going to have to address before I can get back to working on physics-based movement...



1. Stuff going through other stuff, and contact between objects not being stable

I've tried turning the number of iterations the constraints solver does up from 15 to 200... that seems to fix the problem, but it also makes the game unacceptably slow. Somehow I need to achieve the effect of 200 iterations, while only using the processing time of 15 iterations


The current setup is basically just a for loop iterating for MAX_CONSTRAINT_SOLVER_ITERATIONS around a for loop iterating through the list of constraints. It's "dumb" but has zero overhead.

In the past I tried a "smart" system where I broke the constraint graph into isolated subgraphs (caveat: constraint edges to immobile objects don't count for merging subgraphs), and then tracked which edges were "awake" due to an applied impulse at an adjacent edge during the previous iteration. That method had some initial setup overhead (I don't know how bad), and some overhead per constraint evaluated, but the benefit is that it let me skip evaluating some constraints which would end up doing nothing when I evaluated them. Also the results might be less consistent than the current setup, since constraints wouldn't always execute in the same order.

When I was trying to do stuff on the GPU I had another setup where I broke the constraint graph into batches with no adjacent edges. But that turned out slower than the pure-CPU implementation! I've tried a multi-threaded CPU implementation with this sort of batching as well, and it didn't seem to help much. This setup is also "dumb" in that it evaluates all the constraints, every iteration. I probably could've found edges which were completely isolated and made them only evaluate once, but beyond that I don't know if it would be possible to make this scheme do "smart" evaluation like what I mentioned in the isolated-subgraphs scheme.

What to do?



2. Contact regions that aren't just "points"

E.g. if I have a box resting on a slightly sloped surface, the entire bottom surface of the box will be in contact with the surface, and thus an "inward" velocity at any of the edges will be counteracted by the normal force / restitution / whatever we're calling it these days. A sphere, on the other hand, would only have a single point in contact with the surface, and thus would roll down the slope. But in my physics engine, if I only create a single contact point at the center of the box's bottom face, it will try to roll like a ball anyway... but unlike a ball, a box has a bigger radius at its corners than in the center of its faces, so it'll end up sinking into the slope as it tries to roll.

Currently I can have multiple contact points between a pair of objects, and it does what I want... but each one is an additional constraint for the constraint solver to process, and even with a lot of iterations of the constraint solver I need an "adhesion" threshold to keep the impulses at one corner from lifting another corner out of the ground. Also right now I don't have my collision detection set up to generate multiple contact points, except for collisions between multispheres and infinite planes, e.g. the ground plane I sometimes use to test physics with, which won't actually be used in the game anyway

I can probably modify my existing collision detection to produce multiple contact points for multisphere-multisphere and multisphere-triangle (of triangle mesh) collisions easily enough.

I'm thinking maybe I should change how ContactPoint works, so that instead of having a bunch of ContactPoint constraints between a pair of objects that has a non-pointlike region of contact, I would have a single constraint object that contains the shape data for the region (information which the current setup represents as a list of multiple ContactPoint constraints). What do you guys think?

[Tomo]

I'm pretty sure you have to abandon the idea of any surface being perfectly hard, and deliberately allow an initial interpenetration based on the dynamic load, settling on a final interpenetration based on the static forces after collision energy is dissipated.

- Think "dropping a box on a mattress".

If you calculated the area of the interpenetration and use that as a scaling factor for the restitution force in the collision, would that work?
- The interpenetrating volumes might be more accurate, but harder to work out as you'll have to find the area first.

[Aardwolf]

I'm pretty sure you have to abandon the idea of any surface being perfectly hard, and deliberately allow an initial interpenetration based on the dynamic load, settling on a final interpenetration based on the static forces after collision energy is dissipated.

- Think "dropping a box on a mattress".

I know there's going to be some initial interpenetration, just because I'm dealing with finite timesteps. But I'm pretty sure treating the objects as "springy" isn't the right way to go, if that's what you're suggesting.

If you calculated the area of the interpenetration and use that as a scaling factor for the restitution force in the collision, would that work?
- The interpenetrating volumes might be more accurate, but harder to work out as you'll have to find the area first.

The problem is not with the amount of restitution force, it's with the distribution of it. If I only measure relative local velocities at a single point, and apply impulses for restitution and friction at that same point, a box will behave identically to a sphere. To make a box behave like a box, it needs to have one such ContactPoint under each of its corners.




As far as the actual task of modifying my existing collision stuffs to create multiple contact points... I'm stuck. I started working on making the changes to multisphere-multisphere collisions... I made it find which of the spheres of each multisphere shape are past the "overlap distance" along the axis, and I made some switch statements to do different stuff according to how many such spheres there are from each object, but they don't do anything yet, and I don't know what to do as far as implementing them.




In other news, I've successfully re-implemented a "smart" constraint graph solver! But it broke my "adhesion threshold" fix for jittering Ah well, I'll probably come up with something.

[z64555]

Perhaps the bouncing is due to usage of a > instead of a >= comparison?

[Aardwolf]

Nope. The comparison is (normal dot relative local velocity) < 0, but I've tried doing <= 0, and < some positive threshold. Positive threshold (aka "adhesion threshold") was working... until I recently reimplemented the "smart" constraint graph solver, which broke it. I feel like I just said this. But looking at the most recent posts in this thread... maybe I only explained it in the WHIYL thread or something.

Maybe if I used a larger threshold I could make it work again... it feels kind of hackish though.

Edit: Confirmed, a larger threshold makes it work again. Still feels hackish though.




And I still need to figure out how to generate multiple contact points for my collisions (as appropriate). 

[Mika]

I'm bit late in this thread, but there might be something I can help with.

First I would like to know what you are aiming at in the grand scheme of things? You have plenty of building blocks here, but to use some of them, I feel like it is going to contradict something else in your building blocks. I read that you'd like to have destructible terrain, but are you planning destructible units as well?

I think your engine would require finite element analysis sort of approach depending on how deep you want to go with something pushing something, or something hitting something. Though I'm not sure, but it seems to be heading that way.

My own background is in scientific computing, mainly in numerical methods and ray-object intersection tests.

Heh, never thought that traditional approach would be to have a box floating on the terrain, there's so much "cheaty" stuff in gaming that it's hard to believe it given its immersiveness.

[Aardwolf]

O HAI!

As far as the destructible terrain system... I can already make holes in the terrain. I want to do island detection, but beyond that I don't have any plans.

Hm... destructible units... it would be cool to be able to blow a limb off a bug, but that would be yet another complication for physics-based movement. Idunno. I don't think I'm going to be doing anything like that scene in Starship Troopers where Rico carves a hole into the tanker bug's armor and tosses a grenade inside it



I don't see what I would need finite element method for? Except if I wanted realistic terrain deformation and fracturing... that's not going to happen any time soon, if ever.



Really I'm just stuck on getting the rigid body physics working cleanly 

[Mongoose]

I know this is probably a really stupid question, but are the methods you're implementing something that's fairly different than the standard approach, or are they something where there might be some resources out there to help set things up the way you want?  Trying to avoid reinventing the wheel seems like a good policy in general.