+2

Is there a way to create extruded 3d solid from planar polygon?

Anonymous 10 years ago 0
This discussion was imported from CodePlex

luanshixia wrote at 2013-03-02 03:35:

I am using HelixToolkit to create a simple city data visualization app. I need to extrude building plans from AutoCAD dwg file. ExtrudedVisual3D only result the side surface, without caps.

Rossie wrote at 2013-03-04 01:06:

Hi I had a similar requirement - but i had caps. The way I achieved it was to find the border edges of the polygon(s) and extrude them along the Z axis. But I implemented my own FindBorderEdges() method - because Helix3D's version did not entirely suit. Mainly because I wanted a contiguous list of edges - (Helix3D will put the output edges in the same sequence as the input edges - meaning that they may/may not be a contiguous list) I also wanted them in a particular winding order. I'll post my implementation - that might help you. (and perhaps the guys developing the Helix3D devs might want to use this code as well) I'll just paste in the main methods to do the work - i made a class called MeshGeometryHelper2. Let me know if i have missed anything - you might have to fiddle the source to fit your purpose.
        public static List<int> FindBorderEdges(MeshGeometry3D mesh)
        {
            var dict = new Dictionary<ulong, int>();

            for (int i = 0; i < mesh.TriangleIndices.Count / 3; i++)
            {
                int i0 = i * 3;
                for (int j = 0; j < 3; j++)
                {
                    int index0 = mesh.TriangleIndices[i0 + j];
                    int index1 = mesh.TriangleIndices[i0 + (j + 1) % 3];
                    int minIndex = Math.Min(index0, index1);
                    int maxIndex = Math.Max(index1, index0);
                    ulong key = CreateKey((UInt32)minIndex, (UInt32)maxIndex);
                    if (dict.ContainsKey(key))
                    {
                        dict[key] = dict[key] + 1;
                    }
                    else
                    {
                        dict.Add(key, 1);
                    }
                }
            }

            var edges = new List<int>();
            foreach (var kvp in dict)
            {
                // find edges only used by 1 triangle
                if (kvp.Value == 1)
                {
                    uint i0, i1;
                    ReverseKey(kvp.Key, out i0, out i1);
                    edges.Add((int)i0);
                    edges.Add((int)i1);
                }
            }

            var borderPoints = new List<Point>();
            mesh.Positions.ToList().ForEach(p => borderPoints.Add(new Point(p.X, p.Y)));

            var result = OrganizeEdges(edges, borderPoints);
            return result;
        }


        private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
        {
            var visited = new Dictionary<int, bool>();
            var edgeList = new List<int>();
            var resultList = new List<int>();
            var nextIndex = -1;
            while (resultList.Count < edges.Count)
            {
                if (nextIndex < 0)
                {
                    for (int i = 0; i < edges.Count; i += 2)
                    {
                        if (!visited.ContainsKey(i))
                        {
                            nextIndex = edges[i];
                            break;
                        }
                    }
                }

                for (int i = 0; i < edges.Count; i += 2)
                {
                    if (visited.ContainsKey(i))
                        continue;

                    int j = i + 1;
                    
                    int k = -1;
                    if (edges[i] == nextIndex)
                        k = j;
                    else if (edges[j] == nextIndex)
                        k = i;

                    if (k >= 0)
                    {
                        var edge = edges[k];
                        visited[i] = true;
                        edgeList.Add(nextIndex);
                        edgeList.Add(edge);
                        nextIndex = edge;
                        i = 0;
                    }
                }

                // calculate winding order - then add to final result.
                var borderPoints = new List<Point>();
                edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
                var winding = CalculateWindingOrder(borderPoints);
                if (winding > 0)
                    edgeList.Reverse();

                resultList.AddRange(edgeList);
                edgeList = new List<int>();
                nextIndex = -1;
            }

            return resultList;
        }


        public static MeshGeometry3D Extrude(MeshGeometry3D surface, double z)
        {
            var borderIndexes = MeshGeometryHelper2.FindBorderEdges(surface);
            var borderPoints = new List<Point3D>();
            borderIndexes.ToList().ForEach(bi => borderPoints.Add(surface.Positions[bi]));

            var topPoints = borderPoints.ToList();
            var botPoints = borderPoints.Select(p => new Point3D(p.X, p.Y, p.Z + z)).ToList();
            
            var allPoints = new List<Point3D>();
            var allIndexes = new List<int>();
            var allNormals = new List<Vector3D>();

            // sides.
            allPoints.AddRange(topPoints);
            allPoints.AddRange(botPoints);

            for (int i = 0; i < topPoints.Count; i +=2)
            {
                int j = (i + 1) % topPoints.Count;

                allIndexes.Add(i);
                allIndexes.Add(j);
                allIndexes.Add(topPoints.Count + j);
                allIndexes.Add(topPoints.Count + j);
                allIndexes.Add(topPoints.Count + i);
                allIndexes.Add(i);

                var a = allPoints[i].ToVector3D();
                var b = allPoints[j].ToVector3D();
                var c = allPoints[topPoints.Count + j].ToVector3D();

                var n0 = b.Subtract(a).Cross(c.Subtract(a)).Unit();
                allNormals.Add(n0);
                allNormals.Add(n0);
                allNormals.Add(n0);
                allNormals.Add(n0);
            }

            var surfaceNormals = new List<Vector3D>();
            if (surface.Normals == null)
                surface.TriangleIndices.ToList().ForEach(i => surfaceNormals.Add(new Vector3D(0, 0, 1)));

            // top
            var count = allPoints.Count;
            var topSurfacePoints = surface.Positions.Select(p => new Point3D(p.X, p.Y, p.Z + z)).ToList();
            var topNormals = surfaceNormals.ToList();
            allPoints.AddRange(topSurfacePoints);
            allNormals.AddRange(topNormals);
            var topSurfaceIndexes = surface.TriangleIndices.Select(i => count + i).ToList();
            AddTriangleIndexes(topSurfaceIndexes, allIndexes, false);

            // bottom
            count = allPoints.Count;
            var botSurfacePoints = surface.Positions.ToList();
            var botNormals = surfaceNormals.Select(n => n.Flip()).ToList();
            allPoints.AddRange(botSurfacePoints);
            allNormals.AddRange(botNormals);
            var botSurfaceIndexes = surface.TriangleIndices.Select(i => count + i).ToList();
            AddTriangleIndexes(botSurfaceIndexes, allIndexes, true);

            var mesh = new Mesh3D(allPoints, allIndexes);
            var meshGeom = mesh.ToMeshGeometry3D();
            meshGeom.Normals = new Vector3DCollection(allNormals);

            if (z < 0) 
                ReverseWinding(meshGeom);

            var simple = Simplify(meshGeom);
            return simple;
        }

        private static void AddTriangleIndexes(List<int> triangleIndices, List<int> allIndexes, bool reverseWindingOrder)
        {
            for (int i = 0; i < triangleIndices.Count; i += 3)
            {
                var i0 = triangleIndices[i + 0];
                var i1 = triangleIndices[i + 1];
                var i2 = triangleIndices[i + 2];
                if (reverseWindingOrder)
                    allIndexes.AddRange(new[] { i2, i1, i0 });
                else
                    allIndexes.AddRange(new[] { i0, i1, i2 });
            }
        }

        public static void ReverseWinding(MeshGeometry3D mesh)
        {
            var indices = mesh.TriangleIndices.ToList();
            var flippedIndices = new List<int>();
            AddTriangleIndexes(indices, flippedIndices, true);
            mesh.TriangleIndices = new System.Windows.Media.Int32Collection(flippedIndices);
        }

       /// <summary>
        /// returns 1 for CW, -1 for CCW, 0 for unknown.
        /// </summary>
        public static int CalculateWindingOrder(IList<Point> points)
        {
            // the sign of the 'area' of the polygon is all we are interested in.
            var area = CalculateSignedArea(points);
            if (area < 0.0)
                return 1;
            else if (area > 0.0)
                return -1;        
            return 0; // error condition - not even verts to calculate, non-simple poly, etc.
        }

        public static double CalculateSignedArea(IList<Point> points)
        {
            double area = 0.0;
            for (int i = 0; i < points.Count; i++)
            {
                int j = (i + 1) % points.Count;
                area += points[i].X * points[j].Y;
                area -= points[i].Y * points[j].X;
            }
            area /= 2.0;

            return area;
        }