Cura/util/mesh.py

   1 from __future__ import absolute_import
   2 __copyright__ = "Copyright (C) 2013 David Braam - Released under terms of the AGPLv3 License"
   3
   4 import time
   5 import math
   6 import os
   7
   8 import numpy
   9 numpy.seterr(all='ignore')
  10
  11 def convexHull(pointList):
  12         def _isRightTurn((p, q, r)):
  13                 sum1 = q[0]*r[1] + p[0]*q[1] + r[0]*p[1]
  14                 sum2 = q[0]*p[1] + r[0]*q[1] + p[0]*r[1]
  15
  16                 if sum1 - sum2 < 0:
  17                         return 1
  18                 else:
  19                         return 0
  20
  21         unique = {}
  22         for p in pointList:
  23                 unique[(int(p[0]),int(p[1]))] = 1
  24
  25         points = unique.keys()
  26         points.sort()
  27
  28         # Build upper half of the hull.
  29         upper = [points[0], points[1]]
  30         for p in points[2:]:
  31                 upper.append(p)
  32                 while len(upper) > 2 and not _isRightTurn(upper[-3:]):
  33                         del upper[-2]
  34
  35         # Build lower half of the hull.
  36         points = points[::-1]
  37         lower = [points[0], points[1]]
  38         for p in points[2:]:
  39                 lower.append(p)
  40                 while len(lower) > 2 and not _isRightTurn(lower[-3:]):
  41                         del lower[-2]
  42
  43         # Remove duplicates.
  44         del lower[0]
  45         del lower[-1]
  46
  47         return numpy.array(upper + lower, numpy.float32) - numpy.array([0.0,0.0], numpy.float32)
  48
  49 class printableObject(object):
  50         def __init__(self, originFilename):
  51                 self._originFilename = originFilename
  52                 if originFilename is None:
  53                         self._name = 'None'
  54                 else:
  55                         self._name = os.path.basename(originFilename)
  56                 if '.' in self._name:
  57                         self._name = os.path.splitext(self._name)[0]
  58                 self._meshList = []
  59                 self._position = numpy.array([0.0, 0.0])
  60                 self._matrix = numpy.matrix([[1,0,0],[0,1,0],[0,0,1]], numpy.float64)
  61                 self._transformedMin = None
  62                 self._transformedMax = None
  63                 self._transformedSize = None
  64                 self._boundaryCircleSize = None
  65                 self._drawOffset = None
  66                 self._loadAnim = None
  67
  68         def copy(self):
  69                 ret = printableObject(self._originFilename)
  70                 ret._matrix = self._matrix.copy()
  71                 ret._transformedMin = self._transformedMin.copy()
  72                 ret._transformedMax = self._transformedMax.copy()
  73                 ret._transformedSize = self._transformedSize.copy()
  74                 ret._boundaryCircleSize = self._boundaryCircleSize
  75                 ret._boundaryHull = self._boundaryHull.copy()
  76                 ret._drawOffset = self._drawOffset.copy()
  77                 for m in self._meshList[:]:
  78                         m2 = ret._addMesh()
  79                         m2.vertexes = m.vertexes
  80                         m2.vertexCount = m.vertexCount
  81                         m2.vbo = m.vbo
  82                         m2.vbo.incRef()
  83                 return ret
  84
  85         def _addMesh(self):
  86                 m = mesh(self)
  87                 self._meshList.append(m)
  88                 return m
  89
  90         def _postProcessAfterLoad(self):
  91                 for m in self._meshList:
  92                         m._calculateNormals()
  93                 self.processMatrix()
  94                 if numpy.max(self.getSize()) > 10000.0:
  95                         for m in self._meshList:
  96                                 m.vertexes /= 1000.0
  97                         self.processMatrix()
  98                 if numpy.max(self.getSize()) < 1.0:
  99                         for m in self._meshList:
 100                                 m.vertexes *= 1000.0
 101                         self.processMatrix()
 102
 103         def applyMatrix(self, m):
 104                 self._matrix *= m
 105                 self.processMatrix()
 106
 107         def processMatrix(self):
 108                 self._transformedMin = numpy.array([999999999999,999999999999,999999999999], numpy.float64)
 109                 self._transformedMax = numpy.array([-999999999999,-999999999999,-999999999999], numpy.float64)
 110                 self._boundaryCircleSize = 0
 111
 112                 hull = numpy.zeros((0, 2), numpy.float32)
 113                 for m in self._meshList:
 114                         transformedVertexes = m.getTransformedVertexes()
 115                         hull = convexHull(numpy.concatenate((transformedVertexes[:,0:2], hull), 0))
 116                         transformedMin = transformedVertexes.min(0)
 117                         transformedMax = transformedVertexes.max(0)
 118                         for n in xrange(0, 3):
 119                                 self._transformedMin[n] = min(transformedMin[n], self._transformedMin[n])
 120                                 self._transformedMax[n] = max(transformedMax[n], self._transformedMax[n])
 121
 122                         #Calculate the boundary circle
 123                         transformedSize = transformedMax - transformedMin
 124                         center = transformedMin + transformedSize / 2.0
 125                         boundaryCircleSize = round(math.sqrt(numpy.max(((transformedVertexes[::,0] - center[0]) * (transformedVertexes[::,0] - center[0])) + ((transformedVertexes[::,1] - center[1]) * (transformedVertexes[::,1] - center[1])) + ((transformedVertexes[::,2] - center[2]) * (transformedVertexes[::,2] - center[2])))), 3)
 126                         self._boundaryCircleSize = max(self._boundaryCircleSize, boundaryCircleSize)
 127                 self._transformedSize = self._transformedMax - self._transformedMin
 128                 self._drawOffset = (self._transformedMax + self._transformedMin) / 2
 129                 self._drawOffset[2] = self._transformedMin[2]
 130                 self._boundaryHull = hull - self._drawOffset[0:2]
 131                 self._transformedMax -= self._drawOffset
 132                 self._transformedMin -= self._drawOffset
 133
 134         def getName(self):
 135                 return self._name
 136         def getOriginFilename(self):
 137                 return self._originFilename
 138         def getPosition(self):
 139                 return self._position
 140         def setPosition(self, newPos):
 141                 self._position = newPos
 142         def getMatrix(self):
 143                 return self._matrix
 144
 145         def getMaximum(self):
 146                 return self._transformedMax
 147         def getMinimum(self):
 148                 return self._transformedMin
 149         def getSize(self):
 150                 return self._transformedSize
 151         def getDrawOffset(self):
 152                 return self._drawOffset
 153         def getBoundaryCircle(self):
 154                 return self._boundaryCircleSize
 155
 156         def mirror(self, axis):
 157                 matrix = [[1,0,0], [0, 1, 0], [0, 0, 1]]
 158                 matrix[axis][axis] = -1
 159                 self.applyMatrix(numpy.matrix(matrix, numpy.float64))
 160
 161         def getScale(self):
 162                 return numpy.array([
 163                         numpy.linalg.norm(self._matrix[::,0].getA().flatten()),
 164                         numpy.linalg.norm(self._matrix[::,1].getA().flatten()),
 165                         numpy.linalg.norm(self._matrix[::,2].getA().flatten())], numpy.float64);
 166
 167         def setScale(self, scale, axis, uniform):
 168                 currentScale = numpy.linalg.norm(self._matrix[::,axis].getA().flatten())
 169                 scale /= currentScale
 170                 if scale == 0:
 171                         return
 172                 if uniform:
 173                         matrix = [[scale,0,0], [0, scale, 0], [0, 0, scale]]
 174                 else:
 175                         matrix = [[1.0,0,0], [0, 1.0, 0], [0, 0, 1.0]]
 176                         matrix[axis][axis] = scale
 177                 self.applyMatrix(numpy.matrix(matrix, numpy.float64))
 178
 179         def setSize(self, size, axis, uniform):
 180                 scale = self.getSize()[axis]
 181                 scale = size / scale
 182                 if scale == 0:
 183                         return
 184                 if uniform:
 185                         matrix = [[scale,0,0], [0, scale, 0], [0, 0, scale]]
 186                 else:
 187                         matrix = [[1,0,0], [0, 1, 0], [0, 0, 1]]
 188                         matrix[axis][axis] = scale
 189                 self.applyMatrix(numpy.matrix(matrix, numpy.float64))
 190
 191         def resetScale(self):
 192                 x = 1/numpy.linalg.norm(self._matrix[::,0].getA().flatten())
 193                 y = 1/numpy.linalg.norm(self._matrix[::,1].getA().flatten())
 194                 z = 1/numpy.linalg.norm(self._matrix[::,2].getA().flatten())
 195                 self.applyMatrix(numpy.matrix([[x,0,0],[0,y,0],[0,0,z]], numpy.float64))
 196
 197         def resetRotation(self):
 198                 x = numpy.linalg.norm(self._matrix[::,0].getA().flatten())
 199                 y = numpy.linalg.norm(self._matrix[::,1].getA().flatten())
 200                 z = numpy.linalg.norm(self._matrix[::,2].getA().flatten())
 201                 self._matrix = numpy.matrix([[x,0,0],[0,y,0],[0,0,z]], numpy.float64)
 202                 self.processMatrix()
 203
 204         def layFlat(self):
 205                 transformedVertexes = self._meshList[0].getTransformedVertexes()
 206                 minZvertex = transformedVertexes[transformedVertexes.argmin(0)[2]]
 207                 dotMin = 1.0
 208                 dotV = None
 209                 for v in transformedVertexes:
 210                         diff = v - minZvertex
 211                         len = math.sqrt(diff[0] * diff[0] + diff[1] * diff[1] + diff[2] * diff[2])
 212                         if len < 5:
 213                                 continue
 214                         dot = (diff[2] / len)
 215                         if dotMin > dot:
 216                                 dotMin = dot
 217                                 dotV = diff
 218                 if dotV is None:
 219                         return
 220                 rad = -math.atan2(dotV[1], dotV[0])
 221                 self._matrix *= numpy.matrix([[math.cos(rad), math.sin(rad), 0], [-math.sin(rad), math.cos(rad), 0], [0,0,1]], numpy.float64)
 222                 rad = -math.asin(dotMin)
 223                 self._matrix *= numpy.matrix([[math.cos(rad), 0, math.sin(rad)], [0,1,0], [-math.sin(rad), 0, math.cos(rad)]], numpy.float64)
 224
 225
 226                 transformedVertexes = self._meshList[0].getTransformedVertexes()
 227                 minZvertex = transformedVertexes[transformedVertexes.argmin(0)[2]]
 228                 dotMin = 1.0
 229                 dotV = None
 230                 for v in transformedVertexes:
 231                         diff = v - minZvertex
 232                         len = math.sqrt(diff[1] * diff[1] + diff[2] * diff[2])
 233                         if len < 5:
 234                                 continue
 235                         dot = (diff[2] / len)
 236                         if dotMin > dot:
 237                                 dotMin = dot
 238                                 dotV = diff
 239                 if dotV is None:
 240                         return
 241                 if dotV[1] < 0:
 242                         rad = math.asin(dotMin)
 243                 else:
 244                         rad = -math.asin(dotMin)
 245                 self.applyMatrix(numpy.matrix([[1,0,0], [0, math.cos(rad), math.sin(rad)], [0, -math.sin(rad), math.cos(rad)]], numpy.float64))
 246
 247         def scaleUpTo(self, size):
 248                 vMin = self._transformedMin
 249                 vMax = self._transformedMax
 250
 251                 scaleX1 = (size[0] / 2 - self._position[0]) / ((vMax[0] - vMin[0]) / 2)
 252                 scaleY1 = (size[1] / 2 - self._position[1]) / ((vMax[1] - vMin[1]) / 2)
 253                 scaleX2 = (self._position[0] + size[0] / 2) / ((vMax[0] - vMin[0]) / 2)
 254                 scaleY2 = (self._position[1] + size[1] / 2) / ((vMax[1] - vMin[1]) / 2)
 255                 scaleZ = size[2] / (vMax[2] - vMin[2])
 256                 scale = min(scaleX1, scaleY1, scaleX2, scaleY2, scaleZ)
 257                 if scale > 0:
 258                         self.applyMatrix(numpy.matrix([[scale,0,0],[0,scale,0],[0,0,scale]], numpy.float64))
 259
 260         #Split splits an object with multiple meshes into different objects, where each object is a part of the original mesh that has
 261         # connected faces. This is useful to split up plate STL files.
 262         def split(self, callback):
 263                 ret = []
 264                 for oriMesh in self._meshList:
 265                         ret += oriMesh.split(callback)
 266                 return ret
 267
 268         def canStoreAsSTL(self):
 269                 return len(self._meshList) < 2
 270
 271         #getVertexIndexList returns an array of vertexes, and an integer array for each mesh in this object.
 272         # the integer arrays are indexes into the vertex array for each triangle in the model.
 273         def getVertexIndexList(self):
 274                 vertexMap = {}
 275                 vertexList = []
 276                 meshList = []
 277                 for m in self._meshList:
 278                         verts = m.getTransformedVertexes(True)
 279                         meshIdxList = []
 280                         for idx in xrange(0, len(verts)):
 281                                 v = verts[idx]
 282                                 hashNr = int(v[0] * 100) | int(v[1] * 100) << 10 | int(v[2] * 100) << 20
 283                                 vIdx = None
 284                                 if hashNr in vertexMap:
 285                                         for idx2 in vertexMap[hashNr]:
 286                                                 if numpy.linalg.norm(v - vertexList[idx2]) < 0.001:
 287                                                         vIdx = idx2
 288                                 if vIdx is None:
 289                                         vIdx = len(vertexList)
 290                                         vertexMap[hashNr] = [vIdx]
 291                                         vertexList.append(v)
 292                                 meshIdxList.append(vIdx)
 293                         meshList.append(numpy.array(meshIdxList, numpy.int32))
 294                 return numpy.array(vertexList, numpy.float32), meshList
 295
 296 class mesh(object):
 297         def __init__(self, obj):
 298                 self.vertexes = None
 299                 self.vertexCount = 0
 300                 self.vbo = None
 301                 self._obj = obj
 302
 303         def _addFace(self, x0, y0, z0, x1, y1, z1, x2, y2, z2):
 304                 n = self.vertexCount
 305                 self.vertexes[n][0] = x0
 306                 self.vertexes[n][1] = y0
 307                 self.vertexes[n][2] = z0
 308                 n += 1
 309                 self.vertexes[n][0] = x1
 310                 self.vertexes[n][1] = y1
 311                 self.vertexes[n][2] = z1
 312                 n += 1
 313                 self.vertexes[n][0] = x2
 314                 self.vertexes[n][1] = y2
 315                 self.vertexes[n][2] = z2
 316                 self.vertexCount += 3
 317
 318         def _prepareFaceCount(self, faceNumber):
 319                 #Set the amount of faces before loading data in them. This way we can create the numpy arrays before we fill them.
 320                 self.vertexes = numpy.zeros((faceNumber*3, 3), numpy.float32)
 321                 self.normal = numpy.zeros((faceNumber*3, 3), numpy.float32)
 322                 self.vertexCount = 0
 323
 324         def _calculateNormals(self):
 325                 #Calculate the normals
 326                 tris = self.vertexes.reshape(self.vertexCount / 3, 3, 3)
 327                 normals = numpy.cross( tris[::,1 ] - tris[::,0]  , tris[::,2 ] - tris[::,0] )
 328                 lens = numpy.sqrt( normals[:,0]**2 + normals[:,1]**2 + normals[:,2]**2 )
 329                 normals[:,0] /= lens
 330                 normals[:,1] /= lens
 331                 normals[:,2] /= lens
 332
 333                 n = numpy.zeros((self.vertexCount / 3, 9), numpy.float32)
 334                 n[:,0:3] = normals
 335                 n[:,3:6] = normals
 336                 n[:,6:9] = normals
 337                 self.normal = n.reshape(self.vertexCount, 3)
 338                 self.invNormal = -self.normal
 339
 340         def _vertexHash(self, idx):
 341                 v = self.vertexes[idx]
 342                 return int(v[0] * 100) | int(v[1] * 100) << 10 | int(v[2] * 100) << 20
 343
 344         def _idxFromHash(self, map, idx):
 345                 vHash = self._vertexHash(idx)
 346                 for i in map[vHash]:
 347                         if numpy.linalg.norm(self.vertexes[i] - self.vertexes[idx]) < 0.001:
 348                                 return i
 349
 350         def getTransformedVertexes(self, applyOffsets = False):
 351                 if applyOffsets:
 352                         pos = self._obj._position.copy()
 353                         pos.resize((3))
 354                         pos[2] = self._obj.getSize()[2] / 2
 355                         offset = self._obj._drawOffset.copy()
 356                         offset[2] += self._obj.getSize()[2] / 2
 357                         return (numpy.matrix(self.vertexes, copy = False) * numpy.matrix(self._obj._matrix, numpy.float32)).getA() - offset + pos
 358                 return (numpy.matrix(self.vertexes, copy = False) * numpy.matrix(self._obj._matrix, numpy.float32)).getA()
 359
 360         def split(self, callback):
 361                 vertexMap = {}
 362
 363                 vertexToFace = []
 364                 for idx in xrange(0, self.vertexCount):
 365                         if (idx % 100) == 0:
 366                                 callback(idx * 100 / self.vertexCount)
 367                         vHash = self._vertexHash(idx)
 368                         if vHash not in vertexMap:
 369                                 vertexMap[vHash] = []
 370                         vertexMap[vHash].append(idx)
 371                         vertexToFace.append([])
 372
 373                 faceList = []
 374                 for idx in xrange(0, self.vertexCount, 3):
 375                         if (idx % 100) == 0:
 376                                 callback(idx * 100 / self.vertexCount)
 377                         f = [self._idxFromHash(vertexMap, idx), self._idxFromHash(vertexMap, idx+1), self._idxFromHash(vertexMap, idx+2)]
 378                         vertexToFace[f[0]].append(idx / 3)
 379                         vertexToFace[f[1]].append(idx / 3)
 380                         vertexToFace[f[2]].append(idx / 3)
 381                         faceList.append(f)
 382
 383                 ret = []
 384                 doneSet = set()
 385                 for idx in xrange(0, len(faceList)):
 386                         if idx in doneSet:
 387                                 continue
 388                         doneSet.add(idx)
 389                         todoList = [idx]
 390                         meshFaceList = []
 391                         while len(todoList) > 0:
 392                                 idx = todoList.pop()
 393                                 meshFaceList.append(idx)
 394                                 for n in xrange(0, 3):
 395                                         for i in vertexToFace[faceList[idx][n]]:
 396                                                 if not i in doneSet:
 397                                                         doneSet.add(i)
 398                                                         todoList.append(i)
 399
 400                         obj = printableObject(self._obj.getOriginFilename())
 401                         obj._matrix = self._obj._matrix.copy()
 402                         m = obj._addMesh()
 403                         m._prepareFaceCount(len(meshFaceList))
 404                         for idx in meshFaceList:
 405                                 m.vertexes[m.vertexCount] = self.vertexes[faceList[idx][0]]
 406                                 m.vertexCount += 1
 407                                 m.vertexes[m.vertexCount] = self.vertexes[faceList[idx][1]]
 408                                 m.vertexCount += 1
 409                                 m.vertexes[m.vertexCount] = self.vertexes[faceList[idx][2]]
 410                                 m.vertexCount += 1
 411                         obj._postProcessAfterLoad()
 412                         ret.append(obj)
 413                 return ret