Changes required for printing one at a time

5 files changed, 142 insertions, 9 deletions

diff --git a/cura/ConvexHullDecorator.py b/cura/ConvexHullDecorator.py
index 709731c2e9..c2a6913404 100644
--- a/cura/ConvexHullDecorator.py
+++ b/cura/ConvexHullDecorator.py
@@ -5,6 +5,13 @@ class ConvexHullDecorator(SceneNodeDecorator):
     def __init__(self):
         super().__init__()
         self._convex_hull = None
+        
+        # In case of printing all at once this is the same as the convex hull. For one at the time this is the area without the head.
+        self._convex_hull_boundary = None 
+        
+        # In case of printing all at once this is the same as the convex hull. For one at the time this is area with full head
+        self._convex_hull_head = None
+        
         self._convex_hull_node = None
         self._convex_hull_job = None
         settings = Application.getInstance().getActiveMachine()
@@ -23,6 +30,22 @@ class ConvexHullDecorator(SceneNodeDecorator):
     def getConvexHull(self):
         return self._convex_hull
     
+    def getConvexHullHead(self):
+        if not self._convex_hull_head:
+            return self.getConvexHull()
+        return self._convex_hull_head
+    
+    def getConvexHullBoundary(self):
+        if not self._convex_hull_boundary:
+            return self.getConvexHull()
+        return self._convex_hull_boundary
+    
+    def setConvexHullBoundary(self, hull):
+        self._convex_hull_boundary = hull
+        
+    def setConvexHullHead(self, hull):
+        self._convex_hull_head = hull
+    
     def setConvexHull(self, hull):
         self._convex_hull = hull
     
diff --git a/cura/ConvexHullJob.py b/cura/ConvexHullJob.py
index af3e990123..9de4f13073 100644
--- a/cura/ConvexHullJob.py
+++ b/cura/ConvexHullJob.py
@@ -6,7 +6,7 @@ from UM.Application import Application
 from UM.Math.Polygon import Polygon
 
 import numpy
-
+import copy
 from . import ConvexHullNode
 
 class ConvexHullJob(Job):
@@ -49,6 +49,9 @@ class ConvexHullJob(Job):
         
         if settings.getSettingValueByKey("print_sequence") == "One at a time" and not self._node.getParent().callDecoration("isGroup"):
             # Printing one at a time and it's not an object in a group
+            self._node.callDecoration("setConvexHullBoundary", copy.deepcopy(hull))
+            head_hull = hull.getMinkowskiHull(Polygon(numpy.array(settings.getSettingValueByKey("machine_head_with_fans_polygon"),numpy.float32)))
+            self._node.callDecoration("setConvexHullHead", head_hull)
             hull = hull.getMinkowskiHull(Polygon(numpy.array(settings.getSettingValueByKey("machine_head_polygon"),numpy.float32)))
         hull_node = ConvexHullNode.ConvexHullNode(self._node, hull, Application.getInstance().getController().getScene().getRoot())
         self._node.callDecoration("setConvexHullNode", hull_node)
diff --git a/cura/OneAtATimeIterator.py b/cura/OneAtATimeIterator.py
new file mode 100644
index 0000000000..e617f4b232
--- /dev/null
+++ b/cura/OneAtATimeIterator.py
@@ -0,0 +1,102 @@
+# Copyright (c) 2015 Ultimaker B.V.
+# Cura is released under the terms of the AGPLv3 or higher.
+
+from UM.Scene.Iterator import Iterator
+from functools import cmp_to_key
+
+## 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)
+class OneAtATimeIterator(Iterator.Iterator):
+    def __init__(self, scene_node):
+        super(OneAtATimeIterator, self).__init__(scene_node) # Call super to make multiple inheritence work.
+        self._hit_map = [[]]
+        self._original_node_list = []
+    
+    def _fillStack(self):
+        node_list = []
+        for node in self._scene_node.getChildren():
+            if node.callDecoration("getConvexHull"):
+                node_list.append(node)
+        
+        if len(node_list) < 2:
+            return node_list 
+        
+        self._original_node_list = node_list[:]
+        
+        ## Initialise the hit map (pre-compute all hits between all objects)
+        self._hit_map = [[self._checkHit(j,i) for i in node_list] for j in node_list]
+        
+        # Check if we have to files that block eachother. 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.
+                        todo_node_list = None
+                        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, other_nodes):
+        node_index = self._original_node_list.index(node)
+        for other_node in other_nodes:
+            if self._hit_map[node_index][self._original_node_list.index(other_node)]:
+                return True
+        return False
+    
+    def _checkBlockMultiple(self, node, other_nodes):
+        node_index = self._original_node_list.index(node)
+        for other_node in other_nodes:
+            if self._hit_map[self._original_node_list.index(other_node)][node_index] and node_index != self._original_node_list.index(other_node):
+                return True
+        return False
+    
+    ##  Calculate score simply sums the number of other objects it 'blocks'
+    def _calculateScore(self, a, b):
+        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
+    
+    #   Checks if A can be printed before B
+    def _checkHit(self, a, b):
+        if a == b:
+            return False
+        
+        overlap = a.callDecoration("getConvexHullBoundary").intersectsPolygon(b.callDecoration("getConvexHullHead"))
+        if overlap:
+            return True
+        else: 
+            return False
+        
+
+## Internal object used to keep track of a possible order in which to print objects.      
+class _objectOrder():
+    def __init__(self, order, todo):
+        """
+        :param order:   List of indexes in which to print objects, ordered by printing order.
+        :param todo:    List of indexes which are not yet inserted into the order list.
+        """
+        self.order = order
+        self.todo = todo
+        
\ No newline at end of file
diff --git a/plugins/CuraEngineBackend/CuraEngineBackend.py b/plugins/CuraEngineBackend/CuraEngineBackend.py
index d5e948d0cd..c0eb0aa14d 100644
--- a/plugins/CuraEngineBackend/CuraEngineBackend.py
+++ b/plugins/CuraEngineBackend/CuraEngineBackend.py
@@ -11,6 +11,7 @@ from UM.Signal import Signal
 from UM.Logger import Logger
 from UM.Resources import Resources
 
+from cura.OneAtATimeIterator import OneAtATimeIterator
 from . import Cura_pb2
 from . import ProcessSlicedObjectListJob
 from . import ProcessGCodeJob
@@ -147,6 +148,10 @@ class CuraEngineBackend(Backend):
         msg = Cura_pb2.ObjectList()
 
         #TODO: All at once/one at a time mode
+        #print("Iterator time! ", OneAtATimeIterator(self._scene.getRoot()))
+        #for item in OneAtATimeIterator(self._scene.getRoot()):
+        #    print(item)
+        
         center = Vector()
         for object in objects:
             center += object.getPosition()
diff --git a/resources/settings/fdmprinter.json b/resources/settings/fdmprinter.json
index ba56f217ba..0b717a34d5 100644
--- a/resources/settings/fdmprinter.json
+++ b/resources/settings/fdmprinter.json
@@ -83,20 +83,20 @@
 	{
 	      "default": [
                 [
-                    -15,
-                    15
+                    -20,
+                    10
                 ],
                 [
-                    15,
-                    15
+                    10,
+                    10
                 ],
                 [
-                    15,
-                    -15
+                    10,
+                    -10
                 ],
                 [
-                    -15,
-                    -15
+                    -20,
+                    -10
                 ]
             ]
 	},