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\$

1 Answer 1

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\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .