Nest2DArrange.py 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
  1. # Copyright (c) 2020 Ultimaker B.V.
  2. # Cura is released under the terms of the LGPLv3 or higher.
  3. import numpy
  4. from pynest2d import Point, Box, Item, NfpConfig, nest
  5. from typing import List, TYPE_CHECKING, Optional, Tuple
  6. from UM.Application import Application
  7. from UM.Logger import Logger
  8. from UM.Math.Matrix import Matrix
  9. from UM.Math.Polygon import Polygon
  10. from UM.Math.Quaternion import Quaternion
  11. from UM.Math.Vector import Vector
  12. from UM.Operations.AddSceneNodeOperation import AddSceneNodeOperation
  13. from UM.Operations.GroupedOperation import GroupedOperation
  14. from UM.Operations.RotateOperation import RotateOperation
  15. from UM.Operations.TranslateOperation import TranslateOperation
  16. if TYPE_CHECKING:
  17. from UM.Scene.SceneNode import SceneNode
  18. from cura.BuildVolume import BuildVolume
  19. def findNodePlacement(nodes_to_arrange: List["SceneNode"], build_volume: "BuildVolume", fixed_nodes: Optional[List["SceneNode"]] = None, factor = 10000) -> Tuple[bool, List[Item]]:
  20. """
  21. Find placement for a set of scene nodes, but don't actually move them just yet.
  22. :param nodes_to_arrange: The list of nodes that need to be moved.
  23. :param build_volume: The build volume that we want to place the nodes in. It gets size & disallowed areas from this.
  24. :param fixed_nodes: List of nods that should not be moved, but should be used when deciding where the others nodes
  25. are placed.
  26. :param factor: The library that we use is int based. This factor defines how accurate we want it to be.
  27. :return: tuple (found_solution_for_all, node_items)
  28. WHERE
  29. found_solution_for_all: Whether the algorithm found a place on the buildplate for all the objects
  30. node_items: A list of the nodes return by libnest2d, which contain the new positions on the buildplate
  31. """
  32. spacing = int(1.5 * factor) # 1.5mm spacing.
  33. machine_width = build_volume.getWidth()
  34. machine_depth = build_volume.getDepth()
  35. build_plate_bounding_box = Box(int(machine_width * factor), int(machine_depth * factor))
  36. if fixed_nodes is None:
  37. fixed_nodes = []
  38. # Add all the items we want to arrange
  39. node_items = []
  40. for node in nodes_to_arrange:
  41. hull_polygon = node.callDecoration("getConvexHull")
  42. if not hull_polygon or hull_polygon.getPoints is None:
  43. Logger.log("w", "Object {} cannot be arranged because it has no convex hull.".format(node.getName()))
  44. continue
  45. converted_points = []
  46. for point in hull_polygon.getPoints():
  47. converted_points.append(Point(int(point[0] * factor), int(point[1] * factor)))
  48. item = Item(converted_points)
  49. node_items.append(item)
  50. # Use a tiny margin for the build_plate_polygon (the nesting doesn't like overlapping disallowed areas)
  51. half_machine_width = 0.5 * machine_width - 1
  52. half_machine_depth = 0.5 * machine_depth - 1
  53. build_plate_polygon = Polygon(numpy.array([
  54. [half_machine_width, -half_machine_depth],
  55. [-half_machine_width, -half_machine_depth],
  56. [-half_machine_width, half_machine_depth],
  57. [half_machine_width, half_machine_depth]
  58. ], numpy.float32))
  59. disallowed_areas = build_volume.getDisallowedAreas()
  60. num_disallowed_areas_added = 0
  61. for area in disallowed_areas:
  62. converted_points = []
  63. # Clip the disallowed areas so that they don't overlap the bounding box (The arranger chokes otherwise)
  64. clipped_area = area.intersectionConvexHulls(build_plate_polygon)
  65. if clipped_area.getPoints() is not None and len(clipped_area.getPoints()) > 2: # numpy array has to be explicitly checked against None
  66. for point in clipped_area.getPoints():
  67. converted_points.append(Point(int(point[0] * factor), int(point[1] * factor)))
  68. disallowed_area = Item(converted_points)
  69. disallowed_area.markAsDisallowedAreaInBin(0)
  70. node_items.append(disallowed_area)
  71. num_disallowed_areas_added += 1
  72. for node in fixed_nodes:
  73. converted_points = []
  74. hull_polygon = node.callDecoration("getConvexHull")
  75. if hull_polygon is not None and hull_polygon.getPoints() is not None and len(hull_polygon.getPoints()) > 2: # numpy array has to be explicitly checked against None
  76. for point in hull_polygon.getPoints():
  77. converted_points.append(Point(int(point[0] * factor), int(point[1] * factor)))
  78. item = Item(converted_points)
  79. item.markAsFixedInBin(0)
  80. node_items.append(item)
  81. num_disallowed_areas_added += 1
  82. config = NfpConfig()
  83. config.accuracy = 1.0
  84. config.alignment = NfpConfig.Alignment.DONT_ALIGN
  85. num_bins = nest(node_items, build_plate_bounding_box, spacing, config)
  86. # Strip the fixed items (previously placed) and the disallowed areas from the results again.
  87. node_items = list(filter(lambda item: not item.isFixed(), node_items))
  88. found_solution_for_all = num_bins == 1
  89. return found_solution_for_all, node_items
  90. def createGroupOperationForArrange(nodes_to_arrange: List["SceneNode"],
  91. build_volume: "BuildVolume",
  92. fixed_nodes: Optional[List["SceneNode"]] = None,
  93. factor = 10000,
  94. add_new_nodes_in_scene: bool = False) -> Tuple[GroupedOperation, int]:
  95. scene_root = Application.getInstance().getController().getScene().getRoot()
  96. found_solution_for_all, node_items = findNodePlacement(nodes_to_arrange, build_volume, fixed_nodes, factor)
  97. not_fit_count = 0
  98. grouped_operation = GroupedOperation()
  99. for node, node_item in zip(nodes_to_arrange, node_items):
  100. if add_new_nodes_in_scene:
  101. grouped_operation.addOperation(AddSceneNodeOperation(node, scene_root))
  102. if node_item.binId() == 0:
  103. # We found a spot for it
  104. rotation_matrix = Matrix()
  105. rotation_matrix.setByRotationAxis(node_item.rotation(), Vector(0, -1, 0))
  106. grouped_operation.addOperation(RotateOperation(node, Quaternion.fromMatrix(rotation_matrix)))
  107. grouped_operation.addOperation(TranslateOperation(node, Vector(node_item.translation().x() / factor, 0,
  108. node_item.translation().y() / factor)))
  109. else:
  110. # We didn't find a spot
  111. grouped_operation.addOperation(
  112. TranslateOperation(node, Vector(200, node.getWorldPosition().y, -not_fit_count * 20), set_position = True))
  113. not_fit_count += 1
  114. return grouped_operation, not_fit_count
  115. def arrange(nodes_to_arrange: List["SceneNode"],
  116. build_volume: "BuildVolume",
  117. fixed_nodes: Optional[List["SceneNode"]] = None,
  118. factor = 10000,
  119. add_new_nodes_in_scene: bool = False) -> bool:
  120. """
  121. Find placement for a set of scene nodes, and move them by using a single grouped operation.
  122. :param nodes_to_arrange: The list of nodes that need to be moved.
  123. :param build_volume: The build volume that we want to place the nodes in. It gets size & disallowed areas from this.
  124. :param fixed_nodes: List of nods that should not be moved, but should be used when deciding where the others nodes
  125. are placed.
  126. :param factor: The library that we use is int based. This factor defines how accuracte we want it to be.
  127. :param add_new_nodes_in_scene: Whether to create new scene nodes before applying the transformations and rotations
  128. :return: found_solution_for_all: Whether the algorithm found a place on the buildplate for all the objects
  129. """
  130. grouped_operation, not_fit_count = createGroupOperationForArrange(nodes_to_arrange, build_volume, fixed_nodes, factor, add_new_nodes_in_scene)
  131. grouped_operation.push()
  132. return not_fit_count == 0