September 29th, 2017 | Posted by admin
Categories: Uncategorized | Tags:
Comments Off on Improved Lerp Smoothing.

A Useful Snippet:

A lot of game developers will recognize this line of code:

value = lerp(value, targetValue, 0.1);

It’s super useful, and can be used for all sorts of things. With a higher constant, it’s a good way to smooth out jittery input from a mouse or joystick. With a low constant, it’s a nice way to smoothly animate a progress bar or a camera following a player. It will never overshoot the target value even if it’s changing, and it changes the speed based on how far away it is so it will always quickly converge on the target. Pretty good for a one liner!

BUT!

Unfortunately it has a couple problems that are often ignored. The first is that it’s highly dependent on framerate, but is usually applied per frame anyway. The second is that the lerp constant that you need to use is really hard to control. It’s not uncommon to start adding a lot of zeros to the front of the lerp constant to get the desired smoothing amount. Assuming 60 fps, if you want to move halfway towards an object in a second you need to use a lerp constant of 0.0115. To move halfway in a minute, you need to use 0.000193. On the other end of the spectrum if you use a lerp constant of 0.9 you will run out of 32 floating point precision within 7 frames, and it will be exactly at the target value. That’s a little wacky.

Fortunately, with a little math, both issues are easy to fix.

The Math

Don’t feel bad about skipping this section if you don’t care about the math. The solution at the end works just fine without understanding why. 😉

Think of it another way. Say you are lerping by 0.9 each frame. That means you are leaving (1 - 0.9) = 0.1 = 10% of the remaining value. After 2 frames, there will be (1 - 0.9)*(1 - 0.9) = 0.01 = 1% of the remaining value. After 3, (1 - 0.9)*(1 - 0.9)*(1 - 0.9) = 0.001 = 0.1%. After n frames you’ll have (1 - 0.9)^n of the remaining value. Let’s graph that and see what it looks like.

An exponential curve.

You can see that this example does close in on the target very quickly. Also, since it’s a continuous function, we can figure out what the value between frames would be. This is how you fix the framerate issue, but we’ll get into that more later.

Since floating point numbers have limited precision, you’ll eventually run out and you’ll “arrive” at the target value exactly. Floats can store ~7 significant digits, and doubles ~16. Here’s a quick snippet of Ruby code to test that out.

value = 0.0
target = 1.0
alpha = 0.9
100.times do|i|
  value = (1 - alpha)*value + alpha*target
  puts "#{i + 1}: #{value == target}"
end

And the output?

1: false
2: false
... (more false values)
15: false
16: false
17: true

It shouldn’t be too surprising that precision runs out after the 16th iteration. (1 - 0.9)^17 is quite small. 1e-17 to be exact. That is so small, that in order to store 1 - 1e-17 you would need 17 significant digits, and doubles can only store 16! More interestingly, no matter what your starting and ending values are, it will always run out of precision after 16 iterations. Most game engines use floats instead of doubles, and those can only store ~7 significant digits. So you should expect precision to run out after only the 7th iteration.

What about for other constants? (Keep in mind I’m using doubles, and floats would run out in half as many iterations.) For 0.8 you run out of precision after ~23 iterations, ~53 for 0.5. With constants less than 0.5 it sort of breaks down and something curious can happen. Say you keep lerping with a constant of 0.5. Eventually, you will run out of precision and the next possible floating point number after value will be target. When you try to find the new value half way between, it will cause it to round up to target instead. If you use a constant smaller than 0.5, it will round down to value instead. Instead of “arriving” at target, it will get stuck at the floating point number immediately before it. Interesting, but not all that important since with a few exceptions it’s not a good idea check floating point numbers for equality anyway. Anyway for a constant of 0.4, the value gets stuck at ~70 iterations, or ~332 for 0.1.

So really all you are doing by repeatedly lerping is evaluating an exponential curve. We can use this knowledge both to fix the framerate independence issue, as well as make the values used more reasonable.

Improved Version:

Let’s replace the simple lerp constant with an exponential function that involves time, and see how it works.

// exp() works just as well, probably with little to no measurable performance difference.
value = lerp(target, value, exp2(-rate*deltaTime))

In this version, rate controls how quickly the value converges on the target. With a rate of 1.0, the value will move halfway to the target each second. If you double a rate, the value will move in twice as fast. If you halve the rate, it will move in half as fast. Couldn’t be easier.

Even better, it’s framerate independent. If you lerp this way 60 times with a delta time of 1/60 s, it will be the same result as lerping 30 times with 1/30 s, or once with 1 s. No fixed time step required nor the jittery movement it causes. However, do keep in mind that if your target value is changing over time (such as one object following another) you won’t get the exact same behavior. It’s close enough for many uses though.

Conversion:

So this new version is framerate independent, and easier to tune. Now how do you convert your old lerp() statements into the new ones without changing the smoothing coefficients that already work so well at 60 fps? Math to the rescue again. The following formula will can convert them: rate = -fps*log2(1 - coef). (Note: Use log() instead of log2() if you are using exp() instead of exp2() in your lerp expression.)

Performance:

I’ve never actually tested it! On the other hand, I’ve never run into issues with it. I’m also pretty sure most CPUs have instructions for computing log2() and exp2() nowadays. Computing exp() is only a couple instructions then. Different systems/languages/VMs vary, but I would not worry about it.

Going Further:

I have on few occasions considered going a step further and putting rate on a logarithmic scale too. The advantage is if you are adjusting the rate value through a UI. Halving or doubling a number by typing it in is easy, but not when dragging a slider with the mouse. You would also have to be very careful not to adjust the rate to be negative. Putting it on a logarithmic scale makes the problem go away. Dragging a certain amount to the left would always mean halve the rate, and dragging the same amount to the right would always mean to double the rate.

value = lerp(target, value, exp2(-exp2(logRate)*deltaTime))

February 11th, 2016 | Posted by Andy Korth
Categories: Uncategorized | Tags:
Comments Off on Announcing Verdant Skies

We’ve been busy on a lot of projects lately, including updates to our Super Fast Soft Shadows system, but today I’d like to announce our newest game: Verdant Skies!

Check out our teaser trailer on the Verdant Skies Blog.

And follow us on Twitter or Facebook for regular updates.

June 8th, 2015 | Posted by Andy Korth
Categories: Uncategorized | Tags:
Comments Off on Super Fast Soft Shadow system in progress for Unity

Hi everyone- We’ve started a 2D soft shadow system and we wanted to share some screenshots and in-progress videos of how it’s going. The goals are:

Moving and flickering! Click to embiggen

* Speed on mobile platforms
* High number of colored lights and shadowed objects
* Flexibility in light size and softness of shadows

Super Fast Soft Shadows uses a unique shader based algorithm: Shadow projection occurs inside the vertex shader, not on the CPU.

Shadow mask generation occurs in a single pass – it doesn’t use expensive image filters or pixel shaders to soften the shadows. This means it runs great on mobile!

Physically realistic penumbra, umbra, and antumbra rendering is based on configurable light sizes. This produces accurate rendering when the light source is larger than the objects casting the shadows.

 

Penumbras and Antumbras

It can produce nice, accurate penumbras, and even antumbras when the light source is bigger than the object casting the shadow. This is because we are calculating the actual occlusion percentages when casting the shadows instead of applying some sort of blur or other image based effect. Blurs are incredibly bandwidth intensive, and this is especially a problem on mobile. Even though the occlusion we calculate is per pixel, it’s a pretty short fragment shader and most of the math is done in the vertex shader. You are really just paying for the fillrate to blend the visible parts of the shadow masks and lights.

 

Multiple colors! Click to embiggen

January 15th, 2015 | Posted by Andy Korth
Categories: Uncategorized | Tags:
Comments Off on Chipmunk 7 released- Pro tools open sourced

The Chipmunk 7.0.0 release is complete!

Most notably, we’ve decided to integrate all of the Chipmunk2D Pro into the free and open source version of Chipmunk2D. We want the ARM NEON optimizations and autogeometry code to be in the hands of as many people as possible. This also allows these features to be integrated into popular engines like Cocos2D.

Have fun!

What’s new in 7.0.0:

  • All features from Chipmunk Pro are now free and open source! (threaded and NEON solver, autogeometry)
  • API: Lots of cleanup to the API naming for better consistency.
  • API: Renamed nearest point queries to simply point queries.
  • API: Removed many deprecated functions.
  • API: Struct definitions have become fully opaque instead of mangling names with the CP_PRIVATE() macro.
  • API: Replaced templated accessor functions with concrete ones. Should be simpler to deal with for FFIs.
  • API: Optional automatic mass properties for shapes. Calculates the moment of inertia and center of gravity for you.
  • API: Optional anchor point for bodies that is separate from the center of gravity.
  • API: Added radius parameters to many functions dealing with shapes (moment calculation, initialization, etc).
  • API: The convex hull and winding is automatically calculated when creating a poly shape.
  • API: Added a cpShapesCollide() function to check overlap of arbitrary shapes.
  • API: cpShape filter property to supersede layers and groups.
  • API: Collision handlers now return a collision handler struct to make it simpler to set up callbacks.
  • API: Wildcard collision types.
  • API: The cpArbiterTotalImpulseWithFriction() function was renamed to cpArbiterTotalImpulse(). The old useless cpArbiterTotalImpulse() implementation was removed.
  • API: Contacts now store the colliding point on the surface of both shapes.
  • API: cpArbiterIsRemoval() to check if a separate callback is called due to a removal and not a true separating collision.
  • API: Arbiters now only store one normal per pair of colliding shapes.
  • API: cpBBNewForExtents().
  • API: Added a concrete kinematic body type to replace the confusing “rogue” body concept.
  • API: Added a 2×3 affine transform type, cpTransform.
  • API: Added a new debug rendering API.
  • MISC: Numerous improvements to the collision detection.
  • MISC: cpPolyline structs are passed by reference instead of value. (I’ve regretted that decision for years!)
October 14th, 2013 | Posted by admin
Categories: Uncategorized | Tags:
Comments Off on Chipmunk2D selected as official engine of Cocos2D!
April 24th, 2013 | Posted by Andy Korth
Categories: Uncategorized | Tags:
Comments Off on Chipmunk2D for Unity is in progress

The last few weeks we’ve been working on Chipmunk bindings for Unity! If you’d like to stay up to date on our progress, follow us on Twitter:

http://twitter.com/kortham
http://twitter.com/slembcke

So far we’re finding a lot of challenges, but we’re really trying to go the extra mile to make it feel Unity-ish. And very early performance tests put it simulating over twice as many objects as PhysX, in spite of our need to cross the managed/native barrier each frame for each object!

April 1st, 2013 | Posted by slembcke
Categories: Uncategorized | Tags:
Comments Off on

We had a great time at GDC last week! We ended up meeting a lot of new and interesting people. It’s always great because we can chat with a lot of people who are and are not using Chipmunk to figure out how we can make it even better.

Farewell Chipmunk Physics. Long Live Chipmunk2D!

Chipmunk isn’t going anywhere. Just rebranding a little bit to make it easier to search for. Google for “Chipmunk” and see how much of it is physics related. 😉

This was a suggestion that came up a bit before GDC in a Cocos2D thread, but came up a couple times more when there.

On that note, I’ve set up a new URL, chipmunk2d.net (currently just a redirect), and a new twitter account @chipmunk2d dedicated to Chipmunk stuff. Follow us and help spread the word!

Unity3D support:

I was never quite sure how to make Chipmunk fit in nicely with Unity, so it’s been an idea that sat on the very back burner. After talking with people at GDC, there definitely seems to be a nice niche market for a good 2D physics engine. It seems a lot of people are frustrated trying to get the builtin 3D physics to do 2D nicely. I think with a bunch of custom editor components we can get something pretty close to the simplicity Unity provides now and then sprinkle in some of our own secret Chipmunk sauce to make it even better.

Chipmunk provides a number of nice features that PhysX does not (or at least are not exposed). Since Chipmunk isn’t doing all that extra work for a dimension that is just being thrown away it’s also *much* faster. So we think we can go simpler, faster, and more flexible. Seems like a win/win/win scenario if you want to do 2D physics games.

Better JS Support:

Last year, Joseph Gentle made a fantastic port of Chipmunk to Javascript. He’s also done a great job so far of keeping it up to date so far. I don’t do much Javascript myself, but it’s become so much better recently that I’m excited for the possibilities! I’d love to put some interactive stuff on the Chipmunk website and in the documentation.

Anyway, with Chipmunk-JS becoming a more or less standard part of Cocos2D-JS, I’m going to try and make timely patches for Joseph so he’s not stuck volunteering to port all my changes and fixes.

Simplify Simplify Simplify!

One of my design goals with Chipmunk is to keep the API as simple as it can be without taking away flexibility. I’ve spent a lot of time thinking about how to avoid thresholds, sensitivity to units and other “tuning” factors. I’ve gotten some very nice compliments on it’s simplicity, so I think I’ve probably done OK in that regard. It could be better though! You shouldn’t need to be a physics engine master to make great games using one. Sometimes I lose sight of what it’s like to be a beginner. I’ve got two particular cases in mind. Simplified object creation and a collision only mode.

Creating a physics object in Unity or Box2D is different than Chipmunk. You lay out your collision shapes and they guess the mass, center of gravity and moment of inertia for you. This takes away some flexibility, but it’s also vastly simpler for beginners. I have utility functions in Chipmunk to help out with that, but sometimes people don’t care or need to know what a moment of inertia is to make a good game. It’s just a barrier that gets in their way.

A lot of people want to make a game that needs collision detection, but don’t really care about physics. It’s perfectly possible to do that with Chipmunk now, but it’s certainly not obvious how for a beginner. I could totally build a simpler API on top of Chipmunk to help with this.

Continuous Collision Detection (CCD):

This is related to the previous point. I’ve tried to make Chipmunk’s API as simple as possible and make it so that things “just work” without having to fiddle with thresholds and scales and such. One thing that doesn’t “just work” in Chipmunk is continuous collision detection. I usually sort of brush it off as being unecessary or usually very easy to work around, which is true, but missing my own point. Collisions should “just work” and not be something that you need to worry about as a designer. Erin Catto made that point in his GDC talk on collision detection, and it really struck a chord. The 6.2 beta branch is already a big step in the right direction.

I’ve been sitting on some ideas for mixing pseudo-velocities and speculative contacts for some time. I think it could work really well and solve some of the things I didn’t initially like about speculative contacts. If it works well, it will be awesome. 😀 If not… then I’ll have to go with something more traditional. 🙁

More Tutorial Content:

Documentation, examples, tutorials… There can never be enough! I try to make as much as I can, but it’s very time consuming to do. I met up with Ray Wenderlich and Rod Strougo (They wrote the book “Learning Cocos2D”) at GDC and they sounded pretty interested in working with us to make more of it and get it out where people can see it. They are pretty active in the books and documentation realms, so I think that can be a great asset.

Great. Can you have it done by Friday?

Oof. So clearly that is a lot of stuff to chew on. Our company mostly supports itself by doing contracting work, but we’ve scheduled a big block of time for enhancing Chipmunk for a while. If there’s something you’re really dying to have in Chipmunk, let me know. It’s good to have some external input when prioritizing.

March 11th, 2013 | Posted by slembcke
Categories: Uncategorized | Tags:

There are some notable limitations with Chipmunk’s current code that a lot of people run into. Deep poly/poly or poly/segment collisions could produce a lot of contact points with wacky positions and normals which were difficult to filter sensibly. This was preventing me from implementing smoothed terrain collision feature that I wanted (fix the issue where shapes can catch on the “cracks” between the endpoints of segment shapes). Also, until recently line segment shapes couldn’t collide against other line segment shapes even if they had a nice fat beveling radius. They can now thanks to a patch from LegoCylon, but they have the same issues as above, generating too many points with wacky normals. I also had no way to calculate the closest points between two shapes preventing the implementation of polygon shapes with a beveling radius. Yet another issue is that the collision depth for all of the contacts is assigned the minimum separating distance determined by SAT. This can cause contacts to pop when driven together by a large force. Lastly, calculating the closest points is also a stepping stone on the way to get proper swept collision support in Chipmunk in the future.

For some time now, I’ve been quietly toiling away on a Chipmunk branch to improve the collision detection and fix all of these issues. I’ve implemented the GJK/EPA collision detection algorithms as well as a completely new contact point generation algorithm. After struggling on and off for a few months with a number of issues (getting stuck in infinite recursion/loops, issues with caching, issues with floating point precision, suboptimal performance, etc… ugh), it finally seems to be working to my expectations! The performance is about the same as my old SAT based collision code, maybe 10% faster or slower in some cases. Segment to segment collisions work perfectly as do beveled polygons. Smoothed terrain collisions are even working, although the API to define them is a little awkward right now.

All collision types.
Beveled line segments colliding with other shapes!

GJK:

The aptly named Gilbert–Johnson–Keerthi algorithm is what calculates the closest points between two convex shapes. My implementation preserves the winding of the vertexes it returns which helps avoid precision issues when calculating the separating axis of shapes that are very close together or touching exactly. With the correct winding, you can assume the edge you are given lies along a contour in the gradient of the distance field of the minkowski difference. I’ve also modified the bounding box tree to cache GJK solution. Then in the next frame, you can use that as the starting point. It’s a classic trick that makes GJK generally require only a single iteration per pair of colliding objects.

GJK example
GJK is rather abstract, but it calculates the closest points between two shapes by finding the distance between the minkowski difference of two shapes (the red polygon) and the origin (the big red dot). If you look closely, the red shape is a flipped version of the pentagon with the little triangle tacked on to all it’s corners. It’s one of the coolest and most bizarre algorithms I’ve ever seen. 😀 I’ll probably make a blog entry about my implementation eventually too.

EPA:

EPA stands for Erik-Peterson-Anders… Nah, it stands for Expanding Polytope Algorithm and is a very close cousin to GJK. While GJK can detect the distance between two shapes, EPA is what you can use to find the minimum separating axis when they are overlapping. It’s sort of the opposite of the closest points. It gives you the distance and direction to slide the two shapes to bring them apart (as well as which points on the surface will be touching). It’s not quite as efficient as GJK and it’s an extra step to run which has the interesting effect of making collision detection of beveled polygons more efficient than regular hard edged ones. This is one thing I’m not completely happy with. Polygon heavy simulations will generally run slower than with 6.1 unless you enable some beveling. It’s not a lot slower, but I don’t like taking steps backwards. On the other hand, it will be much easier to apply SIMD to the hotspots shared by the GJK/EPA code than my previous SAT based code.

Contact Points:

Having new collision detection algorithms is neat and all, but that didn’t solve the biggest (and hardest) issue; my contact point generation algorithm sucked! Actually, it worked pretty good. It has stayed mostly unchanged for 6 years now, but it has also accumulated some strange workarounds for rare conditions that it didn’t handle well. The workarounds sometimes produced strange results (like too many contact points or weird normals…). They also made it practically impossible to add the smoothed terrain collision feature.

In the new collision detection code, polygon to polygon and polygon to segment collisions are treated exactly the same. They pass through the same GJK/EPA steps and end up being passed to the same contact handling code as a pair of colliding edges. It handles collisions with endcaps nicely, always generates either 1 or 2 contact points for the pair, and uses the minimum separating axis for the normals. It’s all very predictable and made the smoothed terrain collisions go pretty easily. It only took me about 10 iterations of ideas for how to calculate the contact points before I got something I was happy with. -_- It really ended up being much, much harder than I expected for something that seems so simple in concept.

The implementation works somewhat similarly to Erin Catto’s contact clipping algorithm, although adding support for beveling (without causing popping contacts) and contact id’s made it quite a bit harder. There are some pretty significant differences now. Perhaps that is another good post for another day.

Coming to a Branch Near You!

The branch is on GitHub here if you want to take a peek and poke around. It’s been a pretty big change, and hasn’t been extensively tested yet. I wouldn’t recommend releasing anything based on it quite yet, but it should be plenty stable for development work, and should even fix a number of existing issues. I’d certainly appreciate feedback!

January 9th, 2013 | Posted by slembcke
Categories: Random | Tags: , ,
Comments Off on Chipmunk Pro performance on the iPhone 5

I finally joined the 21st century after buying a smartphone, an iPhone 5. (Woo I guess?) Anyway. One of the only interesting things that changed with the iPhone 5 was the CPU. It’s supposed to be much faster and uses an new instruction set with extra registers for the NEON vector unit. I was curious to see how much faster it was compared to our iPad 2 at running Chipmunk so I ran the benchmark app and crunched the numbers. It’s certainly a nice leap in performance!

These aren’t conclusive results, but they do paint a nice picture. Normally I run each set a few times and pick the lowest time for each benchmark to remove outliers due to being scheduled on a multitasking OS.

Comparing the iPhone 5 to the iPad 2:

speedup: 2.72x (benchmark - SimpleTerrainCircles_1000)
speedup: 2.60x (benchmark - SimpleTerrainCircles_500)
speedup: 2.50x (benchmark - SimpleTerrainCircles_100)
speedup: 2.68x (benchmark - SimpleTerrainBoxes_1000)
speedup: 2.57x (benchmark - SimpleTerrainBoxes_500)
speedup: 2.55x (benchmark - SimpleTerrainBoxes_100)
speedup: 2.64x (benchmark - SimpleTerrainHexagons_1000)
speedup: 2.63x (benchmark - SimpleTerrainHexagons_500)
speedup: 2.53x (benchmark - SimpleTerrainHexagons_100)
speedup: 2.56x (benchmark - SimpleTerrainVCircles_200)
speedup: 2.62x (benchmark - SimpleTerrainVBoxes_200)
speedup: 2.62x (benchmark - SimpleTerrainVHexagons_200)
speedup: 2.60x (benchmark - ComplexTerrainCircles_1000)
speedup: 2.62x (benchmark - ComplexTerrainHexagons_1000)
speedup: 1.95x (benchmark - BouncyTerrainCircles_500)
speedup: 2.10x (benchmark - BouncyTerrainHexagons_500)
speedup: 1.77x (benchmark - NoCollide)

If you want an idea of what these benchmarks do, the Chipmunk Pro page has little animations of them.

I was also curious how much the extended NEON register set improved performance. It’s been a while, but from what I remember of looking at the disassembled output, the NEON solver in Chipmunk Pro did run out of registers and push values to the stack. So it was possible that the extra registers would be able to speed it up more. It was initially a pain to support armv7s as it was sprung on everybody unexpectedly. All projects were automagically upgraded to build for armv7s when Apple released the new SDK which was annoying for library developers. Having had bad experiences with compiler bugs in Apple’s Clang, I wasn’t willing to release an armv7s build without being able to test it. Anyway, it turns out it was worth the hassle with a decent little performance boost.

The speedups for armv7s vs. armv7 are as follows:

armv7 -> armv7s Speedup:

speedup: 1.23x (benchmark - SimpleTerrainCircles_1000)
speedup: 1.32x (benchmark - SimpleTerrainCircles_500)
speedup: 1.24x (benchmark - SimpleTerrainCircles_100)
speedup: 1.17x (benchmark - SimpleTerrainBoxes_1000)
speedup: 1.17x (benchmark - SimpleTerrainBoxes_500)
speedup: 1.18x (benchmark - SimpleTerrainBoxes_100)
speedup: 1.13x (benchmark - SimpleTerrainHexagons_1000)
speedup: 1.14x (benchmark - SimpleTerrainHexagons_500)
speedup: 1.15x (benchmark - SimpleTerrainHexagons_100)
speedup: 1.23x (benchmark - SimpleTerrainVCircles_200)
speedup: 1.18x (benchmark - SimpleTerrainVBoxes_200)
speedup: 1.15x (benchmark - SimpleTerrainVHexagons_200)
speedup: 1.18x (benchmark - ComplexTerrainCircles_1000)
speedup: 1.13x (benchmark - ComplexTerrainHexagons_1000)
speedup: 1.03x (benchmark - BouncyTerrainCircles_500)
speedup: 1.03x (benchmark - BouncyTerrainHexagons_500)
speedup: 1.00x (benchmark - NoCollide)

That’s about what I expected to see. It was able to speed up a lot of the benchmarks that were using the solver heavily while the last 3 benchmarks that attempted to stress the collision detection performance instead were mostly unaffected. A 10-30% speedup is pretty nice for something as simple as a recompile.

I wonder how this would compare to performance on similar Android devices like the Galaxy S III or Nexus 7. I’ll have to get my hands on one of them and try it.

December 31st, 2012 | Posted by Andy Korth
Categories: Uncategorized | Tags:
Comments Off on Fifth Annual New Year App Blowout

I promise we’re not dead, I’ve just been working on the New Year App Blowout. This year’s sale went great. I had all the spots filled by mid-December, and we got some really great high-profile apps.



New Year App Blowout

The Fifth Annual New Year App Blowout



We’ve already had some press mentions, we’re looking forward to more!