[Beginning Database Design Solutions, Second Edition]

Title: Use a dictionary to draw a 3D Menger sponge fractal more efficiently using WPF, XAML, and C#

$Menger sponge fractal$ The example Draw a 3D Menger sponge fractal using WPF, XAML, and C# shows how to build a Menger sponge. That example recursively chops up cubes and discards pieces of them until it reaches a desired level of recursion. At that point, it draws a cube.

This is reasonably easy to understand, but it requires a fair amount of duplicated drawing because many of the cubes share faces. In fact, if two cubes share a face, then neither of those instances of the common face should be drawn.

This example uses a Dictionary to avoid drawing those shared faces. Implementing the program was trickier than I thought it would be. That makes this post a bit long, but I think it's interesting.

To avoid drawing duplicated faces, the program uses three main techniques:

An ApproxPoint class to represent points with limited precision. If two points are very close, they should be regarded as the same point. They may differ slightly due to rounding errors.
A Rectangle3D class to represent rectangles. If two rectangles have the same approximate points, even if they are arranged in different orders, then the two rectangles should be regarded as the same rectangle.
A Dictionary holding Rectangle3D objects so it's easy to tell if the same face is being drawn twice.

Essential Algorithms: A Practical Approach to Computer Algorithms. That book doesn't talk much about graphics, but it does cover sorting (which this program uses), hash tables (which is how dictionaries are implemented), recursion (it describes some two-dimensional recursive fractals), and a bunch of other interesting stuff. For more information including a table of contents, go to the book's Wiley web page.

ApproxPoint

Due to rounding errors during calculations, two points that should be the same might not have exactly the same coordinates. That means when the program compares them to see whether two rectangles are the same, it might think two rectangles that use the same points are different. To overcome this problem, I created the following ApproxPoint class. Unfortunately to compare points, this class needs to be somewhat more complicated than I would like.

// A class to represent approximate points. public class ApproxPoint : IComparable<ApproxPoint> { public double X, Y, Z; public ApproxPoint(double x, double y, double z) { X = Math.Round(x, 3); Y = Math.Round(y, 3); Z = Math.Round(z, 3); } public ApproxPoint(Point3D point) : this(point.X, point.Y, point.Z) { } public bool Equals(ApproxPoint point) { return ( (X == point.X) && (Y == point.Y) && (Z == point.Z)); } public override bool Equals(object obj) { if (obj == null) return false; if (!(obj is ApproxPoint)) return false; return this.Equals(obj as ApproxPoint); } public static bool operator ==(ApproxPoint point1, ApproxPoint point2) { return point1.Equals(point2); } public static bool operator !=(ApproxPoint point1, ApproxPoint point2) { return !point1.Equals(point2); } public override int GetHashCode() { int hashx = X.GetHashCode() << 3; int hashy = Y.GetHashCode() << 5; int hashz = Z.GetHashCode(); int result = hashx ^ hashy ^ hashz; return result; } public int CompareTo(ApproxPoint other) { if (X < other.X) return -1; if (X > other.X) return 1; if (Y < other.Y) return -1; if (Y > other.Y) return 1; if (Z < other.Z) return -1; if (Z > other.Z) return 1; return 0; } }

The class starts by declaring variables to hold the point's X, Y, and Z coordinates. Its constructor uses Math.Round to round the point's true coordinates to 3 decimal places. The result is the points (0.01, 0.02, 0.03) and (0.0101, 0.0201, 0.0301) have the same rounded coordinates, so the program can treat them as equal.

To make it easy to test equality, the class provides an Equals method. It also overrides the default Equals method that it inherits, and overrides the == and != operators. (Those come as a pair so if you override == then you must also override !=.)

Next the class overrides its GetHashCode method. Usually if you override Equals, you should also override GetHashCode. (So two objects that are equal produce the same hash code.) This method will be useful in the Rectangle3D class.

This class's GetHashCode method calls the coordinates' GetHashCode methods, bit shifts them by varying amounts, and uses the XOR operator to combine the results. It uses different bit shifts for the coordinates so two points with the same coordinates in different orders, such as (1, 2, 3) and (3, 2, 1), are unlikely to have the same hash codes.

Finally the class provides a CompareTo method to determine an ordering between points. This allows the class to implement the IComparable interface. Again this will be useful in the Rectangle3D class.

Rectangle3D

The Rectangle3D class represents the points that make up a rectangle. It also allows the program to compare two rectangles to see if they are the same. The following code shows the Rectangle3D class used by this program.

public class Rectangle3D { // The rectangle's approximate points. public ApproxPoint[] APoints; // The rectangle's approximate points. public Point3D[] Points; // Initializing constructor. public Rectangle3D(Point3D point1, Point3D point2, Point3D point3, Point3D point4) { // Save the points. Points = new Point3D[] { point1, point2, point3, point4, }; // Save the approximate points. APoints = new ApproxPoint[] { new ApproxPoint(point1), new ApproxPoint(point2), new ApproxPoint(point3), new ApproxPoint(point4), }; // Sort the approximate points. Array.Sort(APoints); } // Return true if the rectangles // contain roughly the same points. public bool Equals(Rectangle3D other) { // Return true if the ApproxPoints are equal. for (int i = 0; i < 4; i++) if (APoints[i] != other.APoints[i]) return false; return true; } public override bool Equals(Object obj) { // If parameter is null, return false. if (obj == null) return false; // If parameter cannot be cast into a Rectangle3D, // return false. if (!(obj is Rectangle3D)) return false; // Invoke the previous version of Equals. return this.Equals(obj as Rectangle3D); } public static bool operator ==(Rectangle3D rect1, Rectangle3D rect2) { return rect1.Equals(rect2); } public static bool operator !=(Rectangle3D rect1, Rectangle3D rect2) { return !rect1.Equals(rect2); } // Return a hash code. public override int GetHashCode() { int hash0 = APoints[0].GetHashCode() << 3; int hash1 = APoints[1].GetHashCode() << 5; int hash2 = APoints[2].GetHashCode() << 7; int hash3 = APoints[3].GetHashCode(); int result = hash0 ^ hash1 ^ hash2 ^ hash3; return result; } }

The class starts by defining arrays to hold the rectangle's true Point3D values and rounded ApproxPoint values. The constructor saves the rectangle's points and the points rounded. It then sorts the ApproxPoint values. (This is why the ApproxPoint class must implement IComparable.) That makes it easy to compare the points in two rectangles to see if they are the same rectangle without worrying about the points' ordering. (In this example, if a rectangle is repeated, then the two rectangles have different orientations and it's unlikely that they start with the same point. Ignoring the points' ordering makes it easier to tell if the rectangles contain the same points.)

Next the class redefines equality much as the ApproxPoint class does. It defines Equals, overrides the inherited version of Equals, and overrides == and !=.

Finally the class overrides its GetHashCode method. It takes the hash codes of the ApproxPoint values (this is why the ApproxPoint class overrides its GetHashCode method), bit shifts them by different amounts, and combines them with the XOR operator. (This GetHashCode method is used by the dictionary described next.)

Using a Dictionary

The program uses the ApproxPoint and Rectangle3D classes to ensure that it doesn't draw any rectangles that are created twice by the Menger sponge algorithm. To do that, it creates a dictionary to hold Rectangle3D objects.

// A dictionary to hold triangle information. private Dictionary<Rectangle3D, int> RectanglesMade;

Before it creates the data, it initializes the dictionary. MakeSpongeRectangles is the recursive method that generates the sponge's data. (It's similar to the version used by the previous example so it isn't shown here.) When it reaches the desired level of recursion, the method calls the AddCube method to add a cube to the mesh data. AddCube calls the following AddRectangle method 6 times to create the cube's 6 faces. That's where things get interesting again.

private void AddRectangle(MeshGeometry3D mesh, Point3D point1, Point3D point2, Point3D point3, Point3D point4) { // See if we already made this rectangle. Rectangle3D rect = new Rectangle3D(point1, point2, point3, point4); if (RectanglesMade.ContainsKey(rect)) { // We've drawn it before. Remove it. RectanglesMade.Remove(rect); } else { // This is a new one. Add it. RectanglesMade.Add(rect, 1); } }

This method creates a new Rectangle3D object representing the new rectangle. It then calls the dictionary's ContainsKey method to see if that rectangle has already been built. If it has, then this is a rectangle that is created twice by the sponge algorithm, so it lies inside the sponge's solid object and should not be drawn. In that case, the program removes the rectangle from the dictionary. (Internally the dictionary uses the rectangle's GetHashCode method to find its location in the dictionary's data structure. It then uses the overridden Equals method to see if two rectangles with the same hash codes are actually the same. That's why the Rectangle3D class needs good GetHashCode and Equals methods.)

If the rectangle is not already in the dictionary, the AddRectangle method adds it. (Note that the program doesn't add the rectangle to the 3D mesh yet.)

After it has generated all the data, the program uses the following code to loop through the Rectangle3D objects stored in the dictionary.

// Draw the rectangles. foreach (Rectangle3D rect in RectanglesMade.Keys) DrawRectangle(mesh, rect);

The following code shows the DrawRectangle method.

private void DrawRectangle(MeshGeometry3D mesh, Rectangle3D rect) { // Create the rectangle's triangles. AddTriangle(mesh, rect.Points[0], rect.Points[1], rect.Points[2]); AddTriangle(mesh, rect.Points[0], rect.Points[2], rect.Points[3]); }

This method simply calls the AddTriangle method used by the previous version of the program twice to create the two triangles that make up the rectangle.

Menger Sponge Fractal Results

That's a lot of work, so you may be wondering whether it was worth the effort. It should draw fewer rectangles (and therefore triangles), but it's a lot more complicated than the previous version, so you might think it will take longer to build the sponge data.

In fact, this version of the program does build the sponge more quickly than the previous version. (I think that's because it doesn't need to add data to the mesh's point and triangle index collections.) On my computer, the original version of the program takes about 5.10 seconds to build a level 5 sponge, but this version takes only 4.05 seconds.

That's a modest time savings, but it's even more important that this version draws fewer triangles. That saves memory and makes rendering faster. On my computer, the original version's level 5 sponge contains so many triangles that it cannot rotate freely without a noticeable lag. The new version can (although it seems to be near its limit). That means this kind of WPF program can display about 600,000 triangles and provide reasonable animation performance, at least on my computer.

The following table shows the number of points and triangles used by the program with and without the dictionary.

	w/o Dictionary	w/Dictionary	Data Saved
Level 1 Points	36	36	0%
Level 1 Triangles	12	12	0%
Level 2 Points	720	432	40%
Level 2 Triangles	240	144	40%
Level 3 Points	14,400	6,336	56%
Level 3 Triangles	4,800	2,112	56%
Level 4 Points	288,000	108,288	62.4%
Level 4 Triangles	96,000	36,096	62.4%
Level 5 Points	5,760,000	2,018,304	64.96%
Level 5 Triangles	1,920,000	672,768	64.96%

In the sponge with the most recursion, the program saves almost two thirds of the data. It's a lot of work, but it's worth it to be able to render the sponge so quickly.

Download the example to experiment with it and to see additional details.