Arc length parametrization example interpolation understanding

Processing Coding Questions
1

https://github.com/processing/processing-docs/blob/master/content/examples/Topics/Curves/ArcLengthParametrization/BezierCurve.pde

I am having trouble understanding the interpolation of two surrounding indexes in equidistantPoints function. How is the interpolation working giving equidistant points? Also what is segment count actually doing? There are supposed to be n segments for n+1 points but points are 80 & segment count is 100?

1 Like
2

Could you explain your question more thoroughly? If possible, isolate the code-snippet in question and add it to your post

3 
// Returns an array of equidistant point on the curve
  PVector[] equidistantPoints(int howMany) {
    
    PVector[] resultPoints = new PVector[howMany];
    
    // we already know the beginning and the end of the curve
    resultPoints[0] = v0.get();
    resultPoints[howMany - 1] = v3.get(); 
    
    int arcLengthIndex = 1;
    for (int i = 1; i < howMany - 1; i++) {
      
      // compute wanted arc length
      float fraction = (float) i / (howMany - 1);
      float wantedLength = fraction * curveLength;
      
      // move through the look up table until we find greater length
      while (wantedLength > arcLengths[arcLengthIndex] && arcLengthIndex < arcLengths.length) {
        arcLengthIndex++;
      }
      
      // interpolate two surrounding indexes
      int nextIndex = arcLengthIndex;
      int prevIndex = arcLengthIndex - 1;
      float prevLength = arcLengths[prevIndex];
      float nextLength = arcLengths[nextIndex];
      float mappedIndex = map(wantedLength, prevLength, nextLength, prevIndex, nextIndex);
      
      // map index from range (0, SEGMENT_COUNT) to parameter in range (0.0, 1.0)
      float parameter = mappedIndex / SEGMENT_COUNT;
      
      resultPoints[i] = pointAtParameter(parameter);
    }
    
    return resultPoints;
  }

I am finding interpolation of surrounding indexes in the above function bit tricky to understand.How does the mapping provides equidistant points?

class BezierCurve {
  
  private final int SEGMENT_COUNT = 100;
  
  private PVector v0, v1, v2, v3;
  
  private float arcLengths[] = new float[SEGMENT_COUNT + 1]; // there are n segments between n+1 points
  
  private float curveLength;

Also I tried varying the segment count in the beziercurve class but couldn’t really see any visual change unless I drastically reduced the segment count. It then behaves the same way as standard parametrization. The points taken are 80. So segment count should be technically 79 but here its value is 100. I cannot fathom the direct visual interpretation of segment count and if its value as 100 is arbitrary or in relation to points?

1 Like
4

Where did you get the value of 80 for the number of points? I am not sure how 80 is relevant to this discussion…

Have a look at this simple demo. As you can see, float t = i / float(steps); defines a fraction of the length of the curve to draw the point at. Drawing points as incremental fractions along the curve guarantees the equidistant feature as advertised by the function (or at best, an approximation in a worse case scenario)

The algorithm above is based on this simple concept.

This would be my interpretation after reviewing this code:

Initially there is a table built where the curve’s length is calculated per index and stored assuming there are 100 segments. I see this as an implicit statement and it should be considered as hidden implementation. This is a way to build a model where one has a curve represented with 100 segments. I would guess 100 is a good number for most practical cases and if you try hard, you can find situations/conditions were 100 might not be enough to create an adequate model. The key point is that you have a model and you do the interpolation using this model instead of calculating infinitesimal segments on any curve. If we think about science, natural phenomena are represented by models and models are accepted only if they are valid within practical ranges.

The second part of this algorithm is described by the following lines:

  float fraction = (float) i / (howMany - 1);
  float wantedLength = fraction * curveLength;
  
  // move through the look up table until we find greater length
  while (wantedLength > arcLengths[arcLengthIndex] && arcLengthIndex < arcLengths.length) {
    arcLengthIndex++;
  }

This is tricky. What happens if you have less than 100, exactly 100 or more than 100 for npoints? Well, if you choose 100, I will assume that the calculation will be based on the actual calculated segments. If you choose npoints to be less than 100, then the interpolation is based on about these npoints. The algorithm above will choose the closest points that aligns to the right segments. Think this way: for given npoints, the algorithm will choose the best npoints out of 100 from the initial model to perform the calculation. This is not an issue because each point selected is not a coordinate but a length. The index arcLengthIndex will pick the length of the curve from the table built from the initial model.

Now, if you have npoints that is larger than 100, that should not be a problem. Let’s say you have npoints=200 meaning than there are two points that the function above will return the same arcLengthIndex. The third part of the code will do a mapping based on a fraction:

float mappedIndex = map(wantedLength, prevLength, nextLength, prevIndex, nextIndex);

As you see, wantedLength is a length based on npoints, which should be a value between prevLength, nextLength. The mappIndex will be a linear interpolation between prevIndex, nextIndex and proportional to the fraction of wantedLength within the range of [ prevLength, nextLength]. For example, if wantedLength is half way withing the range, then mappindex will return exactly the half value between prevIndex, nextIndex. Finally, mapIndex is normalized to a value between 0 and 1 using the following operation: float parameter = mappedIndex / SEGMENT_COUNT;. This is to say that mappedIndex is a value between 0 and 100 and you divide by 100 to get a value between 0 and 1.

The above explanation also applies when npoints is 100 or less than 100.

The final step invokes resultPoints[i] = pointAtParameter(parameter); to calculate the actual point as a coordinate.

I would like to add the following posts that are relevant (check the first one for sure):

I hope this helps.

Kf

2 Likes
5

Thanks @kfrajer for detailed explanation. I was actually getting confused by correlating the npoints(in eg its 80) & segment count. That made it difficult to understand the further expressions. Its bit tricky to understand though.