From e80f1b73a3db05566eec79dc91953151d527771c Mon Sep 17 00:00:00 2001
From: daid303 <daid303@gmail.com>
Date: Thu, 4 Apr 2013 14:33:31 +0200
Subject: [PATCH] Add proper slicing order.

---
 Cura/util/objectScene.py | 63 ++++++++++++++++++++++++++++++++++++++--
 Cura/util/sliceEngine.py |  5 ++--
 2 files changed, 62 insertions(+), 6 deletions(-)

diff --git a/Cura/util/objectScene.py b/Cura/util/objectScene.py
index 4ddfdddd..b469c071 100644
--- a/Cura/util/objectScene.py
+++ b/Cura/util/objectScene.py
@@ -1,7 +1,65 @@
 import random
 import numpy
 
-class Scene():
+class _objectOrder(object):
+	def __init__(self, order, todo):
+		self.order = order
+		self.todo = todo
+
+class _objectOrderFinder(object):
+	def __init__(self, scene, offset):
+		self._scene = scene
+		self._offset = offset - numpy.array([0.1,0.1])
+		self._objs = scene.objects()
+		self._leftToRight = True
+		self._frontToBack = True
+		initialList = []
+		for n in xrange(0, len(self._objs)):
+			if scene.checkPlatform(self._objs[n]):
+				initialList.append(n)
+		self._todo = [_objectOrder([], initialList)]
+		while len(self._todo) > 0:
+			current = self._todo.pop()
+			for addIdx in current.todo:
+				if not self._checkHitFor(addIdx, current.order):
+					todoList = current.todo[:]
+					todoList.remove(addIdx)
+					order = current.order[:] + [addIdx]
+					if len(todoList) == 0:
+						self.order = order
+						return
+					self._todo.append(_objectOrder(order, todoList))
+		self.order = None
+
+	def _checkHitFor(self, addIdx, others):
+		for idx in others:
+			if self._checkHit(addIdx, idx):
+				return True
+		return False
+
+	def _checkHit(self, addIdx, idx):
+		addPos = self._scene._objectList[addIdx].getPosition()
+		addSize = self._scene._objectList[addIdx].getSize()
+		pos = self._scene._objectList[idx].getPosition()
+		size = self._scene._objectList[idx].getSize()
+
+		if self._leftToRight:
+			if addPos[0] + addSize[0] / 2 + self._offset[0] <= pos[0] - size[0] / 2:
+				return False
+		else:
+			if addPos[0] - addSize[0] / 2 - self._offset[0] <= pos[0] + size[0] / 2:
+				return False
+
+		if self._frontToBack:
+			if addPos[1] - addSize[1] / 2 - self._offset[1] >= pos[1] + size[1] / 2:
+				return False
+		else:
+			if addPos[1] + addSize[1] / 2 + self._offset[1] >= pos[1] - size[1] / 2:
+				return False
+
+		return True
+
+class Scene(object):
 	def __init__(self):
 		self._objectList = []
 		self._sizeOffsets = numpy.array([3.0,3.0], numpy.float32)
@@ -54,8 +112,7 @@ class Scene():
 			obj.setPosition(obj.getPosition() + offset)
 
 	def printOrder(self):
-		order = range(0, len(self._objectList))
-		return order
+		return _objectOrderFinder(self, self._headOffsets + self._sizeOffsets).order
 
 	def _pushFree(self):
 		for a in self._objectList:
diff --git a/Cura/util/sliceEngine.py b/Cura/util/sliceEngine.py
index 84fab9a7..5eca1544 100644
--- a/Cura/util/sliceEngine.py
+++ b/Cura/util/sliceEngine.py
@@ -47,9 +47,8 @@ class Slicer(object):
 		commandList += ['-b', self._binaryStorageFilename]
 		self._objCount = 0
 		with open(self._binaryStorageFilename, "wb") as f:
-			for obj in scene._objectList:
-				if not scene.checkPlatform(obj):
-					continue
+			for n in scene.printOrder():
+				obj = scene.objects()[n]
 				for mesh in obj._meshList:
 					n = numpy.array(mesh.vertexCount, numpy.int32)
 					f.write(n.tostring())
-- 
2.30.2