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.