Page 1 of 1

Bezier Curves Part 1 [Linear Algebra Series] Rate Topic: -----

#1 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1105
  • View blog
  • Posts: 6,918
  • Joined: 07-September 06

Posted 09 May 2013 - 09:47 PM

Introduction

The most up to date code for this tutorial can be forked from Github.

Starting off, what is a Bezier Curve? It is a curve defined by 2 or more control points which determine how the curve looks. The first and last control points are, by definition, passed directly through while other control points (in the general cases) are simply moved towards and not directly through.

This can all sounds little difficult to understand at first, so I will give you an interactive demo on what Bezier Curves look like and how they work. In the demo, the blue squares are the “hard” control points and the red circles are the “soft” control points. As you drag the control points around the screen you will see the curve change accordingly.

(Requires Flash Player) Demo
http://skydrive.live.com/embed?cid=66EABC8857A84A52&resid=66EABC8857A84A52%21308&authkey=ADBJ6ygTt1A_mzk
Demo Here (Skydrive)

Getting Started

Before we start diving into the math and programming behind Bezier Curves, let us first look into why you would ever want to be interested in them. Here are a few fields where Bezier Curves are put to use, and what they are used for:
Fonts – Truetype and other vector-based fonts have been known to use Bezier Curves.
Auto-body modeling – That’s right, your car’s sweet curves were likely designed using Bezier Curves
Vector art – Vector art is almost always based around Bezier Curves, which are desired because the graphics are defined by a series of equations which can be scaled infinitely.

As I spoke about a little above, Bezier Curves are just equations which act on a series of points to define the look of a curve. As a result they can be scaled and modified easily without losing their integrity or fine edge. However, since they are equations that means we also have to look at some math.

Math Time!

Bezier Curves are defined for multiple dimensions starting with linear and working our way up we have:
B_2 (t)=(1-t) P_0+tP_1,t∈[0,1]
B_3 (t)=(1-t)^2 P_0+2(1-t)tP_1+t^2 P_2
B_4 (t)=(1-t)^3 P_0+3(1-t)^2 tP_1+3(1-t) t^2 P_2+t^3 P_3

If you haven’t caught on yet, this is all leading to a nice little series which is defined like so:
B(t)=∑_(i=0)^n▒〖(n¦i) (1-t)^(n-i) t^i P_i 〗
And, for the sake of being thorough:
(n¦i)=n!/i!(n-i)!

Sweet, now that we have the math down it is time to get programming! In this tutorial we will cover two different programs. The first will be the demo you saw above, which will enable you to actually go out and replicate it (it isn’t large, 57 lines of code total – in flash). The second part of this tutorial will be covering how to implement a generalization of Bezier Curves in C++ and have it read in an input file from stdin and output to stdout (using cin and cout respectively). So, without any further ado, let us begin.

Creating the Bezier Curve Demo

The first step to creating any application is determining what you want it to do, and what you want it to be written in. In this case it isn’t exactly important (since the demo was in Flash, which will automatically-include files needed as you type, and we are going to code up this part of the tutorial in Flash AS3 as well), but in many languages, you will have to manually do the inclusions. So, as you have seen in the demo, we need to have mouse input, events, graphics, and a container. For the container I chose the simple solution of using a MovieClip. One final requirement that is slightly less obvious (and not strictly required) is Points to store the x and y values we calculate. This could, however, be done with 2 separate variables, one for x and the other for y. For these includes you can just use this block of code:
 import flash.geom.Point;
import flash.display.MovieClip;
import flash.display.Graphics;
import flash.events.MouseEvent;
import flash.events.Event;


Now that we have this part done, it makes sense to take a quick detour and get the stage set properly for the control points. Start off by creating a circle and square, then convert them into symbols such that they can be named for AS usage. Duplicate one of each of the control points and name them p1 through p4 from the properties panel. You want p1 and p4 to be one symbol type, and p2 and p3 to be the other.

Continuing with the code, we need to set up a few variables. This is pretty simple overall; you just need an array of the movieclips we just set up, and an additional movieclip to draw on.
 var pts:Array = [p1, p2, p3, p4];
var drawer:MovieClip = new MovieClip();
stage.addChild(drawer);


As you saw above in the math section, we need to have the factorial, power, and choose mathematical functions. Lucky for us we don’t need to recreate the power function so that just leaves the other two.

 function factorial(num:Number):Number{
	if(num <= 1){
		return 1;
	}
	var ret:Number = 1;
	for(var i:Number = 1; i <= num; i++){
		ret *= i;
	}
	return ret;
}

function choose(a:Number, b:Number):Number{
	return factorial(a) / (factorial(b ) * factorial(a - b ));
}


It is about time that we went through creating the Bezier Curve function. It is just like the math above, expect that we need to also draw the curve on the stage. Furthermore, we need to loop over time from 0 to 1. Since 1/100 (or .01) isn’t a power of 2 (and as a result cannot be stored exactly as a binary number) we are just going to decrease that to 1/128 which is a power of 2.

 function bCurve(e:Event):void{
	var mc:MovieClip = drawer;
	var g:Graphics = mc.graphics;
	g.clear();
	g.lineStyle(2, 0xff0000);
	g.moveTo(pts[0].x, pts[0].y);
	for(var t:Number = 0; t <= 1; t += (1./128.)){
		var pt:Point = new Point();
		for(var i:uint = 0; i < pts.length; i++){
			pt.x += pts[i].x * choose(pts.length - 1, i) * Math.pow(1 - t, pts.length - 1 - i) * Math.pow(t, i);
			pt.y += pts[i].y * choose(pts.length - 1, i) * Math.pow(1 - t, pts.length - 1 - i) * Math.pow(t, i);
		}
		g.lineTo(pt.x, pt.y);
	}
}


Now, to finish off the function writing, we just need some way to drag the control points around the stage and drop them in new places. While we are dragging a control point we also want to be re-calculating the Bezier Curve and drawing it to the stage.

 function dragAndDraw(e:Event):void{
	e.target.startDrag();
	stage.addEventListener(MouseEvent.MOUSE_MOVE, bCurve);
}

function drop(e:Event):void{
	e.target.stopDrag();
	stage.removeEventListener(MouseEvent.MOUSE_MOVE, bCurve);
}


Finally, we need to get each of the control points actually listening for mouse dragging events. Additionally, we need to ensure that the control points are above the movieclip we are going to draw the curves on, and we want to draw the curve at the beginning of the program.

 for(var i:uint = 0; i < pts.length; i++){
	stage.addChild(pts[i]);
	pts[i].addEventListener(MouseEvent.MOUSE_DOWN, dragAndDraw); 
	pts[i].addEventListener(MouseEvent.MOUSE_UP, drop);
}
bCurve(null);


I’ll leave you to put the code together in the final format; otherwise this tutorial may get a bit lengthier than it is already going to be.

Calculating Bezier Points in C++

We are about to go through 200 more lines of C++ code which will allow us to calculate the Bezier Curve of a series of control points and output the coordinates for the curve specified by the control points.

A lot of this program is exactly the same as what we have already done above, except the obvious change of language. For that reason we will start with the functions that we can reuse. We will also be writing a Point class to allow us an easy analogue and abstraction of the mathematical operators (plus it will simplify the code slightly). We are also going to separate the time loop from the Bezier Curve function to make the actual function a little more versatile.

Part of main.cpp:
 Point bezier(std::vector<Point>& pts, double t){
  Point p;
  std::size_t len = pts.size();
  for(std::size_t i = 0; i < len; i++){
    p += pts[i] * choose(len - 1, i) * pow(1 - t, len - 1 - i) * pow(t, i);
  }
  return p;
}

double factorial(double num){
  if(num <= 1){
    return 1;
  }
  double fac = 1;
  for(double i = 1; i <= num; i++){
    fac *= i;
  }
  return fac;
}

double choose(double a, double b ){
  return factorial(a) / (factorial(b ) * factorial(a - b ));
}


Let’s quickly jump over and write in main.h for future use.
 #ifndef __MAIN_H__
#define __MAIN_H__

#include "Point.h"
#include <cmath>
#include <iostream>
#include <vector>

Point bezier(std::vector<Point>& pts, double t);
double factorial(double num);
double choose(double a, double b );

#endif


Now for Point.h:
#ifndef __POINT_H__
#define __POINT_H__

#include <iostream>

class Point{
public:
	Point(void);
	Point(double nx, double ny);
	Point(const Point& src);
	~Point(void);

	Point& operator=(const Point& src);
	Point operator*(const Point& alt);
	Point operator/(const Point& alt);
	Point operator-(const Point& alt);
	Point operator+(const Point& alt);
	Point operator*(double num);
	Point operator/(double num);
	Point operator-(double num);
	Point operator+(double num);
	Point operator*=(const Point& alt);
	Point operator/=(const Point& alt);
	Point operator-=(const Point& alt);
	Point operator+=(const Point& alt);
	Point operator*=(double num);
	Point operator/=(double num);
	Point operator-=(double num);
	Point operator+=(double num);

	friend std::ostream& operator<<(std::ostream& out, const Point& pt);
private:
	double x;
	double y;
};

#endif


As you can see from the above header file, this is where a lot of the code falls for the C++ program. Basically, it is created to simplify numerical computation and programming for a 2-dimensional x, y coordinate. The majority of the code behind it is self-explanatory, we want to allow points to be arithmetically compatible with other points as well as doubles, so we have a copy of each of the arithmetic operators for both points and doubles. The most interesting thing is probably the friend function at the bottom of the file, and that just says that the function is allowed to access private members of the class. Here is the implementation Point.cpp:

 #include "Point.h"


Point::Point(void){
	x = y = 0;
}
Point::Point(double nx, double ny){
	x = nx;
	y = ny;
}
Point::Point(const Point& src){
	(*this) = src;
}
Point::~Point(void){
}

Point& Point::operator=(const Point& src){
	x = src.x;
	y = src.y;
	return *this;
}
Point Point::operator*(const Point& alt){
	Point p(x * alt.x, y * alt.y);
	return p;
}
Point Point::operator/(const Point& alt){
	Point p(x / alt.x, y / alt.y);
	return p;
}
Point Point::operator-(const Point& alt){
	Point p(x - alt.x, y - alt.y);
	return p;
}
Point Point::operator+(const Point& alt){
	Point p(x + alt.x, y + alt.y);
	return p;
}
Point Point::operator*(double num){
	Point p(x * num, y * num);
	return p;
}
Point Point::operator/(double num){
	Point p(x / num, y / num);
	return p;
}
Point Point::operator-(double num){
	Point p(x - num, y - num);
	return p;
}
Point Point::operator+(double num){
	Point p(x + num, y + num);
	return p;
}
Point Point::operator*=(const Point& alt){
	x *= alt.x;
	y *= alt.y;
	return *this;
}
Point Point::operator/=(const Point& alt){
	x /= alt.x;
	y /= alt.y;
	return *this;
}
Point Point::operator-=(const Point& alt){
	x -= alt.x;
	y -= alt.y;
	return *this;
}
Point Point::operator+=(const Point& alt){
	x += alt.x;
	y += alt.y;
	return *this;
}
Point Point::operator*=(double num){
	x *= num;
	y *= num;
	return *this;
}
Point Point::operator/=(double num){
	x /= num;
	y /= num;
	return *this;
}
Point Point::operator-=(double num){
	x -= num;
	y -= num;
	return *this;
}
Point Point::operator+=(double num){
	x += num;
	y += num;
	return *this;
}

std::ostream& operator<<(std::ostream& out, const Point& pt){
	out << pt.x << "\t" << pt.y;
	return out;
}


And it is time to finish up the main function and get a Makefile put together for compiling (this is built in Linux, but should work in Windows as well – NOTE, untested). The make file will read from standard input a series of lines in the following format:
The first line will contain 2 numbers, the first one being the number of lines to follow, and the second being the delta time variable. Recall that time is a value between 0 and 1, so the smaller delta time is the more points will be calculated across the curve.
Every line to follow will define a control point which is either a soft or a hard control point (soft control points are meant to be in the middle of a curve, as seen in the demo, and hard control points will be passed directly through, the end points in the demo). These lines will contain 3 numbers. The first two will be the x and y coordinate respectively, and the third will be either a 0 or a 1. Where 0 means it is a soft control point, and 1 means it is a hard control point.

Here is the full main.cpp file:
 #include "main.h"
using namespace std;

int main(void){
	std::vector<std::vector<Point> > pts;
	char endPointCount = 0;
	double inx;
	double iny;
	int ptCount = 0;
	int endPoint;
	double deltaT;

	cin >> ptCount >> deltaT;
	for(int i = 0; i < ptCount; i++){
		cin >> inx >> iny >> endPoint;
		Point p(inx, iny);
		if(endPointCount == 0 && endPoint == 1){
			pts.push_back(std::vector<Point>());
			pts[pts.size() - 1].push_back(p);
			endPointCount++;
			continue;
		}
		pts[pts.size() - 1].push_back(p);
		if(endPointCount != 0 && endPoint == 1 && i != ptCount - 1){
			pts.push_back(std::vector<Point>());
			pts[pts.size() - 1].push_back(p);
			endPointCount++;
		}
	}
	

	for(std::size_t i = 0; i < pts.size(); i++){
		for(double t = 0; t <= 1; t += deltaT){
			cout << bezier(pts[i], t) << endl;
		}
	}
	return 0;
}

Point bezier(std::vector<Point>& pts, double t){
	Point p;
	std::size_t len = pts.size();
	for(std::size_t i = 0; i < len; i++){
		p += pts[i] * choose(len - 1, i) * pow(1 - t, len - 1 - i) * pow(t, i);
	}
	return p;
}

double factorial(double num){
	if(num <= 1){
		return 1;
	}
	double fac = 1;
	for(double i = 1; i <= num; i++){
		fac *= i;
	}
	return fac;
}

double choose(double a, double b ){
	return factorial(a) / (factorial(b ) * factorial(a - b ));
}


As far as the Makefile goes, it is a pretty simple one:
 EXE=bezier

.cpp.o:
	g++ -Wall $^ -c

install:
	make ${EXE}
	rm -rf *.o

${EXE}:Point.o main.o
	g++ -Wall $^ -o $@

clean:
	rm -f *.o *.gch ${EXE}


Now, it is time to take a look at the input used to draw a curve:
 13 .125
20 20 1
20 25 0
25 30 0
30 30 1
35 30 0
40 25 0
40 20 1
40 15 0
35 10 0
30 10 1
25 10 0
20 15 0
20 20 1


The above file is for a circle approximation (there are better ones out there, but this is a quick approximation I threw together). Here is another example of how someone could go about approximating a circle, with fewer control points (and fewer points in general).
 5 .125
10 10 1
10 15 0
20 10 0
10 5 0
10 10 1


If you run the program and redirect the output to a file you can just copy and paste the output into a excel or other spreadsheet program and graph it to see what your curve looks like. Sadly, drawing the curves is outside of the scope of this tutorial (mainly because it would increase the length by quite a bit).

Enjoy your time with Bezier Curves!

This post has been edited by BetaWar: 06 July 2013 - 10:48 PM
Reason for edit:: Cleaned up forum bug and disabled emoticons


Is This A Good Question/Topic? 2
  • +

Replies To: Bezier Curves Part 1 [Linear Algebra Series]

#2 jimblumberg  Icon User is offline

  • member icon


Reputation: 3845
  • View blog
  • Posts: 11,753
  • Joined: 25-December 09

Posted 10 May 2013 - 06:27 AM

What program does one need in order to see your demo?

Never mind. After reading further it seem to be using flash.


Jim

This post has been edited by jimblumberg: 10 May 2013 - 08:59 AM

Was This Post Helpful? 0
  • +
  • -

#3 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1105
  • View blog
  • Posts: 6,918
  • Joined: 07-September 06

Posted 10 May 2013 - 09:42 AM

Sorry about that Jim, I went ahead and edited the demo heading to specify it is in flash.
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon


Reputation: 3845
  • View blog
  • Posts: 11,753
  • Joined: 25-December 09

Posted 19 May 2013 - 06:38 AM

I have a couple of suggestions about your header files. First the code in question:
 #ifndef __POINT_H__
#define __POINT_H__

#include <iostream>

class Point{
public:
Point(void);
Point(double nx, double ny);
Point(const Point& src);
~Point(void);

Point& operator=(const Point& src);
Point operator*(const Point& alt);
Point operator/(const Point& alt);
Point operator-(const Point& alt);
Point operator+(const Point& alt);
Point operator*(double num);
Point operator/(double num); 
Point operator-(double num);
Point operator+(double num);
Point operator*=(const Point& alt);
Point operator/=(const Point& alt);
Point operator-=(const Point& alt);
Point operator+=(const Point& alt);
Point operator*=(double num);
Point operator/=(double num);
Point operator-=(double num);
Point operator+=(double num);

friend std::ostream& operator<<(std::ostream& out, const Point& pt);
private:
double x;
double y;
};

#endif



My first problem with this snippet is with the first two lines:

#ifndef __POINT_H__
#define __POINT_H__


In C/C++ the use of leading underscores can be problematic, but two leading underscores are reserved for the implementation, as is an underscore followed by an uppercase letter. A variable starting with a single underscore is also reserved for the implementation if it is used in the global scope. I really recommend never using a leading underscore, anywhere in your code.

Next a little indentation will make your headers much easier to read.

#ifndef POINT_H__
#define POINT_H__

#include <iostream>

class Point {
   public:
      Point(void);
      Point(double nx, double ny);
      Point(const Point& src);
      ~Point(void);

      Point& operator=(const Point& src);
      Point operator*(const Point& alt);
      Point operator/(const Point& alt);
      Point operator-(const Point& alt);
      Point operator+(const Point& alt);
      Point operator*(double num);
      Point operator/(double num);
      Point operator-(double num);
      Point operator+(double num);
      Point operator*=(const Point& alt);
      Point operator/=(const Point& alt);
      Point operator-=(const Point& alt);
      Point operator+=(const Point& alt);
      Point operator*=(double num);
      Point operator/=(double num);
      Point operator-=(double num);
      Point operator+=(double num);

      friend std::ostream& operator<<(std::ostream& out, const Point& pt);
   private:
      double x;
      double y;
};

#endif




Jim
Was This Post Helpful? 0
  • +
  • -

#5 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1105
  • View blog
  • Posts: 6,918
  • Joined: 07-September 06

Posted 19 May 2013 - 09:41 AM

Ah, I didn't know about the underscore thing, I just used that as a quick and easy way to determine that it was an include guard and not a #defined value to be used. As far as the header indentation goes, I am not sure what is up with that (must have been a copy/paste error) since I do indent all my files (though not in the same way you showed). I'll update that file when I get access to my VM next.
Was This Post Helpful? 0
  • +
  • -

#6 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1105
  • View blog
  • Posts: 6,918
  • Joined: 07-September 06

Posted 06 July 2013 - 10:49 PM

Just a as a quick update. I added a link to the Github repo for the code and have fixed the indentation of Point.h. In the future I will update the include guards, but the code for this tutorial will remain untouched seeing as there has already been a little discussion on it and others may find it useful.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1