Curbe Bezier

O curbă Bézier este o curbă parametrică inventată de inginerul francez Pierre Bézier şi făcută publică în anul 1962. Bézier a folosito în procesul de design al automobilelor. Curbele Bézier sunt foarte importante şi pentru domeniul tehnologiei informaţiei, fiind folosite în construcţia fonturilor TrueType.

Fig. 1 - Graficul polinoamelor Bernstein de ordinul 0

Fig. 2 - Graficul polinoamelor Bernstein de ordinul 1

Polinoame Bernstein

Polinoamele Bernstein stau la baza curbelor Bézier. Acestea poartă numele matematicianului ucrainian Sergei Natanovich Bernstein.

Pentru a determina polinoamele Bernstein de orice grad se porneşte de la polinomul Bernstein de ordinul zero.

Apoi se scade din ambele părţi o varibilă t şi obţinem:

Ultima expresie este o combinaţie liniară a polinoamelor Bernstein de bază de ordinul unu. Polinoamele sunt:

<math>\begin{cases} B_{0,1} = 1-t \\ B_{1,1} = t\end{cases}</math>

Acum putem obţine polinoame Bernstein de orice grad prin ridicarea la putere a ultimei expresii:

Obţinem astfel polinoamele Berstein de bază de ordinul doi: <math>\begin{cases}B_{0,2} = (1-t)^2 \\ B_{1,2} = 2t(1-t) \\ B_{2,2} = t^2 \end{cases}</math>

Fig. 3 - Graficul polinoamelor Bernstein de ordinul 2

Foarte interesante şi utile sunt graficele polinoamelor Bernstein, pentru înţelegerea modului în care "funcţionează" curbele Bézier.

Definirea unei curbe Bézier

O curbă Bézier de ordinul n se defineşte, cu ajutorul a N puncte, după cum urmează: <math>P(t) = \sum_{k=0}^N B_{k,N}P_{k}</math>, unde <math>B_{k,N}</math> este polinomul Bernstein de indice k şi de ordin N. <math>P_{k}</math> sunt puncte în plan, adică vectori cu două componente <math>(x_{k}, y_{k})</math>.

Curba Bézier liniară

Curba Bézier liniară este definită folosind polinoamele Bernstein de ordinul 1: <math>\begin{cases} B_{0,1} = 1-t \\ B_{1,1} = t\end{cases}</math>

Ecuaţia:

Reprezentarea grafică este doar o linie şi din acest motiv această formă nu este aproape deloc folosită.

Fig. 4 - Graficul polinoamelor Bernstein de ordinul 3

Curba Bézier pătratică

Curba Bézier pătratică sau de ordinul doi este o curbă dată prin trei puncte, punctul din mijloc fiind un punct de control care nu se află pe curbă, dar care influenţează aspectul acesteia.

Aceasta foloseşte polinoamele Bernstein de ordinul doi:

<math>\begin{cases}B_{0,2} = (1-t)^{2} \\ B_{1,2} = 2t(1-t) \\ B_{2,2} = t^2\end{cases}</math>

Ecuaţia curbei este:

În anumite documente ecuaţiile sunt date în funcţie de puterile lui t, lucru care aduce confuzie, de aceea prezint în continuare şi această formă.

Se fac notaţiile: <math>\begin{cases}A = P_2 - 2P_1 - P_0 \\ B = 2P_1 \\ C = P_0\end{cases} \iff \begin{cases}A = P_2 - B - C \\ B = 2P_1 \\ C = P_0 \end{cases}</math>

Şi ecuaţia capătă următoarea formă: <math>P(t) = At^2 + Bt + C</math>

Ca şi proprietăţi ale curbei trebuie să subliniez următoarele:

Acest lucru poate fi uşor observat şi motivat cu ajutorul graficelor din figura 3.

Curba Bézier cubică

Curba Bézier cubică sau de ordinul trei este dată prin patru puncte <math>P_0, P_1, P_2</math> şi <math>P_4</math>. <math>P_1</math> şi <math>P_2</math> sunt puncte de control ale curbei.

Pentru a putea scrie ecuaţia curbei scriem mai întâi ecuaţiile polinoamelor Bernstein de ordinul trei:

<math>\begin{cases}B_{0,3} = (1-t)^{3} \\ B_{1,3} = 3t(1-t)^2 \\ B_{2,3} = 3t^2(1-t) \\ B_{3,3} = t^{3} \end{cases}</math>.

Ecuaţia curbei:

Scriem în funcţie de puterile lui t şi obţinem:

Se fac notaţiile:

<math>\begin{cases}A = P_3 - 3P_2 + 3P_1 - P_0 \\ B = 3P_2 - 6P_1 + 3P_0 \\ C = 3P_1 - 3P_0 \end{cases} \iff \begin{cases}A = P_3 - P_0 - B - C \\ B = 3(P_2 - P_1) - C \\ C = 3(P_1 - P_0)\end{cases}</math>

Ecuaţia curbei în funcţie de A, B şi C: <math>P(t) = At^3 + Bt^2 + Ct+P_0</math>

Desenarea unei curbe Bézier

Desenarea unei curbe Bézier nu este o sarcină trivială şi asta nu din cauza calculelor, pe care le-am lămurit până la acest moment ci din cauza afişării curbei astfel încât să aibe un aspect foarte lin.

Algoritmul cel mai simplu de desenare este următorul (pentru curba cubica).

Date de intrare: P1, P2, P3, P4 (P2, P3 - puncte de control) B03, B13, B23, B33 sunt functii care intorc valorile polinoamelor Bernstein de ordin 3 si indice k (k = 0..3).

1. PP <- P1    ;initializam punctul anterior (Previous Point) cu P1
2. IS <- .01   ;setam pasul de incrementare
3. pentru t = IS; t < 1; t <- t + IS executa
4.        CP.x = P1.x * B03(t) + P2.x * B13(t) + P3.x * B23(t) + P4.x * B33(t);
5.        CP.y = P1.y * B03(t) + P2.y * B13(t) + P3.y * B23(t) + P4.y * B33(t);
6.        drawLine(PP.x, PP.y, CP.x, CP.y);
7.        PP = CP;
8. end pentru

În continuare codul scris în Java pentru pseudocodul anterior.

QuadraticBezier.java import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.RenderingHints; import java.awt.geom.Point2D;

import javax.swing.JPanel;

public class QuadraticBezier extends JPanel { private static final long serialVersionUID = -6991920282065229392L;

public void paint(Graphics g) { Graphics2D g2 = (Graphics2D)g; super.paint(g2);

drawCubicBezier(g2, new Point2D.Float(100,100), new Point2D.Float(130,150), new Point2D.Float(150,200), new Point2D.Float(200,130)); }

/** * Aceasta functie deseneaza o curba Bezier cubica. * @param g2 Graphics2D * @param p1 BezPoint 1 * @param p2 Control Point 1 * @param p3 Control Point 2 * @param p4 BezPoint 2 */ public void drawCubicBezier(Graphics2D g2, Point2D.Float p1, Point2D.Float p2, Point2D.Float p3, Point2D.Float p4) { float is = 0.01f; //pasul de incrementare Point2D.Float prevPoint = p1; //Punctul calculat anterior Point2D.Float curPoint = new Point2D.Float(0,0); //Punctul curent

for (float t = is; t <= 1; t += is) { curPoint.x = B03(t)*p1.x + B13(t)*p2.x + B23(t)*p3.x + B33(t)*p4.x; curPoint.y = B03(t)*p1.y + B13(t)*p2.y + B23(t)*p3.y + B33(t)*p4.y; System.out.println(prevPoint.distance(curPoint)); if (prevPoint.distance(curPoint) > 5) { g2.drawLine((int)prevPoint.x, (int)prevPoint.y, (int)curPoint.x, (int)curPoint.y); prevPoint.x = curPoint.x; prevPoint.y = curPoint.y; } } }

private float B03(float t) { return (float) Math.pow(1-t, 3); }

private float B13(float t) { return (float) (3*t*Math.pow(1-t, 2)); }

private float B23(float t) { return (3*t*t*(1-t)); }

private float B33(float t) { return (float) Math.pow(t,3); } }

MainFormDesign.java import javax.swing.JFrame;

public abstract class MainFormDesign extends JFrame { private QuadraticBezier quadraticBezier = null;

public MainFormDesign() { setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setTitle("Test Bezier"); setSize(400, 400);

setContentPane(getQuadraticBezier()); }

private QuadraticBezier getQuadraticBezier() { if (null == quadraticBezier) { quadraticBezier = new QuadraticBezier(); } return quadraticBezier; } }

MainForm.java import javax.swing.SwingUtilities;

public class MainForm extends MainFormDesign { private static final long serialVersionUID = 1L;

public MainForm() { super(); }

public static void main(String[] args) { SwingUtilities.invokeLater(new Runnable() { public void run() { MainForm mf = new MainForm(); mf.setVisible(true); } }); } }

Se poate vedea în imaginea alăturată aspectul urât al curbei. Devine foarte clar că nu aceasta este calea de urmat pentru a desena o curbă Bézier.

Probleme de interpolare folosind curbe Bézier

Interpolare: Interpolarea reprezintă o metodă matematică de a creea date care lipsesc.

Multe persoane nu se simt confortabil să deseneze curbe Bézier folosind acele controale care nu se află pe curbă. Este un pic nenatural, deşi în aplicaţii complexe ale curbelor acele controale devin mult mai importante şi uşurează foarte mult munca. De exemplu atunci când se doreşte alipirea a două curbe Bézier, dorind păstrarea continuităţii punctul de control al celei de-a doua curbe se modifică astfel încât să fie coliniar cu punctul de control al primei curbe şi punctul comun celor două curbe.

În cazurile în care cunoaştem înainte puncte de pe curbă şi vrem să găsim ecuaţia curbei care trece prin acele puncte, trebuie să găsim o metodă de interpolare.

Interpolarea a trei puncte

Cunoaştem trei puncte <math>P_1</math>, <math>P_C</math> şi <math>P_3</math>. Dorim să găsim o curbă Bézier care să trecă prin aceste trei puncte. Este clar că <math>P_1</math> şi <math>P_3</math> sunt două dintre punctele care definesc curba Bézier şi mai trebuie să aflăm un punct asfel încât să definim o curbă Bézier de ordinul doi, dar care să treacă prin <math>P_C</math>.

Pentru că <math>P_C</math> se află pe curbă, înseamnă că satisface ecuaţia ei.

<math>P_C = P_1B_{0,2}(t_c) + P_2B_{1,2}(t_c) + P_3B_{2,2}(t_c)</math>, unde <math>P_2</math> este punctul pe care trebuie să-l aflăm. Ţinând cont că P_C este definit pentru un anumit <math>t_c</math>, trebuie să-l aflăm pentru a putea afla <math>P_2</math> folosind doar ecuaţia liniară scrisă anterior.

O metodă bună de a aproxima t-ul cunoscând un punct de pe curbă este printr-un raport al distanţelor.

Cunoscând <math>t_c</math> putem scrie soluţia ecuaţiei:

În continuare codul sursă Java care implementează interpolarea a trei puncte folosind o curbă Bézier de ordinul doi. import java.awt.geom.Point2D;

/**


* 
* @author cristi
*/

public class BezierUtils {
	/**
	 * Functia ia ca parametri trei puncte de pe curba si intoarce un array de 
	 * trei elemente care sunt punctele pentru definirea curbei Bezier de ordinul
	 * doi care trece prin cele trei puncte (Interpolare).
	 * @param x0 Primul punct de pe curba
	 * @param x3 Al doilea punct de pe curba
	 * @param x2 Al treilea punct de pe curba
	 * @return Point2D.Float[]
	 */
	public static Point2D.Float[] getQuadInterpPoints(Point2D.Float x0, Point2D.Float x3, Point2D.Float x2) {
		Point2D.Float[] result = new Point2D.Float[3];
		result[0] = new Point2D.Float(x0.x, x0.y);
		result[2] = new Point2D.Float(x2.x, x2.y);
		result[1] = new Point2D.Float();
		double t = x0.distance(x3) / (x0.distance(x3) + x3.distance(x2));
		result[1].x = ((float)((x3.getX() - fq2(t)*x2.getX() - fq0(t)*x0.getX())/fq1(t)));
		result[1].y = ((float)((x3.getY() - fq2(t)*x2.getY() - fq0(t)*x0.getY())/fq1(t)));
		return result;
	}
	/**
	 * Polinomul Bernstein de indice 0 si ordin 2
	 * @param t
	 * @return
	 * 	returneaza valoarea polinomului Bernstein B_{k,n}(t) in t, k - indice, n - ordin
	 */
	private static double fq0(double t) {
		return Math.pow((1-t), 2);
	}
	/**
	 * Polinomul Bernstein de indice 1 si ordin 2
	 * @param t
	 * @return
	 * 	returneaza valoarea polinomului Bernstein B_{k,n}(t) in t, k - indice, n - ordin
	 */
	private static double fq1(double t) {
		return 2*t*(1-t);
	}
	/**
	 * Polinomul Bernstein de indice 2 si ordin 2
	 * @param t
	 * @return
	 * 	returneaza valoarea polinomului Bernstein B_{k,n}(t) in t, k - indice, n - ordin
	 */
	private static double fq2(double t) {
		return Math.pow(t, 2);
	}	
	public static void main(String[] args) {
		Point2D.Float P1 = new Point2D.Float(10,10);
		Point2D.Float PC = new Point2D.Float(30,50);
		Point2D.Float P3 = new Point2D.Float(15,20);

Point2D.Float bezPoints[] = getQuadInterpPoints(P1, PC, P3); System.out.println("Curba Bezier este definita de:"); System.out.println(bezPoints[0]); System.out.println(bezPoints[1]); System.out.println(bezPoints[2]); } }

Interpolarea a patru puncte

Cunoştem patru puncte <math>P_1, P_{C1}, P_{C2}, P_4</math>, dintre care două puncte sunt pe curbă şi două reprezintă capetele acesteia. Punctele <math>P_{C1}</math> şi <math>P_{C2}</math> verifică ecuaţia curbei pentru <math> t_{c1}</math> şi respectiv <math>t_{c2}</math>. Pentru a putea obţine un sistem de două ecuaţii cu două necunoscute (<math>P_2, P_3</math>) trebuie să aproximăm cumva t-urile. Voi folosi aceeaşi metodă ca la interpolarea prin trei puncte:

Cunoscând t-urile pentru punctele de pe curbă putem scrie ecuaţiile sistemului:

<math>\begin{cases}P_{C1} = B_{0,3}(t_{c1})P_1 + B_{1,3}(t_{c1})P_2 + B_{2,3}(t_{c1})P_3 + B_{3,3}(t_{c1})P_4 \\ P_{C2} = B_{0,3}(t_{c2})P_1 + B_{1,3}(t_{c2})P_2 + B_{2,3}(t_{c2})P_3 + B_{3,3}(t_{c2})P_4\end{cases}</math>

Rezolvând sistemul se obţine:

<math>\begin{cases}P_2 = - \frac{B_{2,3}(t_{c1})P_{C2} - B_{2,3}(t_{c2})P_{C1} +(B_{2,3}(t_{c2})B_{3,3}(t_{c1}) - B_{2,3}(t_{c1})B_{3,3}(t_{c2}))P_4 + (B_{0,3}(t_{c1})B_{2,3}(t_{c2}) - B_{0,3}(t_{c2})B_{2,3}(t_{c1}))P_1}{B_{1,3}(t_{c1})B_{2,3}(t_{c2}) - B_{1,3}(t_{c2})B_{2,3}(t_{c1})} \\ P_3 = \frac{B_{1,3}(t_{c1})P_{C2} - B_{1,3}(t_{c2})P_{C1} +(B_{1,3}(t_{c2})B_{3,3}(t_{c1}) - B_{1,3}(t_{c1})B_{3,3}(t_{c2}))P_4 + (B_{0,3}(t_{c1})B_{1,3}(t_{c2}) - B_{0,3}(t_{c2})B_{1,3}(t_{c1}))P_1}{B_{1,3}(t_{c1})B_{2,3}(t_{c2}) - B_{1,3}(t_{c2})B_{2,3}(t_{c1})}\end{cases}</math>

În continuare codul sursă Java care implementează interpolarea a patru puncte folosind o curbă Bézier de ordinul trei.

import java.awt.geom.Point2D;

public class BezierUtils {

/** * Ecuatiile sunt rezolvate in Maxima 0.7.0a folosind urmatoarele * eqn: x4 = x0*f1(t4) + x1*f2(t4) + x2*f3(t4) + x3*f4(t4); * eqn1: x5 = x0*f1(t5) + x1*f2(t5) + x2*f3(t5) + x3*f4(t5); * algsys([eqn, eqn1], [x1, x2]); * * Functiile f1, f2, f3 si f4 sunt polinoamele Bernstein de ordinul 3. * * @param x0 * @param x4 * @param x5 * @param x3 * @return */ public static Point2D.Float[] getBezierInterpPoints(Point2D.Float x0, Point2D.Float x4, Point2D.Float x5, Point2D.Float x3) { Point2D.Float[] result = new Point2D.Float[4]; result[0] = new Point2D.Float(); result[0].x = x0.x; result[0].y = x0.y; result[3] = new Point2D.Float(); result[3].x = x3.x; result[3].y = x3.y;

float t4 = (float) (x0.distance(x4) / (x0.distance(x4) + x4.distance(x5) + x5.distance(x3))); float t5 = (float) ((x0.distance(x4) + x4.distance(x5)) / (x0.distance(x4) + x4.distance(x5) + x5.distance(x3)));

result[1] = new Point2D.Float(); result[2] = new Point2D.Float(); result[1].x = ((float) (-(f3(t4) * x5.x - f3(t5) * x4.x + (f4(t4) * f3(t5) - f3(t4) * f4(t5)) * x3.x + (f1(t4) * f3(t5) - f3(t4) * f1(t5)) * x0.x) / (f2(t4) * f3(t5) - f3(t4) * f2(t5)))); result[2].x = ((float) ((f2(t4) * x5.x - f2(t5) * x4.x + (f4(t4) * f2(t5) - f2(t4) * f4(t5)) * x3.x + (f1(t4) * f2(t5) - f2(t4) * f1(t5)) * x0.x) / (f2(t4) * f3(t5) - f3(t4) * f2(t5)))); result[1].y = ((float) (-(f3(t4) * x5.y - f3(t5) * x4.y + (f4(t4) * f3(t5) - f3(t4) * f4(t5)) * x3.y + (f1(t4) * f3(t5) - f3(t4) * f1(t5)) * x0.y) / (f2(t4) * f3(t5) - f3(t4) * f2(t5)))); result[2].y = ((float) ((f2(t4) * x5.y - f2(t5) * x4.y + (f4(t4) * f2(t5) - f2(t4) * f4(t5)) * x3.y + (f1(t4) * f2(t5) - f2(t4) * f1(t5)) * x0.y) / (f2(t4) * f3(t5) - f3(t4) * f2(t5)))); return result; }

/** * Polinomul Bernstein de indice 0 si de ordin 3 * * @param t */ private static double f1(double t) { return Math.pow((1 - t), 3); }

/** * Polinomul Bernstein de indice 1 si de ordin 3 * * @param t */ private static double f2(double t) { return 3 * t * Math.pow(1 - t, 2); }

/** * Polinomul Bernstein de indice 2 si de ordin 3 * * @param t */ private static double f3(double t) { return 3 * Math.pow(t, 2) * (1 - t); }

/** * Polinomul Bernstein de indice 3 si de ordin 3 * * @param t */ private static double f4(double t) { return Math.pow(t, 3); }

public static void main(String[] args) { Point2D.Float P1 = new Point2D.Float(0,0); Point2D.Float Pc1 = new Point2D.Float(50,50); Point2D.Float Pc2 = new Point2D.Float(100,60); Point2D.Float P4 = new Point2D.Float(100,0);

Point2D.Float[] bezCoords = getBezierInterpPoints(P1, Pc1, Pc2, P4); System.out.println("Curba Bezier cubica este data de:"); System.out.println(bezCoords[0]); System.out.println(bezCoords[1]); System.out.println(bezCoords[2]); System.out.println(bezCoords[3]); } }

Personal tools

Curbe Bezier - linux360

Search

Navigation

Tools