Does Piecewise Bezier curve pass vertical line test?

Question

Consider a piecewise cubic Bezier curve with N segments, defined in terms of 4N control points. How can I determine whether this curve passes the Vertical Line Test? That is: do there exist points x,y1,y2 such that y1!=y2 and both (x,y1) and (x,y2) lie on the curve? Additionally, it would be nice but not essential to return the values of the points x,y1,y2 if such points exist.

In principle, one could just evaluate the curve explicitly at a large number of points, but in my application the curves can have a large number of segments so this is prohibitively slow. Thus I am looking for an algorithm that operates on the control points only, and does not rely on explicitly evaluating the curves at a large number of points.

@Mike 'Pomax" Kamermans right, but a curve could still fail the test without having an inflection. consider x(t)=(t-1/2)^2. The second derivative is constant x''(t)=2 so there are no inflection points, but it fails the test because x(1/4)=x(3/4). — Mike Hawk
I've posted an actual answer - I was also thinking of the wrong algorithm, so the answer actually gives the right one (no second derivatives, we're not looking for inflections but maxima/minima) — Mike 'Pomax' Kamermans

Mike 'Pomax' Kamermans Mike 'Pomax' Kamermans · Accepted Answer · 2021-07-15T16:56:13

Closed curves will fail your test by definition, so let's look at open curves: for a curve to fail your vertical line test, at least one segment in your piecewise cubic polyBezier needs to "reverse direction" along the x-axis, which means its x component needs to have extrema in the inclusive interval [0,1].

For example, this curve doesn't (the right side shows the component function for x, with global extrema in red and inflections in purple):

(Also note that we're only drawing the [0,1] interval, but if we were to extend it, those global extrema wouldn't actually be at t=0 and t=1. This is in fact critically important, and we'll see why, below)

This curve also doesn't (but only just):

But this curve does:

As does this one. Twice, in fact:

As does a curve "just past its cusp":

Which is easier to see when we exaggerate it:

This means we need to find the first derivative, find out where it's zero, and then make sure that (because Beziers can have cusps) the sign of that derivative flips at that point (or points, as there can be two).

Turns out, the derivative is trivially not-even-really-computed, so for each segment we have:

w = [x1, x2, x3, x4]

Bx(t) = w[0] * (1-t)³ + 3 * w[1] * t(1-t)² + w[2] * t²(1-t) + w[3] * t³

// bezier form of the derivative:

v = [
  3 * (w[1] - w[0]),
  3 * (w[2] - w[1]),
  3 * (w[3] - w[2]),
]

Bx'(t) = v[0] * (1-t)² + 2 * v[1] * t(1-t) + v[2] * t²

Which we can trivially rewrite to polynomial form:

a = v[0] - 2*v[1] + v[2]
b = 2 * (v[1] - v[0])
c = v[0]

Bx'(t) = a * t² + b * t + c

So we find the roots for that, which is a matter of applying the quadratic formula, which gives us 0, 1, or 2 roots.

if (a == 0) there are no roots

denominator = 2 * a
discriminant = b * b - 2 * denominator * c

if (discriminant < 0) there are no (real) roots

d = sqrt(discriminant)

t1 = -(b + d) / denominator
if (0 ≤ t1 ≤ 1) then t1 is a valid root

t2 = (d - b) / denominator
if (0 ≤ t2 ≤ 1) then t2 is a valid root

If there are no (real) roots, then this segment does not cause the curve to fail your vertical line test, and we move on to the next segment and repeat until we've either found a failure, or we've run out of segments to test.

If it's 1 or 2 roots, we check that the signs of Bx'(t-ε) and Bx'(t+ε) for some very small value of ε differ (because we want to make sure we don't conclude that the above curve with a cusp fails the test: it has a zero derivative but it "keeps going in the same direction" across that root instead of flipping direction). If they do, this segment is (one of) the segment(s) that makes your curve fail your vertical line test.

Also, note that we're testing even if the root is at 0 or 1: the piecewise curve might inflect "across segments", and we can take advantage of the fact that we can evaluate Bx'(t) for t = -ε or t = 1+ε to see if we flip direction, even if we never draw the curve prior to t=0 or after t=1.

Does Piecewise Bezier curve pass vertical line test?

2 Answers