Sunday, October 23, 2011

Low Level Animation -- Part 2

Some time ago I wrote an article describing how animation compression is implemented in the BitSquid engine. In that article I made a vague promise that I would follow up with a description of how to pack the data in a cache-friendly way. Now, the time has come to deliver on that vague promise.

A quick recap: After curve fitting, each track of our animation consists of a number of curve points that describe the curve for each animation track:

By an animation track I mean the animation of a single parameter, typically the position or rotation of a bone.

The data for the track is a sequence of times and curve data:

Here t_i is the time of a curve point and A_i is the corresponding curve data.

To evaluate the curve at any particular point t we need the curve points both before and after the time t

Depending on what curve type you use (hermite, bezier, b-spline, etc) you might actually need more than two curve points to evaluate a segment, but that doesn’t really affect the discussion in this article, so for the sake of simplicity, let’s stick with two.

Note that the time points for the different tracks in the animation typically do not match up. For example, one curve may be completely flat and only require one sample at the start and one sample at the end. Another curve may be complicated and require lots of samples.

To simplify the discussion further, assume that the animation only contains two tracks (it is easy to generalize the solution to more tracks). We will call the curve points of one (t_i, A_i) and the curve points of the other (s_i, B_i):

How can we organize this data to be as cache friendly as possible?

The most natural approach is perhaps to sort the data first by track and then by time. Let’s see what this means for the cache. To evaluate the animation for some particular time t, we have to go into the data for each track at that time to look up the two neighboring curve points. Let’s assume that we have somehow cached our current position in each track, so that we don’t have to search for it, we will still have at least one cache miss for each track. A modern character can have over 100 bones, with two tracks per bone. That’s 200 cache misses for just a single frame of a single animation.

To do better, we need to organize the data by time somehow. But it is not immediately clear how. Just sorting the data by time won’t help, because then a flat curve with just two curve points, one at the beginning and one at the end, will have them at complete opposite ends of the data and no matter what we do we will get cache misses when touching them.

Let’s consider all the data we need to evaluate the tracks at time t. We need (t_i, A_i), (t_i+1, A_i+1) and (s_j, B_j), (s_j+1, B_j+1) where t_i <= t <= t_i+1 and s_j <= t <= s_j+1. This is our ”hot” data, because we will need to refer to it several times as we evaluate the curve at different points in time. In fact, we can keep using this same data until we reach whichever is smallest of t_i+1 and s_j+1. A general rule in memory access optimization is to keep the ”hot” data together, so let’s create an additional data structure, an array with the currently active curve points for a playing animation instance.

Now we’re getting somewhere. Not only have we significantly improved the cache behavior; as long as we don’t need to fetch new curve points we only need to refer to the active array, a single memory access. We have also decomposed our animation evaluation problem into two simpler tasks: evaluating curves and fetching new curve points. This makes our code both simpler and more flexible.

Let’s look at the second issue, fetching new curve points. In the example above, when we reach the time t_i+1 we will need to fetch the new curve point (t_i+2, A_i+2) and when we reach the time s_j+1 we will need to fetch (s_j+2, B_j+2).

Generalizing, we always need to fetch the point (t_i, A_i) at the time t_i-1, and we always need to fetch the point (s_i, B_i) at the time s_i-1. This is excellent, because since we now the time when each of our curve points will be needed we can put them all in a single stream of data which is sorted by the time when they will be needed.

This means that our animation player only needs to keep a single pointer into the animation stream. That pointer will always point to the next curve point that needs to be moved to the active list. As time is advanced, curve points are copied from the animation data into the active list and then the curve is evaluated.

Note the excellent cache behavior this gives us. To fetch new curve points, we just move a pointer forward in memory. And then, to evaluate the curves, we just need to access our active array, a single continuous memory block. This gives us a grand total of just two memory accesses.

Another nice property is that since we are now accessing the animation data as a stream (strictly linearly, from beginning to end) we can gzip it and get another factor two of compression. We can also easily stream it from disk.

One drawback of this system is that it only supports playing an animation forward, you cannot jump to a particular time in an animation without ”fast forwarding” through all intermediate curve points.

If you need support for jumping, the easiest way to achieve it is perhaps to add a separate index with jump frames. A jump frame consists of the state of the active array at some point in time, together with an offset into the data stream. In other words, all the state information that the animation player needs to jump to that time point and resume playing.

Using jump frames let’s you balance performance and memory use. If you add more jump frames you will use more memory but on the other hand, you will be able to find a jump frame closer to the time you actually want to go to which means less fast forwarding.

1. Looks like there's something I don't understand: How do you know the index in the array of currently active points where a key frame must be moved to? Do you store the joint index in every key frame?

2. Yes, I use 10 bits to store the joint index (maximum of 1024 joints) and 1 bit to indicate if it is position or rotation data.

11 bits extra per key is not insignificant, but I find it worth it, considering the other benefits.

3. I visit your web page. It is really useful and easy to understand. Hope everyone get benefit. Thanks for sharing your Knowledge and experience with us.
Norton setup - Get started with Norton by downloading the setup and installing it on the device. Enter the unique 25-character alphanumeric product key for activation. Check your subscription norton.com/setup | norton.com/setup

4. Norton Setup-To get protection, access your Norton account and download the Norton product on your device. Installing the Norton software and activate with 25-digit alphanumeric product key at Official platform of Norton Setup.
norton.com/setup |norton.com/setup

5. We at Epson Printer Support have a mind blowing acknowledgment of being the palatable Epson reestablish focus in the commercial center for providing our customers with the agreeable in class administrations. Our unimaginably talented specialists can deal with any printer related issue and investigate it with brief answers. We have a toll loosened helpline run +1-877-760-6111 at which you could name to explain your printer concerns and profit simple and short answers from our masters.
epson printer setup

ข่าวเชลซี

ดูเชลซี

ข่าวบอล

โปรแกรมฟุตบอล

montiepower.com
barrelblaster.net

openergroup"
erlangpatterns"

9. Soda ash is an inorganic compound. In appearance, all the forms of soda ash are white. Soda ash is known as a water-soluble salt.

soda ash plant cost

Top 10 Fintech Companies in America
Top Antivirus Software 2021

11. 789betting
Your blog has a lot of interesting articles. I will use the information I have gained. https://www.789betting.biz/

12. Thank you! I really enjoyed your post I want to share with you all a useful source If you are planning a short one day trip the gandikota is the best place to visit with amazing sightseeing. Gandikota is a small town in India that can be explored in one day. But don’t judge this place by its size.

13. According to a new report by Expert Market Research, ‘Smart Electric Meter Market Size, Share, Price, Trends, Growth, Report and Forecast 2021-2026’, the Smart Electric Meter Market size was valued at USD XX million in 2020 and is predicted to register a CAGR of XX% from 2021 to 2026.

Download a free Sample Report : Smart Electric Meter Market Size, Report & Forecast

14. Hi, not a bot here. Great article

15. This is a very Useful & Informative Topic, I got lots of information from it,
There is also something to discuss with you guys,
Design Remodeling Rancho Santa Fe CA

You guys try it for the best Home Inspection services.

16. Thanks for writing such a great article. I happened to stumble upon your blog and read a few posts. 123bet แนะนำเพื่อน

17. Looking for effective and reliable customer care support to troubleshoot your technical glitches? Dial Telstra contact number Australia and get effective assistance.

18. I mentioned shoes briefly in my Men's Wardrobe Essentials Series and in my Summer Essentials Ebook, but the most-requested topic for a long time has been the quantity and type of shoes any guy should own. So here you have it: These are the classic men shoes that every man should have in his wardrobe for all-year wear. Anything else, such as snow boots, is considered a specialist item and is not included in this article.

19. Fun Casino in Bognor High Street​ at Cassino Amusements

Cassino is the place to have fun, enjoy the excitement of casino gaming in a relaxed, family-friendly environment. With Casino in Bangor High Street, you’ll be spoiled for choice. Our state-of-the-art facilities are guaranteed to put a smile on your face, with a wide selection of slot and gaming machines to cater to everyone.

20. However, changing lifestyle has resulted in hair loss that makes the lash look thin and out of shape. Cosmetic companies use different treatment methods like Lash Extensions Scottsdale, Brow Pencils, Brow Lamination etc to provide the right shape to your eyes, making them look denser and longer.

21. Thanks for the good stuff here. I will come back to visit your blog again.

สล็อตออนไลน์

22. Here you find all type on information in hindi. Hindi ki News is a good platform for all type of information .
Tik-tok ka malik kon hai