Arrange.py 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
  1. # Copyright (c) 2018 Ultimaker B.V.
  2. # Cura is released under the terms of the LGPLv3 or higher.
  3. from typing import List
  4. from UM.Scene.Iterator.DepthFirstIterator import DepthFirstIterator
  5. from UM.Logger import Logger
  6. from UM.Math.Polygon import Polygon
  7. from UM.Math.Vector import Vector
  8. from UM.Scene.SceneNode import SceneNode
  9. from cura.Arranging.ShapeArray import ShapeArray
  10. from cura.Scene import ZOffsetDecorator
  11. from collections import namedtuple
  12. import numpy
  13. import copy
  14. ## Return object for bestSpot
  15. LocationSuggestion = namedtuple("LocationSuggestion", ["x", "y", "penalty_points", "priority"])
  16. ## The Arrange classed is used together with ShapeArray. Use it to find
  17. # good locations for objects that you try to put on a build place.
  18. # Different priority schemes can be defined so it alters the behavior while using
  19. # the same logic.
  20. #
  21. # Note: Make sure the scale is the same between ShapeArray objects and the Arrange instance.
  22. class Arrange:
  23. build_volume = None
  24. def __init__(self, x, y, offset_x, offset_y, scale= 0.5):
  25. self._scale = scale # convert input coordinates to arrange coordinates
  26. world_x, world_y = int(x * self._scale), int(y * self._scale)
  27. self._shape = (world_y, world_x)
  28. self._priority = numpy.zeros((world_y, world_x), dtype=numpy.int32) # beware: these are indexed (y, x)
  29. self._priority_unique_values = []
  30. self._occupied = numpy.zeros((world_y, world_x), dtype=numpy.int32) # beware: these are indexed (y, x)
  31. self._offset_x = int(offset_x * self._scale)
  32. self._offset_y = int(offset_y * self._scale)
  33. self._last_priority = 0
  34. self._is_empty = True
  35. ## Helper to create an Arranger instance
  36. #
  37. # Either fill in scene_root and create will find all sliceable nodes by itself,
  38. # or use fixed_nodes to provide the nodes yourself.
  39. # \param scene_root Root for finding all scene nodes
  40. # \param fixed_nodes Scene nodes to be placed
  41. @classmethod
  42. def create(cls, scene_root = None, fixed_nodes = None, scale = 0.5, x = 350, y = 250, min_offset = 8):
  43. arranger = Arrange(x, y, x // 2, y // 2, scale = scale)
  44. arranger.centerFirst()
  45. if fixed_nodes is None:
  46. fixed_nodes = []
  47. for node_ in DepthFirstIterator(scene_root):
  48. # Only count sliceable objects
  49. if node_.callDecoration("isSliceable"):
  50. fixed_nodes.append(node_)
  51. # Place all objects fixed nodes
  52. for fixed_node in fixed_nodes:
  53. vertices = fixed_node.callDecoration("getConvexHullHead") or fixed_node.callDecoration("getConvexHull")
  54. if not vertices:
  55. continue
  56. vertices = vertices.getMinkowskiHull(Polygon.approximatedCircle(min_offset))
  57. points = copy.deepcopy(vertices._points)
  58. # After scaling (like up to 0.1 mm) the node might not have points
  59. if len(points) == 0:
  60. continue
  61. shape_arr = ShapeArray.fromPolygon(points, scale = scale)
  62. arranger.place(0, 0, shape_arr)
  63. # If a build volume was set, add the disallowed areas
  64. if Arrange.build_volume:
  65. disallowed_areas = Arrange.build_volume.getDisallowedAreasNoBrim()
  66. for area in disallowed_areas:
  67. points = copy.deepcopy(area._points)
  68. shape_arr = ShapeArray.fromPolygon(points, scale = scale)
  69. arranger.place(0, 0, shape_arr, update_empty = False)
  70. return arranger
  71. ## This resets the optimization for finding location based on size
  72. def resetLastPriority(self):
  73. self._last_priority = 0
  74. ## Find placement for a node (using offset shape) and place it (using hull shape)
  75. # return the nodes that should be placed
  76. # \param node
  77. # \param offset_shape_arr ShapeArray with offset, for placing the shape
  78. # \param hull_shape_arr ShapeArray without offset, used to find location
  79. def findNodePlacement(self, node: SceneNode, offset_shape_arr: ShapeArray, hull_shape_arr: ShapeArray, step = 1):
  80. best_spot = self.bestSpot(
  81. hull_shape_arr, start_prio = self._last_priority, step = step)
  82. x, y = best_spot.x, best_spot.y
  83. # Save the last priority.
  84. self._last_priority = best_spot.priority
  85. # Ensure that the object is above the build platform
  86. node.removeDecorator(ZOffsetDecorator.ZOffsetDecorator)
  87. bbox = node.getBoundingBox()
  88. if bbox:
  89. center_y = node.getWorldPosition().y - bbox.bottom
  90. else:
  91. center_y = 0
  92. if x is not None: # We could find a place
  93. node.setPosition(Vector(x, center_y, y))
  94. found_spot = True
  95. self.place(x, y, offset_shape_arr) # place the object in arranger
  96. else:
  97. Logger.log("d", "Could not find spot!"),
  98. found_spot = False
  99. node.setPosition(Vector(200, center_y, 100))
  100. return found_spot
  101. ## Fill priority, center is best. Lower value is better
  102. # This is a strategy for the arranger.
  103. def centerFirst(self):
  104. # Square distance: creates a more round shape
  105. self._priority = numpy.fromfunction(
  106. lambda j, i: (self._offset_x - i) ** 2 + (self._offset_y - j) ** 2, self._shape, dtype=numpy.int32)
  107. self._priority_unique_values = numpy.unique(self._priority)
  108. self._priority_unique_values.sort()
  109. ## Fill priority, back is best. Lower value is better
  110. # This is a strategy for the arranger.
  111. def backFirst(self):
  112. self._priority = numpy.fromfunction(
  113. lambda j, i: 10 * j + abs(self._offset_x - i), self._shape, dtype=numpy.int32)
  114. self._priority_unique_values = numpy.unique(self._priority)
  115. self._priority_unique_values.sort()
  116. ## Return the amount of "penalty points" for polygon, which is the sum of priority
  117. # None if occupied
  118. # \param x x-coordinate to check shape
  119. # \param y y-coordinate
  120. # \param shape_arr the ShapeArray object to place
  121. def checkShape(self, x, y, shape_arr):
  122. x = int(self._scale * x)
  123. y = int(self._scale * y)
  124. offset_x = x + self._offset_x + shape_arr.offset_x
  125. offset_y = y + self._offset_y + shape_arr.offset_y
  126. if offset_x < 0 or offset_y < 0:
  127. return None # out of bounds in self._occupied
  128. occupied_x_max = offset_x + shape_arr.arr.shape[1]
  129. occupied_y_max = offset_y + shape_arr.arr.shape[0]
  130. if occupied_x_max > self._occupied.shape[1] + 1 or occupied_y_max > self._occupied.shape[0] + 1:
  131. return None # out of bounds in self._occupied
  132. occupied_slice = self._occupied[
  133. offset_y:occupied_y_max,
  134. offset_x:occupied_x_max]
  135. try:
  136. if numpy.any(occupied_slice[numpy.where(shape_arr.arr == 1)]):
  137. return None
  138. except IndexError: # out of bounds if you try to place an object outside
  139. return None
  140. prio_slice = self._priority[
  141. offset_y:offset_y + shape_arr.arr.shape[0],
  142. offset_x:offset_x + shape_arr.arr.shape[1]]
  143. return numpy.sum(prio_slice[numpy.where(shape_arr.arr == 1)])
  144. ## Find "best" spot for ShapeArray
  145. # Return namedtuple with properties x, y, penalty_points, priority.
  146. # \param shape_arr ShapeArray
  147. # \param start_prio Start with this priority value (and skip the ones before)
  148. # \param step Slicing value, higher = more skips = faster but less accurate
  149. def bestSpot(self, shape_arr, start_prio = 0, step = 1):
  150. start_idx_list = numpy.where(self._priority_unique_values == start_prio)
  151. if start_idx_list:
  152. start_idx = start_idx_list[0][0]
  153. else:
  154. start_idx = 0
  155. for priority in self._priority_unique_values[start_idx::step]:
  156. tryout_idx = numpy.where(self._priority == priority)
  157. for idx in range(len(tryout_idx[0])):
  158. x = tryout_idx[1][idx]
  159. y = tryout_idx[0][idx]
  160. projected_x = int((x - self._offset_x) / self._scale)
  161. projected_y = int((y - self._offset_y) / self._scale)
  162. penalty_points = self.checkShape(projected_x, projected_y, shape_arr)
  163. if penalty_points is not None:
  164. return LocationSuggestion(x = projected_x, y = projected_y, penalty_points = penalty_points, priority = priority)
  165. return LocationSuggestion(x = None, y = None, penalty_points = None, priority = priority) # No suitable location found :-(
  166. ## Place the object.
  167. # Marks the locations in self._occupied and self._priority
  168. # \param x x-coordinate
  169. # \param y y-coordinate
  170. # \param shape_arr ShapeArray object
  171. # \param update_empty updates the _is_empty, used when adding disallowed areas
  172. def place(self, x, y, shape_arr, update_empty = True):
  173. x = int(self._scale * x)
  174. y = int(self._scale * y)
  175. offset_x = x + self._offset_x + shape_arr.offset_x
  176. offset_y = y + self._offset_y + shape_arr.offset_y
  177. shape_y, shape_x = self._occupied.shape
  178. min_x = min(max(offset_x, 0), shape_x - 1)
  179. min_y = min(max(offset_y, 0), shape_y - 1)
  180. max_x = min(max(offset_x + shape_arr.arr.shape[1], 0), shape_x - 1)
  181. max_y = min(max(offset_y + shape_arr.arr.shape[0], 0), shape_y - 1)
  182. occupied_slice = self._occupied[min_y:max_y, min_x:max_x]
  183. # we use a slice of shape because it can be out of bounds
  184. new_occupied = numpy.where(shape_arr.arr[
  185. min_y - offset_y:max_y - offset_y, min_x - offset_x:max_x - offset_x] == 1)
  186. if update_empty and new_occupied:
  187. self._is_empty = False
  188. occupied_slice[new_occupied] = 1
  189. # Set priority to low (= high number), so it won't get picked at trying out.
  190. prio_slice = self._priority[min_y:max_y, min_x:max_x]
  191. prio_slice[new_occupied] = 999
  192. # If you want to see how the rasterized arranger build plate looks like, uncomment this code
  193. # numpy.set_printoptions(linewidth=500, edgeitems=200)
  194. # print(self._occupied.shape)
  195. # print(self._occupied)
  196. @property
  197. def isEmpty(self):
  198. return self._is_empty