Mesh Simplification (Again)

Heres a really simple mesh simplification routine. Its based on merging adjacent triangles that are nearly coplanar.

Simple as that really…..

 /// <summary>
        /// Reduce the vertex count by comparing the Normals and eliminating vertexes with the least difference in normals that share the same face. 
        /// </summary>
        /// <param name="vertexes">A list of vertex positions</param>
        /// <param name="fixedIndexes">List of indexes which indicate fixed vertexes which cannot be considered for removal - these are typically edge vertexes</param>
        /// <param name="normals">A list of Normals matching the list of Vertexes</param>
        /// <param name="faces">A list of the Faces which make up Triangles. </param>
        /// <param name="vertexReductionCount">The number of vertexes we want to reduce by</param>
        /// <returns>A list of vertex indexes identified that point to vertexes which are candidates for removal</returns>
        public List<int> Reduce(List<Vector3> vertexes, List<int> fixedIndexes, List<Vector3> normals, List<Face> faces, int vertexReductionCount)
            // List of vector indexes and their relative difference between their face normal and their vector normal
            Dictionary<int, Tuple<int,float>> vertexIndexSharpness = new Dictionary<int, Tuple<int,float>>();
            foreach(Face face in faces)
                if (!vertexIndexSharpness.ContainsKey(face.Vector0Index)) vertexIndexSharpness.Add(face.Vector0Index, new Tuple<int,float>(0,0));
                if (!vertexIndexSharpness.ContainsKey(face.Vector1Index)) vertexIndexSharpness.Add(face.Vector1Index, new Tuple<int, float>(0, 0));
                if (!vertexIndexSharpness.ContainsKey(face.Vector2Index)) vertexIndexSharpness.Add(face.Vector2Index, new Tuple<int, float>(0, 0));

                // Whats the difference between the Vertex Normal and the Face Normal
                float vector0NormalSharpness = Vector3.Cross(normals[face.Vector0Index], face.FaceNormal).Length();
                float vector1NormalSharpness = Vector3.Cross(normals[face.Vector1Index], face.FaceNormal).Length();
                float vector2NormalSharpness = Vector3.Cross(normals[face.Vector2Index], face.FaceNormal).Length();

                Tuple<int, float> existingData = vertexIndexSharpness[face.Vector0Index];
                vertexIndexSharpness[face.Vector0Index] = new Tuple<int, float>(existingData.Item1 + 1, existingData.Item2 + vector0NormalSharpness);

                existingData = vertexIndexSharpness[face.Vector1Index];
                vertexIndexSharpness[face.Vector1Index] = new Tuple<int, float>(existingData.Item1 + 1, existingData.Item2 + vector1NormalSharpness);

                existingData = vertexIndexSharpness[face.Vector2Index];
                vertexIndexSharpness[face.Vector2Index] = new Tuple<int, float>(existingData.Item1 + 1, existingData.Item2 + vector2NormalSharpness);


            HashSet<int> removalCandidates = new HashSet<int>();

            List<KeyValuePair<int, Tuple<int, float>>> sortedList = vertexIndexSharpness.Where(item => !fixedIndexes.Contains(item.Key)).OrderBy(item => item.Value.Item2).ToList();
            if(vertexReductionCount >= sortedList.Count)
                return removalCandidates.ToList();

            // Get the sharpness of the last one in the range.
            float lastItemSharpness = sortedList[vertexReductionCount-1].Value.Item2;
            foreach (int index in sortedList.Take(vertexReductionCount).Select(item => item.Key))
                // Dont allow a removal candidate that has only two faces - its likely to be an edge
                if (vertexIndexSharpness[index].Item1 > 2)
            // Now make sure we've added all the items that match the last sharpness, otherwise we'll get an arbitrary number of remaining triangles of exactly the sharpness we last got rid of, which is 
            // odd.
            foreach(int index in sortedList.Where(item => item.Value.Item2 == lastItemSharpness).Select(item => item.Key))
                if (vertexIndexSharpness[index].Item1 > 2)

            return removalCandidates.ToList();


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s