Add an HSR helper class
[vrm.git] / vrm.py
diff --git a/vrm.py b/vrm.py
index 26a14d7..b121765 100755 (executable)
--- a/vrm.py
+++ b/vrm.py
@@ -58,9 +58,8 @@ __bpydoc__ = """\
 #   - Implement Edge Styles (silhouettes, contours, etc.) (partially done).
 #   - Implement Shading Styles? (partially done, to make more flexible).
 #   - Add Vector Writers other than SVG.
+#   - set the background color!
 #   - Check memory use!!
-#   - Support Indexed palettes!! (Useful for ILDA FILES, for example,
-#     see http://www.linux-laser.org/download/autotrace/ilda-output.patch)
 #
 # ---------------------------------------------------------------------
 #
@@ -102,7 +101,7 @@ class config:
     polygons['SHOW'] = True
     polygons['SHADING'] = 'FLAT'
     #polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
-    polygons['HSR'] = 'PAINTER'
+    polygons['HSR'] = 'NEWELL'
     # Hidden to the user for now
     polygons['EXPANSION_TRICK'] = True
 
@@ -112,24 +111,58 @@ class config:
     edges['SHOW'] = False
     edges['SHOW_HIDDEN'] = False
     edges['STYLE'] = 'MESH' # or SILHOUETTE
-    edges['STYLE'] = 'SILHOUETTE'
     edges['WIDTH'] = 2
     edges['COLOR'] = [0, 0, 0]
 
     output = dict()
     output['FORMAT'] = 'SVG'
-    output['FORMAT'] = 'SWF'
-    output['ANIMATION'] = True
+    output['ANIMATION'] = False
     output['JOIN_OBJECTS'] = True
 
+    #output['FORMAT'] = 'SWF'
+    #output['ANIMATION'] = True
 
 
 # Utility functions
+print_debug = False
+
+def dumpfaces(flist, filename):
+    """Dump a single face to a file.
+    """
+    if not print_debug:
+        return
+
+    class tmpmesh:
+        pass
+
+    m = tmpmesh()
+    m.faces = flist
+
+    writerobj = SVGVectorWriter(filename)
+
+    writerobj.open()
+    writerobj._printPolygons(m)
+
+    writerobj.close()
+
+def debug(msg):
+    if print_debug:
+        sys.stderr.write(msg)
+
+def EQ(v1, v2):
+    return (abs(v1[0]-v2[0]) < EPS and 
+            abs(v1[1]-v2[1]) < EPS )
+by_furthest_z = (lambda f1, f2:
+    cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2])+EPS)
+    )
+
 def sign(x):
 
     if x < -EPS:
+    #if x < 0:
         return -1
     elif x > EPS:
+    #elif x > 0:
         return 1
     else:
         return 0
@@ -137,9 +170,538 @@ def sign(x):
 
 # ---------------------------------------------------------------------
 #
+## HSR Utility class
+#
+# ---------------------------------------------------------------------
+
+EPS = 10e-5
+INF = 10e5
+
+class HSR:
+    """A utility class for HSR processing.
+    """
+
+    def is_nonplanar_quad(face):
+        """Determine if a quad is non-planar.
+
+        From: http://mathworld.wolfram.com/Coplanar.html
+
+        Geometric objects lying in a common plane are said to be coplanar.
+        Three noncollinear points determine a plane and so are trivially coplanar.
+        Four points are coplanar iff the volume of the tetrahedron defined by them is
+        0, 
+        
+            | x_1 y_1 z_1 1 |
+            | x_2 y_2 z_2 1 |
+            | x_3 y_3 z_3 1 |
+            | x_4 y_4 z_4 1 | == 0
+
+        Coplanarity is equivalent to the statement that the pair of lines
+        determined by the four points are not skew, and can be equivalently stated
+        in vector form as (x_3-x_1).[(x_2-x_1)x(x_4-x_3)]==0.
+
+        An arbitrary number of n points x_1, ..., x_n can be tested for
+        coplanarity by finding the point-plane distances of the points
+        x_4, ..., x_n from the plane determined by (x_1,x_2,x_3)
+        and checking if they are all zero.
+        If so, the points are all coplanar.
+
+        We here check only for 4-point complanarity.
+        """
+        n = len(face)
+
+        # assert(n>4)
+        if n < 3 or n > 4:
+            print "ERROR a mesh in Blender can't have more than 4 vertices or less than 3"
+            raise AssertionError
+
+        elif n == 3:
+            # three points must be complanar
+            return False
+        else: # n == 4
+            x1 = Vector(face[0].co)
+            x2 = Vector(face[1].co)
+            x3 = Vector(face[2].co)
+            x4 = Vector(face[3].co)
+
+            v = (x3-x1) * CrossVecs((x2-x1), (x4-x3))
+            if v != 0:
+                return True
+
+        return False
+
+    is_nonplanar_quad = staticmethod(is_nonplanar_quad)
+
+    def pointInPolygon(poly, v):
+        return False
+
+    pointInPolygon = staticmethod(pointInPolygon)
+
+    def edgeIntersection(s1, s2, do_perturbate=False):
+
+        (x1, y1) = s1[0].co[0], s1[0].co[1]
+        (x2, y2) = s1[1].co[0], s1[1].co[1]
+
+        (x3, y3) = s2[0].co[0], s2[0].co[1]
+        (x4, y4) = s2[1].co[0], s2[1].co[1]
+
+        #z1 = s1[0].co[2]
+        #z2 = s1[1].co[2]
+        #z3 = s2[0].co[2]
+        #z4 = s2[1].co[2]
+
+
+        # calculate delta values (vector components)
+        dx1 = x2 - x1;
+        dx2 = x4 - x3;
+        dy1 = y2 - y1;
+        dy2 = y4 - y3;
+
+        #dz1 = z2 - z1;
+        #dz2 = z4 - z3;
+
+        C = dy2 * dx1 - dx2 * dy1 #  /* cross product */
+        if C == 0:  #/* parallel */
+            return None
+
+        dx3 = x1 - x3 # /* combined origin offset vector */
+        dy3 = y1 - y3
+
+        a1 = (dy3 * dx2 - dx3 * dy2) / C;
+        a2 = (dy3 * dx1 - dx3 * dy1) / C;
+
+        # check for degeneracies
+        #print_debug("\n")
+        #print_debug(str(a1)+"\n")
+        #print_debug(str(a2)+"\n\n")
+
+        if (a1 == 0 or a1 == 1 or a2 == 0 or a2 == 1):
+            # Intersection on boundaries, we consider the point external?
+            return None
+
+        elif (a1>0.0 and a1<1.0 and a2>0.0 and a2<1.0): #  /* lines cross */
+            x = x1 + a1*dx1
+            y = y1 + a1*dy1
+
+            #z = z1 + a1*dz1
+            z = 0
+            return (NMesh.Vert(x, y, z), a1, a2)
+
+        else:
+            # lines have intersections but not those segments
+            return None
+
+    edgeIntersection = staticmethod(edgeIntersection)
+
+    def isVertInside(self, v):
+        winding_number = 0
+        coincidence = False
+
+        # Create point at infinity
+        point_at_infinity = NMesh.Vert(-INF, v.co[1], -INF)
+
+        for i in range(len(self.v)):
+            s1 = (point_at_infinity, v)
+            s2 = (self.v[i-1], self.v[i])
+
+            if EQ(v.co, s2[0].co) or EQ(v.co, s2[1].co):
+                coincidence = True
+
+            if HSR.edgeIntersection(s1, s2, do_perturbate=False):
+                winding_number += 1
+
+        # Check even or odd
+        if winding_number % 2 == 0 :
+            return False
+        else:
+            if coincidence:
+                return False
+            return True
+
+    isVertInside = staticmethod(isVertInside)
+
+    def projectionsOverlap(f1, f2):
+        """ If you have nonconvex, but still simple polygons, an acceptable method
+        is to iterate over all vertices and perform the Point-in-polygon test[1].
+        The advantage of this method is that you can compute the exact
+        intersection point and collision normal that you will need to simulate
+        collision. When you have the point that lies inside the other polygon, you
+        just iterate over all edges of the second polygon again and look for edge
+        intersections. Note that this method detects collsion when it already
+        happens. This algorithm is fast enough to perform it hundreds of times per
+        sec.  """
+
+        for i in range(len(f1.v)):
+
+
+            # If a point of f1 in inside f2, there is an overlap!
+            v1 = f1.v[i]
+            if HSR.isVertInside(f2, v1):
+                return True
+
+            # If not the polygon can be ovelap as well, so we check for
+            # intersection between an edge of f1 and all the edges of f2
+
+            v0 = f1.v[i-1]
+
+            for j in range(len(f2.v)):
+                v2 = f2.v[j-1]
+                v3 = f2.v[j]
+
+                e1 = v0, v1
+                e2 = v2, v3
+
+                intrs = HSR.edgeIntersection(e1, e2)
+                if intrs:
+                    #print_debug(str(v0.co) + " " + str(v1.co) + " " +
+                    #        str(v2.co) + " " + str(v3.co) )
+                    #print_debug("\nIntersection\n")
+
+                    return True
+
+        return False
+
+    projectionsOverlap = staticmethod(projectionsOverlap)
+
+    def midpoint(p1, p2):
+        """Return the midpoint of two vertices.
+        """
+        m = MidpointVecs(Vector(p1), Vector(p2))
+        mv = NMesh.Vert(m[0], m[1], m[2])
+
+        return mv
+
+    midpoint = staticmethod(midpoint)
+
+    def facesplit(P, Q, facelist, nmesh):
+        """Split P or Q according to the strategy illustrated in the Newell's
+        paper.
+        """
+
+        by_furthest_z = (lambda f1, f2:
+                cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2])+EPS)
+                )
+
+        # Choose if split P on Q plane or vice-versa
+
+        n = 0
+        for Pi in P:
+            d = HSR.Distance(Vector(Pi), Q)
+            if d <= EPS:
+                n += 1
+        pIntersectQ = (n != len(P))
+
+        n = 0
+        for Qi in Q:
+            d = HSR.Distance(Vector(Qi), P)
+            if d >= -EPS:
+                n += 1
+        qIntersectP = (n != len(Q))
+
+        newfaces = []
+
+        # 1. If parts of P lie in both half-spaces of Q
+        # then splice P in two with the plane of Q
+        if pIntersectQ:
+            #print "We split P"
+            f = P
+            plane = Q
+
+            newfaces = HSR.splitOn(plane, f)
+
+        # 2. Else if parts of Q lie in both half-space of P
+        # then splice Q in two with the plane of P
+        if qIntersectP and newfaces == None:
+            #print "We split Q"
+            f = Q
+            plane = P
+
+            newfaces = HSR.splitOn(plane, f)
+            #print "After"
+
+        # 3. Else slice P in half through the mid-point of
+        # the longest pair of opposite sides
+        if newfaces == None:
+
+            print "We ignore P..."
+            facelist.remove(P)
+            return facelist
+
+            #f = P
+
+            #if len(P)==3:
+            #    v1 = midpoint(f[0], f[1])
+            #    v2 = midpoint(f[1], f[2])
+            #if len(P)==4:
+            #    v1 = midpoint(f[0], f[1])
+            #    v2 = midpoint(f[2], f[3])
+            #vec3 = (Vector(v2)+10*Vector(f.normal))
+            #
+            #v3 = NMesh.Vert(vec3[0], vec3[1], vec3[2])
+
+            #plane = NMesh.Face([v1, v2, v3])
+            #
+            #newfaces = splitOn(plane, f)
+
+        
+        if newfaces == None:
+            print "Big FAT problem, we weren't able to split POLYGONS!"
+            raise AssertionError
+
+        #print newfaces
+        if newfaces:
+            #for v in f:
+            #    if v not in plane and v in nmesh.verts:
+            #        nmesh.verts.remove(v)
+            for nf in newfaces:
+
+                nf.mat = f.mat
+                nf.sel = f.sel
+                nf.col = [f.col[0]] * len(nf.v)
+
+                nf.smooth = 0
+
+                for v in nf:
+                    nmesh.verts.append(v)
+                # insert pieces in the list
+                facelist.append(nf)
+
+            facelist.remove(f)
+
+        # and resort the faces
+        facelist.sort(by_furthest_z)
+        facelist.sort(lambda f1, f2: cmp(f1.smooth, f2.smooth))
+        facelist.reverse()
+
+        #print [ f.smooth for f in facelist ]
+
+        return facelist
+
+    facesplit = staticmethod(facesplit)
+
+    def isOnSegment(v1, v2, p, extremes_internal=False):
+        """Check if point p is in segment v1v2.
+        """
+
+        l1 = (v1-p).length
+        l2 = (v2-p).length
+
+        # Should we consider extreme points as internal ?
+        # The test:
+        # if p == v1 or p == v2:
+        if l1 < EPS or l2 < EPS:
+            return extremes_internal
+
+        l = (v1-v2).length
+
+        # if the sum of l1 and l2 is circa l, then the point is on segment,
+        if abs(l - (l1+l2)) < EPS:
+            return True
+        else:
+            return False
+
+    isOnSegment = staticmethod(isOnSegment)
+
+    def Distance(point, face):
+        """ Calculate the distance between a point and a face.
+
+        An alternative but more expensive method can be:
+
+            ip = Intersect(Vector(face[0]), Vector(face[1]), Vector(face[2]),
+                    Vector(face.no), Vector(point), 0)
+
+            d = Vector(ip - point).length
+
+        See: http://mathworld.wolfram.com/Point-PlaneDistance.html
+        """
+
+        p = Vector(point)
+        plNormal = Vector(face.no)
+        plVert0 = Vector(face.v[0])
+
+        d = (plVert0 * plNormal) - (p * plNormal)
+
+        #d = plNormal * (plVert0 - p)
+
+        #print "\nd: %.10f - sel: %d, %s\n" % (d, face.sel, str(point))
+
+        return d
+
+    Distance = staticmethod(Distance)
+
+    def makeFaces(vl):
+        #
+        # make one or two new faces based on a list of vertex-indices
+        #
+        newfaces = []
+
+        if len(vl) <= 4:
+            nf = NMesh.Face()
+
+            for v in vl:
+                nf.v.append(v)
+
+            newfaces.append(nf)
+
+        else:
+            nf = NMesh.Face()
+
+            nf.v.append(vl[0])
+            nf.v.append(vl[1])
+            nf.v.append(vl[2])
+            nf.v.append(vl[3])
+            newfaces.append(nf)
+
+            nf = NMesh.Face()
+            nf.v.append(vl[3])
+            nf.v.append(vl[4])
+            nf.v.append(vl[0])
+            newfaces.append(nf)
+
+        return newfaces
+
+    makeFaces = staticmethod(makeFaces)
+
+    def splitOn(Q, P):
+        """Split P using the plane of Q.
+        Logic taken from the knife.py python script
+        """
+
+        # Check if P and Q are parallel
+        u = CrossVecs(Vector(Q.no),Vector(P.no))
+        ax = abs(u[0])
+        ay = abs(u[1])
+        az = abs(u[2])
+
+        if (ax+ay+az) < EPS:
+            print "PARALLEL planes!!"
+            return
+
+
+        # The final aim is to find the intersection line between P
+        # and the plane of Q, and split P along this line
+
+        nP = len(P.v)
+
+        # Calculate point-plane Distance between vertices of P and plane Q
+        d = []
+        for i in range(0, nP):
+            d.append(HSR.Distance(P.v[i], Q))
+
+        newVertList = []
+
+        posVertList = []
+        negVertList = []
+        for i in range(nP):
+            d0 = d[i-1]
+            V0 = P.v[i-1]
+
+            d1 = d[i]
+            V1 = P.v[i]
+
+            #print "d0:", d0, "d1:", d1
+
+            # if the vertex lies in the cutplane                       
+            if abs(d1) < EPS:
+                #print "d1 On cutplane"
+                posVertList.append(V1)
+                negVertList.append(V1)
+            else:
+                # if the previous vertex lies in cutplane
+                if abs(d0) < EPS:
+                    #print "d0 on Cutplane"
+                    if d1 > 0:
+                        #print "d1 on positive Halfspace"
+                        posVertList.append(V1)
+                    else:
+                        #print "d1 on negative Halfspace"
+                        negVertList.append(V1)
+                else:
+                    # if they are on the same side of the plane
+                    if d1*d0 > 0:
+                        #print "On the same half-space"
+                        if d1 > 0:
+                            #print "d1 on positive Halfspace"
+                            posVertList.append(V1)
+                        else:
+                            #print "d1 on negative Halfspace"
+                            negVertList.append(V1)
+
+                    # the vertices are not on the same side of the plane, so we have an intersection
+                    else:
+                        #print "Intersection"
+
+                        e = Vector(V0), Vector(V1)
+                        tri = Vector(Q[0]), Vector(Q[1]), Vector(Q[2])
+
+                        inters = Intersect(tri[0], tri[1], tri[2], e[1]-e[0], e[0], 0)
+                        if inters == None:
+                            print "Split Break"
+                            break
+
+                        #print "Intersection", inters
+
+                        nv = NMesh.Vert(inters[0], inters[1], inters[2])
+                        newVertList.append(nv)
+
+                        posVertList.append(nv)
+                        negVertList.append(nv)
+
+                        if d1 > 0:
+                            posVertList.append(V1)
+                        else:
+                            negVertList.append(V1)
+
+        
+        # uniq
+        posVertList = [ u for u in posVertList if u not in locals()['_[1]'] ]
+        negVertList = [ u for u in negVertList if u not in locals()['_[1]'] ]
+
+
+        # If vertex are all on the same half-space, return
+        #if len(posVertList) < 3:
+        #    print "Problem, we created a face with less that 3 verteices??"
+        #    posVertList = []
+        #if len(negVertList) < 3:
+        #    print "Problem, we created a face with less that 3 verteices??"
+        #    negVertList = []
+
+        if len(posVertList) < 3 or len(negVertList) < 3:
+            print "RETURN NONE, SURE???"
+            return None
+
+
+        newfaces = HSR.addNewFaces(posVertList, negVertList)
+
+        return newfaces
+
+    splitOn = staticmethod(splitOn)
+
+    def addNewFaces(posVertList, negVertList):
+        # Create new faces resulting from the split
+        outfaces = []
+        if len(posVertList) or len(negVertList):
+
+            #newfaces = [posVertList] + [negVertList]
+            newfaces = ( [[ NMesh.Vert(v[0], v[1], v[2]) for v in posVertList]] +
+                    [[ NMesh.Vert(v[0], v[1], v[2]) for v in negVertList]] )
+
+            for nf in newfaces:
+                if nf and len(nf)>2:
+                    outfaces += HSR.makeFaces(nf)
+
+        return outfaces
+
+
+    addNewFaces = staticmethod(addNewFaces)
+
+
+# ---------------------------------------------------------------------
+#
 ## Mesh Utility class
 #
 # ---------------------------------------------------------------------
+
 class MeshUtils:
 
     def buildEdgeFaceUsersCache(me):
@@ -222,6 +784,7 @@ class MeshUtils:
 ## Shading Utility class
 #
 # ---------------------------------------------------------------------
+
 class ShadingUtils:
 
     shademap = None
@@ -791,10 +1354,11 @@ class SVGVectorWriter(VectorWriter):
 
             self.file.write("<path d=\"")
 
-            p = self._calcCanvasCoord(face.verts[0])
+            #p = self._calcCanvasCoord(face.verts[0])
+            p = self._calcCanvasCoord(face.v[0])
             self.file.write("M %g,%g L " % (p[0], p[1]))
 
-            for v in face.verts[1:]:
+            for v in face.v[1:]:
                 p = self._calcCanvasCoord(v)
                 self.file.write("%g,%g " % (p[0], p[1]))
             
@@ -873,7 +1437,11 @@ class SVGVectorWriter(VectorWriter):
 
 ## SWF Writer
 
-from ming import *
+try:
+    from ming import *
+    SWFSupported = True
+except:
+    SWFSupported = False
 
 class SWFVectorWriter(VectorWriter):
     """A concrete class for writing SWF output.
@@ -1080,7 +1648,8 @@ edgeStyles['SILHOUETTE'] = MeshUtils.isSilhouetteEdge
 # A dictionary to collect the supported output formats
 outputWriters = dict()
 outputWriters['SVG'] = SVGVectorWriter
-outputWriters['SWF'] = SWFVectorWriter
+if SWFSupported:
+    outputWriters['SWF'] = SWFVectorWriter
 
 
 class Renderer:
@@ -1673,7 +2242,6 @@ class Renderer:
         """Newell's depth sorting.
 
         """
-        from hsrtk import *
 
         #global progress
 
@@ -1754,7 +2322,7 @@ class Renderer:
                         debug("met a marked face\n")
                         continue
 
-                
                 # Test 1: X extent overlapping
                 xP = [v.co[0] for v in P.v]
                 xQ = [v.co[0] for v in Q.v]
@@ -1782,7 +2350,7 @@ class Renderer:
                 # Test 3: P vertices are all behind the plane of Q
                 n = 0
                 for Pi in P:
-                    d = qSign * Distance(Vector(Pi), Q)
+                    d = qSign * HSR.Distance(Vector(Pi), Q)
                     if d <= EPS:
                         n += 1
                 pVerticesBehindPlaneQ = (n == len(P))
@@ -1796,7 +2364,7 @@ class Renderer:
                 # Test 4: Q vertices in front of the plane of P
                 n = 0
                 for Qi in Q:
-                    d = pSign * Distance(Vector(Qi), P)
+                    d = pSign * HSR.Distance(Vector(Qi), P)
                     if d >= -EPS:
                         n += 1
                 qVerticesInFrontPlaneP = (n == len(Q))
@@ -1810,7 +2378,8 @@ class Renderer:
                 # Test 5: Check if projections of polygons effectively overlap,
                 # in previous tests we checked only bounding boxes.
 
-                if not projectionsOverlap(P, Q):
+                #if not projectionsOverlap(P, Q):
+                if not ( HSR.projectionsOverlap(P, Q) or HSR.projectionsOverlap(Q, P)):
                     debug("\nTest 5\n")
                     debug("Projections do not overlap!\n")
                     continue
@@ -1824,7 +2393,7 @@ class Renderer:
                     debug("Possibly a cycle detected!\n")
                     debug("Split here!!\n")
 
-                    facelist = facesplit(P, Q, facelist, nmesh)
+                    facelist = HSR.facesplit(P, Q, facelist, nmesh)
                     split_done = 1
                     break 
 
@@ -1834,7 +2403,7 @@ class Renderer:
                 # Test 3bis: Q vertices are all behind the plane of P
                 n = 0
                 for Qi in Q:
-                    d = pSign * Distance(Vector(Qi), P)
+                    d = pSign * HSR.Distance(Vector(Qi), P)
                     if d <= EPS:
                         n += 1
                 qVerticesBehindPlaneP = (n == len(Q))
@@ -1847,7 +2416,7 @@ class Renderer:
                 # Test 4bis: P vertices in front of the plane of Q
                 n = 0
                 for Pi in P:
-                    d = qSign * Distance(Vector(Pi), Q)
+                    d = qSign * HSR.Distance(Vector(Pi), Q)
                     if d >= -EPS:
                         n += 1
                 pVerticesInFrontPlaneQ = (n == len(P))
@@ -1864,7 +2433,7 @@ class Renderer:
                     debug("Test 3bis or 4bis failed\n")
                     debug("Split here!!2\n")
 
-                    facelist = facesplit(P, Q, facelist, nmesh)
+                    facelist = HSR.facesplit(P, Q, facelist, nmesh)
                     split_done = 1
                     break 
                     
@@ -1874,14 +2443,19 @@ class Renderer:
                 face_marked = 1
                 debug("Q marked!\n")
                 break
-           
             # Write P!                     
             if split_done == 0 and face_marked == 0:
                 facelist.remove(P)
                 maplist.append(P)
+                dumpfaces(maplist, "dump"+str(len(maplist)).zfill(4)+".svg")
 
                 progress.update()
 
+            if len(facelist) == 870:
+                dumpfaces([P, Q], "loopdebug.svg")
+
+
             #if facelist == None:
             #    maplist = [P, Q]
             #    print [v.co for v in P]
@@ -1892,8 +2466,8 @@ class Renderer:
          
 
         nmesh.faces = maplist
-        for f in nmesh.faces:
-            f.sel = 1
+        #for f in nmesh.faces:
+        #    f.sel = 1
 
         nmesh.update()
 
@@ -1943,7 +2517,6 @@ class Renderer:
             if edgestyleSelect(e, mesh):
                 e.sel = 1
         """
-                
 
 
 # ---------------------------------------------------------------------
@@ -2202,6 +2775,8 @@ def vectorize(filename):
 
     if editmode: Window.EditMode(1) 
 
+
+
 # Here the main
 if __name__ == "__main__":