Search Unity

A Fast BlobCurve

Discussion in 'Entity Component System' started by Lieene-Guo, Oct 10, 2020.

  1. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    This BlobCurve runs about 12 times faster than UnityEngine.AnimationCurve. And about 30% faster than Unity.Animation.AnimationCurve.
    upload_2020-10-13_11-33-7.png

    Basically, it uses only one dot(float4,float4) for one sample.
    Code (CSharp):
    1.        public float Sample(float time)
    2.         {
    3.             TimeCheck();
    4.             float t = (time - StartTime) * InvDuration;
    5.             float tSq = t * t;
    6.             float4 timeSerial = float4(tSq * t, tSq, t, 1);
    7.             return dot(Factors, timeSerial);
    8.         }
    Because Matrix multiplication is done in blob baking.
    Code (CSharp):
    1.        /// <summary>
    2.         /// Convert From Cubic Hermite spline parameter
    3.         /// </summary>
    4.         public NativeCurveSegment(
    5.             float value0, float tangent0, float time0,
    6.             float value1, float tangent1, float time1)
    7.         {
    8.             float duration = time1 - time0;
    9.             float4 factors = mul(S_BezierMat, float4(value0, value0 + (tangent0 * duration * OneThird), value1 - (tangent1 * duration * OneThird), value1));
    10.             this = new NativeCurveSegment(factors, time0, duration);
    11.         }
    So it should run much faster than Unity.Animation.Curves.

    keyframe index search is done by a cached local first binary search.

    Source attached.

    This curve has been used in my game for some time. It does reference several functions from my Toolkit, but that's trivial. Will upload to GitHub when the whole lib is ready. Let me know if there are optimization suggestions.

    Code (CSharp):
    1.  
    2.     [NaughtyAttributes.Button(nameof(PerformanceTest))]
    3.     unsafe private void PerformanceTest()
    4.     {
    5.         if (curve == null || !blobCurveRef.IsCreated) return;
    6.         var keys = curve.keys;
    7.         var start = curve.keys[0].time;
    8.         var time = start;
    9.         var watch = System.Diagnostics.Stopwatch.StartNew();
    10.         //-------------------------------------------------------------------------------------------------
    11.         var pFun = NativeDelegate<EvaluateCall>.Compile(BurstEvaluateBlobCurve).AsFunctionPointer().Invoke;
    12.         var copy = blobCurveRef;
    13.         var value = 0f;
    14.         watch.Restart();
    15.         pFun(start, performanceTestStepLen, sampleCount, UnsafeUtility.AddressOf(ref copy), &value);
    16.         watch.Stop();
    17.         var tick = watch.ElapsedTicks;
    18.         //-------------------------------------------------------------------------------------------------
    19.         var copy2 = unityCurve;
    20.         var pFunUnity = NativeDelegate<EvaluateCall>.Compile(BurstEvaluateUnityCurveBlob).AsFunctionPointer().Invoke;
    21.         var value1 = 0f;
    22.         watch.Restart();
    23.         pFunUnity(start, performanceTestStepLen, sampleCount, UnsafeUtility.AddressOf(ref copy2), &value1);
    24.         watch.Stop();
    25.         var tick1 = watch.ElapsedTicks;
    26.  
    27.         //-------------------------------------------------------------------------------------------------
    28.         watch.Restart();
    29.         var value2 = 0f;
    30.         for (int i = 0; i < sampleCount; i++)
    31.         {
    32.             value2 += curve.Evaluate(time);
    33.             time += performanceTestStepLen;
    34.         }
    35.         watch.Stop();
    36.         var tick2 = watch.ElapsedTicks;
    37.  
    38.         float f = System.Diagnostics.Stopwatch.Frequency * 1.0e-3f;
    39.         float ms = tick / f;
    40.         float ms1 = tick1 / f;
    41.         float ms2 = tick2 / f;
    42.  
    43.         Debug.Log($"Simpled {sampleCount} times, BlobCurve : {tick} ticks {ms} ms, Unity.Animation.AnimationCurve : {tick1} ticks {ms1} ms, UnityEngine.AnimationCurve : {tick2} ticks {ms2} ms");
    44.         //Debug.Log($"None-Bursted BlobCurve used{tick2} ticks {ms2} ms");
    45.     }
    46.     unsafe delegate void EvaluateCall(float time, float step, int count, void* ptr, float* valueOut);
    47.     [BurstCompile]
    48.     unsafe public static void BurstEvaluateBlobCurve(float time, float step, int count, void* pBlobCurveRef, float* valueOut)
    49.     {
    50.         var assetReference = UnsafeUtility.AsRef<BlobAssetReference<BlobCurve>>(pBlobCurveRef);
    51.         ref var blobCurve = ref assetReference.Value;
    52.         var value = 0f;
    53.         var cache = BlobCurveCache.Empty;
    54.         for (int i = 0; i < count; i++)
    55.         {
    56.             value += blobCurve.EvaluateIgnoreWrapMode(time, ref cache);
    57.             time += step;
    58.         }
    59.         *valueOut = value;
    60.     }
    61.  
    62.     [BurstCompile]
    63.     unsafe public static void BurstEvaluateUnityCurveBlob(float time, float step, int count, void* pAnimCurve, float* valueOut)
    64.     {
    65.         ref var curve = ref UnsafeUtility.AsRef<UnityCurve>(pAnimCurve);
    66.         var value = 0f;
    67.         for (int i = 0; i < count; i++)
    68.         {
    69.             value += AnimationCurveEvaluator.Evaluate(time, ref curve);
    70.             time += step;
    71.         }
    72.         *valueOut = value;
    73.     }
    74.  

    Also, I got float2 float3 curve working.
    the reason for them is that keyframe searching is the slowest part of curve evaluation. keep xyz synced in one curve is much faster than using 3 curves.
    Quaternion curve and Transform curve is under test. will upload later.
     

    Attached Files:

    Last edited: Oct 13, 2020
    Enzi, One1Guy, mgear and 28 others like this.
  2. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    upload_2020-10-10_23-3-28.png
    Shape match: UnityEngine.AnimationCurve is drawn as a red line, which is completely covered by NativeCurve (green line).
    The Number is KeyFrame segment index. Red means they are out ranging curve time and extended via Loop/PingPong/Clamp.

    And the original curve:
    upload_2020-10-10_23-5-50.png
     
  3. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    Manually vectorized BinarySearch could further improve performance.
    Basically, in each iteration divide the current range into 4 segments, and search them all with int4 index, float4 time range, and bool4 result. and this could be generalized to all BinarySearch.

    Continuous sampling will not benefit from this, but random access will.
     
    Last edited: Oct 10, 2020
  4. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    Could extend local search to 4 Neighbors while it's still one SIMD, one more step ahead will make fast forward playing animation hit Neighbors better.
     
  5. jashan

    jashan

    Joined:
    Mar 9, 2007
    Posts:
    3,307
    Wow, this is very cool - thanks for sharing! I can't comment on potential optimizations, just wanted to express my appreciation! This is very useful!

    EDIT: Ah, just one question ... is there a reason you call the method to evaluate the value of the curve at a given point in time Sample instead of Evaluate? Sample is a great name, but it's inconsistent with the naming of AnimationCurve. I haven't found documentation for Unity.Animation.Curves to check how they called the method there.
     
    Last edited: Oct 11, 2020
  6. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    No specific reason for that. you can use Evaluate if you like it ;)
     
    jashan likes this.
  7. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    I updated the source code. renamed to BlobCrrve.
    And I found that Unity.Animation.AnimationCurve supports only clamp mode as for wrap mode.
    The original post and source code is updated.
     
    Last edited: Oct 12, 2020
    jashan likes this.
  8. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    The new test, after some optimization:
    About 12 times faster than UnityEngine.AnimationCurve. And about 30% faster than Unity.Animation.AnimationCurve.
    Detail profile and source update in the original post.

    It looks like math operation complexity is not that important in this case. Because they are as trivial as several assembly instructions. BlobArray memory access time takes way much longer than that. So I used some cache to reduce the chance of memory access (like Unity.Animation.AnimationCurve does).
    And I got a result that's 30% faster than Unity.Animation.AnimationCurve.
    Also, the comparison is done in a Clamp only warp mode(no Loop/PingPong). as Unity.Animation.AnimationCurve support only clamp mode for now.
    My Curve supports Loop/PingPong. but when any none Clamp mode is used in the curve. It's about 5 times slower.
    due to the use of modular operator (%) and two if branch.
     
    Last edited: Oct 13, 2020
    Lukas_Kastern and jashan like this.
  9. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    New version uses Evaluate as you suggested ;)
     
    Antypodish and jashan like this.
  10. Lieene-Guo

    Lieene-Guo

    Joined:
    Aug 20, 2013
    Posts:
    547
    Fixed BlobCurve2/3 Conversion bug. Source updated.
     
    bb8_1 and jashan like this.
  11. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    298
    Can you upload missing files? Currently missing BlobCurveCache and extensions it looks like.
     
  12. Thygrrr

    Thygrrr

    Joined:
    Sep 23, 2013
    Posts:
    700
    Oh. This is a pretty sweet idea, I'm rolling my own tweening system in DOTS and I have a "Curve" and a "CurveAndKeyframe" BlobAsset, and those would benefit greatly from this.
     
  13. Armitage1982

    Armitage1982

    Joined:
    Jul 26, 2012
    Posts:
    38
    Is there any news about this library?

    I also don't know if there is an official solution for this (one that takes advantage of all the features of UnityEngine.AnimationCurve, unlike Unity.Animation which only supports clamp mode).
     
    Last edited: Feb 13, 2022
    chadfranklin47 likes this.
  14. xVergilx

    xVergilx

    Joined:
    Dec 22, 2014
    Posts:
    3,296
    It still works just fine in 2022.
     
  15. Armitage1982

    Armitage1982

    Joined:
    Jul 26, 2012
    Posts:
    38
    The proposed example is not very clear.
    Are we supposed to use AnimationCurve from com.unity.animation in order to use BlobAssetReference<BlobCurve>>?

    Because I use Unity 2021 I am not able to import the Animation package (it breaks and is unsupported) which is also why I am looking for an alternative.
     
  16. xVergilx

    xVergilx

    Joined:
    Dec 22, 2014
    Posts:
    3,296
    AnimationCurve used for initial conversion is not from Animation package. Its from UnityEngine namespace.

    Use BlobCurve.Create to convert AnimationCurve to BlobAssetReference<BlobCurve>, then you can attach BlobCurveSampler to the entity.

    After that you can use Evaluate extension methods either on BlobCurveSampler, or
    BlobAssetReference<BlobCurve>. Or you can call it directly on the BlobCurve.
     
  17. Armitage1982

    Armitage1982

    Joined:
    Jul 26, 2012
    Posts:
    38
    Thank you for explaining how it works.
    Everything works fine.
    Thanks also to the OP, this is exactly what I was looking for.
     
  18. Armitage1982

    Armitage1982

    Joined:
    Jul 26, 2012
    Posts:
    38
    Do the new features of Entities 1.0.0 allow a better approach to animation curves or is it still relevant to try to update these classes?
    These are the only external systems I use in my project and some of the techniques they cover are still unknown to me.
     
  19. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,262
    There's nothing new in Entities 1.0 in this regard. I am working on updating my solution, which is a very different technique from what is discussed in this thread, but very fast.