Kai-Uwe Bux wrote:

<snip>

However, I am curious: what is the underlying problem that this design is

supposed to solve? Maybe there is a different approach altogether.

I'll try to summarise as briefly as possible, but it's still going to be

quite long, so feel free to retract the offer of help if your curiosity

wanes :-)

I am working with a planet-sized fractal terrain with dynamic level of

detail, represented by a binary tree of triangular "patches". I use a

variant of the ROAM algorithm[1] to construct this tree. I have a class

representing such a patch - let's call it TriPatch. The algorithm that

turns a TriPatch into actual rendered triangles can work at one of four

global "density" settings - each higher density level stores more

vertices (call them Points) per patch, so I templated TriPatch as follows:

template<int densityclass TriPatch

{

TriPatch* leftChild, *rightChild;

// ... more common attributes/methods

Point points[SomeFunctionOf(density)];

void GenerateNewPoints();

};

template<int densityvoid TriPatch<0>::GenerateNewPoints()

{

// unique code for density setting 0...

points[0] = Point::GeneratePoint(...);

...

}

....

template<int densityvoid TriPatch<3>::GenerateNewPoints()

{

// unique code for density setting 3...

}

Now, I want to reuse the terrain code to render water (effectively as a

"flat" terrain), sharing the same basic binary tree structure and

operations.

The Points stored inside each TriPatch are generated by a fractal

algorithm (midpoint displacement[2]) that takes surrounding vertices as

input. The vertices store fractal seeds along with their 3D positions.

With water, though, the vertex generation code will not apply a fractal

perturbation, and no fractal parameters will be stored at each vertex.

So, my plan was to create a distinct WaterPoint type (with its own

implementation of GenPoint), and to further templatise TriPatch on the

point type:

template<typename PointT, int densityclass TriPatch

{

// as above, except

PointT points[...];

};

Terrain and water binary trees could then be initialised as follows:

const int density = 2;

TriPatch<Point, densitymyTerrain = new TriPatch<Point, density>;

TriPatch<WaterPoint, densitymyWater = new TriPatch<WaterPoint, density>;

The GenerateNewPoints method given above remains the same regardless of

the point type used, since it calls PointT's own GenPoint for the actual

generation. It needs to be specialised only for /density/, hence the

example in my original post where we specialised on the non-type

parameter, while the type parameter remained unspecified.

Now, to achieve my "terrain patch" and "water patch" types I could

simply duplicate the bin-tree structure and associated algorithms, but

since these make up most of the code, and are identical in both cases, I

felt that I should strive for shared code. Since I am potentially

calling methods on many thousands of TriPatches per frame (at 60 frames

per second), I don't want methods like GenerateNewPoints to be virtual

functions. And since the density setting and vertex generation algorithm

for any particular tree of TriPatches is known at compile-time, I

figured this was an ideal situation for templates.

I'm trying to find a solution that maximises performance and code

re-use, while remaining fairly readable. If there is a different

approach that satisfies these criteria, I'd be happy to hear about it!

Thanks if you read this far :-)

--

Paul Roberts

www.m3fe.com
[1]

http://www.llnl.gov/graphics/ROAM/
[2]

http://www.gameprogrammer.com/fractal.html