Cura/plugins/X3DReader/X3DReader.py

# Contributed by Seva Alekseyev <sevaa@nih.gov> with National Institutes of Health, 2016
# Cura is released under the terms of the LGPLv3 or higher.

from math import pi, sin, cos, sqrt

import numpy

from UM.Job import Job
from UM.Logger import Logger
from UM.Math.Matrix import Matrix
from UM.Math.Vector import Vector
from UM.Mesh.MeshBuilder import MeshBuilder
from UM.Mesh.MeshReader import MeshReader
from cura.Scene.CuraSceneNode import CuraSceneNode as SceneNode

MYPY = False
try:
    if not MYPY:
        import xml.etree.cElementTree as ET
except ImportError:
    import xml.etree.ElementTree as ET

# TODO: preserve the structure of scenes that contain several objects
# Use CADPart, for example, to distinguish between separate objects

DEFAULT_SUBDIV = 16 # Default subdivision factor for spheres, cones, and cylinders
EPSILON = 0.000001

class Shape:

    # Expects verts in MeshBuilder-ready format, as a n by 3 mdarray
    # with vertices stored in rows
    def __init__(self, verts, faces, index_base, name):
        self.verts = verts
        self.faces = faces
        # Those are here for debugging purposes only
        self.index_base = index_base
        self.name = name

class X3DReader(MeshReader):
    def __init__(self, application):
        super().__init__(application)
        self._supported_extensions = [".x3d"]
        self._namespaces = {}

    # Main entry point
    # Reads the file, returns a SceneNode (possibly with nested ones), or None
    def _read(self, file_name):
        try:
            self.defs = {}
            self.shapes = []

            tree = ET.parse(file_name)
            xml_root = tree.getroot()

            if xml_root.tag != "X3D":
                return None

            scale = 1000 # Default X3D unit it one meter, while Cura's is one millimeters
            if xml_root[0].tag == "head":
                for head_node in xml_root[0]:
                    if head_node.tag == "unit" and head_node.attrib.get("category") == "length":
                        scale *= float(head_node.attrib["conversionFactor"])
                        break
                xml_scene = xml_root[1]
            else:
                xml_scene = xml_root[0]

            if xml_scene.tag != "Scene":
                return None

            self.transform = Matrix()
            self.transform.setByScaleFactor(scale)
            self.index_base = 0

            # Traverse the scene tree, populate the shapes list
            self.processChildNodes(xml_scene)

            if self.shapes:
                builder = MeshBuilder()
                builder.setVertices(numpy.concatenate([shape.verts for shape in self.shapes]))
                builder.setIndices(numpy.concatenate([shape.faces for shape in self.shapes]))
                builder.calculateNormals()
                builder.setFileName(file_name)
                mesh_data = builder.build()

                # Manually try and get the extents of the mesh_data. This should prevent nasty NaN issues from
                # leaving the reader.
                mesh_data.getExtents()

                node = SceneNode()
                node.setMeshData(mesh_data)
                node.setSelectable(True)
                node.setName(file_name)

            else:
                return None

        except Exception:
            Logger.logException("e", "Exception in X3D reader")
            return None

        return node

    # ------------------------- XML tree traversal

    def processNode(self, xml_node):
        xml_node =  self.resolveDefUse(xml_node)
        if xml_node is None:
            return

        tag = xml_node.tag
        if tag in ("Group", "StaticGroup", "CADAssembly", "CADFace", "CADLayer", "Collision"):
            self.processChildNodes(xml_node)
        if tag == "CADPart":
            self.processTransform(xml_node) # TODO: split the parts
        elif tag == "LOD":
            self.processNode(xml_node[0])
        elif tag == "Transform":
            self.processTransform(xml_node)
        elif tag == "Shape":
            self.processShape(xml_node)


    def processShape(self, xml_node):
        # Find the geometry and the appearance inside the Shape
        geometry = appearance = None
        for sub_node in xml_node:
            if sub_node.tag == "Appearance" and not appearance:
                appearance = self.resolveDefUse(sub_node)
            elif sub_node.tag in self.geometry_importers and not geometry:
                geometry = self.resolveDefUse(sub_node)

        # TODO: appearance is completely ignored. At least apply the material color...
        if not geometry is None:
            try:
                self.verts = self.faces = [] # Safeguard
                self.geometry_importers[geometry.tag](self, geometry)
                m = self.transform.getData()
                verts = m.dot(self.verts)[:3].transpose()

                self.shapes.append(Shape(verts, self.faces, self.index_base, geometry.tag))
                self.index_base += len(verts)

            except Exception:
                Logger.logException("e", "Exception in X3D reader while reading %s", geometry.tag)

    # Returns the referenced node if the node has USE, the same node otherwise.
    # May return None is USE points at a nonexistent node
    # In X3DOM, when both DEF and USE are in the same node, DEF is ignored.
    # Big caveat: XML element objects may evaluate to boolean False!!!
    # Don't ever use "if node:", use "if not node is None:" instead
    def resolveDefUse(self, node):
        USE = node.attrib.get("USE")
        if USE:
            return self.defs.get(USE, None)

        DEF = node.attrib.get("DEF")
        if DEF:
            self.defs[DEF] = node
        return node

    def processChildNodes(self, node):
        for c in node:
            self.processNode(c)
            Job.yieldThread()

    # Since this is a grouping node, will recurse down the tree.
    # According to the spec, the final transform matrix is:
    # T * C * R * SR * S * -SR * -C
    # Where SR corresponds to the rotation matrix to scaleOrientation
    # C and SR are rather exotic. S, slightly less so.
    def processTransform(self, node):
        rot = readRotation(node, "rotation", (0, 0, 1, 0)) # (angle, axisVactor) tuple
        trans = readVector(node, "translation", (0, 0, 0)) # Vector
        scale = readVector(node, "scale", (1, 1, 1)) # Vector
        center = readVector(node, "center", (0, 0, 0)) # Vector
        scale_orient = readRotation(node, "scaleOrientation", (0, 0, 1, 0)) # (angle, axisVactor) tuple

        # Store the previous transform; in Cura, the default matrix multiplication is in place
        prev = Matrix(self.transform.getData()) # It's deep copy, I've checked

        # The rest of transform manipulation will be applied in place
        got_center = (center.x != 0 or center.y != 0 or center.z != 0)

        T = self.transform
        if trans.x != 0 or trans.y != 0 or trans.z != 0:
            T.translate(trans)
        if got_center:
            T.translate(center)
        if rot[0] != 0:
            T.rotateByAxis(*rot)
        if scale.x != 1 or scale.y != 1 or scale.z != 1:
            got_scale_orient = scale_orient[0] != 0
            if got_scale_orient:
                T.rotateByAxis(*scale_orient)
            # No scale by vector in place operation in UM
            S = Matrix()
            S.setByScaleVector(scale)
            T.multiply(S)
            if got_scale_orient:
                T.rotateByAxis(-scale_orient[0], scale_orient[1])
        if got_center:
            T.translate(-center)

        self.processChildNodes(node)
        self.transform = prev

    # ------------------------- Geometry importers
    # They are supposed to fill the self.verts and self.faces arrays, the caller will do the rest

    # Primitives

    def processGeometryBox(self, node):
        (dx, dy, dz) = readFloatArray(node, "size", [2, 2, 2])
        dx /= 2
        dy /= 2
        dz /= 2
        self.reserveFaceAndVertexCount(12, 8)

        # xz plane at +y, ccw
        self.addVertex(dx, dy, dz)
        self.addVertex(-dx, dy, dz)
        self.addVertex(-dx, dy, -dz)
        self.addVertex(dx, dy, -dz)
        # xz plane at -y
        self.addVertex(dx, -dy, dz)
        self.addVertex(-dx, -dy, dz)
        self.addVertex(-dx, -dy, -dz)
        self.addVertex(dx, -dy, -dz)

        self.addQuad(0, 1, 2, 3)   # +y
        self.addQuad(4, 0, 3, 7)   # +x
        self.addQuad(7, 3, 2, 6)   # -z
        self.addQuad(6, 2, 1, 5)   # -x
        self.addQuad(5, 1, 0, 4)   # +z
        self.addQuad(7, 6, 5, 4)  # -y

    # The sphere is subdivided into nr rings and ns segments
    def processGeometrySphere(self, node):
        r = readFloat(node, "radius", 0.5)
        subdiv = readIntArray(node, "subdivision", None)
        if subdiv:
            if len(subdiv) == 1:
                nr = ns = subdiv[0]
            else:
                (nr, ns) = subdiv
        else:
            nr = ns = DEFAULT_SUBDIV

        lau = pi / nr  # Unit angle of latitude (rings) for the given tesselation
        lou = 2 * pi / ns  # Unit angle of longitude (segments)

        self.reserveFaceAndVertexCount(ns*(nr*2 - 2), 2 + (nr - 1)*ns)

        # +y and -y poles
        self.addVertex(0, r, 0)
        self.addVertex(0, -r, 0)

        # The non-polar vertices go from x=0, negative z plane counterclockwise -
        # to -x, to +z, to +x, back to -z
        for ring in range(1, nr):
            for seg in range(ns):
                self.addVertex(-r*sin(lou * seg) * sin(lau * ring),
                          r*cos(lau * ring),
                          -r*cos(lou * seg) * sin(lau * ring))

        vb = 2 + (nr - 2) * ns  # First vertex index for the bottom cap

        # Faces go in order: top cap, sides, bottom cap.
        # Sides go by ring then by segment.

        # Caps
        # Top cap face vertices go in order: down right up
        # (starting from +y pole)
        # Bottom cap goes: up left down (starting from -y pole)
        for seg in range(ns):
            self.addTri(0, seg + 2, (seg + 1) % ns + 2)
            self.addTri(1, vb + (seg + 1) % ns, vb + seg)

        # Sides
        # Side face vertices go in order:  down right upleft, downright up left
        for ring in range(nr - 2):
            tvb = 2 + ring * ns
            # First vertex index for the top edge of the ring
            bvb = tvb + ns
            # First vertex index for the bottom edge of the ring
            for seg in range(ns):
                nseg = (seg + 1) % ns
                self.addQuad(tvb + seg, bvb + seg, bvb + nseg, tvb + nseg)

    def processGeometryCone(self, node):
        r = readFloat(node, "bottomRadius", 1)
        height = readFloat(node, "height", 2)
        bottom = readBoolean(node, "bottom", True)
        side = readBoolean(node, "side", True)
        n = readInt(node, "subdivision", DEFAULT_SUBDIV)

        d = height / 2
        angle = 2 * pi / n

        self.reserveFaceAndVertexCount((n if side else 0) + (n-2 if bottom else 0), n+1)

        # Vertex 0 is the apex, vertices 1..n are the bottom
        self.addVertex(0, d, 0)
        for i in range(n):
            self.addVertex(-r * sin(angle * i), -d, -r * cos(angle * i))

        # Side face vertices go: up down right
        if side:
            for i in range(n):
                self.addTri(1 + (i + 1) % n, 0, 1 + i)
        if bottom:
            for i in range(2, n):
                self.addTri(1, i, i+1)

    def processGeometryCylinder(self, node):
        r = readFloat(node, "radius", 1)
        height = readFloat(node, "height", 2)
        bottom = readBoolean(node, "bottom", True)
        side = readBoolean(node, "side", True)
        top = readBoolean(node, "top", True)
        n = readInt(node, "subdivision", DEFAULT_SUBDIV)

        nn = n * 2
        angle = 2 * pi / n
        hh = height/2

        self.reserveFaceAndVertexCount((nn if side else 0) + (n - 2 if top else 0) + (n - 2 if bottom else 0), nn)

        # The seam is at x=0, z=-r, vertices go ccw -
        # to pos x, to neg z, to neg x, back to neg z
        for i in range(n):
            rs = -r * sin(angle * i)
            rc = -r * cos(angle * i)
            self.addVertex(rs, hh, rc)
            self.addVertex(rs, -hh, rc)

        if side:
            for i in range(n):
                ni = (i + 1) % n
                self.addQuad(ni * 2 + 1, ni * 2, i * 2, i * 2 + 1)

        for i in range(2, nn-3, 2):
            if top:
                self.addTri(0, i, i+2)
            if bottom:
                self.addTri(1, i+1, i+3)

    # Semi-primitives

    def processGeometryElevationGrid(self, node):
        dx = readFloat(node, "xSpacing", 1)
        dz = readFloat(node, "zSpacing", 1)
        nx = readInt(node, "xDimension", 0)
        nz = readInt(node, "zDimension", 0)
        height = readFloatArray(node, "height", False)
        ccw = readBoolean(node, "ccw", True)

        if nx <= 0 or nz <= 0 or len(height) < nx*nz:
            return # That's weird, the wording of the standard suggests grids with zero quads are somehow valid

        self.reserveFaceAndVertexCount(2*(nx-1)*(nz-1), nx*nz)

        for z in range(nz):
            for x in range(nx):
                self.addVertex(x * dx, height[z*nx + x], z * dz)

        for z in range(1, nz):
            for x in range(1, nx):
                self.addTriFlip((z - 1)*nx + x - 1, z*nx + x, (z - 1)*nx + x, ccw)
                self.addTriFlip((z - 1)*nx + x - 1, z*nx + x - 1, z*nx + x, ccw)

    def processGeometryExtrusion(self, node):
        ccw = readBoolean(node, "ccw", True)
        begin_cap = readBoolean(node, "beginCap", True)
        end_cap = readBoolean(node, "endCap", True)
        cross = readFloatArray(node, "crossSection", (1, 1, 1, -1, -1, -1, -1, 1, 1, 1))
        cross = [(cross[i], cross[i+1]) for i in range(0, len(cross), 2)]
        spine = readFloatArray(node, "spine", (0, 0, 0, 0, 1, 0))
        spine = [(spine[i], spine[i+1], spine[i+2]) for i in range(0, len(spine), 3)]
        orient = readFloatArray(node, "orientation", None)
        if orient:
            # This converts X3D's axis/angle rotation to a 3x3 numpy matrix
            def toRotationMatrix(rot):
                (x, y, z) = rot[:3]
                a = rot[3]
                s = sin(a)
                c = cos(a)
                t = 1-c
                return numpy.array((
                    (x * x * t + c,  x * y * t - z*s, x * z * t + y * s),
                    (x * y * t + z*s, y * y * t + c, y * z * t - x * s),
                    (x * z * t - y * s, y * z * t + x * s, z * z * t + c)))

            orient = [toRotationMatrix(orient[i:i+4]) if orient[i+3] != 0 else None for i in range(0, len(orient), 4)]

        scale = readFloatArray(node, "scale", None)
        if scale:
            scale = [numpy.array(((scale[i], 0, 0), (0, 1, 0), (0, 0, scale[i+1])))
                     if scale[i] != 1 or scale[i+1] != 1 else None for i in range(0, len(scale), 2)]


        # Special treatment for the closed spine and cross section.
        # Let's save some memory by not creating identical but distinct vertices;
        # later we'll introduce conditional logic to link the last vertex with
        # the first one where necessary.
        crossClosed = cross[0] == cross[-1]
        if crossClosed:
            cross = cross[:-1]
        nc = len(cross)
        cross = [numpy.array((c[0], 0, c[1])) for c in cross]
        ncf = nc if crossClosed else nc - 1
        # Face count along the cross; for closed cross, it's the same as the
        # respective vertex count

        spine_closed = spine[0] == spine[-1]
        if spine_closed:
            spine = spine[:-1]
        ns = len(spine)
        spine = [Vector(*s) for s in spine]
        nsf = ns if spine_closed else ns - 1

        # This will be used for fallback, where the current spine point joins
        # two collinear spine segments. No need to recheck the case of the
        # closed spine/last-to-first point juncture; if there's an angle there,
        # it would kick in on the first iteration of the main loop by spine.
        def findFirstAngleNormal():
            for i in range(1, ns - 1):
                spt = spine[i]
                z = (spine[i + 1] - spt).cross(spine[i - 1] - spt)
                if z.length() > EPSILON:
                    return z
            # All the spines are collinear. Fallback to the rotated source
            # XZ plane.
            # TODO: handle the situation where the first two spine points match
            if len(spine) < 2:
                return Vector(0, 0, 1)
            v = spine[1] - spine[0]
            orig_y = Vector(0, 1, 0)
            orig_z = Vector(0, 0, 1)
            if v.cross(orig_y).length() > EPSILON:
                # Spine at angle with global y - rotate the z accordingly
                a = v.cross(orig_y) # Axis of rotation to get to the Z
                (x, y, z) = a.normalized().getData()
                s = a.length()/v.length()
                c = sqrt(1-s*s)
                t = 1-c
                m = numpy.array((
                    (x * x * t + c,  x * y * t + z*s, x * z * t - y * s),
                    (x * y * t - z*s, y * y * t + c, y * z * t + x * s),
                    (x * z * t + y * s, y * z * t - x * s, z * z * t + c)))
                orig_z = Vector(*m.dot(orig_z.getData()))
            return orig_z

        self.reserveFaceAndVertexCount(2*nsf*ncf + (nc - 2 if begin_cap else 0) + (nc - 2 if end_cap else 0), ns*nc)

        z = None
        for i, spt in enumerate(spine):
            if (i > 0 and i < ns - 1) or spine_closed:
                snext = spine[(i + 1) % ns]
                sprev = spine[(i - 1 + ns) % ns]
                y = snext - sprev
                vnext = snext - spt
                vprev = sprev - spt
                try_z = vnext.cross(vprev)
                # Might be zero, then all kinds of fallback
                if try_z.length() > EPSILON:
                    if z is not None and try_z.dot(z) < 0:
                        try_z = -try_z
                    z = try_z
                elif not z:  # No z, and no previous z.
                    # Look ahead, see if there's at least one point where
                    # spines are not collinear.
                    z = findFirstAngleNormal()
            elif i == 0:  # And non-crossed
                snext = spine[i + 1]
                y = snext - spt
                z = findFirstAngleNormal()
            else:  # last point and not crossed
                sprev = spine[i - 1]
                y = spt - sprev
                # If there's more than one point in the spine, z is already set.
                # One point in the spline is an error anyway.

            z = z.normalized()
            y = y.normalized()
            x = y.cross(z) # Already normalized
            m = numpy.array(((x.x, y.x, z.x), (x.y, y.y, z.y), (x.z, y.z, z.z)))

            # Columns are the unit vectors for the xz plane for the cross-section
            if orient:
                mrot = orient[i] if len(orient) > 1 else orient[0]
                if not mrot is None:
                    m = m.dot(mrot)  # Tested against X3DOM, the result matches, still not sure :(

            if scale:
                mscale = scale[i] if len(scale) > 1 else scale[0]
                if not mscale is None:
                    m = m.dot(mscale)

            # First the cross-section 2-vector is scaled,
            # then rotated (which may make it a 3-vector),
            # then applied to the xz plane unit vectors

            sptv3 = numpy.array(spt.getData()[:3])
            for cpt in cross:
                v = sptv3 + m.dot(cpt)
                self.addVertex(*v)

        if begin_cap:
            self.addFace([x for x in range(nc - 1, -1, -1)], ccw)

        # Order of edges in the face: forward along cross, forward along spine,
        # backward along cross, backward along spine, flipped if now ccw.
        # This order is assumed later in the texture coordinate assignment;
        # please don't change without syncing.

        for s in range(ns - 1):
            for c in range(ncf):
                self.addQuadFlip(s * nc + c, s * nc + (c + 1) % nc,
                    (s + 1) * nc + (c + 1) % nc, (s + 1) * nc + c, ccw)

        if spine_closed:
            # The faces between the last and the first spine points
            b = (ns - 1) * nc
            for c in range(ncf):
                self.addQuadFlip(b + c, b + (c + 1) % nc,
                    (c + 1) % nc, c, ccw)

        if end_cap:
            self.addFace([(ns - 1) * nc + x for x in range(0, nc)], ccw)

# Triangle meshes

    # Helper for numerous nodes with a Coordinate subnode holding vertices
    # That all triangle meshes and IndexedFaceSet
    # num_faces can be a function, in case the face count is a function of vertex count
    def startCoordMesh(self, node, num_faces):
        ccw = readBoolean(node, "ccw", True)
        self.readVertices(node) # This will allocate and fill the vertex array
        if hasattr(num_faces, "__call__"):
            num_faces = num_faces(self.getVertexCount())
        self.reserveFaceCount(num_faces)

        return ccw


    def processGeometryIndexedTriangleSet(self, node):
        index = readIntArray(node, "index", [])
        num_faces = len(index) // 3
        ccw = int(self.startCoordMesh(node, num_faces))

        for i in range(0, num_faces*3, 3):
            self.addTri(index[i + 1 - ccw], index[i + ccw], index[i+2])

    def processGeometryIndexedTriangleStripSet(self, node):
        strips = readIndex(node, "index")
        ccw = int(self.startCoordMesh(node, sum([len(strip) - 2 for strip in strips])))

        for strip in strips:
            sccw = ccw # Running CCW value, reset for each strip
            for i in range(len(strip) - 2):
                self.addTri(strip[i + 1 - sccw], strip[i + sccw], strip[i+2])
                sccw = 1 - sccw

    def processGeometryIndexedTriangleFanSet(self, node):
        fans = readIndex(node, "index")
        ccw = int(self.startCoordMesh(node, sum([len(fan) - 2 for fan in fans])))

        for fan in fans:
            for i in range(1, len(fan) - 1):
                self.addTri(fan[0], fan[i + 1 - ccw], fan[i + ccw])

    def processGeometryTriangleSet(self, node):
        ccw = int(self.startCoordMesh(node, lambda num_vert: num_vert // 3))
        for i in range(0, self.getVertexCount(), 3):
            self.addTri(i + 1 - ccw, i + ccw, i+2)

    def processGeometryTriangleStripSet(self, node):
        strips = readIntArray(node, "stripCount", [])
        ccw = int(self.startCoordMesh(node, sum([n-2 for n in strips])))

        vb = 0
        for n in strips:
            sccw = ccw
            for i in range(n-2):
                self.addTri(vb + i + 1 - sccw, vb + i + sccw, vb + i + 2)
                sccw = 1 - sccw
            vb += n

    def processGeometryTriangleFanSet(self, node):
        fans = readIntArray(node, "fanCount", [])
        ccw = int(self.startCoordMesh(node, sum([n-2 for n in fans])))

        vb = 0
        for n in fans:
            for i in range(1, n-1):
                self.addTri(vb, vb + i + 1 - ccw, vb + i + ccw)
            vb += n

    # Quad geometries from the CAD module, might be relevant for printing

    def processGeometryQuadSet(self, node):
        ccw = self.startCoordMesh(node, lambda num_vert: 2*(num_vert // 4))
        for i in range(0, self.getVertexCount(), 4):
            self.addQuadFlip(i, i+1, i+2, i+3, ccw)

    def processGeometryIndexedQuadSet(self, node):
        index = readIntArray(node, "index", [])
        num_quads = len(index) // 4
        ccw = self.startCoordMesh(node, num_quads*2)

        for i in range(0, num_quads*4, 4):
            self.addQuadFlip(index[i], index[i+1], index[i+2], index[i+3], ccw)

    # 2D polygon geometries
    # Won't work for now, since Cura expects every mesh to have a nontrivial convex hull
    # The only way around that is merging meshes.

    def processGeometryDisk2D(self, node):
        innerRadius = readFloat(node, "innerRadius", 0)
        outerRadius = readFloat(node, "outerRadius", 1)
        n = readInt(node, "subdivision", DEFAULT_SUBDIV)

        angle = 2 * pi / n

        self.reserveFaceAndVertexCount(n*4 if innerRadius else n-2, n*2 if innerRadius else n)

        for i in range(n):
            s = sin(angle * i)
            c = cos(angle * i)
            self.addVertex(outerRadius*c, outerRadius*s, 0)
            if innerRadius:
                self.addVertex(innerRadius*c, innerRadius*s, 0)
                ni = (i+1) % n
                self.addQuad(2*i, 2*ni, 2*ni+1, 2*i+1)

        if not innerRadius:
            for i in range(2, n):
                self.addTri(0, i-1, i)

    def processGeometryRectangle2D(self, node):
        (x, y) = readFloatArray(node, "size", (2, 2))
        self.reserveFaceAndVertexCount(2, 4)
        self.addVertex(-x/2, -y/2, 0)
        self.addVertex(x/2, -y/2, 0)
        self.addVertex(x/2, y/2, 0)
        self.addVertex(-x/2, y/2, 0)
        self.addQuad(0, 1, 2, 3)

    def processGeometryTriangleSet2D(self, node):
        verts = readFloatArray(node, "vertices", ())
        num_faces = len(verts) // 6;
        verts = [(verts[i], verts[i+1], 0) for i in range(0, 6 * num_faces, 2)]
        self.reserveFaceAndVertexCount(num_faces, num_faces * 3)
        for vert in verts:
            self.addVertex(*vert)

        # The front face is on the +Z side, so CCW is a variable
        for i in range(0, num_faces*3, 3):
            a = Vector(*verts[i+2]) - Vector(*verts[i])
            b = Vector(*verts[i+1]) - Vector(*verts[i])
            self.addTriFlip(i, i+1, i+2, a.x*b.y > a.y*b.x)

    # General purpose polygon mesh

    def processGeometryIndexedFaceSet(self, node):
        faces = readIndex(node, "coordIndex")
        ccw = self.startCoordMesh(node, sum([len(face) - 2 for face in faces]))

        for face in faces:
            if len(face) == 3:
                self.addTriFlip(face[0], face[1], face[2], ccw)
            elif len(face) > 3:
                self.addFace(face, ccw)

    geometry_importers = {
        "IndexedFaceSet": processGeometryIndexedFaceSet,
        "IndexedTriangleSet": processGeometryIndexedTriangleSet,
        "IndexedTriangleStripSet": processGeometryIndexedTriangleStripSet,
        "IndexedTriangleFanSet": processGeometryIndexedTriangleFanSet,
        "TriangleSet": processGeometryTriangleSet,
        "TriangleStripSet": processGeometryTriangleStripSet,
        "TriangleFanSet": processGeometryTriangleFanSet,
        "QuadSet": processGeometryQuadSet,
        "IndexedQuadSet": processGeometryIndexedQuadSet,
        "TriangleSet2D": processGeometryTriangleSet2D,
        "Rectangle2D": processGeometryRectangle2D,
        "Disk2D": processGeometryDisk2D,
        "ElevationGrid": processGeometryElevationGrid,
        "Extrusion": processGeometryExtrusion,
        "Sphere": processGeometrySphere,
        "Box": processGeometryBox,
        "Cylinder": processGeometryCylinder,
        "Cone": processGeometryCone
    }

    # Parses the Coordinate.@point field, fills the verts array.
    def readVertices(self, node):
        for c in node:
            if c.tag == "Coordinate":
                c = self.resolveDefUse(c)
                if not c is None:
                    pt = c.attrib.get("point")
                    if pt:
                        # allow the list of float values in 'point' attribute to
                        # be separated by commas or whitespace as per spec of
                        # XML encoding of X3D
                        # Ref  ISO/IEC 19776-1:2015 : Section 5.1.2
                        co = [float(x) for vec in pt.split(',') for x in vec.split()]
                        num_verts = len(co) // 3
                        self.verts = numpy.empty((4, num_verts), dtype=numpy.float32)
                        self.verts[3,:] = numpy.ones((num_verts), dtype=numpy.float32)
                        # Group by three
                        for i in range(num_verts):
                            self.verts[:3,i] = co[3*i:3*i+3]

    # Mesh builder helpers

    def reserveFaceAndVertexCount(self, num_faces, num_verts):
        # Unlike the Cura MeshBuilder, we use 4-vectors stored as columns for easier transform
        self.verts = numpy.zeros((4, num_verts), dtype=numpy.float32)
        self.verts[3,:] = numpy.ones((num_verts), dtype=numpy.float32)
        self.num_verts = 0
        self.reserveFaceCount(num_faces)

    def reserveFaceCount(self, num_faces):
        self.faces = numpy.zeros((num_faces, 3), dtype=numpy.int32)
        self.num_faces = 0

    def getVertexCount(self):
        return self.verts.shape[1]

    def addVertex(self, x, y, z):
        self.verts[0, self.num_verts] = x
        self.verts[1, self.num_verts] = y
        self.verts[2, self.num_verts] = z
        self.num_verts += 1

    # Indices are 0-based for this shape, but they won't be zero-based in the merged mesh
    def addTri(self, a, b, c):
        self.faces[self.num_faces, 0] = self.index_base + a
        self.faces[self.num_faces, 1] = self.index_base + b
        self.faces[self.num_faces, 2] = self.index_base + c
        self.num_faces += 1

    def addTriFlip(self, a, b, c, ccw):
        if ccw:
            self.addTri(a, b, c)
        else:
            self.addTri(b, a, c)

    # Needs to be convex, but not necessaily planar
    # Assumed ccw, cut along the ac diagonal
    def addQuad(self, a, b, c, d):
        self.addTri(a, b, c)
        self.addTri(c, d, a)

    def addQuadFlip(self, a, b, c, d, ccw):
        if ccw:
            self.addTri(a, b, c)
            self.addTri(c, d, a)
        else:
            self.addTri(a, c, b)
            self.addTri(c, a, d)


    # Arbitrary polygon triangulation.
    # Doesn't assume convexity and doesn't check the "convex" flag in the file.
    # Works by the "cutting of ears" algorithm:
    # - Find an outer vertex with the smallest angle and no vertices inside its adjacent triangle
    # - Remove the triangle at that vertex
    # - Repeat until done
    # Vertex coordinates are supposed to be already set
    def addFace(self, indices, ccw):
        # Resolve indices to coordinates for faster math
        face = [Vector(data=self.verts[0:3, i]) for i in indices]

        # Need a normal to the plane so that we can know which vertices form inner angles
        normal = findOuterNormal(face)

        if not normal: # Couldn't find an outer edge, non-planar polygon maybe?
            return

        # Find the vertex with the smallest inner angle and no points inside, cut off. Repeat until done
        n = len(face)
        vi = [i for i in range(n)] # We'll be using this to kick vertices from the face
        while n > 3:
            max_cos = EPSILON # We don't want to check anything on Pi angles
            i_min = 0 # max cos corresponds to min angle
            for i in range(n):
                inext = (i + 1) % n
                iprev = (i + n - 1) % n
                v = face[vi[i]]
                next = face[vi[inext]] - v
                prev = face[vi[iprev]] - v
                nextXprev = next.cross(prev)
                if nextXprev.dot(normal) > EPSILON: # If it's an inner angle
                    cos = next.dot(prev) / (next.length() * prev.length())
                    if cos > max_cos:
                        # Check if there are vertices inside the triangle
                        no_points_inside = True
                        for j in range(n):
                            if j != i and j != iprev and j != inext:
                                vx = face[vi[j]] - v
                                if pointInsideTriangle(vx, next, prev, nextXprev):
                                    no_points_inside = False
                                    break

                        if no_points_inside:
                            max_cos = cos
                            i_min = i

            self.addTriFlip(indices[vi[(i_min + n - 1) % n]], indices[vi[i_min]], indices[vi[(i_min + 1) % n]], ccw)
            vi.pop(i_min)
            n -= 1
        self.addTriFlip(indices[vi[0]], indices[vi[1]], indices[vi[2]], ccw)


# ------------------------------------------------------------
# X3D field parsers
# ------------------------------------------------------------
def readFloatArray(node, attr, default):
    s = node.attrib.get(attr)
    if not s:
        return default
    return [float(x) for x in s.split()]

def readIntArray(node, attr, default):
    s = node.attrib.get(attr)
    if not s:
        return default
    return [int(x, 0) for x in s.split()]

def readFloat(node, attr, default):
    s = node.attrib.get(attr)
    if not s:
        return default
    return float(s)

def readInt(node, attr, default):
    s = node.attrib.get(attr)
    if not s:
        return default
    return int(s, 0)

def readBoolean(node, attr, default):
    s = node.attrib.get(attr)
    if not s:
        return default
    return s.lower() == "true"

def readVector(node, attr, default):
    v = readFloatArray(node, attr, default)
    return Vector(v[0], v[1], v[2])

def readRotation(node, attr, default):
    v = readFloatArray(node, attr, default)
    return (v[3], Vector(v[0], v[1], v[2]))

# Returns the -1-separated runs
def readIndex(node, attr):
    v = readIntArray(node, attr, [])
    chunks = []
    chunk = []
    for i in range(len(v)):
        if v[i] == -1:
            if chunk:
                chunks.append(chunk)
                chunk = []
        else:
            chunk.append(v[i])
    if chunk:
        chunks.append(chunk)
    return chunks

# Given a face as a sequence of vectors, returns a normal to the polygon place that forms a right triple
# with a vector along the polygon sequence and a vector backwards
def findOuterNormal(face):
    n = len(face)
    for i in range(n):
        for j in range(i+1, n):
            edge = face[j] - face[i]
            if edge.length() > EPSILON:
                edge = edge.normalized()
                prev_rejection = Vector()
                is_outer = True
                for k in range(n):
                    if k != i and k != j:
                        pt = face[k] - face[i]
                        pte = pt.dot(edge)
                        rejection = pt - edge*pte
                        if rejection.dot(prev_rejection) < -EPSILON: # points on both sides of the edge - not an outer one
                            is_outer = False
                            break
                        elif rejection.length() > prev_rejection.length(): # Pick a greater rejection for numeric stability
                            prev_rejection = rejection

                if is_outer: # Found an outer edge, prev_rejection is the rejection inside the face. Generate a normal.
                    return edge.cross(prev_rejection)

    return False

# Given two *collinear* vectors a and b, returns the coefficient that takes b to a.
# No error handling.
# For stability, taking the ration between the biggest coordinates would be better...
def ratio(a, b):
    if b.x > EPSILON or b.x < -EPSILON:
        return a.x / b.x
    elif b.y > EPSILON or b.y < -EPSILON:
        return a.y / b.y
    else:
        return a.z / b.z

def pointInsideTriangle(vx, next, prev, nextXprev):
    vxXprev = vx.cross(prev)
    r = ratio(vxXprev, nextXprev)
    if r < 0:
        return False
    vxXnext = vx.cross(next);
    s = -ratio(vxXnext, nextXprev)
    return s > 0 and (s + r) < 1