Offsetting Bezier Curve

[Hippogriff]

Looking at Bezier curves has been pretty simple so far but I seem to have run into a slight problem. Right now I am trying to create a "railroad" type object from offsetting a single Bezier curve. (I am actually trying to copy the sliders from a game based on EBA for the DS, called osu!, seen here http://puu.sh/3bgLP.jpg).

Everything works correctly when the curves are curved gradually but things seem to break when I use a sharp curve, I am not sure if my math is wrong or just the overall theory. (Ignore the terrible graphics right now).
Smooth curve- http://puu.sh/3bieQ.png
Sharp curve - http://puu.sh/3bifn.png

Right now I am just looping through 0-1 and calculating the point on the curve + the slope (while normalizing everything), I then get the next point + slope and construct a quad between them using 25 as the width for the offset.

Any help with what I am doing wrong would be appreciated.

struct Point
{
   Point(double X, double Y) : x(X), y(Y) {} 
   double x,y;

   void normalize()
   {
	double Length = sqrt((x * x) + (y * y));

	if(Length != 0)
	{
	     x /= Length;
	     y /= Length;
	}
   }
};

Point DeriveBezier(double t, Point &P1, Point &P2, Point& P3) //Derivative of quadratic Bezier
{
	Point pt;
	pt.x = ((pow(1-t,1) * 2) * (P2.x - P1.x)) + ((pow(1-t,0) * t) * (P3.x - P2.x));
	pt.y = ((pow(1-t,1) * 2) * (P2.y - P1.y)) + ((pow(1-t,0) * t) * (P3.y - P2.y));
	return pt;
}

Point Bezier(double t, Point &P1, Point &P2, Point& P3) // Creating quadratic Bezier
{
	Point pt;
	pt.x = (pow(1-t,2) * P1.x) + (2 * pow(1-t, 1) * t) * P2.x + (pow(t,2) * P3.x);
	pt.y = (pow(1-t,2) * P1.y) + (2 * pow(1-t, 1) * t) * P2.y + (pow(t,2) * P3.y);
	return pt;
}

void Create()
{
    Point BezierPoint, BezierPoint2;
    int W = 25;

    //Doesn't need to be such a small number, just for testing 
    for(double t = 0; t < 1; t += 0.001)
    {
	  Point Slope = DeriveBezier(t,P1,P2,P3); // Slope of current Point
	  Point Slope2 = DeriveBezier(t + 0.001,P1,P2,P3);  // Slope of next point 

          //Get Normal to slope, then normalize
	  Slope = NormalVec(Slope);  
	  Slope.normalize();

	  Slope2 = NormalVec(Slope2);
	  Slope2.normalize();

          BezierPoint = Bezier(t, P1, P2, P3);  // Point on graph
	  BezierPoint2 = Bezier(t + 0.001, P1, P2, P3); // Next point 

	  glBegin(GL_QUADS);
		  glVertex2f(BezierPoint.x,                 BezierPoint.y);
		  glVertex2f(BezierPoint.x + Slope.x * W,   BezierPoint.y + Slope.y * W);
		  glVertex2f(BezierPoint2.x + Slope2.x * W, BezierPoint2.y + Slope2.y * W);
		  glVertex2f(BezierPoint2.x,                BezierPoint2.y);
	  glEnd();

	  glBegin(GL_QUADS);
		  glVertex2f(BezierPoint.x,                  BezierPoint.y);
		  glVertex2f(BezierPoint.x + Slope.x *- W,   BezierPoint.y + Slope.y * -W);
		  glVertex2f(BezierPoint2.x + Slope2.x * -W, BezierPoint2.y + Slope2.y * -W);
		  glVertex2f(BezierPoint2.x,                 BezierPoint2.y);
	  glEnd();

	  Apply_Surface(BezierPoint.x, BezierPoint.y, Square, NULL); // Curve with no offset applied 
    }
}

[ne555]

I suppose that the vertices of the quads are not in order
http://www.toldo.info/roberto/LaboratorioGrafica/Slides/images/constraints_polygons.gif (not simple)


> pow(1-t,1)
overkill

Also, consider using DeCasteljau to compute the points and derivatives

[Hippogriff]

I have seen people talk about the DeCasteljau algorithm and will probably switch over to that, but I think I would run into the same problem as it is right now?

I suppose that the vertices of the quads are not in order
http://www.toldo.info/roberto/LaboratorioGrafica/Slides/images/constraints_polygons.gif (not simple)

Not 100% sure what you mean about this, the vertices are in order of the quad as I would imagine it (they don't cross over or anything).

I know some of my pow functions are unnecessary (I have a pow function with a 0 exponent up there :P, but that will all be improved after).

EDIT:
I guess I see what you mean with the slopes added, but how would I fix this correctly?

[ne555]

a = x1,y1
b = x1,y1 + w*s1

r = x2,y2
s = x2,y2 + w*s2

You defined your quad as (a,b,s,r), however that gives you a non-simple polygon in some cases
Simply change the definition to (a,r,b,s) if ab intersects rs

To check for intersection, use the cross product

 if(
	(ab x as)*(ab x ar) < 0 //they lay in different semiplanes
	and (rs x ra)*(rs x rb) < 0
)
	//intersects  

Also, you should define all polygons as being cw (or ccw)
If they don't make a right turn, reverse the representation

[Hippogriff]

I set up that formula and it did show me where the quads intersect but switching the vertices there didn't seem to solve the problem?

I am guessing it would be easier to use textures instead and just rotate their position on the z-axis based on the slope of the curve (seeing as this will all be 2D).
From what I have read to get the slope at a single point of a parametric equation it is
Derivative of y(t) / Derivative of x(t)

Then after that I am guessing I have to take the atan to convert it to degrees to use with glrotatef. Not sure if I am on the right track here or way off.

[ne555]

Try to define the quad using only the slope in the current point.
a = x1,y1
b = x1,y1 + w*s1

r = x1,y1 + dt * s1'
s = r + w*s1

where s1' is orthogonal to the slope, and dt is quite small
(so you'll end with a rotated rectangle)


> but switching the vertices there didn't seem to solve the problem?
¿have you got the same image?

[Hippogriff]

Assuming I have implemented your equations correctly I came up with this. (All functions not shown haven't changed).

    
Point NormalVec(Point &P1)
{
    Point tmp(-P1.y, P1.x);
    return tmp;
}

void Func()
{
   for(double t = 0; t < 1; t += 0.001)
   {
       BezierPoint = Bezier(t, P1, P2, P3); 
       Point Slope = DeriveBezier(t,P1,P2,P3);

       //dt = 20
      //W = 40
       Point a(BezierPoint);
       Point b(BezierPoint.x,   BezierPoint.y + Slope.y * W);
       Point r(BezierPoint.x + NormalVec(Slope).x * 20,   BezierPoint.y + NormalVec(Slope).y * 20);
       Point s(r.x + W * Slope.x, r.y + W * Slope.y);

       glBegin(GL_QUADS);
          glVertex2f(a.x, a.y);
          glVertex2f(b.x, b.y );
          glVertex2f(s.x, s.y );
          glVertex2f(r.x , r.y );
       glEnd();
    }
}

Which can give some very strange looking curves (limited to 1 quad right now) http://puu.sh/3cehS.jpg
It works fine under certain situations http://puu.sh/3ceGD.png
I feel like I am making this harder than it needs to be.

When I checked for line intersection I changed the "new' quadsto a different color that seemed to show up when the curve became tight but it still had same problem as original images.