This article was originally published in the “Inner Product†column in Game Developer Magazine, May 2006
USING VERLET PHYSICS TO SIMULATE BLOBS
Download the blob code and executable:
DOWNLOAD
91K
Games such as Gish from Chronic Logic on the PC and LocoRoco from Sony on the PSP use a 2D physical simulation of a blob as the main character. The physics behind this blob provides the main basis for the gameplay within these games. Since the focus is heavily on gameplay, the actual physics has very little relation to reality, and is not the kind of thing you find covered in books on game physics. This article sets out the basics behind one method of 2D blob physics, and discusses some of the practical implementation issues. I also provide full source code and a demo program for a working blob system.
MASS SPRING SYSTEM
Both games mentioned use a model that has been used for decades; a “mass spring systemâ€. This is simply a collection of point masses connected by a series of springs, roughly in the shape of the object you desire. You can think of it like a particle system, where each particle is attached to some other particles by a number of springs. See figure 1 for a simple example.
Figure 1 – A simple mass-sping system with three masses and three springs
A simple spring connects two points, and has four basic parameters.
1. The rest length, which is the length of the spring when it is neither stretched not compressed
2. The minimum length of the spring when fully compressed
3. The maximum length of the spring when fully extended
4. The force exerted by the spring, proportional to its displacement from the rest length
Some springs can exert a different force depending on if they are compressed or stretched. The force can also vary in a non-linear relationship with the displacement, but for our purposes, the simple spring described above works well, and is easy to use.
A simple point mass has three parameters
1. The position in space, expressed as a 2D vector
2. Its previous position
2. Its mass
For most of what we are doing, I use a mass of 1.0 for all the point masses. However it’s useful to have a per-point mass, as it makes it easy to try various effects. If you end up with all the masses being the same, then you can obviously optimize this out of the computation.
VERLET MADE EASY
Verlet Integration is a fancy name for a slightly different way of applying the velocity and acceleration of a point to its position. Normally a point P will have a position X and a velocity V. Forces act on the particle, namely gravity, air resistance and the springs. The traditional (non-Verlet) way of updating the position of a particle is to first update the velocity with the acceleration and then update the position with this velocity:
F = total of forces acting on this point
T = Time step to update over
V += T*F/M
X += V*T + F/M/2*T*T
This generally referred to as Euler integration (with a second order Taylor series correction), but you might recognize it as the standard Newtonian equations of motion, (more usually notated as v=u+a*t and s=u*t+1/2*a*t*t). While referring to this as “integration†is technically correct, and will lead to a deeper understanding eventually, don’t worry if you don’t follow what is meant by “integration†– just think in terms of the equations of motion.
Verlet integration is basically another way of performing this physics advancement step. With Verlet we do not store the velocity, instead we store the previous position, and the velocity is implied as the difference of the current position from the previous position. The physics update then becomes:
F = total of forces acting on this point
T = Time step to update over
X0 is the previous position, X1 is the current position
XT = X1
X1 += (X1-X0) + F/M*T*T
X0 = XT
So why use Verlet, well technically using Verlet integration is more accurate than using Euler integration when the forces vary along with position and velocity. The reasons why this is so are a little obscure, and for many practically game purposes this difference in accuracy is not a major issue. The main reason for using Verlet is that it makes it very easy to apply constraints to a physical system. When a point moves past a physical limit (such as one point moving further away from another point than the maximum length of a spring that connects them), then we can simply move the point back to a “safe†position within that length. There is no need to calculate an impulse velocity, as the velocity is implied in the position, and is automatically handled by the movement.
BUILDING A BLOB
Once I got the basic spring-mass system working, I needed to create a blob. I figured that since the natural shape of a body of water is a sphere (when subjected to neutral external forces, such as a rain drop, or a blob of water in zero gravity), then I should start with a circular spring mass system, and then the application of gravity would naturally deform it into a nice blob shape.
Figure 2 – A single skinned blob, suffers from an easily folded skin
So my first attempt (figure 2) was a circle of 20 point masses, each joined to each other , and to a center point by springs. This is a standard N-gon, with the rest lengths of the springs being the natural lengths of the sides of the N-gon. This worked reasonably well for a first pass, and gave me something vaguely blobby that settled into circle under zero gravity, and deformed a bit when resting on the ground under gravity. But it suffered from several problems:
• The “skin†of the blob (the lines around the edge) kept folding over themselves, leading to ugly spikes in the skin.
• The blob was either too wobbly, meaning the edges of the blob wiggled like a giant piece of Jello, or too stiff, meaning it looked like a rubber ball.
• It kept getting caught on things, the outer edges would wrap around a corner of the environment, and the blob would hang there, looking like a dishrag.
My first attempt at solving this was to make the inner springs (the “spokes), have a longer rest length, so they would be under compression, and have the outer springs (the “skinâ€), have a shorter rest length. I was thinking this would simulate surface tension. However, this did not work very well, the shape did not improve, and the blob tended to violently collapse if gently nudged.
A BETTER BLOB
So I decided I needed a bit more structure to the blobs to make them more stable. After a few more failed experiments I hit upon the solution. Simply give the blob two layers of skin, one inside the other like concentric circles, joined together with a fairly rigid zig-zag set of joints. The inner skin is joined to a central point as before. See figure 3.
Figure 3 – Double skinned blob, the double skin structure provides a very stable skin.
This works remarkably well. I had to tweak the constants a bit, most specifically the number of segments, the thickness of the skin, and the strength of the springs. But quite quickly I had a very realistic acting blob. See figure 4 for the blobs in action
Why does this work so well? A “blob†here is a blob of very thick and slippery liquid, something like mercury. Mercury has a negative coefficient of surface tension, meaning the “skin†of a drop of mercury has very different properties to the interior. I initially though that the increased tension within the skin structure of our new blob was in some way simulating the effects of surface tension. But after looking at it for a while, I saw that the main effect it was having was constraining the curvature of the skin, thus smoothing out the high frequency wobbles we saw earlier. It’s simulating the appearance of surface tension rather than the underlying physics.
Figure 4 – The blob physics in action with various blobs. Download the sample to see for yourself.
BLOB PROBLEMS
I encountered three major problems in implementing this system. Firstly the blobs tended to be unstable, and wobbled all over the screen in the absence of external forces. Secondly, the blobs would get stuck, especially against corners, but also against surfaces. Finally the blob edges tended to get twisted when they impacted the environment at high speed.
The first problem (instability) struck me as a bit odd, since Verlet integration is known for being a bit more stable than Euler integration. This problem had me scratching my head for a while, but I finally figured out that it was due to the order in which I was performing the updates. I was looping over all the points, gathering the forces for a point (from the springs) and then moving the point.
The problem with that was that when a point moved, the force it applied to another point via a spring would change. In the case of two points connected by a single spring, the force exerted by the spring should be symmetrical for each point. However, if you move one point before gathering the force for the second point, then the forces will be different. This causes the spring system to have a net force imbalance in a particular direction (depending on the order of update). The solution here was very simple. I just split the loop up into two separate loops: one to gather the forces, and then one to apply them in the integration step. This ensured that all forces were symmetrical.
The second problem (getting stuck) has to do with the way collisions are handled. Since the collision of a point is implicit in its last movement, then if a collision resolution causes a point not to move very much, then it effectively kills its velocity. For collision resolution of a single point mass to work correctly (i.e. bounce off the surface), the next movement must be of appropriate magnitude and direction so future movement is correct. However, we are not simulating points; we are simulating a blob, so we need to consider the movement of the system as a whole.
With a spring mass system, the compression of the springs can handle the bouncing (to a certain degree). So if the leading edge points of a spring mass system simply stop when they hit a wall, the springs connecting to the points behind them will be compressed, and eventually bounce the whole blob off the wall in a nice convincing manner.
This works fine for something that just bounces up and down, but something hitting a surface at an angle needs to slide along the wall. This was quite easily accomplished with point/surface collisions by simply allowing the point the move parallel to the wall by the distance it would have originally traveled.
Something similar was done with line/surface collisions, but instead of the points moving parallel to the surface, they move parallel to the line. This allows the blob to slide over corners.
These collision resolutions were also where I implemented friction, simply scaling the distanced moved by a constant (like 0.95) gives a relatively pleasing result. You could calculate a friction force to be applied the next frame, but it’s simpler to directly incorporate it into the movement calculation. In the demo the friction can be altered by holding “S†to become slippery, and “A†to become less slippery. Holding “S†will allow you to slip though holes faster.
The final problem was edges getting twisted. This generally happened because a point moved furthur past another point it was supposed to keep away from. Since the spring constrain only measures distance, the point is then pushed away by the spring, but in the wrong direction, causing the edge to become twisted. One it’s twisted, it does not become un-twisted by itself.
The simplest solution, and the one I implement in the demo, is to try to never move in large steps. The easiest way of doing this is to run the physics multiple times with a smaller time-step. In the demo I run it six times per frame. Even so, the blobs can get kinks in them if shaken violently.
Something that exacerbates this problem is increasing the number of segments in a blob. With a large number of segments, the skin edges are much shorter, and so more likely to exceed their constraints in a single iteration. A lower number of segments works better. I found a 40 segment blob was impossible to kink, and yet still looked almost as nice as a 80 segment blob that was much more prone to kinking.
Obviously running the physics multiple times is not ideal, as it can be quite expensive. A better solution would be to simply ensure the kinking does not happen in the first place. Perhaps by adding some kind of angular constraint to a point on the surface. Another alternative is to link surface points to their second neighbors with a rigid constraint, so if the point gets past the first neighbor, then the second neighbor will push it back into the correct position. This type of second-neighbor constraint is commonly found in cloth simulation.
RESOURCES
Thomas Jakobsen, Advanced Character Physics, Gamasutra 2001, http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml
Erleben, et al, Physics Based Animation, 2005, Charles River Media, Chapter 8, p265.
Chronic Logic, Gish Demo, http://www.chroniclogic.com/index.htm?gish.htm
Interesting. I note that you wrote an article entitled ‘managed code in games’, Jan 07 (not published on your site yet), where you mentioned that you converted this example to managed code. Are you going to release that code for download as well?
Comment by Washu — February 7, 2007 @ 1:07 pm
It’s the same code (Managed C++, not C#), all I did was specify the /clr option and toggle the few incompatible optimization options.
Comment by Mick West — February 7, 2007 @ 1:47 pm
So you set the /clr compiler flag, and adjusted the incompatible compilation settings (/MT -> /MD)…
That’s really not a valid comparison of managed code performance to unmanaged code performance. While it is true that you will generate IL when you switch to that flag, the IL generated attempts to mirror the patterns and principles that you would use in an unmanaged application, not those of a managed application. If you really wanted to do such a comparison, the least you could have done was rewritten it in C++/CLI, utilizing the .Net framework and design principles behind managed applications. As it is, all you’ve really done is demonstrate why you don’t just turn on /clr wily nily.
What really annoys me is that now developers are going to read this article and will use it as a justification for claiming that managed code is slow, even though the performance metric used was not an appropriate one at all. As with any platform comparison unless you write it for the platform such that both samples utilize the platform as it was meant to be used, the results will be highly biased towards whichever platform the sample’s design favors.
Comment by Washu — February 7, 2007 @ 2:39 pm
Managed code is slow for this type of thing. The code is really very simple, it iterates over a large number of small atomic objects and then perform fairly simple operations on them. That’s all it does. It’s low level code that needs to be compiled in a way that takes advantage of the hardware. “Utilizing the .NET framework” it not going to help.
The whole point of my Managed Code article was that certain core functionality inherent in game engines is not suitable for IL/CLR compilation. It’s not fast enough.
My article is probably viewed as heretical by most game developers. I’m actually encouraging the use of managed code (for non-engine components).
Comment by Mick West — February 7, 2007 @ 4:39 pm
As I’ve already pointed out, your comparison is not valid in the slightest. In case you hadn’t noticed, it was force to convert every piece of the standard library that you touched to IL. It also had to generate a huge number of wrapper and utility functions in order to properly compile your application into IL. Designing the application with managed languages in mind would have avoided all of that and easily increased the performance of the application.
That’s an interesting point, but it’s only a good point if you can back it up with real evidence. The example you’ve shown doesn’t actually utilize the power of managed code, so its not a very good example of what managed code is capable with in those tight inner loops. For example, your code requires the generation of IL for every standard library template instantiation that you’ve used. In the end, the IL generated is not very good at all, with it being forced to generate large numbers of temporary objects and other messy problems. In short, your program is far from an optimal managed application in most aspects.
Yes, and C was also viewed as heretical at one point in time. Then C++ was the next victim. Java didn’t pan out, so it was rightfully regarded as suspect, although even there we can see some large successes in the mobile field. Note the use of scripting languages exploded not too long ago, but even there many regard them as suspect.
Note that I’m not saying that managed code doesn’t have an inherit amount of overhead to it, however the performance overhead that your article implies with its frame-rate comparison is extremely ludicrous.
Comment by Washu — February 7, 2007 @ 6:06 pm
There’s really only three things going here in my code.
1 – Iterating over various STL Vectors of various abstract classes
2 – Calling a virtual function on each abstract class
3 – Performing a bunch of math and/or some simple collision detection on each object.
Now, I’ll freely admit I don’t know if the first two could have been implemented in some different “managed” way that would have been faster. Quite possibly, and I’d be happy to hear about it. It’s code like:
// apply all the constraintsvoid CVerletPoint::SatisfyConstraints()
{
vector::iterator i;
for (i = mp_constraints.begin(); i != mp_constraints.end(); i++)
{
(*i)->Satisfy(this);
}
}
But I think the code that accounts for much of the slowdown is the actual per-object code that is executed, which is pretty straightforward stuff. Looking at the CLR generated asm, you get a lot of memory accesses, and you don’t get the SSE2 optimization (the two things probably being somewhat related, with SSE2 giving you a lot more registers to play with).
Again, the intent of my article was to encourage people to use managed code. I’m all for it. But the best way is for them to use it where the performance overheads are not an issue. Eventually the balance will shift and more and more code will be managed. But right now, the CLR compiler was just not doing a good job.
Comment by Mick West — February 7, 2007 @ 9:03 pm
To give you an idea of how bad just compiling it with /clr is, here’s that SAME code as the CLR sees it:
public private: static void __gc* modopt(System::Runtime::CompilerServices::CallConvThiscall __gc*) CVerletPoint::SatisfyConstraints(CVerletPoint __gc** modopt(System::Runtime::CompilerServices::IsConst __gc*) modopt(System::Runtime::CompilerServices::IsConst __gc*) local6){
std::_Vector_iterator > __gc* t *> >1;
CVerletPoint __gc** modopt(System::Runtime::CompilerServices::IsConst __gc*) modopt(System::Runtime::CompilerServices::IsConst __gc*) local3 = (local6 + 28);
std::vector > __gc** modopt(System::Runtime::CompilerServices::IsConst __gc*) modopt(System::Runtime::CompilerServices::IsConst __gc*) local2 = local3;
CVerletConstraint __gc*** constraintPtrPtr2 = local2[4];
if (constraintPtrPtr2 > local2[8])
{
::_invalid_parameter_noinfo();
}
*(*static_cast(&t *> >1)) = local2;
*(*static_cast((&t *> >1 + 4))) = constraintPtrPtr2;
std::_Vector_iterator > __gc* t *> >2 = t *> >1;
std::vector > __gc** modopt(System::Runtime::CompilerServices::IsConst __gc*) modopt(System::Runtime::CompilerServices::IsConst __gc*) local1 = local3;
std::vector > __gc** modopt(System::Runtime::CompilerServices::IsConst __gc*) modopt(System::Runtime::CompilerServices::IsConst __gc*) local5 = (local1 + 4);
std::vector > __gc** modopt(System::Runtime::CompilerServices::IsConst __gc*) modopt(System::Runtime::CompilerServices::IsConst __gc*) local4 = (local1 + 8);
while (true)
{
CVerletConstraint __gc*** constraintPtrPtr1 = local4[0];
if (local5[0] > constraintPtrPtr1)
{
::_invalid_parameter_noinfo();
}
if ((*(*static_cast(&t *> >2)) == 0) || (*(*static_cast(&t *> >2)) != local1))
{
::_invalid_parameter_noinfo();
}
if (*static_cast((*static_cast((*(*static_cast((&t *> >2 + 4))) == constraintPtrPtr1)) == 0)) == 0)
{
return;
}
if (*(*static_cast(&t *> >2)) == 0)
{
::_invalid_parameter_noinfo();
}
System::Int32 __gc* num2 = (*(*static_cast(&t *> >2)) + 8);
if (*(*static_cast((&t *> >2 + 4))) >= num2[0])
{
::_invalid_parameter_noinfo();
}
System::Int32 __gc* num1 = *(*(*static_cast((&t *> >2 + 4))));
**(*(num1))(num1, local6);
if (*(*static_cast((&t *> >2 + 4))) >= num2[0])
{
::_invalid_parameter_noinfo();
}
*(*static_cast((&t *> >2 + 4))) += 4;
}
}
The equivelent system (mostly, I’m still trying to dig through this horrible mess you call code) in MC++
public: void __gc* SatisfyConstraint(){
foreach (Kent::VerletSample::VerletConstraint __gc* constraint1 in this->constraints)
{
constraint1->Satisfy(this);
}
}
And, just for comparison, the IL generated for each:
Yours:
.method assembly static void modopt([mscorlib]System.Runtime.CompilerServices.CallConvThiscall) CVerletPoint.SatisfyConstraints(CVerletPoint* modopt([mscorlib]System.Runtime.CompilerServices.IsConst) modopt([mscorlib]System.Runtime.CompilerServices.IsConst)) cil managed
{
.maxstack 3
.locals (
[0] std.vector >* modopt([mscorlib]System.Runtime.CompilerServices.IsConst) modopt([mscorlib]System.Runtime.CompilerServices.IsConst) local1,
[1] std.vector >* modopt([mscorlib]System.Runtime.CompilerServices.IsConst) modopt([mscorlib]System.Runtime.CompilerServices.IsConst) local2,
[2] int32 num1,
[3] int32 num2,
[4] CVerletConstraint** constraintPtrPtr1,
[5] CVerletConstraint** constraintPtrPtr2,
[6] CVerletPoint* modopt([mscorlib]System.Runtime.CompilerServices.IsConst) modopt([mscorlib]System.Runtime.CompilerServices.IsConst) local3,
[7] std.vector >* modopt([mscorlib]System.Runtime.CompilerServices.IsConst) modopt([mscorlib]System.Runtime.CompilerServices.IsConst) local4,
[8] std.vector >* modopt([mscorlib]System.Runtime.CompilerServices.IsConst) modopt([mscorlib]System.Runtime.CompilerServices.IsConst) local5,
[9] std._Vector_iterator > t *> >1,
[10] std._Vector_iterator > t *> >2)
L_0000: ldarg.0
L_0001: ldc.i4.s 28
L_0003: add
L_0004: stloc.s local3
L_0006: ldloc.s local3
L_0008: stloc.1
L_0009: ldloc.1
L_000a: ldc.i4.4
L_000b: add
L_000c: ldind.i4
L_000d: stloc.s constraintPtrPtr2
L_000f: ldloc.s constraintPtrPtr2
L_0011: ldloc.1
L_0012: ldc.i4.8
L_0013: add
L_0014: ldind.i4
L_0015: ble.un.s L_001c
L_0017: call void modopt([mscorlib]System.Runtime.CompilerServices.CallConvCdecl) ::_invalid_parameter_noinfo()
L_001c: ldloca.s t *> >1
L_001e: ldloc.1
L_001f: stind.i4
L_0020: ldloca.s t *> >1
L_0022: ldc.i4.4
L_0023: add
L_0024: ldloc.s constraintPtrPtr2
L_0026: stind.i4
L_0027: ldloc.s t *> >1
L_0029: stloc.s t *> >2
L_002b: ldloc.s local3
L_002d: stloc.0
L_002e: ldloc.0
L_002f: ldc.i4.4
L_0030: add
L_0031: stloc.s local5
L_0033: ldloc.0
L_0034: ldc.i4.8
L_0035: add
L_0036: stloc.s local4
L_0038: ldloc.s local4
L_003a: ldind.i4
L_003b: stloc.s constraintPtrPtr1
L_003d: ldloc.s local5
L_003f: ldind.i4
L_0040: ldloc.s constraintPtrPtr1
L_0042: ble.un.s L_0049
L_0044: call void modopt([mscorlib]System.Runtime.CompilerServices.CallConvCdecl) ::_invalid_parameter_noinfo()
L_0049: ldloca.s t *> >2
L_004b: ldind.i4
L_004c: brfalse.s L_0054
L_004e: ldloca.s t *> >2
L_0050: ldind.i4
L_0051: ldloc.0
L_0052: beq.s L_0059
L_0054: call void modopt([mscorlib]System.Runtime.CompilerServices.CallConvCdecl) ::_invalid_parameter_noinfo()
L_0059: ldloca.s t *> >2
L_005b: ldc.i4.4
L_005c: add
L_005d: ldind.i4
L_005e: ldloc.s constraintPtrPtr1
L_0060: ceq
L_0062: conv.u1
L_0063: ldc.i4.0
L_0064: ceq
L_0066: conv.u1
L_0067: brfalse.s L_00b4
L_0069: ldloca.s t *> >2
L_006b: ldind.i4
L_006c: brtrue.s L_0073
L_006e: call void modopt([mscorlib]System.Runtime.CompilerServices.CallConvCdecl) ::_invalid_parameter_noinfo()
L_0073: ldloca.s t *> >2
L_0075: ldind.i4
L_0076: ldc.i4.8
L_0077: add
L_0078: stloc.3
L_0079: ldloca.s t *> >2
L_007b: ldc.i4.4
L_007c: add
L_007d: ldind.i4
L_007e: ldloc.3
L_007f: ldind.i4
L_0080: blt.un.s L_0087
L_0082: call void modopt([mscorlib]System.Runtime.CompilerServices.CallConvCdecl) ::_invalid_parameter_noinfo()
L_0087: ldloca.s t *> >2
L_0089: ldc.i4.4
L_008a: add
L_008b: ldind.i4
L_008c: ldind.i4
L_008d: stloc.2
L_008e: ldloc.2
L_008f: ldarg.0
L_0090: ldloc.2
L_0091: ldind.i4
L_0092: ldind.i4
L_0093: calli method unmanaged thiscall void modopt([mscorlib]System.Runtime.CompilerServices.CallConvThiscall) *(native int, CVerletPoint*)
L_0098: ldloca.s t *> >2
L_009a: ldc.i4.4
L_009b: add
L_009c: ldind.i4
L_009d: ldloc.3
L_009e: ldind.i4
L_009f: blt.un.s L_00a6
L_00a1: call void modopt([mscorlib]System.Runtime.CompilerServices.CallConvCdecl) ::_invalid_parameter_noinfo()
L_00a6: ldloca.s t *> >2
L_00a8: ldc.i4.4
L_00a9: add
L_00aa: ldloca.s t *> >2
L_00ac: ldc.i4.4
L_00ad: add
L_00ae: ldind.i4
L_00af: ldc.i4.4
L_00b0: add
L_00b1: stind.i4
L_00b2: br.s L_0038
L_00b4: ret
}
Mine:
.method public hidebysig instance void SatisfyConstraint() cil managed
{
.maxstack 2
.locals init (
[0] Kent.VerletSample.VerletConstraint constraint1,
[1] [mscorlib]System.Collections.Generic.List`1/Enumerator enumerator1,
[2] bool flag1)
L_0000: nop
L_0001: nop
L_0002: ldarg.0
L_0003: ldfld [mscorlib]System.Collections.Generic.List`1 Kent.VerletSample.VerletPoint::constraints
L_0008: callvirt instance [mscorlib]System.Collections.Generic.List`1/Enumerator [mscorlib]System.Collections.Generic.List`1::GetEnumerator()
L_000d: stloc.1
L_000e: br.s L_0022
L_0010: ldloca.s enumerator1
L_0012: call instance !0 [mscorlib]System.Collections.Generic.List`1/Enumerator::get_Current()
L_0017: stloc.0
L_0018: nop
L_0019: ldloc.0
L_001a: ldarg.0
L_001b: callvirt instance void Kent.VerletSample.VerletConstraint::Satisfy(Kent.VerletSample.VerletPoint)
L_0020: nop
L_0021: nop
L_0022: ldloca.s enumerator1
L_0024: call instance bool [mscorlib]System.Collections.Generic.List`1/Enumerator::MoveNext()
L_0029: stloc.2
L_002a: ldloc.2
L_002b: brtrue.s L_0010
L_002d: leave.s L_003e
L_002f: ldloca.s enumerator1
L_0031: constrained [mscorlib]System.Collections.Generic.List`1/Enumerator
L_0037: callvirt instance void [mscorlib]System.IDisposable::Dispose()
L_003c: nop
L_003d: endfinally
L_003e: nop
L_003f: ret
.try L_000e to L_002f finally handler L_002f to L_003e
}
Can you see my point now? Your code does not translate nicely into a managed environment because it does not utilize managed methodologies. Of course its going to perform horribly. That type of a mess is all throughout the entire code base.
Now, I don’t expect people to make the next HL2 in managed code, at this point in time that’s not a realistic goal, that extra 10% that managed code ACTUALLY costs you (which is actually even misleading, because many managed methodologies are faster than their unmanaged counterparts) can sometimes make the difference. But in reality, that 10% for most games isn’t that important. Especially with the current trend of pushing rediculous graphics and little to no story/ai/playability.
Comment by Washu — February 7, 2007 @ 10:04 pm
Okay, so I just recompiled a messy C++ tech demo with /clr, and that’s not representative of what I would have got had I recoded the entire thing in a managed language. This greatly inflated the drop in framerate, and might put some people off looking at using managed code in games. Sorry about that.
Are you re-writing the whole thing? I’d be interested to see what happens.
Other people agree with you:
http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1160556&SiteID=1
So my example was off the mark. But the gist of the article still stands. Managed code is great for rapid development, it’s more solid and maintainable. Some games can be written entirely in managed code since performance is not always an issue. Game engine components suffer some degradation in performance with the current CLR, but you can divided up your code into managed and unmanaged parts if this is an issue.
Another relevant quote (and a very interesting page in general, with good links):
http://blogs.msdn.com/netcfteam/archive/2006/12/22/managed-code-performance-on-xbox-360-for-the-xna-framework-1-0.aspx
I asked someone in the Microsoft Game Technology group if they agreed with the way I split the tasks and he said:
Side note: the Managed Code article is available online in the sample Game Developer:
http://gamedeveloper.texterity.com/gamedeveloper/sample/?pg=41
Comment by Mick West — February 8, 2007 @ 8:31 am
And regarding that IL you posted above, a good part of that is the STL parameter checking which is really inappropriate for optimized release mode code in this type of application, and can be removed with:
#define _SECURE_SCL 0
The resultant IL then looks like:
ldloca.s 2 ; _i$
ldarg.0 ; _this$
ldc.i4.s 32 ; i32 0x20
add
ldind.i4
stind.i4
ldarg.0 ; _this$
ldc.i4.s 36 ; i32 0x24
add
stloc.1 ; $T98077
$LL20@SatisfyCon:
ldloca.s 2 ; _i$
ldind.i4
ldloc.1 ; $T98077
ldind.i4
ceq
conv.u1
ldc.i.0 0 ; u8 0x0
ceq
conv.u1
brfalse.s $LN1@SatisfyCon
ldloca.s 2 ; _i$
ldind.i4
ldind.i4
stloc.0
ldloc.0
ldarg.0 ; _this$
ldloc.0
ldind.i4
ldind.i4
calli D:V(II)
ldloca.s 2 ; _i$
ldloca.s 2 ; _i$
ldind.i4
ldc.i.4 4 ; i32 0x4
add
stind.i4
br.s $LL20@SatisfyCon
$LN1@SatisfyCon:
ret
Which on first glance looks like it might be simpler than your version (longer, but no system calls).
This made the /clr version go from 50fps to 60fps, and the unmanaged version from 150fps to
180. Woot. But still the same slowdown for managed vs. unmanaged.
I think I’ll look into this a bit more and see what is going on.
Comment by Mick West — February 8, 2007 @ 10:49 am
Okay, I feel that the above shows that the iteration overhead is not as great as I might have though. Now much of my code is doing floating point vector calculations like this:
Vector2 CSemiRigidConstraint::GetForce(CVerletPoint* p_verlet)
{
Vector2 to_me = p_verlet->GetPos() - mp_other_verlet->GetPos();
if (to_me.Length() < 0.000001) { to_me = Vector2(1.0f,0.0f); } Vector2 mid = mp_other_verlet->GetPos() + to_me.Normal()*m_mid;
Vector2 to_mid = mid-p_verlet->GetPos() ;
return to_mid*m_force;
}
Which in my unmanaged version compiles as:
Vector2 CSemiRigidConstraint::GetForce(CVerletPoint* p_verlet)
{
004062F0 push ebp
004062F1 mov ebp,esp
004062F3 and esp,0FFFFFFF8h
Vector2 to_me = p_verlet->GetPos() - mp_other_verlet->GetPos();
004062F6 mov edx,dword ptr [ebp+0Ch]
004062F9 mov eax,dword ptr [ecx+4]
004062FC movss xmm0,dword ptr [eax]
00406300 movss xmm1,dword ptr [eax+4]
00406305 movss xmm4,dword ptr [edx]
00406309 movss xmm5,dword ptr [edx+4]
if (to_me.Length() < 0.000001) 0040630E xorps xmm6,xmm6 00406311 movaps xmm2,xmm4 00406314 subss xmm2,xmm0 00406318 movaps xmm3,xmm5 0040631B subss xmm3,xmm1 0040631F movaps xmm0,xmm3 00406322 mulss xmm0,xmm3 00406326 movaps xmm1,xmm2 00406329 mulss xmm1,xmm2 0040632D addss xmm0,xmm1 00406331 movsd xmm1,mmword ptr [__real@3eb0c6f7a0b5ed8d (418060h)] 00406339 sqrtss xmm0,xmm0 0040633D sub esp,8 00406340 cvtps2pd xmm0,xmm0 00406343 comisd xmm1,xmm0 00406347 movss xmm1,dword ptr [__real@3f800000 (41803Ch)] 0040634F jbe CSemiRigidConstraint::GetForce+67h (406357h) { to_me = Vector2(1.0f,0.0f); 00406351 movaps xmm2,xmm1 00406354 movaps xmm3,xmm6 } Vector2 mid = mp_other_verlet->GetPos() + to_me.Normal()*m_mid;
00406357 movaps xmm0,xmm3
0040635A mulss xmm0,xmm3
0040635E movaps xmm7,xmm2
00406361 mulss xmm7,xmm2
00406365 addss xmm0,xmm7
00406369 sqrtss xmm0,xmm0
0040636D comiss xmm0,xmm6
00406370 jbe CSemiRigidConstraint::GetForce+93h (406383h)
00406372 divss xmm1,xmm0
00406376 movaps xmm0,xmm1
00406379 mulss xmm0,xmm2
0040637D mulss xmm1,xmm3
00406381 jmp CSemiRigidConstraint::GetForce+9Eh (40638Eh)
00406383 movss xmm1,dword ptr [esp+4]
00406389 movss xmm0,dword ptr [esp]
0040638E movss xmm2,dword ptr [ecx+0Ch]
00406393 mulss xmm1,xmm2
00406397 mulss xmm0,xmm2
0040639B movss xmm2,dword ptr [eax+4]
004063A0 movaps xmm3,xmm1
004063A3 movss xmm1,dword ptr [eax]
Vector2 to_mid = mid-p_verlet->GetPos() ;
return to_mid*m_force;
004063A7 mov eax,dword ptr [ebp+8]
004063AA addss xmm1,xmm0
004063AE addss xmm2,xmm3
004063B2 movaps xmm0,xmm4
004063B5 subss xmm1,xmm0
004063B9 movss xmm0,dword ptr [ecx+14h]
004063BE movaps xmm3,xmm5
004063C1 subss xmm2,xmm3
004063C5 mulss xmm1,xmm0
004063C9 mulss xmm2,xmm0
004063CD movss dword ptr [eax],xmm1
004063D1 movss dword ptr [eax+4],xmm2
}
004063D6 mov esp,ebp
004063D8 pop ebp
004063D9 ret 8
Now that’s using SIMD extensions, we we can’t in CLR, so let’s turn them off:
Vector2 CSemiRigidConstraint::GetForce(CVerletPoint* p_verlet)
{
Vector2 to_me = p_verlet->GetPos() - mp_other_verlet->GetPos();
00405860 mov edx,dword ptr [ecx+4]
00405863 fld dword ptr [edx]
00405865 sub esp,8
00405868 fld dword ptr [edx+4]
0040586B push esi
0040586C mov esi,dword ptr [esp+14h]
00405870 fld dword ptr [esi]
00405872 fsubrp st(2),st
00405874 fsubr dword ptr [esi+4]
if (to_me.Length() < 0.000001) 00405877 fld st(0) 00405879 fmul st,st(1) 0040587B fld st(2) 0040587D fmul st,st(3) 0040587F faddp st(1),st 00405881 fsqrt 00405883 fcomp qword ptr [__real@3eb0c6f7a0b5ed8d (414508h)] 00405889 fnstsw ax 0040588B fld1 0040588D test ah,5 00405890 fldz 00405892 jp CSemiRigidConstraint::GetForce+46h (4058A6h) { to_me = Vector2(1.0f,0.0f); 00405894 fstp st(3) 00405896 fstp st(1) 00405898 fld st(0) 0040589A fld st(2) 0040589C fxch st(1) 0040589E fxch st(3) 004058A0 fxch st(1) 004058A2 fxch st(2) 004058A4 fxch st(1) } Vector2 mid = mp_other_verlet->GetPos() + to_me.Normal()*m_mid;
004058A6 fld st(2)
004058A8 fmul st,st(3)
004058AA fld st(4)
004058AC fmul st,st(5)
004058AE faddp st(1),st
004058B0 fsqrt
004058B2 fcom st(1)
004058B4 fnstsw ax
004058B6 fstp st(1)
004058B8 test ah,41h
004058BB jne CSemiRigidConstraint::GetForce+67h (4058C7h)
004058BD fdivp st(1),st
004058BF fld st(0)
004058C1 fmulp st(3),st
004058C3 fmulp st(1),st
004058C5 jmp CSemiRigidConstraint::GetForce+77h (4058D7h)
004058C7 fstp st(0)
004058C9 fstp st(2)
004058CB fstp st(0)
004058CD fstp st(0)
004058CF fld dword ptr [esp+4]
004058D3 fld dword ptr [esp+8]
004058D7 fld dword ptr [ecx+0Ch]
Vector2 to_mid = mid-p_verlet->GetPos() ;
return to_mid*m_force;
004058DA mov eax,dword ptr [esp+10h]
004058DE fmul st(2),st
004058E0 fmulp st(1),st
004058E2 fld dword ptr [edx]
004058E4 faddp st(2),st
004058E6 fadd dword ptr [edx+4]
004058E9 fld dword ptr [esi]
004058EB fld dword ptr [esi+4]
004058EE pop esi
004058EF fxch st(3)
004058F1 fsubrp st(1),st
004058F3 fxch st(1)
004058F5 fsubrp st(2),st
004058F7 fld dword ptr [ecx+14h]
004058FA fmul st(1),st
004058FC fxch st(1)
004058FE fstp dword ptr [eax]
00405900 fmulp st(1),st
00405902 fstp dword ptr [eax+4]
}
00405905 add esp,8
00405908 ret 8
Similar size, just doing the FP on the FP stack rather than in SIMD registers
Now look at the /clr version:
Vector2 CSemiRigidConstraint::GetForce(CVerletPoint* p_verlet)
{
Vector2 to_me = p_verlet->GetPos() - mp_other_verlet->GetPos();
00000000 push ebp
00000001 mov ebp,esp
00000003 push edi
00000004 push esi
00000005 push ebx
00000006 sub esp,94h
0000000c mov esi,ecx
0000000e mov edi,edx
00000010 cmp dword ptr ds:[006C2DC8h],0
00000017 je 0000001E
00000019 call 78DE2926
0000001e fldz
00000020 fstp dword ptr [ebp-10h]
00000023 xor ebx,ebx
00000025 fldz
00000027 fstp dword ptr [ebp-14h]
0000002a fldz
0000002c fstp dword ptr [ebp-18h]
0000002f fldz
00000031 fstp dword ptr [ebp-1Ch]
00000034 fldz
00000036 fstp dword ptr [ebp-20h]
00000039 fldz
0000003b fstp dword ptr [ebp-24h]
0000003e xor edx,edx
00000040 mov dword ptr [ebp-28h],edx
00000043 xor edx,edx
00000045 mov dword ptr [ebp-2Ch],edx
00000048 fldz
0000004a fstp dword ptr [ebp-30h]
0000004d fldz
0000004f fstp dword ptr [ebp-34h]
00000052 fldz
00000054 fstp dword ptr [ebp-38h]
00000057 fldz
00000059 fstp dword ptr [ebp-3Ch]
0000005c fldz
0000005e fstp dword ptr [ebp-40h]
00000061 fldz
00000063 fstp dword ptr [ebp-44h]
00000066 fldz
00000068 fstp dword ptr [ebp-48h]
0000006b fldz
0000006d fstp dword ptr [ebp-4Ch]
00000070 fldz
00000072 fstp dword ptr [ebp-50h]
00000075 fldz
00000077 fstp dword ptr [ebp-54h]
0000007a mov eax,dword ptr [esi+4]
0000007d mov dword ptr [ebp-2Ch],eax
00000080 mov eax,dword ptr [ebp-2Ch]
00000083 mov dword ptr [ebp-28h],eax
00000086 mov eax,dword ptr [ebp-28h]
00000089 fld dword ptr [eax]
0000008b fstp dword ptr [ebp+FFFFFF7Ch]
00000091 mov eax,dword ptr [ebp-28h]
00000094 fld dword ptr [eax+4]
00000097 fstp dword ptr [ebp-80h]
0000009a mov eax,dword ptr [ebp+8]
0000009d fld dword ptr [eax]
0000009f fstp dword ptr [ebp-7Ch]
000000a2 mov eax,dword ptr [ebp+8]
000000a5 fld dword ptr [eax+4]
000000a8 fstp dword ptr [ebp-78h]
000000ab fld dword ptr [ebp-7Ch]
000000ae fsub dword ptr [ebp+FFFFFF7Ch]
000000b4 fstp dword ptr [ebp-24h]
000000b7 fld dword ptr [ebp-78h]
000000ba fsub dword ptr [ebp-80h]
000000bd fstp dword ptr [ebp-20h]
000000c0 fld dword ptr [ebp-24h]
000000c3 fstp dword ptr [ebp-74h]
000000c6 fld dword ptr [ebp-20h]
000000c9 fstp dword ptr [ebp-70h]
if (to_me.Length() < 0.000001) 000000cc fld dword ptr [ebp-20h] 000000cf fmul st,st(0) 000000d1 fld dword ptr [ebp-24h] 000000d4 fmul st,st(0) 000000d6 faddp st(1),st 000000d8 fstp dword ptr [ebp-54h] 000000db fld dword ptr [ebp-54h] 000000de fsqrt 000000e0 fstp qword ptr [ebp+FFFFFF74h] 000000e6 fld qword ptr [ebp+FFFFFF74h] 000000ec fstp dword ptr [ebp+FFFFFF68h] 000000f2 fld dword ptr [ebp+FFFFFF68h] 000000f8 fstp qword ptr [ebp+FFFFFF60h] 000000fe fld qword ptr [ebp+FFFFFF60h] 00000104 fld qword ptr ds:[012AFBD0h] 0000010a fcomip st,st(1) 0000010c fstp st(0) 0000010e jp 0000011C 00000110 jbe 0000011C { to_me = Vector2(1.0f,0.0f); 00000112 fld1 00000114 fstp dword ptr [ebp-74h] 00000117 fldz 00000119 fstp dword ptr [ebp-70h] } Vector2 mid = mp_other_verlet->GetPos() + to_me.Normal()*m_mid;
0000011c fld dword ptr [ebp-70h]
0000011f fmul st,st(0)
00000121 fld dword ptr [ebp-74h]
00000124 fmul st,st(0)
00000126 faddp st(1),st
00000128 fstp dword ptr [ebp-50h]
0000012b fld dword ptr [ebp-50h]
0000012e fsqrt
00000130 fstp qword ptr [ebp+FFFFFF6Ch]
00000136 fld qword ptr [ebp+FFFFFF6Ch]
0000013c fstp dword ptr [ebp-1Ch]
0000013f fld dword ptr [ebp-1Ch]
00000142 fldz
00000144 fcomip st,st(1)
00000146 fstp st(0)
00000148 jp 00000168
0000014a jae 00000168
0000014c fld dword ptr [ebp-1Ch]
0000014f fld1
00000151 fdivrp st(1),st
00000153 fstp dword ptr [ebp-18h]
00000156 fld dword ptr [ebp-18h]
00000159 fmul dword ptr [ebp-74h]
0000015c fstp dword ptr [ebp-6Ch]
0000015f fld dword ptr [ebp-18h]
00000162 fmul dword ptr [ebp-70h]
00000165 fstp dword ptr [ebp-68h]
00000168 fld dword ptr [esi+0Ch]
0000016b fstp dword ptr [ebp-14h]
0000016e fld dword ptr [ebp-6Ch]
00000171 fmul dword ptr [ebp-14h]
00000174 fstp dword ptr [ebp-4Ch]
00000177 fld dword ptr [ebp-68h]
0000017a fmul dword ptr [ebp-14h]
0000017d fstp dword ptr [ebp-48h]
00000180 mov ebx,dword ptr [ebp-2Ch]
00000183 fld dword ptr [ebx]
00000185 fstp dword ptr [ebp-64h]
00000188 fld dword ptr [ebx+4]
0000018b fstp dword ptr [ebp-60h]
0000018e fld dword ptr [ebp-64h]
00000191 fadd dword ptr [ebp-4Ch]
00000194 fstp dword ptr [ebp-44h]
00000197 fld dword ptr [ebp-60h]
0000019a fadd dword ptr [ebp-48h]
0000019d fstp dword ptr [ebp-40h]
Vector2 to_mid = mid-p_verlet->GetPos() ;
000001a0 mov eax,dword ptr [ebp+8]
000001a3 fld dword ptr [eax]
000001a5 fstp dword ptr [ebp-5Ch]
000001a8 mov eax,dword ptr [ebp+8]
000001ab fld dword ptr [eax+4]
000001ae fstp dword ptr [ebp-58h]
000001b1 fld dword ptr [ebp-44h]
000001b4 fsub dword ptr [ebp-5Ch]
000001b7 fstp dword ptr [ebp-3Ch]
000001ba fld dword ptr [ebp-40h]
000001bd fsub dword ptr [ebp-58h]
000001c0 fstp dword ptr [ebp-38h]
return to_mid*m_force; //
000001c3 fld dword ptr [esi+14h]
000001c6 fstp dword ptr [ebp-10h]
000001c9 fld dword ptr [ebp-3Ch]
000001cc fmul dword ptr [ebp-10h]
000001cf fstp dword ptr [ebp-34h]
000001d2 fld dword ptr [ebp-38h]
000001d5 fmul dword ptr [ebp-10h]
000001d8 fstp dword ptr [ebp-30h]
000001db fld dword ptr [ebp-34h]
000001de fstp dword ptr [edi]
000001e0 fld dword ptr [ebp-30h]
000001e3 fstp dword ptr [edi+4]
000001e6 mov eax,edi
000001e8 lea esp,[ebp-0Ch]
000001eb pop ebx
000001ec pop esi
000001ed pop edi
000001ee pop ebp
000001ef ret 4
Even just glancing over it, it look like it would take twice as long, possible more depending on the memory cache situation. Is this just bad CLR compiling, or am I doing something wrong?
Comment by Mick West — February 8, 2007 @ 11:27 am
I do appologize for the spam. It would appear that there is a limit to the length of a reply I can send, so I’ve moved the comparisons off to a file on my site.
It’s a bit of both, in reality. The CLR can’t currently take good advantage of SIMD instructions yet, so that’s obviously a ding against it. But the C++/CLI compiler is not the brightest when dealing with doing an unmanaged -> managed conversion.
The above contains a naïve implementation of your function, on the left. It is significantly shorter than the one above that the C++/CLI compiler generated, still not that great though. So what kinds of problems are there? Well, there is a lot of excessive copying. Operators like – generate temporaries…so if we write like a managed person in a performant environment would, mind you, not completely sacrificing readability…which you can see on the right.
Mind you, i could get the right one down to about the same size of yours, without SIMD benefits, but it sacrifices readability.
Comment by Washu — February 8, 2007 @ 1:57 pm
I take it your code got chopped off at the <, maybe not closing both your <code;> tags?
But I get your point, you can massage the code using what are essentially intrinsics, to get the JIT compiler to spit out code that equals or betters the performance of native compiled C++ code (at least in a straightforward situation like this).
There are a number of calls in your code, which helps make it shorter. Of course size is not so important here – it’s how fast it runs.
And it seems a little counterintuitive, to be having to hack away at code to massage the resultant assembly.
Comment by Mick West — February 8, 2007 @ 2:13 pm
And now I’ve seen your whole code (nice comparison BTW), it’s still 10% longer than the non-SIMD version, plus it calls functions for Magnitude, adding and subtracting. Whereas the C++ version just calls sqrtf, ect. I don’t know what’s in those functions, but I highly suspect at least another ten lines of asm per function, possibly more.
But how fast does it run?
Comment by Mick West — February 8, 2007 @ 2:21 pm
Actually, its not so much to hack it to make the assembly nice. Its a difference in how various types are treated.
ValueType’s in .Net are a copy based mechanism, much like they are in other languages. Anything marked with the struct type in C# is considered to be a value type. Making it a class will not solve the problem though (actually, it makes it worse, but I’ll detail why in a bit). Since value-types are primarily a copy mechanism (the old immutable idea) then you’ve got to account for that in your code. Things like taking a reference to the value type (pass by-ref or as an out parameter) enable the CLR to realize how you are attempting to use these various objects, enabling it to eliminate redundant copies and the like. The JIT has very little time to run in, and so its not going to make the best decisions always (it does make a lot of smart ones though).
Classes don’t solve the problem because they hare heap only. You cannot allocate a non-heap based class, as such the allocation of a class type will lead to a GC eventually. Now, Gen0 collections are INSANELY fast, but if you’re pumping out a lot of short lived temporaries, what will happen is that some objects will live a bit longer, and get pushed into the Gen1 collection. Then when the Gen1 collection gets full, it will also be collected, and those short lived temps will be released, but any that live just a bit longer could end up being pushed up into gen2. Gen2 takes a long time to free up, especially with the LOH being up there in the Gen2 as well. So obviously short lived temporaries can cost you…if you’re not careful.
But, its not all horror stories, a gen0 collection is INSANELY fast, as I mentioned above, a wee bit of profiling on my part found it to be faster than a C++ allocation on a moderately fragmented heap. Since most C++ allocators use a heap walk to find a free chunk of memory to allocation (this is unspecified in the standard, as such not all implementations have to behave this way), that traversal can become quite expensive. With managed languages however, an allocation is a constant time operation. The GC will typically do a sweep and compact when a gen2 or gen1 collection happens, but in general, gen0 collections rarely have such actions. Plus, the GC typically doesn’t have to freeze your application[1].
You have to watch out for finalizers though, since destruction is not a deterministic action, finalizers can cause short lived elements to be pushed into the Gen1 heap, when they are really just waiting to be finalized.
[1] Using GC Efficiently – Part 1
Using GC Efficiently – Part 2
Using GC Efficiently – Part 3
[2] Clearing up some confusion over finalization and other areas in GC
Comment by Washu — February 8, 2007 @ 2:27 pm
Indeed, there are ways to get around that too, ways that will generate better/faster code, ways that a professional application would use…such as ngen. Using that pre-JIT the program on the target machine during installation will allow it more time to optimize. How much better it will be, I can’t be sure.
Faster, I don’t have the entire sample done, and probably am not going to complete it either (I have other commitments) but profiling suggests that it is about 5-10% slower than yours (without SIMD).
Which isn’t bad, it is not great, but overall that’s a significant performance boost of compiling with just /clr. Still won’t be able to write a HL2 killer in it, at least not yet. What is interesting are the future JIT compilers that are being invested in by Microsoft. JIT compilers that can optimize based on the machine configuration, something that current statically built applications cannot do. As an example, if you want to use SIMD, you typically have to build in several code-paths. Ones that can use SIMD, and ones that can’t. You then decide (at runtime) which path to take depending on the available features. The disadvantage here is a single level of indirection, and a whole hell of a lot of code on the developer’s part. A well written inner product can easily outperform the SSE generated by VSTS (Visual Studio Team System). Compilers just aren’t good at vectorization, even ones like the Intel compiler (which produces bugs when used, as translation of code to a vectorized format inherently changes the behavior of the application in unpredictable ways.
A more advanced JIT will be able to target the processor that the machine is running on, including hardware extensions, when the application is launched. This presents an opportunity for extreme runtime optimizations based on extended instruction sets. The JIT will still be constrained to a shorter running time than a static compiler, but using tricks like NGEN, you will be able to really optimize it to a great extent.
Comment by Washu — February 8, 2007 @ 2:41 pm
I wrote an “old fashioned” version for kicks:
Vector2 CSemiRigidConstraint::GetForce(CVerletPoint* p_verlet)
{ float v_x = p_verlet->GetPos().x;
float v_y = p_verlet->GetPos().y;
float o_x = mp_other_verlet->GetPos().x;
float o_y = mp_other_verlet->GetPos().y;
float t_x = (v_x - o_x);
float t_y = (v_y - o_y);
float t_len = sqrtf(t_x*t_x + t_y*t_y);
if (t_len <0.000001) // should be f, but leave it for comparison
{
t_x = 1.0f;
t_y = 0.0f;
t_len = 1.0f;
}
float mid = m_mid;
float m_x = o_x + t_x/t_len*mid;
float m_y = o_y + t_y/t_len*mid;
float tm_x = m_x - v_x;
float tm_y = m_y - v_y;
float force = m_force;
return Vector2(tm_x*force,tm_y*force);
}
And here's the comparison.
https://cowboyprogramming.com/code/ComparisonOfManagedOptimizations2.html
And really I should be using the MD part of SIMD, which should be able to halve it again.
So my original example was somewhat misleading. However, when you look at actual engine code, it WILL be optimized to take advantage of the processor architecture, and I suspect based on that then the speed comparisons will be similar to what I was getting.
Comment by Mick West — February 8, 2007 @ 3:03 pm
Yes, I suppose if I really wanted to I could also sacrifice a huge amount of readability to hyperoptimize the managed version. Experience tells me that there are better ways to spend my time though. The 90/10 rule applies even here :)
What I do note is the lack of ‘good’ SIMD in most applications. For instance, the lack of usage of parallelizing of operations. Instead of performing 1 dot product at a time using SIMD, do 4…as in below (note that I do not claim that you should use the code below, just that its typically a better parallelization than single operations)
; Given that XMM0 - XMM7 contain R4 vectors V0 - V7, such that we wish to
; calculate the inner product of and return the results of
; all four inner products in a result vector.
mulps xmm0, xmm1
mulps xmm2, xmm3
haddps xmm0, xmm2
mulps xmm4, xmm5
mulps xmm6, xmm7
haddps xmm4, xmm6
haddps xmm0, xmm4
movaps result, xmm0
Comment by Washu — February 8, 2007 @ 3:21 pm
Better ways to spend 90% of your time, that’s for sure. But I just made my application 8% faster with 15 minutes work (it went from 134 to 123 fps, in non-simd, just with that one change!). Remember what Knuth said about similar optimization:
Your point on “good” SIMD is well taken. I’m from console-land, and if you are doing anything intensive with vectors like this, then you want to be using SIMD (or preferably the vector units).
It’s a period of transition. Managed code is great, but there’s still an appropriate division between game code and engine code. It’s not a hard and fast division, and depends on the game (and several other factors), but it’s still there. As managed code gets better at targeting hardware, then it will get used more.
Comment by Mick West — February 8, 2007 @ 4:07 pm
Simulando "blobs" 2D…
En la web de Mick West hay un interesante tutorial sobre cómo programar blobs (o "goterones viscosos", a falta de un mejor sinónimo) como los que aparecen en juegos como Roco Loco….
Trackback by pixelalo.com — September 10, 2007 @ 7:57 am
Another awesome article, well done. I think this might be good for car tires too (Probably with stiffer springs). They could simulate nice bending, bulging and you could have a really simple traction policy too, traction = GetNumberOfPointsContactingRoad() / nNormalNumberPointsContactingRoad. Keep up the good work.
Comment by Chris — February 22, 2009 @ 1:02 am
Yeah, it probably would work for car tires. However it would also be rather a waste of computing power (and programming time), as the effects would be too slight to see unless you had some kind of “tire cam”. :)
Comment by Mick West — February 22, 2009 @ 7:35 am
Just stumbled on that site, nice articles. I programmed similar physics for a game called Soul Bubbles on the DS. Lots of moving blobs and geometry collisions (typical level 15k points), funny to fit into DS.
You said:
“This causes the spring system to have a net force imbalance in a particular direction (depending on the order of update). The solution here was very simple. I just split the loop up into two separate loops: one to gather the forces, and then one to apply them in the integration step. This ensured that all forces were symmetrical.”
I generally solved this kind of pertubation by inverting the processing order on each update loop (eg: frame n update points to 0 to max, frame n+1 update points max to 0). It is as cache-friendly but allow to avoid iterating the points more than one time for this kind of operation, and generally tends to stabilize the system.
The bubbles in Soul Bubbles are 32 verlet-integrated points to which are applied:
– A single layer of spring constraints ( point N to point N+1%32 ).
– Angle constraints to try to maintain an overall round shape. Applied by moving point N to tend to satisfy an ideal angle between N-1,N,N+1. I don’t recall the details but this proven to be different from applying strings between points N-1 and N+1.
– A slight scaling up of all points from their average center to cope with external pressure when the surface became too small.
– In cases where bubbles gets into thin/sharp objects collisions responses are biased to push points back toward blob center, and friction increased for those points to reduce penetration.
Add in some thresholds to optimize idle cases and various common-sense low level optimization. In the end other components (such as managing the membranes between 2 collides bubbles) were more heavy.
Comment by Omar — October 9, 2009 @ 5:09 am
[…] an excellent article by Mick West all about springs and blobby […]
Pingback by Fun With Springs… | FML — July 20, 2011 @ 6:22 am