I'm obviously a github noob. Perhaps this pull request will be smoother sailing. I'll respond to the points you made in the old pull request here once I find the time. For now, this version should allow me to sign the CLA.

We didn't expect to push this into a new version of ACL immediately, especially not if 2.0 is almost done. This is more for preliminary info sharing. We're happy to reintegrate our edits into the next release, and consider full integration from there.

I made the regression test compatible with ACL_BIND_POSE this time. I also filled in the code paths we didn't use for track animation, so I can run the regression test. Finally, note how I've disabled ACL_BIT_RATE until I figure out why it fails regression :|

Hello. I'm having problem with building ACL for windows. I'll probably fix it by disabling warning treated as errors but made an issue FYI :

Platform : VC 2019 CMake : updated to latest version before build. Did properly all git submodule update --init first as documented.

My machine is japanese Windows 10. (Note : my OS language is set to english but I bought and made it while in japan)

Having a lot of those : W:\acl\external\catch2\single_include\catch2\catch.hpp(3243): warning C4819: The file contains a character that cannot be represented in the current code page (932). Save the file in Unicode format to prevent data loss (compiling source file W:\acl\tests\sources\core\test_bit_manip _utils.cpp) [W:\acl\build\tests\main_generic\acl_unit_tests.vcxproj]

(Warning treated as error obviously stop the build)

I temporarely removed the warning treated as errors and end up with just the following warning now. W:\acl\tools\acl_compressor\sources\acl_compressor.cpp(631): warning C4996: 'rtm::scalar_near_equal': was declared deprecated W:\acl\external\rtm\includes\rtm/scalarf.h(368): note: see declaration of 'rtm::scalar_near_equal' W:\acl\tools\acl_compressor\sources\acl_compressor.cpp(632): warning C4996: 'rtm::scalar_near_equal': was declared deprecated

Warmest regards, Romain

https://github.com/nfrechette/acl/issues/353 https://github.com/nfrechette/acl/issues/373

ACL_SJSON_FIX

Fix that supports testing of sjson_file_type::raw_track_list, instead of only sjson_file_type::raw_clip.

I needed this to test my edge case animation within ACL.

ACL_COMPRESSION_OPTIMIZED

Prevent low-magnitude channels from becoming constant when worst-case shell distance and object space distance are exceeded. Apply error correction after constant and default tracks are processed. Propagate shell distance and object space distance through ancestors before compression.

Massive memory and quality upgrade. In our use case, there's a 28% reduction in memory overall(33% in humans, 22% in creatures). Our worst edge case used to compress in 30 seconds, and failed regression with an error of nearly 2 meters. Now regression passes well within precision settings, and it compresses 10x faster. Compression is faster generally, as seen in py make.py -regression_test:

uniformly_sampled_database.config.sjson: 04.04s -> 03.38s
uniformly_sampled_database_4kb.config.sjson: 04.03s -> 03.33s
uniformly_sampled_database_4kb_mixed.config.sjson: 04.73s  -> 04.04s
uniformly_sampled_database_mixed.config.sjson: 04.64s -> 03.99s
uniformly_sampled_mixed_var_0.config.sjson: 01.14s -> 01.26s
uniformly_sampled_mixed_var_1.config.sjson: 01.61s -> 01.35s
uniformly_sampled_quant_bind_relative.config.sjson: 01.87s -> 01.29s
uniformly_sampled_quant_high.config.sjson: 02.27s -> 01.33s
uniformly_sampled_quant_highest.config.sjson: 03.82s -> 01.27s
uniformly_sampled_quant_medium.config.sjson: 01.68s -> 01.27s
uniformly_sampled_quant_mtx_error.config.sjson: 01.68s -> 01.27s
uniformly_sampled_raw.config.sjson: 01.19s -> 01.20s

I also tried a more accurate version of propagation which compared every bone with every ancestor. It resulted in smaller distances, but was more complex(O(N^2)), compression took longer, and memory savings shrank.

I'm confident that introducing error correction within segment compression would improve memory and compression time further. It seems unlikely that most of the logic in find_optimal_bit_rates would be required anymore. Perhaps I'll experiment with this later, but the current state of ACL_COMPRESSION_OPTIMIZED is fast enough, and high-quality enough, for our immediate needs.

ACL_BIT_RATE_EXPANSION

Expand bit rate options, from [3..19] to [1..23].

Note that these results assume that ACL_COMPRESSION_OPTIMIZED is enabled. I don't recommend trying ACL_BIT_RATE_EXPANSION without it. Additional 2% reduction in memory overall(3% in humans, 2% in creatures). No changes to py make.py -regression_test timings worth reporting, but some of our creature compression does get slower. Edge cases are rare, and max out at 7 seconds this time.

See this PR for original inspiration: https://github.com/nfrechette/acl/pull/348 by @ddeadguyy.

Animations are typically stored in one of two formats: relative to the identity transform or relative to some base pose. I've already explored how to store relative to the bind pose here.

As illustrated by that blog post, many joints end up being equal or close to the bind pose (the default character pose) which makes sense: not all joints are animated (and not all sub-tracks for joints that are animated).

ACL currently considers sub-tracks to be in one of 3 possible states: animated (with N samples), constant (with 1 sample), or default (equal to the identity, 0 sample).

In practice, animations that aren't relative to some base pose have their sub-tracks rarely equal to the identity. Instead it would be best if the default sub-track value could be something provided by the game engine: the bind pose. This would allow ACL to store sub-tracks that are equal to the bind pose with just two bits since we'll be able to avoid storing the bind pose per clip (it's often used for many things at runtime and could easily be provided by the game engine).

However, this is a lossy process and special care must be taken. If a clip is compressed with that assumption and the bind pose isn't provided during decompression, then sub-tracks returned by ACL that are default will not be able to return the right value. In a sense, either those sub-tracks must be skipped during decompression or the bind pose must be provided and looked up.

ACL 2.0 reworked the compression API and removed the RigidSkeleton which previous contained the bind_transform for debugging purposes. We would have to re-introduce the concept. Since this is optional, a separate track_qvvf should be provided to the compression API. Compression can continue normally except that when we detect if a track is default, we check against the bind pose if it is provided instead of the identity. The compressed clip will contain a new metadata flag to mark it as 'bind pose needed/aware'. During decompression, new optional functions on the pose writer will be added to handle this. Together with the metadata flag, we'll be able to assert at runtime that proper support is handled.

Decompression can be handled in one of two ways by the engine:

• Skip default tracks and output nothing
• Read the bind pose value and output it

The first case would be used when the engine pre-fills the output buffer with the bind pose. We would skip default sub-tracks to avoid overwriting the value.

The second case is more efficient.

To this end, a new function on the pose writer will be added: handle_default_rotation(uint32_t track_index, rtm::quatf_arg0) (and translation/scale). ACL will continue to provide the identity transform as an argument and it will be up to the game engine to handle default sub-tracks through the pose writer implementation.

This branch will be used for the development work: feat/improve-bind-pose-handling

Please consider using a tool like Google benchmark for providing measurements.

See also

• https://www.bfilipek.com/2016/05/google-benchmark-library.html
• https://www.bfilipek.com/2016/01/micro-benchmarking-libraries-for-c.html

Trying to generate Visual Studio 2017 project with cmake for ARM64 platform but fails to compile since "warning C4324: 'acl::RigidBone': structure was padded due to alignment specifier"

Any way to get this to work?

/Johan

Range reduction sometimes causes accuracy loss. Investigate fixed point arithmetic to see if it can improve accuracy.

Perhaps a mix of fixed point/float32 arithmetic should be used for optimal results? Also keep in mind performance implications for the decompression.

http://x86asm.net/articles/fixed-point-arithmetic-and-tricks/

https://en.wikipedia.org/wiki/Fixed-point_arithmetic

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwj2_fSo87LXAhVV5GMKHS9BCVgQFggrMAE&url=http%3A%2F%2Fwww-inst.eecs.berkeley.edu%2F~cs61c%2Fsp06%2Fhandout%2Ffixedpt.html&usg=AOvVaw30e1B92ekXbTzJeUDNfMgb

Use a rotation track from CMU for a segment, 16 rotations. Compare with current float32 code path. Compare with float64 code path. Compare with fixed point code path (possibly various precision settings).

Exhaustive comparison for every possible bit rate?

https://software.intel.com/en-us/forums/intel-isa-extensions/topic/301988

http://codesuppository.blogspot.ca/2015/02/sse2neonh-porting-guide-and-header-file.html

===============================================================================
All tests passed (170 assertions in 6 test cases)

Consider this a proof of concept, you shouldn't really be using conio.h in 2017…

#include <windows.h> is also a bit iffy in this case, but I'll let you solve that yourself.

Please enable AppVeyor, free-for-open-source CI service that hosts (amongst others) MSVC toolchains. Once done, you can merge this to automatically build each commit and verify it against MSVC2015 and MSVC2017

When decompressing, we first seek with the decompression context. This performs a linear search to find the segments needed to sample at a time T. This can be slow for longer clips and isn't terribly cache friendly with the current memory layout (pointer offsets add noise that we have to skip over).

A better idea would be to split the segment header into two parts. A first part with the first segment sample index contiguous with 16 or 32 bit per index (most clips are small and fit on 16 bits, should we do 8 bits?). This will allow for cache efficient searching. A binary search can be implemented for long clips and a SIMD search for short clips. The second part can contain the necessary offsets and can trivially be index from the segment index.

It seems some tests fail:

$ python3 make.py -clean -build -unit_test -${COMPILER} -Debug -x86
<…snip…>
/home/travis/build/janisozaur/acl/tests/sources/core/test_memory_utils.cpp:108: FAILED:
  REQUIRE( padding0 == 4 )
with expansion:
  0 == 4

We currently use a position based error metric. This simulates the skinning process as described here.

However, this does not really account for the error perceived by the end user on screen. For example, under high velocity, a larger error can be tolerated because it isn't as visible on account of the fast movement. An error of 5cm might be very visible when the velocity is low, but entirely invisible if sufficiently high. In the same vein, a large positional error could be tolerated on limbs not in contact with the environment/other things as there is no frame of reference for the user to evaluate accuracy. An error of 5cm on a floating hand is hard to see, but easy to spot if reaching for a door knob.

The general idea is that the first derivative (velocity) of our data might provide more relevant information when it comes to measuring error accuracy. Similarly, perhaps using the second derivative (acceleration) can be of use as well.

David Goodhue has published a paper where he uses velocity to compress animation data however I believe part of that work has been patented. See here: https://dl.acm.org/doi/10.1145/3102163.3102236

Is it possible to remap pointers decompression_context and database_context after the associated compressed_tracks or compressed_database get relocated?

Given that both compressed_tracks and compressed_database are just plain bytes that can be memcpy'd around, a natural way to reduce runtime memory footprint is to compress them (losslessly) when the clip/database is not actively used and decompress when they get hot again.

A problem arises is that we cannot use the same decompression/database_context later when the data got decompressed. Because there is no way to update the compressed_tracks/database in the contexts. The only available option I found is to destroy and re-initialize the contexts (also re-stream-in database bulk data), which is much more expensive than it needs. Note: The content of the new tracks/database is exactly the same as before, i.e. they are just relocated as seen by ACL.

Conceptually, we need a cheap way to remap pointers in decompression/database_context. Is it possible to add such functionalities? Another option is to replace every pointers in the context with ptr_offset, but I am not sure how will this impact the performance.

When we try bit rates, we decay our values by simulating quantization to the desired number of bits. Perhaps instead we could quantize once to the highest bit rate, and shift the least significant bits off.

Can we treat the values as fixed point since the range is fixed?

If we can, can we leverage this somehow during decompression or by streaming those truncated bits?

The current database streaming works in bulk. All clips within stream together at the desired quality level. This can make it quite hard to have fined grained control over quality. It forces runtimes to group few clips together and have many databases. In turn, this harms the ability of the algorithm to globally optimize for quality when targeting a specific memory footprint.

Streaming has been implemented in bulk to optimize for older disk based hardware where seeks and reads are expensive and must thus be minimized. However, with flash memory on mobile and SSD/NVMe on PC and consoles, seeks and reads are dramatically cheaper. As such, it makes sense to extend the ability to stream individual clips within a database for those platforms.

Bulk streaming is nice because it requires little metadata. All chunks are read from disk linearly and they contain the necessary metadata. Streaming individual clips will require extra metadata. We need to know where in the bulk buffer the clip lives for each quality level. This metadata will need to be present in memory with the rest of the database runtime metadata.

Streaming a clip would then first look up which offset to read from disk for the desired quality level. A read from disk would be performed, and we'd update the runtime metadata.

Each quality level would perform an individual seek and read. We can later optimize this by swizzling the data such that data for all quality levels of a clip live contiguously on disk. This will allow us to perform a single read for all quality levels. Optimizing the data in this way will make it much slower to stream/unstream the whole database at a specified quality level.

Streaming out no longer makes sense if we manipulate individual clips. Streaming out a single clip would not allow us to reduce the memory footprint as we can't allocate memory for individual clips.

A different paradigm is necessary when managing memory at the clip level. We will need to allocate memory in chunks of a fixed size and clips will populate them in the order we stream them in. Because our runtime metadata stores 32bit offsets, we need to be careful where things live and how we manage it. We could reserve virtual memory up front in a single buffer large enough to accommodate multiple times the size of the database to account for fragmentation. When we need to stream out, we'd mark the allocation as free in our chunk. Later, a garbage compaction phase would kick off and reclaim unused space by compacting things into existing/new chunks. This can be done entirely async and in a thread safe way since we atomically update our offsets. Reserving virtual memory could also be avoided if we split out 32bit offset into two parts: a chunk index (8bit) and an offset into the chunk (24 bit). This would allow us to have non-contiguous chunks. If we do this, we need a heuristic to figure out how many chunk indices to reserve. We could reserve enough indices to store the whole database plus some slack for fragmentation. If fragmentation exceeds our expectations because compaction hasn't run in a while, we could force one if we run out of indices. Something along those lines.

Currently, segment samples are normalized and thus the range values are also normalized. We currently encode the range as [min, extent] where max = min + extent. This allows us to represent the full range of [0.0, 1.0].

An alternative could be to store it as [centre, half extent]. This has the benefit that we need 1 bit less for the half extent encoding because we need both +- values. The down side is that we can only represent [0.0, 1.0). This might be a good fit for bit shifting float coercion where we just line up the mantissa. This boundary condition can also be handled by the clip range since we already pad it to handle rounding.

If we drop the number of bits for the extent portion, we can save up to 8 bits per component. However, because segments have ~16 samples, if the bit rate increases by 1 bit as a result, we'll end up with a net loss of 8 bits. We'd only win if we can maintain the same bit rate.

If the range bounds aren't tight, it leaves room for sample values to encode values that are out of the possible range of values. As such, we'd have a portion of our sample encoded range that would be unused. This would decrease the percentage used.

We could add fixed padding to the extent and use fewer bits.

We could also leverage the fact that segment ranges are packed in groups of 4 sub-tracks. We current store 12+12 bytes for [min, extent]. We could do 12+8, or 12+9, etc.

Can we leverage the group as well? Sort by min/centre and reduce the range of possible values that way? Store the sub-track order on 4-6 bits (2 bits per sub-track, last one can be dropped and reconstructed). Can we do something clever with this? This would still allow for fast single track decompression.

Can we bucket ranges?

If we need to, we could add metadata etc but ideally we have to keep the decompression path lean and simple.