Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs	(revision 15520)
@@ -74,5 +74,5 @@
     private Dictionary<int, DiffuseMaterial> materials;
 
-    public ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>> ResidualSpaces { get; set; }
+    public ObservableDictionary<BinPacking3D.PackingPosition, ResidualSpace> ResidualSpaces { get; set; }
     public ObservableCollection<BinPacking3D.PackingPosition> ExtremePoints { get; set; }
 
@@ -81,5 +81,5 @@
       camMain.Position = new Point3D(0.5, 3, 3); // for design time we use a different camera position 
       materials = new Dictionary<int, DiffuseMaterial>();
-      ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>>();
+      ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, ResidualSpace>();
       ExtremePoints = new ObservableCollection<BinPacking3D.PackingPosition>();
       selectedExtremePointIndex = -1;
@@ -248,7 +248,7 @@
           extremePoint.Y,
           extremePoint.Z,
-          rs.Item1,
-          rs.Item2,
-          rs.Item3);
+          rs.Width,
+          rs.Height,
+          rs.Depth);
 
       }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs	(revision 15520)
@@ -75,6 +75,6 @@
         itemSelection.Items.Add(item.Key);
       }
-      foreach (var ep in packing.ExtremePoints) {
-        var rs = ((BinPacking3D.BinPacking3D)packing).ResidualSpace[ep];
+      foreach (var ep in ((BinPacking3D.BinPacking3D)packing).ExtremePoints) {
+        var rs = ((BinPacking3D.BinPacking3D)packing).ResidualSpaces[ep];
         extremePointsSelection.Items.Add($"({ep.X}, {ep.Y}, {ep.Z})");
         packingPlan3D.ExtremePoints.Add(ep);
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs	(revision 15520)
@@ -31,7 +31,10 @@
   [StorableClass]
   public class BinPacking2D : BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> {
+    [Storable]
+    public SortedSet<PackingPosition> ExtremePoints { get; protected set; }
 
     public BinPacking2D(PackingShape binShape)
       : base(binShape) {
+      ExtremePoints = new SortedSet<PackingPosition>();
       OccupationLayers = new Dictionary<int, List<int>>();
       ExtremePoints.Add(binShape.Origin);
@@ -46,4 +49,6 @@
         OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
       }
+
+      this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p)));
     }
     public override IDeepCloneable Clone(Cloner cloner) {
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs	(revision 15520)
@@ -36,26 +36,31 @@
 
     [Storable]
-    public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; set; }
-
-
+    public Dictionary<PackingPosition, ResidualSpace> ResidualSpaces { get; set; }
+
+    [Storable]
+    public SortedSet<PackingPosition> ExtremePoints { get; protected set; }
 
 
     public BinPacking3D(PackingShape binShape)
       : base(binShape) {
-      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
+      ExtremePoints = new SortedSet<PackingPosition>();
+      ResidualSpaces = new Dictionary<PackingPosition, ResidualSpace>();
       
       ExtremePoints.Add(binShape.Origin);
-      ResidualSpace.Add(binShape.Origin, new Tuple<int, int, int>(BinShape.Width, BinShape.Height, BinShape.Depth));
-
-//      AddExtremePoint(binShape.Origin);
-    }
+      ResidualSpaces.Add(binShape.Origin, new ResidualSpace(BinShape.Width, BinShape.Height, BinShape.Depth));
+    }
+
     [StorableConstructor]
     protected BinPacking3D(bool deserializing) : base(deserializing) { }
+
     protected BinPacking3D(BinPacking3D original, Cloner cloner)
       : base(original, cloner) {
-      this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
-      foreach (var o in original.ResidualSpace)
-        this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3));
-    }
+      this.ResidualSpaces = new Dictionary<PackingPosition, ResidualSpace>();
+      foreach (var o in original.ResidualSpaces)
+        this.ResidualSpaces.Add(cloner.Clone(o.Key), ResidualSpace.Create(o.Value));
+
+      this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p)));
+    }
+
     public override IDeepCloneable Clone(Cloner cloner) {
       return new BinPacking3D(this, cloner);
@@ -67,6 +72,6 @@
       // BackwardsCompatibility3.3
       #region Backwards compatible code, remove with 3.4
-      if (ResidualSpace == null)
-        ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
+      if (ResidualSpaces == null)
+        ResidualSpaces = new Dictionary<PackingPosition, ResidualSpace>();
       #endregion
     }
@@ -85,5 +90,5 @@
       Positions[itemID] = position;
       ExtremePoints.Remove(position);
-      ResidualSpace.Remove(position);
+      ResidualSpaces.Remove(position);
     }
 
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.cs	(revision 15520)
@@ -1,4 +1,5 @@
 ﻿using HeuristicLab.Common;
 using HeuristicLab.Problems.BinPacking3D.Geometry;
+using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
 using System;
 using System.Collections.Generic;
@@ -11,7 +12,18 @@
 
 
-    public abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
-
-    public abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
+    public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      UpdateExtremePoints(binPacking, item, position);
+      UpdateResidualSpace(binPacking, item, position);
+    }
+
+    protected abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
+
+    /// <summary>
+    /// Updates the residual space for a given bin packing
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
     protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
 
@@ -23,5 +35,5 @@
     /// <param name="newItem"></param>
     /// <param name="position"></param>
-    protected virtual void GenerateNewExtremePointsForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
+    protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
@@ -35,5 +47,5 @@
         var below = ProjectDown(binPacking, sourcePoint);
         var residualSpace = CalculateResidualSpace(binPacking, below);
-        if (IsNonZero(residualSpace)
+        if (!residualSpace.IsZero()
           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -45,5 +57,5 @@
         var back = ProjectBackward(binPacking, sourcePoint);
         residualSpace = CalculateResidualSpace(binPacking, back);
-        if (IsNonZero(residualSpace)
+        if (!residualSpace.IsZero()
           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -60,5 +72,5 @@
         var left = ProjectLeft(binPacking, sourcePoint);
         var residualSpace = CalculateResidualSpace(binPacking, left);
-        if (IsNonZero(residualSpace)
+        if (!residualSpace.IsZero()
           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -70,5 +82,5 @@
         var back = ProjectBackward(binPacking, sourcePoint);
         residualSpace = CalculateResidualSpace(binPacking, back);
-        if (IsNonZero(residualSpace)
+        if (!residualSpace.IsZero()
           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -85,5 +97,5 @@
         var below = ProjectDown(binPacking, sourcePoint);
         var residualSpace = CalculateResidualSpace(binPacking, below);
-        if (IsNonZero(residualSpace)
+        if (!residualSpace.IsZero()
           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -95,5 +107,5 @@
         var left = ProjectLeft(binPacking, sourcePoint);
         residualSpace = CalculateResidualSpace(binPacking, left);
-        if (IsNonZero(residualSpace)
+        if (!residualSpace.IsZero()
           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -171,9 +183,4 @@
     #region Residual space
 
-
-
-    protected virtual bool IsNonZero(Tuple<int, int, int> space) {
-      return space.Item1 > 0 && space.Item2 > 0 && space.Item3 > 0;
-    }
 
     /// <summary>
@@ -184,11 +191,11 @@
     /// <param name="residualSpace"></param>
     /// <returns></returns>
-    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, Tuple<int, int, int> residualSpace) {
-      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpace[x]));
-      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpace[x]));
-    }
-
-    /// <summary>
-    /// 
+    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
+      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpaces[x]));
+      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpaces[x]));
+    }
+
+    /// <summary>
+    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
     /// </summary>
     /// <param name="pos"></param>
@@ -197,8 +204,8 @@
     /// <param name="rsEp"></param>
     /// <returns></returns>
-    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
-      return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
-          && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
-          && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
+    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
+      return rsEp.Width >= pos.X - ep.X + rsPos.Width
+          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
+          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;
     }
 
@@ -210,5 +217,11 @@
     /// <param name="pos"></param>
     /// <returns>A Tuple(width, Height, Depth)</width></returns>
-    protected Tuple<int, int, int> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
+    protected virtual ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
+      //return ResidualSpaceCalculator.Create().CalculateResidualSpace(binPacking, pos).First();
+      return new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
+    }
+
+    protected virtual Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
+
       if (pos == null) {
         return Tuple.Create(0, 0, 0);
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/IExtremePointCreator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/IExtremePointCreator.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/IExtremePointCreator.cs	(revision 15520)
@@ -15,13 +15,7 @@
     /// <param name="item"></param>
     /// <param name="position"></param>
-    void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
+    void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position);
 
-    /// <summary>
-    /// Updates the residual space for a given bin packing
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
+    
   }
 }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs	(revision 15520)
@@ -1,4 +1,5 @@
 ﻿using HeuristicLab.Common;
 using HeuristicLab.Problems.BinPacking3D.Geometry;
+using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
 using System;
 using System.Collections.Generic;
@@ -10,101 +11,162 @@
   /// <summary>
   /// This extreme point creation class uses the line projection based method for creating extreme points.
+  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
   /// </summary>
   public class LineProjectionBasedEPCreator : ExtremePointCreator {
 
 
-    
-
-    public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      // Before any extreme point for an item can be created, each residual space must be resized if the new item is in the residual space.
-      // If the residual spaces were not updated, it could be that an extreme point won't be generated because it lies in a residual space which 
-      // size isn't correct anymore.
-      RecalculateResidualSpaces(binPacking, item, position);
-
-      GenerateNewExtremePointsForNewItem(binPacking, item, position);
-
-      foreach (var ep in GetEpsOnLeft(binPacking, item, position)) {
+
+
+    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      // After a item has been placed, the residual space has to be recalculated.
+      //RecalculateResidualSpaces(binPacking);
+
+      //GenerateNewExtremePointsForItem(binPacking, item, position);
+
+      binPacking.ExtremePoints.Clear();
+      binPacking.ResidualSpaces.Clear();
+
+      foreach (var i in binPacking.Items) {
+        PackingItem it = i.Value;
+        PackingPosition p = binPacking.Positions[i.Key];
+        GenerateNewExtremePointsForItem(binPacking, it, p);
+      }
+      //RecalculateResidualSpaces(binPacking);
+    }
+
+    /// <summary>
+    /// Adds an new extreme point an the related residual space to a given bin packing.
+    /// - The given position has to be valid
+    /// - The residual space must not be zero
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
+      if (position == null) {
+        return false;
+      }
+
+      if (PointIsInItem(binPacking, new Vector3D(position))) {
+        return false;
+      }
+
+      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
+
+      if (rs.IsZero()) {
+        return false;
+      }
+
+      if (!binPacking.ExtremePoints.Add(position)) {
+        return false;
+      }
+
+      binPacking.ResidualSpaces.Add(position, rs);
+      return true;
+    }
+
+    /// <summary>
+    /// Getnerates the extreme points for a given item.
+    /// It creates extreme points by using a point projection based method and
+    /// creates points by using an edge projection based method.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="newItem"></param>
+    /// <param name="position"></param>
+    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
+      PointProjectionForNewItem(binPacking, newItem, position);
+      EdgeProjectionForNewItem(binPacking, newItem, position);
+    }
+
+    #region Extreme point creation by using a point projection based method
+
+    /// <summary>
+    /// This method creates extreme points by using a point projection based method.
+    /// For each item there will be three points created and each of the point will be projected twice.
+    /// The direction of the projection depends on position of the point.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="newItem"></param>
+    /// <param name="position"></param>
+    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
+      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
+      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
+      var binShape = binPacking.BinShape;
+      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
+      PointProjection(binPacking, sourcePoint, ProjectDown);
+      PointProjection(binPacking, sourcePoint, ProjectBackward);
+
+      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
+      PointProjection(binPacking, sourcePoint, ProjectLeft);
+      PointProjection(binPacking, sourcePoint, ProjectBackward);
+
+      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
+      PointProjection(binPacking, sourcePoint, ProjectDown);
+      PointProjection(binPacking, sourcePoint, ProjectLeft);
+    }
+
+
+    /// <summary>
+    /// Projects a given point by using the given projection method to the neares item.
+    /// The given projection method returns a point which lies on a side of the nearest item in the direction. 
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="position"></param>
+    /// <param name="projectionMethod"></param>
+    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
+      Vector3D sourcePoint = new Vector3D(position);
+      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
+        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
+        AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
+      }
+    }
+    #endregion
+
+    #region Extreme point creation by using an edge projection based method
+
+    /// <summary>
+    /// This method creates extreme points be projecting the edges of a given item 
+    ///   - left
+    ///   - back
+    ///   - down.
+    /// A extreme point will be created, if an edge instersects with an edge of another item.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="newItem"></param>
+    /// <param name="position"></param>
+    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
+      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
+      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
+      var binShape = binPacking.BinShape;
+
+      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
         AddExtremePoint(binPacking, ep);
       }
 
-      foreach (var ep in GetEpsBelow(binPacking, item, position)) {
+      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
         AddExtremePoint(binPacking, ep);
       }
 
-      foreach (var ep in GetEpsBehind(binPacking, item, position)) {
+      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
         AddExtremePoint(binPacking, ep);
       }
     }
-
-    /// <summary>
-    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
-    /// </summary>
-    /// <param name="pos">New Position</param>
-    /// <param name="rsPos"></param>
-    /// <param name="ep"></param>
-    /// <param name="rsEp"></param>
-    /// <returns></returns>
-    protected override bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
-      bool x = pos.X >= ep.X && rsPos.Item1 + pos.X <= rsEp.Item1 + ep.X;
-      bool y = (pos.Y >= ep.Y && pos.Y == 0 || pos.Y > ep.Y && pos.Y > 0) && rsPos.Item2 + pos.Y <= rsEp.Item2 + ep.Y;
-      bool z = pos.Z >= ep.Z && rsPos.Item3 + pos.Z <= rsEp.Item3 + ep.Z;
-      return x && y && z;
-    }
-
-    public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      foreach (var ep in binPacking.ExtremePoints.ToList()) {
-        var rs = binPacking.ResidualSpace[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.Item1, diff);
-            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
-            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.Item2, diff);
-            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
-            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.Item3, diff);
-          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
-          changed = true;
-        }
-
-        if (changed) {
-          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
-            binPacking.ResidualSpace[ep] = rs;
-          } else {
-            binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpace.Remove(ep);
-          }
-        }
-      }
+    #endregion
+
+
+    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
       return;
     }
 
-    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
-      if (binPacking.ExtremePoints.Add(position)) {
-        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
-        binPacking.ResidualSpace.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.ResidualSpace[ep], position, rs)) {
-            binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpace.Remove(ep);
-          }
-        }
-        return true;
+    private bool PointIsInItem(BinPacking3D binPacking, Vector3D point) {
+      foreach (var item in binPacking.Items) {
+        PackingPosition position = binPacking.Positions[item.Key];
+        var depth = position.Rotated ? item.Value.Width : item.Value.Depth;
+        var width = position.Rotated ? item.Value.Depth : item.Value.Width;
+        if (position.X <= point.X && point.X < position.X + width &&
+            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
+            position.Z <= point.Z && point.Z < position.Z + depth) {
+          return true;
+        }
       }
       return false;
@@ -118,5 +180,5 @@
     /// <param name="position">Given position</param>
     /// <returns></returns>
-    private bool ItemIsInRs(KeyValuePair<PackingPosition, Tuple<int, int, int>> rs, PackingItem item, PackingPosition position) {
+    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
       return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
     }
@@ -124,34 +186,43 @@
     /// <summary>
     /// Recalculates the residual spaces if needed.
-    /// It checks if an item is in an residual space and if so the residual space will be recalculated
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    private void RecalculateResidualSpaces(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      var recalculatedSpaces = new Dictionary<PackingPosition, Tuple<int, int, int>>();
-      foreach (var rs in binPacking.ResidualSpace) {
-        int width = rs.Value.Item1;
-        int height = rs.Value.Item2;
-        int depth = rs.Value.Item3;
-
-        if (ItemIsInRs(rs, item, position)) {
-          if (rs.Key.X + rs.Value.Item1 > position.X) {
-            width = position.X - rs.Key.X;
-          } else if (rs.Key.Y + rs.Value.Item2 > position.Y) {
-            height = position.Y - rs.Key.Y;
-          } else if (rs.Key.Z + rs.Value.Item3 > position.Z) {
-            depth = position.Z - rs.Key.Z;
-          }
-        }
-
-        var newRs = new Tuple<int, int, int>(width, height, depth);
-        if (IsNonZero(newRs)) {
-          recalculatedSpaces.Add(rs.Key, newRs);
+    /// It checks if an item is in an residual space and if so the residual space will be recalculated.
+    /// If the residual space has gone to zero, this residual space and its related extreme point will be removed.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    private void RecalculateResidualSpaces(BinPacking3D binPacking) {
+      var recalculatedSpaces = new Dictionary<PackingPosition, ResidualSpace>();
+      foreach (var ep in binPacking.ExtremePoints.ToList()) {
+        var newRs = CalculateResidualSpace(binPacking, new Vector3D(ep));
+        if (!newRs.IsZero() && !PointIsInItem(binPacking, new Vector3D(ep))) {
+          recalculatedSpaces.Add(ep, newRs);
         } else {
-          recalculatedSpaces.Add(rs.Key, rs.Value);
-        }
-      }
-      binPacking.ResidualSpace = recalculatedSpaces;
+          binPacking.ExtremePoints.Remove(ep);
+        }
+      }
+      binPacking.ResidualSpaces = recalculatedSpaces;
+    }
+
+    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      return binPacking.Items.Select(x => new {
+        Item = x.Value,
+        Position = binPacking.Positions[x.Key]
+      }).Where(x => x.Position.Y < position.Y)
+          .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      return binPacking.Items.Select(x => new {
+        Item = x.Value,
+        Position = binPacking.Positions[x.Key]
+      }).Where(x => x.Position.Z < position.Z)
+          .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      return binPacking.Items.Select(x => new {
+        Item = x.Value,
+        Position = binPacking.Positions[x.Key]
+      }).Where(x => x.Position.X < position.X)
+          .Select(x => Tuple.Create(x.Position, x.Item));
     }
 
@@ -164,21 +235,24 @@
     private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
       IList<PackingPosition> eps = new List<PackingPosition>();
-      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, position);
+      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
       var edges = GetProjectionEdgesOnLeft(item, position);
 
-      foreach (var i in items) {
-        foreach (var edge in edges) {
-          var newEps = IntersectionsForItem(edge, GetEdgesOnRight(i.Item2, i.Item1));
-          foreach (var ep in newEps) {
-            try {
-              if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-                var point = ProjectLeft(binPacking, ep);
-                var residualSpace = CalculateResidualSpace(binPacking, point);
-                if (IsNonZero(residualSpace)) {
-                  eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
-                }
-              }
-            } catch {
-              var s = ep;
+      foreach (var otherItem in items) {
+        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
+        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
+          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
+            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
+            var residualSpace = CalculateResidualSpace(binPacking, point);
+            if (!residualSpace.IsZero()) {
+              eps.Add(point.ToPackingPosition(position.AssignedBin));
+            }
+          }
+        }
+        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
+          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
+            var point = ProjectLeft(binPacking, ep);
+            var residualSpace = CalculateResidualSpace(binPacking, point);
+            if (!residualSpace.IsZero()) {
+              eps.Add(point.ToPackingPosition(position.AssignedBin));
             }
           }
@@ -187,4 +261,5 @@
       return eps;
     }
+
 
     /// <summary>
@@ -199,16 +274,21 @@
       var edges = GetProjectionEdgesBelow(item, position);
 
-      foreach (var i in items) {
-        foreach (var edge in edges) {
-          var newEps = IntersectionsForItem(edge, GetEdgesOnTop(i.Item2, i.Item1));
-          foreach (var ep in newEps) {
-            try {
-              var point = ProjectDown(binPacking, ep);
-              var residualSpace = CalculateResidualSpace(binPacking, point);
-              if (IsNonZero(residualSpace)) {
-                eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
-              }
-            } catch {
-              var s = ep;
+      foreach (var otherItem in items) {
+        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
+        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
+          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
+            var point = ProjectDown(binPacking, ep);
+            var residualSpace = CalculateResidualSpace(binPacking, point);
+            if (!residualSpace.IsZero()) {
+              eps.Add(point.ToPackingPosition(position.AssignedBin));
+            }
+          }
+        }
+        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
+          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
+            var point = ProjectDown(binPacking, ep);
+            var residualSpace = CalculateResidualSpace(binPacking, point);
+            if (!residualSpace.IsZero()) {
+              eps.Add(point.ToPackingPosition(position.AssignedBin));
             }
           }
@@ -219,5 +299,5 @@
 
     /// <summary>
-    /// Returns the extremepoints on the left side of an given item
+    /// Returns 
     /// </summary>
     /// <param name="item"></param>
@@ -229,16 +309,21 @@
       var edges = GetProjectionEdgesBehind(item, position);
 
-      foreach (var i in items) {
-        foreach (var edge in edges) {
-          var newEps = IntersectionsForItem(edge, GetEdgesInFront(i.Item2, i.Item1));
-          foreach (var ep in newEps) {
-            try {
-              var point = ProjectBackward(binPacking, ep);
-              var residualSpace = CalculateResidualSpace(binPacking, point);
-              if (IsNonZero(residualSpace)) {
-                eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
-              }
-            } catch {
-              var s = ep;
+      foreach (var otherItem in items) {
+        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
+        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
+          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
+            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
+            var residualSpace = CalculateResidualSpace(binPacking, point);
+            if (!residualSpace.IsZero()) {
+              eps.Add(point.ToPackingPosition(position.AssignedBin));
+            }
+          }
+        }
+        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
+          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
+            var point = ProjectBackward(binPacking, ep);
+            var residualSpace = CalculateResidualSpace(binPacking, point);
+            if (!residualSpace.IsZero()) {
+              eps.Add(point.ToPackingPosition(position.AssignedBin));
             }
           }
@@ -367,14 +452,27 @@
 
     /// <summary>
-    /// Returns a list of extreme points.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <param name="projectedEdge3D"></param>
-    /// <returns></returns>
-    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges) {
+    /// 
+    /// </summary>
+    /// <param name="projectedEdge"></param>
+    /// <param name="edges"></param>
+    /// <returns></returns>
+    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
       IList<Vector3D> eps = new List<Vector3D>();
       foreach (var edge in edges) {
-        var ep = edge.Intersects(projectedEdge);
+        Edge3D e = projectedEdge;
+        if (direction != null) {
+          if (direction.X != 0) {
+            e.Start.X = edge.Start.X;
+            e.End.X = edge.End.X;
+          } else if (direction.Y != 0) {
+            e.Start.Y = edge.Start.Y;
+            e.End.Y = edge.End.Y;
+          } else if (direction.Z != 0) {
+            e.Start.Z = edge.Start.Z;
+            e.End.Z = edge.End.Z;
+          }
+        }
+
+        var ep = edge.Intersects(e);
         if (ep != null) {
           eps.Add(ep);
@@ -385,6 +483,13 @@
 
 
+
     #endregion
 
+    
+    protected override ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
+      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos).First();
+    }
   }
+
+  
 }
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 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs	(revision 15520)
@@ -15,22 +15,22 @@
   /// </summary>
   public class PointProjectionBasedEPCreator : ExtremePointCreator {
-    public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      GenerateNewExtremePointsForNewItem(binPacking, item, position);
+    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      GenerateNewExtremePointsForItem(binPacking, item, position);
 
       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
       foreach (var above in GetItemsAbove(binPacking, position)) {
-        GenerateNewExtremePointsForNewItem(binPacking, above.Item2, above.Item1);
+        GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
       }
       foreach (var front in GetItemsInfront(binPacking, position)) {
-        GenerateNewExtremePointsForNewItem(binPacking, front.Item2, front.Item1);
+        GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
       }
       foreach (var right in GetItemsOnRight(binPacking, position)) {
-        GenerateNewExtremePointsForNewItem(binPacking, right.Item2, right.Item1);
+        GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
       }
     }
     
-    public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
       foreach (var ep in binPacking.ExtremePoints.ToList()) {
-        var rs = binPacking.ResidualSpace[ep];
+        var rs = binPacking.ResidualSpaces[ep];
         var depth = position.Rotated ? item.Width : item.Depth;
         var width = position.Rotated ? item.Depth : item.Width;
@@ -39,12 +39,12 @@
           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.Item1, diff);
-            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
+            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.Item2, diff);
-            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
+            var newRSY = Math.Min(rs.Height, diff);
+            rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
             changed = true;
           }
@@ -55,15 +55,15 @@
             ep.X >= position.X && ep.X < position.X + width) {
           var diff = position.Z - ep.Z;
-          var newRSZ = Math.Min(rs.Item3, diff);
-          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
+          var newRSZ = Math.Min(rs.Depth, diff);
+          rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
           changed = true;
         }
 
         if (changed) {
-          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
-            binPacking.ResidualSpace[ep] = rs;
+          if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
+            binPacking.ResidualSpaces[ep] = rs;
           } else {
             binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpace.Remove(ep);
+            binPacking.ResidualSpaces.Remove(ep);
           }
         }
@@ -83,11 +83,11 @@
       if (binPacking.ExtremePoints.Add(position)) {
         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
-        binPacking.ResidualSpace.Add(position, rs);
+        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.ResidualSpace[ep], position, rs)) {
+          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
             binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpace.Remove(ep);
+            binPacking.ResidualSpaces.Remove(ep);
           }
         }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Edge3D.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Edge3D.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Edge3D.cs	(revision 15520)
@@ -52,5 +52,5 @@
 
     /// <summary>
-    /// Returns a point where the two edges intersects.
+    /// Returns a point where two edges are intersecting.
     /// It returns null if they don't intersect.
     /// </summary>
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs	(revision 15520)
@@ -79,8 +79,8 @@
     }
 
-    public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
-      return X >= pos.X && X < pos.X + rs.Item1
-        && Y >= pos.Y && Y < pos.Y + rs.Item2
-        && Z >= pos.Z && Z < pos.Z + rs.Item3;
+    public bool IsInside(PackingPosition pos, ResidualSpace rs) {
+      return X >= pos.X && X < pos.X + rs.Width
+        && Y >= pos.Y && Y < pos.Y + rs.Height
+        && Z >= pos.Z && Z < pos.Z + rs.Depth;
     }
 
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection.txt
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection.txt	(revision 15520)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection.txt	(revision 15520)
@@ -0,0 +1,7 @@
+BIN DIMENSION
+Length	Width	Height	MaxWeight
+20	20	20	5832
+ITEMS
+ID	Pcs	Length	Width	Height	Weight	Stack	Layer	Rotate	Tilt
+0	1	8	8	4	800	1	0	0	0
+
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection0.txt
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection0.txt	(revision 15520)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection0.txt	(revision 15520)
@@ -0,0 +1,8 @@
+BIN DIMENSION
+Length	Width	Height	MaxWeight
+20	20	20	5832
+ITEMS
+ID	Pcs	Length	Width	Height	Weight	Stack	Layer	Rotate	Tilt
+0	1	8	8	4	800	1	0	0	0
+1	1	4	4	10	800	2	0	0	0
+
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs	(revision 15520)
@@ -80,8 +80,7 @@
       }
       packingBin.PackItem(itemId, packingItem, position);
-      extremePointCreator.UpdateExtremePoints(packingBin, packingItem, position);
-      extremePointCreator.UpdateResidualSpace(packingBin, packingItem, position);
+      extremePointCreator.UpdateBinPacking(packingBin, packingItem, position);
     }
-
+        
     /// <summary>
     /// This method tries to find a valid packing position for an given item in a given packing bin
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs	(revision 15520)
@@ -101,6 +101,6 @@
       foreach (BinPacking3D bp in packingList) {
         foreach (var ep in bp.ExtremePoints) {
-          var rs = bp.ResidualSpace[ep];
-          if (rs.Item1 < item.Width || rs.Item2 < item.Height || rs.Item3 < item.Depth) {
+          var rs = bp.ResidualSpaces[ep];
+          if (rs.Width < item.Width || rs.Height < item.Height || rs.Depth < item.Depth) {
             continue;
           }
@@ -118,8 +118,8 @@
     /// <param name="ep"></param>
     /// <returns></returns>
-    private static int CalculateResidualMerit(Tuple<int, int, int> rs, PackingItem item, PackingPosition ep) {
-      return ((rs.Item1 - item.Width) +
-          (rs.Item2 - item.Height) +
-          (rs.Item3 - item.Depth));
+    private static int CalculateResidualMerit(ResidualSpace rs, PackingItem item, PackingPosition ep) {
+      return ((rs.Width - item.Width) +
+          (rs.Height - item.Height) +
+          (rs.Depth - item.Depth));
     }
   }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpace.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpace.cs	(revision 15520)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpace.cs	(revision 15520)
@@ -0,0 +1,120 @@
+﻿using HeuristicLab.Core;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.Geometry;
+
+namespace HeuristicLab.Problems.BinPacking3D {
+  [Item("ResidualSpace", "Represents a residual space für a 3D bin-packing problem.")]
+  [StorableClass]
+  public class ResidualSpace : Item {
+
+    public static ResidualSpace Create(int width, int height, int depth) {
+      return new ResidualSpace(width, height, depth);
+    }    
+
+    public static ResidualSpace Create(ResidualSpace other) {
+      return new ResidualSpace() {
+        Width = other.Width,
+        Height = other.Height,
+        Depth = other.Depth
+      };
+    }
+
+    public ResidualSpace() {
+      SetZero();
+    }
+
+    public ResidualSpace(int width, int height, int depth) {
+      Width = width;
+      Height = height;
+      Depth = depth;
+    }
+
+    public ResidualSpace(Tuple<int, int, int> rs) {
+      Width = rs.Item1;
+      Height = rs.Item2;
+      Depth = rs.Item3;
+
+      if (IsZero()) {
+        SetZero();
+      }
+    }
+
+    public ResidualSpace(BinPacking3D binPacking, Vector3D point) {
+      Width = binPacking.BinShape.Width - point.X;
+      Height = binPacking.BinShape.Height - point.Y;
+      Depth = binPacking.BinShape.Depth - point.Z;
+
+      if (IsZero()) {
+        SetZero();
+      }
+    }
+
+    [StorableConstructor]
+    protected ResidualSpace(bool deserializing) : base(deserializing) { }
+
+
+    protected ResidualSpace(ResidualSpace original, Cloner cloner) : base(original, cloner) {
+      this.Width = original.Width;
+      this.Height = original.Height;
+      this.Depth = original.Depth;
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new ResidualSpace(this, cloner);
+    }
+
+    [Storable]
+    public int Width { get; set; }
+
+    [Storable]
+    public int Height { get; set; }
+
+    [Storable]
+    public int Depth { get; set; }
+    
+    public override bool Equals(object obj) {
+
+      if (obj == null || GetType() != obj.GetType()) {
+        return false;
+      }
+      ResidualSpace rs = obj as ResidualSpace;            
+      return this.Width == rs.Width && this.Height == rs.Height && this.Depth == rs.Depth;
+    }
+
+    public override string ToString() {
+      return $"({Width},{Height},{Depth})";
+    }
+
+    /*************************************************************
+     * 
+     * ***********************************************************/
+
+    public Tuple<int, int, int> ToTuple() {
+      return new Tuple<int, int, int>(Width, Height, Depth);
+    }
+
+    public PackingItem ToPackingItem() {
+      return new PackingItem() {
+        Width = this.Width,
+        Height = this.Height,
+        Depth = this.Depth
+      };
+    }
+
+    public bool IsZero() {
+      return Width == 0 || Height == 0 || Depth == 0;
+    }
+    
+    public void SetZero() {
+      Width = 0;
+      Height = 0;
+      Depth = 0;
+    }
+  }
+}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/IResidualSpaceCalculator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/IResidualSpaceCalculator.cs	(revision 15520)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/IResidualSpaceCalculator.cs	(revision 15520)
@@ -0,0 +1,19 @@
+﻿using HeuristicLab.Problems.BinPacking3D.Geometry;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
+  public interface IResidualSpaceCalculator {
+
+    /// <summary>
+    /// Calculates all available residual spaces for a given point and returns them packed in a collection.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="point"></param>
+    /// <returns></returns>
+    IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point);
+  }
+}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs	(revision 15520)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs	(revision 15520)
@@ -0,0 +1,180 @@
+﻿using HeuristicLab.Problems.BinPacking3D.Geometry;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
+  internal class ResidualSpaceCalculator : IResidualSpaceCalculator {
+
+    internal ResidualSpaceCalculator() {}
+
+    public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
+      IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
+      var rs1 = CalculateXZY(binPacking, point);
+      var rs2 = CalculateZYX(binPacking, point);
+      var rs3 = CalculateYXZ(binPacking, point);
+
+      residualSpaces.Add(rs1);
+
+
+      if (!residualSpaces.Any(rs => rs.Equals(rs2))) {
+        residualSpaces.Add(rs2);
+      }
+      if (!residualSpaces.Any(rs => rs.Equals(rs3))) {
+        residualSpaces.Add(rs3);
+      }
+      return residualSpaces;
+    }
+
+    private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
+      ResidualSpace rs = new ResidualSpace(binPacking, point);
+
+      LimitResidualSpaceOnRight(binPacking, point, rs);
+      LimitResidualSpaceInFront(binPacking, point, rs);
+      LimitResidualSpaceAbove(binPacking, point, rs);
+      return rs;
+    }
+
+    private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
+      ResidualSpace rs = new ResidualSpace(binPacking, point);
+
+      LimitResidualSpaceInFront(binPacking, point, rs);
+      LimitResidualSpaceAbove(binPacking, point, rs);
+      LimitResidualSpaceOnRight(binPacking, point, rs);
+      return rs;
+    }
+
+    private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
+      ResidualSpace rs = new ResidualSpace(binPacking, point);
+
+      LimitResidualSpaceAbove(binPacking, point, rs);
+      LimitResidualSpaceOnRight(binPacking, point, rs);
+      LimitResidualSpaceInFront(binPacking, point, rs);
+      return rs;
+    }
+    
+    private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
+      if (point.X > position.X && point.X >= position.X + item.Width) {
+        return false;
+      }
+
+      if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
+        return false;
+      }
+      return true;
+    }
+    
+    private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
+      if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
+        return false;
+      }
+
+      if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
+        return false;
+      }
+      return true;
+    }
+
+    private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
+      if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
+        return false;
+      }
+
+      if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
+        return false;
+      }
+      return true;
+    }
+
+    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
+      if (point.X >= position.X) {
+        return false;
+      }
+      var y = OverlapsY(point, residualSpace, position, item);
+      var z = OverlapsZ(point, residualSpace, position, item);
+      return y && z;
+    }
+
+    private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
+      if (point.Z >= position.Z) {
+        return false;
+      }
+      var x = OverlapsX(point, residualSpace, position, item);
+      var y = OverlapsY(point, residualSpace, position, item);
+
+      return x && y;
+    }
+
+    private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
+      if (point.Y >= position.Y) {
+        return false;
+      }
+      var x = OverlapsX(point, residualSpace, position, item);
+      var z = OverlapsZ(point, residualSpace, position, item);
+
+      return x && z;
+    }
+    
+    private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
+      if (residualSpace.IsZero()) {
+        return;
+      }
+      
+      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
+                                  .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
+      if (items.Count() > 0) {
+        foreach (var item in items) {
+          int newWidth = item.Position.X - point.X;
+          if (newWidth <= 0) {
+            residualSpace.SetZero();
+            return;
+          } else if (residualSpace.Width > newWidth) {
+            residualSpace.Width = newWidth;
+          }
+        }
+      }      
+    }
+
+    private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
+      if (residualSpace.IsZero()) {
+        return;
+      }
+
+      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
+                                  .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
+      if (items.Count() > 0) {
+        foreach (var item in items) {
+          int newDepth = item.Position.Z - point.Z;
+          if (newDepth <= 0) {
+            residualSpace.SetZero();
+            return;
+          } else if (residualSpace.Depth > newDepth) {
+            residualSpace.Depth = newDepth;
+          }
+        }
+      }
+    }
+
+    private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
+      if (residualSpace.IsZero()) {
+        return;
+      }
+
+      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
+                                  .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
+      if (items.Count() > 0) {
+        foreach (var item in items) {
+          int newHeight = item.Position.Y - point.Y;
+          if (newHeight <= 0) {
+            residualSpace.SetZero();
+            return;
+          } else if (residualSpace.Height > newHeight) {
+            residualSpace.Height = newHeight;
+          }
+        }
+      }
+    }
+  }
+}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculatorFactory.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculatorFactory.cs	(revision 15520)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculatorFactory.cs	(revision 15520)
@@ -0,0 +1,13 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
+  public static class ResidualSpaceCalculatorFactory {
+    public static IResidualSpaceCalculator CreateCalculator() {
+      return new ResidualSpaceCalculator();
+    }
+  }
+}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs	(revision 15520)
@@ -48,6 +48,5 @@
     public TBin BinShape { get; private set; }
 
-    [Storable]
-    public SortedSet<TPos> ExtremePoints { get; protected set; }
+    
 
     public double PackingDensity {
@@ -71,5 +70,4 @@
       Items = new ObservableDictionary<int, TItem>();
       BinShape = (TBin)binShape.Clone();
-      ExtremePoints = new SortedSet<TPos>();
     }
 
@@ -88,5 +86,4 @@
       }
       this.BinShape = (TBin)original.BinShape.Clone(cloner);
-      this.ExtremePoints = new SortedSet<TPos>(original.ExtremePoints.Select(p => cloner.Clone(p)));
     }
     
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj	(revision 15519)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj	(revision 15520)
@@ -130,4 +130,8 @@
     <Compile Include="3D\Encoding\IDecoder.cs" />
     <Compile Include="3D\Evaluators\IEvaluator.cs" />
+    <Compile Include="3D\ResidualSpace.cs" />
+    <Compile Include="3D\ResidualSpaceCalculation\IResidualSpaceCalculator.cs" />
+    <Compile Include="3D\ResidualSpaceCalculation\ResidualSpaceCalculator.cs" />
+    <Compile Include="3D\ResidualSpaceCalculation\ResidualSpaceCalculatorFactory.cs" />
     <Compile Include="3D\Sorting\IOperator.cs" />
     <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" />
