Verlet Integration: Constraint Collisions

Blitz3D Forums/Blitz3D Programming/Verlet Integration: Constraint Collisions

ClayPigeon(Posted 2010) [#1]
Okay, I have a Verlet engine I made and I absolutely need collisions. From what I can tell, collision response for pointmass-to-constraint is all that's required to have rigid body behavior. Can someone post a GOOD explanation of how to do the collision detection/impulse (reaction) in a Verlet engine? And maybe a code? I don't just want a code so I can stick it in my program, I want to understand it so I can make my own. So can anyone help me with this?

P.S. I've looked at a bunch of Verlet engines in B3D that have successfully done this, but are so messy and cluttered that I can't tell what's going on in them. Sigh..

P.P.S. Here's my code so far:


Last edited 2010

Last edited 2010


Stevie G(Posted 2010) [#2]
This is a good article:

http://www.gamedev.net/reference/programming/features/verletPhys/


ClayPigeon(Posted 2010) [#3]
Yea, I've seen that one. The collision handling in it isn't really that in-depth, as it shows a collision with a square. Then, if you go to the second page, it goes into the Separating Axis Theorem, which I know more complicated than need be. There's some way that collisions are done with constraints that everyone seems to know but me..

Last edited 2010


Yasha(Posted 2010) [#4]
I've looked at a bunch of Verlet engines in B3D that have successfully done this


Are you sure? I've only ever come across Verlet engines in B3D that used point-to-point collision and simply made the points' collision radius huge.


ClayPigeon(Posted 2010) [#5]
Oh, yeah. I guess that's the kludgy method. I saw a few that did that. The way that works, the objects can pass through one another if their velocity is great enough. I originally thought that if I did a line-line collision between a constraint line and a line created from a point's previous and current position, I could just move said point to the location where the lines intersect. But for some reason that didn't work one bit. The instant two objects collided, they would slow down, but slip through each other. I don't understand why that wouldn't work?

Last edited 2010


ClayPigeon(Posted 2010) [#6]
I've noticed that all my topics seem to die eventually without it ever really getting solved.. If no one can figure it out, feel free to say so.


Yasha(Posted 2010) [#7]
Well I for one have nothing else constructive to contribute... I gave this a brief attempt myself a while back, but couldn't get it right at the time (wasn't going about it the same way as you are, I think).

I gave up on bothering to make it work myself for a combination of two reasons: 1) Collisions are expensive, so you really need a good collision engine like ColDet to do them for you rather than write it from scratch, if they're to be fast enough; and 2) if you're going to use a DLL anyway, may as well just use ODE and be done with it. To be honest I can't really see how any Verlet-based system that also uses rigid bodies is going to be better than ODE (which is a rigid body engine) anyway... seems like extra complexity for a less complete system? (in fact in my limited experience any B3D-code solution is slower than ODE, even a very simple kludge-Verlet system that only uses point collisions. StevieG might have some tricks involving space partitioning up his sleeve though).


ClayPigeon(Posted 2010) [#8]
I guess I see what you're saying...? I might have forgotten to mention I'm after 2D Verlet. Can ODE do 2D? If so, how. I didn't know..


Yasha(Posted 2010) [#9]
Oh... that's a completely different matter! It makes rather more sense that you would want collisions only with lines, rather than polygons, in light of that information. Anyway, in that case, it sounds like your original idea ought to work (I think? Never done such a thing) - perhaps there was an error in the implementation? Sorry, for some reason I never thought to actually look at your posted code. I'll do that now.

Yes ODE and other 3D physics engines can be used for 2D, but I wouldn't bother... for the vast majority of 2D projects, native Blitz physics actually is fast enough (and constraining a 3D engine to two dimensions is more trouble than it's worth). It's the transition to 3D where they slow down. I think Physix (part of the original Draw3D package, I don't think it's in V2 any more though) was pretty fast, and had working collision, so it might be worth a look if you need examples.

Well anyway here's a quick (and admittedly broken) take on the idea suggested above:


Several obvious problems appear in the above: the biggest is that the movement of a constraint over a point when the point isn't moving isn't caught, so the static corner has no effect; and there's no attempt to correct for the inevitable errors introduced by the collision check (moving the point in response to a collision requires moving the rest of the constrained points which I haven't done, which in turn will involve re-correcting everything else).

In response to the problem of detecting contraints moving over points... perhaps you could do it another way; define "collision polygons" over three points (you could define squares as two triangles... although you could use separate algorithms for regular shapes like squares and circles), and "collision bodies" that are made up of a set of points, constraints and polygons, and do a check (faster than line intersection I think?) whether any relevant points are within each polygon. If they are, apply a movement to both the complete object attached to the offending point, and the complete object attached to the collision polygon. This should require rather less repetitive correction. Not sure whether you should then check for a new set of collisions or just enqueue it as a force for the next update (probably the latter as otherwise you might get stuck in an infinite loop if the particular collision is too complex).

Last edited 2010


ClayPigeon(Posted 2010) [#10]
Oh, great! So it isn't completely worthless. Good attempt! I might be able to get this working. BTW, I didn't know you could declare global vars right before a function - how does that work?


Serpent(Posted 2010) [#11]
You can declare them anywhere in the source code. From what I know (and hopefully I'm not wrong) the compiler will make it so that they're declared from the start of the program.


Yasha(Posted 2010) [#12]
the compiler will make it so that they're declared from the start of the program.


Actually it won't... they still have to be declared before any uses in the "main" scope. However, they will work correctly from within a function, regardless of whether the function was declared before or after the global.

Remember that when a variable is declared you can iitialise it on the same line:

Global startX = GetStartingX(), startY = GetStartingY()


That line of code will run in order with everything else, at the point where it appears in the main program. This means two things: 1) Global declarations are tied to a particular point within the main scope, because their initialisation expression is part of that scope, and 2) while the variable is accessible at any time from within a function, if you call that function before reaching the initialiser line in the main scope, it won't have happened yet and the variable may still be un-set.

Last edited 2010


Serpent(Posted 2010) [#13]
I stand corrected....