# celloe

Member

16

266 Neutral

• Rank
Member
1. ## Signed distance field collisions in 2D

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?
2. ## Swept AABB collisions and the crack problem

@ LorenzoGatti That was my instinct, too, which made me wonder as to the specifics of my implementation, and where I'd.. gotten it wrong. With constant forces such as the mouse joint, it would bounce off on an initial swing (if the response was made elastic) then sink straight through. Is it to do with the ordering of resolving collisions, applying outside forces / impulses, and the integration itself?   @Krohm I understand your point fully about tools and libraries already existing to tackle this problem (box2d suffers from this also, you have to use edge chains I believe for static objects in sequence). However I do also view this as a learning experience and I value the process of solving the problem. I don't have a tight deadline or anything, I quite enjoy getting lost in the intricacies of physical simulation!   The main issue I have at this point is that I've seen from SacredSoftware's implementation that it is possible to get a more general solution, through the use of sorting collision priority based on which collision has a greater surface area of penetration in a given timeslice (or rather, time step with a threshold, as of course CCD would only really solve one at a time so you have to step forward and test a little). What puzzles me is the two facts that a) It does not function correctly without positional correction, and b) It gets stuck on an edge even in the case of a single box. I suppose if it's correcting it to the EXACT edge position, when it moves back down it would maybe get snagged on a corner? But is that correct behaviour?.. It's not common to many others, which makes me think the penetration resolution isn't quite correct, in terms of initial contact times.
3. ## Swept AABB collisions and the crack problem

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 [url=http://sacredsoftware.net/tutorials/Collisions/CollisionsPart1.html]here[/url] 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 [url=http://www.gamedev.net/page/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084]GameDev article on swept collisions[/url] (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
4. ## Impulse based friction on line segment

Just as an update I figured out the cause of the problem, I was using the center of mass velocity as opposed to the contact point velocity.. silly. All fixed now!
5. ## Impulse based friction on line segment

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: [code] // 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; [/code] 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?
6. ## Continuous collision time subdivision

Hi Paul, I've tried working with speculative contacts before (consider me a fan.. I've even commented on the article!) but the inability to model elastic collisions is a bit too much of a downside to me. As a side note, can you implement friction with speculative contacts? I imagine it's possible but don't know how you could circumvent the same problems that prevent elasticity. I'll take a look at Box2D's source, it's a little.. overwhelming at this point, but I'll keep at it. And I agree regarding deformable bodies, I was more just taking a look to see how he handled the TOI ordering. Turns out it breaks pretty easily with more than a few bodies anyway!
7. ## Continuous collision time subdivision

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 [url="http://blog.andre-michelle.com/2006/announcing-new-physics-engine-in-as3/"]PopShapes[/url] 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: [code]var dt = 1.; var pair = new CirclePair(cs[0], cs[1]); while (pair.willCollide(dt)) { pair.c1.integrate(pair.toi); pair.c2.integrate(pair.toi); dt -= pair.toi; pair.resolve(); } for (c in cs) { c.integrate(dt); // Reset forces etc c.fx = 0; c.fy = c.mass*gravity; }[/code] 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?
8. ## 2D Rotational constraint impulse

That made things way clearer, thank you! Managed to get it up and running. I'd never thought of that way of converting torque to particle acceleration! Only thing I'm going to change now is to work on angles originating from a 0,0 position as opposed to.. "relative angles" between joints, if you know what I mean. For instance, if I make a square out of 4 joints, I have to set each joint min/max angle to 90 degrees, as opposed to however many degrees it'd logically be from the origin. Shouldn't be too difficult! Thanks again. I wonder if I can somehow make it behave in a "continuous collision" sense, so that fast rotations don't distort the structures too much. Could be interesting to try.
9. ## 2D Rotational constraint impulse

Thank you! That's genius.. I'd had the same sort of idea as the method you're using, just wasn't sure how to implement it. The code's a little difficult for me to decipher (not used to freebasic syntax) but I'm sure if I spend a bit of time on it I'll be able to crack it. 2 initial questions though: In the "get angular spring angle" section, how did you derive the method to get the angle of the joint? And I assume dotnormal is just the normalised dot product, or is it literally "normal" to the dot product in the sense that it's geometrically perpendicular? Another thing.. you mention the spring torque based on sine angle being less efficient but faster - what do you mean less efficient? It seems like it'd be overall better as an optimization to avoid having to calculate the atan2 which'd require the cosine and sine.
10. ## 2D Rotational constraint impulse

Brilliant, thanks. I'm in Europe too, looking forward to it!
11. ## 2D Rotational constraint impulse

That'd be great, yes please! (is it the shape matching one? I remember stalking that thread for days a while ago)
12. ## 2D Rotational constraint impulse

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: [code]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 }[/code] Obviously a little unoptimized at the moment, just trying to keep things relatively simple. Any help or insight is appreciated!
13. ## Dynamic circle vs line segment friction

I've been trying to wrap my head around this for a while - I've got a circle sliding down an inclined plane, in an entirely non-elastic reaction, and I can't figure out how to slow it down accordingly. I'm not simulating angular motion, as in the circle doesn't explicitly rotate, it just slides down. Would anybody be able to help me understand the correct force to apply for simple sliding friction on the circle? All the articles / explanations I've found either explain entirely static friction or between 2 moving bodies.
14. ## Closest point on cubic bézier curve

I'm trying to find the point on a cubic bézier curve closest to another external point P, in 2D space. I've read the Graphics Gems explanation on the method and other stuff but the math's way over my head. Specifically I don't really understand how finding the roots of the.. curve's polynomial (am I making sense?) gets you closer to the solution. Would somebody be able to explain this in a 14 year old's terms? (:
15. ## Angular constraints in 2D

Yup, exactly! All I have thus far are simple Jakobsen-style distance constraints in a particle system.