July 10, 2005

July 10, 2005

If n = 2, the code, as shown yesterday, with GLfloat v[3][2] = {{0,0.866},{-1,-1},{1,-1}}; produces a figure showing two of the three edges of the nested triangle. Angel, of course, has said we should see none. Let’s step into it and see what we see.

The first recursive calls are

divide_triangle( a, v[0], v[2], 1, 3);

divide_triangle(v[0], b, v[1], 1, 1);

divide_triangle(v[2], v[1], c, 1, 2);

divide_triangle(v[0], v[1], v[2], 1, 7);

Again,

a={0,0.866}, b={-1,-1}, c={1,-1},
v[0]={-0.5,-0.067},v[1]={0.0,-1.0},v[2]={0.5,-0.067}

So divide_triangle(a,v[0],v[2],1,3) will subdivide the top sub-triangle, renaming the vertices a, b and c and first computing the midpoints of its edges as
a={0,0.866}, b={-0.5,-0.067},c={0.5,-0.067},
v[0]={-0.25,-0.067},v[1]={0.0,-1.0},v[2]={0.5,-0.067}
Now switch(3) will set

case(3):

flag[0] = 3;

flag[1] = 5;

flag[2] = 4;

and, as always, flag[3] = 7. Each of the next recursive calls has m = 0 and so leads to the “else” base case call to

triangle( a, v[0], v[2], 3);

triangle(v[0], b, v[1], 5);

triangle(v[2], v[1], c, 4);

triangle(v[0], v[1], v[2], 7);

So the first triangle above will, what? This is very confusing. Ok, to get a handle on this I inserted color changes in between the triangle calls:

glColor3f(1.0,0.0,0.0);

divide_triangle(a, v[0], v[2], m-1, flag[0] );

glColor3f(0.0,1.0,0.0);

divide_triangle(v[0], b, v[1], m-1, flag[1] );

glColor3f(0.0,0.0,1.0);

divide_triangle(v[2], v[1], c, m-1, flag[2] );

glColor3f(1.0,0.0,1.0);

divide_triangle(v[0], v[1], v[2], m-1, flag[3] );

This helps. So the top triangle is almost what it should be after the top triangle is drawn from the top vertex counterclockwise with red edges on/off/on. The next little triangle (green) is drawn with type=5 -> on/off/off and the final triangle (blue) is is drawn with type=4 -> off/off/on. We see the bottoms of the 2^nd and 3^rd triangles as red and blue, but that must come from some later event. Of course the middle triangle is drawn in invisible ink.

Let’s move to the next group of 4. These are invoked by the recursive function call, divide_triangle(v[0],b,v[1],1,1) which set flags

case(1):

flag[0] = 5;

flag[1] = 1;

flag[2] = 6;

then renames the vertices a, b and c and computes the midpoints of its edges according to

a={-0.5,-0.067}, b={-1.0,-1.0}, c={0.0,-1.0},
v[0]={-0.75,-0.5335},v[1]={0.0,-1.0},v[2]={-0.25,-0.5335}

and then the base case calls

triangle( a, v[0], v[2], 5);

triangle(v[0], b, v[1], 1);

triangle(v[2], v[1], c, 6);

triangle(v[0], v[1], v[2], 7);

I’m starting to get the rhythm of this, but the truth of why some interior edges appear may or may not be uncovered.

Again, the first three triangle calls are colored red, green and blue. So the first one is type 5 drawing only the red left edge. The second (green) triangle is type 1, drawing, as expected, the left and bottom green edges. Then the third is a blue type 6 which draws only the bottom, as it should.

It may be worth observing that the outside part of the triangle is all correctly colored, as we expect. The mystery are the interior parts: which according to Angel, shouldn’t be there.

Ok, the third triangle is called with k=2, which leads to

case(2):

flag[0] = 4;

flag[1] = 6;

flag[2] = 2;

which draws a red right side for the top triangle, a green bottom side for the bottom left triangle, and bottom+right blue edges of the bottom left triangle. This is right, alright. So where do the middle ones come from?

Oh, gentle reader, I thank you for your forbearance and for not spoiling my fun by pointing out that cases 6 and 7 are just plain wrong, wrong, wrong…and that explains perfectly the messing up. The first column below shows how I had it wrong, the second shows how it should read and the third shows the result of fixing the code. Still, the pathology of miscreant triangle lattices was kind of interesting!

case(6):

flag[0] = 7;

flag[1] = 7;

flag[2] = 7;

break;

case(7):

flag[0] = 3;

flag[1] = 5;

flag[2] = 4;

case(6):

flag[0] = 7;

flag[1] = 6;

flag[2] = 6;

break;

case(7):

flag[0] = 7;

flag[1] = 7;

flag[2] = 7;

I guess that means I can move on.

Rotation

This might seem not immediately related to tessellation and interpolation, but hang on, I’m Angel can bring it together for us.

The rotation transformation

is written here, first matrix transformation form, then matrix expanded form and finally as a pair of equations any precalculus student would be expected to understand. Well, a good precalc student. A geometric transformation is best understood using geometry. In 2D, this is not too hard. Alpha is the counterclockwise angle. The rectangular point (x,y) with polar angel theta and modulus r has polar coordinates (r,theta) where

Rotating about the origin through an angle alpha leads to new coordinates, which by the addition formulas comes out as promised

But it’s more satisfying to me to see the pieces of lengths in the transformation geometrically:

This diagram is a great help in understanding the terms in the rotation transformation. Right triangle OAB is rotated counterclockwise an angle α about O to triangle OA’B’. By definition of sine and cosine, the coordinates of A’ are . Now A’C’ is parallel to OA and B’C’ is parallel to AB, so angle A’B’C’ is also α. Thus , and the result is evident. Plus, it’s a pretty slick MS Word drawing, no?

So here’re the new twisted triangles I made using Angel twisted revision on the triangle function (see below):

#include <cmath>

float twist = .1;

void triangle(GLfloat *a, GLfloat *b, GLfloat *c, int type) {

GLfloat v[2];

double d;

glBegin(GL_POLYGON);

switch(type)

{

case(2):

case(4):

case(6):

case(7):

glEdgeFlag(GL_FALSE);

break;

default:

glEdgeFlag(GL_TRUE);

}

d = sqrt(a[0]*a[0] + a[1]*a[1]);

v[0] = cos(twist*d)*a[0] - sin(twist*d)*a[1];

v[1] = sin(twist*d)*a[0] + cos(twist*d)*a[1];

glVertex2fv(v);

switch(type)

{

case(3):

case(4):

case(5):

case(7):

glEdgeFlag(GL_FALSE);

break;

default:

glEdgeFlag(GL_TRUE);

}

d = sqrt(b[0]*b[0] + b[1]*b[1]);

v[0] = cos(twist*d)*b[0] - sin(twist*d)*b[1];

v[1] = sin(twist*d)*b[0] + cos(twist*d)*b[1];

glVertex2fv(v);

switch(type)

{

case(1):

case(5):

case(6):

case(7):

glEdgeFlag(GL_FALSE);

break;

default:

glEdgeFlag(GL_TRUE);

}

d = sqrt(c[0]*c[0] + c[1]*c[1]);

v[0] = cos(twist*d)*c[0] - sin(twist*d)*c[1];

v[1] = sin(twist*d)*c[0] + cos(twist*d)*c[1];

glVertex2fv(v);

glEnd();

}