4
\$\begingroup\$

I'm using THREEjs's exporter to export a 2D polygon plane. The resulting JSON gives me the vertices. I'm trying to properly order these vertices as to make the actual polygon shape, without luck.

Right: Default vertex order

Left: Actual order enter image description here enter image description here

I manually put the needed order together and found it to be this. 0,1,2,3,4,5,6,7,8,9,11,13,17,16,15,19,21,22,23,25,27,29,39,38,37,36,35,34,33,32,31,30,28,26,24,20,18,14,12,10 (element represents index in default order).

Is there a pattern to this ordering? Does the JSON file reveal more information on how to properly order it? Seems the only other information in there is the faces array. I do not understand how to read it or what it represents.

\$\endgroup\$
2
\$\begingroup\$

As you guessed, you can know the vertices order by checking the faces. To know how faces could be read, check this link.

Next follows an example (C#) on how it could be done (no errors checking).

public class Face
{
    static int TYPE_BITMASK_TRIANGLE_QUAD = 0;
    static int TYPE_BITMASK_FACE_MATERIAL = 1;
    static int TYPE_BITMASK_FACE_UV = 2;
    static int TYPE_BITMASK_FACE_VERTEX_UV = 3;
    static int TYPE_BITMASK_FACE_NORMAL = 4;
    static int TYPE_BITMASK_FACE_VERTEX_NORMAL = 5;
    static int TYPE_BITMASK_FACE_COLOR = 6;
    static int TYPE_BITMASK_FACE_VERTEX_COLOR = 7;

    private static string[] DATA_BLOCK_SEPARATOR = { ", " };
    private static char[] DATA_SEPARATOR = { ',' };

    private byte _typeBitmask;
    public bool HasMaterial = false;
    public bool HasFaceUv = false;
    public bool HasFaceVertexUv = false;
    public bool HasFaceNormal = false;
    public bool HasFaceVertexNormal = false;
    public bool HasFaceColor = false;
    public bool HasFaceVertexColor = false;

    public int VerticesAmount { get; private set; }
    public int[] VertexIndex;
    public int MaterialIndex;
    public int FaceUv;
    public int[] FaceVertexUv;
    public int FaceNormal;
    public int[] FaceVertexNormal;
    public int FaceColor;
    public int[] FaceVertexColor;

    private Face() : this(3) { }

    private Face(int verticesAmount)
    {
        this.VerticesAmount = verticesAmount;
        this._typeBitmask = (byte)(verticesAmount == 3 ? 0 : 1);
        this.VertexIndex = new int[verticesAmount];
        this.FaceVertexUv = new int[verticesAmount];
        this.FaceVertexNormal = new int[verticesAmount];
        this.FaceVertexColor = new int[verticesAmount];
    }

    public static Face Triangle()
    {
        return new Face(3);
    }

    public static Face Quad()
    {
        return new Face(4);
    }

    public Edge[] GetEdges()
    {
        return GetEdges(this);
    }

    public static Edge[] GetEdges(Face face)
    {
        Edge[] edges = new Edge[face.VerticesAmount];
        for (int i = 0; i < face.VerticesAmount - 1; i++)
        {
            edges[i] = new Edge(face.VertexIndex[i], face.VertexIndex[i + 1]);
        }
        edges[face.VerticesAmount - 1] = new Edge(face.VertexIndex[face.VerticesAmount - 1], face.VertexIndex[0]);
        return edges;
    }

    public static List<Face> Deserialize(string json)
    {
        // Split json string into data blocks
        string[] dataBlocks = json.Split(DATA_BLOCK_SEPARATOR, StringSplitOptions.None);

        // Set amount of vertices and types of data to read
        int verticesAmount;
        bool hasMaterial, hasFaceUv, hasFaceVertexUv, hasFaceNormal, hasFaceVertexNormal, hasFaceColor, hasFaceVertexColor;
        byte typeBitmask = byte.Parse(dataBlocks[0]);
        verticesAmount = IsBitSet(typeBitmask, TYPE_BITMASK_TRIANGLE_QUAD) ? 4 : 3;
        hasMaterial = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_MATERIAL);
        hasFaceUv = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_UV);
        hasFaceVertexUv = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_VERTEX_UV);
        hasFaceNormal = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_NORMAL);
        hasFaceVertexNormal = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_VERTEX_NORMAL);
        hasFaceColor = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_COLOR);
        hasFaceVertexColor = IsBitSet(typeBitmask, TYPE_BITMASK_FACE_VERTEX_COLOR);

        List<Face> faces = new List<Face>();
        Face face;
        int dataBlockIndex = 1;

        // Build Face instances until all data blocks parsed
        while (dataBlockIndex < dataBlocks.Length)
        {
            face = new Face(verticesAmount);
            face._typeBitmask = typeBitmask;
            face.HasMaterial = hasMaterial;
            face.HasFaceUv = hasFaceUv;
            face.HasFaceVertexUv = hasFaceVertexUv;
            face.HasFaceNormal = hasFaceNormal;
            face.HasFaceVertexNormal = hasFaceVertexNormal;
            face.HasFaceColor = hasFaceColor;
            face.HasFaceVertexColor = hasFaceVertexColor;

            // Parse vertices
            face.VertexIndex = ParseBlock(dataBlocks[dataBlockIndex]);
            dataBlockIndex++;

            // Parse other data, as needed
            if (hasMaterial)
            {
                face.MaterialIndex = int.Parse(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }
            if (hasFaceUv)
            {
                face.FaceUv = int.Parse(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }
            if (hasFaceVertexUv)
            {
                face.FaceVertexUv = ParseBlock(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }
            if (hasFaceNormal)
            {
                face.FaceNormal = int.Parse(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }
            if (hasFaceVertexNormal)
            {
                face.FaceVertexNormal = ParseBlock(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }
            if (hasFaceColor)
            {
                face.FaceColor = int.Parse(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }
            if (hasFaceVertexColor)
            {
                face.FaceVertexColor = ParseBlock(dataBlocks[dataBlockIndex]);
                dataBlockIndex++;
            }

            // Add the face to the resulting list
            faces.Add(face);
        }

        // Return the list
        return faces;
    }

    private static bool IsBitSet(int value, int position)
    {
        return (value & ( 1 << position )) == 0 ? false : true;
    }

    private static int[] ParseBlock(string dataBlock)
    {
        string[] data = dataBlock.Split(DATA_SEPARATOR);
        int[] result = new int[data.Length];
        for (int i = 0; i < data.Length; i++)
        {
            result[i] = int.Parse(data[i]);
        }
        return result;
    }

    public static List<int> GetOutline(List<Face> faces)
    {
        List<int> sortedVertices = new List<int>();
        Dictionary<long, Edge> edges = new Dictionary<long, Edge>();

        // Get the edges in the outline
        foreach (Face face in faces)
        {
            foreach (Edge edge in face.GetEdges())
            {
                if (edges.ContainsKey(edge.Id))
                {
                    // Remove any edge shared by 2 faces
                    edges.Remove(edge.Id);
                }
                else
                {
                    // Add new edges
                    edges.Add(edge.Id, edge);
                }
            }
        }

        // Assuming that at least 1 triangle will have 1 edge starting at vertex 0
        long firstEdgeId = edges.First(ed => (ed.Key & 0x7FFFFFFF00000000) == 0).Key;

        // Add the first edge's vertices to the resulting list
        Edge nextEdge = edges[firstEdgeId];
        sortedVertices.Add(nextEdge.A);
        int nextVertex = nextEdge.B;
        sortedVertices.Add(nextVertex);
        // Remove the edge from 
        edges.Remove(nextEdge.Id);

        // For all remaining edges
        while (edges.Count > 0)
        {
            // Search the next edge, sharing a vertex with last edge
            nextEdge = edges.First(ed => (ed.Key & 0x7FFFFFFF00000000) >> 32 == nextVertex).Value;
            // Add the new vertex to the resulting list
            sortedVertices.Add(nextVertex);
            // Remove the edge from remaining edges
            edges.Remove(nextEdge.Id);
            // Set the vertex to use in next search
            nextVertex = nextEdge.B;
        }

        // return the resulting list of vertices (sorted and ready for your use)
        return sortedVertices;
    }
}

public class Edge
{
    public int A;
    public int B;
    public long Id;

    public Edge(int a, int b)
    {
        this.A = a;
        this.B = b;
        this.Id = a << 32 + b;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.