NewsForumsCodeLogsGallerySpecsSearch

Verlet Blob

Blitz3D Forums/Blitz3D Programming/Verlet Blob

Buggy(Posted 2009) [#1]
Firstly, sorry for all of the verlet posts.

I know that some Blitz users have had success with what appears to be Verlet blobs (Oddball comes to mind), and would appreciate any help.

After successfully creating Verlet chains, I decided to make a fun little Verlet blob. Following this article, I have a program that creates a blob of a user-specified number of joints. It has a double-layered skin and a center point in the exact same style as that of the article. And all works well when the number of outer joints is less than around 8 or 9 (that is, 8 outer joints, 8 inner joints, and the single central joint). My problem arises when I try to have bigger (and thus more blob-like) blobs.

Once I have about 9 outer joints, the blob does well for a few seconds, then begins to shake and ultimately collapses, and the end result is that it folds over on itself. The article mentions folding, but only when the number of joints gets towards 80, which I am obviously nowhere near.

The article also mentions stability as an issue, and the author said that this was fixed when he divided the verlet integration into two separate loops... one loop to calculate the force of all of the constraints, and a second to move each joint. When implementing this method, however, the points go all over the place. Examining it frame-by-frame, it appears that using this method, the points overcorrect themselves to cause chaos. For example, in one frame, the central point will move a hair upwards. The next frame, it will overcorrect downwards. Then upwards, then downwards, until its Y-value becomes infinity, or NaN.

If anyone either knows what is happening (if this makes any sense at all) or has ideas for how I could fix this, they would be much appreciated. I can post code if necessary.

Thanks in advance.


Nate the Great(Posted 2009) [#2]
I had a similar problem with my verlet physics engine/experiment thingy.. when I had maybe 50 verlets in a sphere shape they would all vibrate and wiggle but somehow I got around this... not sure how it just happened when I was messing around with it

good luck

I may be able to offer more help if you could post some code?

feel free to take a look :)

http://www.blitzbasic.com/Community/posts.php?topic=80075

http://www.blitzbasic.com/Community/posts.php?topic=80320


Stevie G(Posted 2009) [#3]
@ Buggy, how many relaxation iterations are you using for the contraints? What timestep size are you using? Can you show some code for this 2 loop method?

In my experience, this will always be a problem, particularly with hard collisions. The only way round it is to have an orientation constraint, from the center of the sphere to one of the outer points. Store each point's start position relative to the center of the orientation before you start the simulation. Every time you move a point check to see how much it has deviated from where it should be in relation to this orientation constraint and where it currently is. If the difference is over a certain threshold then force it towards it's correct position.


Buggy(Posted 2009) [#4]
Stevie, the orientation constraint's a great idea, and I might have to use it. I was trying to steer away from an orientation/angle restraint, at least until I got it to work as-is, because with 10 outer joints, it collapses quite quickly without colliding into anything, which leads me to believe there's a problem with the joint-joint constraint code/implementation.

As of now, I'm using just one relaxation iteration, and a timestep of 1. But I've tried relaxation iterations of anything from 1 to 100, and nothing helps. In fact, with ridiculously large relaxation iterations, once-stable shapes tend to wobble quite violently.

I decided to examine the extension values (the difference between the actual distance and the correct distance) in the very first iteration after creating a blob. While no values are suspiciously high, I have some around .2 or .3, which I suspect may be due to discrepancies between floating-point location variables and integer pixel values, though I haven't been able to fix this even by converting everything to floats. Could this be the source of the instability?

I don't have the code on me right now, but here's the general framework:

Go through each joint and:
-Move it according to its last position, current position, and current acceleration.
-Reposition it to keep it onscreen (i.e. with 800x600, if an x value > 800, the x value = 800, etc.)
-Calculate constraints for each joint's first neighbor (adjacent ones), and move joints accordingly.
-Calculate constraints for each joint's second neighbor (diagonal or vertical ones), and move joints accordingly.

Then:
-Move center point according to its last position, current position, and current acceleration.
-For each inner joint, calculate constraint between joint and center point, and move both accordingly.

...and Stevie, with the 2-loop method, each joint has an adjustX# and adjustY# value. Implementation is the same, except when calculating constraints, instead of moving the joint, values are added to its adjustX# and adjustY# values. After everything has been done, it goes through and moves each joint according to these values, and then sets adjustX# and adjustY# back to zero.

It just occurred to me that the reason this particular 2-loop method isn't working could be that I still move each joint in the moving phase, even though I don't move them during the constraint phase any more. Could that be one of the problems?

Thanks for all the help.


Nate the Great(Posted 2009) [#5]
It just occurred to me that the reason this particular 2-loop method isn't working could be that I still move each joint in the moving phase, even though I don't move them during the constraint phase any more. Could that be one of the problems?



as far as I know you arent supposed to move them in the constraint phase

ummm based on your description of the framework this is a 2-d verlet system? ok that simplifies stuff a little :)

a simple example of what you are trying to do with your verlet system or what you plan to do would be helpful :)


Buggy(Posted 2009) [#6]
By moving them in the constraint phase, I meant moving both points either closer together or farther apart, to satisfy the distance constraints.

Yes, this is a 2D system... sorry for any confusion.

As far as what I plan to do, I don't really know, but this something like this springs to mind at the moment.


Nate the Great(Posted 2009) [#7]
hmmm from the looks of that game it seems as though they only needed 3 or 4 verlets for the main character... does your character really need 10 outer joints?... if it does that could be and probably will be solved if you mess around with the numbers and equations for a while... it took me a few weeks of messing around with my verlet system after i thought I had "finished" it to get it working properly for car physics :)

again if you have any code or an exe to download it would help us help you :)


Stevie G(Posted 2009) [#8]
@ Buggy,

Never used that method before so can't comment on how well it works. Have you tried using the standard, accumulate forces, update verlet, update constraints method?

Can you show a picture of how your verlet body is constructed, including the constraints? This is important.

It's not an angular constraint I'm was talking about - more a local space distance constraint. The angular method will probably work too - your standard dot product or minimum distance constraint.

Some ideas which should improve stability :

* Always have the longest constraints processed last. The bigger the distance the more the error so if it's processed last it more likely to be closer to it's restlength.
* Use more constraint relaxation iterations. I use 3-5 most of the time.
* Use a smaller timestep. I use 0.05 as this seems to work best for me.
* Make your central joint/pivot have a radius at least as large as the inner joint distance.
* Limit the speed of the joints by a maximum speed.
* Add proper drag & friction forces
* Post your code, you may be doing something wrong and best to get is sorted now before you start coding workarounds which you don't need.

Stevie


Nate the Great(Posted 2009) [#9]
heres another thing that I did to stabalize my update constraints function... instead of doing this

For i = 1 To 5
	;do the math stuff here
	;move the verlets to the exact place they need to be
Next


I did this

For i = 1 To 5
	;do the math stuff here
	;move the verlets HALF the distance to their target position unless it is the last loop... if it is the last loop then position them exactly
Next


its just a simple /2 but it seems to help me with stability


Pongo(Posted 2009) [#10]
It is very important which verlets are constrained to where. If they are not set properly, then things will collapse no matter how many constraints you use.

For example, a 2d box shape will need constraints between the four points, but if you do not constrain the diagonals then the whole thing will collapse easily. It would be helpful to see what your shape is and how you are constraining it.

In my own verlet code I have come up with some very stable 3d configurations that use a minimum number of verlets and constraints. Higher verlet count can slow things down as well, so it's best to keep things as light as possible.


Buggy(Posted 2009) [#11]
Firstly, thanks for all the help and support. Much appreciated.

Secondly, sorry for a ridiculously long post. Feel free to skim.

@ Stevie

I'm not exactly sure which method you're talking about. I've scrapped (for now) the adjustX#/adjustY# method, but its remains can still be seen in the code. Could you explain what you mean by the "standard" method? I don't appear to have any "accumulate forces" part of my code... perhaps I should? Or is that what I was trying (unsuccessfully) to accomplish with my adjustX#/adjustY# code? I'm a bit confused here...

My blob is (I believe) set up identically to the one in this article. Run the code to see.

I may have to implement angular or distance constraints, but I think there's an underlying problem that needs to get dealt with first.

Thanks a ton for all of your suggestions! I haven't tried them all, but changing the number of relaxations and time step doesn't seem to help too much. I have drag implemented (just a basic *1.99 sort of thing), but friction wouldn't seem to matter at this point as I have no level!

@ Nate the Great

Thanks so much... great idea! I implemented it and it helped the stability somewhat. Blobs with 10 outer joints used to collapse/fold in half. With your trick, they did much better, but blobs would still collapse when I got around 12 outer joints, so clearly there is a deeper problem.

@ Pongo

Thanks for the advice. My shape is the same as that of the article I mentioned, and you can always run my code to see. I still could be setting it up incorrectly, because it seems like there is an excess of energy in the system at the start - and this is magnified by the number of joints in the system.

@ All

Without any further ado, I present my code! Even though some suggestions (Nate the Great's neat trick, Stevie's - and others' - advice to increase the number of relaxation iterations and decrease the time step, etc.) helped some, none solved the underlying problem, so here is the code as I originally wrote it. I apologize in advance for any unreadability. Ask me if you have any questions.

Another problem I forgot to mention is every blob's tendency to spin counter-clockwise during its initial freefall. Could this have to do with the problem? I have absolutely no clue why it happens, so maybe...

Also good to know:
-Blobs are created by clicking the mouse.
-Blobs can be controlled by the arrow keys and the spacebar.
-To change the size of a blob, you must alter the constant NUM_OUTER_BLOB_JOINTS at the top of the code. Because of Blitz arrays, I couldn't implement a way to change the number of blob joints during the running of the program.

And here it is.



Guy Fawkes(Posted 2009) [#12]
Did this cuz I was bored. It doesnt quite work, but you get the idea. This will stop lag.




Buggy(Posted 2009) [#13]
@ DarkShadowWing

What you want is two global variables, not type fields. And thanks, but that's not really the issue here at all.


Stevie G(Posted 2009) [#14]
@ DarkShadowWing - your code doesn't run.

@ Buggy, I can see immediately that you don't have enough constraints. You need some more diagonals between the outer and inner joints and also constrain the outer joints to the center of the blob.

Your iteration method for constraints isn't coded correctly which is probably why setting it higher than 1 makes no difference. The iteration loop should be outside the constraint loop, otherwise your just correcting the same constraint a number of times & moving on to the next. You should be correcting all the constraints each iteration. Even then something is not right as increasing the iterations now causes it to go haywire.

Why are you keeping point and joint separate? They are basically the same thing ( pointmasses ) and should have the same properties.

Basically, I don't understand why you are doing constraints this way - I think you've over complicated things. I guess I'm just used to the simple Jacobsen methods.


Guy Fawkes(Posted 2009) [#15]
I know. Thats why I said "it doesnt quite work, but you get the idea".


Pongo(Posted 2009) [#16]
Ahh, I see now. I hadn't looked at the link until now. It's a pretty neat concept.

I agree with Stevie that you may need more constraints, but more importantly, you need to fix the iteration loop. Once you are able to feed a few iterations through, then things will stabilize quite a bit.


Nate the Great(Posted 2009) [#17]
hmmm it looks as though you are using a much more complicated method than I originally thought... I will look through it a bit and see what I can figure out


Buggy(Posted 2009) [#18]
@ Stevie

I changed the joint setup. Now, inner joints are spaced inside and between outer joints, and all joints are connected to the center point. I don't know if this is good or bad, but it allows me to at least see things clearer.

Thank you, thank you, thank you for noticing the iteration problem. I can't believe I didn't catch that, but it was indeed the source of many (I won't dare say all) of my woes. Now I can do around 12 outer joints without it imploding. More than that, however, and you're right - it goes haywire. The whole thing starts wobbling and spinning (counterclockwise, as always) until it goes nuts. Collisions seem to help it calm down.

Funny you should say that about Jacobsen - I started this project by thoroughly reading and rereading his paper. I admit I wouldn't like to have "joints" and the "center point" be separate types, but I've become quite attached to using types. From there, it made sense to store the joints in a blitz array within a "blob" type, but blitz arrays are quite finicky. They only accept a constant number of elements, so if I have each joint store the joints it's connected to, then each joint would have two other joints stored, except the center point, which is connected to all of them (used to be half of them). So you see, I really didn't see any other options at the time. I suppose now, if I'm connecting each joint to the center point, I could have the joints each store the center point as well, but then the center point wouldn't store any and would have to be a separate type to keep my memory-conscious impulses appeased. And now I'm rambling, and possibly unintelligible.

The bottom line is, thank you everyone. While this is still not really fixed per se, I appreciate the support, and I am making progress. Now I just have to figure out why using more than 12-ish outer joints makes it go nuts. Any more ideas?


Buggy(Posted 2009) [#19]
Hmm... problem solved? Apparently I had forgotten to fix the iteration for the center point. And with a small time step, a few iterations, and not *too* many joints... eet verks! And it even occasionally spins clockwise! Go figure!

Complete source code below:


Thanks everyone for all the help!


Nate the Great(Posted 2009) [#20]
now I assume you will have to turn all of the constraints into rubberband-like constraints for a blob effect?


Stevie G(Posted 2009) [#21]
To make it more blobbish I'd recommend not using an elasticity value when doing your constraints. Use the inverse mass proportioning as per the jacobsen article. If you make the center point have a large mass and the outer and inner points have a smaller mass then it should behave as you want.


Buggy(Posted 2009) [#22]
I don't actually know how I'd go about using rubberband-like constraints, but I've tried Stevie G's advice, and it works somewhat. The best I can get is a circle with sides (well, circles technically don't have sides, but anyway...) that compress upon colliding with the ground or walls. I can't seem to get it to really droop at all on my own. Is there something else I should be doing, or should I just keep fiddling? I've searched online and can't find any answers...

I suppose I could also have a blob-like shape, instead of a circle, at the start. But it wouldn't really deform like Mick West's (once again, here) seem to.

Thanks again for the help.


Nate the Great(Posted 2009) [#23]
you could give the constraints a length 'range'


Buggy(Posted 2009) [#24]
I tried something like that I think (only perform the constraint correction if abs(extension#) > 5 or some other number), and it didn't really work at all. It just seemed to make everything vibrate. I'll continue to fiddle. And maybe violin a bit as well. ;)