Mesh outline correction

2025-01-30 21:19 UTC gpt-4o Open in ChatGPT ↗

You

this algorithm for mesh outline is not correct. fix the bugs

///

/// Extracts the boundary edges of the mesh and orders them into a continuous outline. ///

private List GetOrderedMeshOutline(Mesh mesh) { var edgeSet = new HashSet(); var orderedOutline = new List();

    var triangles = mesh.triangles;
    var vertices = mesh.vertices;

    // Step 1: Find boundary edges (edges that belong to only one triangle)
    for (int i = 0; i < triangles.Length; i += 3)
    {
        Edge[] edges =
        {
            new Edge(triangles[i], triangles[i + 1]),
            new Edge(triangles[i + 1], triangles[i + 2]),
            new Edge(triangles[i + 2], triangles[i])
        };

        foreach (var edge in edges)
        {
            if (!edgeSet.Add(edge))
                edgeSet.Remove(edge); // If it's already in, remove it (shared edges are not boundaries)
        }
    }

    // Step 2: Order the boundary edges into a continuous path
    if (edgeSet.Count > 0)
    {
        var firstEdge = edgeSet.First();
        orderedOutline.Add(vertices[firstEdge.V1]);
        orderedOutline.Add(vertices[firstEdge.V2]);

        edgeSet.Remove(firstEdge);

        while (edgeSet.Count > 0)
        {
            Edge nextEdge = edgeSet.FirstOrDefault(e => e.V1 == firstEdge.V2 || e.V2 == firstEdge.V2);
            if (!nextEdge.valid) break;

            orderedOutline.Add(vertices[nextEdge.V1 == firstEdge.V2 ? nextEdge.V2 : nextEdge.V1]);
            edgeSet.Remove(nextEdge);
            firstEdge = nextEdge;
        }
    }

    return orderedOutline;
}

ChatGPT

Here is the corrected version of your algorithm. The original code had a few issues:

1. Edge Hashing Issue: If Edge is a struct and doesn’t properly implement Equals and GetHashCode, HashSet operations will fail to identify duplicate edges correctly.
2. Edge Ordering Issue: The edge ordering logic assumes the first found edge is a good starting point, but it doesn’t guarantee a proper continuous path.
3. Unordered Edge Removal: The algorithm does not always ensure that the next edge in sequence exists, leading to broken outlines.

Fixes:

• Ensure Edge correctly defines Equals and GetHashCode.
• Use a dictionary to track adjacency for correct ordering.
• Improve ordering logic to ensure a continuous loop.

Here’s the fixed version:

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class MeshOutlineExtractor
{
    private struct Edge
    {
        public int V1, V2;

        public Edge(int v1, int v2)
        {
            V1 = Mathf.Min(v1, v2); // Ensure consistent ordering
            V2 = Mathf.Max(v1, v2);
        }

        public override bool Equals(object obj)
        {
            if (obj is Edge other)
                return V1 == other.V1 && V2 == other.V2;
            return false;
        }

        public override int GetHashCode()
        {
            return V1 * 31 + V2;
        }
    }

    /// <summary>
    /// Extracts the boundary edges of the mesh and orders them into a continuous outline.
    /// </summary>
    private List<Vector3> GetOrderedMeshOutline(Mesh mesh)
    {
        var edgeCount = new Dictionary<Edge, int>();
        var edgeAdjacency = new Dictionary<int, List<int>>();
        var orderedOutline = new List<Vector3>();

        var triangles = mesh.triangles;
        var vertices = mesh.vertices;

        // Step 1: Find boundary edges
        for (int i = 0; i < triangles.Length; i += 3)
        {
            Edge[] edges =
            {
                new Edge(triangles[i], triangles[i + 1]),
                new Edge(triangles[i + 1], triangles[i + 2]),
                new Edge(triangles[i + 2], triangles[i])
            };

            foreach (var edge in edges)
            {
                if (edgeCount.ContainsKey(edge))
                    edgeCount[edge]++;
                else
                    edgeCount[edge] = 1;
            }
        }

        // Step 2: Identify boundary edges
        var boundaryEdges = new List<Edge>();
        foreach (var kvp in edgeCount)
        {
            if (kvp.Value == 1) // Boundary edges appear only once
            {
                boundaryEdges.Add(kvp.Key);

                // Track adjacency (for ordering)
                if (!edgeAdjacency.ContainsKey(kvp.Key.V1))
                    edgeAdjacency[kvp.Key.V1] = new List<int>();
                if (!edgeAdjacency.ContainsKey(kvp.Key.V2))
                    edgeAdjacency[kvp.Key.V2] = new List<int>();

                edgeAdjacency[kvp.Key.V1].Add(kvp.Key.V2);
                edgeAdjacency[kvp.Key.V2].Add(kvp.Key.V1);
            }
        }

        // Step 3: Order edges into a continuous path
        if (boundaryEdges.Count > 0)
        {
            var startVertex = boundaryEdges[0].V1;
            var currentVertex = startVertex;
            int previousVertex = -1;

            do
            {
                orderedOutline.Add(vertices[currentVertex]);

                if (!edgeAdjacency.ContainsKey(currentVertex) || edgeAdjacency[currentVertex].Count == 0)
                    break;

                var nextVertex = edgeAdjacency[currentVertex].FirstOrDefault(v => v != previousVertex);
                previousVertex = currentVertex;
                currentVertex = nextVertex;

                // Remove used edge
                edgeAdjacency[previousVertex].Remove(currentVertex);
                edgeAdjacency[currentVertex].Remove(previousVertex);

            } while (currentVertex != startVertex && currentVertex != -1);
        }

        return orderedOutline;
    }
}

Summary of Fixes:

✅ Ensures edge consistency by always storing edges with the smaller index first.
✅ Uses a dictionary to track edge counts, correctly identifying boundary edges.
✅ Uses an adjacency list to correctly order boundary edges into a continuous path.
✅ Prevents broken outlines by ensuring continuous traversal of the outline.

This should now reliably extract and order the mesh outline correctly. 🚀