{"id":224,"date":"2010-03-12T16:07:42","date_gmt":"2010-03-12T14:07:42","guid":{"rendered":"http:\/\/labs.miaumiau.cat\/?p=224"},"modified":"2011-07-29T14:42:38","modified_gmt":"2011-07-29T14:42:38","slug":"beziers-our-approach","status":"publish","type":"post","link":"https:\/\/www.miaumiau.cat\/?p=224","title":{"rendered":"Beziers (our approach…!)"},"content":{"rendered":"

\"Beziers\"<\/a><\/p>\n

Bezier curves are widely used in Flash for many effects, from tweening one property to drawing complex curves and surfaces, but we \u00a0have never found one Class that would allow us to work with them the way we wanted to.<\/p>\n

Our main goal writing one Class for Bezier manipulation is to have one tool that calculate Bezier interpolations for curves and surfaces of any degree, so the first thing to do was to study the mathematical model of the Bezier curves in these useful\u00a0article<\/a>. In the article the Bezier curves are treated as a combination of the Berstain polinomials which uses the factorial function that requires many calculations for high degrees.<\/p>\n

The previous problem is solved calculating the coefficients of the curve for the given control points and saving them on a buffer Array that helps us to speed up the calculation process for further interpolations. As the article suggests the interpolation of any curve is given in the [0 – 1] domain.<\/p>\n

The class itself is this one:
\n[as]
\npackage math {
\nimport flash.geom.Vector3D;<\/p>\n

\/**
\n* @author miaumiau.cat
\n* Clase que se encarga de generar una parametrizaci\u00f3n
\n* Bezier de trayectoria o superficie.
\n*
\n*\/
\npublic class Bezier {<\/p>\n

\/\/Variable que determina si se trabaja en 3D…
\npublic static var _3D : Boolean = false;<\/p>\n

\/\/Variable que permite tener los datos de la combinatoria para cada grado…
\nprivate static var combinatoriaData : Array = new Array();
\ncombinatoriaData[0] = [0];
\ncombinatoriaData[1] = [1];<\/p>\n

\/\/A part\u00edr de 2 se tienen la cantidad m\u00ednima de puntos para interpolar
\ncombinatoriaData[2] = new Array(1, 1);
\ncombinatoriaData[3] = new Array(1, 2, 1);
\ncombinatoriaData[4] = new Array(1, 3, 3, 1);
\ncombinatoriaData[5] = new Array(1, 4, 6, 4, 1);
\ncombinatoriaData[6] = new Array(1, 5, 10, 10, 5, 1);
\ncombinatoriaData[7] = new Array(1, 6, 15, 20, 15, 6, 1);
\ncombinatoriaData[8] = new Array(1, 7, 21, 35, 35, 21, 7, 1);
\ncombinatoriaData[9] = new Array(1, 8, 28, 56, 70, 56, 28, 8, 1);
\ncombinatoriaData[10] = new Array(1, 9, 36, 84, 126, 126, 84, 36, 9, 1);
\ncombinatoriaData[11] = new Array(1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1);
\ncombinatoriaData[12] = new Array(1, 11, 56, 165, 330, 462, 462, 330, 165, 56, 11, 1);<\/p>\n

\/\/Variables est\u00e1ticas que permiten guardar los valores de segmentaci\u00f3n de la malla (evita recalcular la cantidad de puntos…)
\nprivate static var Ne : uint = 0;
\nprivate static var Nn : uint = 0;
\nprivate static var paramsE : Array = new Array();
\nprivate static var paramsN : Array = new Array();<\/p>\n

\/\/Variable que contiene las constantes de la curva bezier para un grado y una parametrizaci\u00f3n (cantidad de puntos) fija.
\nprivate static var coeficientesCurva : Array = new Array();<\/p>\n

\/\/Funci\u00f3n que calcula los coeficientes de la curva…
\npublic static function bezier(t : Number, controlPoints : Vector.) : Vector3D {<\/p>\n

var salida : Vector3D = new Vector3D;
\nvar coeficientes : Array = new Array();
\nvar i : uint;
\nvar length : uint = controlPoints.length;
\nvar n : uint = length – 1;<\/p>\n

\/\/Si los valores de la combinatoria para la cantidad de puntos no estan definidos, los defino…
\nif(combinatoriaData[length] == undefined) {
\ncombinatoriaData[length] = setCoeficients(n);
\n}<\/p>\n

\/\/Determino los coeficientes…
\nfor (i = 0;i <= n; i++) {
\ncoeficientes[i] = combinatoriaData[length][i] * Math.pow(t, i) * Math.pow((1 – t), (n – i));
\n}<\/p>\n

\/\/Obtengo los valores de salida del vector3D…
\nfor(i = 0;i <= n; i++) {
\nsalida.x += coeficientes[i] * controlPoints[i].x;
\nsalida.y += coeficientes[i] * controlPoints[i].y;
\nsalida.z += coeficientes[i] * controlPoints[i].z;
\n}
\nsalida.w = 1;<\/p>\n

return salida;
\n}<\/p>\n

\/\/Funci\u00f3n que se encarga de obtener un conjunto de puntos xyz agrupados en un array para una curva bezier…
\npublic static function bezierPoints(m : uint, controlPoints : Array, borderDistance : Number = -1) : Vector. {
\nvar salida : Vector. = new Vector.();
\nvar length1 : uint = controlPoints.length;
\nvar n : uint = controlPoints.length – 1;
\nvar i : uint;
\nvar j : uint;<\/p>\n

\/\/Si los valores de la combinatoria para la cantidad de puntos no estan definidos, los defino…
\nif(combinatoriaData[length1] == undefined) {
\ncombinatoriaData[length1] = setCoeficients(n);
\n}<\/p>\n

\/\/Si no hay un arreglo que guarde la referencia para un grado definido, se define…
\nif(coeficientesCurva[n] == undefined) {
\ncoeficientesCurva[n] = new Array();
\n}<\/p>\n

\/\/Si no hay un arreglo que guarde los coeficientes para “m” puntos se define…
\n\/\/Se guarda un arreglo de cuatro dimensiones seg\u00fan la siguiente definici\u00f3n…
\n\/\/
\n\/\/coeficientes[n][m][j][i] donde:
\n\/\/n : grado,
\n\/\/m : cantidad de puntos a parametrizar,
\n\/\/j : vector de coeficientes para un valor de parametrizaci\u00f3n perteneciente al rango [0, 1]
\n\/\/i : coeficientes a multiplicar por cada punto para la parametrizaci\u00f3n anterior…
\n\/\/<\/p>\n

if(coeficientesCurva[n][m] == undefined) {
\ncoeficientesCurva[n][m] = new Array();
\nfor (j = 0;j < m; j++) {
\n\/\/Defino la parametrizaci\u00f3n…
\nvar delta : Number = j \/ (m – 1);
\ncoeficientesCurva[n][m][j] = new Array();
\nfor(i = 0;i <= n; i++) {
\ncoeficientesCurva[n][m][j].push(combinatoriaData[length1][i] * Math.pow(delta, i) * Math.pow((1 – delta), (n – i)));
\n}
\n}
\n}<\/p>\n

\/\/Obtengo los distintos puntos que componen el vector de salida…
\nfor(j = 0;j < m; j++) {
\nvar pointer : Vector3D = new Vector3D(0, 0, 0, 0);
\nfor(i = 0;i <= n; i++) { pointer.x += coeficientesCurva[n][m][j][i] * controlPoints[i].x; pointer.y += coeficientesCurva[n][m][j][i] * controlPoints[i].y; pointer.z += coeficientesCurva[n][m][j][i] * controlPoints[i].z; } salida.push(pointer); } \/\/En caso de requerir bordes fijos… if(borderDistance > 0) {
\n\/\/Determino la longitud de la curva y calculo el valor porcentual de la parametrizaci\u00f3n de 0 a 1
\nvar length : Number = 0;
\nfor(i = 1;i < salida.length; i++) {
\nlength += Vector3D.distance(salida[i], salida[i – 1]);
\n}
\nvar percentDistance : Number = borderDistance \/ length;
\nvar centerDistance : Number = (1 – 2 * percentDistance) \/ (m – 3);
\nvar parameters : Array = new Array();
\nvar relativeCoeficients : Array = new Array();
\nparameters.push(0);
\nfor(i = 0;i < m – 2; i++) {
\nparameters.push(percentDistance + i * centerDistance);
\n}
\nparameters.push(1);
\n\/\/Determino el nuevo grupo de coeficientes a utilizar dependiendo de la parametrizaci\u00f3n…
\nfor (j = 0;j < m; j++) {
\nrelativeCoeficients.push(new Array());
\nfor(i = 0;i <= n; i++) {
\nrelativeCoeficients[j].push(combinatoriaData[controlPoints.length][i] * Math.pow(parameters[j], i) * Math.pow((1 – parameters[j]), (n – i)));
\n}
\n}
\n\/\/Obtengo los nuevos puntos tomando en cuenta las separaciones requeridas…
\nsalida.length = 0;
\nfor(j = 0;j < m; j++) {
\nvar pointer1 : Vector3D = new Vector3D(0, 0, 0, 0);
\nfor(i = 0;i <= n; i++) {
\npointer1.x += relativeCoeficients[j][i] * controlPoints[i].x;
\npointer1.y += relativeCoeficients[j][i] * controlPoints[i].y;
\nif(_3D) pointer.z += relativeCoeficients[j][i] * controlPoints[i].z;
\n}
\nsalida.push(pointer1);
\n}
\n}<\/p>\n

return salida;
\n}<\/p>\n

\/\/Funci\u00f3n que devuelve una superficie Bezier de MxN puntos de control (de borde e internos), se diferencia del patch porque esta \u00faltima solo permite el control con las curvas de borde (no hay puntos internos…)
\npublic static function surface(u_cps : uint, points : Vector., Ne : uint = 10, Nn : uint = 10, force : uint = 1) : Vector. {<\/p>\n

var i : uint;
\nvar j : uint;
\nvar k : uint;
\nvar r : uint;
\nvar output : Vector. = new Vector.();
\nvar v_cps : uint = points.length \/ u_cps;
\nvar cp_curves : Array = new Array();<\/p>\n

\/\/Separo los puntos para obtener cada curva…
\nfor(i = 0; i < u_cps; i++) {
\ncp_curves[i] = new Vector.();
\nfor(j = i; j <= v_cps * (u_cps – 1) + i; j += u_cps) {
\nfor(r = 0; r < force; r ++) {
\ncp_curves[i].push(points[j]);
\n}
\n}
\n}<\/p>\n

\/\/Genero los par\u00e1metros si no estan definidos…
\nif(Bezier.Ne != Ne && Bezier.Nn != Ne) {
\nBezier.Ne = Ne;
\nBezier.Nn = Nn;
\nparamsN = [];
\nparamsE = [];
\nfor (i = 1;i <= Nn; i++) {
\nparamsN.push((i – 1) \/ (Nn – 1));
\n}<\/p>\n

for (i = 1;i <= Ne; i++) {
\nparamsE.push((i – 1) \/ (Ne – 1));
\n}
\n}<\/p>\n

\/\/Genero el arreglo de puntos…
\nvar jMax : uint = paramsN.length;
\nvar iMax : uint = paramsE.length;<\/p>\n

for (j = 0;j < jMax; j++) {<\/p>\n

\/\/Conjunto de puntos obtenidos de evaluar las curvas verticales…
\nvar resultant_curve : Vector. = new Vector.();
\nfor(k = 0; k < cp_curves.length; k++) {
\nfor(r = 0; r < force; r++) {
\nresultant_curve.push(bezier(paramsN[j], cp_curves[k]));
\n}
\n}<\/p>\n

\/\/De los puntos obtenidos de las curvas verticales se obtiene una curva horizontal que al ser evaluada entrega cada punto de la superficie…
\nfor (i = 0;i < iMax; i++) {
\noutput.push(bezier(paramsE[i], resultant_curve));
\n}
\n}
\nreturn output;
\n}<\/p>\n

\/\/Funci\u00f3n que se encarga de conseguir todos los puntos de una malla generada por bordes…
\n\/\/Entrega los puntos ordenados de la siguiente manera suponiendo un arreglo de 3X3…
\n\/\/
\n\/\/ 0 1 2
\n\/\/ 3 4 5
\n\/\/ 6 7 8
\n\/\/<\/p>\n

public static function getPatch(Xt0 : Vector3D, Xt1 : Vector3D, Xb0 : Vector3D, Xb1 : Vector3D, BT : Array, BB : Array, BL : Array, BR : Array, Ne : uint = 10, Nn : uint = 10, borderSeparation : Number = -1) : Array {<\/p>\n

var i : uint;
\nvar points : Array = new Array();<\/p>\n

\/\/Obtengo los puntos de las curvas para interpolar…
\nvar b_top : Vector. = Bezier.bezierPoints(Ne, BT, borderSeparation);
\nvar b_bottom : Vector. = Bezier.bezierPoints(Ne, BB, borderSeparation);
\nvar b_left : Vector. = Bezier.bezierPoints(Nn, BL, borderSeparation);
\nvar b_right : Vector. = Bezier.bezierPoints(Nn, BR, borderSeparation);<\/p>\n

\/\/Genero los par\u00e1metros si no estan definidos…
\nif(Bezier.Ne != Ne && Bezier.Nn != Ne) {
\nBezier.Ne = Ne;
\nBezier.Nn = Nn;
\nparamsN = [];
\nparamsE = [];
\nfor (i = 1;i <= Nn; i++) {
\nparamsN.push((i – 1) \/ (Nn – 1));
\n}<\/p>\n

for (i = 1;i <= Ne; i++) {
\nparamsE.push((i – 1) \/ (Ne – 1));
\n}
\n}<\/p>\n

\/\/Genero el arreglo de puntos…
\nvar j : uint;
\nvar jMax : uint = paramsN.length;
\nvar iMax : uint = paramsE.length;
\nfor (i = 0;i < iMax; i++) {
\nfor (j = 0;j < jMax; j++) {
\npoints.push(TFI(paramsE[i], paramsN[j], b_top[i], b_bottom[i], b_left[j], b_right[j], Xt0, Xt1, Xb0, Xb1));
\n}
\n}
\nreturn points;
\n}<\/p>\n

\/\/Funci\u00f3n que permite liberar la memoria de la clase Bezier…
\npublic static function clearMemory() : void {
\ncoeficientesCurva = [];
\nparamsN = [];
\nparamsE = [];
\ncombinatoriaData = [];<\/p>\n

coeficientesCurva = paramsN = paramsE = combinatoriaData = null;
\n}<\/p>\n

\/\/Funci\u00f3n que genera una interpolaci\u00f3n tranfinita TFI para un grupo de cuatro curvas de borde bezier.
\n\/\/Se pasan los puntos de borde Xt0, Xt1, Xb0, Xb1 y los valores e, n definidos de 0 a 1 para pasar de
\n\/\/estado plano al definido por las cuatro curvas… se busca generar los puntos P intermedios…
\n\/\/
\n\/\/
\n\/\/ Xt0 Xt Xt Xt Xt Xt Xt Xt1
\n\/\/ Xl Xr
\n\/\/ Xl Xr
\n\/\/ Xl P Xr
\n\/\/ Xl Xr
\n\/\/ Xl Xr
\n\/\/ Xl Xr
\n\/\/ Xl Xr
\n\/\/ Xb0 Xb Xb Xb Xb Xb Xb Xb1
\n\/\/
\n\/\/
\nprivate static function TFI(e : Number, n : Number, Xt : Vector3D, Xb : Vector3D, Xl : Vector3D, Xr : Vector3D , Xt0 : Vector3D, Xt1 : Vector3D, Xb0 : Vector3D, Xb1 : Vector3D) : Vector3D {<\/p>\n

var TFIPoint : Vector3D = new Vector3D();<\/p>\n

\/\/Eval\u00fao la interpolaci\u00f3n para cada coordenada del punto, x, y, z…
\nTFIPoint.x = (1 – n) * Xt.x + n * Xb.x + (1 – e) * Xl.x + e * Xr.x – (e * n * Xb1.x + e * (1 – n) * Xt1.x + n * (1 – e) * Xb0.x + (1 – n) * (1 – e) * Xt0.x);
\nTFIPoint.y = (1 – n) * Xt.y + n * Xb.y + (1 – e) * Xl.y + e * Xr.y – (e * n * Xb1.y + e * (1 – n) * Xt1.y + n * (1 – e) * Xb0.y + (1 – n) * (1 – e) * Xt0.y);
\nif(_3D) TFIPoint.z = (1 – n) * Xt.z + n * Xb.z + (1 – e) * Xl.z + e * Xr.z – (e * n * Xb1.z + e * (1 – n) * Xt1.z + n * (1 – e) * Xb0.z + (1 – n) * (1 – e) * Xt0.z);
\nTFIPoint.w = 1;
\nreturn TFIPoint;
\n}<\/p>\n

\/\/Funci\u00f3n que realiza un set de los coeficientes en caso que cantidad de puntos sean distintos a los valores almacenados…
\nprivate static function setCoeficients(n : Number) : Array {
\nvar datos : Array = new Array();
\nvar i : Number;
\nfor (i = 0;i <= n; i++) {
\ndatos.push(MathFunctions.combinatoria(n, i));
\n}
\nreturn datos;
\n}<\/p>\n

\/\/f\u00edn del programa….
\n}
\n}
\n[\/as]<\/p>\n

As you can see all the comments are written in Spanish and many functions have so many parameters that is somehow difficult to understand what these functions do, so i\u00b4ll try to explain every function and it\u00b4s implementation in this post and in the near future post. Anyway i\u00b4ll comment some important features of it.<\/p>\n

The combinatoriaData Array is a set of coefficients of the Berstain polinomials that are pre-calculated for degrees lower than 12, this helps us to speed the initial calculation for one interpolation. If you are going to work with a higher degree, the program calculates the coefficients for that degree and saves the values on the array.<\/p>\n

The bezier function is the simplest function of the class, it allows to interpolate one single 3D point from a set of controlPoints and a parameter value between 0 an 1. You can use this function to get the interpolation point to point.<\/p>\n

The bezierPoints function does the same thing but gives all the points of the interpolation in one array, you have to note that the “m” value is the number of points that you want to interpolate. \u00a0Since all the points are equidistant in the domain space you can\u00b4t control interpolation by distance from point to point in the parameter space, but there\u00b4s one parameter that allows you to at least control the initial distance between borders and the next \/ previous parameter point, if you would like one margin if you are treating with surfaces (i\u00b4ll promise i\u00b4ll make one example of this, because it\u00b4s difficult to understand just by reading it).<\/p>\n

The surface function does the same thins that Away3D\u00b4s bezier surface function except that you can define the MxN control points as you want (not just 4X4 surface). To use the function you have to pass the M dimension, the Vector with the MxN points and the segmentation for the U,V direction of the surface. The last parameter, the “force” is the repetition of the control points in the surface to simulate weights \u00a0for a given controlPoints, this makes the surface approximate more to the controlPoints resulting more like a Nurbs curve with the same controlPoints.\u00a0The previos function is used to calculate the surface in this post<\/a> .<\/p>\n

The getPatch function also returns a surface, but this surface has the property of being controlled only by the curves that defines the borders of the surface, it means that the internal values of the surface are only border dependant and there are no internal controlPoints for this surface. This function is more complicated to use, but is more versatil in some applications like transitions and deformations.
\nFinally we have written one simple implementation of this class using only the fist function “Bezier.bezier()”. If you want to see it, just click on the image in above and relax!.<\/p>\n","protected":false},"excerpt":{"rendered":"

Bezier curves are widely used in Flash for many effects, from tweening one property to drawing complex curves and surfaces, but we \u00a0have never found one Class that would allow us to work with them the way we wanted to. Our main goal writing one Class for Bezier manipulation is to have one tool that […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-224","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=\/wp\/v2\/posts\/224","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=224"}],"version-history":[{"count":2,"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=\/wp\/v2\/posts\/224\/revisions"}],"predecessor-version":[{"id":671,"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=\/wp\/v2\/posts\/224\/revisions\/671"}],"wp:attachment":[{"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.miaumiau.cat\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}