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(Span<float> lengths, | |||||
| const bool cyclic, | |||||
| const int count, | |||||
| ResultSamples &result) | |||||
| { | |||||
| BLI_assert(lengths.size() >= 1); | |||||
| BLI_assert(std::is_sorted(lengths.begin(), lengths.end())); | |||||
| const int edges_size = lengths.size(); | |||||
| const int points_size = cyclic ? edges_size : edges_size + 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_size; | |||||
| #endif | |||||
| if (count == 1) { | |||||
| return; | |||||
| } | |||||
| const float total_length = lengths.last(); | |||||
| const float sample_length = total_length / (count - (cyclic ? 0 : 1)); | |||||
JacquesLucke: Maybe call this `step_length`? | |||||
| /* Start at the first sample to avoid storing the first, which always corresponds 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_size - 1)) { | |||||
| const float next_length = lengths[i_src]; | |||||
| const float segment_length = next_length - prev_length; | |||||
| /* Add every sample that fits in this edge. */ | |||||
JacquesLuckeUnsubmitted Done Inline Actionsedge -> segment? JacquesLucke: `edge` -> `segment`? | |||||
| while (sample_length * i_dst <= next_length) { | |||||
JacquesLuckeUnsubmitted 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… | |||||
HooglyBooglyAuthorUnsubmitted 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… | |||||
| const float length_in_segment = sample_length * i_dst - prev_length; | |||||
| const float factor = length_in_segment / segment_length; | |||||
| 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 (sample_length * i_dst < total_length) { | |||||
| const float length_in_segment = sample_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?