### Probando el raytracing en AS3

24, Mar 2010/Categories 3D, AS3/No Comments

VIEW EXAMPLE

Some time ago I wanted to program a ray tracer on real time. The main problem I faced is that ray tracing is difficult to compute, because the quantity of calculations grows when you place more objects on the scene. In order to get a good frame rate I needed to reduce the calculations per frame to a minimum.

So I started with something very simple: one cube, one sphere and one light. The algorithm trows one ray per pixel of the image from the camera to the scene, checking if it collides with any object on the scene. In the first tries, besides the simplicity of the scene (five squares and one sphere), the performance was very bad. Since I couldn´t reduce more the quantity of objects to show, I had to make some improvements, sacrificing the code legibility, until the point of placing all the functionality in one single function in the style of spaghetti code. I wish I could have a goto instruction in AS3!.

Finally, as a final optimization, every image is drawn in a very small bitmapData, this data is then scaled through the smoothing option found in the Bitmap Class finding the final image with a more useful size. In this case the distortion is very clear, so I “killed” the sphere.

If you are curious, these raytracers are very interesting:
· www.strille.net/works/as3/raytracer/
· www.laserpirate.com/as3raytracer
· www.peternitsch.net/blog/?p=182

#### Original post in Spanish

Hacía tiempo que tenía en mente programar un ray tracer en tiempo real. El principal problema al que me enfrentaba es que el raytracing es costoso de computar, aumentando la cantidad de cálculos cuantos más objetos hay en la escena. Para conseguir un buen frame rate necesitaba reducir al máximo los cálculos por cada frame.

Así que decidí probar con algo sencillo: un cubo, una esfera y una luz. Básicamente, el algoritmo lanza un rayo por cada píxel de imagen desde la cámara hacia la escena, comprobando si colisiona con algún objeto de la escena. En las primeras pruebas, a pesar de la sencillez de la escena (cinco cuadrados y una esfera), el rendimiento era bastante malo. Ya que no podía reducir más la cantidad de objetos a mostrar, tuve que echar mano de optimizaciones, sacrificando la legibilidad del código, hasta el punto de meter casi toda la funcionalidad en una función principal al estilo spaghetti code. Incluso eché en falta una instruccion goto en AS3.

Finalmente, como última optimización, cada imagen se dibuja en tamaño pequeño ampliandolo mediante la opción smoothing de la clase Bitmap a un tamaño más adecuado. En este caso la distorsión es muy clara, así que eliminé la esfera.

Si tenéis curiosidad, estos raytracers son interesantes:
· www.strille.net/works/as3/raytracer/
· www.laserpirate.com/as3raytracer
· www.peternitsch.net/blog/?p=182

### Beziers (our approach…!)

12, Mar 2010/Categories AS3, General/No Comments

Bezier curves are widely used in Flash for many effects, from tweening one property to drawing complex curves and surfaces, but we  have 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 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 article. 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.

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.

The class itself is this one:
[as]
package math {
import flash.geom.Vector3D;

/**
* @author miaumiau.cat
* Clase que se encarga de generar una parametrización
* Bezier de trayectoria o superficie.
*
*/
public class Bezier {

//Variable que determina si se trabaja en 3D…
public static var _3D : Boolean = false;

//Variable que permite tener los datos de la combinatoria para cada grado…
private static var combinatoriaData : Array = new Array();

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

//Variables estáticas que permiten guardar los valores de segmentación de la malla (evita recalcular la cantidad de puntos…)
private static var Ne : uint = 0;
private static var Nn : uint = 0;
private static var paramsE : Array = new Array();
private static var paramsN : Array = new Array();

//Variable que contiene las constantes de la curva bezier para un grado y una parametrización (cantidad de puntos) fija.
private static var coeficientesCurva : Array = new Array();

//Función que calcula los coeficientes de la curva…
public static function bezier(t : Number, controlPoints : Vector.) : Vector3D {

var salida : Vector3D = new Vector3D;
var coeficientes : Array = new Array();
var i : uint;
var length : uint = controlPoints.length;
var n : uint = length – 1;

//Si los valores de la combinatoria para la cantidad de puntos no estan definidos, los defino…
}

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

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

return salida;
}

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

//Si los valores de la combinatoria para la cantidad de puntos no estan definidos, los defino…
}

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

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

if(coeficientesCurva[n][m] == undefined) {
coeficientesCurva[n][m] = new Array();
for (j = 0;j < m; j++) {
//Defino la parametrización…
var delta : Number = j / (m – 1);
coeficientesCurva[n][m][j] = new Array();
for(i = 0;i <= n; i++) {
coeficientesCurva[n][m][j].push(combinatoriaData[length1][i] * Math.pow(delta, i) * Math.pow((1 – delta), (n – i)));
}
}
}

//Obtengo los distintos puntos que componen el vector de salida…
for(j = 0;j < m; j++) {
var pointer : Vector3D = new Vector3D(0, 0, 0, 0);
for(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) {
//Determino la longitud de la curva y calculo el valor porcentual de la parametrización de 0 a 1
var length : Number = 0;
for(i = 1;i < salida.length; i++) {
length += Vector3D.distance(salida[i], salida[i – 1]);
}
var percentDistance : Number = borderDistance / length;
var centerDistance : Number = (1 – 2 * percentDistance) / (m – 3);
var parameters : Array = new Array();
var relativeCoeficients : Array = new Array();
parameters.push(0);
for(i = 0;i < m – 2; i++) {
parameters.push(percentDistance + i * centerDistance);
}
parameters.push(1);
//Determino el nuevo grupo de coeficientes a utilizar dependiendo de la parametrización…
for (j = 0;j < m; j++) {
relativeCoeficients.push(new Array());
for(i = 0;i <= n; i++) {
relativeCoeficients[j].push(combinatoriaData[controlPoints.length][i] * Math.pow(parameters[j], i) * Math.pow((1 – parameters[j]), (n – i)));
}
}
//Obtengo los nuevos puntos tomando en cuenta las separaciones requeridas…
salida.length = 0;
for(j = 0;j < m; j++) {
var pointer1 : Vector3D = new Vector3D(0, 0, 0, 0);
for(i = 0;i <= n; i++) {
pointer1.x += relativeCoeficients[j][i] * controlPoints[i].x;
pointer1.y += relativeCoeficients[j][i] * controlPoints[i].y;
if(_3D) pointer.z += relativeCoeficients[j][i] * controlPoints[i].z;
}
salida.push(pointer1);
}
}

return salida;
}

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

var i : uint;
var j : uint;
var k : uint;
var r : uint;
var output : Vector. = new Vector.();
var v_cps : uint = points.length / u_cps;
var cp_curves : Array = new Array();

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

//Genero los parámetros si no estan definidos…
if(Bezier.Ne != Ne && Bezier.Nn != Ne) {
Bezier.Ne = Ne;
Bezier.Nn = Nn;
paramsN = [];
paramsE = [];
for (i = 1;i <= Nn; i++) {
paramsN.push((i – 1) / (Nn – 1));
}

for (i = 1;i <= Ne; i++) {
paramsE.push((i – 1) / (Ne – 1));
}
}

//Genero el arreglo de puntos…
var jMax : uint = paramsN.length;
var iMax : uint = paramsE.length;

for (j = 0;j < jMax; j++) {

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

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

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

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 {

var i : uint;
var points : Array = new Array();

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

//Genero los parámetros si no estan definidos…
if(Bezier.Ne != Ne && Bezier.Nn != Ne) {
Bezier.Ne = Ne;
Bezier.Nn = Nn;
paramsN = [];
paramsE = [];
for (i = 1;i <= Nn; i++) {
paramsN.push((i – 1) / (Nn – 1));
}

for (i = 1;i <= Ne; i++) {
paramsE.push((i – 1) / (Ne – 1));
}
}

//Genero el arreglo de puntos…
var j : uint;
var jMax : uint = paramsN.length;
var iMax : uint = paramsE.length;
for (i = 0;i < iMax; i++) {
for (j = 0;j < jMax; j++) {
points.push(TFI(paramsE[i], paramsN[j], b_top[i], b_bottom[i], b_left[j], b_right[j], Xt0, Xt1, Xb0, Xb1));
}
}
return points;
}

//Función que permite liberar la memoria de la clase Bezier…
public static function clearMemory() : void {
coeficientesCurva = [];
paramsN = [];
paramsE = [];

coeficientesCurva = paramsN = paramsE = combinatoriaData = null;
}

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

var TFIPoint : Vector3D = new Vector3D();

TFIPoint.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);
TFIPoint.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);
if(_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);
TFIPoint.w = 1;
return TFIPoint;
}

//Función que realiza un set de los coeficientes en caso que cantidad de puntos sean distintos a los valores almacenados…
private static function setCoeficients(n : Number) : Array {
var datos : Array = new Array();
var i : Number;
for (i = 0;i <= n; i++) {
datos.push(MathFunctions.combinatoria(n, i));
}
return datos;
}

//fín del programa….
}
}
[/as]

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´ll try to explain every function and it´s implementation in this post and in the near future post. Anyway i´ll comment some important features of it.

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.

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.

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.  Since all the points are equidistant in the domain space you can´t control interpolation by distance from point to point in the parameter space, but there´s 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´ll promise i´ll make one example of this, because it´s difficult to understand just by reading it).

The surface function does the same thins that Away3D´s 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  for a given controlPoints, this makes the surface approximate more to the controlPoints resulting more like a Nurbs curve with the same controlPoints. The previos function is used to calculate the surface in this post .

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.
Finally 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!.

### Simple Surface Editor

08, Mar 2010/Categories 3D, AS3, General/No Comments

After we programmed the surface renderer for our last project, we decided to work a little more in order to implement a simple editor that could give use the opportunity to model simple objects based on a single surface. This editor enables us to work on further materials and uses for lighting, and it also allows us to make simple morphing surface animations in the near future.

The above image is a saddle modeled with the editor, the initial surface is a 7 x 7 RationalBezier Surface and all we did was to move points arround in order to get the shape done. The editor has a very easy interface to use, you can rotate the view by pressing on the screen and moving the mouse arround, when you press the control points you can drag them in 3d in order to adapt the shape to the convex hull made by the points.

There are some commands that enables you to view your model in differents  ways, these are:

• w” : sets the wireframe mode.
• t“: sets the texture mode.
• l“: shows or hides the yellow guides lines.
• c“: shows or hides the control points and the lights.
• r“: reset the mesh and the lights.

As you can see, you can model your object using the control points and the guide lines, changing your view on a wireframe to get the mesh without lighting and change the texture mode to see how the lights affect the mesh. You can also move the lights in every moment to see how the shading changes with the light´s position.

By the moment we have made two shapes with this editor, the first one is a simple attempt to make a basic surface with the shape of one mouse, and the next object was the saddle shown in the beginning of the post. The first mesh, the surface mouse, is shown on the next two images

Since the surface is a rational Bezier surface, there are some artifacts that happend  in the border with the texture, this is because the weight of the control points in the borders make the surface tessellate with less spacing around them. If you want to give it a try just press on the editor´s image (next image) and have fun!…