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