Curva de Bézier píxel a píxel

Este grupo de expertos luego de muchos días de trabajo y de recopilar de datos, hallamos los datos necesarios, queremos que te sea útil en tu plan.

Solución:

Una variación del algoritmo de Bresenham funciona con funciones cuadráticas como círculos, elipses y parábolas, por lo que también debería funcionar con curvas cuadráticas de Bezier.

Iba a intentar una implementación, pero luego encontré una en la web: http://members.chello.at/~easyfilter/bresenham.html.

Si desea más detalles o ejemplos adicionales, la página mencionada anteriormente tiene un enlace a un PDF de 100 páginas que explica el método: http://members.chello.at/~easyfilter/Bresenham.pdf.

Aquí está el código del sitio de Alois Zingl para trazar cualquier curva de Bezier cuadrática. La primera rutina subdivide la curva en cambios de gradiente horizontal y vertical:

void plotQuadBezier(int x0, int y0, int x1, int y1, int x2, int y2)
 /* plot any quadratic Bezier curve */
  int x = x0-x1, y = y0-y1;
  double t = x0-2*x1+x2, r;
  if ((long)x*(x2-x1) > 0)  /* horizontal cut at P4? */
    if ((long)y*(y2-y1) > 0) /* vertical cut at P6 too? */
      if (fabs((y0-2*y1+y2)/t*x) > abs(y))  /* which first? */
        x0 = x2; x2 = x+x1; y0 = y2; y2 = y+y1; /* swap points */
       /* now horizontal cut at P4 comes first */
    t = (x0-x1)/t;
    r = (1-t)*((1-t)*y0+2.0*t*y1)+t*t*y2; /* By(t=P4) */
    t = (x0*x2-x1*x1)*t/(x0-x1); /* gradient dP4/dx=0 */
    x = floor(t+0.5); y = floor(r+0.5);
    r = (y1-y0)*(t-x0)/(x1-x0)+y0; /* intersect P3 
  if ((long)(y0-y1)*(y2-y1) > 0)  P0 P1 */
    plotQuadBezierSeg(x0,y0, floor(r+0.5),y, x,y);
    r = (x1-x2)*(t-y2)/(y1-y2)+x2; /* intersect P7 
  plotQuadBezierSeg(x0,y0, x1,y1, x2,y2); /* remaining part */

La segunda rutina en realidad traza un segmento de curva Bezier (uno sin cambios de gradiente):

void plotQuadBezierSeg(int x0, int y0, int x1, int y1, int x2, int y2)
 /* plot a limited quadratic Bezier segment */
  int sx = x2-x1, sy = y2-y1;
  long xx = x0-x1, yy = y0-y1, xy; /* relative values for checks */
  double dx, dy, err, cur = xx*sy-yy*sx; /* curvature */
  assert(xx*sx <= 0 && yy*sy <= 0); /* sign of gradient must not change */
  if (sx*(long)sx+sy*(long)sy > xx*xx+yy*yy)  /* begin with longer part */
    x2 = x0; x0 = sx+x1; y2 = y0; y0 = sy+y1; cur = -cur; /* swap P0 P2 */
  
  if (cur != 0)  /* no straight line */
    xx += sx; xx *= sx = x0 < x2 ? 1 : -1; /* x step direction */
    yy += sy; yy *= sy = y0 < y2 ? 1 : -1; /* y step direction */
    xy = 2*xx*yy; xx *= xx; yy *= yy; /* differences 2nd degree */
    if (cur*sx*sy < 0)  /* negated curvature? */
      xx = -xx; yy = -yy; xy = -xy; cur = -cur;
    
    dx = 4.0*sy*cur*(x1-x0)+xx-xy; /* differences 1st degree */
    dy = 4.0*sx*cur*(y0-y1)+yy-xy;
    xx += xx; yy += yy; err = dx+dy+xy; /* error 1st step */
    do 
      setPixel(x0,y0); /* plot curve */
      if (x0 == x2 && y0 == y2) return; /* last pixel -> curve finished */
      y1 = 2*err < dx; /* save value for test of y step */
      if (2*err > dy)  x0 += sx; dx -= xy; err += dy += yy;  /* x step */
      if ( y1 )  y0 += sy; dy -= xy; err += dx += xx;  /* y step */
     while (dy < 0 && dx > 0); /* gradient negates -> algorithm fails */
  
  plotLine(x0,y0, x2,y2); /* plot remaining part to end */

El código para suavizado también está disponible en el sitio.

Las funciones correspondientes del sitio de Zingl para curvas de Bezier cúbicas son

void plotCubicBezier(int x0, int y0, int x1, int y1,
  int x2, int y2, int x3, int y3)
 /* plot any cubic Bezier curve */
  int n = 0, i = 0;
  long xc = x0+x1-x2-x3, xa = xc-4*(x1-x2);
  long xb = x0-x1-x2+x3, xd = xb+4*(x1+x2);
  long yc = y0+y1-y2-y3, ya = yc-4*(y1-y2);
  long yb = y0-y1-y2+y3, yd = yb+4*(y1+y2);
  float fx0 = x0, fx1, fx2, fx3, fy0 = y0, fy1, fy2, fy3;
  double t1 = xb*xb-xa*xc, t2, t[5];
  /* sub-divide curve at gradient sign changes */
  if (xa == 0)  /* horizontal */
    if (abs(xc) < 2*abs(xb)) t[n++] = xc/(2.0*xb); /* one change */
   else if (t1 > 0.0)  /* two changes */
    t2 = sqrt(t1);
    t1 = (xb-t2)/xa; if (fabs(t1) < 1.0) t[n++] = t1;
    t1 = (xb+t2)/xa; if (fabs(t1) < 1.0) t[n++] = t1;
  
  t1 = yb*yb-ya*yc;
  if (ya == 0)  /* vertical */
    if (abs(yc) < 2*abs(yb)) t[n++] = yc/(2.0*yb); /* one change */
   else if (t1 > 0.0)  /* two changes */
    t2 = sqrt(t1);
    t1 = (yb-t2)/ya; if (fabs(t1) < 1.0) t[n++] = t1;
    t1 = (yb+t2)/ya; if (fabs(t1) < 1.0) t[n++] = t1;
  
  for (i = 1; i < n; i++) /* bubble sort of 4 points */
    if ((t1 = t[i-1]) > t[i])  t[i-1] = t[i]; t[i] = t1; i = 0; 
    t1 = -1.0; t[n] = 1.0; /* begin / end point */
    for (i = 0; i <= n; i++)  /* plot each segment separately */
    t2 = t[i]; /* sub-divide at t[i-1], t[i] */
    fx1 = (t1*(t1*xb-2*xc)-t2*(t1*(t1*xa-2*xb)+xc)+xd)/8-fx0;
    fy1 = (t1*(t1*yb-2*yc)-t2*(t1*(t1*ya-2*yb)+yc)+yd)/8-fy0;
    fx2 = (t2*(t2*xb-2*xc)-t1*(t2*(t2*xa-2*xb)+xc)+xd)/8-fx0;
    fy2 = (t2*(t2*yb-2*yc)-t1*(t2*(t2*ya-2*yb)+yc)+yd)/8-fy0;
    fx0 -= fx3 = (t2*(t2*(3*xb-t2*xa)-3*xc)+xd)/8;
    fy0 -= fy3 = (t2*(t2*(3*yb-t2*ya)-3*yc)+yd)/8;
    x3 = floor(fx3+0.5); y3 = floor(fy3+0.5); /* scale bounds to int */
    if (fx0 != 0.0)  fx1 *= fx0 = (x0-x3)/fx0; fx2 *= fx0; 
    if (fy0 != 0.0)  fy1 *= fy0 = (y0-y3)/fy0; fy2 *= fy0; 
    if (x0 != x3 

y

void plotCubicBezierSeg(int x0, int y0, float x1, float y1,
  float x2, float y2, int x3, int y3)

Como ha señalado Mike 'Pomax' Kamermans, la solución para las curvas cúbicas de Bezier en el sitio no está completa; en particular, existen problemas con las curvas de Bézier cúbicas de suavizado, y la discusión de las curvas de Bézier cúbicas racionales es incompleta.

Puede utilizar el algoritmo de De Casteljau para subdividir una curva en suficientes piezas para que cada subsección sea un píxel.

Esta es la ecuación para encontrar el [x,y] punto en una curva cuadrática en el intervalo T:

// Given 3 control points defining the Quadratic curve 
// and given T which is an interval between 0.00 and 1.00 along the curve.
// Note:
//   At the curve's starting control point T==0.00.
//   At the curve's ending control point T==1.00.

var x = Math.pow(1-T,2)*startPt.x + 2 * (1-T) * T * controlPt.x + Math.pow(T,2) * endPt.x; 
var y = Math.pow(1-T,2)*startPt.y + 2 * (1-T) * T * controlPt.y + Math.pow(T,2) * endPt.y; 

Para hacer un uso práctico de esta ecuación, puede ingresar alrededor de 1000 valores de T entre 0.00 y 1.00. Esto da como resultado un conjunto de 1000 puntos garantizados para estar a lo largo de la curva cuadrática.

El cálculo de 1000 puntos a lo largo de la curva probablemente sea un muestreo excesivo (algunos puntos calculados estarán en la misma coordenada de píxeles), por lo que querrá desduplicar los 1000 puntos hasta que el conjunto represente coordenadas de píxeles únicas a lo largo de la curva.

Existe una ecuación similar para las curvas Cubic Bezier.

A continuación, se muestra un código de ejemplo que traza una curva cuadrática como un conjunto de píxeles calculados:

var canvas=document.getElementById("canvas");
var ctx=canvas.getContext("2d");

var points=[];
var lastX=-100;
var lastY=-100;
var startPt=x:50,y:200;
var controlPt=x:150,y:25;
var endPt=x:250,y:100;

for(var t=0;t<1000;t++)
  var xyAtT=getQuadraticBezierXYatT(startPt,controlPt,endPt,t/1000);
  var x=parseInt(xyAtT.x);
  var y=parseInt(xyAtT.y);
  if(!(x==lastX && y==lastY))
    points.push(xyAtT);
    lastX=x;
    lastY=y;
  


$('#curve').text('Quadratic Curve made up of '+points.length+' individual points');

ctx.fillStyle='red';
for(var i=0;i

body background-color: ivory; 
#canvasborder:1px solid red; margin:0 auto; 

Q