Bezier Curve in Modern C++

Question

Could someone update this into modern C++ so I could better understand what is going on?

https://stackoverflow.com/a/21642962/10470367

I've been trying to replace the pointer to points with an std::vector to remove the necessity of manual mem allocation.

I've also been trying to utilize for (auto& foo : foos), but I just cannot follow the logic for this math.

Also, I understand this would improve its optimization a bunch by updating to modern C++.

This is a strange question. I would leave the link to the original question, but post the code here with the specific query about what you have trouble with. This almost seems like a "my code don't work, what's wrong? " kind of question (which is off topic), but I know it's not. If this were a link to code on a non-StackExchange site it would be downvoted and possibly closed. — Steve, Nov 09 '18 at 06:30
@Steve I see your point. I don't think it's off-topic, but I agree that at least a current-best-effort example would be good. I think we're going to see more of these questions as C++17 (and soon C++20) matures. — jonspaceharper, Nov 09 '18 at 10:15
@JonHarper: The linked code isn't just bad by C++17 standards. It's not even good C++98 code. — MSalters, Nov 09 '18 at 11:27

Yakk - Adam Nevraumont · Answer 1 · 2018-11-09T12:17:06.427

point getBezierPoint( span<const point>  points, float t ) {
  vector<point> tmp = as_vector(points);
  while (tmp.size()>1) {
    for (auto k:indexes_of(tmp).except_last())
        tmp[k] = tmp[k] + t * ( tmp[k+1] - tmp[k] );
    tmp.resize(tmp.size()-1);
  }
  return tmp[0];
}

span, as_vector and point should be obvious.

Here is indexes_of:

template<class It>
struct range_t{
  It b,e;
  It begin()const{return b;}
  It end()const{return e;}
  range_t except_last(std::size_t i=1)const{
    auto r = *this;
    r.e-=i;
    return r;
  }
};
template<class It>
range_t<It> range(It be, It e){ return {std::move(b),std::move(e)}; }
template<class X>
struct indexer_t {
  X x;
  X operator*()const{return x;}
  void operator++(){ ++x; }
  void operator--(){ --x; }
  void operator+=(std::ptrdiff_t i){ x+=i; }
  void operator-=(std::ptrdiff_t i){ x-=i; }
  friend bool operator==(indexer_t const&lhs, indexer_t  const& rhs){return lhs.x==rhs.x;}
  friend bool operator!=(indexer_t const&lhs, indexer_t  const& rhs){return lhs.x!=rhs.x;}
};
range_t<indexer_t<std::size_t>> count( std::size_t start, std::size_t finish ){
  return {{start}, {finish}};
}
template<class C>
auto indexes_of(C&&c) { return count(0, c.size()); }

or somesuch.

While this works, it's somewhat inefficient. It re-generates `indexes_of(tmp)`. This style also makes it hard for the optimizer to generate SIMD code (e.g. AVX or NEON). — MSalters, Nov 09 '18 at 11:33
@msal indexes of tmp is the numbers 0 and size-1. Just 2 numbers. — Yakk - Adam Nevraumont, Nov 09 '18 at 12:16
Of course, but `size` keeps changing due to that `.resize` in the outer loop. — MSalters, Nov 09 '18 at 12:20

score 0 · Answer 2 · answered Nov 09 '18 at 11:50

"Also, I understand this would improve its optimization a bunch by updating to modern C++"

Actually, the code looks like the best optimization is vectorization, e.g. using AVX on x86 or NEON on ARM. And that works best if the vectorizer can work with indexes and clear bounds. So:

vec2 getBezierPoint( std::vector<vec2> points, float t ) {
    auto const maxi = points.size()-1;
    for(int i = 0; i != maxi; ++i) 
    {
        auto const maxj = maxi-i;
        for (int j = 0; j < maxj; ++j)
            points[j] += t * ( points[j+1] - points[j] );
    }
    return points[0];
}

However, note that the main optimization problem here is that you only get one point at a time. You typically want the whole curve (from t=0.0 to t=1.0) and then this is doing quite a bit of redundant work - all those loop bounds are identical for all t values.

Bezier Curve in Modern C++

2 Answers2