Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 21 Jan 2011
Offline Last Active Apr 07 2014 05:11 PM

Topics I've Started

Signed distance field collisions in 2D

01 February 2014 - 10:09 AM

I've been eyeing up this article for a little while - http://lab.polygonal.de/?p=239


My idea is to get a collision detection system working in AS3 based on a bitmap representing static terrain, convert it to a SDF and collide an AABB against it - so essentially, terrain can be generated based on any image, as opposed to inputting polygon information and vertices etc. The signed distance field method seems suitable for this, but I'm having trouble actually understanding the implementation - unfortunately, that article is the clearest of the sources on it I've come across. Could anybody provide an explanation as to how to go about actually implementing the algorithm for this?

Swept AABB collisions and the crack problem

30 May 2013 - 05:02 PM

Hello! Copying this over from a post I made on tigsource, hopefully I can articulate my troubles sufficiently.. I've been working on a tile based game that might end up involving high velocities and decided to go for a continuous collision detection sort of model, due to some nasty looking behaviour where the character approaches the edge of a tile too fast. I've done some searching around at various implementations of CCD, and it seems to vary from example to example.
Having looked at ThemsAllTook's implementation and guide for swept AABB collisions here I understood the theory but found the actual intersection check a little hard to follow, particularly with the use of previous positions as opposed to velocities - but I suppose they're equivalent. I've ended up settling for an amalgam of that and a GameDev article on swept collisions (which I found a bit more intuitive).

The trouble is, I'm finding it difficult to overcome the surface area 'stubbed toe' problem. I figured I could find out minimum translation distances from new positions and intersection positions, but sorting by the surface area calculated in that fashion (technically just on one axis in the case of my implementation) doesn't seem to quite work and I get edge 'stopping' even in the case of just one collision.

Here is a demo of it in action, you can control it with arrow keys or the mouse - http://www.filz.us/view/1e940c5a-764/. The most noticable effect is if you slide up against one side, then slide off it on that axis and try to slide back - you'll get stuck on the corner.

Another thing I wasn't quite clear on was the fact that I found myself having to set the object's position to its corrected one, is that standard for a CCD simulation? I wasn't sure if I'd only be dealing with negating velocities and so on, it just struck me as odd. Without the positional correction in the collision resolution, I'd get issues with persistent forces acting on the body causing it to sink through other AABBs.

This is the simplified code, if it's at all decipherable I'd really appreciate it if somebody could point out how to go about solving the problem, and if my implementation of CCD even makes sense - http://pastebin.com/xWFsuxWm

Impulse based friction on line segment

24 February 2012 - 04:30 PM

Trying to figure out the friction impulse to apply on a circle rolling down a line segment, I've read a lot of other threads and it seems like it's kind of similar to the elastic impulse:

// nx & ny = contact normal
// fE = elastic impulse
// dx & dy = distance from center of mass to contact point

var tx = -ny;
var ty = nx;

var tCross = dx*ty-dy*tx;

var friction = .5;

var fF = tx*c.vx+ty*c.vy;
fF /= (c.inverseMass+(tCross*tCross)/c.momentOfInertia);

var fx = (fE*nx)+(friction*fF*tx);
var fy = (fE*ny)+(friction*fF*ty);

// xy velocity + angular

c.vx -= fx*c.inverseMass;
c.vy -= fy*c.inverseMass;

c.av -= (dx*fy-dy*fx)/c.momentOfInertia;

This is following the same sort of "pattern" adapted for the angular force as the usual
j = -(1 + e)rV . n / (n . n(iM1) + (pv1 . n)^2 / I1)

However when it came to the implementation, the behaviour of it's a little.. strange. Here's a demo - http://www.fileize.com/view/9137d063-58a/
I've tried clamping the friction to be a limit based on the elastic impulse but that didn't really do much. Could anybody enlighten me as to where I've slipped up?

Continuous collision time subdivision

13 February 2012 - 01:01 PM

Hey guys, been working on something all day and haven't been able to make any progress whatsoever.. I've been trying out continuous collision detection through an approach of "find time of impact, if it's within the next frame integrate positions to that time, solve, then resume simulating" which should work fine. I've been looking at a few implementations, namely Andre Michelle's PopShapes physics engine (and his other one, Revive, but I think his site's down just now). I understand the method and the theory behind it but when it comes to implementation I can never seem to get it quite right, it'll detect first collisions and attempt to solve them but it can easily.. go wrong.

Here's an example of the sort of thing I'm doing:
var dt = 1.;

var pair = new CirclePair(cs[0], cs[1]);

while (pair.willCollide(dt)) {
    dt -= pair.toi;

for (c in cs) {
    // Reset forces etc
    c.fx = 0;
    c.fy = c.mass*gravity;

This works in certains situations, though in others will just completely lock up. If I add a breaking term, for instance incrementing a variable each step and terminating the while loop if it exceeds a certain value, then it never crashes but penetration occurs. What could be the cause of this?

2D Rotational constraint impulse

22 November 2011 - 11:38 AM

Hi guys, I've been having some trouble implementing rotational min/max angle constraints. It's pretty straightforward with verlet integration but right now I'm using semi-implicit euler (subject to change) and velocity needs to be explicitly modified. I don't really know how to apply a rotational impulse..
With 3 points, p1, p2 and p3, all holding their own velocities and forces, I need to resolve the constraint of the angle between p1, p2 and p3 (p2 being the midpoint) such that min <= angle <= max. I assume what I should be doing is rotating p3 around p2 based on the difference between the desired and current angle, but that could get unstable and I don't really know where to start.

So far it's just basic angle detection from -PI to PI so it looks like this:
public function solveAngular() {
	var ex = p2.x-p1.x;
	var ey = p2.y-p1.y;
	var fx = p3.x-p2.x;
	var fy = p3.y-p2.y;
	var dot = ex*fx+ey*fy;
	var cross = ex*fy-ey*fx;
	var angle = Math.atan2(cross, dot);
	if (angle > min && angle < max) return;
	var correction = 0.;
	if (angle < min) correction = min-angle;
	if (angle > max) correction = max-angle;
	// Resolve

Obviously a little unoptimized at the moment, just trying to keep things relatively simple. Any help or insight is appreciated!