### NURBS in Flash (part 2)

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

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.

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/No Comments

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/No Comments

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]