Changeset View
Standalone View
source/blender/blenlib/intern/length_parameterize.cc
- This file was added.
| /* SPDX-License-Identifier: GPL-2.0-or-later */ | |||||
| #include "BLI_length_parameterize.hh" | |||||
| namespace blender::length_parameterize { | |||||
| void create_uniform_samples(const Span<float> lengths, | |||||
| const bool cyclic, | |||||
| const int count, | |||||
| ResultSamples &result) | |||||
| { | |||||
| BLI_assert(count > 0); | |||||
| BLI_assert(lengths.size() >= 1); | |||||
| BLI_assert(std::is_sorted(lengths.begin(), lengths.end())); | |||||
| const int segments_num = lengths.size(); | |||||
| const int points_num = cyclic ? segments_num : segments_num + 1; | |||||
| result.indices.clear(); | |||||
| result.factors.clear(); | |||||
| result.cyclic_samples.clear(); | |||||
| result.indices.reserve(count); | |||||
| result.factors.reserve(count); | |||||
| result.cyclic = cyclic; | |||||
| #ifdef DEBUG | |||||
| result.src_points_size = points_num; | |||||
| #endif | |||||
| if (count == 1) { | |||||
| return; | |||||
| } | |||||
| const float total_length = lengths.last(); | |||||
| const float step_length = total_length / (count - (cyclic ? 0 : 1)); | |||||
JacquesLucke: Maybe call this `step_length`? | |||||
| /* Start at the second sample to avoid storing the first index and the first factor, | |||||
| * which always correspond exactly to the first source point anyway. */ | |||||
| int i_dst = 1; | |||||
| /* Store the length at the previous point in a variable so it can start out at zero | |||||
| * (the lengths array doesn't contain 0 for the first point). */ | |||||
| float prev_length = 0.0f; | |||||
| for (const int i_src : IndexRange(points_num - 1)) { | |||||
| const float next_length = lengths[i_src]; | |||||
| const float segment_length = next_length - prev_length; | |||||
| if (segment_length == 0.0f) { | |||||
| continue; | |||||
Done Inline Actionsedge -> segment? JacquesLucke: `edge` -> `segment`? | |||||
| } | |||||
Not Done Inline ActionsMight be possible to optimize this loop a bit more.
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). JacquesLucke: Might be possible to optimize this loop a bit more.
* If I'm not mistaken there should be a… | |||||
Done Inline ActionsI 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. 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. HooglyBoogly: I avoided the repeat division here, that might be an improvement.
I looked into the other… | |||||
| /* Add every sample that fits in this segment. */ | |||||
| const float segment_length_inv = 1.0f / segment_length; | |||||
| while (step_length * i_dst <= next_length) { | |||||
| const float length_in_segment = step_length * i_dst - prev_length; | |||||
| const float factor = length_in_segment * segment_length_inv; | |||||
| result.indices.append_unchecked(i_src); | |||||
| result.factors.append_unchecked(factor); | |||||
| i_dst++; | |||||
| } | |||||
| prev_length = next_length; | |||||
| } | |||||
| /* Deal with the samples for the last cyclic segment separately. */ | |||||
| if (cyclic) { | |||||
| const float segment_length = lengths.last() - lengths.last(1); | |||||
| while (step_length * i_dst < total_length) { | |||||
| const float length_in_segment = step_length * i_dst - prev_length; | |||||
| const float factor = length_in_segment / segment_length; | |||||
| result.cyclic_samples.append(factor); | |||||
| i_dst++; | |||||
| } | |||||
| } | |||||
| } | |||||
| } // namespace blender::length_parameterize | |||||
Maybe call this step_length?