+## 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)
+
+
+# ---------------------------------------------------------------------
+#
projects / vrm.git / blobdiff