I know how to draw it :) And some theory and stuff, but no math...
So code, yep, I'm understand math more clearly when I look at code, so the way for me is understand how it works is transform to code, and then read it, but problem is that I'm not so quite to solve equations like Z = ax+bx+cx+d or something like that...
I can solve solution like ax+b=0
equation sample : kx+b=0 two components should be known
solution for x if known k and b
kx=0-b
x=(-b/k)
solution for k if known x and b
k = b/x
solution for b if known x and k
b = 0-kx
I try to figure out something for ax+bx+c=0
like place bx+c=0 as t then solve ax+t=0
but no luck...
But it's just equations, what the deal with vector here? What we searching by line equation ax+bx+c=0 where we get "C" and so on?
[Edited by - Lolmen on December 3, 2007 8:27:24 PM]
Line segment intersecting curve
The equation of the line has two unknown: x and y.
The equation you have written (ax+bx+c=0) has one unknown (x) and the solution is -c/(a+b).
The equation of the line has infinite solutions (all the coordinates of the points in the line are solutions of the equation).
But in this case you don’t need to solve the equation. You have to use the first part of the equation to calculate the distance from the line to a given point (for example the first control point).
Have you ever listened about the de Casteljau algorithm? Do you know how to subdivide a bézier curve in two or more bézier curve? Do you know what the Convex Hull is?
My fear is that if I give you the code you will probably use it without any understanding.
The equation you have written (ax+bx+c=0) has one unknown (x) and the solution is -c/(a+b).
The equation of the line has infinite solutions (all the coordinates of the points in the line are solutions of the equation).
But in this case you don’t need to solve the equation. You have to use the first part of the equation to calculate the distance from the line to a given point (for example the first control point).
Have you ever listened about the de Casteljau algorithm? Do you know how to subdivide a bézier curve in two or more bézier curve? Do you know what the Convex Hull is?
My fear is that if I give you the code you will probably use it without any understanding.
>Have you ever listened about the de Casteljau algorithm?
Nope...
>Do you know how to subdivide a bézier curve in two or more bézier curve?
I know that solution can be found without subdivisions, recursion will be costly thing...
>Do you know what the Convex Hull is?
Well, cheap is AABB, but best is OBB, using polygons bad idea.
Do Bezier clipping use one of these two first algorithms?
Nope...
>Do you know how to subdivide a bézier curve in two or more bézier curve?
I know that solution can be found without subdivisions, recursion will be costly thing...
>Do you know what the Convex Hull is?
Well, cheap is AABB, but best is OBB, using polygons bad idea.
Do Bezier clipping use one of these two first algorithms?
Bézier clipping is a recursive algorithm that involve the subdivision of the Bézier curve.
You have to find the intersection between the convex hull and the y=0 line. If you call t0 and t1 the first and the last intersection, you subdivide the Bézier curve in 3 parts: the part with the parameter less than t0, the part with parameter between t0 and t1 and the last part of the Bézier curve. You then do the same things with the second part until t1-t0 is less than a given number.
You have to find the intersection between the convex hull and the y=0 line. If you call t0 and t1 the first and the last intersection, you subdivide the Bézier curve in 3 parts: the part with the parameter less than t0, the part with parameter between t0 and t1 and the last part of the Bézier curve. You then do the same things with the second part until t1-t0 is less than a given number.
The “given number” is the error that you think is acceptable in your implementation. The Bézier clipping give an approximated solution. With every iteration you get a better approximation but there will always be some error. The algorithm stop to recurse when the error is lower than what you have decided.
The convex hull of the bézier curve is the smaller polygon that contains the control points. The bézier curve is always contained in that polygon and, if the segment doesn’t intersect with the convex hull it doesn’t intersect with the curve.
You have to consider the 1D bézier curve with the control “points” dist(P0), dist(P1), dist(P2), dist(P3) where dist is the formula previously described where you substitute x and y with the coordinates of the point passed as the parameter.
In code is something like this:
This curve gives you the distance of a point on the bézier curve to the line that contains the segment. Calculating the intersection between the original curve and the line become the problem to find all the values of t that, inserted in the formula of this 1D bézier curve, gives a value equals to zero.
The bézier clipping algorithm works in the following way:
* Calculate the convex hull of the curve (the 1D curve...)
* Find where the convex hull cross the x-axis (t0 is the lower value and t1 is the higher)
* If t1-t0 is bigger than 0.8 subdivide in half the curve and recurse for each half and return the two intersections founded.
* If t1-t0 is lower than the maximum error acceptable than return (t0+t1)/2
* Subdivide the curve in three parts (“cut” the curve at the points t0 and t1)
* Recurse passing as parameter the part of the curve defined inside the interval [t0,t1]
The convex hull of the bézier curve is the smaller polygon that contains the control points. The bézier curve is always contained in that polygon and, if the segment doesn’t intersect with the convex hull it doesn’t intersect with the curve.
You have to consider the 1D bézier curve with the control “points” dist(P0), dist(P1), dist(P2), dist(P3) where dist is the formula previously described where you substitute x and y with the coordinates of the point passed as the parameter.
In code is something like this:
float dist(Vector &d, float c, Point &p){ return d.y*p.x + d.x*p.y + c;}
This curve gives you the distance of a point on the bézier curve to the line that contains the segment. Calculating the intersection between the original curve and the line become the problem to find all the values of t that, inserted in the formula of this 1D bézier curve, gives a value equals to zero.
The bézier clipping algorithm works in the following way:
* Calculate the convex hull of the curve (the 1D curve...)
* Find where the convex hull cross the x-axis (t0 is the lower value and t1 is the higher)
* If t1-t0 is bigger than 0.8 subdivide in half the curve and recurse for each half and return the two intersections founded.
* If t1-t0 is lower than the maximum error acceptable than return (t0+t1)/2
* Subdivide the curve in three parts (“cut” the curve at the points t0 and t1)
* Recurse passing as parameter the part of the curve defined inside the interval [t0,t1]
I'm currently can't imagine 1D curve :D
So I'm post up some code later, check out below:
[Edited by - Lolmen on December 5, 2007 8:19:16 PM]
So I'm post up some code later, check out below:
[Edited by - Lolmen on December 5, 2007 8:19:16 PM]
Ok, It takes too long time, I can't waste too much time, I have to make my game...
So can you show me formulas to compute A,B,C coefficients for cubic equation solver from given line segment start, end and Curves Px?
And also check do I compute roots right:
I write this code here, so I can't know how much it correct.
Because of these hard mathematics, which mush up my mind...
So can you show me formulas to compute A,B,C coefficients for cubic equation solver from given line segment start, end and Curves Px?
And also check do I compute roots right:
// Bezier: (1-t)^3 * P0 + 3t(1-t)^2 * P1 + 3t^2 * (1-t)P2 + t^3 * P3, t -> [0, 1]inline Vector B( float t, Vector P1, Vector P2, Vector P3, Vector P4 ){ t = clamp( t, 0.0f, 1.0f ); // make sure t doesn't grows up return CUBE(1.0f-t)*P1 + 3.0f*t*SQUARE(1.0f-t) * P2 + 3.0f*SQUARE(t)*(1.0f-t)*P3 + CUBE(t)* P4;}// Intersetion function// returns: t -> [0, 1] parameter and segment intersection point in M.// if function returns false, so there is no intersections;inline bool Intersection(BezierCurvePoints & bCurve, Vector vSrc, Vector vEnd, Vector& M, float t){ double A,B,C; // TODO : compute them out use bCurve.Px and vSrc, vEnd double results[3]; // maximum roots // resturns roots quantity and fill results array int roots = SolveCubic(results, a, b, c); if ( roots != 2 ) // roots < 2 && roots > 2 { // first root is less than 0 or bigger than 1 if ( results[0] < 0 || results[0] > 1 ) return false; // Try findout inerestion point for first root M = B( results[0], bCurve.P0, bCurve.P1, bCurve.P2, bCurve.P3 ); // check do out segment intersect given point on curve if ( IsLineSegmentIntersectPoint( vSrc, vEnd, M ) ) { t = results[0]; return true; // point match } // otherwise point not match return false; } Vector temp; // checking for bad root numer one and two bool badRoot1 = results[1] < 0 || results[1] > 1; bool badRoot2 = results[2] < 0 || results[2] > 1; if ( badRoot1 && badRoot2 ) return false; if (badRoot1) { // put root 1 to bezier function M = B( results[1], bCurve.P0, bCurve.P1, bCurve.P2, bCurve.P3 ); if ( IsLineSegmentIntersectPoint( vSrc, vEnd, M ) ) { t = results[1]; return true; } return false; } else if (badRoot2) { M = B( results[2], bCurve.P0, bCurve.P1, bCurve.P2, bCurve.P3 ); if (IsLineSegmentIntersectPoint( vSrc, vEnd, M ) ) { t = results[2]; return true; } return false; } else { // we probably have two intersection points, find closest? // try find out match root Vector M1 = B( results[1], bCurve.P0, bCurve.P1, bCurve.P2, bCurve.P3 ); Vector M2 = B( results[2], bCurve.P0, bCurve.P1, bCurve.P2, bCurve.P3 ); int root = 0; Vector d1 = vSrc - M1; Vector d2 = vSrc - M2; // compare vector lengths if ( d1.Length() >= d2.Length() ){ M = M1; root = 1; } if ( IsLineSegmentIntersectPoint( vSrc, vEnd, M ) ) t = results[root]; return true; return false; }}
I write this code here, so I can't know how much it correct.
Because of these hard mathematics, which mush up my mind...
A cubic bézier curve written as a cubic polynomial is
(P3 - 3P2 + 3P1 - P0)t3 + 3(P2 - 2P1 + P0)t2 + 3(P1 - P0)t + P0
where P0, P1, P2, P3 are the control point of the bézier curve.
If you divide everything by the coefficient of t3 you obtain the following polynomial
t3 + at2 + bt + c
where
a = 3(P2 - 2P1 + P0)/(P3 - 3P2 + 3P1 - P0)
b = 3(P1 - P0)/(P3 - 3P2 + 3P1 - P0)
c = P0/(P3 - 3P2 + 3P1 - P0)
The 1D bézier “curve” that I have presented before is a function that, given a value for t as argument, returns a value (the distance between the line and a point in the original bézier curve). It’s very similar to the curve in 2D but it returns a single float value instead of a 2D point (a point in a line has a single coordinate). The points of intersections are those points that have a distance from the line equals to zero.
[Edited by - apatriarca on December 5, 2007 2:53:49 PM]
(P3 - 3P2 + 3P1 - P0)t3 + 3(P2 - 2P1 + P0)t2 + 3(P1 - P0)t + P0
where P0, P1, P2, P3 are the control point of the bézier curve.
If you divide everything by the coefficient of t3 you obtain the following polynomial
t3 + at2 + bt + c
where
a = 3(P2 - 2P1 + P0)/(P3 - 3P2 + 3P1 - P0)
b = 3(P1 - P0)/(P3 - 3P2 + 3P1 - P0)
c = P0/(P3 - 3P2 + 3P1 - P0)
The 1D bézier “curve” that I have presented before is a function that, given a value for t as argument, returns a value (the distance between the line and a point in the original bézier curve). It’s very similar to the curve in 2D but it returns a single float value instead of a 2D point (a point in a line has a single coordinate). The points of intersections are those points that have a distance from the line equals to zero.
[Edited by - apatriarca on December 5, 2007 2:53:49 PM]
Here is some code.
I haven’t tested or compiled the code.
[Edited by - apatriarca on December 6, 2007 2:18:15 PM]
float dist(const Vector &d, float c, const Point &p){ return d.y*p.x + d.x*p.y + c;}bool intersection(const Point &A, const Point &B, const BezierCurve &bez){ Vector d = normalize(B-A); float c = A.y*d.x - A.x*d.y; float D0 = dist(d, c, bez.P0); float D1 = dist(d, c, bez.P1); float D2 = dist(d, c, bez.P2); float D3 = dist(d, c, bez.P3); float s = 1.0f/(D3 - 3.0f*D2 + 3.0f*D1 - D0); float c0 = 3.0f*(D2 - 2.0f*D1 + D0)*s; float c1 = 3.0f*(D1 - D0)*s; float c2 = D0*s; float t0, t1, t2; unsigned roots; // I suppose solveCubic is a function that finds the roots of x^3 + c0*x^2 + c1*x + c2 // returns the number of roots roots = solveCubic(c0, c1, c2, &t0, &t1, &t2); // you have now to see if the intersections are in the interval [0,1] and if the points // are in the segment}
I haven’t tested or compiled the code.
[Edited by - apatriarca on December 6, 2007 2:18:15 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement