This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Bezier Patch Tesselator Submitted by

This code renders a Bezier Patch to a D3D device, it's pretty basic. Possible improvements: generate normals, give patch vertices texture coordinates, try central differencing (gamasutra article) to reduce the cost of calculating points. -Wade

Currently browsing [bezier.zip] (2,442 bytes) - [bezier.h] - (1,391 bytes)

    #ifndef BEZIER_H
    #define BEZIER_H

    // Mini algebra.h for standalone version.
    #ifndef ALGEBRA_H
    class vector2d
    {
    public:
        float x, y;
    };

    class vector3d
    {
    public:
        vector3d() {}
        vector3d( float _x, float _y, float _z ) : x( _x ), y( _y ), z( _z ) {}
        float x, y, z;
    };
    #endif

    //
    // TPatchVertex
    //
    // 3x3 array of vector3d's define a patch vertex.  This provides sharing of vertices and control points
    // between seperate patches in a 'patch mesh'.  An improved version might implement this higher level
    // structure and provide sharing of calculated surface points, since there's currently some redundant work.
    //
    // The middle vert (vert[1][1]) is the vertex, the surrounding verts are control points.
    // The four corners of the patches fall on their patch vertices.  The curve is adjusted by the control points
    // but doesn't neccessarily intersect them.
    typedef vector3d TPatchVertex[3][3];

    struct SPatch
    {
        int Verts[4];       // index into vertex pool ordered clockwise from UL
    };

    // Debugging tools.
    extern bool DrawCtrl, DrawLines, DrawPolys;

    // Number of patch point calculations per frame.
    extern int PointCount;

    // Draw a patch using the 3D Device.  Generates vertices and 0 to 1 texture coordinates.
    void DrawPatch( LPDIRECT3DDEVICE7 pd3dDevice, SPatch* Patch, TPatchVertex* VertexPool, float Subdiv );

    #endif

Currently browsing [bezier.zip] (2,442 bytes) - [bezier.cpp] - (5,746 bytes)

    #pragma warning(disable:4244)
    #pragma warning(disable:4800)
    #pragma warning(disable:4305)

    // Comment this line if you have algebra.h
    //#define NO_ALGEBRA_H

    #include <d3d.h>
    #include <assert.h>

    #ifndef NO_ALGEBRA_H
    #include "algebra.h"
    #endif

    #include "bezier.h"

    // Globals
    D3DVERTEX D3DVerts[6] = { { 0 } };
    bool DrawCtrl, DrawLines, DrawPolys;
    int PointCount;

    // Bezier basis functions
    void bez(float u, float* bez)
    {
        float invu = 1 - u;
        bez[0] = invu * invu * invu;
        bez[1] = 3 * u * invu * invu;
        bez[2] = 3 * u * u * invu;
        bez[3] = u * u * u;
    }

    // TCtrlPoints - bezier basis function inputs.  A TCtrlPoints is created from the inner sections
    // of 4 TPatchVertex objects by DrawPatch.
    typedef vector3d TCtrlPoints[4][4];

    void GetPatchPoint( float u, float v, TCtrlPoints* Ctrl, vector3d* Out )
    {
        vector3d Point( 0, 0, 0 ); // Output

        // Keep track of how many Points evaluated per frame.
        PointCount++;

        float bezx[4], bezy[4];
        bez( u, bezx );
        bez( v, bezy );

        int i, j;
        for ( i = 0; i < 4; i++ )
            for ( j = 0; j < 4; j++ )
            {
                vector3d* cp = &( *Ctrl )[j][i];
                float cpscale = bezx[j] * bezy[i];
                Point.x += cp->x * cpscale;
                Point.y += cp->y * cpscale;
                Point.z += cp->z * cpscale;
            }

        *Out = Point;
    }

    void DrawPatch( LPDIRECT3DDEVICE7 pd3dDevice, SPatch* Patch, TPatchVertex* VertexPool, float Subdiv )
    {
        TCtrlPoints Ctrl;        // 16 control Points that ultimately define SPatch
        TPatchVertex* pv;

        // Get control Points from TL SPatch vertex.
        pv = &VertexPool[Patch->Verts[0]];
        Ctrl[0][0] = (*pv)[1][1];
        Ctrl[1][0] = (*pv)[2][1];
        Ctrl[0][1] = (*pv)[1][2];
        Ctrl[1][1] = (*pv)[2][2];

        // Get control Points from TR SPatch vertex.
        pv = &VertexPool[Patch->Verts[1]];
        Ctrl[2][0] = (*pv)[0][1];
        Ctrl[3][0] = (*pv)[1][1];
        Ctrl[2][1] = (*pv)[0][2];
        Ctrl[3][1] = (*pv)[1][2];

        // Get control Points from BR SPatch vertex.
        pv = &VertexPool[Patch->Verts[2]];
        Ctrl[2][2] = (*pv)[0][0];
        Ctrl[3][2] = (*pv)[1][0];
        Ctrl[2][3] = (*pv)[0][1];
        Ctrl[3][3] = (*pv)[1][1];

        // Get control Points from BL SPatch vertex.
        pv = &VertexPool[Patch->Verts[3]];
        Ctrl[0][2] = (*pv)[1][0];
        Ctrl[1][2] = (*pv)[2][0];
        Ctrl[0][3] = (*pv)[1][1];
        Ctrl[1][3] = (*pv)[2][1];

        if ( DrawCtrl )
        {
            // draw the control poxnts.
            for ( int x = 0; x < 3; x++ )
                for ( int y = 0; y < 3; y++ )
                {
                    D3DVerts[0].x = Ctrl[x][y].x;
                    D3DVerts[0].y = Ctrl[x][y].y;
                    D3DVerts[0].z = Ctrl[x][y].z;

                    D3DVerts[1].x = Ctrl[x + 1][y].x;
                    D3DVerts[1].y = Ctrl[x + 1][y].y;
                    D3DVerts[1].z = Ctrl[x + 1][y].z;

                    D3DVerts[2].x = Ctrl[x + 1][y + 1].x;
                    D3DVerts[2].y = Ctrl[x + 1][y + 1].y;
                    D3DVerts[2].z = Ctrl[x + 1][y + 1].z;

                    D3DVerts[3].x = Ctrl[x][y + 1].x;
                    D3DVerts[3].y = Ctrl[x][y + 1].y;
                    D3DVerts[3].z = Ctrl[x][y + 1].z;

                    D3DVerts[4].x = Ctrl[x][y].x;
                    D3DVerts[4].y = Ctrl[x][y].y;
                    D3DVerts[4].z = Ctrl[x][y].z;

                    pd3dDevice->DrawPrimitive( D3DPT_LINESTRIP, D3DFVF_VERTEX, D3DVerts, 5, NULL );
                }
        }

        if ( DrawLines || DrawPolys )
        {
            assert( Subdiv >= 1.0 );
            float Step = 1.0 / Subdiv;

            // ok, now draw the curve Points
            for ( float i = 0.0; i < 1.0; i += Step )
                for ( float j = 0.0; j < 1.0; j += Step )
                {
                    vector3d v;
                    float di = Step, dj = Step;

                    if ( i + di > 1.0 )
                        di = 1.0 - i;

                    if ( j + dj > 1.0 )
                        dj = 1.0 - j;

                    // triangle 1
                    GetPatchPoint( i, j, &Ctrl, &v );
                    D3DVerts[0].x = v.x;
                    D3DVerts[0].y = v.y;
                    D3DVerts[0].z = v.z;
                    D3DVerts[0].tu = i;
                    D3DVerts[0].tv = j;

                    GetPatchPoint( i + di, j, &Ctrl, &v );
                    D3DVerts[1].x = v.x;
                    D3DVerts[1].y = v.y;
                    D3DVerts[1].z = v.z;
                    D3DVerts[1].tu = i + di;
                    D3DVerts[1].tv = j;

                    GetPatchPoint( i, j + dj, &Ctrl, &v );
                    D3DVerts[2].x = v.x;
                    D3DVerts[2].y = v.y;
                    D3DVerts[2].z = v.z;
                    D3DVerts[2].tu = i;
                    D3DVerts[2].tv = j + dj;

                    GetPatchPoint( i + di, j + dj, &Ctrl, &v );
                    D3DVerts[3].x = v.x;
                    D3DVerts[3].y = v.y;
                    D3DVerts[3].z = v.z;
                    D3DVerts[3].tu = i + di;
                    D3DVerts[3].tv = j + dj;

                    if ( DrawPolys )
                        pd3dDevice->DrawPrimitive( D3DPT_TRIANGLESTRIP, D3DFVF_VERTEX, D3DVerts, 4, NULL );

                    if ( DrawLines )
                    {
                        // Flip stuff around to get the extra lines.
                        D3DVERTEX TempVert = D3DVerts[2];
                        D3DVerts[2] = D3DVerts[3];
                        D3DVerts[3] = TempVert;
                        D3DVerts[4] = D3DVerts[0];
                        D3DVerts[5] = D3DVerts[2];
                        pd3dDevice->DrawPrimitive( D3DPT_LINESTRIP, D3DFVF_VERTEX, D3DVerts, 6, NULL );
                    }
                }
        }
    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.