chiark / gitweb /
c913e7d3935177f4131f8087a301cb7119090289
[cura.git] / Cura / fabmetheus_utilities / geometry / manipulation_paths / overhang.py
1 """
2 Add material to support overhang or remove material at the overhang angle.
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.creation import lineation
11 from fabmetheus_utilities.geometry.geometry_utilities.evaluate_elements import setting
12 from fabmetheus_utilities.geometry.geometry_utilities import evaluate
13 from fabmetheus_utilities.vector3 import Vector3
14 from fabmetheus_utilities import euclidean
15 import math
16
17
18 __author__ = 'Enrique Perez (perez_enrique@yahoo.com)'
19 __credits__ = 'Art of Illusion <http://www.artofillusion.org/>'
20 __date__ = '$Date: 2008/02/05 $'
21 __license__ = 'GNU Affero General Public License http://www.gnu.org/licenses/agpl.html'
22
23
24 globalExecutionOrder = 100
25
26
27 def addUnsupportedPointIndexes( alongAway ):
28         "Add the indexes of the unsupported points."
29         addedUnsupportedPointIndexes = []
30         for pointIndex in xrange( len( alongAway.loop ) ):
31                 point = alongAway.loop[pointIndex]
32                 if pointIndex not in alongAway.unsupportedPointIndexes:
33                         if not alongAway.getIsClockwisePointSupported(point):
34                                 alongAway.unsupportedPointIndexes.append( pointIndex )
35                                 addedUnsupportedPointIndexes.append( pointIndex )
36         for pointIndex in addedUnsupportedPointIndexes:
37                 point = alongAway.loop[pointIndex]
38                 point.y += alongAway.maximumYPlus
39
40 def alterClockwiseSupportedPath( alongAway, elementNode ):
41         "Get clockwise path with overhangs carved out."
42         alongAway.bottomPoints = []
43         alongAway.overhangSpan = setting.getOverhangSpan(elementNode)
44         maximumY = - 987654321.0
45         minimumYPointIndex = 0
46         for pointIndex in xrange( len( alongAway.loop ) ):
47                 point = alongAway.loop[pointIndex]
48                 if point.y < alongAway.loop[ minimumYPointIndex ].y:
49                         minimumYPointIndex = pointIndex
50                 maximumY = max( maximumY, point.y )
51         alongAway.maximumYPlus = 2.0 * ( maximumY - alongAway.loop[ minimumYPointIndex ].y )
52         alongAway.loop = euclidean.getAroundLoop( minimumYPointIndex, minimumYPointIndex, alongAway.loop )
53         overhangClockwise = OverhangClockwise( alongAway )
54         alongAway.unsupportedPointIndexes = []
55         oldUnsupportedPointIndexesLength = - 987654321.0
56         while len( alongAway.unsupportedPointIndexes ) > oldUnsupportedPointIndexesLength:
57                 oldUnsupportedPointIndexesLength = len( alongAway.unsupportedPointIndexes )
58                 addUnsupportedPointIndexes( alongAway )
59         for pointIndex in alongAway.unsupportedPointIndexes:
60                 point = alongAway.loop[pointIndex]
61                 point.y -= alongAway.maximumYPlus
62         alongAway.unsupportedPointIndexes.sort()
63         alongAway.unsupportedPointIndexLists = []
64         oldUnsupportedPointIndex = - 987654321.0
65         unsupportedPointIndexList = None
66         for unsupportedPointIndex in alongAway.unsupportedPointIndexes:
67                 if unsupportedPointIndex > oldUnsupportedPointIndex + 1:
68                         unsupportedPointIndexList = []
69                         alongAway.unsupportedPointIndexLists.append( unsupportedPointIndexList )
70                 oldUnsupportedPointIndex = unsupportedPointIndex
71                 unsupportedPointIndexList.append( unsupportedPointIndex )
72         alongAway.unsupportedPointIndexLists.reverse()
73         for unsupportedPointIndexList in alongAway.unsupportedPointIndexLists:
74                 overhangClockwise.alterLoop( unsupportedPointIndexList )
75
76 def alterWiddershinsSupportedPath( alongAway, close ):
77         "Get widdershins path with overhangs filled in."
78         alongAway.bottomPoints = []
79         alongAway.minimumY = getMinimumYByPath( alongAway.loop )
80         for point in alongAway.loop:
81                 if point.y - alongAway.minimumY < close:
82                         alongAway.addToBottomPoints(point)
83         ascendingYPoints = alongAway.loop[:]
84         ascendingYPoints.sort( compareYAscending )
85         overhangWiddershinsLeft = OverhangWiddershinsLeft( alongAway )
86         overhangWiddershinsRight = OverhangWiddershinsRight( alongAway )
87         for point in ascendingYPoints:
88                 alterWiddershinsSupportedPathByPoint( alongAway, overhangWiddershinsLeft, overhangWiddershinsRight, point )
89
90 def alterWiddershinsSupportedPathByPoint( alongAway, overhangWiddershinsLeft, overhangWiddershinsRight, point ):
91         "Get widdershins path with overhangs filled in for point."
92         if alongAway.getIsWiddershinsPointSupported(point):
93                 return
94         overhangWiddershins = overhangWiddershinsLeft
95         if overhangWiddershinsRight.getDistance() < overhangWiddershinsLeft.getDistance():
96                 overhangWiddershins = overhangWiddershinsRight
97         overhangWiddershins.alterLoop()
98
99 def compareYAscending( point, pointOther ):
100         "Get comparison in order to sort points in ascending y."
101         if point.y < pointOther.y:
102                 return - 1
103         return int( point.y > pointOther.y )
104
105 def getManipulatedPaths(close, elementNode, loop, prefix, sideLength):
106         "Get path with overhangs removed or filled in."
107         if len(loop) < 3:
108                 print('Warning, loop has less than three sides in getManipulatedPaths in overhang for:')
109                 print(elementNode)
110                 return [loop]
111         derivation = OverhangDerivation(elementNode, prefix)
112         overhangPlaneAngle = euclidean.getWiddershinsUnitPolar(0.5 * math.pi - derivation.overhangRadians)
113         if derivation.overhangInclinationRadians != 0.0:
114                 overhangInclinationCosine = abs(math.cos(derivation.overhangInclinationRadians))
115                 if overhangInclinationCosine == 0.0:
116                         return [loop]
117                 imaginaryTimesCosine = overhangPlaneAngle.imag * overhangInclinationCosine
118                 overhangPlaneAngle = euclidean.getNormalized(complex(overhangPlaneAngle.real, imaginaryTimesCosine))
119         alongAway = AlongAway(loop, overhangPlaneAngle)
120         if euclidean.getIsWiddershinsByVector3(loop):
121                 alterWiddershinsSupportedPath(alongAway, close)
122         else:
123                 alterClockwiseSupportedPath(alongAway, elementNode)
124         return [euclidean.getLoopWithoutCloseSequentialPoints(close,  alongAway.loop)]
125
126 def getMinimumYByPath(path):
127         "Get path with overhangs removed or filled in."
128         minimumYByPath = path[0].y
129         for point in path:
130                 minimumYByPath = min( minimumYByPath, point.y )
131         return minimumYByPath
132
133 def getNewDerivation(elementNode, prefix, sideLength):
134         'Get new derivation.'
135         return OverhangDerivation(elementNode, prefix)
136
137 def processElementNode(elementNode):
138         "Process the xml element."
139         lineation.processElementNodeByFunction(elementNode, getManipulatedPaths)
140
141
142 class AlongAway:
143         "Class to derive the path along the point and away from the point."
144         def __init__( self, loop, overhangPlaneAngle ):
145                 "Initialize."
146                 self.loop = loop
147                 self.overhangPlaneAngle = overhangPlaneAngle
148                 self.ySupport = - self.overhangPlaneAngle.imag
149
150         def __repr__(self):
151                 "Get the string representation of AlongAway."
152                 return '%s' % ( self.overhangPlaneAngle )
153
154         def addToBottomPoints(self, point):
155                 "Add point to bottom points and set y to minimumY."
156                 self.bottomPoints.append(point)
157                 point.y = self.minimumY
158
159         def getIsClockwisePointSupported(self, point):
160                 "Determine if the point on the clockwise loop is supported."
161                 self.point = point
162                 self.pointIndex = None
163                 self.awayIndexes = []
164                 numberOfIntersectionsBelow = 0
165                 for pointIndex in xrange( len( self.loop ) ):
166                         begin = self.loop[pointIndex]
167                         end = self.loop[ (pointIndex + 1) % len( self.loop ) ]
168                         if begin != point and end != point:
169                                 self.awayIndexes.append( pointIndex )
170                                 yIntersection = euclidean.getYIntersectionIfExists( begin.dropAxis(), end.dropAxis(), point.x )
171                                 if yIntersection != None:
172                                         numberOfIntersectionsBelow += ( yIntersection < point.y )
173                         if begin == point:
174                                 self.pointIndex = pointIndex
175                 if numberOfIntersectionsBelow % 2 == 0:
176                         return True
177                 if self.pointIndex == None:
178                         return True
179                 if self.getIsPointSupportedBySegment( self.pointIndex - 1 + len( self.loop ) ):
180                         return True
181                 return self.getIsPointSupportedBySegment( self.pointIndex + 1 )
182
183         def getIsPointSupportedBySegment( self, endIndex ):
184                 "Determine if the point on the widdershins loop is supported."
185                 endComplex = self.loop[ ( endIndex % len( self.loop ) ) ].dropAxis()
186                 endMinusPointComplex = euclidean.getNormalized( endComplex - self.point.dropAxis() )
187                 return endMinusPointComplex.imag < self.ySupport
188
189         def getIsWiddershinsPointSupported(self, point):
190                 "Determine if the point on the widdershins loop is supported."
191                 if point.y <= self.minimumY:
192                         return True
193                 self.point = point
194                 self.pointIndex = None
195                 self.awayIndexes = []
196                 numberOfIntersectionsBelow = 0
197                 for pointIndex in xrange( len( self.loop ) ):
198                         begin = self.loop[pointIndex]
199                         end = self.loop[ (pointIndex + 1) % len( self.loop ) ]
200                         if begin != point and end != point:
201                                 self.awayIndexes.append( pointIndex )
202                                 yIntersection = euclidean.getYIntersectionIfExists( begin.dropAxis(), end.dropAxis(), point.x )
203                                 if yIntersection != None:
204                                         numberOfIntersectionsBelow += ( yIntersection < point.y )
205                         if begin == point:
206                                 self.pointIndex = pointIndex
207                 if numberOfIntersectionsBelow % 2 == 1:
208                         return True
209                 if self.pointIndex == None:
210                         return True
211                 if self.getIsPointSupportedBySegment( self.pointIndex - 1 + len( self.loop ) ):
212                         return True
213                 return self.getIsPointSupportedBySegment( self.pointIndex + 1 )
214
215
216 class OverhangClockwise:
217         "Class to get the intersection up from the point."
218         def __init__( self, alongAway ):
219                 "Initialize."
220                 self.alongAway = alongAway
221                 self.halfRiseOverWidth = 0.5 * alongAway.overhangPlaneAngle.imag / alongAway.overhangPlaneAngle.real
222                 self.widthOverRise = alongAway.overhangPlaneAngle.real / alongAway.overhangPlaneAngle.imag
223
224         def __repr__(self):
225                 "Get the string representation of OverhangClockwise."
226                 return '%s' % ( self.intersectionPlaneAngle )
227
228         def alterLoop( self, unsupportedPointIndexes ):
229                 "Alter alongAway loop."
230                 unsupportedBeginIndex = unsupportedPointIndexes[0]
231                 unsupportedEndIndex = unsupportedPointIndexes[-1]
232                 beginIndex = unsupportedBeginIndex - 1
233                 endIndex = unsupportedEndIndex + 1
234                 begin = self.alongAway.loop[ beginIndex ]
235                 end = self.alongAway.loop[ endIndex ]
236                 truncatedOverhangSpan = self.alongAway.overhangSpan
237                 width = end.x - begin.x
238                 heightDifference = abs( end.y - begin.y )
239                 remainingWidth = width - self.widthOverRise * heightDifference
240                 if remainingWidth <= 0.0:
241                         del self.alongAway.loop[ unsupportedBeginIndex : endIndex ]
242                         return
243                 highest = begin
244                 supportX = begin.x + remainingWidth
245                 if end.y > begin.y:
246                         highest = end
247                         supportX = end.x - remainingWidth
248                 tipY = highest.y + self.halfRiseOverWidth * remainingWidth
249                 highestBetween = - 987654321.0
250                 for unsupportedPointIndex in unsupportedPointIndexes:
251                         highestBetween = max( highestBetween, self.alongAway.loop[ unsupportedPointIndex ].y )
252                 if highestBetween > highest.y:
253                         truncatedOverhangSpan = 0.0
254                         if highestBetween < tipY:
255                                 below = tipY - highestBetween
256                                 truncatedOverhangSpan = min( self.alongAway.overhangSpan, below / self.halfRiseOverWidth )
257                 truncatedOverhangSpanRadius = 0.5 * truncatedOverhangSpan
258                 if remainingWidth <= truncatedOverhangSpan:
259                         supportPoint = Vector3( supportX, highest.y, highest.z )
260                         self.alongAway.loop[ unsupportedBeginIndex : endIndex ] = [ supportPoint ]
261                         return
262                 midSupportX = 0.5 * ( supportX + highest.x )
263                 if truncatedOverhangSpan <= 0.0:
264                         supportPoint = Vector3( midSupportX, tipY, highest.z )
265                         self.alongAway.loop[ unsupportedBeginIndex : endIndex ] = [ supportPoint ]
266                         return
267                 supportXLeft = midSupportX - truncatedOverhangSpanRadius
268                 supportXRight = midSupportX + truncatedOverhangSpanRadius
269                 supportY = tipY - self.halfRiseOverWidth * truncatedOverhangSpan
270                 supportPoints = [ Vector3( supportXLeft, supportY, highest.z ), Vector3( supportXRight, supportY, highest.z ) ]
271                 self.alongAway.loop[ unsupportedBeginIndex : endIndex ] = supportPoints
272
273
274 class OverhangDerivation:
275         "Class to hold overhang variables."
276         def __init__(self, elementNode, prefix):
277                 'Set defaults.'
278                 self.overhangRadians = setting.getOverhangRadians(elementNode)
279                 self.overhangInclinationRadians = math.radians(evaluate.getEvaluatedFloat(0.0, elementNode,  prefix + 'inclination'))
280
281
282 class OverhangWiddershinsLeft:
283         "Class to get the intersection from the point down to the left."
284         def __init__( self, alongAway ):
285                 "Initialize."
286                 self.alongAway = alongAway
287                 self.intersectionPlaneAngle = - alongAway.overhangPlaneAngle
288                 self.setRatios()
289
290         def __repr__(self):
291                 "Get the string representation of OverhangWiddershins."
292                 return '%s' % ( self.intersectionPlaneAngle )
293
294         def alterLoop(self):
295                 "Alter alongAway loop."
296                 insertedPoint = self.alongAway.point.copy()
297                 if self.closestXIntersectionIndex != None:
298                         self.alongAway.loop = self.getIntersectLoop()
299                         intersectionRelativeComplex = self.closestXDistance * self.intersectionPlaneAngle
300                         intersectionPoint = insertedPoint + Vector3( intersectionRelativeComplex.real, intersectionRelativeComplex.imag )
301                         self.alongAway.loop.append( intersectionPoint )
302                         return
303                 if self.closestBottomPoint == None:
304                         return
305                 if self.closestBottomPoint not in self.alongAway.loop:
306                         return
307                 insertedPoint.x = self.bottomX
308                 closestBottomIndex = self.alongAway.loop.index( self.closestBottomPoint )
309                 self.alongAway.addToBottomPoints( insertedPoint )
310                 self.alongAway.loop = self.getBottomLoop( closestBottomIndex, insertedPoint )
311                 self.alongAway.loop.append( insertedPoint )
312
313         def getBottomLoop( self, closestBottomIndex, insertedPoint ):
314                 "Get loop around bottom."
315                 endIndex = closestBottomIndex + len( self.alongAway.loop ) + 1
316                 return euclidean.getAroundLoop( self.alongAway.pointIndex, endIndex, self.alongAway.loop )
317
318         def getDistance(self):
319                 "Get distance between point and closest intersection or bottom point along line."
320                 self.pointMinusBottomY = self.alongAway.point.y - self.alongAway.minimumY
321                 self.diagonalDistance = self.pointMinusBottomY * self.diagonalRatio
322                 if self.alongAway.pointIndex == None:
323                         return self.getDistanceToBottom()
324                 rotatedLoop = euclidean.getRotatedComplexes( self.intersectionYMirror,  euclidean.getComplexPath( self.alongAway.loop ) )
325                 rotatedPointComplex = rotatedLoop[ self.alongAway.pointIndex ]
326                 beginX = rotatedPointComplex.real
327                 endX = beginX + self.diagonalDistance + self.diagonalDistance
328                 xIntersectionIndexList = []
329                 for pointIndex in self.alongAway.awayIndexes:
330                         beginComplex = rotatedLoop[pointIndex]
331                         endComplex = rotatedLoop[ (pointIndex + 1) % len( rotatedLoop ) ]
332                         xIntersection = euclidean.getXIntersectionIfExists( beginComplex, endComplex, rotatedPointComplex.imag )
333                         if xIntersection != None:
334                                 if xIntersection >= beginX and xIntersection < endX:
335                                         xIntersectionIndexList.append( euclidean.XIntersectionIndex( pointIndex, xIntersection ) )
336                 self.closestXDistance = 987654321.0
337                 self.closestXIntersectionIndex = None
338                 for xIntersectionIndex in xIntersectionIndexList:
339                         xDistance = abs( xIntersectionIndex.x - beginX )
340                         if xDistance < self.closestXDistance:
341                                 self.closestXIntersectionIndex = xIntersectionIndex
342                                 self.closestXDistance = xDistance
343                 if self.closestXIntersectionIndex != None:
344                         return self.closestXDistance
345                 return self.getDistanceToBottom()
346
347         def getDistanceToBottom(self):
348                 "Get distance between point and closest bottom point along line."
349                 self.bottomX = self.alongAway.point.x + self.pointMinusBottomY * self.xRatio
350                 self.closestBottomPoint = None
351                 closestDistanceX = 987654321.0
352                 for point in self.alongAway.bottomPoints:
353                         distanceX = abs( point.x - self.bottomX )
354                         if self.getIsOnside(point.x):
355                                 if distanceX < closestDistanceX:
356                                         closestDistanceX = distanceX
357                                         self.closestBottomPoint = point
358                 return closestDistanceX + self.diagonalDistance
359
360         def getIntersectLoop(self):
361                 "Get intersection loop."
362                 endIndex = self.closestXIntersectionIndex.index + len( self.alongAway.loop ) + 1
363                 return euclidean.getAroundLoop( self.alongAway.pointIndex, endIndex, self.alongAway.loop )
364
365         def getIsOnside( self, x ):
366                 "Determine if x is on the side along the direction of the intersection line."
367                 return x <= self.alongAway.point.x
368
369         def setRatios(self):
370                 "Set ratios."
371                 self.diagonalRatio = 1.0 / abs( self.intersectionPlaneAngle.imag )
372                 self.intersectionYMirror = complex( self.intersectionPlaneAngle.real, - self.intersectionPlaneAngle.imag )
373                 self.xRatio = self.intersectionPlaneAngle.real / abs( self.intersectionPlaneAngle.imag )
374
375
376 class OverhangWiddershinsRight( OverhangWiddershinsLeft ):
377         "Class to get the intersection from the point down to the right."
378         def __init__( self, alongAway ):
379                 "Initialize."
380                 self.alongAway = alongAway
381                 self.intersectionPlaneAngle = complex( alongAway.overhangPlaneAngle.real, - alongAway.overhangPlaneAngle.imag )
382                 self.setRatios()
383
384         def getBottomLoop( self, closestBottomIndex, insertedPoint ):
385                 "Get loop around bottom."
386                 endIndex = self.alongAway.pointIndex + len( self.alongAway.loop ) + 1
387                 return euclidean.getAroundLoop( closestBottomIndex, endIndex, self.alongAway.loop )
388
389         def getIntersectLoop(self):
390                 "Get intersection loop."
391                 beginIndex = self.closestXIntersectionIndex.index + len( self.alongAway.loop ) + 1
392                 endIndex = self.alongAway.pointIndex + len( self.alongAway.loop ) + 1
393                 return euclidean.getAroundLoop( beginIndex, endIndex, self.alongAway.loop )
394
395         def getIsOnside( self, x ):
396                 "Determine if x is on the side along the direction of the intersection line."
397                 return x >= self.alongAway.point.x