0

There are numerous questions on checking if two Bezier curves intersect, the most prominent being this one. However, this answers the question of checking if

B1(t1)=B2(t2)

Where B1 and B2 are Bezier curves. We may thus have that t1 is not t2. But I want to check for collision, that is

B1(t)=B2(t)

So they must intersect at the same time t. Is there an algorithm that can quickly detect this without having to go over all times t, i.e. is it possible to figure it out from just the control points?

Thomas Wagenaar
  • 6,489
  • 5
  • 30
  • 73
  • 1
    Your case is actually simpler as you have a single variable for a single equation. While the referred topic had to find two variables for a single equation. A piece of paper or WolframAlpha may be your next stop. – tevemadar Sep 29 '21 at 12:01
  • 1
    I'm not sure I understand what you think this will let you do: collisions and intersections are the same thing in geometric programming. Two curves intersection at the same `t` value is a special case, but it's _still_ an intersection, it's not suddenly something else. – Mike 'Pomax' Kamermans Sep 29 '21 at 20:07

1 Answers1

2

Your restriction means that you can just solve for t for a single dimension, then verify in all others. I.e. solve Bx₁(t) = Bx₂(t) since there's only one variable, and if that yields (a) t value(s) in the interval [0,1], plug the found value(s) into By(t) without needing to solve for anything, to see if you get another equality. If so, plug it into Bz(t) to verify, etc. etc. for however many dimensions your Bezier is defined for.

With the caveat that solving for t means you're performing root finding, which means that any fifth order expression or higher can't be solved symbolically (see the Abel-Ruffini theorem for why that is) and you'd have to "solve" for t using numerical analysis instead.

Although I'm not sure what doing this would get you: it's not a particularly useful constraint, and will conclude that "there is no collision" for almost every possible situation in which a human would conclude that there very much is a collision. You'd need to get otherworldly lucky for two arbitrary curves to coincide at the exact same t value. Or you'd have to use curves specifically designed to intersect at the same t value (in which case there's nothing to calculate, you already know they do, and where ;)

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153