2 Triangle Mesh holds the faces and edges of a triangular mesh.
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.
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
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'
31 def addEdgePair( edgePairTable, edges, faceEdgeIndex, remainingEdgeIndex, remainingEdgeTable ):
32 'Add edge pair to the edge pair table.'
33 if faceEdgeIndex == remainingEdgeIndex:
35 if not faceEdgeIndex in remainingEdgeTable:
37 edgePair = EdgePair().getFromIndexesEdges( [ remainingEdgeIndex, faceEdgeIndex ], edges )
38 edgePairTable[ str( edgePair ) ] = edgePair
40 def addFacesByConcaveLoop(faces, indexedLoop):
41 'Add faces from a polygon which is concave.'
42 if len(indexedLoop) < 3:
44 remainingLoop = indexedLoop[:]
45 while len(remainingLoop) > 2:
46 remainingLoop = getRemainingLoopAddFace(faces, remainingLoop)
48 def addFacesByConvex(faces, indexedLoop):
49 'Add faces from a convex polygon.'
50 if len(indexedLoop) < 3:
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)
64 def addFacesByConvexBottomTopLoop(faces, indexedLoopBottom, indexedLoopTop):
65 'Add faces from loops.'
66 if len(indexedLoopBottom) == 0 or len(indexedLoopTop) == 0:
68 for indexedPointIndex in xrange(max(len(indexedLoopBottom), len(indexedLoopTop))):
70 if len(indexedLoopBottom) > 1:
71 indexedConvex.append(indexedLoopBottom[indexedPointIndex])
72 indexedConvex.append(indexedLoopBottom[(indexedPointIndex + 1) % len(indexedLoopBottom)])
74 indexedConvex.append(indexedLoopBottom[0])
75 if len(indexedLoopTop) > 1:
76 indexedConvex.append(indexedLoopTop[(indexedPointIndex + 1) % len(indexedLoopTop)])
77 indexedConvex.append(indexedLoopTop[indexedPointIndex])
79 indexedConvex.append(indexedLoopTop[0])
80 addFacesByConvex(faces, indexedConvex)
82 def addFacesByConvexLoops(faces, indexedLoops):
83 'Add faces from loops.'
84 if len(indexedLoops) < 2:
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)
94 def addFacesByConvexReversed(faces, indexedLoop):
95 'Add faces from a reversed convex polygon.'
96 addFacesByConvex(faces, indexedLoop[: : -1])
98 def addFacesByGrid(faces, grid):
99 'Add faces from grid.'
100 cellTopLoops = getIndexedCellLoopsFromIndexedGrid(grid)
101 for cellTopLoop in cellTopLoops:
102 addFacesByConvex(faces, cellTopLoop)
104 def addFacesByLoop(faces, indexedLoop):
105 'Add faces from a polygon which may be concave.'
106 if len(indexedLoop) < 3:
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)
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)
127 def addFacesByLoopReversed(faces, indexedLoop):
128 'Add faces from a reversed convex polygon.'
129 addFacesByLoop(faces, indexedLoop[: : -1])
131 def addFacesByMeldedConvexLoops(faces, indexedLoops):
132 'Add faces from melded loops.'
133 if len(indexedLoops) < 2:
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)
143 def addLoopToPointTable(loop, pointTable):
144 'Add the points in the loop to the point table.'
146 pointTable[point] = None
148 def addMeldedPillarByLoops(faces, indexedLoops):
149 'Add melded pillar by loops which may be concave.'
150 if len(indexedLoops) < 1:
152 if len(indexedLoops[-1]) < 1:
153 addFacesByMeldedConvexLoops(faces, indexedLoops)
155 addFacesByLoopReversed(faces, indexedLoops[0])
156 addFacesByMeldedConvexLoops(faces, indexedLoops)
157 addFacesByLoop(faces, indexedLoops[-1])
159 def addPillarByLoops(faces, indexedLoops):
160 'Add pillar by loops which may be concave.'
161 if len(indexedLoops) < 1:
163 if len(indexedLoops[-1]) < 1:
164 addFacesByConvexLoops(faces, indexedLoops)
166 addFacesByLoopReversed(faces, indexedLoops[0])
167 addFacesByConvexLoops(faces, indexedLoops)
168 addFacesByLoop(faces, indexedLoops[-1])
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])
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)
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)
191 def addSymmetricXPath(outputs, path, x):
192 'Add x path output to outputs.'
194 loops = [getSymmetricXLoop(path, vertexes, -x), getSymmetricXLoop(path, vertexes, x)]
195 outputs.append(getPillarOutput(loops))
197 def addSymmetricXPaths(outputs, paths, x):
198 'Add x paths outputs to outputs.'
200 addSymmetricXPath(outputs, path, x)
202 def addSymmetricYPath(outputs, path, y):
203 'Add y path output to outputs.'
205 loops = [getSymmetricYLoop(path, vertexes, -y), getSymmetricYLoop(path, vertexes, y)]
206 outputs.append(getPillarOutput(loops))
208 def addSymmetricYPaths(outputs, paths, y):
209 'Add y paths outputs to outputs.'
211 addSymmetricYPath(outputs, path, y)
213 def addVector3Loop(loop, loops, vertexes, z):
214 'Add vector3Loop to loops if there is something in it, for inset and outset.'
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)
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
228 shortestPointIndex = None
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
237 shortestPointIndex = pointIndex
238 if shortestPointIndex != None:
239 shortestLoop.insert( shortestPointIndex, point )
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)
249 def getAddIndexedGrid( grid, vertexes, z ):
250 'Get and add an indexed grid.'
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)
261 def getAddIndexedLoop(loop, vertexes, z):
262 'Get and add an indexed loop.'
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)
271 def getAddIndexedLoops( loop, vertexes, zList ):
272 'Get and add indexed loops.'
275 indexedLoop = getAddIndexedLoop( loop, vertexes, z )
276 indexedLoops.append(indexedLoop)
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)
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
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
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)
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)
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))
325 def getGeometryOutputByFacesVertexes(faces, vertexes):
326 'Get geometry output dictionary by faces and vertexes.'
327 return {'trianglemesh' : {'vertex' : vertexes, 'face' : faces}}
329 def getGeometryOutputCopy(object):
330 'Get the geometry output copy.'
331 objectClass = object.__class__
332 if objectClass == dict:
335 objectCopy[key] = getGeometryOutputCopy(object[key])
337 if objectClass == list:
340 objectCopy.append(getGeometryOutputCopy(value))
342 if objectClass == face.Face or objectClass == Vector3 or objectClass == Vector3Index:
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
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
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] )
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
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
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):
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:
419 afterEndComplex = loop[(pointIndex + 1) % len(loop)]
420 if not isInline( point, afterCenterComplex, afterEndComplex ):
422 beforeCenterComplex = loop[(pointIndex + len(loop) - 1) % len(loop)]
423 if abs(beforeCenterComplex - point) > close:
425 beforeEndComplex = loop[(pointIndex + len(loop) - 2) % len(loop)]
426 return isInline(point, beforeCenterComplex, beforeEndComplex)
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()
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
442 while isPathAdded( edges, faces, loops, remainingEdgeTable, vertexes, z ):
446 for idx in xrange(0, len(loops)-1):
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))
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:')
466 # remainingLoops = []
467 # for untouchable in untouchables:
468 # remainingLoops.append( untouchable.loop )
469 # return remainingLoops
471 def getLoopsFromUnprovenMesh(edges, faces, importRadius, vertexes, z):
472 'Get loops from a carve of an unproven mesh.'
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)
489 return getDescendingAreaLoops(allPoints, corners, importRadius)
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)
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)
506 def getMeldedPillarOutput(loops):
507 'Get melded pillar output.'
509 vertexes = getUniqueVertexes(loops)
510 addMeldedPillarByLoops(faces, loops)
511 return getGeometryOutputByFacesVertexes(faces, vertexes)
513 def getNewDerivation(elementNode):
514 'Get new derivation.'
515 return evaluate.EmptyObject(elementNode)
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:
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):
535 def getOverlapRatio( loop, pointTable ):
536 'Get the overlap ratio between the loop and the point table.'
539 if point in pointTable:
540 numberOfOverlaps += 1
541 return float( numberOfOverlaps ) / float(len(loop))
543 def getPath( edges, pathIndexes, loop, z ):
544 'Get the path from the edge intersections.'
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 )
553 def getPillarOutput(loops):
556 vertexes = getUniqueVertexes(loops)
557 addPillarByLoops(faces, loops)
558 return getGeometryOutputByFacesVertexes(faces, vertexes)
560 def getPillarsOutput(loopLists):
561 'Get pillars output.'
563 for loopList in loopLists:
564 pillarsOutput.append(getPillarOutput(loopList))
565 return getUnifiedOutput(pillarsOutput)
567 def getRemainingEdgeTable(edges, vertexes, z):
568 'Get the remaining edge hashtable.'
569 remainingEdgeTable = {}
571 if edges[0].zMinimum == None:
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
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:')
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 ]
608 def getSymmetricXLoop(path, vertexes, x):
609 'Get symmetrix x loop.'
612 vector3Index = Vector3Index(len(vertexes), x, point.real, point.imag)
613 loop.append(vector3Index)
614 vertexes.append(vector3Index)
617 def getSymmetricYLoop(path, vertexes, y):
618 'Get symmetrix y loop.'
621 vector3Index = Vector3Index(len(vertexes), point.real, y, point.imag)
622 loop.append(vector3Index)
623 vertexes.append(vector3Index)
626 def getUnifiedOutput(outputs):
627 'Get unified output.'
630 if len(outputs) == 1:
632 return {'union' : {'shapes' : outputs}}
634 def getUniqueVertexes(loops):
635 'Get unique vertexes.'
636 vertexDictionary = {}
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]
644 if vertex.__class__ == Vector3Index:
645 loop[vertexIndex].index = len(vertexDictionary)
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
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
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 )
665 if dotProduct < dotProductMinimum:
666 dotProductMinimum = dotProduct
667 widestPointIndex = pointIndex
668 return widestPointIndex
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:
678 centerBeginComplex /= centerBeginLength
679 centerEndComplex /= centerEndLength
680 return euclidean.getDotProduct( centerBeginComplex, centerEndComplex ) < -0.999
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:
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
703 loops.append( getPath( edges, pathIndexes, vertexes, z ) )
706 def processElementNode(elementNode):
707 'Process the xml element.'
708 evaluate.processArchivable(TriangleMesh, elementNode)
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
720 beginZ = vertexes[beginIndex].z
721 endZ = vertexes[endIndex].z
722 edge.zMinimum = min(beginZ, endZ)
723 edge.zMaximum = max(beginZ, endZ)
725 def sortLoopsInOrderOfArea(isDescending, loops):
726 'Sort the loops in the order of area according isDescending.'
727 loops.sort(key=euclidean.getAreaLoopAbsolute, reverse=isDescending)
732 'Pair of edges on a face.'
733 self.edgeIndexes = []
737 'Get the string representation of this EdgePair.'
738 return str( self.edgeIndexes )
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 ] )
751 def __init__(self, faces, indexedLoopBottom, indexedLoopTop):
754 if len(indexedLoopBottom) == 0 or len(indexedLoopTop) == 0:
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])
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
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):
795 betweenIndex = topPointIndex
799 class TriangleMesh( group.Group ):
803 group.Group.__init__(self)
807 self.importCoarseness = 1.0
808 self.isCorrectMesh = True
810 self.oldChainTetragrid = None
811 self.transformedVertexes = None
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 )
819 def getCarveBoundaryLayers(self):
820 'Get the boundary layers.'
821 if self.getMinimumZ() == None:
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
829 getLoopLayerAppend(self.loopLayers, layerCount, z).loops = self.getLoopsFromMesh(self.zoneArrangement.getEmptyZ(z))
830 z += self.layerHeight
831 return self.loopLayers
833 def getCarveCornerMaximum(self):
834 'Get the corner maximum of the vertexes.'
835 return self.cornerMaximum
837 def getCarveCornerMinimum(self):
838 'Get the corner minimum of the vertexes.'
839 return self.cornerMinimum
841 def getCarveLayerHeight(self):
842 'Get the layer height.'
843 return self.layerHeight
845 def getFabmetheusXML(self):
846 'Return the fabmetheus XML.'
849 def getGeometryOutput(self):
850 'Get geometry output dictionary.'
851 return getGeometryOutputByFacesVertexes(self.faces, self.vertexes)
853 def getInterpretationSuffix(self):
854 'Return the suffix for a triangle mesh.'
857 def getLoops(self, importRadius, z):
858 'Get loops sliced through shape.'
859 self.importRadius = importRadius
860 return self.getLoopsFromMesh(z)
862 def getLoopsFromMesh( self, z ):
863 'Get loops from a carve of a mesh.'
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)
874 def getMinimumZ(self):
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:
881 for point in transformedVertexes:
882 self.cornerMaximum.maximize(point)
883 self.cornerMinimum.minimize(point)
884 return self.cornerMinimum.z
886 def getTransformedVertexes(self):
887 'Get all transformed vertexes.'
888 if self.elementNode == None:
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
900 def getTriangleMeshes(self):
901 'Get all triangleMeshes.'
904 def getVertexes(self):
906 self.transformedVertexes = None
909 def setCarveImportRadius( self, importRadius ):
910 'Set the import radius.'
911 self.importRadius = importRadius
913 def setCarveIsCorrectMesh( self, isCorrectMesh ):
914 'Set the is correct mesh flag.'
915 self.isCorrectMesh = isCorrectMesh
917 def setCarveLayerHeight( self, layerHeight ):
918 'Set the layer height.'
919 self.layerHeight = layerHeight
921 def setEdgesForAllFaces(self):
922 'Set the face edges of all the faces.'
924 for face in self.faces:
925 face.setEdgeIndexesToVertexIndexes( self.edges, edgeTable )
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 ))
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:
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