Page MenuHome

Curves: Add length cache, length paramerterize utility
ClosedPublic

Authored by Hans Goudey (HooglyBoogly) on Mar 19 2022, 5:38 AM.

Details

Summary

This commit adds calculation of lengths along the curve for each
evaluated point. This is used for sampling, resampling, the "curve
parameter" node, and potentially more places.

The length calculation and calculation of uniform samples is
generalized to a new utility header in blenlib, which can find evenly
spaced samples along a sequence of points, and use linear interpolation
to move data from those points to the samples. Making the utility more
general aligns better with the more functional approach of the new
curves code and makes the behavior available elsewhere.

Diff Detail

Repository
rB Blender

Event Timeline

Hans Goudey (HooglyBoogly) requested review of this revision.Mar 19 2022, 5:38 AM
Hans Goudey (HooglyBoogly) planned changes to this revision.
Hans Goudey (HooglyBoogly) created this revision.
Hans Goudey (HooglyBoogly) retitled this revision from BLI: Add length parameterization utility to Curves: Add length cache, length paramerterize utility.
Hans Goudey (HooglyBoogly) edited the summary of this revision. (Show Details)

Incorporate use of the utility in curves into this patch

Hans Goudey (HooglyBoogly) set the repository for this revision to rB Blender.

Small fix

Jacques Lucke (JacquesLucke) requested changes to this revision.Mar 27 2022, 12:42 PM
Jacques Lucke (JacquesLucke) added inline comments.
source/blender/blenkernel/BKE_curves.hh
282

"necessarily single threaded [per curve]"

source/blender/blenkernel/intern/curves_geometry.cc
728

While the interface is generally fine, i's probably not very efficient. Accessing ->cyclic() for every curve adds a lot of overhead.

748

A comment for why this is the total_size what be good.

source/blender/blenlib/BLI_length_parameterize.hh
25

I think it is not obvious that a curve cannot be cyclic when it only has two points. I don't see a fundamental reason for why this should be the case. If there is a reason for this behavior, it should be mentioned here.

96

Even when count is zero or one?

source/blender/blenlib/intern/length_parameterize.cc
33

Maybe call this step_length?

45

edge -> segment?

46

Might be possible to optimize this loop a bit more.

  • If I'm not mistaken there should be a closed-form expression to compute how often the loop has to run.
  • Avoid repeated division by the same number (use multiplication instead).

Furthermore, it's likely necessary to deal with floating point accuracy issues here to make sure that the expected amount of samples is actually generated and not more or less. Although, to be fair, I didn't manage to generate a failing test yet. Having a closed form solution might help with the analysis a bit (and would even allow for some parallelization when count is very large).

source/blender/blenlib/tests/BLI_length_parameterize_test.cc
165

Maybe test if the computed result is actually correct?

This revision now requires changes to proceed.Mar 27 2022, 12:42 PM
source/blender/blenlib/tests/BLI_length_parameterize_test.cc
60

Would maybe be good to have an example where all segments have the same length. This doesn't really test if the code does actually creates uniform samples.

Hans Goudey (HooglyBoogly) marked 8 inline comments as done.

Update based on most of the review comments (still a couple remaining)

source/blender/blenkernel/intern/curves_geometry.cc
728

Yeah. It's definitely not idea, especially with no caching of name lookups in CustomData. Adding cyclic as an argument doesn't feel great either though, since that allows the user to potentially access bad values for those last floats.

I wonder if we can make ->cyclic() fast enough that calling it here isn't unreasonable. Here are two more options though:


A function in the bke::curves namespace

namespace blender::bke::curves {
IndexRange lengths_range_for_curve(IndexRange points, int curve_index, bool cyclic)
{
  return ...
}

I'm not sure about that though. The other stuff in the bke::curves namespace seems almost general enough that it could move to blenlib, but this is a bit more specific to CurvesGeometry.


A static method on CurvesGeometry

static CurvesGeometry::lengths_range_for_curve(IndexRange points, int curve_index, bool cyclic
{
  return ...
}

I think I prefer this method?

source/blender/blenlib/BLI_length_parameterize.hh
25

I think I was copying the logic from existing curve code, but I also can't think of a fundamental reason, at this level.
At a higher level, for a two point poly curve, cyclic might not make sense since since it can't be reflected visually.

96

Good point, I adjusted the comment. And the function expects the count to be greater than zero so I added that too.

source/blender/blenlib/tests/BLI_length_parameterize_test.cc
60

Good idea! It's implicitly tested in the "expected" values, but I added an explicit check for uniform lengths to a couple of them too. (the distances between consecutive sampled points in Cartesian space aren't necessarily uniform in the general case).

165

I added that as a "does this compile" test, but I might as well! :)

source/blender/blenkernel/intern/curves_geometry.cc
728

I think passing in some redundant data for performance reasons is fine. The function should assert that the passed in data is correct. A comment can mention that this data is passed in for performance reasons.

Trying to make cyclic() fast enough for this use case would be an optimization at the wrong end for me. There shouldn't be a need to construct a new VArray for every curve.

source/blender/blenlib/BLI_length_parameterize.hh
25

Well, there are always ways to visualize it. We could just use the arrows that you see when adjusting the tilt.

Then better mention that reason in a comment.

Hans Goudey (HooglyBoogly) marked 3 inline comments as done.
  • Test color results
  • Pass cyclic separately to existing function
  • Add some comments
source/blender/blenlib/BLI_length_parameterize.hh
25

Honestly I don't remember the reasoning well enough to document it. I'll just remove that 2 point check for now I think. If it becomes a problem we can add it back.

source/blender/blenlib/intern/length_parameterize.cc
46

I avoided the repeat division here, that might be an improvement.

I looked into the other comments for a while and didn't find a nice solution though. Anything I added to change to using a for loop significantly increased the complexity, and also requires more processing with epsilons, etc.
As far as I know, the current method with less than or equal comparison is fairly solid, at least it's been tested with current curve code a fair amount.

I can continue looking into this if you feel strongly, right now I'd prefer to keep this as is though, if it's okay with you.

This revision is now accepted and ready to land.Mar 29 2022, 7:18 PM

I actually ended up mostly making the changes you suggested inline. I also removed the ResultSamples class and used index and factor arrays directly. Turns out that's a bit simpler anyway. And gives more flexibility about where to put the data.