Index: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs
===================================================================
--- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs	(revision 15520)
+++ branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs	(revision 15554)
@@ -31,41 +31,45 @@
     
     protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      foreach (var ep in binPacking.ExtremePoints.ToList()) {
-        var rs = binPacking.ResidualSpaces[ep];
-        var depth = position.Rotated ? item.Width : item.Depth;
-        var width = position.Rotated ? item.Depth : item.Width;
-        var changed = false;
-        if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
-          if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
-            var diff = position.X - ep.X;
-            var newRSX = Math.Min(rs.Width, diff);
-            rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
+      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
+        var ep = extremePoint.Key;
+        var residualSpaces = extremePoint.Value as IList<ResidualSpace>;
+        for (int i = 0; i < residualSpaces.Count(); i++) {
+          var rs = residualSpaces[i];
+          var depth = position.Rotated ? item.Width : item.Depth;
+          var width = position.Rotated ? item.Depth : item.Width;
+          var changed = false;
+          if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
+            if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
+              var diff = position.X - ep.X;
+              var newRSX = Math.Min(rs.Width, diff);
+              rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
+              changed = true;
+            }
+            if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
+              var diff = position.Y - ep.Y;
+              var newRSY = Math.Min(rs.Height, diff);
+              rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
+              changed = true;
+            }
+          }
+
+          if (ep.Z <= position.Z &&
+              ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
+              ep.X >= position.X && ep.X < position.X + width) {
+            var diff = position.Z - ep.Z;
+            var newRSZ = Math.Min(rs.Depth, diff);
+            rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
             changed = true;
           }
-          if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
-            var diff = position.Y - ep.Y;
-            var newRSY = Math.Min(rs.Height, diff);
-            rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
-            changed = true;
+
+          if (changed) {
+            if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
+              residualSpaces[i] = rs;
+            } else {
+              binPacking.ExtremePoints.Remove(ep);
+              break;
+            }
           }
-        }
-
-        if (ep.Z <= position.Z &&
-            ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
-            ep.X >= position.X && ep.X < position.X + width) {
-          var diff = position.Z - ep.Z;
-          var newRSZ = Math.Min(rs.Depth, diff);
-          rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
-          changed = true;
-        }
-
-        if (changed) {
-          if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
-            binPacking.ResidualSpaces[ep] = rs;
-          } else {
-            binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpaces.Remove(ep);
-          }
-        }
+        }        
       }
       return;
@@ -81,18 +85,73 @@
     /// <returns></returns>
     protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
-      if (binPacking.ExtremePoints.Add(position)) {
-        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
-        binPacking.ResidualSpaces.Add(position, rs);
-        // Check if the existing extreme points are shadowed by the new point
-        // This is, their residual space fit entirely into the residual space of the new point
-        foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
-          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
+      if (binPacking.ExtremePoints.ContainsKey(position)) {
+        return false;
+      }
+
+      var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));
+      binPacking.ExtremePoints.Add(position, residualSpaces);
+      // Check if the existing extreme points are shadowed by the new point
+      // This is, their residual space fit entirely into the residual space of the new point
+      foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {
+        foreach (var residualSpace in ep.Value) {
+          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {
             binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpaces.Remove(ep);
+            break;
           }
+        }          
+      }
+      return true;
+    }
+
+    /// <summary>
+    /// Calculates the residual space for a given bin packing and position.
+    /// It returns the residual space as a tuple which contains the dimensions
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="pos"></param>
+    /// <returns>A Tuple(width, Height, Depth)</width></returns>
+    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
+      var residualSpaces = new List<ResidualSpace>();
+      var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
+      if (!residualSpace.IsZero()) {
+        residualSpaces.Add(residualSpace);
+      }
+      return residualSpaces;
+    }
+
+    protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
+
+      if (pos == null) {
+        return Tuple.Create(0, 0, 0);
+      }
+      var itemPos = binPacking.Items.Select(x => new {
+        Item = x.Value,
+        Position = binPacking.Positions[x.Key]
+      });
+      Vector3D limit = new Vector3D() {
+        X = binPacking.BinShape.Width,
+        Y = binPacking.BinShape.Height,
+        Z = binPacking.BinShape.Depth
+      };
+
+      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
+        var rightLimit = ProjectRight(binPacking, pos);
+        var upLimit = ProjectUp(binPacking, pos);
+        var forwardLimit = ProjectForward(binPacking, pos);
+        if (rightLimit.X > 0) {
+          limit.X = rightLimit.X;
         }
-        return true;
+        if (upLimit.Y > 0) {
+          limit.Y = upLimit.Y;
+        }
+        if (forwardLimit.Z > 0) {
+          limit.Z = forwardLimit.Z;
+        }
       }
-      return false;
+
+      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
+        return Tuple.Create(0, 0, 0);
+      }
+      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
     }
   }
