10

I was hoping someone could help me figure out a computationally inexpensive method for detecting kinks in a line drawn parallel to a Bezier curve as you can see here

What I would like to do is be able to determine the intersection of the kink, the segment with a starting point before the intersection and the first segment with an ending point after the kink. This way I can simply remove any unnecessary segments and adjust the first and last segments to meet at the intersection.

Apologies if I'm using the incorrect terms. But as far as I understand it the way I'm positioning these segments is by determining the unit vector of the segments for the Bezier curve (yellow) and multiplying it by the offset and finding the normal vector to create two new start and end points for the offset segment (white).

Mathematics isn't my strong suit so I'm hoping someone can give me a push in the right direction.

EDIT: The image has actually been resized by HTML so if you're having a hard time seeing what I'm talking about here's the direct link: http://i.stack.imgur.com/xtils.png

Nice diagram. What do you want to do in the case where the Bezier itself is self crossing - Mark Ransom 2012-04-03 20:17

I don't need anything special to happen in those cases - Spencer Ruport 2012-04-03 20:22

the guys over at math.stackexchange.com may be better equipped to help you with this - Sam Axe 2012-04-03 21:11

I've x-posted the question there as well. Link: http://math.stackexchange.com/questions/127742/detect-kinks-in-parallel-lines-to-bezier-curves-x-pos - Spencer Ruport 2012-04-03 21:15

The definitive answer is here: http://processingjs.nihongoresources.com/bezierinfo/#offsets : - Magnus Hoff 2012-04-03 22:48

@Magnus - that's good stuff. You should post it as an answer so I can give you an upvote. Are you able to explain it in a little more programmer oriented terms for me? I have a faint understanding of the length estimation he talks about but I'm having trouble understanding how that helps him draw parallel curves - Spencer Ruport 2012-04-04 17:06

@SpencerRuport: No, I am currently unable to explain it further, and that's why I'm not posting it as an answer :) Good luck. Training your math muscles is always valuable exercise ; - Magnus Hoff 2012-04-04 17:49

The "line drawn parallel to a Bezier curve" is actually called a parallel or offset curve. The bad news is that in general, the offset curve for a Bezier curve is a 10-th order polynomial! (source: Kilgard, p. 28) It seems to me what you're trying to compute is self-intersections of these offset curves, but your question isn't clear enough for me to provide an answer - Fizz 2014-08-14 15:32

5

As a first approximation, compute the radius of curvature of your Bezier curve. If the offset is greater or equal to the radius of curvature, you should look for a kink.

Specifically, for a cubic Bezier with control points `P0, P1, P2, P3`

:

```
B(t) = P0 * (1-t)^3 + P1 * 3*t*(1-t)^2 + P2 * 3*t^2*(1-t) + P3 * t^3
-> B'(t) = (P1-P0) * 3*(1-t)^2 + (P2-P1) * 6*t*(1-t) + (P3-P2) * 3*t^2
-> B''(t) = (P2+P0-2*P1) * 6*(1-t) + (P3+P1-2*P2) * 6*t
let: cross2d(p, q) = p.x*q.y - p.y*q.x
then, radius of curvature = |B'(t)|^3 / cross2d(B'(t), B''(t))
```

I have left the radius of curvature in signed form; the sign should indicate the side of the curve on which you can expect the kink.

Note: you can have zero radius of curvature, or infinite radius of curvature; it may be better to compare `|B'(t)|^3`

with `signed_offset * cross2d(B'(t), B''(t))`

instead.

Awesome. This seems like it will work. I'll give it a try and get back to you. Might take me a while. :) + - Spencer Ruport 2012-04-04 17:11

Forgive me if this is a dumb question but like I said mathematics isn't my strong suit. While your cross2d(p, q) function takes note that my points P are x and y coordinates the B, B' and B'' functions do not. Does this mean I just run these once for each axis - Spencer Ruport 2012-04-05 19:28

The

`B(t)`

, `B'(t)`

and `B''(t)`

should be 2-D vectors, just like `P0`

, `P1`

, `P2`

, and `P3`

. Also, note that `|B'(t)|`

should take the length of the 2-D vector. It is probably best to use a `Vector2`

structure (or any existing structure you are currently using for your 2-D points), so you don't have to recompute the Bezier weights multiple times. However, you can write scalar functions and run them for each axis if you want. Just keep in mind that you will need to put them together again when computing the vector length and the cross2d() - comingstorm 2012-04-05 20:40