Surface Tracker

Surface Tracker

26, Jul 2010/Categories AS3, General/2 Comments

VIEW EXAMPLE

Many sites have been done implementing the interaction between video and photos, text, or any other additional assets that could be inserted in the original video to enhance the final experience. Tracking simple planes can be done very easy with the help of After-Effects or any other post- production software, but when it comes to track complex surfaces there is not a simple way to do it.
We were asked to develop one way to track surfaces for one project designed by David Navarro (www.davidnavarro.net). David wanted to track one t-shirt in order to place the users photo in the chest of the t-shirt. So after thinking how we could make it we got the main idea in five simple steps:
1. Track predefined control points placed in the t-shirt with the help of After-Effects.
2. Modify the video in order to create the mask and the shadings that would affect the mesh previously created.
3. Define one Nurbs-Mesh using the tracked control points in the t-shirt.
4. Create a color correction for the inserted image by the user.
5. Integrate the mesh and the video for the final result.

Tracking Control Points:
When it comes to track control points in a t-shirt the first idea that came to us was to draw a grid of points in a t-shirt, and try to track them with Motion. The main problem with it is that if you define an 8×8 grid you would end up tracking 64 for points per frame, (that would probably not be well tracked so you would be editing many frames in order to get the result that would be required).
So instead of tracking points we ended up tracking regions, these regions are defined as four corners areas that would be equidistantly defined in the original grid of points (see next image).

In the image below there is a rectangular region of the chest that would be changed with one image defined by the user. This region contains rectangular areas that would be tracked using Mocha (a plug-in for After Effects). Since all the squares share at least one corner with each other, only the black squares in the t-shirt must be tracked in order to get all the control points needed.
Once the squares are tracked for all the needed frames, you should re-order the four corners obtained for each square in order to rewrite the points in a row-column ordered format used to create one interpolated Nurbs Mesh. Finally you could export these points with the X, Y and Frame information in a XML to use in Action Script.

Video Masking and Shading:
Since we are not specialist in video post-production, we counted with the help of Manolo Calvo (www.freelancetv.es), he was responsible of the final tracking of the rectangular regions, but most important He was the guy that made the masking and shading of the video in order to superimpose lights and shadows to the generated mesh. Video masking can be done using the mesh generated with the original control points, one thing to take into account is that this mask should be smaller than the final integrated mesh in order to avoid holes between the mesh and the video.
In this work this was not the case, Manolo made the masking by hand, and he also painted the lights and shadows over the video in order to give us a final composition with the alpha channel ready to integrate the final mesh. In the next image you can see the final result of the video composition with the lights and shadows added.

Creating the Nurbs Mesh:
Using the Classes commented in these previous posts (http://labs.miaumiau.cat/?p=178, http://labs.miaumiau.cat/?p=338), we could interpolate one mesh with the original control points, the final mesh could have the resolution needed to show the final image in a flexible way, and it also allowed us to modify the behavior of the interpolation (the degree of the final mesh in the u,v directions). Depending of the typology of the surface you could decide the way you could interpolate the surface, if the internal points do not affect the final interpolation, you could interpolate using only the border curves of the surface, in the other hand if the surface has big changes in its interior you should interpolate using all the control points defined in the grid of the t-shirt (or the surface you are tracking in the video).

Color Correction:
The final video made by Manolo had desaturated colors, low values of contrast and also low values of brightness, so in order to adapt the final mesh to the video some color corrections should be done to the image inserted by the user. In order to do so we programmed a set of modifiers for a given bitmap data and we tried with many pictures in order to define the final values of contrast, brightness, saturation and blur that would by applied to each image inserted. Every time one image is going to be inserted in the t-shirt the values of these parameters are changed to make the final color correction.
Using this correction and the shading created over the video would give the illusion of integration between the mesh and the video.

Video and Mesh Integration:
Having the video post-produced with the alpha channel and the lights and shadows painted in the final composition, integrating the mesh for the final result is very easy. The mesh must one layer under the video so this last one can affect the mesh representation like a multiply blend mode.
So using the five previous commented steps, we have programmed one simple example (click on the first image) that shows the final integration in the video. You can change between one image or the webcam, you can also change the depth of the video and the mesh to see how the video affects the mesh, and finally you can see how the mesh is created.

Finally we would like to thanks Manolo & Ivan for their invaluable help with the video tracking and post-production for this project.

Elastic triangles

15, Jun 2010/Categories AS3, General/1 Comment

delaunay

DrawTriangles es una herramienta potente, nos permite no solo pintar una serie de líneas o rellenos planos en pantalla, sino que además podemos mapear imágenes en las mallas de triángulos que generemos, cosa que puede aprovecharse para manipular la forma de las imágenes de manera interactiva.

Imaginemos que tenemos un campo de puntos distribuidos equitativamente a modo de retícula. No resulta complicado calcular en todo momento la distancia de cada punto o nodo de la reticula con respecto al ratón.

Por otro lado también podríamos usar los eventos de ratón mouseDown y mouseUp, para calcular el número de pixeles que hemos arrastrado el ratón mientras apretábamos el botón. Ese resultado es el número de pixeles que debemos mover cada nodo de la retícula, en positivo o negativo, tanto en x como en y, con respecto a su posición actual. Si a ese movimiento le aplicamos una ecuación de movimiento oscilatorio y los valores de velocidad y elasticidad se asignasen en función de la distáncia que separa al puntero del ratón con respecto a cada nodo, tendríamos una malla de puntos que se puede arrastrar de forma interactiva y que además responde con mayor celeridad en el área mas próxima al ratón que en zonas alejadas.

Hay que tener cuidado ya que los números se pueden disparar a valores muy elevados en función del tamaño que tenga el objeto a mover y la velocidad con que se mueva el ratón. En este caso lo que se ha implementado es un sistema de control para que la velocidad aumente de manera cúbica dependiendo de la distáncia, pero solo hasta cierta constante apartir de la cual, la multiplicación se hace sobre esa constante. Con esto conseguimos que apartir de esa distancia, la velocidad crezca de manera lineal y no exponencial.

Esto nos lleva a la siguiente fase que es el pintado de triángulos. Básicamente se ha de generar un mapa UV para la imagen dada, es decir que tenemos que guardar en un vector, valores normalizados de 0 a 1 para cada vértice de cada triángulo que se va a tejer, tomando como base el grid original.

Para concluir debemos activar un enterFrame y en cada fotograma tendremos que redibujar la malla completa usando el mapa UV y usando los valores de posición de cada paso en el movimiento de los nodos.
Así conseguimos tener una imagen arrastrable que se deforma con el movimiento del ratón.

Jugando con este concepto y con más tiempo se podrían llegar a hacer experiencias tan gustosas como el MORISAWA FONT PARK de Tha.jp

Podéis descargar la clase para jugar con ella aquí.

Un saludo.

NURBS in Flash (part 2)

22, Apr 2010/Categories 3D, AS3, General/3 Comments

NURBS Curve

Working with surfaces in Flash can be done in many ways, Away3D offers one way to work with Bezier patches that is suitable for many things (one example of this is this very nice example of the Utah teapot), but if you want a more precise interpolation among the control points, the Nurbs surfaces give you more control over them.

Nurbs surfaces require to understand how the Nurbs curves work, We have written one post about it, so if you haven´t read it yet press here. The surfaces are a extension of the curves, the only thing is that you´ll need to parameters (u, v) in order to define the surface, so when you are going to calculate the surface you need to calculate the curves in one direction “V” and the results are used to calculate the curves in the next direction “U”.

The main advantage of Nurbs surfaces against Bezier surfaces is the control of the degree for each direction, this means that for each surface you have two independent degree values (degreeU, degreeV), that define the local control interpolation for each direction. Nurbs surfaces also count with the posibility to adapt the weight for each control point in order to make the surface go closer to that point.

The modeller presented in this post allows you to work with one Nurbs surface of 7X7 control points, you can change the degree for each direction, the segmentation for the whole surface and the distribution of the domain region parameters.

Surface Tessellation:

Nurbs surfaces can be seen as a two dimensional non linear transformation of a rectangular domain region  [0-1] [0-1] to a parameter region. This behaviour presents one problem when you try to tessellate the surface because if the parameters in the domain space are equally distributed, the result of the tessellation in the parameter space is not going to present the same equal distribution. In order to overcome this issue a couple of cubic transformations are used to define the distribution of the parameters, these curves are located in the surface editor of the modeller (the light blue boxes).

If you rotate the surface (try to make it when is plannar) and change the sliders of the boxes you will see how the distribution of the segments change, this should be done in the plannar case for each change of the degree in order to get an equal distribution in the parameter space.

These curves don´t solve the distribution problem in a exact way. The best thing to do is to calculate the parameter that should be used for each step forcing the condition of a fixed step between each point in the curve. This process requires to precalculate the curve, then calculate the curve´s length to define the step for each pair of points, and finally use the first derivates of the curves to calculate the needed parameter. The bad thing about the previous process is that it requires many iterations for a given parameter in order to evaluate if the parameter fits the defined fixed step, so this is not a good solution for real time rendering.

Degree U,V:

The change of the degree in each direction change the interpolation factor (local control) for each direction, the same control points (with the same weight definitions) can result in NxM differents surfaces (being N the number of control points in the U direction and M the number of control points in the V direction). So you can have a linear interpolation in one direction and cubic interpolation in the other (second image), or you can have a quadratic interpolation in one direction and a cubic interpolation in the other (third image).


Segmentation (level of detail):

One advantage of working with parametric surfaces (Bezier or Nurbs) is the total control of the level of detail for a given surface. The tessellation of the surface can be done evaluating the error of the aproximation from the parametric surface, this means that defining the error (distance from a given parametric point to the tessellated point in the surface) you could know exactly the segmentation needed o satisfy the error. In the modeller you have an option for segmentations changes in the surfaces if you want to have a better or worst aproximation.

Changes on the segmentation can be used in real time to satisfy a required frame rate and level of detail, if you have many surfaces on one scene, you could define more segments for the surfaces close to the camera and reduce segments for the surfaces away from the focal view. This would help to speed up the rendering of one scene. The last option in the Nurbs editor control the total segments used to tessellate the surface, you can model with low segmentations (keeping a high frame rate to move the points and rotate the shape), and then you can see the final result giving more segmentations to the surface.  If you want to try the modeller just press on the next image.

NURBS Surfaces

The code:

As it is explained before, implementing Nurbs surfaces require the use of Nurbs curves, so part of the actual code is explained here so only a new function is needed to calculate the surface tessellation, just copy the code from below in the Nurbs class (from part 1).
[as]
//Function that generate a Nurbs surface…
public static function surface(u_cps : uint, points : Vector., Ne : uint = 10, Nn : uint = 10, degreeU : uint = 3, degreeV : uint = 3, order : int = -1, cU : Number = 1, cV : Number = 1) : Vector. {
var i : uint;
var j : uint;
var k : uint;
var output : Vector. = new Vector.();
var v_cps : uint = points.length / u_cps;
var cp_curves : Array = new Array();
var param : Number;

//Separate the points for each curve…
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) {
cp_curves[i].push(points[j]);
}
}

//Generate parameters if they are not defined…
if(Nurbs.Ne != Ne) {
Nurbs.Ne = Ne;
paramsE = [];
for (i = 1;i <= Ne; i++) {
param = (i – 1) / (Nn – 1);
paramsE.push(-2 * (1 – cV) * Math.pow(param, 3) + 3 * (1 – cV) * Math.pow(param, 2) + cV * param);
}
}

if(Nurbs.Nn != Nn) {
Nurbs.Nn = Nn;
paramsN = [];
for (i = 1;i <= Nn; i++) {
param = (i – 1) / (Nn – 1);
paramsN.push(-2 * (1 – cU) * Math.pow(param, 3) + 3 * (1 – cU) * Math.pow(param, 2) + cU * param);
}
}

var jMax : uint = paramsN.length;
var iMax : uint = paramsE.length;

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

//Points for the “V” curves…
var resultant_curve : Vector. = new Vector.();
for(k = 0;k < cp_curves.length; k++) {
resultant_curve.push(nurbs(paramsN[j], cp_curves[k], degreeU, order));
}

//Points fot the “U” curve….
for (i = 0;i < iMax; i++) {
output.push(nurbs(paramsE[i], resultant_curve, degreeV, order));
}
}

return output;
}
[/as]

There will be a third part of these series of post (Nurbs in Flash) based on how can the surfaces be rendered using the advantage of the parametrization for the vertex normal calculation and other features that speed up the rendering in real time (only for parametric surfaces).

Delaunay for fun

15, Apr 2010/Categories 3D, AS3, Sound Spectrum/6 Comments

delaunay

En este experimento he querido probar lo que podía hacer utilizando el algoritmo de triangulación Delaunay y las cosas han salido de un modo diferente a como yo esperaba aunque el resultado ha sido curioso.

Buscando por la red información sobre el tema, me he encontrado con un post en el blog de Nicolas Barradeau que ya había portado a as3 el código de la triangulación. La idea era dibujar una forma con el ratón, guardar las coordenadas en un Vector y triangularlo, con el modelo de datos resultante y creando un mapeado UV para una imagen deberíamos tener un generador de formas texturizadas en tiempo real, primero probé añadiendo algo de ruido a cada vertice para conseguir darle un movimiento orgánico aunque el resultado era muy brusco por lo que en cada ‘enterframe’ filtré todos los vertices con una funcion que agrega un patrón de movimiento usando seno y coseno jugando con un valor que se incrementaba con el paso del tiempo para simular la phase y dar así un efecto de bandera ondeando al viento. Al tener todos estos valores metidos dentro de un Vector y estar dibujandolos con la instrucción drawTriangles del API de dibujo de flash 10 no debía ser muy dificil añadir el valor del movimiento sinusoidal en una dimensión más (la Z) y así, mediante projectVectors y Matrix3D, conseguí renderizar el modelo de datos tridimensionales sin mayor problema.

Para darle un valor añadido decidí ponerle sonido y utilizar computeSpectrum para recoger los valores de la música en tiempo real y así poder deformar los triangulos al ritmo de la canción. El movimiento no me terminaba de convencer ya que igualar los valores FFT tal cual, hace que el movimiento no sea del todo agradable así que debía añadir un suavizado al mover las propiedades de los vertices, posición de la matriz3D etc… Usando la antigua fórmula de easing de toda la vida el resultado fué bastante bueno.

Al final decidí colocar letras en la textura y para ello creé un simple sistema de pintado de un TextField a un BitmapData y usarlo como textura en los triangulos. En el ejemplo se puede escribir y borrar la palabra que hay en el objeto 3d, rotar el objeto según la posición del ratón (se recomienda mantener el ratón en el centro de la animación), añadir filtros Glow [UP] o DropShadow [DOWN] o filtrar el bitmap de la textura (CPU intensivo) para mostrar tan solo los bordes de la imágen [LEFT] .

Espero que os guste.

NURBS in Flash (part 1)

07, Apr 2010/Categories AS3, General/4 Comments

NURBS Curve

This post is a little long so I will post it in two parts, the fist one is about NURBS in 2D (Curves) and the next one will be about NURBS in 3D (surfaces)…

Ever since I have been working in Flash I wanted to write one Class that would allow me to work with NURBS curves and surfaces the way I used to work them in 3dsMax, but getting to understand how they work is something somehow difficult because there is some math that needs to be applied in order to make it right.

NURBS is the acronym for Non Uniform Ration B-Splines, Nurbs curves and surfaces represent a precise mathematical representation of a free form curve or surface. All the theory needed to understand them is well explained here, but i´ll make a short introduction of the Nurbs concepts for a better undestanding of the example below.

B-Splines:

B-Splines are a generalization of the Bezier curves, these kind of curves use a set of interpolation functions called Basis Funcions , hence the “B” on “B-Splines”, the kind of interpolation of these function has the advantage of  allowing local control on the curve with the control points unlike the bezier curves. This means that meanwhile the all the bezier curve is affected by all the control points, the control points of the B-Spline curve only affect one portion of the whole curve. The construction of the basis function can be read here.

Rational B-Splines:

Rational B-Splines are the generalization of the B-Splines, the rational factor enables to change the control point influence in the curve using weight factors on each control point, changing the weight of one control point will make the curve get closer to or farther from the control point edited. Using rational b-splines conic sections can be represented exactly.

Non Uniform Rational B-Spline:

The non uniform part of the acronym is not another generalization,  it is the way rational b-splines start and end on the desired end points. The basis functions needed to interpolate the spline require a set of knots that define the way each basis function interacts with the global interpolation, the creation of the knots can be done in a uniform distribution, using the same distance among them, or using a non uniform distribution that force the interpolation start in the first control point and finish in the last control point. You can see the way the knots affect the resultant curve here.

The example from below has two curves with seven control points, the red one is a Nurbs curve and the blue one is a Bezier curve, the light blue lines represent the convex hull of both curves. You can move the control points to edit both curves and see the differences between them, you can also change the weights of the control points and the degree of the Nurbs curve to see how the degree change the general interpolation.

One of the most interesting things with Nurbs curves and Bezier curves is that for a given set of control points “n” (all with the same weight), the Nurbs curve of degree n-1 is equal as the Bezier curve created with the same control points. The lower the degree of the Nurbs curve the closer the curve will be to the convex hull. Finally if a degree of 1 is defined the curve will be exactly as the convex hull.

The AS3 Class:

The actionScript class calculates nurbs points on a curve and nurbs points on a surface. It has three static functions: Nurbs.nurbs(), Nurbs.nurbsCurve() and Nurbs.surface(), the parameters needed for each function depends on the theory for the Nurbs curves and surfaces. The whole class is not here, only the first function that allows to find the points on a Nurbs curve given a defined parameter.

The function Nurbs.nurbs() requieres four parameters:

p… parameter (value between 0 and  1).

controlPoints… vector of vectors 3D that define all the control points in the curve.

degree… degree of the curve interpolation.

order… the order alters the way the knots vector are created (uniform or non-uniform), usually it should not be used.

[as]
package math {
import flash.geom.Vector3D;

/**
* @author miaumiau.cat
*/
public class Nurbs {

//Function that calculates a point on a Nurbs curve…
public static function nurbs(p : Number, controlPoints : Vector.<Vector3D>, degreeParam : uint = 3, orderParam : int = -1) : Vector3D {

var cp : uint = controlPoints.length;
var degree : uint = degreeParam < 1 ? 1 : degreeParam > cp ? cp : degreeParam;
var order : uint = orderParam == -1 ? degree + 1 : orderParam < 0 ? degree + 1 : orderParam > degree + 1 ? degree + 1 : orderParam;
var totalKnots : uint = cp + degree + 1;

var i : uint;
var j : uint;
var baseVector : Vector.<Number> = new Vector.<Number>();
var knotsVector : Vector.<Number> = new Vector.<Number>();
var recurtion : uint;
var output : Vector3D = new Vector3D();
var f : Number;
var g : Number;
var rangoFinal : Number;
var t : Number;

i = 0;
while(i < order) {
knotsVector[i] = 0;
i += 1;
}

i = order;
while(i < cp) {
knotsVector.push(i – order + 1);
i += 1;
}

i = cp;
while(i < totalKnots) {
knotsVector.push(cp – order + 1);
i += 1;
}
var data : Number = 1;
rangoFinal = knotsVector[cp + 1];
t = p * (rangoFinal);

//Generate the Basis Functions…
i = 0;
recurtion = totalKnots – 1;
while(i < recurtion) {
baseVector[i] = (knotsVector[i] <= t && t <= knotsVector[i + 1] && knotsVector[i] < knotsVector[i + 1]) ? 1 : 0;
i += 1;
}
recurtion -= 1;
j = 1;
while(j <= degree) {
i = 0;
while(i < recurtion) {
f = (knotsVector[i + j] – knotsVector[i]);
g = (knotsVector[i + j + 1] – knotsVector[i + 1]);
f = f != 0 ? (t – knotsVector[i]) / f : 0;
g = g != 0 ? (knotsVector[i + j + 1] – t) / g : 0;
baseVector[i] = f * baseVector[i] + g * baseVector[i + 1];
i += 1;
}
if(p == data) {
var salida : String = “”;
for(var u : uint = 0;u < recurtion; u++) {
salida += baseVector[u] + “,”;
}
}
j += 1;
recurtion -= 1;
}

//Calculate the Rational points…
i = 0;
var divider : Number = 0;
while(i < cp) {
output.x += baseVector[i] * controlPoints[i].x * controlPoints[i].w;
output.y += baseVector[i] * controlPoints[i].y * controlPoints[i].w;
output.z += baseVector[i] * controlPoints[i].z * controlPoints[i].w;
divider += baseVector[i] * controlPoints[i].w;
i += 1;
}

output.x /= divider;
output.y /= divider;
output.z /= divider;
return output;
}
}
}

[/as]

Probando el raytracing en AS3

Probando el raytracing en AS3

24, Mar 2010/Categories 3D, AS3/3 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/3 Comments

Beziers

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();
combinatoriaData[0] = [0];
combinatoriaData[1] = [1];

//A partír de 2 se tienen la cantidad mínima de puntos para interpolar
combinatoriaData[2] = new Array(1, 1);
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…
if(combinatoriaData[length] == undefined) {
combinatoriaData[length] = setCoeficients(n);
}

//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…
if(combinatoriaData[length1] == undefined) {
combinatoriaData[length1] = setCoeficients(n);
}

//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:
//n : grado,
//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 = [];
combinatoriaData = [];

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();

//Evalúo la interpolación para cada coordenada del punto, x, y, z…
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/1 Comment

Saddle

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.

Edition-mode

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

Mouse-editionMode

Mouse

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!…

Editor

Surface Renderer

23, Feb 2010/Categories 3D, AS3, General/No Comments

queenChess

In these days some of our projects require the use of 3D, and dealing with 3D objects in Flash can be a very painfull situation if you need to show many poligons and apply dinamic material to those poligons. In order to explore some of the “new” features of Flash, we decided to skip the mainstream 3d libraries (Away and Papervision) and  try to create a simple renderer for our projects and our needs.

The renderer is intended to “bring to life” any kind of parametric surface, these kind of surface would give us a domain space were the surface tessellation is defined. Working with the parametric space and the domain space gives us the oportunity to calculate texture maps on the domain space that could be applied to the parametric space. The domain space and tessellation also gives us the chance to simplify the calculations (this can be done because every step of the domain space is formed by two triangles for tessellation purposes), so every texel in the texture is a step in the domain space which can be interpreted as a interpolation of the information of the two triangles that are part of the step.

Working the texture for every texel (product of the mix of two triangles allows us to calculate the lighting for every surface taking into account the distance of every triangle from the light, it also allows us to use multiple lights on the scene and recreate phong materials with specular values defined through the material definition.

In some future posts we will try to clean up the code for this simple renderer if you would like to play with it.

dotted meow from the crypt

30, Sep 2009/Categories AS3, Computer Vision/1 Comment

dotted meow

WEBCAM REQUIRED.

I’ve been playing around with the webcam on AS3 and finally i got into something i liked.

Basically what I’m doing here is to generate a grid of shapes keeping references between objects using a linked list. I am working with a small video size to optimize performance, so I keep two positions in each properties at Particle class: origin and staticPosition.

origin is a Point keeping the coordinates of the pixel on the Video object which corresponds to the particle.

staticPosition is a Point keeping the coordinate that corresponds at stage.

Here there is a sample of the generate grid method, it has comments and the complete source is ready to download at the end of this post.

[as]
private function setupGrid() : void{

// iniatialize the linked list with initLink Particle
var p : Particle = initLink;
// set the x / y coordinates to zero
var _x : uint = 0;
var _y : uint = 0;
// this bucle creates the particles
for (var i : int = 0; i < quantity; i++) {
// if the x coordinate exceeds the defined width limit
if(i % nw == 0 && i!= 0){
// set the ‘x’ coordinate to zero
_x = 0;
// ad the height of the particle to the ‘y’ coordinate
_y += particleHeight;
}

// storing the next particle at current
p.next = new Particle();
// define the coordinate that corresponds this iteration at the source video
var origin : Point = new Point(_x / particleWidth, _y / particleHeight);
// send it to the origin propertie at the particle
p.origin = origin;
// define the current position at stage
var point : Point = new Point(_x, _y);
// place it to two properties at the particle
// at ‘staticPosition’ , this value will not change
p.staticPosition = new Point(point.x, point.y);
// and at ‘position’, this value will change to animate flight
p.position = point;
// place the particle at stage coords
p.x = point.x;
p.y = point.y;
// add the displayObject to the container
particles.addChild(p);
// refresh the ‘p’ variable to store the next particle at next iteration of this bucle
p = p.next;
// add a particle width to the ‘_x’ var for the next iteration
_x += particleWidth;

}

}
[/as]

We can color each particle based on each pixel rgb value that points to the origin coords, doing so we can win a nice semitone effect for the video capture.

On the other side, the class MotionTracker has a very simple motion detection implementation, it draws each frame of the Video Object  over the last frame using BlendMode.DIFFERENCE and then thresholding filtering the pixels with a color higher than 0×111111

Here the code of the detection

[as]
private function tictac(event:TimerEvent) : void{

// locking bitmapdatas for better performance
current.lock();
output.lock();
input.lock();
// a current copy from the source
current.draw(source);
// making a temporary copy of currentFrame to work with both input and current
var temp : BitmapData = current.clone();
// here we are drawing the previous frame on top of the current and the difference blendMode will make the rest
temp.draw(input, null, null, BlendMode.DIFFERENCE);
// filter the pixels tha are greater than darkgrey #111111 and thresholding them into blue #0000FF overwriting the previous bmp
temp.threshold(temp, temp.rect, temp.rect.topLeft, “>”, 0xFF111111, 0xFF0000FF, 0x00FFFFFF, true);
// resets output’s color information
output.fillRect(output.rect, 0xFF000000);
// stores the current frame wich will be the previous on the next tictac
input = current.clone();
// thresholding the temp bitmapdata into the output bitmapdata with ‘equal’ colors
output.threshold(temp, output.rect, output.rect.topLeft, “==”, 0xFF0000FF, 0xFF0000FF, 0x00FFFFFF, false);
// unlocking bitmapdatas
current.unlock();
output.unlock();
input.unlock();
// cleaning memory
temp.dispose();

}
[/as]

I think it would be interesting if the particles would move randomly at the same point where the movement was detected by the motionTracker, and here we go.

The Particle class has two methods to move scale and position, it implements a wonderful bouncing easing equation seen at Erik Natzke’s blog and one method to modify the internal position Point to a random value.

[as]
public function moveScale(scale : Number) : void{

scaleX -= ax = (ax + (scaleX – (scale * 3)) * div) * .9;
scaleY -= ay = (ay + (scaleY – (scale * 3)) * div) * .9;

}

public function movePosition(p : Point) : void{

x -= bx = (bx + (x – (p.x)) * div) * .5;
y -= by = (by + (y – (p.y)) * div) * .5;

}

public function flight() : void{

position.x = staticPosition.x – (Math.random() * 200 * sign());
position.y = staticPosition.y – (Math.random() * 200 * sign());

}

public function unFlight() : void{

position.x = staticPosition.x;
position.y = staticPosition.y;

}
[/as]
These methods are called from the Main class at the enterframe handler
[as]
while(p.next != null){

var color : uint = bmd.getPixel(p.origin.x, p.origin.y);
var scale : Number = color / 0xFFFFFF;

if(motion.output.getPixel(p.origin.x, p.origin.y) != 0){

p.flight();

} else{
p.unFlight();
}

p.moveScale(scale);
p.movePosition(p.position);
p.color = color;
// p.color = colors[Math.floor( scale * colors.length )];
p = p.next;

}
[/as]

And here the complete source.

miaumiau interactive studio © 2011. All rights reserved