1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
# Copyright (c) 2019 Ultimaker B.V.
# Cura is released under the terms of the LGPLv3 or higher.
from typing import List
from UM.Scene.Iterator import Iterator
from UM.Scene.SceneNode import SceneNode
from functools import cmp_to_key
class OneAtATimeIterator(Iterator.Iterator):
"""Iterator that returns a list of nodes in the order that they need to be printed
If there is no solution an empty list is returned.
Take note that the list of nodes can have children (that may or may not contain mesh data)
"""
def __init__(self, scene_node) -> None:
super().__init__(scene_node) # Call super to make multiple inheritance work.
self._hit_map = [[]] # type: List[List[bool]] # For each node, which other nodes this hits. A grid of booleans on which nodes hit which.
self._original_node_list = [] # type: List[SceneNode] # The nodes that need to be checked for collisions.
def _fillStack(self) -> None:
"""Fills the ``_node_stack`` with a list of scene nodes that need to be printed in order. """
node_list = []
for node in self._scene_node.getChildren():
if not issubclass(type(node), SceneNode):
continue
# Node can't be printed, so don't bother sending it.
if getattr(node, "_outside_buildarea", False):
continue
if node.callDecoration("getConvexHull"):
node_list.append(node)
if len(node_list) < 2:
self._node_stack = node_list[:]
return
# Copy the list
self._original_node_list = node_list[:]
# Initialise the hit map (pre-compute all hits between all objects)
self._hit_map = [[self._checkHit(i, j) for i in node_list] for j in node_list]
# Check if we have to files that block each other. If this is the case, there is no solution!
for a in range(0, len(node_list)):
for b in range(0, len(node_list)):
if a != b and self._hit_map[a][b] and self._hit_map[b][a]:
return
# Sort the original list so that items that block the most other objects are at the beginning.
# This does not decrease the worst case running time, but should improve it in most cases.
sorted(node_list, key = cmp_to_key(self._calculateScore))
todo_node_list = [_ObjectOrder([], node_list)]
while len(todo_node_list) > 0:
current = todo_node_list.pop()
for node in current.todo:
# Check if the object can be placed with what we have and still allows for a solution in the future
if not self._checkHitMultiple(node, current.order) and not self._checkBlockMultiple(node, current.todo):
# We found a possible result. Create new todo & order list.
new_todo_list = current.todo[:]
new_todo_list.remove(node)
new_order = current.order[:] + [node]
if len(new_todo_list) == 0:
# We have no more nodes to check, so quit looking.
self._node_stack = new_order
return
todo_node_list.append(_ObjectOrder(new_order, new_todo_list))
self._node_stack = [] #No result found!
# Check if first object can be printed before the provided list (using the hit map)
def _checkHitMultiple(self, node: SceneNode, other_nodes: List[SceneNode]) -> bool:
node_index = self._original_node_list.index(node)
for other_node in other_nodes:
other_node_index = self._original_node_list.index(other_node)
if self._hit_map[node_index][other_node_index]:
return True
return False
def _checkBlockMultiple(self, node: SceneNode, other_nodes: List[SceneNode]) -> bool:
"""Check for a node whether it hits any of the other nodes.
:param node: The node to check whether it collides with the other nodes.
:param other_nodes: The nodes to check for collisions.
:return: returns collision between nodes
"""
node_index = self._original_node_list.index(node)
for other_node in other_nodes:
other_node_index = self._original_node_list.index(other_node)
if self._hit_map[other_node_index][node_index] and node_index != other_node_index:
return True
return False
def _calculateScore(self, a: SceneNode, b: SceneNode) -> int:
"""Calculate score simply sums the number of other objects it 'blocks'
:param a: node
:param b: node
:return: sum of the number of other objects
"""
score_a = sum(self._hit_map[self._original_node_list.index(a)])
score_b = sum(self._hit_map[self._original_node_list.index(b)])
return score_a - score_b
def _checkHit(self, a: SceneNode, b: SceneNode) -> bool:
"""Checks if a can be printed before b
:param a: node
:param b: node
:return: true if a can be printed before b
"""
if a == b:
return False
a_hit_hull = a.callDecoration("getConvexHullBoundary")
b_hit_hull = b.callDecoration("getConvexHullHeadFull")
overlap = a_hit_hull.intersectsPolygon(b_hit_hull)
if overlap:
return True
# Adhesion areas must never overlap, regardless of printing order
# This would cause over-extrusion
a_hit_hull = a.callDecoration("getAdhesionArea")
b_hit_hull = b.callDecoration("getAdhesionArea")
overlap = a_hit_hull.intersectsPolygon(b_hit_hull)
if overlap:
return True
else:
return False
class _ObjectOrder:
"""Internal object used to keep track of a possible order in which to print objects."""
def __init__(self, order: List[SceneNode], todo: List[SceneNode]) -> None:
"""Creates the _ObjectOrder instance.
:param order: List of indices in which to print objects, ordered by printing order.
:param todo: List of indices which are not yet inserted into the order list.
"""
self.order = order
self.todo = todo
|
