123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221 |
- # Copyright (c) 2018 Ultimaker B.V.
- # Cura is released under the terms of the LGPLv3 or higher.
- from typing import List
- from UM.Scene.Iterator.DepthFirstIterator import DepthFirstIterator
- from UM.Logger import Logger
- from UM.Math.Polygon import Polygon
- from UM.Math.Vector import Vector
- from UM.Scene.SceneNode import SceneNode
- from cura.Arranging.ShapeArray import ShapeArray
- from cura.Scene import ZOffsetDecorator
- from collections import namedtuple
- import numpy
- import copy
- ## Return object for bestSpot
- LocationSuggestion = namedtuple("LocationSuggestion", ["x", "y", "penalty_points", "priority"])
- ## The Arrange classed is used together with ShapeArray. Use it to find
- # good locations for objects that you try to put on a build place.
- # Different priority schemes can be defined so it alters the behavior while using
- # the same logic.
- #
- # Note: Make sure the scale is the same between ShapeArray objects and the Arrange instance.
- class Arrange:
- build_volume = None
- def __init__(self, x, y, offset_x, offset_y, scale= 0.5):
- self._scale = scale # convert input coordinates to arrange coordinates
- world_x, world_y = int(x * self._scale), int(y * self._scale)
- self._shape = (world_y, world_x)
- self._priority = numpy.zeros((world_y, world_x), dtype=numpy.int32) # beware: these are indexed (y, x)
- self._priority_unique_values = []
- self._occupied = numpy.zeros((world_y, world_x), dtype=numpy.int32) # beware: these are indexed (y, x)
- self._offset_x = int(offset_x * self._scale)
- self._offset_y = int(offset_y * self._scale)
- self._last_priority = 0
- self._is_empty = True
- ## Helper to create an Arranger instance
- #
- # Either fill in scene_root and create will find all sliceable nodes by itself,
- # or use fixed_nodes to provide the nodes yourself.
- # \param scene_root Root for finding all scene nodes
- # \param fixed_nodes Scene nodes to be placed
- @classmethod
- def create(cls, scene_root = None, fixed_nodes = None, scale = 0.5, x = 350, y = 250, min_offset = 8):
- arranger = Arrange(x, y, x // 2, y // 2, scale = scale)
- arranger.centerFirst()
- if fixed_nodes is None:
- fixed_nodes = []
- for node_ in DepthFirstIterator(scene_root):
- # Only count sliceable objects
- if node_.callDecoration("isSliceable"):
- fixed_nodes.append(node_)
- # Place all objects fixed nodes
- for fixed_node in fixed_nodes:
- vertices = fixed_node.callDecoration("getConvexHullHead") or fixed_node.callDecoration("getConvexHull")
- if not vertices:
- continue
- vertices = vertices.getMinkowskiHull(Polygon.approximatedCircle(min_offset))
- points = copy.deepcopy(vertices._points)
- shape_arr = ShapeArray.fromPolygon(points, scale = scale)
- arranger.place(0, 0, shape_arr)
- # If a build volume was set, add the disallowed areas
- if Arrange.build_volume:
- disallowed_areas = Arrange.build_volume.getDisallowedAreasNoBrim()
- for area in disallowed_areas:
- points = copy.deepcopy(area._points)
- shape_arr = ShapeArray.fromPolygon(points, scale = scale)
- arranger.place(0, 0, shape_arr, update_empty = False)
- return arranger
- ## This resets the optimization for finding location based on size
- def resetLastPriority(self):
- self._last_priority = 0
- ## Find placement for a node (using offset shape) and place it (using hull shape)
- # return the nodes that should be placed
- # \param node
- # \param offset_shape_arr ShapeArray with offset, for placing the shape
- # \param hull_shape_arr ShapeArray without offset, used to find location
- def findNodePlacement(self, node: SceneNode, offset_shape_arr: ShapeArray, hull_shape_arr: ShapeArray, step = 1):
- best_spot = self.bestSpot(
- hull_shape_arr, start_prio = self._last_priority, step = step)
- x, y = best_spot.x, best_spot.y
- # Save the last priority.
- self._last_priority = best_spot.priority
- # Ensure that the object is above the build platform
- node.removeDecorator(ZOffsetDecorator.ZOffsetDecorator)
- if node.getBoundingBox():
- center_y = node.getWorldPosition().y - node.getBoundingBox().bottom
- else:
- center_y = 0
- if x is not None: # We could find a place
- node.setPosition(Vector(x, center_y, y))
- found_spot = True
- self.place(x, y, offset_shape_arr) # place the object in arranger
- else:
- Logger.log("d", "Could not find spot!"),
- found_spot = False
- node.setPosition(Vector(200, center_y, 100))
- return found_spot
- ## Fill priority, center is best. Lower value is better
- # This is a strategy for the arranger.
- def centerFirst(self):
- # Square distance: creates a more round shape
- self._priority = numpy.fromfunction(
- lambda j, i: (self._offset_x - i) ** 2 + (self._offset_y - j) ** 2, self._shape, dtype=numpy.int32)
- self._priority_unique_values = numpy.unique(self._priority)
- self._priority_unique_values.sort()
- ## Fill priority, back is best. Lower value is better
- # This is a strategy for the arranger.
- def backFirst(self):
- self._priority = numpy.fromfunction(
- lambda j, i: 10 * j + abs(self._offset_x - i), self._shape, dtype=numpy.int32)
- self._priority_unique_values = numpy.unique(self._priority)
- self._priority_unique_values.sort()
- ## Return the amount of "penalty points" for polygon, which is the sum of priority
- # None if occupied
- # \param x x-coordinate to check shape
- # \param y y-coordinate
- # \param shape_arr the ShapeArray object to place
- def checkShape(self, x, y, shape_arr):
- x = int(self._scale * x)
- y = int(self._scale * y)
- offset_x = x + self._offset_x + shape_arr.offset_x
- offset_y = y + self._offset_y + shape_arr.offset_y
- if offset_x < 0 or offset_y < 0:
- return None # out of bounds in self._occupied
- occupied_x_max = offset_x + shape_arr.arr.shape[1]
- occupied_y_max = offset_y + shape_arr.arr.shape[0]
- if occupied_x_max > self._occupied.shape[1] + 1 or occupied_y_max > self._occupied.shape[0] + 1:
- return None # out of bounds in self._occupied
- occupied_slice = self._occupied[
- offset_y:occupied_y_max,
- offset_x:occupied_x_max]
- try:
- if numpy.any(occupied_slice[numpy.where(shape_arr.arr == 1)]):
- return None
- except IndexError: # out of bounds if you try to place an object outside
- return None
- prio_slice = self._priority[
- offset_y:offset_y + shape_arr.arr.shape[0],
- offset_x:offset_x + shape_arr.arr.shape[1]]
- return numpy.sum(prio_slice[numpy.where(shape_arr.arr == 1)])
- ## Find "best" spot for ShapeArray
- # Return namedtuple with properties x, y, penalty_points, priority.
- # \param shape_arr ShapeArray
- # \param start_prio Start with this priority value (and skip the ones before)
- # \param step Slicing value, higher = more skips = faster but less accurate
- def bestSpot(self, shape_arr, start_prio = 0, step = 1):
- start_idx_list = numpy.where(self._priority_unique_values == start_prio)
- if start_idx_list:
- start_idx = start_idx_list[0][0]
- else:
- start_idx = 0
- for priority in self._priority_unique_values[start_idx::step]:
- tryout_idx = numpy.where(self._priority == priority)
- for idx in range(len(tryout_idx[0])):
- x = tryout_idx[1][idx]
- y = tryout_idx[0][idx]
- projected_x = int((x - self._offset_x) / self._scale)
- projected_y = int((y - self._offset_y) / self._scale)
- penalty_points = self.checkShape(projected_x, projected_y, shape_arr)
- if penalty_points is not None:
- return LocationSuggestion(x = projected_x, y = projected_y, penalty_points = penalty_points, priority = priority)
- return LocationSuggestion(x = None, y = None, penalty_points = None, priority = priority) # No suitable location found :-(
- ## Place the object.
- # Marks the locations in self._occupied and self._priority
- # \param x x-coordinate
- # \param y y-coordinate
- # \param shape_arr ShapeArray object
- # \param update_empty updates the _is_empty, used when adding disallowed areas
- def place(self, x, y, shape_arr, update_empty = True):
- x = int(self._scale * x)
- y = int(self._scale * y)
- offset_x = x + self._offset_x + shape_arr.offset_x
- offset_y = y + self._offset_y + shape_arr.offset_y
- shape_y, shape_x = self._occupied.shape
- min_x = min(max(offset_x, 0), shape_x - 1)
- min_y = min(max(offset_y, 0), shape_y - 1)
- max_x = min(max(offset_x + shape_arr.arr.shape[1], 0), shape_x - 1)
- max_y = min(max(offset_y + shape_arr.arr.shape[0], 0), shape_y - 1)
- occupied_slice = self._occupied[min_y:max_y, min_x:max_x]
- # we use a slice of shape because it can be out of bounds
- new_occupied = numpy.where(shape_arr.arr[
- min_y - offset_y:max_y - offset_y, min_x - offset_x:max_x - offset_x] == 1)
- if update_empty and new_occupied:
- self._is_empty = False
- occupied_slice[new_occupied] = 1
- # Set priority to low (= high number), so it won't get picked at trying out.
- prio_slice = self._priority[min_y:max_y, min_x:max_x]
- prio_slice[new_occupied] = 999
- # If you want to see how the rasterized arranger build plate looks like, uncomment this code
- # numpy.set_printoptions(linewidth=500, edgeitems=200)
- # print(self._occupied.shape)
- # print(self._occupied)
- @property
- def isEmpty(self):
- return self._is_empty
|