collission with curved surface

can anybody give me clue for efficiently detecting collission with Bezier curves?
I've made a small demo but it's not fast enough.

The demo looks like quadratic curves, which should have a closed form solution using the quadratic formula. Here's what I would do, it's described as a dynamic collision detection between a bezier curve and a moving dot (zero radius). It will take some more effort to do the case with nonzero radius.

Denote vectors using brackets []. On every frame, the moving dot has a known position [R0], and a place it would like to go, [R1]. This desired position, [R1], is probably described by [R1]=[R0]+deltaT*[Velocity] or something like that. Construct a ray that starts at [R0] and shoots towards [R1].

Code:

---

[Ray(u)] = [R0] + u*( [R1]-[R0] )

---

Where U is a parametric variable that gives the distance along the Ray. U=0 corresponds to [R0], and U=1 is [R1]. Another way to describe this set of points, is that every point [P] on the ray must satisfy:

Code:

---

[N] dot [P] = [N] dot [R0]
// (**)

---

Where:

Code:

---

[N] = [Z] cross ( [R1] - [R0] )
// This operation rotates the ray direction by 90 degrees in the xy plane.
// Sometimes it's called the perproduct.

---

What you want to do, is substitute in the parametric (polynomial) form of the Bezier curve and find what values of its parameter satisfy that equation. All the points on the Bezier curve are defined by:

Code:

---

[Bezier(v)] = (1-v)^2 [B0] + 2v(1-v) [B1] + v^2 [B2]

---

Where [B0], [B1] and [B2] are the control points and v is the parametric variable. V=0 pops out [B0], v=1 pops out [B2], and anything in between sweeps along the curvy curve. Substitute this expression for [P], in equation (**).

Code:

---

[N] dot ( (1-v)^2 [B0] + 2v(1-v) [B1] + v^2 [B2]
 ) = [N] dot [R0]

---

With some rearranging, this is a quadratic equation a*v^2+b*v+c. Solve it using the quadratic formula:

Code:

---

v^2 * ( -[N].[B0] - 2[N].[B1] + [N].[B2] )    // that's a*v^2.
+v * ( 2[N].[B1] )                        // that's b*v.
+ (-[N] dot [R0] )        // that's c.

---

Lots of things could happen here:
If (b^2-4ac) < 0 there are no intersections.
Otherwise, let v0 and v1 be the solutions to av^2+bv+c.
If (vi < 0) or (vi > 1), then this is a collision that occurs outside the extents of the Bezier curve and should be ignored.
Otherwise, establish a value of u for this value of v. To do this, compute [Bezier(vi)], then use a dot product against the ray direction [R1]-[R0].

Code:

---

[Bezier(vi)] = (1-vi)^2 [B0] + 2vi(1-vi) [B1] + vi^2 [B2]
ui = ( [Bezier(vi)]-[R0] ) dot ([R1]-[R0]) / lengthSquared
Where:
lengthSquared = ([R1]-[R0]) dot ([R1]-[R0])

---

This will pop out (up to) 2 values of ui, because the ray might intersect the curve in (up to) two places. If (ui < 0) or (ui > 1), ignore it because it is an intersection that occurs outside the extents of the ray. The intersection of interest is the one with the smallest positive value of ui - it's the one that would occur first as the dot sweeps from [R0] to [R1].

Making this work for nonzero dot radius involves an additional step, you'll need to take the original bezier curve and offset it by the radius before you push it through the calculation. Unfortunately, it's not clear to me that such a curve would still be a bezier curve. Instead, I would just take the original curve, offset the two endpoints [B0] and [B2] by the radius value, and then compute a new control point by intersecting the two new endpoint tangents. This gives you a curve with the correct offset height and slope at both ends. (It's not clear to me whether or not the offset height near v=0.5 will be correct, but for curves with shallowish curvature this should work reasonably well).

HTH, please post comments on whether or not it works.

thanks for replying .I'will surely give it a try

i got it working but i think that eqn 6 should be

Code:

---

v^2 * ( [N].[B0] - 2[N].[B1] + [N].[B2] ) // that's a*v^2.
+v * ( 2[N].[B1]-2[N].[B0] ) // that's b*v.
+ ([N].[B0]-[N].[R0] ) // that's c.

---

anyway you nicely illustrated it.
thanks again

Yes I think that first [B0] term didn't get FOIL'ed out properly. Thank you for the correction. Glad you got it working! :yarr:

Have you tried the nonzero radius case? I would especially like to see how this one works in practice. Also, is this method any faster than your original solution (and how did it work)?

i'm working on it.I will post if i get any further.

the above mentioned method worked fine for zero radius case so I tried using it for circles but couldn't go beyond (Could you explain it a bit clearly?)So
I dropped out the previous method and used another.
this one makes the the use of cubic solver(so much slower than previous method)
the values that need to be given to cubic solver are

Code:

---

var c0=A.Dot(b)-B.Dot(b)-A.Dot(A)+A.Dot(B);//Constant term
var c1=2*B.Dot(b)-6*A.Dot(B)-A.Dot(b)+3*A.Dot(A)-b.Dot(C)+A.Dot(C)+2*B.Dot(B);// Coefficient of t
var c2=9*A.Dot(B)-3*A.Dot(A)-3*A.Dot(C)-6*B.Dot(B)+3*B.Dot(C);// Coefficient of t^2
var c3=4*B.Dot(B)-4*A.Dot(B)+A.Dot(A)-4*B.Dot(C)+2*A.Dot(C)+C.Dot(C);//
Coefficient of t^3

---

after finding the root.substituting it in the bezier curve gives the point that is nearest to the given point.
In above equation
the controlPoint of curve are A,B,C and b is the any arbitrary poin that we are checking for.

cubic roots are way harder than quadratic so i simply used this http://members.shaw.ca/flashprogramm...yBundle1.8.zip

I'll try to explain what I meant a bit better.

One way to collide a bezier curve against a circle with nonzero radius R would be to offset the bezier curve by R and then do the curve/point collision against the offset curve. Unfortunately, I don't think that such an offset curve is actually a bezier curve anymore.

Instead, I was thinking that you could fake this offset curve with another bezier curve that is constructable from the one you already have. You have a bezier curve [Bezier(v)] defined by three control points [B0], [B1] and [B2]. You want to compute three new control points, [B0'], [B1'] and [B2'], that approximate the offset curve with some other curve, [Bezier'(v)].

http://esl.eng.ohio-state.edu/~rac/quake/bezier0.gif

The first endpoints, [B0'], can be offset from [B0] by taking the tangent at v=0, rotating it by 90 degrees, rescaling it to be R units in length. Let [A] denote the displacement vector to get to [B0'] from [B0]:

Code:

---

[A] = [Z] CROSS ( [B1]-[B0] )
[A].normalize();
[A] = [A] * R

---

Then,

Code:

---

[B0'] = [B0]+[A]

---

The [B2'] control point is offset from [B2] in a similar manner. The only difference is that the tangent at v=1 is [B2]-[B1].

http://esl.eng.ohio-state.edu/~rac/quake/bezier1.gif

The middle control point, [B1'], comes from the intersection of two lines. Take the original tangents of the (unoffseted) curve and offset them to pass through [B0'] and [B2']. Define [B1'] as their intersection. Here's a gist.

Code:

---

// Compute the two tangent vectors.
[T01] = ([B1]-[B0]).normalize();
[T12] = ([B2]-[B1]).normalize();
// Represent the righthand line (12) in implicit plane form.
[N12] = [Z] CROSS [T12]
D12 = [N12] DOT [B2'];
// Project/cast a ray from [B0'], along [T01], onto this plane.
x = ( D12 - [N12] DOT [B0'] ) / ( [N12] DOT [T01] )
[B1'] = [B0'] + x * [T01]

---

http://esl.eng.ohio-state.edu/~rac/quake/bezier2.gif

The features of the bezier curve [Bezier'(z)] defined by [B0'], [B1'] and [B2'] are:
i. Bezier'(v) is offset by exactly R units from Bezier(v) at v=0 and v=1, so it starts and ends in the correct location.
ii. Bezier'(v) has the same slope as Bezier(v) at v=0 and v=1, so it points in the right directions at the starts and ends.
iii. In between v=0 and v=1, the curve is not offset by R units. I think the error in this offset will be maximum at v=1/2. The sketch is exaggerates this error a bit. As the curve gets more "pointy" (that is, the angle <012 gets further from pi) this error will get worse and worse. So I would keep the curves shallow.

There's probably a smarter way to pick [B012'], this is just one option.

It might work OK, but I'm really not satisfied very much with this solution. I tried to find an exact and closed form solution for the nonzero radius case but it appears to require finding roots of a quartic polynomial. I didn't complete the solution once this became apparent. It might still be workable using newtons method, because you're finding the zeros of a function that you know in closed form and you know its derivative in closed form. Food for thought.

A completely different alternative might be to restrict yourself to circular arcs instead of bezier curves, then everything is easy again. Myself, I never go beyond straight lines! :eek:

thanks i will read it.
I created a small demo with the cubic polynomial solver. here
I haven't tested the speed but it faster than the demo i posted earlier.

Hi,
I just posted an article about this:
http://blog.gludion.com/2009/08/dist...ier-curve.html

I think foam engine by newblack handles circle-bezier collisions (in fact, anything else - bezier, too), so take a look.