Back to July Calendar Previous Entry Next Entry→

July 9, 2005
 

So, where was I?  Oh, yes: turning on/off edges of the nested triangles. Angel writes, “If you complete the program and run it, you will indeed see only the outer edge of the original triangle, and the tessellation will be invisible.  So you might be wondering what is the point of our tessellation.”  Yes, indeed!
      My first attempt produced the charming orphan shown at right (not quite right, is it?)  What do you suppose went awry here? Well, I suspect it’s the order that I gave my vertices on the line initializes triangle vertices GLfloat v[3][2]={{-1,-1},{1,-1},{0,0.866}} just preceding the display function definition.  If you reverse these so they go around clockwise rather than counterclockwise (just swap

GLfloat v[3][2]={{-1,-1},{0,0.866},{1,-1}}
then I get a solid red, big triangle.

 

/* triangleNest2 - From Angel's OpenGL Primer */

 

#include <GL/glut.h>   // This includes gl.h and glu.h

 

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

      glBegin(GL_POLYGON);

        switch(type) {

          case(2):

          case(4):

          case(6):

          case(7):

              glEdgeFlag(GL_FALSE);

              break;

          default:

              glEdgeFlag(GL_TRUE);

        }

        glVertex2fv(a);

        switch(type) {

          case(3):

          case(4):

          case(5):

          case(7):

              glEdgeFlag(GL_FALSE);

              break;

          default:

              glEdgeFlag(GL_TRUE);

        }

        glVertex2fv(b);

        switch(type) {

          case(1):

          case(5):

          case(6):

          case(7):

              glEdgeFlag(GL_FALSE);

              break;

          default:

              glEdgeFlag(GL_TRUE);

        }

        glVertex2fv(c);

    glEnd();

}

 

void divide_triangle(GLfloat *a, GLfloat *b, GLfloat *c, int m, int k) {

      //Triangle subdivision using vertices

      GLfloat v[3][2];  //starting triangle for all furtherly divided:

      //clear window

      //glClear(GL_COLOR_BUFFER_BIT);

      int j, flag[4];

      if(m>0) {

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

                  v[0][j] = (a[j] + b[j])/2;

                  v[1][j] = (b[j] + c[j])/2;

                  v[2][j] = (a[j] + c[j])/2;

            }

            switch(k) {

                  case(0):

                        flag[0] = 3;

                        flag[1] = 1;

                        flag[2] = 2;

                        break;

                  case(1):

                        flag[0] = 5;

                        flag[1] = 1;

                        flag[2] = 6;

                        break;

                  case(2):

                        flag[0] = 4;

                        flag[1] = 6;

                        flag[2] = 2;

                        break;

                  case(3):

                        flag[0] = 3;

                        flag[1] = 5;

                        flag[2] = 4;

                        break;

                  case(4):

                        flag[0] = 4;

                        flag[1] = 7;

                        flag[2] = 4;

                        break;

                  case(5):

                        flag[0] = 5;

                        flag[1] = 5;

                        flag[2] = 7;

                        break;

                  case(6):

                        flag[0] = 7;

                        flag[1] = 7;

                        flag[2] = 7;

                        break;

                  case(7):

                        flag[0] = 3;

                        flag[1] = 5;

                        flag[2] = 4;

                        break;

            }

            flag[3] = 7;

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

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

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

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

      }

      else triangle(a,b,c,k);

}

 

//We generate 4n triangles with this callback

GLfloat v[3][2] = {{-1,-1},{1,-1},{0,0.866}};

void display(void) {

      glClear(GL_COLOR_BUFFER_BIT);

      glPolygonMode(GL_FRONT, GL_LINE);

      int n = 4;

      glColor3f(1.0, 0.0, 0.0);

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

      glFlush();

}

 

void init() {

      //set clear color to white

      glClearColor(1.0,1.0,1.0,1.0);

      //set standard orthogonal (look straight at) clipping view

      glMatrixMode(GL_PROJECTION);

      glLoadIdentity();

      gluOrtho2D(-1.1,1.1,-1.1,1.0);

}

 

int main(int argc, char** argv) {

      glutInit(&argc, argv);

      glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);

      glutInitWindowSize(500,500);

      glutInitWindowPosition(0,0);

      glutCreateWindow("whimple");

      glutDisplayFunc(display);

      init();

      glutMainLoop();

}

 

I need to walk through this, step by step to get a better handle on the logic of the 8 triangle types and how they lead to my orphan and might lead to more of what Angel had in mind.  First lets see the results of doing n=1,2,3 and 4:

 

The function display() calls the recursive function divide_triangle(), which takes the three vertices of the original triangle, each of which is itself a 2D array: (v[0], v[1] and v[2]), renames these a, b and c and finds the midpoints of the edges connecting these, which it rename v[i][j] –again.  Bit confusing reusing this name here, isn’t it? 

 

Now the original call to divide_triangle() has the last parameter k=0, so when we go to the switch structure,  we set
                       flag[0] = 3; flag[1] = 1; and flag[2] = 2;
What does this mean?  It must mean that, for the first subdivision, the “0” triangle will be missing its upper right edge; the “1” triangle will be missing its upper left edge and the “2” triangle will be missing its bottom edge.  In all cases the fourth (“3”) triangle will be all greyed edges.  So it starts on the lower right and progresses around counterclockwise to the top, in that case. 

 

Next come the recursive calls:

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

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

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

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


Let’s suppose m=1.  Since

                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}

Then each of these calls leads to the “base case”  divide_triangle() goes to the “else” condition, so we call first triangle(a, v[0], v[2], 3) where the last parameter is now the “type” value flag[0]=3.   So triangle() renames the three vertices a, b and c again and sets the initial glEdgeFlag to GL_TRUE, plots a, sets the flag to false, plots b and then sets the flag to true again and plots c.  I think this is consistent with plotting the edges of the top triangle!  Part of the confusion I have is that this doesn’t correspond to triangle 3 in Angle’s figure 2.12.

 

Next, triangle(v[0],b,v[1],1) is called, which is the lower left triangle, and appropriately (counting counterclockwise from the top) the first to edges are draw and the 3rd is not. 

 

Next, triangle(v[2],v[1],c,2) is called, which draws, correctly, and starting again from the top and going counterclockwise, edges 2 and 3, but not 1. 

 

Of course, flag[3], the fourth and central triangle is always completely grayed out.

 

Well, that’s a good start, and it matches the correct drawing we see for the case n=1.  But now we need consider the case when n = 2, with sixteen triangles to draw.  Yikes!  Well, we’ll try to thread it through until we grasp or the idea, or we just can’t stand it any more.