Cura/fabmetheus_utilities/geometry/solids/triangle_mesh.py

   1 """
   2 Triangle Mesh holds the faces and edges of a triangular mesh.
   3
   4 """
   5
   6 from __future__ import absolute_import
   7 #Init has to be imported first because it has code to workaround the python bug where relative imports don't work if the module is imported as a main module.
   8 import __init__
   9
  10 from fabmetheus_utilities.geometry.geometry_tools import face
  11 from fabmetheus_utilities.geometry.geometry_tools import dictionary
  12 from fabmetheus_utilities.geometry.geometry_tools import vertex
  13 from fabmetheus_utilities.geometry.geometry_utilities import evaluate
  14 from fabmetheus_utilities.geometry.geometry_utilities import matrix
  15 from fabmetheus_utilities.geometry.solids import group
  16 from fabmetheus_utilities import xml_simple_writer
  17 from fabmetheus_utilities.vector3 import Vector3
  18 from fabmetheus_utilities.vector3index import Vector3Index
  19 from fabmetheus_utilities import euclidean
  20 from fabmetheus_utilities import intercircle
  21 from fabmetheus_utilities import settings
  22 import math
  23
  24
  25 __author__ = 'Enrique Perez (perez_enrique@yahoo.com)'
  26 __credits__ = 'Art of Illusion <http://www.artofillusion.org/>'
  27 __date__ = '$Date: 2008/02/05 $'
  28 __license__ = 'GNU Affero General Public License http://www.gnu.org/licenses/agpl.html'
  29
  30
  31 def addEdgePair( edgePairTable, edges, faceEdgeIndex, remainingEdgeIndex, remainingEdgeTable ):
  32         'Add edge pair to the edge pair table.'
  33         if faceEdgeIndex == remainingEdgeIndex:
  34                 return
  35         if not faceEdgeIndex in remainingEdgeTable:
  36                 return
  37         edgePair = EdgePair().getFromIndexesEdges( [ remainingEdgeIndex, faceEdgeIndex ], edges )
  38         edgePairTable[ str( edgePair ) ] = edgePair
  39
  40 def addFacesByConcaveLoop(faces, indexedLoop):
  41         'Add faces from a polygon which is concave.'
  42         if len(indexedLoop) < 3:
  43                 return
  44         remainingLoop = indexedLoop[:]
  45         while len(remainingLoop) > 2:
  46                 remainingLoop = getRemainingLoopAddFace(faces, remainingLoop)
  47
  48 def addFacesByConvex(faces, indexedLoop):
  49         'Add faces from a convex polygon.'
  50         if len(indexedLoop) < 3:
  51                 return
  52         indexBegin = indexedLoop[0].index
  53         for indexedPointIndex in xrange(1, len(indexedLoop) - 1):
  54                 indexCenter = indexedLoop[indexedPointIndex].index
  55                 indexEnd = indexedLoop[(indexedPointIndex + 1) % len(indexedLoop) ].index
  56                 if indexBegin != indexCenter and indexCenter != indexEnd and indexEnd != indexBegin:
  57                         faceFromConvex = face.Face()
  58                         faceFromConvex.index = len(faces)
  59                         faceFromConvex.vertexIndexes.append(indexBegin)
  60                         faceFromConvex.vertexIndexes.append(indexCenter)
  61                         faceFromConvex.vertexIndexes.append(indexEnd)
  62                         faces.append(faceFromConvex)
  63
  64 def addFacesByConvexBottomTopLoop(faces, indexedLoopBottom, indexedLoopTop):
  65         'Add faces from loops.'
  66         if len(indexedLoopBottom) == 0 or len(indexedLoopTop) == 0:
  67                 return
  68         for indexedPointIndex in xrange(max(len(indexedLoopBottom), len(indexedLoopTop))):
  69                 indexedConvex = []
  70                 if len(indexedLoopBottom) > 1:
  71                         indexedConvex.append(indexedLoopBottom[indexedPointIndex])
  72                         indexedConvex.append(indexedLoopBottom[(indexedPointIndex + 1) % len(indexedLoopBottom)])
  73                 else:
  74                         indexedConvex.append(indexedLoopBottom[0])
  75                 if len(indexedLoopTop) > 1:
  76                         indexedConvex.append(indexedLoopTop[(indexedPointIndex + 1) % len(indexedLoopTop)])
  77                         indexedConvex.append(indexedLoopTop[indexedPointIndex])
  78                 else:
  79                         indexedConvex.append(indexedLoopTop[0])
  80                 addFacesByConvex(faces, indexedConvex)
  81
  82 def addFacesByConvexLoops(faces, indexedLoops):
  83         'Add faces from loops.'
  84         if len(indexedLoops) < 2:
  85                 return
  86         for indexedLoopsIndex in xrange(len(indexedLoops) - 2):
  87                 addFacesByConvexBottomTopLoop(faces, indexedLoops[indexedLoopsIndex], indexedLoops[indexedLoopsIndex + 1])
  88         indexedLoopBottom = indexedLoops[-2]
  89         indexedLoopTop = indexedLoops[-1]
  90         if len(indexedLoopTop) < 1:
  91                 indexedLoopTop = indexedLoops[0]
  92         addFacesByConvexBottomTopLoop(faces, indexedLoopBottom, indexedLoopTop)
  93
  94 def addFacesByConvexReversed(faces, indexedLoop):
  95         'Add faces from a reversed convex polygon.'
  96         addFacesByConvex(faces, indexedLoop[: : -1])
  97
  98 def addFacesByGrid(faces, grid):
  99         'Add faces from grid.'
 100         cellTopLoops = getIndexedCellLoopsFromIndexedGrid(grid)
 101         for cellTopLoop in cellTopLoops:
 102                 addFacesByConvex(faces, cellTopLoop)
 103
 104 def addFacesByLoop(faces, indexedLoop):
 105         'Add faces from a polygon which may be concave.'
 106         if len(indexedLoop) < 3:
 107                 return
 108         lastNormal = None
 109         for pointIndex, point in enumerate(indexedLoop):
 110                 center = indexedLoop[(pointIndex + 1) % len(indexedLoop)]
 111                 end = indexedLoop[(pointIndex + 2) % len(indexedLoop)]
 112                 normal = euclidean.getNormalWeighted(point, center, end)
 113                 if abs(normal) > 0.0:
 114                         if lastNormal != None:
 115                                 if lastNormal.dot(normal) < 0.0:
 116                                         addFacesByConcaveLoop(faces, indexedLoop)
 117                                         return
 118                         lastNormal = normal
 119 #       totalNormal = Vector3()
 120 #       for pointIndex, point in enumerate(indexedLoop):
 121 #               center = indexedLoop[(pointIndex + 1) % len(indexedLoop)]
 122 #               end = indexedLoop[(pointIndex + 2) % len(indexedLoop)]
 123 #               totalNormal += euclidean.getNormalWeighted(point, center, end)
 124 #       totalNormal.normalize()
 125         addFacesByConvex(faces, indexedLoop)
 126
 127 def addFacesByLoopReversed(faces, indexedLoop):
 128         'Add faces from a reversed convex polygon.'
 129         addFacesByLoop(faces, indexedLoop[: : -1])
 130
 131 def addFacesByMeldedConvexLoops(faces, indexedLoops):
 132         'Add faces from melded loops.'
 133         if len(indexedLoops) < 2:
 134                 return
 135         for indexedLoopsIndex in xrange(len(indexedLoops) - 2):
 136                 FaceGenerator(faces, indexedLoops[indexedLoopsIndex], indexedLoops[indexedLoopsIndex + 1])
 137         indexedLoopBottom = indexedLoops[-2]
 138         indexedLoopTop = indexedLoops[-1]
 139         if len(indexedLoopTop) < 1:
 140                 indexedLoopTop = indexedLoops[0]
 141         FaceGenerator(faces, indexedLoopBottom, indexedLoopTop)
 142
 143 def addLoopToPointTable(loop, pointTable):
 144         'Add the points in the loop to the point table.'
 145         for point in loop:
 146                 pointTable[point] = None
 147
 148 def addMeldedPillarByLoops(faces, indexedLoops):
 149         'Add melded pillar by loops which may be concave.'
 150         if len(indexedLoops) < 1:
 151                 return
 152         if len(indexedLoops[-1]) < 1:
 153                 addFacesByMeldedConvexLoops(faces, indexedLoops)
 154                 return
 155         addFacesByLoopReversed(faces, indexedLoops[0])
 156         addFacesByMeldedConvexLoops(faces, indexedLoops)
 157         addFacesByLoop(faces, indexedLoops[-1])
 158
 159 def addPillarByLoops(faces, indexedLoops):
 160         'Add pillar by loops which may be concave.'
 161         if len(indexedLoops) < 1:
 162                 return
 163         if len(indexedLoops[-1]) < 1:
 164                 addFacesByConvexLoops(faces, indexedLoops)
 165                 return
 166         addFacesByLoopReversed(faces, indexedLoops[0])
 167         addFacesByConvexLoops(faces, indexedLoops)
 168         addFacesByLoop(faces, indexedLoops[-1])
 169
 170 def addPillarFromConvexLoopsGrids(faces, indexedGrids, indexedLoops):
 171         'Add pillar from convex loops and grids.'
 172         cellBottomLoops = getIndexedCellLoopsFromIndexedGrid(indexedGrids[0])
 173         for cellBottomLoop in cellBottomLoops:
 174                 addFacesByConvexReversed(faces, cellBottomLoop)
 175         addFacesByConvexLoops(faces, indexedLoops)
 176         addFacesByGrid(faces, indexedGrids[-1])
 177
 178 def addPillarFromConvexLoopsGridTop(faces, indexedGridTop, indexedLoops):
 179         'Add pillar from convex loops and grid top.'
 180         addFacesByLoopReversed(faces, indexedLoops[0])
 181         addFacesByConvexLoops(faces, indexedLoops)
 182         addFacesByGrid(faces, indexedGridTop)
 183
 184 def addPointsAtZ(edgePair, points, radius, vertexes, z):
 185         'Add point complexes on the segment between the edge intersections with z.'
 186         carveIntersectionFirst = getCarveIntersectionFromEdge(edgePair.edges[0], vertexes, z)
 187         carveIntersectionSecond = getCarveIntersectionFromEdge(edgePair.edges[1], vertexes, z)
 188         # threshold radius above 0.8 can create extra holes on Screw Holder, 0.7 should be safe for everything
 189         intercircle.addPointsFromSegment(carveIntersectionFirst, carveIntersectionSecond, points, radius, 0.7)
 190
 191 def addSymmetricXPath(outputs, path, x):
 192         'Add x path output to outputs.'
 193         vertexes = []
 194         loops = [getSymmetricXLoop(path, vertexes, -x), getSymmetricXLoop(path, vertexes, x)]
 195         outputs.append(getPillarOutput(loops))
 196
 197 def addSymmetricXPaths(outputs, paths, x):
 198         'Add x paths outputs to outputs.'
 199         for path in paths:
 200                 addSymmetricXPath(outputs, path, x)
 201
 202 def addSymmetricYPath(outputs, path, y):
 203         'Add y path output to outputs.'
 204         vertexes = []
 205         loops = [getSymmetricYLoop(path, vertexes, -y), getSymmetricYLoop(path, vertexes, y)]
 206         outputs.append(getPillarOutput(loops))
 207
 208 def addSymmetricYPaths(outputs, paths, y):
 209         'Add y paths outputs to outputs.'
 210         for path in paths:
 211                 addSymmetricYPath(outputs, path, y)
 212
 213 def addVector3Loop(loop, loops, vertexes, z):
 214         'Add vector3Loop to loops if there is something in it, for inset and outset.'
 215         vector3Loop = []
 216         for point in loop:
 217                 vector3Index = Vector3Index(len(vertexes), point.real, point.imag, z)
 218                 vector3Loop.append(vector3Index)
 219                 vertexes.append(vector3Index)
 220         if len(vector3Loop) > 0:
 221                 loops.append(vector3Loop)
 222
 223 def addWithLeastLength(importRadius, loops, point):
 224         'Insert a point into a loop, at the index at which the loop would be shortest.'
 225         close = 1.65 * importRadius # a bit over the experimental minimum additional loop length to restore a right angle
 226         shortestAdditionalLength = close
 227         shortestLoop = None
 228         shortestPointIndex = None
 229         for loop in loops:
 230                 if len(loop) > 3:
 231                         for pointIndex in xrange(len(loop)):
 232                                 additionalLoopLength = getAdditionalLoopLength(loop, point, pointIndex)
 233                                 if additionalLoopLength < shortestAdditionalLength:
 234                                         if getIsPointCloseInline(close, loop, point, pointIndex):
 235                                                 shortestAdditionalLength = additionalLoopLength
 236                                                 shortestLoop = loop
 237                                                 shortestPointIndex = pointIndex
 238         if shortestPointIndex != None:
 239                 shortestLoop.insert( shortestPointIndex, point )
 240
 241 def convertElementNode(elementNode, geometryOutput):
 242         'Convert the xml element to a TriangleMesh xml element.'
 243         elementNode.linkObject(TriangleMesh())
 244         matrix.getBranchMatrixSetElementNode(elementNode)
 245         vertex.addGeometryList(elementNode, geometryOutput['vertex'])
 246         face.addGeometryList(elementNode, geometryOutput['face'])
 247         elementNode.getXMLProcessor().processChildNodes(elementNode)
 248
 249 def getAddIndexedGrid( grid, vertexes, z ):
 250         'Get and add an indexed grid.'
 251         indexedGrid = []
 252         for row in grid:
 253                 indexedRow = []
 254                 indexedGrid.append( indexedRow )
 255                 for pointComplex in row:
 256                         vector3index = Vector3Index( len(vertexes), pointComplex.real, pointComplex.imag, z )
 257                         indexedRow.append(vector3index)
 258                         vertexes.append(vector3index)
 259         return indexedGrid
 260
 261 def getAddIndexedLoop(loop, vertexes, z):
 262         'Get and add an indexed loop.'
 263         indexedLoop = []
 264         for index in xrange(len(loop)):
 265                 pointComplex = loop[index]
 266                 vector3index = Vector3Index(len(vertexes), pointComplex.real, pointComplex.imag, z)
 267                 indexedLoop.append(vector3index)
 268                 vertexes.append(vector3index)
 269         return indexedLoop
 270
 271 def getAddIndexedLoops( loop, vertexes, zList ):
 272         'Get and add indexed loops.'
 273         indexedLoops = []
 274         for z in zList:
 275                 indexedLoop = getAddIndexedLoop( loop, vertexes, z )
 276                 indexedLoops.append(indexedLoop)
 277         return indexedLoops
 278
 279 def getAdditionalLoopLength(loop, point, pointIndex):
 280         'Get the additional length added by inserting a point into a loop.'
 281         afterPoint = loop[pointIndex]
 282         beforePoint = loop[(pointIndex + len(loop) - 1) % len(loop)]
 283         return abs(point - beforePoint) + abs(point - afterPoint) - abs(afterPoint - beforePoint)
 284
 285 def getCarveIntersectionFromEdge(edge, vertexes, z):
 286         'Get the complex where the carve intersects the edge.'
 287         firstVertex = vertexes[ edge.vertexIndexes[0] ]
 288         firstVertexComplex = firstVertex.dropAxis()
 289         secondVertex = vertexes[ edge.vertexIndexes[1] ]
 290         secondVertexComplex = secondVertex.dropAxis()
 291         zMinusFirst = z - firstVertex.z
 292         up = secondVertex.z - firstVertex.z
 293         return zMinusFirst * ( secondVertexComplex - firstVertexComplex ) / up + firstVertexComplex
 294
 295 def getClosestDistanceIndexToPoint(point, loop):
 296         'Get the distance squared to the closest point of the loop and index of that point.'
 297         smallestDistance = 987654321987654321.0
 298         closestDistanceIndex = None
 299         pointComplex = point.dropAxis()
 300         for otherPointIndex, otherPoint in enumerate(loop):
 301                 distance = abs(pointComplex - otherPoint.dropAxis())
 302                 if distance < smallestDistance:
 303                         smallestDistance = distance
 304                         closestDistanceIndex = euclidean.DistanceIndex(distance, otherPointIndex)
 305         return closestDistanceIndex
 306
 307 def getDescendingAreaLoops(allPoints, corners, importRadius):
 308         'Get descending area loops which include most of the points.'
 309         loops = intercircle.getCentersFromPoints(allPoints, importRadius)
 310         descendingAreaLoops = []
 311         sortLoopsInOrderOfArea(True, loops)
 312         pointDictionary = {}
 313         for loop in loops:
 314                 if len(loop) > 2 and getOverlapRatio(loop, pointDictionary) < 0.3 and intercircle.getIsLarge(loop, importRadius):
 315                         intercircle.directLoop(not euclidean.getIsInFilledRegion(descendingAreaLoops, loop[0]), loop)
 316                         descendingAreaLoops.append(loop)
 317                         addLoopToPointTable(loop, pointDictionary)
 318         descendingAreaLoops = euclidean.getSimplifiedLoops(descendingAreaLoops, importRadius)
 319         return getLoopsWithCorners(corners, importRadius, descendingAreaLoops, pointDictionary)
 320
 321 def getDescendingAreaOrientedLoops(allPoints, corners, importRadius):
 322         'Get descending area oriented loops which include most of the points.'
 323         return getOrientedLoops(getDescendingAreaLoops(allPoints, corners, importRadius))
 324
 325 def getGeometryOutputByFacesVertexes(faces, vertexes):
 326         'Get geometry output dictionary by faces and vertexes.'
 327         return {'trianglemesh' : {'vertex' : vertexes, 'face' : faces}}
 328
 329 def getGeometryOutputCopy(object):
 330         'Get the geometry output copy.'
 331         objectClass = object.__class__
 332         if objectClass == dict:
 333                 objectCopy = {}
 334                 for key in object:
 335                         objectCopy[key] = getGeometryOutputCopy(object[key])
 336                 return objectCopy
 337         if objectClass == list:
 338                 objectCopy = []
 339                 for value in object:
 340                         objectCopy.append(getGeometryOutputCopy(value))
 341                 return objectCopy
 342         if objectClass == face.Face or objectClass == Vector3 or objectClass == Vector3Index:
 343                 return object.copy()
 344         return object
 345
 346 def getIndexedCellLoopsFromIndexedGrid( grid ):
 347         'Get indexed cell loops from an indexed grid.'
 348         indexedCellLoops = []
 349         for rowIndex in xrange( len( grid ) - 1 ):
 350                 rowBottom = grid[ rowIndex ]
 351                 rowTop = grid[ rowIndex + 1 ]
 352                 for columnIndex in xrange( len( rowBottom ) - 1 ):
 353                         columnIndexEnd = columnIndex + 1
 354                         indexedConvex = []
 355                         indexedConvex.append( rowBottom[ columnIndex ] )
 356                         indexedConvex.append( rowBottom[ columnIndex + 1 ] )
 357                         indexedConvex.append( rowTop[ columnIndex + 1 ] )
 358                         indexedConvex.append( rowTop[ columnIndex ] )
 359                         indexedCellLoops.append( indexedConvex )
 360         return indexedCellLoops
 361
 362 def getIndexedLoopFromIndexedGrid( indexedGrid ):
 363         'Get indexed loop from around the indexed grid.'
 364         indexedLoop = indexedGrid[0][:]
 365         for row in indexedGrid[1 : -1]:
 366                 indexedLoop.append( row[-1] )
 367         indexedLoop += indexedGrid[-1][: : -1]
 368         for row in indexedGrid[ len( indexedGrid ) - 2 : 0 : - 1 ]:
 369                 indexedLoop.append( row[0] )
 370         return indexedLoop
 371
 372 def getInfillDictionary(arounds, aroundWidth, infillInset, infillWidth, pixelTable, rotatedLoops, testLoops=None):
 373         'Get combined fill loops which include most of the points.'
 374         slightlyGreaterThanInfillInset = intercircle.globalIntercircleMultiplier * infillInset
 375         allPoints = intercircle.getPointsFromLoops(rotatedLoops, infillInset, 0.7)
 376         centers = intercircle.getCentersFromPoints(allPoints, slightlyGreaterThanInfillInset)
 377         infillDictionary = {}
 378         for center in centers:
 379                 insetCenter = intercircle.getSimplifiedInsetFromClockwiseLoop(center, infillInset)
 380                 insetPoint = insetCenter[0]
 381                 if len(insetCenter) > 2 and intercircle.getIsLarge(insetCenter, infillInset) and euclidean.getIsInFilledRegion(rotatedLoops, insetPoint):
 382                         around = euclidean.getSimplifiedLoop(center, infillInset)
 383                         euclidean.addLoopToPixelTable(around, pixelTable, aroundWidth)
 384                         arounds.append(around)
 385                         insetLoop = intercircle.getSimplifiedInsetFromClockwiseLoop(center, infillInset)
 386                         euclidean.addXIntersectionsFromLoopForTable(insetLoop, infillDictionary, infillWidth)
 387                         if testLoops != None:
 388                                 testLoops.append(insetLoop)
 389         return infillDictionary
 390
 391 def getInsetPoint( loop, tinyRadius ):
 392         'Get the inset vertex.'
 393         pointIndex = getWideAnglePointIndex(loop)
 394         point = loop[ pointIndex % len(loop) ]
 395         afterPoint = loop[(pointIndex + 1) % len(loop)]
 396         beforePoint = loop[ ( pointIndex - 1 ) % len(loop) ]
 397         afterSegmentNormalized = euclidean.getNormalized( afterPoint - point )
 398         beforeSegmentNormalized = euclidean.getNormalized( beforePoint - point )
 399         afterClockwise = complex( afterSegmentNormalized.imag, - afterSegmentNormalized.real )
 400         beforeWiddershins = complex( - beforeSegmentNormalized.imag, beforeSegmentNormalized.real )
 401         midpoint = afterClockwise + beforeWiddershins
 402         midpointNormalized = midpoint / abs( midpoint )
 403         return point + midpointNormalized * tinyRadius
 404
 405 def getIsPathEntirelyOutsideTriangle(begin, center, end, vector3Path):
 406         'Determine if a path is entirely outside another loop.'
 407         loop = [begin.dropAxis(), center.dropAxis(), end.dropAxis()]
 408         for vector3 in vector3Path:
 409                 point = vector3.dropAxis()
 410                 if euclidean.isPointInsideLoop(loop, point):
 411                         return False
 412         return True
 413
 414 def getIsPointCloseInline(close, loop, point, pointIndex):
 415         'Insert a point into a loop, at the index at which the loop would be shortest.'
 416         afterCenterComplex = loop[pointIndex]
 417         if abs(afterCenterComplex - point) > close:
 418                 return False
 419         afterEndComplex = loop[(pointIndex + 1) % len(loop)]
 420         if not isInline( point, afterCenterComplex, afterEndComplex ):
 421                 return False
 422         beforeCenterComplex = loop[(pointIndex + len(loop) - 1) % len(loop)]
 423         if abs(beforeCenterComplex - point) > close:
 424                 return False
 425         beforeEndComplex = loop[(pointIndex + len(loop) - 2) % len(loop)]
 426         return isInline(point, beforeCenterComplex, beforeEndComplex)
 427
 428 def getLoopsFromCorrectMesh( edges, faces, vertexes, z ):
 429         'Get loops from a carve of a correct mesh.'
 430         remainingEdgeTable = getRemainingEdgeTable(edges, vertexes, z)
 431         remainingValues = remainingEdgeTable.values()
 432         error = False
 433         for edge in remainingValues:
 434                 if len( edge.faceIndexes ) < 2:
 435                         if not hasattr(edge, 'errorReported'):
 436                                 print('Model error(hole): ' + str(vertexes[edge.vertexIndexes[0]]) + ' ' + str(vertexes[edge.vertexIndexes[1]]))
 437                                 edge.errorReported = True
 438                         error = True
 439         if error:
 440                 return []
 441         loops = []
 442         while isPathAdded( edges, faces, loops, remainingEdgeTable, vertexes, z ):
 443                 pass
 444
 445         warning = False
 446         for idx in xrange(0, len(loops)-1):
 447                 loop = loops[idx]
 448                 p0 = loop[-1]
 449                 for p1 in loop:
 450                         if euclidean.isLineIntersectingLoops(loops[idx+1:], p0, p1):
 451                                 print('Warning, the triangle mesh slice intersects itself in getLoopsFromCorrectMesh in triangle_mesh.')
 452                                 print('Model error(intersect): (%f, %f, %f) (%f, %f, %f)' % (p0.real, p0.imag, z, p1.real, p1.imag, z))
 453                                 warning = True
 454                         p0 = p1
 455         if warning:
 456                 return []
 457         return loops
 458 #       untouchables = []
 459 #       for boundingLoop in boundingLoops:
 460 #               if not boundingLoop.isIntersectingList( untouchables ):
 461 #                       untouchables.append( boundingLoop )
 462 #       if len( untouchables ) < len( boundingLoops ):
 463 #               print('This should never happen, the carve layer intersects itself. Something will still be printed, but there is no guarantee that it will be the correct shape.')
 464 #               print('Once the gcode is saved, you should check over the layer with a z of:')
 465 #               print(z)
 466 #       remainingLoops = []
 467 #       for untouchable in untouchables:
 468 #               remainingLoops.append( untouchable.loop )
 469 #       return remainingLoops
 470
 471 def getLoopsFromUnprovenMesh(edges, faces, importRadius, vertexes, z):
 472         'Get loops from a carve of an unproven mesh.'
 473         edgePairTable = {}
 474         corners = []
 475         remainingEdgeTable = getRemainingEdgeTable(edges, vertexes, z)
 476         remainingEdgeTableKeys = remainingEdgeTable.keys()
 477         for remainingEdgeIndexKey in remainingEdgeTable:
 478                 edge = remainingEdgeTable[remainingEdgeIndexKey]
 479                 carveIntersection = getCarveIntersectionFromEdge(edge, vertexes, z)
 480                 corners.append(carveIntersection)
 481                 for edgeFaceIndex in edge.faceIndexes:
 482                         face = faces[edgeFaceIndex]
 483                         for edgeIndex in face.edgeIndexes:
 484                                 addEdgePair(edgePairTable, edges, edgeIndex, remainingEdgeIndexKey, remainingEdgeTable)
 485         allPoints = corners[:]
 486         for edgePairValue in edgePairTable.values():
 487                 addPointsAtZ(edgePairValue, allPoints, importRadius, vertexes, z)
 488         pointTable = {}
 489         return getDescendingAreaLoops(allPoints, corners, importRadius)
 490
 491 def getLoopLayerAppend(loopLayers, layerCount, z):
 492         'Get next z and add extruder loops.'
 493         settings.printProgressByNumber(len(loopLayers), layerCount, 'slice')
 494         loopLayer = euclidean.LoopLayer(z)
 495         loopLayers.append(loopLayer)
 496         return loopLayer
 497
 498 def getLoopsWithCorners(corners, importRadius, loops, pointTable):
 499         'Add corners to the loops.'
 500         for corner in corners:
 501                 if corner not in pointTable:
 502                         addWithLeastLength(importRadius, loops, corner)
 503                         pointTable[corner] = None
 504         return euclidean.getSimplifiedLoops(loops, importRadius)
 505
 506 def getMeldedPillarOutput(loops):
 507         'Get melded pillar output.'
 508         faces = []
 509         vertexes = getUniqueVertexes(loops)
 510         addMeldedPillarByLoops(faces, loops)
 511         return getGeometryOutputByFacesVertexes(faces, vertexes)
 512
 513 def getNewDerivation(elementNode):
 514         'Get new derivation.'
 515         return evaluate.EmptyObject(elementNode)
 516
 517 def getNextEdgeIndexAroundZ(edge, faces, remainingEdgeTable):
 518         'Get the next edge index in the mesh carve.'
 519         for faceIndex in edge.faceIndexes:
 520                 face = faces[faceIndex]
 521                 for edgeIndex in face.edgeIndexes:
 522                         if edgeIndex in remainingEdgeTable:
 523                                 return edgeIndex
 524         return -1
 525
 526 def getOrientedLoops(loops):
 527         'Orient the loops which must be in descending order.'
 528         for loopIndex, loop in enumerate(loops):
 529                 leftPoint = euclidean.getLeftPoint(loop)
 530                 isInFilledRegion = euclidean.getIsInFilledRegion(loops[: loopIndex] + loops[loopIndex + 1 :], leftPoint)
 531                 if isInFilledRegion == euclidean.isWiddershins(loop):
 532                         loop.reverse()
 533         return loops
 534
 535 def getOverlapRatio( loop, pointTable ):
 536         'Get the overlap ratio between the loop and the point table.'
 537         numberOfOverlaps = 0
 538         for point in loop:
 539                 if point in pointTable:
 540                         numberOfOverlaps += 1
 541         return float( numberOfOverlaps ) / float(len(loop))
 542
 543 def getPath( edges, pathIndexes, loop, z ):
 544         'Get the path from the edge intersections.'
 545         path = []
 546         for pathIndexIndex in xrange( len( pathIndexes ) ):
 547                 pathIndex = pathIndexes[ pathIndexIndex ]
 548                 edge = edges[ pathIndex ]
 549                 carveIntersection = getCarveIntersectionFromEdge( edge, loop, z )
 550                 path.append( carveIntersection )
 551         return path
 552
 553 def getPillarOutput(loops):
 554         'Get pillar output.'
 555         faces = []
 556         vertexes = getUniqueVertexes(loops)
 557         addPillarByLoops(faces, loops)
 558         return getGeometryOutputByFacesVertexes(faces, vertexes)
 559
 560 def getPillarsOutput(loopLists):
 561         'Get pillars output.'
 562         pillarsOutput = []
 563         for loopList in loopLists:
 564                 pillarsOutput.append(getPillarOutput(loopList))
 565         return getUnifiedOutput(pillarsOutput)
 566
 567 def getRemainingEdgeTable(edges, vertexes, z):
 568         'Get the remaining edge hashtable.'
 569         remainingEdgeTable = {}
 570         if len(edges) > 0:
 571                 if edges[0].zMinimum == None:
 572                         for edge in edges:
 573                                 setEdgeMaximumMinimum(edge, vertexes)
 574         for edgeIndex in xrange(len(edges)):
 575                 edge = edges[edgeIndex]
 576                 if (edge.zMinimum < z) and (edge.zMaximum > z):
 577                         remainingEdgeTable[edgeIndex] = edge
 578         return remainingEdgeTable
 579
 580 def getRemainingLoopAddFace(faces, remainingLoop):
 581         'Get the remaining loop and add face.'
 582         for indexedVertexIndex, indexedVertex in enumerate(remainingLoop):
 583                 nextIndex = (indexedVertexIndex + 1) % len(remainingLoop)
 584                 previousIndex = (indexedVertexIndex + len(remainingLoop) - 1) % len(remainingLoop)
 585                 nextVertex = remainingLoop[nextIndex]
 586                 previousVertex = remainingLoop[previousIndex]
 587                 remainingPath = euclidean.getAroundLoop((indexedVertexIndex + 2) % len(remainingLoop), previousIndex, remainingLoop)
 588                 if len(remainingLoop) < 4 or getIsPathEntirelyOutsideTriangle(previousVertex, indexedVertex, nextVertex, remainingPath):
 589                         faceConvex = face.Face()
 590                         faceConvex.index = len(faces)
 591                         faceConvex.vertexIndexes.append(indexedVertex.index)
 592                         faceConvex.vertexIndexes.append(nextVertex.index)
 593                         faceConvex.vertexIndexes.append(previousVertex.index)
 594                         faces.append(faceConvex)
 595                         return euclidean.getAroundLoop(nextIndex, indexedVertexIndex, remainingLoop)
 596         print('Warning, could not decompose polygon in getRemainingLoopAddFace in trianglemesh for:')
 597         print(remainingLoop)
 598         return []
 599
 600 def getSharedFace( firstEdge, faces, secondEdge ):
 601         'Get the face which is shared by two edges.'
 602         for firstEdgeFaceIndex in firstEdge.faceIndexes:
 603                 for secondEdgeFaceIndex in secondEdge.faceIndexes:
 604                         if firstEdgeFaceIndex == secondEdgeFaceIndex:
 605                                 return faces[ firstEdgeFaceIndex ]
 606         return None
 607
 608 def getSymmetricXLoop(path, vertexes, x):
 609         'Get symmetrix x loop.'
 610         loop = []
 611         for point in path:
 612                 vector3Index = Vector3Index(len(vertexes), x, point.real, point.imag)
 613                 loop.append(vector3Index)
 614                 vertexes.append(vector3Index)
 615         return loop
 616
 617 def getSymmetricYLoop(path, vertexes, y):
 618         'Get symmetrix y loop.'
 619         loop = []
 620         for point in path:
 621                 vector3Index = Vector3Index(len(vertexes), point.real, y, point.imag)
 622                 loop.append(vector3Index)
 623                 vertexes.append(vector3Index)
 624         return loop
 625
 626 def getUnifiedOutput(outputs):
 627         'Get unified output.'
 628         if len(outputs) < 1:
 629                 return {}
 630         if len(outputs) == 1:
 631                 return outputs[0]
 632         return {'union' : {'shapes' : outputs}}
 633
 634 def getUniqueVertexes(loops):
 635         'Get unique vertexes.'
 636         vertexDictionary = {}
 637         uniqueVertexes = []
 638         for loop in loops:
 639                 for vertexIndex, vertex in enumerate(loop):
 640                         vertexTuple = (vertex.x, vertex.y, vertex.z)
 641                         if vertexTuple in vertexDictionary:
 642                                 loop[vertexIndex] = vertexDictionary[vertexTuple]
 643                         else:
 644                                 if vertex.__class__ == Vector3Index:
 645                                         loop[vertexIndex].index = len(vertexDictionary)
 646                                 else:
 647                                         loop[vertexIndex] = Vector3Index(len(vertexDictionary), vertex.x, vertex.y, vertex.z)
 648                                 vertexDictionary[vertexTuple] = loop[vertexIndex]
 649                                 uniqueVertexes.append(loop[vertexIndex])
 650         return uniqueVertexes
 651
 652 def getWideAnglePointIndex(loop):
 653         'Get a point index which has a wide enough angle, most point indexes have a wide enough angle, this is just to make sure.'
 654         dotProductMinimum = 9999999.9
 655         widestPointIndex = 0
 656         for pointIndex in xrange(len(loop)):
 657                 point = loop[ pointIndex % len(loop) ]
 658                 afterPoint = loop[(pointIndex + 1) % len(loop)]
 659                 beforePoint = loop[ ( pointIndex - 1 ) % len(loop) ]
 660                 afterSegmentNormalized = euclidean.getNormalized( afterPoint - point )
 661                 beforeSegmentNormalized = euclidean.getNormalized( beforePoint - point )
 662                 dotProduct = euclidean.getDotProduct( afterSegmentNormalized, beforeSegmentNormalized )
 663                 if dotProduct < .99:
 664                         return pointIndex
 665                 if dotProduct < dotProductMinimum:
 666                         dotProductMinimum = dotProduct
 667                         widestPointIndex = pointIndex
 668         return widestPointIndex
 669
 670 def isInline( beginComplex, centerComplex, endComplex ):
 671         'Determine if the three complex points form a line.'
 672         centerBeginComplex = beginComplex - centerComplex
 673         centerEndComplex = endComplex - centerComplex
 674         centerBeginLength = abs( centerBeginComplex )
 675         centerEndLength = abs( centerEndComplex )
 676         if centerBeginLength <= 0.0 or centerEndLength <= 0.0:
 677                 return False
 678         centerBeginComplex /= centerBeginLength
 679         centerEndComplex /= centerEndLength
 680         return euclidean.getDotProduct( centerBeginComplex, centerEndComplex ) < -0.999
 681
 682 def isPathAdded( edges, faces, loops, remainingEdgeTable, vertexes, z ):
 683         'Get the path indexes around a triangle mesh carve and add the path to the flat loops.'
 684         if len( remainingEdgeTable ) < 1:
 685                 return False
 686         pathIndexes = []
 687         remainingEdgeIndexKey = remainingEdgeTable.keys()[0]
 688         pathIndexes.append( remainingEdgeIndexKey )
 689         del remainingEdgeTable[remainingEdgeIndexKey]
 690         nextEdgeIndexAroundZ = getNextEdgeIndexAroundZ( edges[remainingEdgeIndexKey], faces, remainingEdgeTable )
 691         while nextEdgeIndexAroundZ != - 1:
 692                 pathIndexes.append( nextEdgeIndexAroundZ )
 693                 del remainingEdgeTable[ nextEdgeIndexAroundZ ]
 694                 nextEdgeIndexAroundZ = getNextEdgeIndexAroundZ( edges[ nextEdgeIndexAroundZ ], faces, remainingEdgeTable )
 695         if len( pathIndexes ) < 3:
 696                 print('Dangling edges, will use intersecting circles to get import layer at height %s' % z)
 697                 for idx in pathIndexes:
 698                         if not hasattr(edges[idx], 'errorReported'):
 699                                 print('Model error(dangle): ' + str(vertexes[edges[idx].vertexIndexes[0]]) + ' ' + str(vertexes[edges[idx].vertexIndexes[1]]))
 700                                 edges[idx].errorReported = True
 701                 del loops[:]
 702                 return False
 703         loops.append( getPath( edges, pathIndexes, vertexes, z ) )
 704         return True
 705
 706 def processElementNode(elementNode):
 707         'Process the xml element.'
 708         evaluate.processArchivable(TriangleMesh, elementNode)
 709
 710 def setEdgeMaximumMinimum(edge, vertexes):
 711         'Set the edge maximum and minimum.'
 712         beginIndex = edge.vertexIndexes[0]
 713         endIndex = edge.vertexIndexes[1]
 714         if beginIndex >= len(vertexes) or endIndex >= len(vertexes):
 715                 print('Warning, there are duplicate vertexes in setEdgeMaximumMinimum in triangle_mesh.')
 716                 print('Something might still be printed, but there is no guarantee that it will be the correct shape.' )
 717                 edge.zMaximum = -987654321.0
 718                 edge.zMinimum = -987654321.0
 719                 return
 720         beginZ = vertexes[beginIndex].z
 721         endZ = vertexes[endIndex].z
 722         edge.zMinimum = min(beginZ, endZ)
 723         edge.zMaximum = max(beginZ, endZ)
 724
 725 def sortLoopsInOrderOfArea(isDescending, loops):
 726         'Sort the loops in the order of area according isDescending.'
 727         loops.sort(key=euclidean.getAreaLoopAbsolute, reverse=isDescending)
 728
 729
 730 class EdgePair:
 731         def __init__(self):
 732                 'Pair of edges on a face.'
 733                 self.edgeIndexes = []
 734                 self.edges = []
 735
 736         def __repr__(self):
 737                 'Get the string representation of this EdgePair.'
 738                 return str( self.edgeIndexes )
 739
 740         def getFromIndexesEdges( self, edgeIndexes, edges ):
 741                 'Initialize from edge indices.'
 742                 self.edgeIndexes = edgeIndexes[:]
 743                 self.edgeIndexes.sort()
 744                 for edgeIndex in self.edgeIndexes:
 745                         self.edges.append( edges[ edgeIndex ] )
 746                 return self
 747
 748
 749 class FaceGenerator:
 750         'A face generator.'
 751         def __init__(self, faces, indexedLoopBottom, indexedLoopTop):
 752                 'Initialize.'
 753                 self.startTop = 0
 754                 if len(indexedLoopBottom) == 0 or len(indexedLoopTop) == 0:
 755                         return
 756                 smallestDistance = 987654321987654321.0
 757                 for pointIndex, point in enumerate(indexedLoopBottom):
 758                         distanceIndex = getClosestDistanceIndexToPoint(point, indexedLoopTop)
 759                         if distanceIndex.distance < smallestDistance:
 760                                 smallestDistance = distanceIndex.distance
 761                                 offsetBottom = pointIndex
 762                                 offsetTop = distanceIndex.index
 763                 self.indexedLoopBottom = indexedLoopBottom[offsetBottom :] + indexedLoopBottom[: offsetBottom]
 764                 self.indexedLoopTop = indexedLoopTop[offsetTop :] + indexedLoopTop[: offsetTop]
 765                 for bottomIndex in xrange(len(self.indexedLoopBottom)):
 766                         self.addFacesByBottomIndex(bottomIndex, faces)
 767                 subsetTop = self.indexedLoopTop[self.startTop :]
 768                 subsetTop.append(self.indexedLoopTop[0])
 769                 addFacesByConvexBottomTopLoop(faces, [self.indexedLoopBottom[0]], subsetTop[: : -1])
 770
 771         def addFacesByBottomIndex(self, bottomIndex, faces):
 772                 'Add faces from the  bottom index to the next index.'
 773                 bottomPoint = self.indexedLoopBottom[bottomIndex % len(self.indexedLoopBottom)]
 774                 bottomPointNext = self.indexedLoopBottom[(bottomIndex + 1) % len(self.indexedLoopBottom)]
 775                 topIndex = self.startTop + getClosestDistanceIndexToPoint(bottomPointNext, self.indexedLoopTop[self.startTop :]).index
 776                 topIndexPlusOne = topIndex + 1
 777                 betweenIndex = self.getBetweenIndex(bottomPoint, bottomPointNext, topIndexPlusOne)
 778                 betweenIndexPlusOne = betweenIndex + 1
 779                 subsetStart = self.indexedLoopTop[self.startTop : betweenIndexPlusOne]
 780                 subsetEnd = self.indexedLoopTop[betweenIndex : topIndexPlusOne]
 781                 addFacesByConvexBottomTopLoop(faces, [bottomPoint], subsetStart[: : -1])
 782                 addFacesByConvexBottomTopLoop(faces, [bottomPoint, bottomPointNext], [self.indexedLoopTop[betweenIndex]])
 783                 addFacesByConvexBottomTopLoop(faces, [bottomPointNext], subsetEnd[: : -1])
 784                 self.startTop = topIndex
 785
 786         def getBetweenIndex(self, bottomPoint, bottomPointNext, topIndexPlusOne):
 787                 'Get the index of the last point along the loop which is closer to the bottomPoint.'
 788                 betweenIndex = self.startTop
 789                 bottomPointComplex = bottomPoint.dropAxis()
 790                 bottomPointNextComplex = bottomPointNext.dropAxis()
 791                 for topPointIndex in xrange(self.startTop, topIndexPlusOne):
 792                         topPointComplex = self.indexedLoopTop[topPointIndex].dropAxis()
 793                         if abs(topPointComplex - bottomPointComplex) > abs(topPointComplex - bottomPointNextComplex):
 794                                 return betweenIndex
 795                         betweenIndex = topPointIndex
 796                 return betweenIndex
 797
 798
 799 class TriangleMesh( group.Group ):
 800         'A triangle mesh.'
 801         def __init__(self):
 802                 'Add empty lists.'
 803                 group.Group.__init__(self)
 804                 self.belowLoops = []
 805                 self.edges = []
 806                 self.faces = []
 807                 self.importCoarseness = 1.0
 808                 self.isCorrectMesh = True
 809                 self.loopLayers = []
 810                 self.oldChainTetragrid = None
 811                 self.transformedVertexes = None
 812                 self.vertexes = []
 813
 814         def addXMLSection(self, depth, output):
 815                 'Add the xml section for this object.'
 816                 xml_simple_writer.addXMLFromVertexes( depth, output, self.vertexes )
 817                 xml_simple_writer.addXMLFromObjects( depth, self.faces, output )
 818
 819         def getCarveBoundaryLayers(self):
 820                 'Get the boundary layers.'
 821                 if self.getMinimumZ() == None:
 822                         return []
 823                 halfHeight = 0.5 * self.layerHeight
 824                 self.zoneArrangement = ZoneArrangement(self.layerHeight, self.getTransformedVertexes())
 825                 layerTop = self.cornerMaximum.z - halfHeight * 0.5
 826                 z = self.cornerMinimum.z + halfHeight
 827                 layerCount = int((layerTop - z) / self.layerHeight) + 1
 828                 while z < layerTop:
 829                         getLoopLayerAppend(self.loopLayers, layerCount, z).loops = self.getLoopsFromMesh(self.zoneArrangement.getEmptyZ(z))
 830                         z += self.layerHeight
 831                 return self.loopLayers
 832
 833         def getCarveCornerMaximum(self):
 834                 'Get the corner maximum of the vertexes.'
 835                 return self.cornerMaximum
 836
 837         def getCarveCornerMinimum(self):
 838                 'Get the corner minimum of the vertexes.'
 839                 return self.cornerMinimum
 840
 841         def getCarveLayerHeight(self):
 842                 'Get the layer height.'
 843                 return self.layerHeight
 844
 845         def getFabmetheusXML(self):
 846                 'Return the fabmetheus XML.'
 847                 return None
 848
 849         def getGeometryOutput(self):
 850                 'Get geometry output dictionary.'
 851                 return getGeometryOutputByFacesVertexes(self.faces, self.vertexes)
 852
 853         def getInterpretationSuffix(self):
 854                 'Return the suffix for a triangle mesh.'
 855                 return 'xml'
 856
 857         def getLoops(self, importRadius, z):
 858                 'Get loops sliced through shape.'
 859                 self.importRadius = importRadius
 860                 return self.getLoopsFromMesh(z)
 861
 862         def getLoopsFromMesh( self, z ):
 863                 'Get loops from a carve of a mesh.'
 864                 originalLoops = []
 865                 self.setEdgesForAllFaces()
 866                 if self.isCorrectMesh:
 867                         originalLoops = getLoopsFromCorrectMesh( self.edges, self.faces, self.getTransformedVertexes(), z )
 868                 if len( originalLoops ) < 1:
 869                         originalLoops = getLoopsFromUnprovenMesh( self.edges, self.faces, self.importRadius, self.getTransformedVertexes(), z )
 870                 loops = euclidean.getSimplifiedLoops(originalLoops, self.importRadius)
 871                 sortLoopsInOrderOfArea(True, loops)
 872                 return getOrientedLoops(loops)
 873
 874         def getMinimumZ(self):
 875                 'Get the minimum z.'
 876                 self.cornerMaximum = Vector3(-987654321.0, -987654321.0, -987654321.0)
 877                 self.cornerMinimum = Vector3(987654321.0, 987654321.0, 987654321.0)
 878                 transformedVertexes = self.getTransformedVertexes()
 879                 if len(transformedVertexes) < 1:
 880                         return None
 881                 for point in transformedVertexes:
 882                         self.cornerMaximum.maximize(point)
 883                         self.cornerMinimum.minimize(point)
 884                 return self.cornerMinimum.z
 885
 886         def getTransformedVertexes(self):
 887                 'Get all transformed vertexes.'
 888                 if self.elementNode == None:
 889                         return self.vertexes
 890                 chainTetragrid = self.getMatrixChainTetragrid()
 891                 if self.oldChainTetragrid != chainTetragrid:
 892                         self.oldChainTetragrid = matrix.getTetragridCopy(chainTetragrid)
 893                         self.transformedVertexes = None
 894                 if self.transformedVertexes == None:
 895                         if len(self.edges) > 0:
 896                                 self.edges[0].zMinimum = None
 897                         self.transformedVertexes = matrix.getTransformedVector3s(chainTetragrid, self.vertexes)
 898                 return self.transformedVertexes
 899
 900         def getTriangleMeshes(self):
 901                 'Get all triangleMeshes.'
 902                 return [self]
 903
 904         def getVertexes(self):
 905                 'Get all vertexes.'
 906                 self.transformedVertexes = None
 907                 return self.vertexes
 908
 909         def setCarveImportRadius( self, importRadius ):
 910                 'Set the import radius.'
 911                 self.importRadius = importRadius
 912
 913         def setCarveIsCorrectMesh( self, isCorrectMesh ):
 914                 'Set the is correct mesh flag.'
 915                 self.isCorrectMesh = isCorrectMesh
 916
 917         def setCarveLayerHeight( self, layerHeight ):
 918                 'Set the layer height.'
 919                 self.layerHeight = layerHeight
 920
 921         def setEdgesForAllFaces(self):
 922                 'Set the face edges of all the faces.'
 923                 edgeTable = {}
 924                 for face in self.faces:
 925                         face.setEdgeIndexesToVertexIndexes( self.edges, edgeTable )
 926
 927
 928 class ZoneArrangement:
 929         'A zone arrangement.'
 930         def __init__(self, layerHeight, vertexes):
 931                 'Initialize the zone interval and the zZone table.'
 932                 self.zoneInterval = layerHeight / math.sqrt(len(vertexes)) / 1000.0
 933                 self.zZoneSet = set()
 934                 for point in vertexes:
 935                         zoneIndexFloat = point.z / self.zoneInterval
 936                         self.zZoneSet.add(math.floor(zoneIndexFloat))
 937                         self.zZoneSet.add(math.ceil(zoneIndexFloat ))
 938
 939         def getEmptyZ(self, z):
 940                 'Get the first z which is not in the zone table.'
 941                 zoneIndex = round(z / self.zoneInterval)
 942                 if zoneIndex not in self.zZoneSet:
 943                         return z
 944                 zoneAround = 1
 945                 while 1:
 946                         zoneDown = zoneIndex - zoneAround
 947                         if zoneDown not in self.zZoneSet:
 948                                 return zoneDown * self.zoneInterval
 949                         zoneUp = zoneIndex + zoneAround
 950                         if zoneUp not in self.zZoneSet:
 951                                 return zoneUp * self.zoneInterval
 952                         zoneAround += 1