OneAtATimeIterator.py 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
  1. # Copyright (c) 2015 Ultimaker B.V.
  2. # Cura is released under the terms of the LGPLv3 or higher.
  3. from UM.Scene.Iterator import Iterator
  4. from UM.Scene.SceneNode import SceneNode
  5. from functools import cmp_to_key
  6. from UM.Application import Application
  7. ## Iterator that returns a list of nodes in the order that they need to be printed
  8. # If there is no solution an empty list is returned.
  9. # Take note that the list of nodes can have children (that may or may not contain mesh data)
  10. class OneAtATimeIterator(Iterator.Iterator):
  11. def __init__(self, scene_node):
  12. super().__init__(scene_node) # Call super to make multiple inheritence work.
  13. self._hit_map = [[]]
  14. self._original_node_list = []
  15. def _fillStack(self):
  16. node_list = []
  17. for node in self._scene_node.getChildren():
  18. if not issubclass(type(node), SceneNode):
  19. continue
  20. if node.callDecoration("getConvexHull"):
  21. node_list.append(node)
  22. if len(node_list) < 2:
  23. self._node_stack = node_list[:]
  24. return
  25. # Copy the list
  26. self._original_node_list = node_list[:]
  27. ## Initialise the hit map (pre-compute all hits between all objects)
  28. self._hit_map = [[self._checkHit(i,j) for i in node_list] for j in node_list]
  29. # Check if we have to files that block eachother. If this is the case, there is no solution!
  30. for a in range(0,len(node_list)):
  31. for b in range(0,len(node_list)):
  32. if a != b and self._hit_map[a][b] and self._hit_map[b][a]:
  33. return
  34. # Sort the original list so that items that block the most other objects are at the beginning.
  35. # This does not decrease the worst case running time, but should improve it in most cases.
  36. sorted(node_list, key = cmp_to_key(self._calculateScore))
  37. todo_node_list = [_ObjectOrder([], node_list)]
  38. while len(todo_node_list) > 0:
  39. current = todo_node_list.pop()
  40. for node in current.todo:
  41. # Check if the object can be placed with what we have and still allows for a solution in the future
  42. if not self._checkHitMultiple(node, current.order) and not self._checkBlockMultiple(node, current.todo):
  43. # We found a possible result. Create new todo & order list.
  44. new_todo_list = current.todo[:]
  45. new_todo_list.remove(node)
  46. new_order = current.order[:] + [node]
  47. if len(new_todo_list) == 0:
  48. # We have no more nodes to check, so quit looking.
  49. todo_node_list = None
  50. self._node_stack = new_order
  51. return
  52. todo_node_list.append(_ObjectOrder(new_order, new_todo_list))
  53. self._node_stack = [] #No result found!
  54. # Check if first object can be printed before the provided list (using the hit map)
  55. def _checkHitMultiple(self, node, other_nodes):
  56. node_index = self._original_node_list.index(node)
  57. for other_node in other_nodes:
  58. other_node_index = self._original_node_list.index(other_node)
  59. if self._hit_map[node_index][other_node_index]:
  60. return True
  61. return False
  62. def _checkBlockMultiple(self, node, other_nodes):
  63. node_index = self._original_node_list.index(node)
  64. for other_node in other_nodes:
  65. other_node_index = self._original_node_list.index(other_node)
  66. if self._hit_map[other_node_index][node_index] and node_index != other_node_index:
  67. return True
  68. return False
  69. ## Calculate score simply sums the number of other objects it 'blocks'
  70. def _calculateScore(self, a, b):
  71. score_a = sum(self._hit_map[self._original_node_list.index(a)])
  72. score_b = sum(self._hit_map[self._original_node_list.index(b)])
  73. return score_a - score_b
  74. # Checks if A can be printed before B
  75. def _checkHit(self, a, b):
  76. if a == b:
  77. return False
  78. overlap = a.callDecoration("getConvexHullBoundary").intersectsPolygon(b.callDecoration("getConvexHullHeadFull"))
  79. if overlap:
  80. return True
  81. else:
  82. return False
  83. ## Internal object used to keep track of a possible order in which to print objects.
  84. class _ObjectOrder():
  85. def __init__(self, order, todo):
  86. """
  87. :param order: List of indexes in which to print objects, ordered by printing order.
  88. :param todo: List of indexes which are not yet inserted into the order list.
  89. """
  90. self.order = order
  91. self.todo = todo