diff options
author | Campbell Barton <ideasman42@gmail.com> | 2006-05-28 14:44:29 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2006-05-28 14:44:29 +0400 |
commit | 98b2e98c79448c35ee4f805dee16bc0f0ffb6063 (patch) | |
tree | d582c651c15818ac3efec0d11e3faa772252e063 /release/scripts | |
parent | e47719d253c3be3217816a8dc83c64e0d3d9828d (diff) |
Added a 2d convex hull function to BPyMathutils
Added a 2D Line intersection function
Added a function to BPyMesh that gets the mesh space vertex location of a Faces UV Pixel.
Diffstat (limited to 'release/scripts')
-rw-r--r-- | release/scripts/bpymodules/BPyMathutils.py | 145 | ||||
-rw-r--r-- | release/scripts/bpymodules/BPyMesh.py | 51 |
2 files changed, 194 insertions, 2 deletions
diff --git a/release/scripts/bpymodules/BPyMathutils.py b/release/scripts/bpymodules/BPyMathutils.py index dd402b66a8c..d991ef03d99 100644 --- a/release/scripts/bpymodules/BPyMathutils.py +++ b/release/scripts/bpymodules/BPyMathutils.py @@ -121,3 +121,148 @@ def genrand(): return ( float(y) / 0xffffffffL ) # reals #------ Mersenne Twister -- end + + + + +""" 2d convexhull +Based from Dinu C. Gherman's work, +modified for Blender/Mathutils by Campell Barton +""" +###################################################################### +# Public interface +###################################################################### +from Blender.Mathutils import DotVecs +def convexHull(point_list_2d): + """Calculate the convex hull of a set of vectors + The vectors can be 3 or 4d but only the Xand Y are used. + returns a list of convex hull indicies to the given point list + """ + + ###################################################################### + # Helpers + ###################################################################### + + def _myDet(p, q, r): + """Calc. determinant of a special matrix with three 2D points. + + The sign, "-" or "+", determines the side, right or left, + respectivly, on which the point r lies, when measured against + a directed vector from p to q. + """ + return (q.x*r.y + p.x*q.y + r.x*p.y) - (q.x*p.y + r.x*q.y + p.x*r.y) + + def _isRightTurn((p, q, r)): + "Do the vectors pq:qr form a right turn, or not?" + #assert p[0] != q[0] and q[0] != r[0] and p[0] != r[0] + if _myDet(p[0], q[0], r[0]) < 0: + return 1 + else: + return 0 + + # Get a local list copy of the points and sort them lexically. + points = [(p, i) for i, p in enumerate(point_list_2d)] + points.sort(lambda a,b: cmp((a[0].x, a[0].y), (b[0].x, b[0].y))) + + # Build upper half of the hull. + upper = [points[0], points[1]] # cant remove these. + for i in xrange(len(points)-2): + upper.append(points[i+2]) + while len(upper) > 2 and not _isRightTurn(upper[-3:]): + del upper[-2] + + # Build lower half of the hull. + points.reverse() + lower = [points.pop(0), points.pop(1)] + for p in points: + lower.append(p) + while len(lower) > 2 and not _isRightTurn(lower[-3:]): + del lower[-2] + + # Concatenate both halfs and return. + return [p[1] for ls in (upper, lower) for p in ls] + + +def lineIntersect2D(v1a, v1b, v2a, v2b): + ''' + Do 2 lines intersect, if so where. + If there is an error, the retured X value will be None + the y will be an error code- usefull when debugging. + + the first line is (v1a, v1b) + the second is (v2a, v2b) + by Campbell Barton + This function accounts for all known cases of 2 lines ;) + ''' + + x1,y1= v1a.x, v1a.y + x2,y2= v1b.x, v1b.y + _x1,_y1= v2a.x, v2a.y + _x2,_y2= v2b.x, v2b.y + + # Bounding box intersection first. + if min(x1, x2) > max(_x1, _x2) or \ + max(x1, x2) < min(_x1, _x2) or \ + min(y1, y2) > max(_y1, _y2) or \ + max(y1, y2) < min(_y1, _y2): + return None, 100 # Basic Bounds intersection TEST returns false. + + # are either of the segments points? Check Seg1 + if abs(x1 - x2) + abs(y1 - y2) <= SMALL_NUM: + return None, 101 + + # are either of the segments points? Check Seg2 + if abs(_x1 - _x2) + abs(_y1 - _y2) <= SMALL_NUM: + return None, 102 + + # Make sure the HOZ/Vert Line Comes first. + if abs(_x1 - _x2) < SMALL_NUM or abs(_y1 - _y2) < SMALL_NUM: + x1, x2, y1, y2, _x1, _x2, _y1, _y2 = _x1, _x2, _y1, _y2, x1, x2, y1, y2 + + if abs(x2-x1) < SMALL_NUM: # VERTICLE LINE + if abs(_x2-_x1) < SMALL_NUM: # VERTICLE LINE SEG2 + return None, 111 # 2 verticle lines dont intersect. + + elif abs(_y2-_y1) < SMALL_NUM: + return x1, _y1 # X of vert, Y of hoz. no calculation. + + yi = ((_y1 / abs(_x1 - _x2)) * abs(_x2 - x1)) + ((_y2 / abs(_x1 - _x2)) * abs(_x1 - x1)) + + if yi > max(y1, y2): # New point above seg1's vert line + return None, 112 + elif yi < min(y1, y2): # New point below seg1's vert line + return None, 113 + + return x1, yi # Intersecting. + + + if abs(y2-y1) < SMALL_NUM: # HOZ LINE + if abs(_y2-_y1) < SMALL_NUM: # HOZ LINE SEG2 + return None, 121 # 2 hoz lines dont intersect. + + # Can skip vert line check for seg 2 since its covered above. + xi = ((_x1 / abs(_y1 - _y2)) * abs(_y2 - y1)) + ((_x2 / abs(_y1 - _y2)) * abs(_y1 - y1)) + if xi > max(x1, x2): # New point right of seg1's hoz line + return None, 112 + elif xi < min(x1, x2): # New point left of seg1's hoz line + return None, 113 + + return xi, y1 # Intersecting. + + # Accounted for hoz/vert lines. Go on with both anglular. + b1 = (y2-y1)/(x2-x1) + b2 = (_y2-_y1)/(_x2-_x1) + a1 = y1-b1*x1 + a2 = _y1-b2*_x1 + + if b1 - b2 == 0.0: + return None, 200 + + xi = - (a1-a2)/(b1-b2) + yi = a1+b1*xi + if (x1-xi)*(xi-x2) >= 0 and (_x1-xi)*(xi-_x2) >= 0 and (y1-yi)*(yi-y2) >= 0 and (_y1-yi)*(yi-_y2)>=0: + return xi, yi + else: + return None, 300 + + diff --git a/release/scripts/bpymodules/BPyMesh.py b/release/scripts/bpymodules/BPyMesh.py index b0351e16a76..79bfd19452f 100644 --- a/release/scripts/bpymodules/BPyMesh.py +++ b/release/scripts/bpymodules/BPyMesh.py @@ -190,6 +190,54 @@ def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=Tru return mesh + + +#============================================================================# +# Takes a face, and a pixel x/y on the image and returns a worldspace x/y/z # +# will return none if the pixel is not inside the faces UV # +#============================================================================# +def getUvPixelLoc(face, pxLoc, img_size = None, uvArea = None): + TriangleArea= Blender.Mathutils.TriangleArea + Vector= Blender.Mathutils.Vector + + if not img_size: + w,h = face.image.size + else: + w,h= img_size + + scaled_uvs= [Vector(uv.x*w, uv.y*h) for uv in f.uv] + + if len(scaled_uvs)==3: + indicies= ((0,1,2),) + else: + indicies= ((0,1,2), (0,2,3)) + + for fidxs in indicies: + for i1,i2,i3 in fidxs: + # IS a point inside our triangle? + # UVArea could be cached? + uv_area = TriangleArea(scaled_uvs[i1], scaled_uvs[i2], scaled_uvs[i3]) + area0 = TriangleArea(pxLoc, scaled_uvs[i2], scaled_uvs[i3]) + area1 = TriangleArea(pxLoc, scaled_uvs[i1], scaled_uvs[i3]) + area2 = TriangleArea(pxLoc, scaled_uvs[i1], scaled_uvs[i2]) + if area0 + area1 + area2 > uv_area + 1: # 1 px bleed/error margin. + pass # if were a quad the other side may contain the pixel so keep looking. + else: + # We know the point is in the tri + area0 /= uv_area + area1 /= uv_area + area2 /= uv_area + + # New location + return Vector(\ + face.v[i1].co[0]*area0 + face.v[i2].co[0]*area1 + face.v[i3].co[0]*area2,\ + face.v[i1].co[1]*area0 + face.v[i2].co[1]*area1 + face.v[i3].co[1]*area2,\ + face.v[i1].co[2]*area0 + face.v[i2].co[2]*area1 + face.v[i3].co[2]*area2\ + ) + + return None + + type_tuple= type( (0,) ) type_list= type( [] ) def ngon(from_data, indices): @@ -230,8 +278,7 @@ def ngon(from_data, indices): oldmode = Mesh.Mode() Mesh.Mode(Mesh.SelectModes['VERTEX']) - for v in temp_mesh.verts: - v.sel= 1 + temp_mesh.sel= True # Select all verst # Must link to scene scn= Scene.GetCurrent() |