Animation_nodes: Adaptive sampling of curve

[3DSinghVFX]

Hi...
Current curve sampling has two methods _Uniform_ and _Resolution_. The _Resolution_ method respects the curve handles but not the slope of the curve.

It would be nice if we have _Adaptive_ method which respects the curve slope,

[OmarEmaraDev]

Implemented in def0593. Let me know if it works as intended.

[3DSinghVFX]

Implemented in def0593. Let me know if it works as intended.

Thanks for implementing this node. It works but sometimes gives unexpected results, maybe I'm doing something wrong,

[OmarEmaraDev]

Reducing the Max Step should solve this. (A value between 0 and 1)

[harisreedhar]

Hi please check Parameters output which is currently FloatList not DoubleList

[JacquesLucke]

I think the inner workings of the node might need a bit more careful design. Ideally the output points should should be symmetric in the case @3DSinghVFX shows.
Also, can the be part of the Evaluate Spline node?

[OmarEmaraDev]

I did try to incorporate it into the Evaluate node, but the evaluation is not parameterized as in the case of Resolution and Uniform parameterization. Not sure if we can do something like uniform conversion, I will take a look.

For symmetry, a solution might be double sided integration, can you try this @3DSinghVFX?

diff --git a/animation_nodes/data_structures/splines/bezier_spline.pyx b/animation_nodes/data_structures/splines/bezier_spline.pyx
index 8b092f37..89bb0307 100644
--- a/animation_nodes/data_structures/splines/bezier_spline.pyx
+++ b/animation_nodes/data_structures/splines/bezier_spline.pyx
@@ -324,20 +324,25 @@ cdef class BezierSpline(Spline):

     @cython.cdivision(True)
     def getAdaptiveParameters(self, float stepMultiplier, float maxStep):
+        cdef float startParameter, endParameter, startRadius, endRadius
         cdef FloatList parameters = FloatList()
         cdef int amount = getSegmentAmount(self)
         cdef float step = 1.0 / amount
-        cdef float parameter, radius
         cdef Vector3* w[4]
         cdef Py_ssize_t i
         for i in range(amount):
-            parameter = 0.0
+            startParameter = 0.0
+            endParameter = 1.0
             getSegmentData_Index(self, i, w)
-            while parameter < 1.0:
-                parameters.append_LowLevel(step * (parameter + i))
-                radius = 1.0 / max(evaluateBezierSegment_Curvature(parameter, w), 1e-5)
-                parameter += min(radius * stepMultiplier, maxStep)
-        parameters.append_LowLevel(1)
+            while startParameter < endParameter:
+                parameters.append_LowLevel(step * (startParameter + i))
+                if endParameter != 1:
+                    parameters.append_LowLevel(step * (endParameter + i))
+                startRadius = 1.0 / max(evaluateBezierSegment_Curvature(startParameter, w), 1e-5)
+                endRadius = 1.0 / max(evaluateBezierSegment_Curvature(endParameter, w), 1e-5)
+                startParameter += min(startRadius * stepMultiplier, maxStep)
+                endParameter -= min(endRadius * stepMultiplier, maxStep)
+        parameters.append_LowLevel(1.0)
         return parameters

Note: No linear order in the above diff.

[3DSinghVFX]

I did try to incorporate it into the Evaluate node, but the evaluation is not parameterized as in the case of Resolution and Uniform parameterization. Not sure if we can do something like uniform conversion, I will take a look.

For symmetry, a solution might be double sided integration, can you try this @3DSinghVFX?

diff --git a/animation_nodes/data_structures/splines/bezier_spline.pyx b/animation_nodes/data_structures/splines/bezier_spline.pyx
index 8b092f37..89bb0307 100644
--- a/animation_nodes/data_structures/splines/bezier_spline.pyx
+++ b/animation_nodes/data_structures/splines/bezier_spline.pyx
@@ -324,20 +324,25 @@ cdef class BezierSpline(Spline):

     @cython.cdivision(True)
     def getAdaptiveParameters(self, float stepMultiplier, float maxStep):
+        cdef float startParameter, endParameter, startRadius, endRadius
         cdef FloatList parameters = FloatList()
         cdef int amount = getSegmentAmount(self)
         cdef float step = 1.0 / amount
-        cdef float parameter, radius
         cdef Vector3* w[4]
         cdef Py_ssize_t i
         for i in range(amount):
-            parameter = 0.0
+            startParameter = 0.0
+            endParameter = 1.0
             getSegmentData_Index(self, i, w)
-            while parameter < 1.0:
-                parameters.append_LowLevel(step * (parameter + i))
-                radius = 1.0 / max(evaluateBezierSegment_Curvature(parameter, w), 1e-5)
-                parameter += min(radius * stepMultiplier, maxStep)
-        parameters.append_LowLevel(1)
+            while startParameter < endParameter:
+                parameters.append_LowLevel(step * (startParameter + i))
+                if endParameter != 1:
+                    parameters.append_LowLevel(step * (endParameter + i))
+                startRadius = 1.0 / max(evaluateBezierSegment_Curvature(startParameter, w), 1e-5)
+                endRadius = 1.0 / max(evaluateBezierSegment_Curvature(endParameter, w), 1e-5)
+                startParameter += min(startRadius * stepMultiplier, maxStep)
+                endParameter -= min(endRadius * stepMultiplier, maxStep)
+        parameters.append_LowLevel(1.0)
         return parameters

Note: No linear order in the above diff.

Omar, It is better now,

But sometimes points are not according to curvature

and these points are not sorted

[OmarEmaraDev]

Don't worry about the order for now.
If you would like a per-point-curvature sampling, masking a resolution sampling is probably the best approach.

[JacquesLucke]

I think it is ok when the set of inputs for the Evaluate Spline node changes when type is set to Adaptive/Curvature. Having a "Detail" input instead of "Amount" is fine.

[OmarEmaraDev]

@JacquesLucke Alright.Now that I looked at the masking approach above, I wonder if it is better than the integration approach. The way I see it, integration is less stable but more flexible, though I suspect its flexibility is not really needed. Masking is also sufficiently simple that we may even leave it to the user. What do you think?

[3DSinghVFX]

Don't worry about the order for now.
If you would like a per-point-curvature sampling, masking a resolution sampling is probably the best approach.

Yes, this exactly what I want, it looks stable.

[JacquesLucke]

First using the resolution and then removing points is fine. I'm not sure whether masking only based on the local curvature is good enough or whether something like decimation works better.
For decimation you'd have to go over all points and find the one point that adds the least information (is the closest to the straight line between the neighboring points). Then remove that point and search for the next point. This might give better results, but is also harder to implement.

Maybe this kind of decimation could even be a separate node, than no new mode in the Evaluate Spline node would be needed.

[3DSinghVFX]

This paper may help for Adaptive Sampling of Parametric Curves http://ariel.chronotext.org/dd/defigueiredo93adaptive.pdf

[OmarEmaraDev]

@3DSinghVFX I already tried an implementation of the paper that you linked. You can see my implementation here. However, it didn't give good results at all, and it was recursive. Not sure if we can make it iterative. So I quickly abandoned it in favor of the other approachs.

@JacquesLucke I did try this decimate approach as well. It gave similar results to the masking approach. So I don't think it is particularly advantageous.

[3DSinghVFX]

@3DSinghVFX I already tried an implementation of the paper that you linked. You can see my implementation here. However, it didn't give good results at all, and it was recursive. Not sure if we can make it iterative. So I quickly abandoned it in favor of the other approachs.

Okay.

[OmarEmaraDev]

I think the solutions we provided here are already satisfactory. If Kuldeep would like to propose another implementation, feel free to open a pull request.

[Gerstmann-Bradley]

Hi, I wondered why the version including this node has been reverted. Now AN doesn't include this node anywhere.
Would Omar provide me any information about the reason and future plan?

[OmarEmaraDev]

We tried four different methods for doing adaptive sampling. Some were better than others but they all suffered from some issues. I would consider this again if a better implementation came along, anybody is welcome to try that. In the mean time, the curvature masking method described in https://github.com/JacquesLucke/animation_nodes/issues/1330#issuecomment-687180527 can be used.

[Gerstmann-Bradley]

I see, thanks for the respond.