Matemáticas y ActionScript de curvas: degradados y normales

() translation by (you can also view the original English article)

Hemos abordado las curvas de dibujo y la búsqueda de sus raíces cuadráticas y cúbicas, así como aplicaciones útiles para usar raíces cuadráticas dentro de los juegos. Ahora, tal como prometimos, veremos aplicaciones para encontrar raíces cúbicas, así como gradientes y normales de las curvas, como hacer que los objetos reboten en superficies curvas. ¡Vamos!

Ejemplo

Echemos un vistazo a un uso práctico de esta matemática:

En esta demostración, el "barco" rebota en los bordes del SWF y la curva. El punto amarillo representa el punto más cercano a la nave que se encuentra en la curva. Puede ajustar la forma de la curva arrastrando los puntos rojos y ajustar el movimiento de la nave con las teclas de flecha.

Paso 1: Distancia más corta a una curva

Consideremos el escenario donde un punto se encuentra cerca de una curva cuadrática. ¿Cómo se calcula la distancia más corta entre el punto y la curva?

Bueno, comencemos con el Teorema de Pitágoras.

\[
Deja \ el \ punto \ ser \ (x_p, \ y_p) \\
y \ llama \ la \ cercano \ punto \ de \ la \ curva \ (X_c, \ y_c) \\
Entonces:\\
z^2 = x^2 + y^2\\
z^2 = (x_c-x_p)^2 + (y_c-y_p)^2\\
Dado\ y_c=ax_c^2 + bx_c + c,\\
z^2 = (x_c-x_p)^2 + [(ax_c^2 + bx_c + c) -y_p]^2
\]

Puedes ver que hemos sustituido \ (y_c \) con la ecuación cuadrática. A simple vista, podemos ver que la potencia más alta es 4. Por lo tanto, tenemos una ecuación cuártica. Todo lo que tenemos que hacer es encontrar un punto mínimo en esta ecuación para darnos la distancia más corta desde un punto a una curva cuadrática.

Pero antes de eso, tendremos que entender los gradientes en una curva ...

Paso 2: gradiente de una curva

Antes de ver el problema de minimizar una ecuación cuártica, intentemos comprender los gradientes de una curva. Una línea recta tiene solo un gradiente. Pero el gradiente de una curva cuadrática depende de qué punto de la curva nos referimos. Mira la presentación de Flash a continuación:

Arrastre los puntos rojos alrededor para cambiar la curva cuadrática. También puede jugar con el control deslizante para cambiar la posición del punto azul a lo largo de x. A medida que el punto azul cambia, también lo hará el gradiente dibujado.

Paso 3: gradiente a través del cálculo

Aquí es donde el cálculo será útil. Puede haber adivinado que diferenciar una ecuación cuadrática le daría el gradiente de la curva.

\[
f(x) = ax^2+bx+c\\
\frac{df(x)}{dx} = 2ax+b
\]

Entonces \ (\ frac {df (x)} {dx} \) es el gradiente de una curva cuadrática, y depende de la coordenada \ (x \). Bien, lo bueno es que tenemos un método para manejar esto: diff1 (x: Number) devolverá el valor después de una única diferenciación.

Para dibujar el degradado, necesitaremos una ecuación para representar la línea, \ (y = mx + c \). La coordenada del punto azul \ ((x_p, y_p) \) se sustituirá por \ (x \) y \ (y \), y el gradiente de la línea que se encuentra a través de la diferenciación irá a \ (m \). Por lo tanto, la intersección con el eje y de la línea, \ (c \) puede calcularse mediante algún trabajo de álgebra.

Mira el AS3:

var x:Number = s.value
var y:Number = quadratic_equation.fx_of(s.value)
point.x = x;
point.y = y;

/**
 * y = mx + c;
 * c = y - mx;  <== use this to find c
 */
var m:Number = quadratic_equation.diff1(x);
var c:Number =  y - m * x;

graphics.clear();
graphics.lineStyle(1, 0xff0000);
graphics.moveTo(0, c);
graphics.lineTo(stage.stageWidth, m * stage.stageWidth + c);

Paso 4: Sistemas de coordenadas

Siempre tenga en cuenta el eje y invertido del espacio de coordenadas del flash como se muestra en la imagen a continuación. A primera vista, el diagrama de la derecha puede parecer un gradiente negativo, pero debido al eje y invertido, en realidad es un gradiente positivo.

Lo mismo aplica para el punto mínimo como se indica a continuación. Debido al eje y invertido, el punto mínimo en el espacio de coordenadas cartesianas (en (0,0)) se ve como un máximo en el espacio de coordenadas del flash. Pero al referirse a la ubicación de origen en el espacio de coordenadas de Flash en relación con la curva cuadrática, en realidad es un punto mínimo.

Paso 5: Tasa de cambio para gradiente

Ahora digamos que estoy interesado en encontrar el punto más bajo en una curva, ¿cómo procedo? Echa un vistazo a la imagen a continuación (ambas figuras están en el mismo espacio de coordenadas).

Para obtener el punto mínimo, igualaremos \ (\ frac {df (x)} {dx} = 0 \), ya que por definición estamos buscando el punto donde el gradiente es cero. Pero como se muestra arriba, resulta que el punto máximo en una curva también satisface esta condición. Entonces, ¿cómo discriminamos entre estos dos casos?

Probemos la diferenciación del segundo grado. Nos dará la tasa de cambio del gradiente.

\[
\frac{df(x)}{dx} = 2ax+b\\
\frac{df^2(x)}{dx^2} = 2a
\]

Explicaré con referencia a la imagen a continuación (dibujada en el espacio de coordenadas cartesianas). Podemos ver que, a medida que aumentamos a lo largo del eje x, el gradiente cambia de negativo a positivo. Entonces la tasa de cambio debería ser un valor positivo.

También podemos ver que cuando \ (\ frac {df ^ 2 (x)} {dx ^ 2} \) es positivo, hay un punto mínimo en la curva. Por el contrario, si la tasa es negativa, hay un punto máximo presente.

Paso 6: volviendo al problema

Ahora estamos listos para resolver el problema presentado en el Paso 1. Recordamos la ecuación cuártica (donde el grado más alto es 4) a la que llegamos:

\[
z^2 = (x_c-x_p)^2 + [(ax_c^2 + bx_c + c) -y_p]^2
\]

La misma ecuación cuártica, trazada

Recuerde, estamos interesados en encontrar el punto mínimo en esta curva, porque el punto correspondiente en la curva cuadrática original será el punto que esté a la distancia mínima del punto rojo.

Entonces, diferenciemos la función cuártica para llegar al gradiente de esta curva y luego igualemos el gradiente de esta función cuártica a cero. Verás que el gradiente es en realidad una función cúbica. Dirigiré a los lectores interesados a la página de Wolfram; para este tutorial, solo obtendré el resultado de su funcionamiento de álgebra:

\[
\frac{d(z^2)}{dx}=
2(x_c-x_p) + 2(ax_c^2 + bx_c + c - y_p)(2ax_c+b)\\
\frac{d(z^2)}{dx}= 2a^2(x_c)^3+3ab(x_c)^2+(b^2+2ac-2ay_p+1)(x_c)+(bc-by_p-x_p)\\
Equiparan \ gradiente \ a \ 0 \\
\frac{d(z^2)}{dx}=0\\
2a^2(x_c)^3+3ab(x_c)^2+(b^2+2ac-2ay_p+1)(x_c)+(bc-by_p-x_p)=0\\
Comparar\ con\ ecuación\ cúbica\\
Ax^3+Bx^2+Cx+D=0\\
A = 2a^2\\
B=3ab\\
C=b^2+2ac-2ay_p+1\\
D=bc-by_p-x_p
\]

Resuelve las raíces de esta función cúbica (bastante desordenada) y llegaremos a las coordenadas de los tres puntos azules como se indicó anteriormente.

A continuación, ¿cómo filtramos nuestros resultados para el punto mínimo? Recuerda del paso anterior que un punto mínimo tiene una tasa de cambio positiva. Para obtener esta tasa de cambio, diferencia la función cúbica que representa el gradiente. Si la tasa de cambio para el punto azul dado es positiva, es uno de los puntos mínimos. Para obtener el punto mínimo, el que nos interesa, elija el punto con la tasa de cambio más alta.

Paso 7: muestra de salida

Así que aquí hay una implementación de muestra de la idea explicada anteriormente. Puede arrastrar los puntos rojos para personalizar su curva cuadrática. El punto azul también se puede arrastrar. A medida que mueva el punto azul, se volverá a colocar el amarillo para que la distancia entre los puntos azul y amarillo sea mínima entre todos los puntos de la curva.

A medida que interactúa con la presentación de Flash, puede haber momentos en que aparecen tres puntos amarillos a la vez. Dos de estos, desvanecidos, se refieren a las raíces obtenidas del cálculo, pero se rechazan porque no son los puntos más cercanos en la curva al punto azul.

Paso 8: Implementación de ActionScript

Así que aquí está la implementación de ActionScript de lo anterior. Puede encontrar el script completo en Demo2.as.

Antes que nada, tendremos que dibujar la curva cuadrática. Tenga en cuenta que se hará referencia a la matriz m2 para realizar más cálculos.

private function redraw_quadratic_curve():void 
{
    var cmd:Vector.<int> = new Vector.<int>;
    var coord:Vector.<Number> = new Vector.<Number>;
    
    //redraw curve;
    m1 = new Matrix3d(
        curve_points[0].x * curve_points[0].x, curve_points[0].x, 1, 0,
        curve_points[1].x * curve_points[1].x, curve_points[1].x, 1, 0,
        curve_points[2].x * curve_points[2].x, curve_points[2].x, 1, 0,
        0,0,0,1
    );
    
    m2 = new Matrix3d(
        curve_points[0].y, 0, 0, 0,
        curve_points[1].y, 0, 0, 0,
        curve_points[2].y, 0, 0, 0,
        0,0,0,1
    )
    
    m1.invert();
    m2.append(m1);
    quadratic_equation.define(m2.n11, m2.n21, m2.n31);
    
    for (var i:int = 0; i < stage.stageWidth; i+=2) 
    {
        if (i == 0) cmd.push(1);
        else		cmd.push(2);
        
        coord.push(i, quadratic_equation.fx_of(i));
    }
    
    graphics.clear();
    graphics.lineStyle(1);
    graphics.drawPath(cmd, coord);
}

Y aquí está el que implementa el concepto matemático explicado. c1 se refiere a un punto colocado al azar en el escenario.

private function recalculate_distance():void 
{
    var a:Number = m2.n11;	
    var b:Number = m2.n21;
    var c:Number = m2.n31;
    
    /*f(x) = Ax^3 + Bx^2 +Cx + D
     */
    var A:Number = 2*a*a
    var B:Number = 3*b*a
    var C:Number = b*b + 2*c*a - 2*a*c1.y +1
    var D:Number = c * b - b * c1.y - c1.x
    
    quartic_gradient = new EqCubic();
    quartic_gradient.define(A, B, C, D);
    quartic_gradient.calcRoots();
    
    roots = quartic_gradient.roots_R;
    var chosen:Number = roots[0];
    
    if (!isNaN(roots[1]) && !isNaN(roots[2])) {
        
        //calculate gradient and rate of gradient of all real roots
        var quartic_rate:Vector.<Number> = new Vector.<Number>;
        
        for (var i:int = 0; i < roots.length; i++) 
        {
            if (!isNaN(roots[i])) 	quartic_rate.push(quartic_gradient.diff1(roots[i]));
            else 					roots.splice(i, 1);
        }
        
        //select the root that will produce the shortest distance
        for (var j:int = 1; j < roots.length; j++) 
        {
            //the rate that corresponds with the root must be the highest positive value
            //because that will correspond with the minimum point
            if (quartic_rate[j] > quartic_rate[j - 1]) {
                chosen = roots[j];
            }
        }
        
        //position the extra roots in demo
        position_extras();
    }
    else {
        
        //remove the extra roots in demo
        kill_extras();
    }
    intersec_points[0].x = chosen
    intersec_points[0].y = quadratic_equation.fx_of(chosen);
}

Paso 9: Ejemplo: Detección de colisión

Hagamos uso de este concepto para detectar la superposición entre un círculo y una curva.

La idea es simple: si la distancia entre el punto azul y el punto amarillo es menor que el radio del punto azul, tenemos una colisión. Mira la demostración a continuación. Los elementos interactivos son los puntos rojos (para controlar la curva) y el punto azul. Si el punto azul choca con la curva, se desvanecerá un poco.

Paso 10: Implementación de ActionScript

Bueno, el código es bastante simple. Consulte la fuente completa en CollisionDetection.as.

graphics.moveTo(intersec_points[0].x, intersec_points[0].y);
graphics.lineTo(c1.x, c1.y);

var distance:Number= Math2.Pythagoras(
    intersec_points[0].x, 
    intersec_points[0].y, 
    c1.x, 
    c1.y)

if (distance < c1.radius)  c1.alpha = 0.5;
else                       c1.alpha = 1.0;

t.text = distance.toPrecision(3);

Paso 11: rebotando en la curva

Entonces, ahora que sabemos cuándo ocurrirá la colisión, intentemos programar alguna respuesta de colisión. ¿Qué hay de rebotar en la superficie? Mira la presentación de Flash a continuación.

Puedes ver el barco (forma de triángulo), está rodeado por un círculo (azul translúcido). Una vez que el círculo colisiona con la curva, la nave rebotará en la superficie.

Paso 12: Controlando la nave

Aquí está el código ActionScript para controlar la nave.

public function CollisionDetection2() 
{
    /**
     * Instantiation of ship & its blue-ish circular area
     */
    ship = new Triangle();	addChild(ship);
    ship.x = Math.random() * stage.stageWidth;
    ship.y = stage.stageHeight * 0.8;
    
    c1 = new Circle(0x0000ff, 15);	addChild(c1);
    c1.alpha = 0.2;
    
    /**
     * Ship's velocity
     */
    velo = new Vector2D(0, -1);
    updateShip();
    
    stage.addEventListener(KeyboardEvent.KEY_DOWN, handleKey);
    stage.addEventListener(KeyboardEvent.KEY_UP, handleKey);
    stage.addEventListener(Event.EXIT_FRAME, handleEnterFrame);
    
    /**
     * The curve and the calculations
     */
    quadratic_equation = new EqQuadratic();
    
    curve_points = new Vector.<Circle>;
    populate(curve_points, 0xff0000, 3);
    
    intersec_points = new Vector.<Circle>;
    populate(intersec_points, 0xffff00, 3, false);
    
    redraw_quadratic_curve();
}

private function handleKey(e:KeyboardEvent):void 
{
    if (e.type == "keyDown") {
        if (e.keyCode == Keyboard.UP) isUp = true;
        else if (e.keyCode == Keyboard.DOWN) isDown = true;
        if (e.keyCode == Keyboard.LEFT) isLeft = true;
        else if (e.keyCode == Keyboard.RIGHT) isRight = true;
    }
    if (e.type == "keyUp") {
        if (e.keyCode == Keyboard.UP) isUp = false;
        else if (e.keyCode == Keyboard.DOWN) isDown = false;
        if (e.keyCode == Keyboard.LEFT) isLeft = false;
        else if (e.keyCode == Keyboard.RIGHT) isRight = false;
    }
}

private function handleEnterFrame(e:Event):void 
{
    /**
     * Control the magnitude
     */
    if (isUp) 		velo.setMagnitude(Math.min(velo.getMagnitude()+0.2, 3));
    else if(isDown)	velo.setMagnitude(Math.max(velo.getMagnitude()-0.2, 1));
    
    /**
     * Control the direction
     */
    if (isRight) velo.setAngle(velo.getAngle() + 0.03);
    else if (isLeft) velo.setAngle(velo.getAngle() - 0.03);
    
    recalculate_distance();
    
    if (distance < c1.radius) bounce();
    updateShip();
}

/**
 * Update ship's position, orientation and it's area (the blue-ish circle)
 */
private function updateShip():void {
    ship.x += velo.x;
    ship.y += velo.y;
    ship.rotation = Math2.degreeOf(velo.getAngle());
    
    c1.x = ship.x; 
    c1.y = ship.y;
    
    if (ship.x > stage.stageWidth || ship.x < 0) velo.x *= -1;
    if (ship.y > stage.stageHeight || ship.y < 0) velo.y *= -1;
}

Puede ver que los controles del teclado están actualizando para indicar si se presionan las teclas de la izquierda, arriba, derecha o abajo. Estos indicadores serán capturados por el manejador de eventos enterframe y actualizarán la magnitud y dirección del barco.

Paso 13: Cálculo del vector de reflexión

Ya he cubierto el cálculo vectorial del vector de reflexión en esta publicación. Aquí, voy a cubrir cómo obtener el vector normal del gradiente.

\[
\frac{df(x)}{dx}=gradiente\\
linea\ gradiente=\frac{y}{x}\\
Asumir\ gradiente=0.5\\
y=0.5\\
x=1\\
Vector\ de\ izquierda\ normal=
\begin{bmatrix}-1 \\0.5\end{bmatrix}\\
Vector\ de\ derecha\ normal=
\begin{bmatrix}1 \\-0.5\end{bmatrix}
\]

Paso 14: Implementación de ActionScript

Entonces, el ActionScript a continuación implementará el concepto matemático explicado en el paso anterior. Mira las líneas resaltadas:

private function bounce():void 
{
    var gradient:Number = quadratic_equation.diff1(intersec_points[0].x);
    var grad_vec:Vector2D = new Vector2D(1, gradient);
    
    var left_norm:Vector2D = grad_vec.getNormal(false);
    var right_norm:Vector2D = grad_vec.getNormal();
    var chosen_vec:Vector2D;
    
    if (velo.dotProduct(left_norm) > 0) chosen_vec = left_norm
    else 								chosen_vec = right_norm
        
    var chosen_unit:Vector2D = chosen_vec.normalise();
    var proj:Number = velo.dotProduct(chosen_unit);
    
    chosen_unit.scale(-2*proj);
    
    velo = velo.add(chosen_unit);
}

Conclusión

Bien, gracias por tu tiempo! Si ha encontrado esto útil, o tiene alguna pregunta, deje algunos comentarios.