Theories and algorithms for subdivision of surface

Question

I have the following problem:

Here is how I draw a cube on the screen:

void drawCube()
{

    //glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); // Clear color and depth buffers
    glPushAttrib(GL_POLYGON_BIT | GL_ENABLE_BIT | GL_COLOR_BUFFER_BIT) ;

    glPolygonMode(GL_FRONT_AND_BACK, GL_LINE) ;
    //glDisable(GL_LIGHTING) ;

    glBegin(GL_QUADS);                // Begin drawing the color cube with size 3cm x 3.5cm x 4cm
        // Top face (y = 1.0f)
        // Define vertices in counter-clockwise (CCW) order with normal pointing out
        glColor3f(0.0f, 1.0f, 0.0f);     // Green
        glVertex3f( 1.75f, 1.75f, -4.0f);
        glVertex3f(-1.75f, 1.75f, -4.0f);
        glVertex3f(-1.75f, 1.75f,  1.0f);
        glVertex3f( 1.75f, 1.75f,  1.0f);

        // Bottom face (y = -1.0f)
        glColor3f(1.0f, 0.5f, 0.0f);     // Orange
        glVertex3f( 1.75f, -1.75f,  1.0f);
        glVertex3f(-1.75f, -1.75f,  1.0f);
        glVertex3f(-1.75f, -1.75f, -4.0f);
        glVertex3f( 1.75f, -1.75f, -4.0f);

        // Front face  (z = 1.0f)
        glColor3f(1.0f, 0.0f, 0.0f);     // Red
        glVertex3f( 1.75f,  1.75f, 1.0f);
        glVertex3f(-1.75f,  1.75f, 1.0f);
        glVertex3f(-1.75f, -1.75f, 1.0f);
        glVertex3f( 1.75f, -1.75f, 1.0f);

        // Back face (z = -1.0f)
        glColor3f(1.0f, 1.0f, 0.0f);     // Yellow
        glVertex3f( 1.75f, -1.75f, -4.0f);
        glVertex3f(-1.75f, -1.75f, -4.0f);
        glVertex3f(-1.75f,  1.75f, -4.0f);
        glVertex3f( 1.75f,  1.75f, -4.0f);

        // Left face (x = -1.0f)
        glColor3f(0.0f, 0.0f, 1.0f);     // Blue
        glVertex3f(-1.75f,  1.75f,  1.0f);
        glVertex3f(-1.75f,  1.75f, -4.0f);
        glVertex3f(-1.75f, -1.75f, -4.0f);
        glVertex3f(-1.75f, -1.75f,  1.0f);

        // Right face (x = 1.0f)
        glColor3f(1.0f, 0.0f, 1.0f);     // Magenta
        glVertex3f(1.75f,  1.75f, -4.0f);
        glVertex3f(1.75f,  1.75f,  1.0f);
        glVertex3f(1.75f, -1.75f,  1.0f);
        glVertex3f(1.75f, -1.75f, -4.0f);
    glEnd();  // End of drawing color-cube


    glPopAttrib() ;
}

The question is how can I assign 'sample points' between all vertices?

From my understanding I need to find the distance between vertices and divide it into (say) five equal parts. For the sake of argument, imagine that the space between two vertices is 1, so 5 points will be placed on 0.2 distance from each other. Also they need to be stored in kind of a memory structure (vector/array) so that each one of them can be accessed and translated into screen coordinates at a later stage.

However, how can I do this in C++ in a totally generic way so that it could be applied basically to any distance metrics?

Here is how the cube looks like

Answer 1

Here is my drawBox function, if you want you can modify it to draw different color at each face.

void DrawBox(GLfloat fWidth,GLfloat fHeight,GLfloat fDepth,GLint wslices,GLint dslices,GLint stacks)
{
     // Calculate number of primitives on each side of box
     // because we can use different tessalation configurations 
     // we must calculate separate group of box sides 

    int iTopButtonQuads = wslices * dslices * 2; // Calculate number of quads in top and button sides
    int iLeftRightQuads = dslices * stacks * 2; // Calculate number of quads in left and right sides
    int iFrontBackQuads = wslices * stacks * 2; // Calculate number of quads in front and back sides

    // If we consider to use quads as primitive then each primitive will
    // have 4 points, and each point has color, coord and normal attribute.
    // So we create separate array to contain each attibute values.

    float* pfVertices = new float[(iTopButtonQuads + iLeftRightQuads + iFrontBackQuads) * 3 * 4];
    float* pfColors = new float[(iTopButtonQuads + iLeftRightQuads + iFrontBackQuads) * 3 * 4];
    float* pfNormals = new float[(iTopButtonQuads + iLeftRightQuads + iFrontBackQuads) * 3 * 4];

    int iVertexIndex = 0;

    GLfloat Xstep = fWidth / wslices;
    GLfloat Ystep = fHeight / stacks;
    GLfloat Zstep = fDepth / dslices;

    GLfloat firstX = fWidth / 2.0f;
    GLfloat firstY = fHeight / 2.0f;
    GLfloat firstZ = fDepth / 2.0f;

    GLfloat currX = 0.0f;
    GLfloat currY = 0.0f;
    GLfloat currZ = 0.0f;

    GLfloat x_status = 0.0f;
    GLfloat y_status = 0.0f;
    GLfloat z_status = 0.0f;

    // the bottom and the top of the box
    for (currZ = -firstZ, z_status = 0.0f; currZ < firstZ - Zstep / 2.0f; currZ += Zstep, z_status += Zstep)
    {
        for (currX = -firstX, x_status = 0.0f; currX < firstX - Xstep / 2.0f; currX += Xstep, x_status += Xstep)
        {
            int iCurrentIndex = iVertexIndex * 3 * 4;

            float pfNormal[3] = { 0.0f, -1.0f, 0.0f };

            memcpy(pfNormals + iCurrentIndex, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 3, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 6, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 9, pfNormal, 3 * 4);

            float pfColor[3] = { 1.0f, 0.0f, 0.0f };

            memcpy(pfColors + iCurrentIndex, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 3, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 6, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 9, pfColor, 3 * 4);

            float pfVertex0[3] = {currX,-firstY,currZ};
            float pfVertex1[3] = {currX + Xstep,-firstY,currZ};
            float pfVertex2[3] = {currX + Xstep,-firstY,currZ + Zstep};
            float pfVertex3[3] = {currX,-firstY,currZ + Zstep};

            memcpy(pfVertices + iCurrentIndex, pfVertex0, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 3, pfVertex1, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 6, pfVertex2, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 9, pfVertex3, 3 * 4);

            iVertexIndex++;
        }

        for (currX = -firstX, x_status = 0.0f; currX < firstX - Xstep / 2.0f; currX += Xstep, x_status += Xstep)
        {
            int iCurrentIndex = iVertexIndex * 3 * 4;

            float pfNormal[3] = { 0.0f, 1.0f, 0.0f };

            memcpy(pfNormals + iCurrentIndex, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 3, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 6, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 9, pfNormal, 3 * 4);

            float pfColor[3] = { 0.0f, 1.0f, 0.0f };

            memcpy(pfColors + iCurrentIndex, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 3, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 6, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 9, pfColor, 3 * 4);

            float pfVertex0[3] = {currX + Xstep,firstY,currZ + Zstep};
            float pfVertex1[3] = {currX + Xstep,firstY,currZ};
            float pfVertex2[3] = {currX,firstY,currZ};
            float pfVertex3[3] = {currX,firstY,currZ + Zstep};

            memcpy(pfVertices + iCurrentIndex, pfVertex0, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 3, pfVertex1, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 6, pfVertex2, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 9, pfVertex3, 3 * 4);

            iVertexIndex++;
        }
    }

    // the front and the back of the box
    for (currY = -firstY, y_status = 0.0f; currY < firstY - Ystep / 2.0f ; currY += Ystep, y_status += Ystep)
    {
        for (currX = -firstX, x_status = 0.0f; currX < firstX - Xstep / 2.0f; currX += Xstep, x_status += Xstep)
        {
            int iCurrentIndex = iVertexIndex * 3 * 4;

            float pfNormal[3] = { 0.0f, 0.0f, 1.0f };

            memcpy(pfNormals + iCurrentIndex, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 3, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 6, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 9, pfNormal, 3 * 4);

            float pfColor[3] = { 0.0f, 0.0f, 1.0f };

            memcpy(pfColors + iCurrentIndex, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 3, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 6, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 9, pfColor, 3 * 4);

            float pfVertex0[3] = {currX,currY,firstZ};
            float pfVertex1[3] = {currX + Xstep,currY,firstZ};
            float pfVertex2[3] = {currX + Xstep,currY + Ystep,firstZ};
            float pfVertex3[3] = {currX,currY + Ystep,firstZ};

            memcpy(pfVertices + iCurrentIndex, pfVertex0, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 3, pfVertex1, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 6, pfVertex2, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 9, pfVertex3, 3 * 4);

            iVertexIndex++;
        }

        for (currX = -firstX, x_status = 0.0f; currX < firstX - Xstep / 2.0f; currX += Xstep, x_status += Xstep)
        {
            int iCurrentIndex = iVertexIndex * 3 * 4;

            float pfNormal[3] = { 0.0f, 0.0f, -1.0f };

            memcpy(pfNormals + iCurrentIndex, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 3, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 6, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 9, pfNormal, 3 * 4);

            float pfColor[3] = { 0.0f, 1.0f, 1.0f };

            memcpy(pfColors + iCurrentIndex, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 3, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 6, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 9, pfColor, 3 * 4);

            float pfVertex0[3] = {currX + Xstep,currY + Ystep,-firstZ};
            float pfVertex1[3] = {currX + Xstep,currY,-firstZ};
            float pfVertex2[3] = {currX,currY,-firstZ};
            float pfVertex3[3] = {currX,currY + Ystep,-firstZ};

            memcpy(pfVertices + iCurrentIndex, pfVertex0, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 3, pfVertex1, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 6, pfVertex2, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 9, pfVertex3, 3 * 4);

            iVertexIndex++;
        }
    }

    // Right side and the left side of the box
    for (currY = -firstY, y_status = 0.0f; currY < firstY - Ystep / 2.0f; currY += Ystep, y_status += Ystep)
    {
        for (currZ = -firstZ, z_status = 0.0f; currZ < firstZ - Zstep / 2.0f; currZ += Zstep, z_status += Zstep)
        {
            int iCurrentIndex = iVertexIndex * 3 * 4;

            float pfNormal[3] = { 1.0f, 0.0f, 0.0f };

            memcpy(pfNormals + iCurrentIndex, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 3, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 6, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 9, pfNormal, 3 * 4);

            float pfColor[3] = { 1.0f, 0.0f, 1.0f };

            memcpy(pfColors + iCurrentIndex, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 3, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 6, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 9, pfColor, 3 * 4);

            float pfVertex0[3] = {firstX,currY,currZ};
            float pfVertex1[3] = {firstX,currY + Ystep,currZ};
            float pfVertex2[3] = {firstX,currY + Ystep,currZ + Zstep};
            float pfVertex3[3] = {firstX,currY,currZ + Zstep};

            memcpy(pfVertices + iCurrentIndex, pfVertex0, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 3, pfVertex1, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 6, pfVertex2, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 9, pfVertex3, 3 * 4);

            iVertexIndex++;
        }

        for (currZ = -firstZ, z_status = 0.0f; currZ < firstZ - Zstep / 2.0f; currZ += Zstep, z_status += Zstep)
        {
            int iCurrentIndex = iVertexIndex * 3 * 4;

            float pfNormal[3] = { -1.0f, 0.0f, 0.0f };

            memcpy(pfNormals + iCurrentIndex, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 3, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 6, pfNormal, 3 * 4);
            memcpy(pfNormals + iCurrentIndex + 9, pfNormal, 3 * 4);

            float pfColor[3] = { 1.0f, 1.0f, 0.0f };

            memcpy(pfColors + iCurrentIndex, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 3, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 6, pfColor, 3 * 4);
            memcpy(pfColors + iCurrentIndex + 9, pfColor, 3 * 4);

            float pfVertex0[3] = {-firstX,currY,currZ};
            float pfVertex1[3] = {-firstX,currY,currZ + Zstep};
            float pfVertex2[3] = {-firstX,currY + Ystep,currZ + Zstep};
            float pfVertex3[3] = {-firstX,currY + Ystep,currZ};

            memcpy(pfVertices + iCurrentIndex, pfVertex0, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 3, pfVertex1, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 6, pfVertex2, 3 * 4);
            memcpy(pfVertices + iCurrentIndex + 9, pfVertex3, 3 * 4);

            iVertexIndex++;
        }
    }

    glEnableClientState(GL_VERTEX_ARRAY);
    glEnableClientState(GL_COLOR_ARRAY);
    glEnableClientState(GL_NORMAL_ARRAY);

    glColorPointer(3, GL_FLOAT, 0, (void*)pfColors);
    glNormalPointer(GL_FLOAT, 0, (void*)pfNormals);
    glVertexPointer(3, GL_FLOAT, 0, (void*)pfVertices);

    glDrawArrays(GL_QUADS, 0, (iTopButtonQuads + iLeftRightQuads + iFrontBackQuads) * 4);

    glDisableClientState(GL_VERTEX_ARRAY);
    glDisableClientState(GL_COLOR_ARRAY);
    glDisableClientState(GL_NORMAL_ARRAY);

    delete [] pfVertices;
    delete [] pfNormals;
    delete [] pfColors;
}

the result will be like

this is the example of usage created arrays, to collect some shape statistics

    // Example 
    // Find min-max of shapes coordinates

    // Get coord of first vertex
    float fMinX = pfVertices[0];
    float fMinY = pfVertices[1];
    float fMinZ = pfVertices[2];

    float fMaxX = pfVertices[0];
    float fMaxY = pfVertices[1];
    float fMaxZ = pfVertices[2];

    for (int iVertexIndex = 0; iVertexIndex < (iTopButtonQuads + iLeftRightQuads + iFrontBackQuads) * 4; iVertexIndex++)
    {
        int iCurrentIndex = iVertexIndex * 3; // (x y z) per vertex

        if (pfVertices[iCurrentIndex] < fMinX)
            fMinX = pfVertices[iCurrentIndex];

        if (pfVertices[iCurrentIndex + 1] < fMinY)
            fMinY = pfVertices[iCurrentIndex + 1];

        if (pfVertices[iCurrentIndex + 2] < fMinZ)
            fMinZ = pfVertices[iCurrentIndex + 2];

        if (pfVertices[iCurrentIndex] > fMaxX)
            fMaxX = pfVertices[iCurrentIndex];

        if (pfVertices[iCurrentIndex + 1] > fMaxY)
            fMaxY = pfVertices[iCurrentIndex + 1];

        if (pfVertices[iCurrentIndex + 2] > fMaxZ)
            fMaxZ = pfVertices[iCurrentIndex + 2];
    }

    // Create an axes aligned bounding box 
    // by simply drawing inflated min-maxes, that we collect
    // example of using indexed primitives

    glDisable(GL_CULL_FACE);

    GLfloat vertices[] = {
        fMinX - 2.0, fMaxY + 2.0, fMaxZ + 2.0,
        fMaxX + 2.0, fMaxY + 2.0, fMaxZ + 2.0,
        fMaxX + 2.0, fMinY - 2.0, fMaxZ + 2.0,
        fMinX - 2.0, fMinY - 2.0, fMaxZ + 2.0,
        fMinX - 2.0, fMaxY + 2.0, fMinZ - 2.0,
        fMaxX + 2.0, fMaxY + 2.0, fMinZ - 2.0,
        fMaxX + 2.0, fMinY - 2.0, fMinZ - 2.0,
        fMinX - 2.0, fMinY - 2.0, fMinZ - 2.0
    };

    GLint indices[] = {
        0, 1, 2, 3,
        4, 5, 1, 0,
        3, 2, 6, 7,
        5, 4, 7, 6,
        1, 5, 6, 2,
        4, 0, 3, 7 
    };

    glColor3f(1.0f, 1.0f, 1.0f);

    glEnableClientState(GL_VERTEX_ARRAY);

    glVertexPointer(3, GL_FLOAT, 0, (void*)vertices);

    glDrawElements(GL_QUADS, 24, GL_UNSIGNED_INT, (void*)indices);

    glDisableClientState(GL_VERTEX_ARRAY);

    glEnable(GL_CULL_FACE);