JOGL v2.6.0-rc-20250706
JOGL, High-Performance Graphics Binding for Java™ (public API).
RectanglePacker.java
Go to the documentation of this file.
1/*
2 * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 * - Redistribution of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *
11 * - Redistribution in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * Neither the name of Sun Microsystems, Inc. or the names of
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * This software is provided "AS IS," without a warranty of any kind. ALL
20 * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
21 * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
22 * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
23 * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
24 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
25 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
26 * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
27 * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
28 * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
29 * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
30 * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
31 *
32 * You acknowledge that this software is not designed or intended for use
33 * in the design, construction, operation or maintenance of any nuclear
34 * facility.
35 *
36 * Sun gratefully acknowledges that this software was originally authored
37 * and developed by Kenneth Bradley Russell and Christopher John Kline.
38 */
39
40package com.jogamp.opengl.util.packrect;
41
42import java.util.*;
43
44/** Packs rectangles supplied by the user (typically representing
45 image regions) into a larger backing store rectangle (typically
46 representing a large texture). Supports automatic compaction of
47 the space on the backing store, and automatic expansion of the
48 backing store, when necessary. */
49
50public class RectanglePacker {
51 private final BackingStoreManager manager;
52 private Object backingStore;
53 private LevelSet levels;
54 private static final float EXPANSION_FACTOR = 0.5f;
55 private static final float SHRINK_FACTOR = 0.3f;
56
57 private final int initialWidth;
58 private final int initialHeight;
59
60 private int maxWidth = -1;
61 private int maxHeight = -1;
62
63 static class RectHComparator implements Comparator<Rect> {
64 @Override
65 public int compare(final Rect r1, final Rect r2) {
66 return r2.h() - r1.h();
67 }
68
69 @Override
70 public boolean equals(final Object obj) {
71 return this == obj;
72 }
73 }
74 private static final Comparator<Rect> rectHComparator = new RectHComparator();
75
77 final int initialWidth,
78 final int initialHeight) {
79 this.manager = manager;
80 levels = new LevelSet(initialWidth, initialHeight);
81 this.initialWidth = initialWidth;
82 this.initialHeight = initialHeight;
83 }
84
85 public Object getBackingStore() {
86 if (backingStore == null) {
87 backingStore = manager.allocateBackingStore(levels.w(), levels.h());
88 }
89
90 return backingStore;
91 }
92
93 /** Sets up a maximum width and height for the backing store. These
94 are optional and if not specified the backing store will grow as
95 necessary. Setting up a maximum width and height introduces the
96 possibility that additions will fail; these are handled with the
97 BackingStoreManager's allocationFailed notification. */
98 public void setMaxSize(final int maxWidth, final int maxHeight) {
99 this.maxWidth = maxWidth;
100 this.maxHeight = maxHeight;
101 }
102
103 /** Decides upon an (x, y) position for the given rectangle (leaving
104 its width and height unchanged) and places it on the backing
105 store. May provoke re-layout of other Rects already added. If
106 the BackingStoreManager does not support compaction, and {@link
107 BackingStoreManager#preExpand BackingStoreManager.preExpand}
108 does not clear enough space for the incoming rectangle, then
109 this method will throw a RuntimeException. */
110 public void add(final Rect rect) throws RuntimeException {
111 // Allocate backing store if we don't have any yet
112 if (backingStore == null)
113 backingStore = manager.allocateBackingStore(levels.w(), levels.h());
114
115 int attemptNumber = 0;
116 boolean tryAgain = false;
117
118 do {
119 // Try to allocate
120 if (levels.add(rect))
121 return;
122
123 if (manager.canCompact()) {
124 // Try to allocate with horizontal compaction
125 if (levels.compactAndAdd(rect, backingStore, manager))
126 return;
127 // Let the manager have a chance at potentially evicting some entries
128 tryAgain = manager.preExpand(rect, attemptNumber++);
129 } else {
130 tryAgain = manager.additionFailed(rect, attemptNumber++);
131 }
132 } while (tryAgain);
133
134 if (!manager.canCompact()) {
135 throw new RuntimeException("BackingStoreManager does not support compaction or expansion, and didn't clear space for new rectangle");
136 }
137
138 compactImpl(rect);
139
140 // Retry the addition of the incoming rectangle
141 add(rect);
142 // Done
143 }
144
145 /** Removes the given rectangle from this RectanglePacker. */
146 public void remove(final Rect rect) {
147 levels.remove(rect);
148 }
149
150 /** Visits all Rects contained in this RectanglePacker. */
151 public void visit(final RectVisitor visitor) {
152 levels.visit(visitor);
153 }
154
155 /** Returns the vertical fragmentation ratio of this
156 RectanglePacker. This is defined as the ratio of the sum of the
157 heights of all completely empty Levels divided by the overall
158 used height of the LevelSet. A high vertical fragmentation ratio
159 indicates that it may be profitable to perform a compaction. */
161 return levels.verticalFragmentationRatio();
162 }
163
164 /** Forces a compaction cycle, which typically results in allocating
165 a new backing store and copying all entries to it. */
166 public void compact() {
167 compactImpl(null);
168 }
169
170 // The "cause" rect may be null
171 private void compactImpl(final Rect cause) {
172 // Have to either expand, compact or both. Need to figure out what
173 // direction to go. Prefer to expand vertically. Expand
174 // horizontally only if rectangle being added is too wide. FIXME:
175 // may want to consider rebalancing the width and height to be
176 // more equal if it turns out we keep expanding in the vertical
177 // direction.
178 boolean done = false;
179 int newWidth = levels.w();
180 int newHeight = levels.h();
181 LevelSet nextLevelSet = null;
182 int attemptNumber = 0;
183 boolean needAdditionFailureNotification = false;
184
185 while (!done) {
186 if (cause != null) {
187 if (cause.w() > newWidth) {
188 newWidth = cause.w();
189 } else {
190 newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR));
191 }
192 }
193
194 // Clamp to maximum values
195 needAdditionFailureNotification = false;
196 if (maxWidth > 0 && newWidth > maxWidth) {
197 newWidth = maxWidth;
198 needAdditionFailureNotification = true;
199 }
200 if (maxHeight > 0 && newHeight > maxHeight) {
201 newHeight = maxHeight;
202 needAdditionFailureNotification = true;
203 }
204
205 nextLevelSet = new LevelSet(newWidth, newHeight);
206
207 // Make copies of all existing rectangles
208 final List<Rect> newRects = new ArrayList<Rect>();
209 for (final Iterator<Level> i1 = levels.iterator(); i1.hasNext(); ) {
210 final Level level = i1.next();
211 for (final Iterator<Rect> i2 = level.iterator(); i2.hasNext(); ) {
212 final Rect cur = i2.next();
213 final Rect newRect = new Rect(0, 0, cur.w(), cur.h(), null);
214 cur.setNextLocation(newRect);
215 // Hook up the reverse mapping too for easier replacement
216 newRect.setNextLocation(cur);
217 newRects.add(newRect);
218 }
219 }
220 // Sort them by decreasing height (note: this isn't really
221 // guaranteed to improve the chances of a successful layout)
222 Collections.sort(newRects, rectHComparator);
223 // Try putting all of these rectangles into the new level set
224 done = true;
225 for (final Iterator<Rect> iter = newRects.iterator(); iter.hasNext(); ) {
226 if (!nextLevelSet.add(iter.next())) {
227 done = false;
228 break;
229 }
230 }
231
232 if (done && cause != null) {
233 // Try to add the new rectangle as well
234 if (nextLevelSet.add(cause)) {
235 // We're OK
236 } else {
237 done = false;
238 }
239 }
240
241 // Don't send addition failure notifications if we're only doing
242 // a compaction
243 if (!done && needAdditionFailureNotification && cause != null) {
244 manager.additionFailed(cause, attemptNumber);
245 }
246 ++attemptNumber;
247 }
248
249 // See whether the implicit compaction that just occurred has
250 // yielded excess empty space.
251 if (nextLevelSet.getUsedHeight() > 0 &&
252 nextLevelSet.getUsedHeight() < nextLevelSet.h() * SHRINK_FACTOR) {
253 int shrunkHeight = Math.max(initialHeight,
254 (int) (nextLevelSet.getUsedHeight() * (1.0f + EXPANSION_FACTOR)));
255 if (maxHeight > 0 && shrunkHeight > maxHeight) {
256 shrunkHeight = maxHeight;
257 }
258 nextLevelSet.setHeight(shrunkHeight);
259 }
260
261 // If we temporarily added the new rectangle to the new LevelSet,
262 // take it out since we don't "really" add it here but in add(), above
263 if (cause != null) {
264 nextLevelSet.remove(cause);
265 }
266
267 // OK, now we have a new layout and a mapping from the old to the
268 // new locations of rectangles on the backing store. Allocate a
269 // new backing store, move the contents over and deallocate the
270 // old one.
271 final Object newBackingStore = manager.allocateBackingStore(nextLevelSet.w(),
272 nextLevelSet.h());
273 manager.beginMovement(backingStore, newBackingStore);
274 for (final Iterator<Level> i1 = levels.iterator(); i1.hasNext(); ) {
275 final Level level = i1.next();
276 for (final Iterator<Rect> i2 = level.iterator(); i2.hasNext(); ) {
277 final Rect cur = i2.next();
278 manager.move(backingStore, cur,
279 newBackingStore, cur.getNextLocation());
280 }
281 }
282 // Replace references to temporary rectangles with original ones
283 nextLevelSet.updateRectangleReferences();
284 manager.endMovement(backingStore, newBackingStore);
285 // Now delete the old backing store
286 manager.deleteBackingStore(backingStore);
287 // Update to new versions of backing store and LevelSet
288 backingStore = newBackingStore;
289 levels = nextLevelSet;
290 }
291
292 /** Clears all Rects contained in this RectanglePacker. */
293 public void clear() {
294 levels.clear();
295 }
296
297 /** Disposes the backing store allocated by the
298 BackingStoreManager. This RectanglePacker may no longer be used
299 after calling this method. */
300 public void dispose() {
301 if (backingStore != null)
302 manager.deleteBackingStore(backingStore);
303 backingStore = null;
304 levels = null;
305 }
306}
Manages a list of Levels; this is the core data structure contained within the RectanglePacker and en...
Definition: LevelSet.java:48
boolean add(final Rect rect)
Returns true if the given rectangle was successfully added to the LevelSet given its current dimensio...
Definition: LevelSet.java:69
void setHeight(final int height)
Sets the height of this LevelSet.
Definition: LevelSet.java:159
boolean remove(final Rect rect)
Removes the given Rect from this LevelSet.
Definition: LevelSet.java:105
void visit(final RectVisitor visitor)
Visits all Rects contained in this LevelSet.
Definition: LevelSet.java:190
float verticalFragmentationRatio()
Returns the vertical fragmentation ratio of this LevelSet.
Definition: LevelSet.java:171
void updateRectangleReferences()
Updates the references to the Rect objects in this LevelSet with the "next locations" of those Rects.
Definition: LevelSet.java:201
boolean compactAndAdd(final Rect rect, final Object backingStore, final BackingStoreManager manager)
Allocates the given Rectangle, performing compaction of a Level if necessary.
Definition: LevelSet.java:119
int getUsedHeight()
Gets the used height of the levels in this LevelSet.
Definition: LevelSet.java:153
void clear()
Clears out all Levels stored in this LevelSet.
Definition: LevelSet.java:209
Represents a rectangular region on the backing store.
Definition: Rect.java:58
Packs rectangles supplied by the user (typically representing image regions) into a larger backing st...
void clear()
Clears all Rects contained in this RectanglePacker.
void dispose()
Disposes the backing store allocated by the BackingStoreManager.
void compact()
Forces a compaction cycle, which typically results in allocating a new backing store and copying all ...
void add(final Rect rect)
Decides upon an (x, y) position for the given rectangle (leaving its width and height unchanged) and ...
void setMaxSize(final int maxWidth, final int maxHeight)
Sets up a maximum width and height for the backing store.
RectanglePacker(final BackingStoreManager manager, final int initialWidth, final int initialHeight)
float verticalFragmentationRatio()
Returns the vertical fragmentation ratio of this RectanglePacker.
void visit(final RectVisitor visitor)
Visits all Rects contained in this RectanglePacker.
This interface must be implemented by the end user and is called in response to events like addition ...
boolean additionFailed(Rect cause, int attemptNumber)
Notification that addition of the given Rect failed because a maximum size was set in the RectanglePa...
boolean preExpand(Rect cause, int attemptNumber)
Notification that expansion of the backing store is about to be done due to addition of the given rec...
void beginMovement(Object oldBackingStore, Object newBackingStore)
Notification that movement is starting.
void endMovement(Object oldBackingStore, Object newBackingStore)
Notification that movement is ending.
boolean canCompact()
Indication whether this BackingStoreManager supports compaction; in other words, the allocation of a ...
void move(Object oldBackingStore, Rect oldLocation, Object newBackingStore, Rect newLocation)
Tells the manager to move the contents of the given rect from the old location on the old backing sto...
Iteration construct without exposing the internals of the RectanglePacker and without implementing a ...