source: game/Nuclex.Game/trunk/Source/Packing/CygonRectanglePacker.cs

Last change on this file was 1322, checked in by cygon, 3 years ago

Updated copyright statement for the year 2011

File size: 11.4 KB
Line 
1#region CPL License
2/*
3Nuclex Framework
4Copyright (C) 2002-2011 Nuclex Development Labs
5
6This library is free software; you can redistribute it and/or
7modify it under the terms of the IBM Common Public License as
8published by the IBM Corporation; either version 1.0 of the
9License, or (at your option) any later version.
10
11This library is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14IBM Common Public License for more details.
15
16You should have received a copy of the IBM Common Public
17License along with this library
18*/
19#endregion
20
21using System;
22using System.Collections.Generic;
23using System.Diagnostics;
24
25using Microsoft.Xna.Framework;
26
27namespace Nuclex.Game.Packing {
28
29  /// <summary>Packer using a custom algorithm by Markus 'Cygon' Ewald</summary>
30  /// <remarks>
31  ///   <para>
32  ///     Algorithm conceived by Markus Ewald (cygon at nuclex dot org), though
33  ///     I'm quite sure I'm not the first one to come up with it :)
34  ///   </para>
35  ///   <para>
36  ///     The algorithm always places rectangles as low as possible in the packing
37  ///     area. So, for any new rectangle that is to be added, the packer has to
38  ///     determine the X coordinate at which the rectangle can have the lowest
39  ///     overall height without intersecting any other rectangles.
40  ///   </para>
41  ///   <para>
42  ///     To quickly discover these locations, the packer uses a sophisticated
43  ///     data structure that stores the upper silhouette of the packing area. When
44  ///     a new rectangle needs to be added, only the silouette edges need to be
45  ///     analyzed to find the position where the rectangle would achieve the lowest
46  ///     placement possible in the packing area.
47  ///   </para>
48  /// </remarks>
49  public class CygonRectanglePacker : RectanglePacker {
50
51    #region class SliceStartComparer
52
53    /// <summary>Compares the starting position of height slices</summary>
54    private class SliceStartComparer : IComparer<Point> {
55
56      /// <summary>Provides a default instance for the anchor rank comparer</summary>
57      public static SliceStartComparer Default = new SliceStartComparer();
58
59      /// <summary>Compares the starting position of two height slices</summary>
60      /// <param name="left">Left slice start that will be compared</param>
61      /// <param name="right">Right slice start that will be compared</param>
62      /// <returns>The relation of the two slice starts ranks to each other</returns>
63      public int Compare(Point left, Point right) {
64        return left.X - right.X;
65      }
66
67    }
68
69    #endregion
70
71    /// <summary>Initializes a new rectangle packer</summary>
72    /// <param name="packingAreaWidth">Maximum width of the packing area</param>
73    /// <param name="packingAreaHeight">Maximum height of the packing area</param>
74    public CygonRectanglePacker(int packingAreaWidth, int packingAreaHeight) :
75      base(packingAreaWidth, packingAreaHeight) {
76
77      this.heightSlices = new List<Point>();
78
79      // At the beginning, the packing area is a single slice of height 0
80      this.heightSlices.Add(new Point(0, 0));
81    }
82
83    /// <summary>Tries to allocate space for a rectangle in the packing area</summary>
84    /// <param name="rectangleWidth">Width of the rectangle to allocate</param>
85    /// <param name="rectangleHeight">Height of the rectangle to allocate</param>
86    /// <param name="placement">Output parameter receiving the rectangle's placement</param>
87    /// <returns>True if space for the rectangle could be allocated</returns>
88    public override bool TryPack(
89      int rectangleWidth, int rectangleHeight, out Point placement
90    ) {
91      // If the rectangle is larger than the packing area in any dimension,
92      // it will never fit!
93      if(
94        (rectangleWidth > PackingAreaWidth) || (rectangleHeight > PackingAreaHeight)
95      ) {
96        placement = Point.Zero;
97        return false;
98      }
99
100      // Determine the placement for the new rectangle
101      bool fits = tryFindBestPlacement(rectangleWidth, rectangleHeight, out placement);
102
103      // If a place for the rectangle could be found, update the height slice table to
104      // mark the region of the rectangle as being taken.
105      if(fits)
106        integrateRectangle(placement.X, rectangleWidth, placement.Y + rectangleHeight);
107
108      return fits;
109    }
110
111    /// <summary>Finds the best position for a rectangle of the given dimensions</summary>
112    /// <param name="rectangleWidth">Width of the rectangle to find a position for</param>
113    /// <param name="rectangleHeight">Height of the rectangle to find a position for</param>
114    /// <param name="placement">Receives the best placement found for the rectangle</param>
115    /// <returns>True if a valid placement for the rectangle could be found</returns>
116    private bool tryFindBestPlacement(
117      int rectangleWidth, int rectangleHeight, out Point placement
118    ) {
119      int bestSliceIndex = -1; // Slice index where the best placement was found
120      int bestSliceY = 0; // Y position of the best placement found
121      int bestScore = PackingAreaHeight; // lower == better!
122
123      // This is the counter for the currently checked position. The search works by
124      // skipping from slice to slice, determining the suitability of the location for the
125      // placement of the rectangle.
126      int leftSliceIndex = 0;
127
128      // Determine the slice in which the right end of the rectangle is located when
129      // the rectangle is placed at the far left of the packing area.
130      int rightSliceIndex = this.heightSlices.BinarySearch(
131        new Point(rectangleWidth, 0), SliceStartComparer.Default
132      );
133      if(rightSliceIndex < 0)
134        rightSliceIndex = ~rightSliceIndex;
135
136      while(rightSliceIndex <= this.heightSlices.Count) {
137
138        // Determine the highest slice within the slices covered by the rectangle at
139        // its current placement. We cannot put the rectangle any lower than this without
140        // overlapping the other rectangles.
141        int highest = this.heightSlices[leftSliceIndex].Y;
142        for(int index = leftSliceIndex + 1; index < rightSliceIndex; ++index)
143          if(this.heightSlices[index].Y > highest)
144            highest = this.heightSlices[index].Y;
145
146        // Only process this position if it doesn't leave the packing area
147        if((highest + rectangleHeight <= PackingAreaHeight)) {
148          int score = highest;
149
150          if(score < bestScore) {
151            bestSliceIndex = leftSliceIndex;
152            bestSliceY = highest;
153            bestScore = score;
154          }
155        }
156
157        // Advance the starting slice to the next slice start
158        ++leftSliceIndex;
159        if(leftSliceIndex >= this.heightSlices.Count)
160          break;
161
162        // Advance the ending slice until we're on the proper slice again, given the new
163        // starting position of the rectangle.
164        int rightRectangleEnd = this.heightSlices[leftSliceIndex].X + rectangleWidth;
165        for(; rightSliceIndex <= this.heightSlices.Count; ++rightSliceIndex) {
166          int rightSliceStart;
167          if(rightSliceIndex == this.heightSlices.Count)
168            rightSliceStart = PackingAreaWidth;
169          else
170            rightSliceStart = this.heightSlices[rightSliceIndex].X;
171
172          // Is this the slice we're looking for?
173          if(rightSliceStart > rightRectangleEnd)
174            break;
175        }
176
177        // If we crossed the end of the slice array, the rectangle's right end has left
178        // the packing area, and thus, our search ends.
179        if(rightSliceIndex > this.heightSlices.Count)
180          break;
181
182      } // while rightSliceIndex <= this.heightSlices.Count
183
184      // Return the best placement we found for this rectangle. If the rectangle
185      // didn't fit anywhere, the slice index will still have its initialization value
186      // of -1 and we can report that no placement could be found.
187      if(bestSliceIndex == -1) {
188        placement = Point.Zero;
189        return false;
190      } else {
191        placement = new Point(this.heightSlices[bestSliceIndex].X, bestSliceY);
192        return true;
193      }
194    }
195
196    /// <summary>Integrates a new rectangle into the height slice table</summary>
197    /// <param name="left">Position of the rectangle's left side</param>
198    /// <param name="width">Width of the rectangle</param>
199    /// <param name="bottom">Position of the rectangle's lower side</param>
200    private void integrateRectangle(int left, int width, int bottom) {
201
202      // Find the first slice that is touched by the rectangle
203      int startSlice = this.heightSlices.BinarySearch(
204        new Point(left, 0), SliceStartComparer.Default
205      );
206      int firstSliceOriginalHeight;
207
208      // Since the placement algorithm always places rectangles on the slices,
209      // the binary search should never some up with a miss!
210      Debug.Assert(
211        startSlice >= 0, "Slice starts within another slice"
212      );
213
214      // We scored a direct hit, so we can replace the slice we have hit
215      firstSliceOriginalHeight = this.heightSlices[startSlice].Y;
216      this.heightSlices[startSlice] = new Point(left, bottom);
217
218      int right = left + width;
219      ++startSlice;
220
221      // Special case, the rectangle started on the last slice, so we cannot
222      // use the start slice + 1 for the binary search and the possibly already
223      // modified start slice height now only remains in our temporary
224      // firstSliceOriginalHeight variable
225      if(startSlice >= this.heightSlices.Count) {
226
227        // If the slice ends within the last slice (usual case, unless it has the
228        // exact same width the packing area has), add another slice to return to
229        // the original height at the end of the rectangle.
230        if(right < PackingAreaWidth)
231          this.heightSlices.Add(new Point(right, firstSliceOriginalHeight));
232
233      } else { // The rectangle doesn't start on the last slice
234
235        int endSlice = this.heightSlices.BinarySearch(
236          startSlice, this.heightSlices.Count - startSlice,
237          new Point(right, 0), SliceStartComparer.Default
238        );
239
240        // Another direct hit on the final slice's end?
241        if(endSlice > 0) {
242
243          this.heightSlices.RemoveRange(startSlice, endSlice - startSlice);
244
245        } else { // No direct hit, rectangle ends inside another slice
246
247          // Make index from negative BinarySearch() result
248          endSlice = ~endSlice;
249
250          // Find out to which height we need to return at the right end of
251          // the rectangle
252          int returnHeight;
253          if(endSlice == startSlice)
254            returnHeight = firstSliceOriginalHeight;
255          else
256            returnHeight = this.heightSlices[endSlice - 1].Y;
257
258          // Remove all slices covered by the rectangle and begin a new slice at its end
259          // to return back to the height of the slice on which the rectangle ends.
260          this.heightSlices.RemoveRange(startSlice, endSlice - startSlice);
261          if(right < PackingAreaWidth)
262            this.heightSlices.Insert(startSlice, new Point(right, returnHeight));
263
264        } // if endSlice > 0
265
266      } // if startSlice >= this.heightSlices.Count
267
268    }
269
270    /// <summary>Stores the height silhouette of the rectangles</summary>
271    private List<Point> heightSlices;
272
273  }
274
275} // namespace Nuclex.Game.Packing
Note: See TracBrowser for help on using the repository browser.