GridArrange.py 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342
  1. import math
  2. from typing import List, TYPE_CHECKING, Tuple, Set, Union
  3. if TYPE_CHECKING:
  4. from UM.Scene.SceneNode import SceneNode
  5. from cura.BuildVolume import BuildVolume
  6. from UM.Application import Application
  7. from UM.Math.AxisAlignedBox import AxisAlignedBox
  8. from UM.Math.Polygon import Polygon
  9. from UM.Math.Vector import Vector
  10. from UM.Operations.AddSceneNodeOperation import AddSceneNodeOperation
  11. from UM.Operations.GroupedOperation import GroupedOperation
  12. from UM.Operations.TranslateOperation import TranslateOperation
  13. from cura.Arranging.Arranger import Arranger
  14. class GridArrange(Arranger):
  15. def __init__(self, nodes_to_arrange: List["SceneNode"], build_volume: "BuildVolume", fixed_nodes: List["SceneNode"] = None):
  16. if fixed_nodes is None:
  17. fixed_nodes = []
  18. self._nodes_to_arrange = nodes_to_arrange
  19. self._build_volume = build_volume
  20. self._build_volume_bounding_box = build_volume.getBoundingBox()
  21. self._fixed_nodes = fixed_nodes
  22. self._margin_x: float = 1
  23. self._margin_y: float = 1
  24. self._grid_width = 0
  25. self._grid_height = 0
  26. for node in self._nodes_to_arrange:
  27. bounding_box = node.getBoundingBox()
  28. self._grid_width = max(self._grid_width, bounding_box.width)
  29. self._grid_height = max(self._grid_height, bounding_box.depth)
  30. self._grid_width += self._margin_x
  31. self._grid_height += self._margin_y
  32. # Round up the grid size to the nearest cm, this assures that new objects will
  33. # be placed on integer offsets from each other
  34. grid_precision = 10 # 1cm
  35. rounded_grid_width = math.ceil(self._grid_width / grid_precision) * grid_precision
  36. rounded_grid_height = math.ceil(self._grid_height / grid_precision) * grid_precision
  37. # The space added by the "grid precision rounding up" of the grid size
  38. self._grid_round_margin_x = rounded_grid_width - self._grid_width
  39. self._grid_round_margin_y = rounded_grid_height - self._grid_height
  40. self._grid_width = rounded_grid_width
  41. self._grid_height = rounded_grid_height
  42. self._offset_x = 0
  43. self._offset_y = 0
  44. self._findOptimalGridOffset()
  45. coord_initial_leftover_x = self._build_volume_bounding_box.right + 2 * self._grid_width
  46. coord_initial_leftover_y = (self._build_volume_bounding_box.back + self._build_volume_bounding_box.front) * 0.5
  47. self._initial_leftover_grid_x, self._initial_leftover_grid_y = self._coordSpaceToGridSpace(
  48. coord_initial_leftover_x, coord_initial_leftover_y)
  49. self._initial_leftover_grid_x = math.floor(self._initial_leftover_grid_x)
  50. self._initial_leftover_grid_y = math.floor(self._initial_leftover_grid_y)
  51. # Find grid indexes that intersect with fixed objects
  52. self._fixed_nodes_grid_ids = set()
  53. for node in self._fixed_nodes:
  54. self._fixed_nodes_grid_ids = self._fixed_nodes_grid_ids.union(
  55. self._intersectingGridIdxInclusive(node.getBoundingBox()))
  56. # grid indexes that are in disallowed area
  57. for polygon in self._build_volume.getDisallowedAreas():
  58. self._fixed_nodes_grid_ids = self._fixed_nodes_grid_ids.union(self._intersectingGridIdxInclusive(polygon))
  59. self._build_plate_grid_ids = self._intersectingGridIdxExclusive(self._build_volume_bounding_box)
  60. # Filter out the corner grid squares if the build plate shape is elliptic
  61. if self._build_volume.getShape() == "elliptic":
  62. self._build_plate_grid_ids = set(
  63. filter(lambda grid_id: self._checkGridUnderDiscSpace(grid_id[0], grid_id[1]),
  64. self._build_plate_grid_ids))
  65. self._allowed_grid_idx = self._build_plate_grid_ids.difference(self._fixed_nodes_grid_ids)
  66. def createGroupOperationForArrange(self, add_new_nodes_in_scene: bool = False) -> Tuple[GroupedOperation, int]:
  67. # Find the sequence in which items are placed
  68. coord_build_plate_center_x = self._build_volume_bounding_box.width * 0.5 + self._build_volume_bounding_box.left
  69. coord_build_plate_center_y = self._build_volume_bounding_box.depth * 0.5 + self._build_volume_bounding_box.back
  70. grid_build_plate_center_x, grid_build_plate_center_y = self._coordSpaceToGridSpace(coord_build_plate_center_x,
  71. coord_build_plate_center_y)
  72. sequence: List[Tuple[int, int]] = list(self._allowed_grid_idx)
  73. sequence.sort(key=lambda grid_id: (grid_build_plate_center_x - grid_id[0]) ** 2 + (
  74. grid_build_plate_center_y - grid_id[1]) ** 2)
  75. scene_root = Application.getInstance().getController().getScene().getRoot()
  76. grouped_operation = GroupedOperation()
  77. for grid_id, node in zip(sequence, self._nodes_to_arrange):
  78. if add_new_nodes_in_scene:
  79. grouped_operation.addOperation(AddSceneNodeOperation(node, scene_root))
  80. grid_x, grid_y = grid_id
  81. operation = self._moveNodeOnGrid(node, grid_x, grid_y)
  82. grouped_operation.addOperation(operation)
  83. leftover_nodes = self._nodes_to_arrange[len(sequence):]
  84. left_over_grid_y = self._initial_leftover_grid_y
  85. for node in leftover_nodes:
  86. if add_new_nodes_in_scene:
  87. grouped_operation.addOperation(AddSceneNodeOperation(node, scene_root))
  88. # find the first next grid position that isn't occupied by a fixed node
  89. while (self._initial_leftover_grid_x, left_over_grid_y) in self._fixed_nodes_grid_ids:
  90. left_over_grid_y = left_over_grid_y - 1
  91. operation = self._moveNodeOnGrid(node, self._initial_leftover_grid_x, left_over_grid_y)
  92. grouped_operation.addOperation(operation)
  93. left_over_grid_y = left_over_grid_y - 1
  94. return grouped_operation, len(leftover_nodes)
  95. def _findOptimalGridOffset(self):
  96. if len(self._fixed_nodes) == 0:
  97. edge_disallowed_size = self._build_volume.getEdgeDisallowedSize()
  98. self._offset_x = edge_disallowed_size
  99. self._offset_y = edge_disallowed_size
  100. return
  101. if len(self._fixed_nodes) == 1:
  102. center_grid_x = 0.5 * self._grid_width + self._build_volume_bounding_box.left
  103. center_grid_y = 0.5 * self._grid_height + self._build_volume_bounding_box.back
  104. bounding_box = self._fixed_nodes[0].getBoundingBox()
  105. center_node_x = (bounding_box.left + bounding_box.right) * 0.5
  106. center_node_y = (bounding_box.back + bounding_box.front) * 0.5
  107. self._offset_x = center_node_x - center_grid_x
  108. self._offset_y = center_node_y - center_grid_y
  109. return
  110. # If there are multiple fixed nodes, an optimal solution is not always possible
  111. # We will try to find an offset that minimizes the number of grid intersections
  112. # with fixed nodes. The algorithm below achieves this by utilizing a scanline
  113. # algorithm. In this algorithm each axis is solved separately as offsetting
  114. # is completely independent in each axis. The comments explaining the algorithm
  115. # below are for the x-axis, but the same applies for the y-axis.
  116. #
  117. # Each node either occupies ceil((node.right - node.right) / grid_width) or
  118. # ceil((node.right - node.right) / grid_width) + 1 grid squares. We will call
  119. # these the node's "footprint".
  120. #
  121. # ┌────────────────┐
  122. # minimum foot-print │ NODE │
  123. # └────────────────┘
  124. # │ grid 1 │ grid 2 │ grid 3 │ grid 4 | grid 5 |
  125. # ┌────────────────┐
  126. # maximum foot-print │ NODE │
  127. # └────────────────┘
  128. #
  129. # The algorithm will find the grid offset such that the number of nodes with
  130. # a _minimal_ footprint is _maximized_.
  131. # The scanline algorithm works as follows, we create events for both end points
  132. # of each node's footprint. The event have two properties,
  133. # - the coordinate: the amount the endpoint can move to the
  134. # left before it crosses a grid line
  135. # - the change: either +1 or -1, indicating whether crossing the grid line
  136. # would result in a minimal footprint node becoming a maximal footprint
  137. class Event:
  138. def __init__(self, coord: float, change: float):
  139. self.coord = coord
  140. self.change = change
  141. # create events for both the horizontal and vertical axis
  142. events_horizontal: List[Event] = []
  143. events_vertical: List[Event] = []
  144. for node in self._fixed_nodes:
  145. bounding_box = node.getBoundingBox()
  146. left = bounding_box.left - self._build_volume_bounding_box.left
  147. right = bounding_box.right - self._build_volume_bounding_box.left
  148. back = bounding_box.back - self._build_volume_bounding_box.back
  149. front = bounding_box.front - self._build_volume_bounding_box.back
  150. value_left = math.ceil(left / self._grid_width) * self._grid_width - left
  151. value_right = math.ceil(right / self._grid_width) * self._grid_width - right
  152. value_back = math.ceil(back / self._grid_height) * self._grid_height - back
  153. value_front = math.ceil(front / self._grid_height) * self._grid_height - front
  154. # give nodes a weight according to their size. This
  155. # weight is heuristically chosen to be proportional to
  156. # the number of grid squares the node-boundary occupies
  157. weight = bounding_box.width + bounding_box.depth
  158. events_horizontal.append(Event(value_left, weight))
  159. events_horizontal.append(Event(value_right, -weight))
  160. events_vertical.append(Event(value_back, weight))
  161. events_vertical.append(Event(value_front, -weight))
  162. events_horizontal.sort(key=lambda event: event.coord)
  163. events_vertical.sort(key=lambda event: event.coord)
  164. def findOptimalShiftAxis(events: List[Event], interval: float) -> float:
  165. # executing the actual scanline algorithm
  166. # iteratively go through events (left to right) and keep track of the
  167. # current footprint. The optimal location is the one with the minimal
  168. # footprint. If there are multiple locations with the same minimal
  169. # footprint, the optimal location is the one with the largest range
  170. # between the left and right endpoint of the footprint.
  171. prev_offset = events[-1].coord - interval
  172. current_minimal_footprint_count = 0
  173. best_minimal_footprint_count = float('inf')
  174. best_offset_span = float('-inf')
  175. best_offset = 0.0
  176. for event in events:
  177. offset_span = event.coord - prev_offset
  178. if current_minimal_footprint_count < best_minimal_footprint_count or (
  179. current_minimal_footprint_count == best_minimal_footprint_count and offset_span > best_offset_span):
  180. best_minimal_footprint_count = current_minimal_footprint_count
  181. best_offset_span = offset_span
  182. best_offset = event.coord
  183. current_minimal_footprint_count += event.change
  184. prev_offset = event.coord
  185. return best_offset - best_offset_span * 0.5
  186. center_grid_x = 0.5 * self._grid_width
  187. center_grid_y = 0.5 * self._grid_height
  188. optimal_center_x = self._grid_width - findOptimalShiftAxis(events_horizontal, self._grid_width)
  189. optimal_center_y = self._grid_height - findOptimalShiftAxis(events_vertical, self._grid_height)
  190. self._offset_x = optimal_center_x - center_grid_x
  191. self._offset_y = optimal_center_y - center_grid_y
  192. def _moveNodeOnGrid(self, node: "SceneNode", grid_x: int, grid_y: int) -> "Operation.Operation":
  193. coord_grid_x, coord_grid_y = self._gridSpaceToCoordSpace(grid_x, grid_y)
  194. center_grid_x = coord_grid_x + (0.5 * self._grid_width)
  195. center_grid_y = coord_grid_y + (0.5 * self._grid_height)
  196. return TranslateOperation(node, Vector(center_grid_x, node.getWorldPosition().y, center_grid_y),
  197. set_position=True)
  198. def _getGridCornerPoints(
  199. self,
  200. bounds: Union[AxisAlignedBox, Polygon],
  201. *,
  202. margin_x: float = 0.0,
  203. margin_y: float = 0.0
  204. ) -> Tuple[float, float, float, float]:
  205. if isinstance(bounds, AxisAlignedBox):
  206. coord_x1 = bounds.left - margin_x
  207. coord_x2 = bounds.right + margin_x
  208. coord_y1 = bounds.back - margin_y
  209. coord_y2 = bounds.front + margin_y
  210. elif isinstance(bounds, Polygon):
  211. coord_x1 = float('inf')
  212. coord_y1 = float('inf')
  213. coord_x2 = float('-inf')
  214. coord_y2 = float('-inf')
  215. for x, y in bounds.getPoints():
  216. coord_x1 = min(coord_x1, x)
  217. coord_y1 = min(coord_y1, y)
  218. coord_x2 = max(coord_x2, x)
  219. coord_y2 = max(coord_y2, y)
  220. else:
  221. raise TypeError("bounds must be either an AxisAlignedBox or a Polygon")
  222. coord_x1 -= margin_x
  223. coord_x2 += margin_x
  224. coord_y1 -= margin_y
  225. coord_y2 += margin_y
  226. grid_x1, grid_y1 = self._coordSpaceToGridSpace(coord_x1, coord_y1)
  227. grid_x2, grid_y2 = self._coordSpaceToGridSpace(coord_x2, coord_y2)
  228. return grid_x1, grid_y1, grid_x2, grid_y2
  229. def _intersectingGridIdxInclusive(self, bounds: Union[AxisAlignedBox, Polygon]) -> Set[Tuple[int, int]]:
  230. grid_x1, grid_y1, grid_x2, grid_y2 = self._getGridCornerPoints(
  231. bounds,
  232. margin_x=-(self._margin_x + self._grid_round_margin_x) * 0.5,
  233. margin_y=-(self._margin_y + self._grid_round_margin_y) * 0.5,
  234. )
  235. grid_idx = set()
  236. for grid_x in range(math.floor(grid_x1), math.ceil(grid_x2)):
  237. for grid_y in range(math.floor(grid_y1), math.ceil(grid_y2)):
  238. grid_idx.add((grid_x, grid_y))
  239. return grid_idx
  240. def _intersectingGridIdxExclusive(self, bounds: Union[AxisAlignedBox, Polygon]) -> Set[Tuple[int, int]]:
  241. grid_x1, grid_y1, grid_x2, grid_y2 = self._getGridCornerPoints(
  242. bounds,
  243. margin_x=(self._margin_x + self._grid_round_margin_x) * 0.5,
  244. margin_y=(self._margin_y + self._grid_round_margin_y) * 0.5,
  245. )
  246. grid_idx = set()
  247. for grid_x in range(math.ceil(grid_x1), math.floor(grid_x2)):
  248. for grid_y in range(math.ceil(grid_y1), math.floor(grid_y2)):
  249. grid_idx.add((grid_x, grid_y))
  250. return grid_idx
  251. def _gridSpaceToCoordSpace(self, x: float, y: float) -> Tuple[float, float]:
  252. grid_x = x * self._grid_width + self._build_volume_bounding_box.left + self._offset_x
  253. grid_y = y * self._grid_height + self._build_volume_bounding_box.back + self._offset_y
  254. return grid_x, grid_y
  255. def _coordSpaceToGridSpace(self, grid_x: float, grid_y: float) -> Tuple[float, float]:
  256. coord_x = (grid_x - self._build_volume_bounding_box.left - self._offset_x) / self._grid_width
  257. coord_y = (grid_y - self._build_volume_bounding_box.back - self._offset_y) / self._grid_height
  258. return coord_x, coord_y
  259. def _checkGridUnderDiscSpace(self, grid_x: int, grid_y: int) -> bool:
  260. left, back = self._gridSpaceToCoordSpace(grid_x, grid_y)
  261. right, front = self._gridSpaceToCoordSpace(grid_x + 1, grid_y + 1)
  262. corners = [(left, back), (right, back), (right, front), (left, front)]
  263. return all([self._checkPointUnderDiscSpace(x, y) for x, y in corners])
  264. def _checkPointUnderDiscSpace(self, x: float, y: float) -> bool:
  265. disc_x, disc_y = self._coordSpaceToDiscSpace(x, y)
  266. distance_to_center_squared = disc_x ** 2 + disc_y ** 2
  267. return distance_to_center_squared <= 1.0
  268. def _coordSpaceToDiscSpace(self, x: float, y: float) -> Tuple[float, float]:
  269. # Transform coordinate system to
  270. #
  271. # coord_build_plate_left = -1
  272. # | coord_build_plate_right = 1
  273. # v (0,1) v
  274. # ┌───────┬───────┐ < coord_build_plate_back = -1
  275. # │ │ │
  276. # │ │(0,0) │
  277. # (-1,0)├───────o───────┤(1,0)
  278. # │ │ │
  279. # │ │ │
  280. # └───────┴───────┘ < coord_build_plate_front = +1
  281. # (0,-1)
  282. disc_x = ((x - self._build_volume_bounding_box.left) / self._build_volume_bounding_box.width) * 2.0 - 1.0
  283. disc_y = ((y - self._build_volume_bounding_box.back) / self._build_volume_bounding_box.depth) * 2.0 - 1.0
  284. return disc_x, disc_y