Cura/cura_sf/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                                 if not warning:
 452                                         print('Warning, the triangle mesh slice intersects itself in getLoopsFromCorrectMesh in triangle_mesh.')
 453                                 print('Model error(intersect): (%f, %f, %f) (%f, %f, %f)' % (p0.real, p0.imag, z, p1.real, p1.imag, z))
 454                                 warning = True
 455                         p0 = p1
 456         if warning:
 457                 return []
 458         return loops
 459 #       untouchables = []
 460 #       for boundingLoop in boundingLoops:
 461 #               if not boundingLoop.isIntersectingList( untouchables ):
 462 #                       untouchables.append( boundingLoop )
 463 #       if len( untouchables ) < len( boundingLoops ):
 464 #               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.')
 465 #               print('Once the gcode is saved, you should check over the layer with a z of:')
 466 #               print(z)
 467 #       remainingLoops = []
 468 #       for untouchable in untouchables:
 469 #               remainingLoops.append( untouchable.loop )
 470 #       return remainingLoops
 471
 472 def getLoopsFromUnprovenMesh(edges, faces, importRadius, vertexes, z):
 473         'Get loops from a carve of an unproven mesh.'
 474         edgePairTable = {}
 475         corners = []
 476         remainingEdgeTable = getRemainingEdgeTable(edges, vertexes, z)
 477         remainingEdgeTableKeys = remainingEdgeTable.keys()
 478         for remainingEdgeIndexKey in remainingEdgeTable:
 479                 edge = remainingEdgeTable[remainingEdgeIndexKey]
 480                 carveIntersection = getCarveIntersectionFromEdge(edge, vertexes, z)
 481                 corners.append(carveIntersection)
 482                 for edgeFaceIndex in edge.faceIndexes:
 483                         face = faces[edgeFaceIndex]
 484                         for edgeIndex in face.edgeIndexes:
 485                                 addEdgePair(edgePairTable, edges, edgeIndex, remainingEdgeIndexKey, remainingEdgeTable)
 486         allPoints = corners[:]
 487         for edgePairValue in edgePairTable.values():
 488                 addPointsAtZ(edgePairValue, allPoints, importRadius, vertexes, z)
 489         pointTable = {}
 490         return getDescendingAreaLoops(allPoints, corners, importRadius)
 491
 492 def getLoopLayerAppend(loopLayers, layerCount, z):
 493         'Get next z and add extruder loops.'
 494         settings.printProgressByNumber(len(loopLayers), layerCount, 'slice')
 495         loopLayer = euclidean.LoopLayer(z)
 496         loopLayers.append(loopLayer)
 497         return loopLayer
 498
 499 def getLoopsWithCorners(corners, importRadius, loops, pointTable):
 500         'Add corners to the loops.'
 501         for corner in corners:
 502                 if corner not in pointTable:
 503                         addWithLeastLength(importRadius, loops, corner)
 504                         pointTable[corner] = None
 505         return euclidean.getSimplifiedLoops(loops, importRadius)
 506
 507 def getMeldedPillarOutput(loops):
 508         'Get melded pillar output.'
 509         faces = []
 510         vertexes = getUniqueVertexes(loops)
 511         addMeldedPillarByLoops(faces, loops)
 512         return getGeometryOutputByFacesVertexes(faces, vertexes)
 513
 514 def getNewDerivation(elementNode):
 515         'Get new derivation.'
 516         return evaluate.EmptyObject(elementNode)
 517
 518 def getNextEdgeIndexAroundZ(edge, faces, remainingEdgeTable):
 519         'Get the next edge index in the mesh carve.'
 520         for faceIndex in edge.faceIndexes:
 521                 face = faces[faceIndex]
 522                 for edgeIndex in face.edgeIndexes:
 523                         if edgeIndex in remainingEdgeTable:
 524                                 return edgeIndex
 525         return -1
 526
 527 def getOrientedLoops(loops):
 528         'Orient the loops which must be in descending order.'
 529         for loopIndex, loop in enumerate(loops):
 530                 leftPoint = euclidean.getLeftPoint(loop)
 531                 isInFilledRegion = euclidean.getIsInFilledRegion(loops[: loopIndex] + loops[loopIndex + 1 :], leftPoint)
 532                 if isInFilledRegion == euclidean.isWiddershins(loop):
 533                         loop.reverse()
 534         return loops
 535
 536 def getOverlapRatio( loop, pointTable ):
 537         'Get the overlap ratio between the loop and the point table.'
 538         numberOfOverlaps = 0
 539         for point in loop:
 540                 if point in pointTable:
 541                         numberOfOverlaps += 1
 542         return float( numberOfOverlaps ) / float(len(loop))
 543
 544 def getPath( edges, pathIndexes, loop, z ):
 545         'Get the path from the edge intersections.'
 546         path = []
 547         for pathIndexIndex in xrange( len( pathIndexes ) ):
 548                 pathIndex = pathIndexes[ pathIndexIndex ]
 549                 edge = edges[ pathIndex ]
 550                 carveIntersection = getCarveIntersectionFromEdge( edge, loop, z )
 551                 path.append( carveIntersection )
 552         return path
 553
 554 def getPillarOutput(loops):
 555         'Get pillar output.'
 556         faces = []
 557         vertexes = getUniqueVertexes(loops)
 558         addPillarByLoops(faces, loops)
 559         return getGeometryOutputByFacesVertexes(faces, vertexes)
 560
 561 def getPillarsOutput(loopLists):
 562         'Get pillars output.'
 563         pillarsOutput = []
 564         for loopList in loopLists:
 565                 pillarsOutput.append(getPillarOutput(loopList))
 566         return getUnifiedOutput(pillarsOutput)
 567
 568 def getRemainingEdgeTable(edges, vertexes, z):
 569         'Get the remaining edge hashtable.'
 570         remainingEdgeTable = {}
 571         if len(edges) > 0:
 572                 if edges[0].zMinimum == None:
 573                         for edge in edges:
 574                                 setEdgeMaximumMinimum(edge, vertexes)
 575         for edgeIndex in xrange(len(edges)):
 576                 edge = edges[edgeIndex]
 577                 if (edge.zMinimum < z) and (edge.zMaximum > z):
 578                         remainingEdgeTable[edgeIndex] = edge
 579         return remainingEdgeTable
 580
 581 def getRemainingLoopAddFace(faces, remainingLoop):
 582         'Get the remaining loop and add face.'
 583         for indexedVertexIndex, indexedVertex in enumerate(remainingLoop):
 584                 nextIndex = (indexedVertexIndex + 1) % len(remainingLoop)
 585                 previousIndex = (indexedVertexIndex + len(remainingLoop) - 1) % len(remainingLoop)
 586                 nextVertex = remainingLoop[nextIndex]
 587                 previousVertex = remainingLoop[previousIndex]
 588                 remainingPath = euclidean.getAroundLoop((indexedVertexIndex + 2) % len(remainingLoop), previousIndex, remainingLoop)
 589                 if len(remainingLoop) < 4 or getIsPathEntirelyOutsideTriangle(previousVertex, indexedVertex, nextVertex, remainingPath):
 590                         faceConvex = face.Face()
 591                         faceConvex.index = len(faces)
 592                         faceConvex.vertexIndexes.append(indexedVertex.index)
 593                         faceConvex.vertexIndexes.append(nextVertex.index)
 594                         faceConvex.vertexIndexes.append(previousVertex.index)
 595                         faces.append(faceConvex)
 596                         return euclidean.getAroundLoop(nextIndex, indexedVertexIndex, remainingLoop)
 597         print('Warning, could not decompose polygon in getRemainingLoopAddFace in trianglemesh for:')
 598         print(remainingLoop)
 599         return []
 600
 601 def getSharedFace( firstEdge, faces, secondEdge ):
 602         'Get the face which is shared by two edges.'
 603         for firstEdgeFaceIndex in firstEdge.faceIndexes:
 604                 for secondEdgeFaceIndex in secondEdge.faceIndexes:
 605                         if firstEdgeFaceIndex == secondEdgeFaceIndex:
 606                                 return faces[ firstEdgeFaceIndex ]
 607         return None
 608
 609 def getSymmetricXLoop(path, vertexes, x):
 610         'Get symmetrix x loop.'
 611         loop = []
 612         for point in path:
 613                 vector3Index = Vector3Index(len(vertexes), x, point.real, point.imag)
 614                 loop.append(vector3Index)
 615                 vertexes.append(vector3Index)
 616         return loop
 617
 618 def getSymmetricYLoop(path, vertexes, y):
 619         'Get symmetrix y loop.'
 620         loop = []
 621         for point in path:
 622                 vector3Index = Vector3Index(len(vertexes), point.real, y, point.imag)
 623                 loop.append(vector3Index)
 624                 vertexes.append(vector3Index)
 625         return loop
 626
 627 def getUnifiedOutput(outputs):
 628         'Get unified output.'
 629         if len(outputs) < 1:
 630                 return {}
 631         if len(outputs) == 1:
 632                 return outputs[0]
 633         return {'union' : {'shapes' : outputs}}
 634
 635 def getUniqueVertexes(loops):
 636         'Get unique vertexes.'
 637         vertexDictionary = {}
 638         uniqueVertexes = []
 639         for loop in loops:
 640                 for vertexIndex, vertex in enumerate(loop):
 641                         vertexTuple = (vertex.x, vertex.y, vertex.z)
 642                         if vertexTuple in vertexDictionary:
 643                                 loop[vertexIndex] = vertexDictionary[vertexTuple]
 644                         else:
 645                                 if vertex.__class__ == Vector3Index:
 646                                         loop[vertexIndex].index = len(vertexDictionary)
 647                                 else:
 648                                         loop[vertexIndex] = Vector3Index(len(vertexDictionary), vertex.x, vertex.y, vertex.z)
 649                                 vertexDictionary[vertexTuple] = loop[vertexIndex]
 650                                 uniqueVertexes.append(loop[vertexIndex])
 651         return uniqueVertexes
 652
 653 def getWideAnglePointIndex(loop):
 654         'Get a point index which has a wide enough angle, most point indexes have a wide enough angle, this is just to make sure.'
 655         dotProductMinimum = 9999999.9
 656         widestPointIndex = 0
 657         for pointIndex in xrange(len(loop)):
 658                 point = loop[ pointIndex % len(loop) ]
 659                 afterPoint = loop[(pointIndex + 1) % len(loop)]
 660                 beforePoint = loop[ ( pointIndex - 1 ) % len(loop) ]
 661                 afterSegmentNormalized = euclidean.getNormalized( afterPoint - point )
 662                 beforeSegmentNormalized = euclidean.getNormalized( beforePoint - point )
 663                 dotProduct = euclidean.getDotProduct( afterSegmentNormalized, beforeSegmentNormalized )
 664                 if dotProduct < .99:
 665                         return pointIndex
 666                 if dotProduct < dotProductMinimum:
 667                         dotProductMinimum = dotProduct
 668                         widestPointIndex = pointIndex
 669         return widestPointIndex
 670
 671 def isInline( beginComplex, centerComplex, endComplex ):
 672         'Determine if the three complex points form a line.'
 673         centerBeginComplex = beginComplex - centerComplex
 674         centerEndComplex = endComplex - centerComplex
 675         centerBeginLength = abs( centerBeginComplex )
 676         centerEndLength = abs( centerEndComplex )
 677         if centerBeginLength <= 0.0 or centerEndLength <= 0.0:
 678                 return False
 679         centerBeginComplex /= centerBeginLength
 680         centerEndComplex /= centerEndLength
 681         return euclidean.getDotProduct( centerBeginComplex, centerEndComplex ) < -0.999
 682
 683 def isPathAdded( edges, faces, loops, remainingEdgeTable, vertexes, z ):
 684         'Get the path indexes around a triangle mesh carve and add the path to the flat loops.'
 685         if len( remainingEdgeTable ) < 1:
 686                 return False
 687         pathIndexes = []
 688         remainingEdgeIndexKey = remainingEdgeTable.keys()[0]
 689         pathIndexes.append( remainingEdgeIndexKey )
 690         del remainingEdgeTable[remainingEdgeIndexKey]
 691         nextEdgeIndexAroundZ = getNextEdgeIndexAroundZ( edges[remainingEdgeIndexKey], faces, remainingEdgeTable )
 692         while nextEdgeIndexAroundZ != - 1:
 693                 pathIndexes.append( nextEdgeIndexAroundZ )
 694                 del remainingEdgeTable[ nextEdgeIndexAroundZ ]
 695                 nextEdgeIndexAroundZ = getNextEdgeIndexAroundZ( edges[ nextEdgeIndexAroundZ ], faces, remainingEdgeTable )
 696         if len( pathIndexes ) < 3:
 697                 print('Dangling edges, will use intersecting circles to get import layer at height %s' % z)
 698                 for idx in pathIndexes:
 699                         if not hasattr(edges[idx], 'errorReported'):
 700                                 print('Model error(dangle): ' + str(vertexes[edges[idx].vertexIndexes[0]]) + ' ' + str(vertexes[edges[idx].vertexIndexes[1]]))
 701                                 edges[idx].errorReported = True
 702                 del loops[:]
 703                 return False
 704         loops.append( getPath( edges, pathIndexes, vertexes, z ) )
 705         return True
 706
 707 def processElementNode(elementNode):
 708         'Process the xml element.'
 709         evaluate.processArchivable(TriangleMesh, elementNode)
 710
 711 def setEdgeMaximumMinimum(edge, vertexes):
 712         'Set the edge maximum and minimum.'
 713         beginIndex = edge.vertexIndexes[0]
 714         endIndex = edge.vertexIndexes[1]
 715         if beginIndex >= len(vertexes) or endIndex >= len(vertexes):
 716                 print('Warning, there are duplicate vertexes in setEdgeMaximumMinimum in triangle_mesh.')
 717                 print('Something might still be printed, but there is no guarantee that it will be the correct shape.' )
 718                 edge.zMaximum = -987654321.0
 719                 edge.zMinimum = -987654321.0
 720                 return
 721         beginZ = vertexes[beginIndex].z
 722         endZ = vertexes[endIndex].z
 723         edge.zMinimum = min(beginZ, endZ)
 724         edge.zMaximum = max(beginZ, endZ)
 725
 726 def sortLoopsInOrderOfArea(isDescending, loops):
 727         'Sort the loops in the order of area according isDescending.'
 728         loops.sort(key=euclidean.getAreaLoopAbsolute, reverse=isDescending)
 729
 730
 731 class EdgePair:
 732         def __init__(self):
 733                 'Pair of edges on a face.'
 734                 self.edgeIndexes = []
 735                 self.edges = []
 736
 737         def __repr__(self):
 738                 'Get the string representation of this EdgePair.'
 739                 return str( self.edgeIndexes )
 740
 741         def getFromIndexesEdges( self, edgeIndexes, edges ):
 742                 'Initialize from edge indices.'
 743                 self.edgeIndexes = edgeIndexes[:]
 744                 self.edgeIndexes.sort()
 745                 for edgeIndex in self.edgeIndexes:
 746                         self.edges.append( edges[ edgeIndex ] )
 747                 return self
 748
 749
 750 class FaceGenerator:
 751         'A face generator.'
 752         def __init__(self, faces, indexedLoopBottom, indexedLoopTop):
 753                 'Initialize.'
 754                 self.startTop = 0
 755                 if len(indexedLoopBottom) == 0 or len(indexedLoopTop) == 0:
 756                         return
 757                 smallestDistance = 987654321987654321.0
 758                 for pointIndex, point in enumerate(indexedLoopBottom):
 759                         distanceIndex = getClosestDistanceIndexToPoint(point, indexedLoopTop)
 760                         if distanceIndex.distance < smallestDistance:
 761                                 smallestDistance = distanceIndex.distance
 762                                 offsetBottom = pointIndex
 763                                 offsetTop = distanceIndex.index
 764                 self.indexedLoopBottom = indexedLoopBottom[offsetBottom :] + indexedLoopBottom[: offsetBottom]
 765                 self.indexedLoopTop = indexedLoopTop[offsetTop :] + indexedLoopTop[: offsetTop]
 766                 for bottomIndex in xrange(len(self.indexedLoopBottom)):
 767                         self.addFacesByBottomIndex(bottomIndex, faces)
 768                 subsetTop = self.indexedLoopTop[self.startTop :]
 769                 subsetTop.append(self.indexedLoopTop[0])
 770                 addFacesByConvexBottomTopLoop(faces, [self.indexedLoopBottom[0]], subsetTop[: : -1])
 771
 772         def addFacesByBottomIndex(self, bottomIndex, faces):
 773                 'Add faces from the  bottom index to the next index.'
 774                 bottomPoint = self.indexedLoopBottom[bottomIndex % len(self.indexedLoopBottom)]
 775                 bottomPointNext = self.indexedLoopBottom[(bottomIndex + 1) % len(self.indexedLoopBottom)]
 776                 topIndex = self.startTop + getClosestDistanceIndexToPoint(bottomPointNext, self.indexedLoopTop[self.startTop :]).index
 777                 topIndexPlusOne = topIndex + 1
 778                 betweenIndex = self.getBetweenIndex(bottomPoint, bottomPointNext, topIndexPlusOne)
 779                 betweenIndexPlusOne = betweenIndex + 1
 780                 subsetStart = self.indexedLoopTop[self.startTop : betweenIndexPlusOne]
 781                 subsetEnd = self.indexedLoopTop[betweenIndex : topIndexPlusOne]
 782                 addFacesByConvexBottomTopLoop(faces, [bottomPoint], subsetStart[: : -1])
 783                 addFacesByConvexBottomTopLoop(faces, [bottomPoint, bottomPointNext], [self.indexedLoopTop[betweenIndex]])
 784                 addFacesByConvexBottomTopLoop(faces, [bottomPointNext], subsetEnd[: : -1])
 785                 self.startTop = topIndex
 786
 787         def getBetweenIndex(self, bottomPoint, bottomPointNext, topIndexPlusOne):
 788                 'Get the index of the last point along the loop which is closer to the bottomPoint.'
 789                 betweenIndex = self.startTop
 790                 bottomPointComplex = bottomPoint.dropAxis()
 791                 bottomPointNextComplex = bottomPointNext.dropAxis()
 792                 for topPointIndex in xrange(self.startTop, topIndexPlusOne):
 793                         topPointComplex = self.indexedLoopTop[topPointIndex].dropAxis()
 794                         if abs(topPointComplex - bottomPointComplex) > abs(topPointComplex - bottomPointNextComplex):
 795                                 return betweenIndex
 796                         betweenIndex = topPointIndex
 797                 return betweenIndex
 798
 799
 800 class TriangleMesh( group.Group ):
 801         'A triangle mesh.'
 802         def __init__(self):
 803                 'Add empty lists.'
 804                 group.Group.__init__(self)
 805                 self.belowLoops = []
 806                 self.edges = []
 807                 self.faces = []
 808                 self.importCoarseness = 1.0
 809                 self.isCorrectMesh = True
 810                 self.loopLayers = []
 811                 self.oldChainTetragrid = None
 812                 self.transformedVertexes = None
 813                 self.vertexes = []
 814
 815         def addXMLSection(self, depth, output):
 816                 'Add the xml section for this object.'
 817                 xml_simple_writer.addXMLFromVertexes( depth, output, self.vertexes )
 818                 xml_simple_writer.addXMLFromObjects( depth, self.faces, output )
 819
 820         def getCarveBoundaryLayers(self):
 821                 'Get the boundary layers.'
 822                 if self.getMinimumZ() == None:
 823                         return []
 824                 halfHeight = 0.5 * self.layerHeight
 825                 self.zoneArrangement = ZoneArrangement(self.layerHeight, self.getTransformedVertexes())
 826                 layerTop = self.cornerMaximum.z - halfHeight * 0.5
 827                 z = self.cornerMinimum.z + halfHeight
 828                 layerCount = int((layerTop - z) / self.layerHeight) + 1
 829                 while z < layerTop:
 830                         getLoopLayerAppend(self.loopLayers, layerCount, z).loops = self.getLoopsFromMesh(self.zoneArrangement.getEmptyZ(z))
 831                         z += self.layerHeight
 832                 return self.loopLayers
 833
 834         def getCarveCornerMaximum(self):
 835                 'Get the corner maximum of the vertexes.'
 836                 return self.cornerMaximum
 837
 838         def getCarveCornerMinimum(self):
 839                 'Get the corner minimum of the vertexes.'
 840                 return self.cornerMinimum
 841
 842         def getCarveLayerHeight(self):
 843                 'Get the layer height.'
 844                 return self.layerHeight
 845
 846         def getFabmetheusXML(self):
 847                 'Return the fabmetheus XML.'
 848                 return None
 849
 850         def getGeometryOutput(self):
 851                 'Get geometry output dictionary.'
 852                 return getGeometryOutputByFacesVertexes(self.faces, self.vertexes)
 853
 854         def getInterpretationSuffix(self):
 855                 'Return the suffix for a triangle mesh.'
 856                 return 'xml'
 857
 858         def getLoops(self, importRadius, z):
 859                 'Get loops sliced through shape.'
 860                 self.importRadius = importRadius
 861                 return self.getLoopsFromMesh(z)
 862
 863         def getLoopsFromMesh( self, z ):
 864                 'Get loops from a carve of a mesh.'
 865                 originalLoops = []
 866                 self.setEdgesForAllFaces()
 867                 if self.isCorrectMesh:
 868                         originalLoops = getLoopsFromCorrectMesh( self.edges, self.faces, self.getTransformedVertexes(), z )
 869                 if len( originalLoops ) < 1:
 870                         originalLoops = getLoopsFromUnprovenMesh( self.edges, self.faces, self.importRadius, self.getTransformedVertexes(), z )
 871                 loops = euclidean.getSimplifiedLoops(originalLoops, self.importRadius)
 872                 sortLoopsInOrderOfArea(True, loops)
 873                 return getOrientedLoops(loops)
 874
 875         def getMinimumZ(self):
 876                 'Get the minimum z.'
 877                 self.cornerMaximum = Vector3(-987654321.0, -987654321.0, -987654321.0)
 878                 self.cornerMinimum = Vector3(987654321.0, 987654321.0, 987654321.0)
 879                 transformedVertexes = self.getTransformedVertexes()
 880                 if len(transformedVertexes) < 1:
 881                         return None
 882                 for point in transformedVertexes:
 883                         self.cornerMaximum.maximize(point)
 884                         self.cornerMinimum.minimize(point)
 885                 return self.cornerMinimum.z
 886
 887         def getTransformedVertexes(self):
 888                 'Get all transformed vertexes.'
 889                 if self.elementNode == None:
 890                         return self.vertexes
 891                 chainTetragrid = self.getMatrixChainTetragrid()
 892                 if self.oldChainTetragrid != chainTetragrid:
 893                         self.oldChainTetragrid = matrix.getTetragridCopy(chainTetragrid)
 894                         self.transformedVertexes = None
 895                 if self.transformedVertexes == None:
 896                         if len(self.edges) > 0:
 897                                 self.edges[0].zMinimum = None
 898                         self.transformedVertexes = matrix.getTransformedVector3s(chainTetragrid, self.vertexes)
 899                 return self.transformedVertexes
 900
 901         def getTriangleMeshes(self):
 902                 'Get all triangleMeshes.'
 903                 return [self]
 904
 905         def getVertexes(self):
 906                 'Get all vertexes.'
 907                 self.transformedVertexes = None
 908                 return self.vertexes
 909
 910         def setCarveImportRadius( self, importRadius ):
 911                 'Set the import radius.'
 912                 self.importRadius = importRadius
 913
 914         def setCarveIsCorrectMesh( self, isCorrectMesh ):
 915                 'Set the is correct mesh flag.'
 916                 self.isCorrectMesh = isCorrectMesh
 917
 918         def setCarveLayerHeight( self, layerHeight ):
 919                 'Set the layer height.'
 920                 self.layerHeight = layerHeight
 921
 922         def setEdgesForAllFaces(self):
 923                 'Set the face edges of all the faces.'
 924                 edgeTable = {}
 925                 for face in self.faces:
 926                         face.setEdgeIndexesToVertexIndexes( self.edges, edgeTable )
 927
 928
 929 class ZoneArrangement:
 930         'A zone arrangement.'
 931         def __init__(self, layerHeight, vertexes):
 932                 'Initialize the zone interval and the zZone table.'
 933                 self.zoneInterval = layerHeight / math.sqrt(len(vertexes)) / 1000.0
 934                 self.zZoneSet = set()
 935                 for point in vertexes:
 936                         zoneIndexFloat = point.z / self.zoneInterval
 937                         self.zZoneSet.add(math.floor(zoneIndexFloat))
 938                         self.zZoneSet.add(math.ceil(zoneIndexFloat ))
 939
 940         def getEmptyZ(self, z):
 941                 'Get the first z which is not in the zone table.'
 942                 zoneIndex = round(z / self.zoneInterval)
 943                 if zoneIndex not in self.zZoneSet:
 944                         return z
 945                 zoneAround = 1
 946                 while 1:
 947                         zoneDown = zoneIndex - zoneAround
 948                         if zoneDown not in self.zZoneSet:
 949                                 return zoneDown * self.zoneInterval
 950                         zoneUp = zoneIndex + zoneAround
 951                         if zoneUp not in self.zZoneSet:
 952                                 return zoneUp * self.zoneInterval
 953                         zoneAround += 1