BLOG.CSHARPHELPER.COM

Draw a more efficient three-dimensional Menger sponge fractal using a dictionary, WPF, XAML, and C#

The example Draw a three-dimensional Menger sponge fractal using WPF, XAML, and C# shows how to build a Menger sponge. That example recursively chops up cubes 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 face should be drawn.

This example uses a Dictionary to avoid drawing those shared faces. It 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:

  1. 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.
  2. A Rectangle3D class to represent rectangles. If two rectangles have the same approximate points, even if they are in different orders, then the two rectangles should be regarded as the same rectangle.
  3. A Dictionary holding Rectangle3D objects so it's easy to tell if the same face is being drawn twice.
I think this is a pretty interesting example. Of course I like tricky algorithms. That's part of the reason I wrote my latest book, Essential Algorithms: A Practical Approach to Computer Algorithms. It 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 use this class to compare points, it 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 should represent the three points that make up a rectangle. It should also allow the program to compare to 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 without worrying about their 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 ordering makes it easier to tell if the 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.

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. (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 to create the two triangles that make up the rectangle.

Results

That's a lot of work, so you may be wondering whether it was worth the effort. It should draw fewer triangles but it's 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 actually builds 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.

It is 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 is cannot rotate freely without noticeable lag. The new version can (although it seems near the 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.


Level 1 Level 2 Level 3 Level 4 Level 5

Points Triangles Points Triangles Points Triangles Points Triangles Points Triangles
w/o Dictionary 36 12 720 240 14,400 4,800 288,000 96,000 5,760,000 1,920,000
w Dictionary 36 12 432 144 6,336 2,112 108,288 36,096 2,018,304 672,768
Data Saved 0% 40% 56% 62.4% 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.

   

Draw a three-dimensional Menger sponge fractal using WPF, XAML, and C#

The algorithm for building a Menger sponge is simple in principle. Start with a cube. If you haven't yet reached the desired level of recursion, divide the cube into 27 sub-cubes and discard the 7 that don't touch any of the main cube's edges. Then recursively apply the method to the remaining 20 sub-cubes.

The following code shows the recursive MakeSponge method that this program uses.

// Make a Menger sponge.
private void MakeSponge(MeshGeometry3D mesh, double xmin, double xmax,
    double ymin, double ymax, double zmin, double zmax, int depth)
{
    // See if this is depth 1.
    if (depth == 1)
    {
        // Just make a cube.
        AddCube(mesh, xmin, xmax, ymin, ymax, zmin, zmax);
    }
    else
    {
        // Divide the cube.
        double dx = (xmax - xmin) / 3.0;
        double dy = (ymax - ymin) / 3.0;
        double dz = (zmax - zmin) / 3.0;
        for (int ix = 0; ix < 3; ix++)
        {
            for (int iy = 0; iy < 3; iy++)
            {
                if ((ix == 1) && (iy == 1)) continue;
                for (int iz = 0; iz < 3; iz++)
                {
                    if ((iz == 1) && ((ix == 1) || (iy == 1))) continue;
                    MakeSponge(mesh,
                        xmin + dx * ix, xmin + dx * (ix + 1),
                        ymin + dy * iy, ymin + dy * (iy + 1),
                        zmin + dz * iz, zmin + dz * (iz + 1),
                        depth - 1);
                }
            }
        }
    }
}

If the remaining depth of recursion is 1, the method calls AddCube to draw the current cube, and the method is done. (The AddCube method simply adds 6 rectangles to make a cube. It's straightforward so it isn't shown here. Download the example to see how it works.)

If the remaining depth of recursion is greater than 1, the method calculates the dimensions of the cube's 27 sub-cubes. It loops through the possible cubes and calls itself recursively for those that aren't in the middle of the sub-cubes in the X, Y, or Z direction.

That's all there is to it. Like many recursive fractals, the code is remarkably short. It's also not too confusing, although that's not true of all short programs that draw fractals.

A much harder question is whether there is an easy way to not draw faces of cubes that lie inside the fractal. For example, if two cubes sit side-by-side, then you don't need to draw their common faces. These fractals contain a LOT of faces, so the potential savings could be significant.

For more information on Menger sponges, see:

My book Essential Algorithms: A Practical Approach to Computer Algorithms describes a lot of other interesting algorithms including some two-dimensional recursive algorithms. For more information including a table of contents, go to the book's Wiley web page.

   

Use segments to draw arrows in a 3D model using WPF and XAML

The example Draw improved 3D "line segments" using WPF and XAML showed how to draw thin rectangular boxes to represent three-dimensional line segments. This example uses that technique to draw arrows.

The following code shows the AddArrow extension method that adds an arrow to a MeshGeometry3D object.


// Make an arrow.
public static void AddArrow(this MeshGeometry3D mesh,
    Point3D point1, Point3D point2, Vector3D up,
    double barb_length)
{
    // Make the shaft.
    AddSegment(mesh, point1, point2, 0.05, true);

    // Get a unit vector in the direction of the segment.
    Vector3D v = point2 - point1;
    v.Normalize();

    // Get a perpendicular unit vector in the plane of the arrowhead.
    Vector3D perp = Vector3D.CrossProduct(v, up);
    perp.Normalize();

    // Calculate the arrowhead end points.
    Vector3D v1 = ScaleVector(-v + perp, barb_length);
    Vector3D v2 = ScaleVector(-v - perp, barb_length);

    // Draw the arrowhead.
    AddSegment(mesh, point2, point2 + v1, up, 0.05);
    AddSegment(mesh, point2, point2 + v2, up, 0.05);
}

The method first calls AddSegment to create the arrow's shaft.

The "up" vector indicates a direction perpendicular to the plane in which the arrow's head should lie. The method uses Vector3D.CrossProduct to get a vector in that plane. It then adds and subtracts combinations of the vector in that plane and the shaft direction's unit vector to find new vectors pointing in the directions of the arrowhead's sides.

The picture on the right shows the vector math that builds the arrowhead's sides. The red segment on the top shows the arrow's shaft. The black vector v is a unit vector in the direction of the shaft. The black vector perp is the vector perpendicular to the shaft and the "up" vector.

On the lower left, the blue arrow shows the result of the vector equation -v + perp. On the lower right, the green arrow shows the result of the vector equation -v - perp. The program scales those vectors to the desired length and then adds them to the shaft's end point to create the arrowhead's barb segments.

The following code shows how the main program makes the X axis. It makes the other axes similarly.

MeshGeometry3D x_axis_mesh = new MeshGeometry3D();
x_axis_mesh.AddArrow(origin, new Point3D(axis_length, 0, 0),
    new Vector3D(0, 1, 0), arrowhead_length);
DiffuseMaterial x_axis_material = new DiffuseMaterial(Brushes.Red);
XAxisModel = new GeometryModel3D(x_axis_mesh, x_axis_material);
model_group.Children.Add(XAxisModel);

This code creates a new MeshGeometry3D object. It calls the mesh's AddArrow extension method, creates a red material for it, and uses the mesh and material to create a GeometryModel3D object. Finally it adds the model to the main model group's Children collection.

Download the example to see additional details.

   

Draw triangle vertex normals on a 3D model using WPF and XAML

The example Draw triangle surface normals on a 3D model using WPF and XAML shows how to draw a surface, wireframe, and triangle surface normals. This example adds vertex normals to that program. It uses the following code to create a MeshGeometry3D object holding segments showing vertex normals for an existing MeshGeometry3D object.


// Return a MeshGeometry3D representing this mesh's triangle normals.
public static MeshGeometry3D ToVertexNormals(this MeshGeometry3D mesh,
    double length, double thickness)
{
    // Copy existing vertex normals.
    Vector3D[] vertex_normals = new Vector3D[mesh.Positions.Count];
    for (int i = 0; i < mesh.Normals.Count; i++)
        vertex_normals[i] = mesh.Normals[i];

    // Calculate missing vetex normals.
    for (int vertex = mesh.Normals.Count; vertex < mesh.Positions.Count; vertex++)
    {
        Vector3D total_vector = new Vector3D(0, 0, 0);
        int num_triangles = 0;

        // Find the triangles that contain this vertex.
        for (int triangle = 0; triangle < mesh.TriangleIndices.Count; triangle += 3)
        {
            // See if this triangle contains the vertex.
            int vertex1 = mesh.TriangleIndices[triangle];
            int vertex2 = mesh.TriangleIndices[triangle + 1];
            int vertex3 = mesh.TriangleIndices[triangle + 2];
            if ((vertex1 == vertex) ||
                (vertex2 == vertex) ||
                (vertex3 == vertex))
            {
                // This triangle contains this vertex.
                // Calculate its surface normal.
                Vector3D normal = FindTriangleNormal(
                    mesh.Positions[vertex1],
                    mesh.Positions[vertex2],
                    mesh.Positions[vertex3]);

                // Add the new normal to the total.
                total_vector = new Vector3D(
                    total_vector.X + normal.X,
                    total_vector.Y + normal.Y,
                    total_vector.Z + normal.Z);
                num_triangles++;
            }
        }

        // Set the vertex's normal.
        if (num_triangles > 0)
            vertex_normals[vertex] = new Vector3D(
                total_vector.X / num_triangles,
                total_vector.Y / num_triangles,
                total_vector.Z / num_triangles);
    }

    // Make a mesh to hold the normals.
    MeshGeometry3D normals = new MeshGeometry3D();

    // Convert the normal vectors into segments.
    for (int i = 0; i < mesh.Positions.Count; i++)
    {
        // Set the normal vector's length.
        vertex_normals[i] = ScaleVector(vertex_normals[i], length);

        // Find the other end point.
        Point3D endpoint = mesh.Positions[i] + vertex_normals[i];

        // Create the segment.
        AddSegment(normals, mesh.Positions[i], endpoint, thickness);
    }

    return normals;
}

This method first creates an array of Vector3D objects to hold normals for all of the mesh's points. Then if the mesh includes normal data, it copies that data into the array.

If the mesh is missing normal data for any of its points, the program loops through those points. For each such point, the code loops through the TriangleIndices array to see which triangles use that point. The code calls the FindTriangleNormal method (described in the earlier post) to get all of the triangles' normals and averages them to create the vertex normal.

(This method of averaging triangle surface normals gives each triangle that contains the vertex the same weight. For example, if one side of the vertex has one big triangle and the other side has lots of little triangles, the little triangles will tend to overpower the big one. You could change that behavior, but I'm not sure how you would want to do that. I don't know what algorithm WPF uses if you don't specify vertex normals yourself.)

After it has calculated all of the vertex normals, the program loops through the normals and adds them to a MeshGeometry3D object for display.

   

Draw triangle surface normals on a 3D model using WPF and XAML

The example Draw a 3D wireframe model for a MeshGeometry3D using WPF and XAML shows how to draw a surface and a wireframe. This example adds surface normals to that program. It uses the following code to create a MeshGeometry3D object holding segments showing surface normals for an existing MeshGeometry3D object.


// Return a MeshGeometry3D representing this mesh's triangle normals.
public static MeshGeometry3D ToTriangleNormals(this MeshGeometry3D mesh,
    double length, double thickness)
{
    // Make a mesh to hold the normals.
    MeshGeometry3D normals = new MeshGeometry3D();

    // Loop through the mesh's triangles.
    for (int triangle = 0; triangle < mesh.TriangleIndices.Count; triangle += 3)
    {
        // Get the triangle's vertices.
        Point3D point1 = mesh.Positions[mesh.TriangleIndices[triangle]];
        Point3D point2 = mesh.Positions[mesh.TriangleIndices[triangle + 1]];
        Point3D point3 = mesh.Positions[mesh.TriangleIndices[triangle + 2]];

        // Make the triangle's normal
        AddTriangleNormal(mesh, normals,
            point1, point2, point3, length, thickness);
    }

    return normals;
}

The method simply creates a MeshGeometry3D object and then loops through the original mesh's triangles calling the following AddTriangleNormal method for each.

// Add a segment representing the triangle's normal to the normals mesh.
private static void AddTriangleNormal(MeshGeometry3D mesh,
    MeshGeometry3D normals, Point3D point1, Point3D point2, Point3D point3,
    double length, double thickness)
{
    // Get the triangle's normal.
    Vector3D n = FindTriangleNormal(point1, point2, point3);

    // Set the length.
    n = ScaleVector(n, length);

    // Find the center of the triangle.
    Point3D endpoint1 = new Point3D(
        (point1.X + point2.X + point3.X) / 3.0,
        (point1.Y + point2.Y + point3.Y) / 3.0,
        (point1.Z + point2.Z + point3.Z) / 3.0);

    // Find the segment's other end point.
    Point3D endpoint2 = endpoint1 + n;

    // Create the segment.
    AddSegment(normals, endpoint1, endpoint2, thickness);
}

This method calls the FindTriangleNormal method described shortly to find a vector normal to the triangle's surface. It averages the triangle's corners to find its "center." (There are other definitions of a triangle's center, but this is easy and probably good enough.) It then adds the normal vector to the "center" to get the other end point for the normal segment. Finally it calls AddSegment to add a segment showing the normal. (See earlier posts for information about the AddSegment method.)

The following code shows the FindTriangleNormal method.

// Calculate a triangle's normal vector.
public static Vector3D FindTriangleNormal(Point3D point1, Point3D point2, Point3D point3)
{
    // Get two edge vectors.
    Vector3D v1 = point2 - point1;
    Vector3D v2 = point3 - point2;

    // Get the cross product.
    Vector3D n = Vector3D.CrossProduct(v1, v2);

    // Normalize.
    n.Normalize();

    return n;
}

This method creates vectors representing the triangle's first and second edges. It then uses Vector3D.CrossProduct to find a vector perpendicular to the two edge vectors. If the triangle is outwardly oriented, then the vector points in the outward direction.

Download the example for additional details.

   

Draw a 3D wireframe model for a MeshGeometry3D using WPF and XAML

This program adds three features to previous examples. First, it creates a wireframe representing the triangles defined in a MeshGeometry3D. Second, it modifies earlier segment drawing methods so it can calculate its own "up" vector. Finally, it allows the user to show or hide different parts of the model.

Making the Wireframe

The example Draw 3D two interlocked tetrahedrons in a cage of "line segments" using WPF and XAML shows how to draw 3D "line segments" in WPF. This example uses that technique to draw a wireframe MeshGeometry3D corresponding to a MeshGeometry3D. The following ToWireFrame extension method extends the MeshGeometry3D class and returns a new MeshGeometry3D representing the original's wireframe model.


// Return a MeshGeometry3D representing this mesh's wireframe.
public static MeshGeometry3D ToWireframe(this MeshGeometry3D mesh, double thickness)
{
    // Make a dictionary in case triangles share segments
    // so we don't draw the same segment twice.
    Dictionary<int, int> already_drawn = new Dictionary<int, int>();

    // Make a mesh to hold the wireframe.
    MeshGeometry3D wireframe = new MeshGeometry3D();

    // Loop through the mesh's triangles.
    for (int triangle = 0; triangle < mesh.TriangleIndices.Count; triangle += 3)
    {
        // Get the triangle's corner indices.
        int index1 = mesh.TriangleIndices[triangle];
        int index2 = mesh.TriangleIndices[triangle + 1];
        int index3 = mesh.TriangleIndices[triangle + 2];

        // Make the triangle's three segments.
        AddTriangleSegment(mesh, wireframe, already_drawn, index1, index2, thickness);
        AddTriangleSegment(mesh, wireframe, already_drawn, index2, index3, thickness);
        AddTriangleSegment(mesh, wireframe, already_drawn, index3, index1, thickness);
    }

    return wireframe;
}

The basic idea is to create "line segments" to represent each triangle's three edges. However, each edge could be shared by other triangles. To avoid drawing the same edge twice, the ToWireframe method uses a Dictionary<int, int> to hold IDs representing the edges. The AddTriangleSegment method described shortly performs the actual check.

The ToWireframe method loops through the original mesh's TriangleIndices collection looking at triples of indices. Each triple holds the indices of the points that make up a triangle. For each triangle, the method calls the following AddTriangleSegment method three times, passing it the indices of the points that make up the triangle's edges.

// Add the triangle's three segments.
private static void AddTriangleSegment(MeshGeometry3D mesh,
    MeshGeometry3D wireframe, Dictionary<int, int> already_drawn,
    int index1, int index2, double thickness)
{
    // Get a unique ID for a segment connecting the two points.
    if (index1 > index2)
    {
        int temp = index1;
        index1 = index2;
        index2 = temp;
    }
    int segment_id = index1 * mesh.Positions.Count * index2;

    // If we've already added this segment for
    // another triangle, do nothing.
    if (already_drawn.ContainsKey(segment_id)) return;
    already_drawn.Add(segment_id, segment_id);

    // Create the segment.
    AddSegment(wireframe, mesh.Positions[index1], mesh.Positions[index2], thickness);
}

The AddTriangleSegment method first determines whether the edge has already been added to the wireframe model. To do that, it calculates the edge's ID. If the original mesh contains NumPoints vertices and the edge's points have indices index1 and index2 where index1 < index2, then the ID is index1 * NumPoints + index2. This scheme guarantees that each edge has a distinct ID in the mesh.

If the edge's ID is already in the dictionary, the segment has been added to the wireframe model already so the method exits.

If the segment has not yet been added to the model, the method calls the AddSegment method to create it. It then adds the edge's ID to the dictionary so it won't be added again.

To create the wireframe, the main program simply calls the surface mesh object's ToWireframe extension method, passing it the thickness the wireframe segments should have. It then creates the wireframe's material and GeometryModel3D, and adds the result to the main model group's Children collection as shown in the following code.

MeshGeometry3D wireframe = mesh.ToWireframe(0.03);
DiffuseMaterial wireframe_material = new DiffuseMaterial(Brushes.Red);
WireframeModel = new GeometryModel3D(wireframe, wireframe_material);
model_group.Children.Add(WireframeModel);

Calculating "Up" Vectors

An earlier post explained how to make an AddSegment method that creates a thin box that can represent a line segment in 3D WPF programs. That method required you to include an "up" vector. The AddSegment method made the sides of the thin box parallel to that vector and to the segment's vector.

That was convenient for the previous example where the segments were parallel to the X, Y, and Z axes and it was easy to pick perpendicular "up" vectors. Sometimes, however, you don't really care which direction is "up." For this program, I added the following overloaded version of AddSegment that doesn't require an "up" vector.

public static void AddSegment(MeshGeometry3D mesh,
    Point3D point1, Point3D point2, double thickness, bool extend)
{
    // Find an up vector that is not colinear with the segment.
    // Start with a vector parallel to the Y axis.
    Vector3D up = new Vector3D(0, 1, 0);

    // If the segment and up vector point in more or less the
    // same direction, use an up vector parallel to the X axis.
    Vector3D segment = point2 - point1;
    segment.Normalize();
    if (Math.Abs(Vector3D.DotProduct(up, segment)) > 0.9)
        up = new Vector3D(1, 0, 0);

    // Add the segment.
    AddSegment(mesh, point1, point2, up, thickness, extend);
}

The only requirement for the "up" vector is that it can't be parallel to the segment being drawn. This method starts with an "up" vector that is parallel to the Y axis. It then uses the Vector3D class's DotProduct method to calculate the dot product between the normalized segment and the "up" vector.

The dot product of two vectors equals the product of the lengths of the vectors and the cosine of the angle between them. In this example, the vectors have length 1, so the result is simply the cosine of the angle. If the cosine is greater than 0.9 (or less than -0.9), then angle between the segment and the "up" vector is small (or offset 180 degrees from a small value). That means the segment and "up" vector point in more or less the same direction (or more or less in opposite directions). In that case, the method uses an "up" vector parallel to the X axis so it doesn't point more or less where the segment does. That ensures that the two are not parallel, as desired.

After finding an acceptable "up" vector, the AddSegment method calls the earlier version of itself, passing it the "up" vector.

Showing and Hiding Models

When you click one of the program's CheckBoxes, the program displays the surface, the wireframe, or both. In order to display the models when needed, the program uses the following code to declare variables to hold the surface and wireframe models at the class level.

// The surface's model.
private GeometryModel3D SurfaceModel;

// The wireframe's model.
private GeometryModel3D WireframeModel;

When you click a CheckBox, the following event handler executes.

// Show and hide the appropriate GeometryModel3Ds.
private void chkContents_Click(object sender, RoutedEventArgs e)
{
    // Remove the GeometryModel3Ds.
    for (int i = MainModel3Dgroup.Children.Count - 1; i >= 0; i--)
    {
        if (MainModel3Dgroup.Children[i] is GeometryModel3D)
            MainModel3Dgroup.Children.RemoveAt(i);
    }

    // Add the selected GeometryModel3Ds.
    if ((SurfaceModel != null) && ((bool)chkSurface.IsChecked))
        MainModel3Dgroup.Children.Add(SurfaceModel);
    if ((WireframeModel != null) && ((bool)chkWireframe.IsChecked))
        MainModel3Dgroup.Children.Add(WireframeModel);
}

This event handler first loops through the objects in the MainModel3Dgroup.Children and removes any that are GeometryModel3D objects. (The other objects in this example are lights.)

The event handler then adds the selected GeometryModel3D objects to the MainModel3Dgroup.Children collection so they are drawn.

   

Draw improved 3D "line segments" using WPF and XAML

The example Draw 3D two interlocked tetrahedrons in a cage of "line segments" using WPF and XAML shows how to draw a skinny rectangular prism to represent line segments. If you make the prisms thick enough, you can see that they don't line up well at their corners. (See the picture on the left side.)

This example uses the following AddSegment method to extend prisms slightly so segments that share an end point overlap by the size of their thickness. That makes them line up nicely. (At least when their prism sides are parallel. See the picture on the right side.) The new code is shown in blue.


private void AddSegment(MeshGeometry3D mesh,
    Point3D point1, Point3D point2, Vector3D up,
    bool extend)
{
    const double thickness = 0.25;

    // Get the segment's vector.
    Vector3D v = point2 - point1;

    if (extend)
    {
        // Increase the segment's length on both ends by thickness / 2.
        Vector3D n = ScaleVector(v, thickness / 2.0);
        point1 -= n;
        point2 += n;
    }

    // Get the scaled up vector.
    Vector3D n1 = ScaleVector(up, thickness / 2.0);

    // Get another scaled perpendicular vector.
    Vector3D n2 = Vector3D.CrossProduct(v, n1);
    n2 = ScaleVector(n2, thickness / 2.0);

    // Make a skinny box.
    // p1pm means point1 PLUS n1 MINUS n2.
    Point3D p1pp = point1 + n1 + n2;
    Point3D p1mp = point1 - n1 + n2;
    Point3D p1pm = point1 + n1 - n2;
    Point3D p1mm = point1 - n1 - n2;
    Point3D p2pp = point2 + n1 + n2;
    Point3D p2mp = point2 - n1 + n2;
    Point3D p2pm = point2 + n1 - n2;
    Point3D p2mm = point2 - n1 - n2;

    // Sides.
    AddTriangle(mesh, p1pp, p1mp, p2mp);
    AddTriangle(mesh, p1pp, p2mp, p2pp);

    AddTriangle(mesh, p1pp, p2pp, p2pm);
    AddTriangle(mesh, p1pp, p2pm, p1pm);

    AddTriangle(mesh, p1pm, p2pm, p2mm);
    AddTriangle(mesh, p1pm, p2mm, p1mm);

    AddTriangle(mesh, p1mm, p2mm, p2mp);
    AddTriangle(mesh, p1mm, p2mp, p1mp);

    // Ends.
    AddTriangle(mesh, p1pp, p1pm, p1mm);
    AddTriangle(mesh, p1pp, p1mm, p1mp);

    AddTriangle(mesh, p2pp, p2mp, p2mm);
    AddTriangle(mesh, p2pp, p2mm, p2pm);
}

If the extend parameter is true, the program creates a vector in the direction of the line segment that has length equal to half of the prism's width. It then moves the segment's end points that distance away from each other to extend the segment the correct amount.

The rest of the method is similar to the code used in the previous example.

   

Draw 3D two interlocked tetrahedrons in a cage of "line segments" using WPF and XAML

A noticeable omission in WPF's 3D tools is any way to draw line segments. That means you can't draw wireframe models, show surface normals, or draw other line-like features. You can use the CodePlex toolkit 3D Tools for the Windows Presentation Foundation, but I usually prefer to implement my own solutions if possible.

The CodePlex toolkit does this by drawing skinny rectangles. That works, but if the viewing angle is along the edge of a rectangle, it disappears. Another approach would be to draw two skinny perpendicular rectangles that are interlocked. Then you can see something from any angle unless you look at them end-on.

Instead ot taking those approaches, I decided to represent line segments with skinny rectangular prisms (boxes). The following code shows how the AddSegment method adds a prism to represent a line segment connecting two points.

// Make a thin rectangular prism between the two points.
private void AddSegment(MeshGeometry3D mesh, Point3D point1, Point3D point2, Vector3D up)
{
    const double thickness = 0.01;

    // Get the segment's vector.
    Vector3D v = point2 - point1;

    // Get the scaled up vector.
    Vector3D n1 = ScaleVector(up, thickness / 2.0);

    // Get another scaled perpendicular vector.
    Vector3D n2 = Vector3D.CrossProduct(v, n1);
    n2 = ScaleVector(n2, thickness / 2.0);

    // Make a skinny box.
    // p1pm means point1 PLUS n1 MINUS n2.
    Point3D p1pp = point1 + n1 + n2;
    Point3D p1mp = point1 - n1 + n2;
    Point3D p1pm = point1 + n1 - n2;
    Point3D p1mm = point1 - n1 - n2;
    Point3D p2pp = point2 + n1 + n2;
    Point3D p2mp = point2 - n1 + n2;
    Point3D p2pm = point2 + n1 - n2;
    Point3D p2mm = point2 - n1 - n2;

    // Sides.
    AddTriangle(mesh, p1pp, p1mp, p2mp);
    AddTriangle(mesh, p1pp, p2mp, p2pp);

    AddTriangle(mesh, p1pp, p2pp, p2pm);
    AddTriangle(mesh, p1pp, p2pm, p1pm);

    AddTriangle(mesh, p1pm, p2pm, p2mm);
    AddTriangle(mesh, p1pm, p2mm, p1mm);

    AddTriangle(mesh, p1mm, p2mm, p2mp);
    AddTriangle(mesh, p1mm, p2mp, p1mp);

    // Ends.
    AddTriangle(mesh, p1pp, p1pm, p1mm);
    AddTriangle(mesh, p1pp, p1mm, p1mp);

    AddTriangle(mesh, p2pp, p2mp, p2mm);
    AddTriangle(mesh, p2pp, p2mm, p2pm);
}

The code first gets a Vector3D representing the vector between the start and end points. It then uses the ScaleVector method (which is straightforward) to create a vector n1 in the "up" direction that has length half of the prism's thickness. It uses the Vactor3D class's CrossProduct method to get a new vector n2 perpendicular to the other two. (If you don't know what a vector cross product is, see WikiPedia.) It then scales vector n2 so it also has length equal to half the prism's desired thickness.

Next the method adds combinations of the vectors n1 and n2 to the segment's end points to get the corners of the prism. It then uses those points to add the necessary triangles to build the prism to the MeshGeometry3D.

This approach uses 12 triangles to represent the segment so it is more work than the CodePlex toolkit's approach, which uses only 2 triangles, but it gives a slightly better result. Still, if you need to draw 100,000 segments, you might want to use CodePlex's approach to save drawing time.

   

Draw two interlocked tetrahedrons defined by a cube using WPF and XAML

My post Platonic Solids Part 2: The tetrahedron shows how to calculate the locations of a tetrahedron's vertices. The example Draw two interlocked tetrahedrons using WPF, XAML, and C# uses those vertices to draw two interlocked tetrahedrons.


The vertex calculations are interesting (if you like geometry), but there's an easier way to find the vertices of two interlocked tetrahedrons. You can use the corners of a cube to define the vertices of two interlocked tetrahedrons as shown in the picture on the right.

Much of this example is similar to Draw two interlocked tetrahedrons using WPF, XAML, and C# except it uses the following code to define its tetrahedrons' vertices and faces.

<!-- Tetrahedron 1 -->
...
<MeshGeometry3D 
Positions="
     1, 1, 1    -1,-1, 1     1,-1,-1
     1, 1, 1    -1, 1,-1    -1,-1, 1
     1, 1, 1     1,-1,-1    -1, 1,-1
    -1,-1, 1    -1, 1,-1     1,-1,-1
"
TriangleIndices="
     0  1  2     3  4  5
     6  7  8     9 10 11
"/>
...

<!-- Tetrahedron 2 -->
...
<MeshGeometry3D 
Positions="
    -1,-1,-1    -1, 1, 1     1, 1,-1
    -1,-1,-1     1,-1, 1    -1, 1, 1
    -1,-1,-1     1, 1,-1     1,-1, 1
     1,-1, 1     1, 1,-1    -1, 1, 1
"
TriangleIndices="
     0  1  2     3  4  5
     6  7  8     9 10 11
"/>
...

If you look carefully at the vertex coordinates, you can see where they lie on the unit cube. The program uses a ScaleTransform3D to scale the coordinates by a factor of 2.5 in the X, Y, and Z directions to make the tetrahedrons fill the viewing area nicely. Download the example for additional details.

   

Draw a 3D surface overlaid with a shaded altitude map using WPF and C#

The example Draw a 3D surface overlaid with a grid using WPF and C# explains how to overlay an image on a three-dimensional surface. This example does something similar. Instead of simply using an existing image containing a grid, however, it generates an image that is shaded to show the surface's height.

The following CreateAltitudeMap method generates the texture bitmap.

// Create the altitude map texture bitmap.
private void CreateAltitudeMap()
{
    // Calculate the function's value over the area.
    const int xwidth = 512;
    const int zwidth = 512;
    const double dx = (xmax - xmin) / xwidth;
    const double dz = (zmax - zmin) / zwidth;
    double[,] values = new double[xwidth, zwidth];
    for (int ix = 0; ix < xwidth; ix++)
    {
        double x = xmin + ix * dx;
        for (int iz = 0; iz < zwidth; iz++)
        {
            double z = zmin + iz * dz;
            values[ix, iz] = F(x, z);
        }
    }

    // Get the upper and lower bounds on the values.
    var get_values =
        from double value in values
        select value;
    double ymin = get_values.Min();
    double ymax = get_values.Max();

    // Make the BitmapPixelMaker.
    BitmapPixelMaker bm_maker = new BitmapPixelMaker(xwidth, zwidth);

    // Set the pixel colors.
    for (int ix = 0; ix < xwidth; ix++)
    {
        for (int iz = 0; iz < zwidth; iz++)
        {
            byte red, green, blue;
            MapRainbowColor(values[ix, iz], ymin, ymax,
                out red, out green, out blue);
            bm_maker.SetPixel(ix, iz, red, green, blue, 255);
        }
    }

    // Convert the BitmapPixelMaker into a WriteableBitmap.
    WriteableBitmap wbitmap = bm_maker.MakeBitmap(96, 96);

    // Save the bitmap into a file.
    wbitmap.Save("Texture.png");
}

The method starts by calculating the surface function's value over the area being drawn. It calculates a value for each pixel in the image it will create, in this case a 512 × 512 pixel image. The code then uses the LINQ Min and Max methods to get the largest and smallest values in the array.

The code then makes a BitmapPixelMaker object. (See this post.) It loops over the pixels in the image and uses the corresponding function value to determine a color for the pixel. The code uses the MapRainbowColor method (described shortly) to map each function value to an appropriate color.

The method finishes by calling the BitmapPixelMaker object's MakeBitmap method to create a WriteableBitmap, and then using the bitmap's Save extension method to save the result into a file. (See this post.)

The MapRainbowColor method uses the following code to map a value between given bounds to a color.

// Map a value to a rainbow color.
private void MapRainbowColor(double value, double min_value, double max_value,
    out byte red, out byte green, out byte blue)
{
    // Convert into a value between 0 and 1023.
    int int_value = (int)(1023 * (value - min_value) / (max_value - min_value));

    // Map different color bands.
    if (int_value < 256)
    {
        // Red to yellow. (255, 0, 0) to (255, 255, 0).
        red = 255;
        green = (byte)int_value;
        blue = 0;
    }
    else if (int_value < 512)
    {
        // Yellow to green. (255, 255, 0) to (0, 255, 0).
        int_value -= 256;
        red = (byte)(255 - int_value);
        green = 255;
        blue = 0;
    }
    else if (int_value < 768)
    {
        // Green to aqua. (0, 255, 0) to (0, 255, 255).
        int_value -= 512;
        red = 0;
        green = 255;
        blue = (byte)int_value;
    }
    else
    {
        // Aqua to blue. (0, 255, 255) to (0, 0, 255).
        int_value -= 768;
        red = 0;
        green = (byte)(255 - int_value);
        blue = 255;
    }
}

The code first scales the value so it ranges from 0 to 1023. Depending on whether the value is the range 0 - 255, 256 - 511, 512 - 767, and 768 - 1023, the code converts the color into different parts of a rainbow.

The rest of the program is similar to the previous one that maps a grid onto the surface. The following code shows how this example uses the texture image saved by the CreateAltitudeMap method to create the surface's material.

// Make the surface's material using an image brush.
ImageBrush texture_brush = new ImageBrush();
texture_brush.ImageSource =
    new BitmapImage(new Uri("Texture.png", UriKind.Relative));
DiffuseMaterial surface_material = new DiffuseMaterial(texture_brush);

Download the example to see additional details.

   

Calendar

April 2014
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930

Subscribe


Blog Software
Blog Software