Step 6:  Triangle Meshes and Graphics Files

This step will introduce concepts that will be handy in Project 1, specifically the concepts of a Triangle Mesh and loading objects from a file. It also shows how to base animations on time rather than the unreliable windows timer messages. The step builds on step 5, so you will start with the step 5 solution.  I will assume you have the CSGRotationTranslation node available to use.  I will also assume you have some way to set material properties such as a CSGMaterials node and some way to enable textures, such as a CSGTexture node. 

You should be working on your project while doing this step.  Everything in this step can be directly incorporated into your project.

You have two tasks when you are done.

Triangle Mesh

Building an elaborate scene entirely with polygon objects is tedious and inefficient.  If you take this approach, you end up with a lot of objects that have many vertices and lots of polygons and end up making lots and lots of scene graph nodes.  So, let's create a very common data structure in graphics systems:  the triangle mesh.

A triangle mesh consists of a set of vertices and a set of triangles that reference those vertices.  Using triangles instead of polygons will simplify our data structures considerably and allow us to some some OpenGL features that will render our scenes very quickly.  And, converting a convex polygon into triangles turns out to be very easy to do.  Look at this example:

All it took to turn this polygon into triangles was to treat it as a triangle fan.  Each triangle will consist of the first vertex of the polygon (a), and two sequential vertices.  For example, [a b c] then [a c d] then [a d e] etc.  Some systems, like DirectX, don't even accept polygons, only triangles and triangle fans.  In those systems you input a polygon as a triangle fan.

So, what do we need to describe an object?  We'll need vertices, normals, and (potentially) texture coordinates.  Create a new class call CSGMesh that is derived from CSGNode.  Create an initial, empty Render procedure for CSGMesh.  Create a simple scene graph that contains your CSGMesh node and assign it material properties just as you would for a polygon.  I will assume you have code somewhere in your CreateSceneGraph() function that looks like this:

    CSGPtr<CSGMesh> mesh = new CSGMesh();
    parent->AddChild(mesh);

The parent may be any node you are using as a parent, such as a CSGRotationTranslation node.  If you have something that displays in the middle of your scene, remove it; we're going to display our mesh there.

Triangle Mesh Data

We need to express two things in our CSGMesh class:  vertex data (consisting of vertices, normals, and texture coordinates) and triangles.  There are many ways to do this.  We're going to do it the most simple way possible.  Add this private member data to CSGMesh:

    std::vector<CGrPoint>   m_vertices;
    std::vector<CGrPoint>   m_normals;
    std::vector<CGrPoint>   m_tvertices;

Look familiar?  This is just like what we did for a polygon, except that this time the data is for an entire object, not just a single polygon.  Instead of using these vertices in order, we'll index into these arrays to use the.  For example, a triangle may use vertex 7, 3, and 2.  Add these member functions to create this data:

    void AddVertex(const CGrPoint &v) {m_vertices.push_back(v);}
    void AddNormal(const CGrPoint &n) {m_normals.push_back(n);}
    void AddTexCoord(const CGrPoint &t) {m_tvertices.push_back(t);}

Now we need to define our triangles.  Each triangle vertex will have to indicate an index into each of our three arrays.  Add this private member data in CSGMesh:

    struct TV
    {
        int     v;      // Vertex
        int     n;      // Normal
        int     t;      // Texture coordinate
    };

    typedef std::vector<TV> Triangles;
    typedef Triangles::iterator PTV;
    Triangles       m_triangles;

    std::vector<TV> m_triangles;

    for(vector<TV>::iterator v=m_triangles.begin(); v!=m_triangles.end(); v++)

    for(PTV v=m_triangles.begin();  v!=m_triangles.end();  v++)

Now, add this public function to CSGMesh:

void CSGMesh::AddTriangleVertex(int v, int n, int t)
{
    TV tv;
    tv.v = v;
    tv.n = n;
    tv.t = t;
    m_triangles.push_back(tv);
}

I have created the data for texture coordinates, but I'm not going to do anything else related to textures in this step assignment.  That will be your problem.  See the tasks as the end of the step.

Creating an Object

We now have everything we need to define an object.  Let's define a cube. 

    double v[8][3] = {{0, 0, 2}, {2, 0, 2}, {2, 2, 2}, {0, 2, 2}, 
        {0, 0, 0}, {2, 0, 0}, {2, 2, 0}, {0, 2, 0}};
    double n[6][3] = {{0, 0, 1}, {1, 0, 0}, {0, 0, -1}, 
	{-1, 0, 0}, {0, 1, 0}, {0, -1, 0}};

    for(int i=0;  i<8;  i++)
        mesh->AddVertex(v[i]);

    for(int i=0;  i<6;  i++)
        mesh->AddNormal(n[i]);

    mesh->AddTriangleVertex(0, 0, 0);
    mesh->AddTriangleVertex(1, 0, 0);
    mesh->AddTriangleVertex(2, 0, 0);

This code defined 8 vertices and added them to the mesh. Those are the 8 corners of the cube. It also defines 6 normals and adds them to the mesh. Those are the six face normals. Finally, it defines a single triangle using the first three vertices and the first normal (0, 0, 1).  This is a front-face triangle.  We're going to get this to display first, then we're going to add the rest, but I'm too lazy to do this with 36 lines of this tedious code.  There's got to be a better way.

Rendering This

Now it's time to render.  We'll be filling in the CSGMesh::Render() function.  This is all it takes:

    glBegin(GL_TRIANGLES);
    for(PTV v=m_triangles.begin();  v!=m_triangles.end();  v++)
    {
        glNormal3dv(m_normals[v->n]);
        glVertex3dv(m_vertices[v->v]);
    }
    glEnd();

Compile this and run. You should see the one triangle from the cube.  Each three vertices you add makes a triangle.  You need to always load three vertices at a time.

Here's SGMesh.h and SGMesh.cpp so far.

Lazy Time

Going back to where we defined that one triangle, it would take six lines per face of the cube, or 36 lines to specify the entire cube.  I am way too lazy to do that much work.  So, I'm going to create a handy function to make it much easier.  Add this public function to CSGMesh:

void CSGMesh::AddFlatQuad(int a, int b, int c, int d, int n)
{
    // First triangle
    AddTriangleVertex(a, n, 0);
    AddTriangleVertex(b, n, 0);
    AddTriangleVertex(c, n, 0);

    // Second triangle
    AddTriangleVertex(a, n, 0);
    AddTriangleVertex(c, n, 0);
    AddTriangleVertex(d, n, 0);
}

This function accepts four vertices that represent a quadrilateral and a single normal to use as all of the vertex normals.  It then creates the quadrilateral as two triangles.  Here's how you'll use this in your program.  Remove the three original AddTriangleVertex calls that created the single triangle, but not the code that created the vertices and normals.  Replace those three lines with this:

    mesh->AddFlatQuad(0, 1, 2, 3, 0);
    mesh->AddFlatQuad(1, 5, 6, 2, 1);
    mesh->AddFlatQuad(5, 4, 7, 6, 2);
    mesh->AddFlatQuad(4, 0, 3, 7, 3);
    mesh->AddFlatQuad(3, 2, 6, 7, 4);
    mesh->AddFlatQuad(0, 4, 5, 1, 5);

There, isn't that easier?  It's just like when we specified vertices with letters; but now it's numbers.  It would be very easy to make a similar function that computes the normal itself and just adds it to the list of normals. 

Here's SGMesh.h and SGMesh.cpp so far.

An "Interesting" Surface

Mesh objects are very powerful.  Since they have a lot of geometry in one place, we can do a lot with it.  We're going to create a surface.  Use a rotation/translation node in your scene graph to move the cube up out of the way and add a new CSGMesh node. Here's the code I've used.  I have a new CSGMesh object called surface:

    CSGPtr<CSGMesh> mesh = new CSGMesh();
    CSGPtr<CSGRotationTranslation> meshRT = new CSGRotationTranslation();
    meshRT->SetTranslate(0, 10, 0);
    root->AddChild(meshRT);
    meshRT->AddChild(mesh);

    CSGPtr<CSGMesh> surface = new CSGMesh();
    root->AddChild(surface);

Now create this function:

void CChildView::CreateSurface(CSGPtr<CSGMesh> &surface)
{
}

Right after you create surface, add this call:

    CreateSurface(surface);

This is where we'll put the code to create our surface.

First, we'll add a helper function to CSGMesh:

void CSGMesh::AddQuad(int a, int b, int c, int d)
{
    // First triangle
    AddTriangleVertex(a, a, 0);
    AddTriangleVertex(b, b, 0);
    AddTriangleVertex(c, c, 0);

    // Second triangle
    AddTriangleVertex(a, a, 0);
    AddTriangleVertex(c, c, 0);
    AddTriangleVertex(d, d, 0);
}

This function is similar to our earlier AddFlatQuad except we don't pass a normal index to it.  We, instead, assume there will be a normal for every vertex; that the normal and vertex indices will correspond.

Given this, we can create our surface:

    double wid = 20;        // 20 units wide
    double dep = 20;        // 20 units deep
    int nW = 15;            // Number of quads across
    int nD = 15;            // Number of quads deep
    const double PI = 3.1415926535897932384626433832795;

    // Create the vertices and -temporary- normals
    // Note that the surface is nW+1 by nD+1 vertices
    for(int j=0;  j<=nD;  j++)
    {
        for(int i=0;  i<=nW;  i++)
        {
            double x = double(i)/double(nW) * wid - wid/2;
            double z = double(j)/double(nD) * dep - dep/2;
            double y = sin( double(i)/double(nW) * 4 * PI ) + 
                sin( double(j)/double(nD) * 3 * PI);

            surface->AddVertex(CGrPoint(x, y, z));
            surface->AddNormal(CGrPoint(0, 1, 0));
        }
    }

    // Create the quadrilaterals
    for(int j=0;  j<nD;  j++)
    {
        for(int i=0;  i<nW;  i++)
        {
            int a = j * (nW + 1) + i;
            int b = a + nW + 1;
            int c = b + 1;
            int d = a + 1;

            surface->AddQuad(a, b, c, d);
        }
    }

The first part is pretty straight-forward.  It just creates a grid of vertices.  The y value serves to move the points up and down so we get a sinusoidal undulation.  Right now I just put in a normal that points straight up, so this will look very strange.  The second part creates the quadrilaterals.  Because we are dividing the world into nW squares left to right, there are actually nW+1 vertices.  This diagram should help you understand the math that is going on here:

The first row has vertex indices 0 to nW.  The second row has nW+1 to nW+1 + nW or 2nW+1.  The next row has 2nW+2 to 3nW+3.  So, the first vertex in row j will be j * (nW + 1).

Be sure this runs.

Now let's make it look interesting.  Add a call to the end of CreateSurface:

    surface->ComputeSmoothNormals();

Now, create this empty function in CSGMesh:

void CSGMesh::ComputeSmoothNormals()
{

}

We're going to compute a normal for each vertex that is the average of the surface normals incident on the vertex.  First, we'll want to ensure there are the same number of normals as there are vertices and that they are all zeroed:

    m_normals.resize(m_vertices.size());
    for(unsigned int i=0;  i<m_vertices.size();  i++)
        m_normals[i] = CGrPoint(0, 0, 0, 0);

Now we need to iterate over all of the triangles.  For each we'll compute a surface normal.  We'll add that to the normal for each vertex the triangle uses:

    for(PTV v=m_triangles.begin();  v!=m_triangles.end();  )
    {
        // Collect up the vertices of a triangle...
        int a = v->v;
        v++;
        int b = v->v;
        v++;
        int c = v->v;
        v++;

        // Surface normal
        CGrPoint normal = Cross3(m_vertices[b] - m_vertices[a], 
                                 m_vertices[c] - m_vertices[a]);
        normal.Normalize3();

        // Add to the incident vertices normals
        m_normals[a] += normal;
        m_normals[b] += normal;
        m_normals[c] += normal;
    }

We're collecting up three vertices for a triangle in a, b, c.  We compute a surface normal from those vertices and add that to the normal for each vertex.  Finally, we normalize this result:

    // Normalize the normals
    for(unsigned int i=0;  i<m_vertices.size();  i++)
        m_normals[i].Normalize3();

Try this.  It should look like a smooth surface.  You might want to consider changing nW and nD to larger values to make it smoother.  I found it looked really nice with a value of 30 for each of these.

Wireframe

Temporarily add this line to the beginning of CSGMesh::Render:

    glPolygonMode(GL_FRONT, GL_LINE);

This is a handy way to tell what is going on in a figure.  It will render the scene in wireframe mode. You can comment that line back out.

Loading a Wavefront Obj File

The last thing we are going to do is to load a graphic object from a Wavefront OBJ file.  This is a standard file format used by many graphics systems.  The file fish.zip contains fish4.obj and BLUEGILL.bmp, a fish object and a texture image for the fish.  Place these two files in your project directory.  The fish object was obtained from www.planit3d.com. 

Create a new CSGMesh scene graph node called fish.  Create a material object that will set the material to a diffuse color of white.  After you create the fish object do this:

    fish->LoadOBJ("fish4.obj");

Now add this function to CSGMesh:

void CSGMesh::LoadOBJ(const char *filename)
{
    ifstream str(filename);
    if(!str)
    {
        AfxMessageBox("File not found");
        return;
    }

    string line;
    while(getline(str, line))
    {
        istringstream lstr(line);

        string code;
        lstr >> code;
        if(code == "v") 
        {
            double x, y, z;
            lstr >> x >> y >> z;
            AddVertex(CGrPoint(x, y, z));
        }
        else if(code == "vn")
        {
        }
        else if(code == "vt")
        {
        }
        else if(code == "f")
        {
        }

    }

}

You will need these includes:

#include <fstream>		// For ifstream
#include <string>		// For string
#include <sstream>		// For istringstream

using namespace std;

What this does:  It opens the file. If the open fails, it pops up a message box.  Then it loops over the file, reading one line at a time into the string "line".  It is then made into a stream so we can read what is on the line.  The first thing on the line will be a code telling what the line is.  I have included code to read the vertex.  The form of a vertex line is this:

v -0.00865893 0.379505 0.0551259

You can find the Wavefront OBJ file format specification at various places, including http://www.eg-models.de/formats/Format_Obj.html.  We'll only be using a few lines from the file.  The vertices are in order in the file. After the v we have x, y, and z.

You need to add code to read the vn line, which contains vertex normals and the vt line, which contains texture coordinates.  Here's what each of these lines looks like:

vn 0.183123 -0.981749 -0.0513315

vt 0.279729 0.036409

Note that the texture coordinate has only two numbers.

Finally, we have a face line:

f  2965/1970/2417 2966/1971/2417 2964/1969/2417

This defines a polygon consisting of three vertices.  Each group of three numbers is a vertex.  The first number is the vertex number.  The second number is the texture coordinate.  The third number is the normal.  Each of these values in a 1-based index.  The first vertex, normal, or texture coordinate is 1.  Since our indices are zero-based, we need to subtract one from each of these numbers.  In the fish file there are only triangles. If you try to load something else, you'll need to convert polygons to triangles.   Here is a simple handler for "f":

            for(int i=0;  i<3;  i++)
            {
                char slash;
                int v, t, n;
                lstr >> v >> slash >> t >> slash >> n;
                AddTriangleVertex(v-1, n-1, t-1);
            }

This will work only for triangles.  It will work for fish.obj.

Making the Fish Swim

The last thing we'll do is a simple animation that makes the fish swim. Put a rotation/translation node as the parent of the fish.  We'll rotate around the Y axis and make a simple swimming motion.  You'll need a hook to this rotation/translation node as a member variable in your CChildView class.  Call it m_fishhook (cute, huh?). 

The previous step assignment added code to rotate objects using a spin angle.  But, this simple method of animation is not very good.  How often does Timer get called?  What happens if you drag the window?   Instead, you should be using a method of animation based on real time. 

Add the header mmsystem.h to CChildView.cpp.  This will allow us to use the Windows multimedia timer functions.

We need to link an additional library to your application.  Select the SolutionView tab in the solution explorer and click on the project name (bold face in the field).  Select Project/Properties. A dialog box should pop up with the zillion or so options you can set for your project.  Expand "Configuration Properties" and "Linker".  Click on "Input".  In the top left of the dialog box you will see "Configuration:".  Change this to:  "All Configurations". 

Now add "winmm.lib" to Additional Dependencies.  We are adding an additional library. The dialog box should look like this:

Add these member variables to CChildView:

    bool        m_firstdraw;
    DWORD       m_starttime;

In the CChildView constructor, set m_firstdraw to true.

At the beginning of OnGLDraw, place this code:

    if(m_firstdraw)
    {
        m_firstdraw = false;
        m_spintimer = SetTimer(1, 30, NULL);
        timeBeginPeriod(1);
        m_starttime = timeGetTime();
    }

This creates the spin timer we had before, except this time we're not waiting for a menu option.  It also initializes the window multimedia timers.  These are millisecond resolution timers we can use to make our animation run accurately based on time.  timeGetTime() returns an integer that is the number of milliseconds since you system started up.  If we keep that number the first time we render, we can use it to determine how long it has been since then.

Now add this code to set the hook rotation.  This will be put in OnGLRender before you render you scene graph:

    double time = (timeGetTime() - m_starttime) * 0.001;
    m_fishhook->SetRotate(10 * sin(time * 6), 0, 1, 0);

Your Tasks

I want you to do two things to finish this up:

1. Texture map a picture onto the wavy surface.

2. Texture map BLUEGILL.bmp onto the fish. 

What you will turn in will be a program that creates a scene consisting of the wavy surface with a picture mapped onto it, the fish swimming above the surface, and the box above the fish.