Improving 3D performance in WPF
I was able to significantly improve the performance of the USA 3D model by reducing the number of discrete 3D models being rendered in the vieport. Originally, I was using the approach in my 3D Tutorial, which involves creating a 3D triangle model for each triangle in the mesh. While this approach makes it very easy to build composite 3D models (by combining many 3D models together), it is very slow for complex models. For example, the state of Minnesota has almost 5200 individual latitude and longitude points defined for it, which amounts to 5200 triangles on the top side, 5200 on the bottom side, and 10,400 triangles for the north/south/east/west sides. That's 20,800 total 3D models! With my new approach, I build only one 3D model per state, but use a more complex mesh. The old approach had one triangle per mesh. Now I'm putting all of the triangles in one mesh. So let's get into some details.
Disclaimer - I'm not going to get into any fundamentals of 3D modeling with WPF in this text. I'm purposely going to skip over what things like MeshGeometry3Ds , viewports, normals, right-hand rules, and triangle indeces are. The 3D Tutorial will help a little with those topics.
A state's cartographic data is defined by some vertices around its perimeter and a center vertex. Take this simplified Minnesota for example:
Minnesota Points
In this example, there are six perimeter points and one center point. The triangle mesh would look like this:
Minnesota Triangles
The right hand rule idea still applies from the tutorial. The triangles will need to be defined in a counter-clockwise direction so that the visible surface faces up:
Triangle 1: {pC, p2, p1}
Triangle 2: {pC, p3, p2}
Triangle 3: {pC, p4, p3}
Triangle 4: {pC, p5, p4}
Triangle 5: {pC, p6, p5}
In code, with a simple sorted list of points, it's pretty easy to define these triangles. The catch is that I want the mesh to be a bit more complex by adding some thickness in the Y direction:
Top and Bottom Points
pCT is the top center point and pCB is the bottom center point. The bottom points are easy to obtain by just subtracting a thickness value in the Y direction from the original points.
Now the mesh is looking a little more complex with triangles on the top, bottom, and sides:
Top Triangles
Bottom Triangles
Side Triangles
The purpose of showing these points and triangles is to help visualize a pattern that can be used to enumerate through the vertices and create the triangles in the mesh as efficiently as possible. With each point around the perimeter, four triangles in the mesh can be created. Take p1 for example. If we can safely assume that the vertices are ordered correctly in a collection, the following triangles can be created from a collection of vertices when we get to the index of p1 during the enumeration:
Triangle 1 (top): {pCT, p2, p1}
Triangle 2 (bottom): {pCB, p8, p7}
Triangle 3 (side 1): {p1, p2, p7}
Triangle 4 (side 2): {p7, p2, p8}
This can be simplified. We can safely assume that the bottom points are the same as the top points - except they have a different Y axis value. The bottom points can be notated with a "b" subscript:
Triangle 1 (top): {pC, p2, p1}
Triangle 2 (bottom): {pCb, p2b, p1b}
Triangle 3 (side 1): {p1, p2, p1b}
Triangle 4 (side 2): {p1b, p2, p2b}
We can finally define all four triangles at any index "i" in the enumeration as:
index i
index values: {1, 2, ... n}
When i < n:
Triangle 1 (top): {pC, p[i+1], p[i]}
Triangle 2 (bottom): {pCb, p[i+1]b, p[i]b}
Triangle 3 (side 1): {p[i], p[i+1], p[i]b}
Triangle 4 (side 2): {p[i]b, p[i+1], p[i+1]b}
When i == n:
Triangle 1 (top): {pC, p[1], p[i]}
Triangle 2 (bottom): {pCb, p[1]b, p[i]b}
Triangle 3 (side 1): {p[i], p[1], p[i]b}
Triangle 4 (side 2): {p[i]b, p[1], p[1]b}
I've chosen to implement the model generation with three methods. The first adds a single triangle to the mesh using any three points and adds triangle indeces, and normals. Triangle indeces must be added with consecutively numbered indexes, so the method must be given the starting index count and returns the new index count:
private int AddSingleMeshTriangle(
MeshGeometry3D mesh, Point3D p0, Point3D p1,
Point3D p2, int currentIndexCount)
{
Vector3D normal;
//add mesh positions from the
//supplied points
mesh.Positions.Add(p0);
mesh.Positions.Add(p1);
mesh.Positions.Add(p2);
//define the mesh's triangle
//indeces from a consecutive
//index count
mesh.TriangleIndices.Add(
currentIndexCount);
mesh.TriangleIndices.Add(
currentIndexCount + 1);
mesh.TriangleIndices.Add(
currentIndexCount + 2);
currentIndexCount += 3;
//calculate and add normals for
//each of the new triangle points
normal = CalculateNormal(p0, p1, p2);
mesh.Normals.Add(normal);
mesh.Normals.Add(normal);
mesh.Normals.Add(normal);
return currentIndexCount;
}
Next is the method that will add four triangles to the mesh given the current set of center points and perimeter points for the current vertex index. Basically, the caller provides the top, bottom, and four perimeter points and the method will add the triangles and return the new triangle index count:
private int AddPointsToMesh(
MeshGeometry3D mesh, Point3D topCenter,
Point3D bottomCenter, Point3D p0, Point3D p1,
Point3D p2, Point3D p3, int currentIndexCount)
{
//top
currentIndexCount = AddSingleMeshTriangle(
mesh, topCenter, p1, p0, currentIndexCount);
//bottom
currentIndexCount = AddSingleMeshTriangle(
mesh, bottomCenter, p2, p3, currentIndexCount);
//side1
currentIndexCount = AddSingleMeshTriangle(
mesh, p0, p1, p2, currentIndexCount);
//side2
currentIndexCount = AddSingleMeshTriangle(
mesh, p1, p3, p2, currentIndexCount);
return currentIndexCount;
}
Finally, the method that does all the action is LoadModel(). It's called by specifying a color for the model, the list
of vertices to use for the perimeter, and a step value. The step value indicates how many vertices to skip over
during enumeration. A higher step value will increase performance but lower the model quality:
public Model3D LoadModel(
Color color, List<Vertex> vertices, int step)
{
//the y value for the top surface
double yValue = 0;
//y axis thickness
double yThickness = 0.5;
//create a mesh to add triangles to
MeshGeometry3D mesh = new MeshGeometry3D();
Point3D p0, p1, p2, p3;
int indexCount = 0;
//define the top and bottom center points
Point3D topCenter = new Point3D(
vertices[0].Latitude,
yValue,
vertices[0].Longitude * -1);
Point3D bottomCenter = new Point3D(
vertices[0].Latitude,
yValue - yThickness,
vertices[0].Longitude * -1);
//loop throuh the vertex list
for (int i = 1; i < vertices.Count; i = i + step)
{
p0 = new Point3D(
vertices[i].Latitude,
yValue,
vertices[i].Longitude * -1);
//p2 is the same as p0, but with
//a different y value
p2 = new Point3D(
vertices[i].Latitude,
yValue - yThickness,
vertices[i].Longitude * -1);
//check to see if we're at the last index.
//If so, use index #1 for the second point
if (i + step >= vertices.Count)
{
p1 = new Point3D(
vertices[1].Latitude,
yValue,
vertices[1].Longitude * -1);
//p3 is the same as p1, but
//with a different y value
p3 = new Point3D(
vertices[1].Latitude,
yValue - yThickness,
vertices[1].Longitude * -1);
}
else
{
p1 = new Point3D(
vertices[i + step].Latitude,
yValue,
vertices[i + step].Longitude * -1);
//p3 is the same as p1, but
//with a different y value
p3 = new Point3D(
vertices[i + step].Latitude,
yValue - yThickness,
vertices[i + step].Longitude * -1);
}
indexCount = AddPointsToMesh(
mesh, topCenter, bottomCenter,
p0, p1, p2, p3, indexCount);
}
//create a visible surface for the mesh
Material material = new DiffuseMaterial(
new SolidColorBrush(color));
//create a new 3D model from the
//mesh and material
GeometryModel3D g = new GeometryModel3D(
mesh, material);
return g;
}
The result is a model of the state of MN (and the USA) that is of good quality and performs well when changing the camera position in real time:
Final Rendered Model (click to enlarge)
Final Rendered Model (click to enlarge)
I was suprised at first how big of an impact this simple refactoring made, but when I stepped back and realized exactly how many fewer models I was rendering (on the order of about 20,000 times fewer), it makes sense that the new way would perform better.
Posted: 06 February 2006