Jump to content
  • Advertisement
Sign in to follow this  

olii's PolyColly - Questions about refactoring

This topic is 3441 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all, I've been translating olii's polycolly to pascal, and I did some refactors/changes to the source. I've gone until tutorial 5 (dealing with rotations). And I'm using Delphi 7. Questions: On his CBody class he has the following method:
void CBody::AddImpulse(const Vector& F, float dt)
	if (IsUnmovable()) return;

	m_xDisplacement += F * (m_fInvMass * dt*dt);

This adds an impulse, and needs to be passed the DeltaTime, and it directly affects the body's displacement. Shouldn't be better to just store the wanted force vector, and process the new displacement in his method Update() ? His Update method:
void CBody::Update(float dt)
	if (IsUnmovable())
		m_xDisplacement = Vector(0, 0);
	m_xPosition += m_xDisplacement;

	m_fAngle      += m_fAngVelocity * dt;
	m_xOrientation = Matrix(m_fAngle);

	wrapf(m_fAngle, 0, TwoPi());

Second, I want to let the player control the rotation of the objects, and this can be done by changing the m_fAngVelocity class member. To allow this, should I approach in a similar way to storing the new angular velocity, and just calculate again in the Update() method?

Share this post

Link to post
Share on other sites
I should kick that code into space...

Hmmm, in fact you gave me something to do over the weekend.

here is an update of the code, which I'm much more comfortable with. The collision detection is much better anyway (the original version is conceptually wrong).

Also, note that the code's focus is on collision detection, not physics. But, I need to clean up the mess, and write a doc or something.

In the test example (I'm referring to the updated code from now on), there is no need for forces, as the only forces are collision impulses. These are not frame time dependent, which removes the need to cache the net force that you would need to apply if you wanted to add control over the body's movement.

So yeah, in the body class, add a m_netforce, m_netTorque vectors, which then would be the external forces you want to apply to the body at the next integration.

Displacement is not a good thing when dealing with rigid bodies. It's better to store quantities as velocities and time slices instead. Which is what I do in the updated code.

You have to be careful about the 'controls' you bring into a rigid body simulation. The only valid form of control is controlling the momentum (angular or linear) of the bodies.

By that I mean, if you modify the position or velocity manually, it can break the physics. For ultimate control, you need to bring in constraints into the fold, but it's maths intensive.

Even my 'separation' code is not valid. That introduces jitter in the simulation when stacking / large forces occurs. But it's a simple method to resolve intersections.

To control angular velocity, you need to add / subtract extra angular momentum. The inertia of a body also impact on how much control you can have over angular momentum (i.e. you need less angular momentum to rotate a thin rod).

If you want to have complete control over the angular component, you will need infinite inertia (inverse inertia = 0), so that you can rotate the body at will, however the body's angular momentum will not change after a collision.

Similarly, if you want platforms that translate (say, along a path) but do not react to player collisions, you will need to set their mass to infinity (inverse mass = 0).

That way, collisions with players and free bodies will act naturally.

To summarise, Depending on what part of the body you want to control manually (meaning, not reacting or breaking collision response), you need to set inverse mass / inertia to 0.

If you want to control a free body (where inertia and mass are not infinite), you will need to introduce the controls via forces / impulses / accelerations.

Share this post

Link to post
Share on other sites
Hi, thanks for the help

I took a brief look at what changed in this updated code, couldn't see much changes in the body class, except collision detection.

I'm ok with very simple physics - it's what I want, simplistic physics and collision detection, that's why I decided to port those old demos, and stopped at tutorial 5, it seemed enough for what I was aiming.

I want a very simple physics engine for a 2D top-down shooter. The rotation should be used for player/ai-driven vehicles. For dynamics objects, mostly pushing/slinding. Later, I was planning for adding multiplayer support (I haven't thought of this yet).

For controling this, you said there would be need for impulses, and I believe it's just like in the code I posted earlier, and on this update code you posted is just like this:

Vector impulse = nc * (jc * -(1.0f + cor)) + nf * (jf * -1.0f);

a->m_velocity += impulse * a->m_invmass;
b->m_velocity -= impulse * b->m_invmass;

a->m_angvelocity += (ra ^ impulse) * a->m_invinertia;
b->m_angvelocity -= (rb ^ impulse) * b->m_invinertia;

Right? I'm just going to change velocity and angular velocity by applying forces to it, right?

I haven't figured out yet this time slice thing you mentioned, and how it would fit my needs, since the old demo seemed to work without problems.

Thanks for the help

Share this post

Link to post
Share on other sites

Just curiously, iirc, your updated code removed circle vs polygon implementation?

As I've lately come across using SAT to do sphere vs triangles collision detection (aware of velocity) and "unpenetration" of sphere already stuck in triangles.

I discovered that in order to do it accurately the axes to test in edge and vertex cases are different than the static overlap test's ones. Each edge or vertex case may yield one or two axes to test. The derivation of the axes involves the velocity vector and the calculation is not very simple (each case may require a few sqrt()), thus the performance is not very good (but still fine for the job).

So, any comment on my implementation? As its very hard to find material in the net describing using SAT for the problem.

Thanks in advance

Share this post

Link to post
Share on other sites
well displacement is velocity * time. That's what I mean by that. I think it's better to use a velocity and a time quantity, rather than just a displacement vector when doing physics.

A force is a change of momentum over time. If you want to apply a force, then you need to supply a time. Usually, when you see

void Body::applyForce(const Vector Force, const Vector& PointOfApplication);

the time is implied, as the force will be integrated over a time period. So you can use forces to control a vehicle, which is usually what is done, and impulses are used for the result of instantaneous events, such as collisions.

void Body::applyForce(const Vector force, const Vector& pointOfApplication)
m_netForce += force;
m_netTorque += (pointOfApplication - m_position) ^ force;

void Body::integrate(float dt)
Vector linAcceleration = m_netForce * m_invMass;
Vector angAcceleration = m_netTorque * m_invInertia;

m_linVelocity += linAcceleration * dt;
m_angVelocity += angAcceleration * dt;

m_position += m_linVelocity * dt;
m_orientation += m_angVelocity * dt;

m_netForce = Vector(0, 0);
m_netTorque = Vector(0, 0);

You will find that controlling bodies via forces can be problematic though.

Share this post

Link to post
Share on other sites
The SAT is not really suited to spheres. You can imagine spheres as polygons with an infinite number of edges, which would make an infinite number of axes to test.

Or you can think of spheres as a single point, however that approximation breaks where spheres become large compared to the polygons.

I use a different method, which is basically a straight forward collision test against the polygon and its edges.


Quite a lot of code, but in there is also the point-sphere test, the sphere-edge test, and the sphere-sphere and ray-sphere test (which are basically derived from the point-sphere algorithm).

If you want a do-it-all algorithm, you would have to look at the GJK, especially its swept versions (for fast moving objects).

Share this post

Link to post
Share on other sites

Thanks for your reply first

Actually, I found that the number of axes to test for the SAT method is finite and the result is very accurate. I know your suggested method and I had used it for years. I think there are a couple of reasons that drived me to use the SAT method. The first one was that to "unpenetrate" the spheres from triangles, I need a direction (also the minimum distance), and the SAT method always has a finite number of axes to test, thus I can obtain the direction from those axes. Second, often the SAT implementation tends to give interval (and first time and last time contact). But after reading your reply, I think I will give the (line-triangle, sphere-lineseg, sphere-pointsphere) a try again, with first and last time contact information (maybe it can save a few cycles for each axis to test).

Share this post

Link to post
Share on other sites
The standard algo should give you the MTD as well, to separate the two objects in case of an intersection.

But yeah, the swept SAT gives you the enter and exit planes for free, as it is basically an extended ray-polygon test.

Anyway, if it works well enough for you, then the argument is moot. I just noticed that the SAT with spheres has innacuracies (false positives) in extreme cases (large sphere, sphere moving fast, ....). kinda the same problem as this one.

EDIT : hmm if you want the enter and exit values using the standard brute-force algo, I suppose that can be done. However that will be more expensive to run (as you cant use the partitioning optimisation to reduce the number of edges to test).

EDIT 2: I will add back the spheres in the latest demo. Two extra examples, but first I need to write a doc. I'm also switching to SDL, for the sake of it.

Share this post

Link to post
Share on other sites
Yeah, my non SAT method also derives from the one your last post linking to. But as said in other posts in the forum (here), the inaccuracy of that one is because the handling of the edge and vertex case is wrong.

Hm... not sure what the inaccuracies that you are referring to for the SAT method. But yes, your previous SAT code did exhibit some inaccuracies, I looked into the code, the axes of the swept test version are the same as of the overlap test version. And I think the inaccuracy is developed from the vertex cases. Deriving from my 3D version, the axis to test for a specific vertex may be first shoot a ray from the vertex to the cirle's negated velocity dir then the axes to test are the directions from the intersecting points of the ray and circle to the center of the circle if any.

Yes, my "unpenetration" gives up a lot of optimization, given a maximum "unpenetrating" distance, all the triangles probably intersecting will need to be tested. And all the potential shortest "unpenetrating" directions (from the SAT) will need to tested too.

Thank you very much, your replies have been very helpful

[Edited by - hellknows2008 on January 16, 2009 7:07:46 AM]

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!