diff options
Diffstat (limited to 'src/jogl/classes/com/sun/opengl/util/packrect')
7 files changed, 1117 insertions, 0 deletions
diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/BackingStoreManager.java b/src/jogl/classes/com/sun/opengl/util/packrect/BackingStoreManager.java new file mode 100755 index 000000000..754ba2757 --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/BackingStoreManager.java @@ -0,0 +1,99 @@ +/* + * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - Redistribution of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistribution in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * Neither the name of Sun Microsystems, Inc. or the names of + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * This software is provided "AS IS," without a warranty of any kind. ALL + * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, + * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A + * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN + * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR + * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR + * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR + * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR + * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE + * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, + * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF + * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + * + * You acknowledge that this software is not designed or intended for use + * in the design, construction, operation or maintenance of any nuclear + * facility. + * + * Sun gratefully acknowledges that this software was originally authored + * and developed by Kenneth Bradley Russell and Christopher John Kline. + */ + +package com.sun.opengl.util.packrect; + +/** This interface must be implemented by the end user and is called + in response to events like addition of rectangles into the + RectanglePacker. It is used both when a full re-layout must be + done as well as when the data in the backing store must be copied + to a new one. */ + +public interface BackingStoreManager { + public Object allocateBackingStore(int w, int h); + public void deleteBackingStore(Object backingStore); + + /** Indication whether this BackingStoreManager supports compaction; + in other words, the allocation of a new backing store and + movement of the contents of the backing store from the old to + the new one. If it does not, then RectanglePacker.add() may + throw an exception if additionFailed() can not make enough room + available. If an implementation returns false, this also implies + that the backing store can not grow, so that preExpand() will + never be called. */ + public boolean canCompact(); + + /** Notification that expansion of the backing store is about to be + done due to addition of the given rectangle. Gives the manager a + chance to do some compaction and potentially remove old entries + from the backing store, if it acts like a least-recently-used + cache. This method receives as argument the number of attempts + so far to add the given rectangle. Manager should return true if + the RectanglePacker should retry the addition (which may result + in this method being called again, with an increased attempt + number) or false if the RectanglePacker should just expand the + backing store. The caller should not call RectanglePacker.add() + in its preExpand() method. */ + public boolean preExpand(Rect cause, int attemptNumber); + + /** Notification that addition of the given Rect failed because a + maximum size was set in the RectanglePacker and the backing + store could not be expanded, or because compaction (and, + therefore, implicitly expansion) was not supported. Should + return false if the manager can do nothing more to handle the + failed addition, which will cause a RuntimeException to be + thrown from the RectanglePacker. */ + public boolean additionFailed(Rect cause, int attemptNumber); + + /** Notification that movement is starting. */ + public void beginMovement(Object oldBackingStore, Object newBackingStore); + + /** Tells the manager to move the contents of the given rect from + the old location on the old backing store to the new location on + the new backing store. The backing stores can be identical in + the case of compacting the existing backing store instead of + reallocating it. */ + public void move(Object oldBackingStore, + Rect oldLocation, + Object newBackingStore, + Rect newLocation); + + /** Notification that movement is ending. */ + public void endMovement(Object oldBackingStore, Object newBackingStore); +} diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/Level.java b/src/jogl/classes/com/sun/opengl/util/packrect/Level.java new file mode 100755 index 000000000..3dae4301d --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/Level.java @@ -0,0 +1,275 @@ +/* + * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - Redistribution of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistribution in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * Neither the name of Sun Microsystems, Inc. or the names of + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * This software is provided "AS IS," without a warranty of any kind. ALL + * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, + * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A + * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN + * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR + * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR + * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR + * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR + * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE + * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, + * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF + * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + * + * You acknowledge that this software is not designed or intended for use + * in the design, construction, operation or maintenance of any nuclear + * facility. + * + * Sun gratefully acknowledges that this software was originally authored + * and developed by Kenneth Bradley Russell and Christopher John Kline. + */ + +package com.sun.opengl.util.packrect; + +import java.util.*; + +public class Level { + private int width; + private int height; + private int yPos; + private LevelSet holder; + + private List/*<Rect>*/ rects = new ArrayList/*<Rect>*/(); + private List/*<Rect>*/ freeList; + private int nextAddX; + + static class RectXComparator implements Comparator { + public int compare(Object o1, Object o2) { + Rect r1 = (Rect) o1; + Rect r2 = (Rect) o2; + return r1.x() - r2.x(); + } + + public boolean equals(Object obj) { + return this == obj; + } + } + private static final Comparator rectXComparator = new RectXComparator(); + + public Level(int width, int height, int yPos, LevelSet holder) { + this.width = width; + this.height = height; + this.yPos = yPos; + this.holder = holder; + } + + public int w() { return width; } + public int h() { return height; } + public int yPos() { return yPos; } + + /** Tries to add the given rectangle to this level only allowing + non-disruptive changes like trivial expansion of the last level + in the RectanglePacker and allocation from the free list. More + disruptive changes like compaction of the level must be + requested explicitly. */ + public boolean add(Rect rect) { + if (rect.h() > height) { + // See whether it's worth trying to expand vertically + if (nextAddX + rect.w() > width) { + return false; + } + + // See whether we're the last level and can expand + if (!holder.canExpand(this, rect.h())) { + return false; + } + + // Trivially expand and try the allocation + holder.expand(this, height, rect.h()); + height = rect.h(); + } + + // See whether we can add at the end + if (nextAddX + rect.w() <= width) { + rect.setPosition(nextAddX, yPos); + rects.add(rect); + nextAddX += rect.w(); + return true; + } + + // See whether we can add from the free list + if (freeList != null) { + Rect candidate = null; + for (Iterator iter = freeList.iterator(); iter.hasNext(); ) { + Rect cur = (Rect) iter.next(); + if (cur.canContain(rect)) { + candidate = cur; + break; + } + } + + if (candidate != null) { + // Remove the candidate from the free list + freeList.remove(candidate); + // Set up and add the real rect + rect.setPosition(candidate.x(), candidate.y()); + rects.add(rect); + // Re-add any remaining free space + if (candidate.w() > rect.w()) { + candidate.setPosition(candidate.x() + rect.w(), candidate.y()); + candidate.setSize(candidate.w() - rect.w(), height); + freeList.add(candidate); + } + + coalesceFreeList(); + + return true; + } + } + + return false; + } + + /** Removes the given Rect from this Level. */ + public boolean remove(Rect rect) { + if (!rects.remove(rect)) + return false; + + // If this is the rightmost rectangle, instead of adding its space + // to the free list, we can just decrease the nextAddX + if (rect.maxX() + 1 == nextAddX) { + nextAddX -= rect.w(); + } else { + if (freeList == null) { + freeList = new ArrayList/*<Rect>*/(); + } + freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null)); + coalesceFreeList(); + } + + return true; + } + + /** Indicates whether this Level contains no rectangles. */ + public boolean isEmpty() { + return rects.isEmpty(); + } + + /** Indicates whether this Level could satisfy an allocation request + if it were compacted. */ + public boolean couldAllocateIfCompacted(Rect rect) { + if (rect.h() > height) + return false; + if (freeList == null) + return false; + int freeListWidth = 0; + for (Iterator iter = freeList.iterator(); iter.hasNext(); ) { + Rect cur = (Rect) iter.next(); + freeListWidth += cur.w(); + } + // Add on the remaining space at the end + freeListWidth += (width - nextAddX); + return (freeListWidth >= rect.w()); + } + + public void compact(Object backingStore, BackingStoreManager manager) { + Collections.sort(rects, rectXComparator); + int nextCompactionDest = 0; + manager.beginMovement(backingStore, backingStore); + for (Iterator iter = rects.iterator(); iter.hasNext(); ) { + Rect cur = (Rect) iter.next(); + if (cur.x() != nextCompactionDest) { + manager.move(backingStore, cur, + backingStore, new Rect(nextCompactionDest, cur.y(), cur.w(), cur.h(), null)); + cur.setPosition(nextCompactionDest, cur.y()); + } + nextCompactionDest += cur.w(); + } + nextAddX = nextCompactionDest; + freeList.clear(); + manager.endMovement(backingStore, backingStore); + } + + public Iterator iterator() { + return rects.iterator(); + } + + /** Visits all Rects contained in this Level. */ + public void visit(RectVisitor visitor) { + for (Iterator iter = rects.iterator(); iter.hasNext(); ) { + Rect rect = (Rect) iter.next(); + visitor.visit(rect); + } + } + + /** Updates the references to the Rect objects in this Level with + the "next locations" of those Rects. This is actually used to + update the new Rects in a newly laid-out LevelSet with the + original Rects. */ + public void updateRectangleReferences() { + for (int i = 0; i < rects.size(); i++) { + Rect cur = (Rect) rects.get(i); + Rect next = cur.getNextLocation(); + next.setPosition(cur.x(), cur.y()); + if (cur.w() != next.w() || cur.h() != next.h()) + throw new RuntimeException("Unexpected disparity in rectangle sizes during updateRectangleReferences"); + rects.set(i, next); + } + } + + private void coalesceFreeList() { + if (freeList == null) + return; + if (freeList.isEmpty()) + return; + + // Try to coalesce adjacent free blocks in the free list + Collections.sort(freeList, rectXComparator); + int i = 0; + while (i < freeList.size() - 1) { + Rect r1 = (Rect) freeList.get(i); + Rect r2 = (Rect) freeList.get(i+1); + if (r1.maxX() + 1 == r2.x()) { + // Coalesce r1 and r2 into one block + freeList.remove(i+1); + r1.setSize(r1.w() + r2.w(), r1.h()); + } else { + ++i; + } + } + // See whether the last block bumps up against the addition point + Rect last = (Rect) freeList.get(freeList.size() - 1); + if (last.maxX() + 1 == nextAddX) { + nextAddX -= last.w(); + freeList.remove(freeList.size() - 1); + } + if (freeList.isEmpty()) { + freeList = null; + } + } + + //---------------------------------------------------------------------- + // Debugging functionality + // + + public void dumpFreeSpace() { + int freeListWidth = 0; + for (Iterator iter = freeList.iterator(); iter.hasNext(); ) { + Rect cur = (Rect) iter.next(); + System.err.println(" Free rectangle at " + cur); + freeListWidth += cur.w(); + } + // Add on the remaining space at the end + System.err.println(" Remaining free space " + (width - nextAddX)); + freeListWidth += (width - nextAddX); + System.err.println(" Total free space " + freeListWidth); + } +} diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/LevelSet.java b/src/jogl/classes/com/sun/opengl/util/packrect/LevelSet.java new file mode 100755 index 000000000..973980fdc --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/LevelSet.java @@ -0,0 +1,213 @@ +/* + * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - Redistribution of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistribution in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * Neither the name of Sun Microsystems, Inc. or the names of + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * This software is provided "AS IS," without a warranty of any kind. ALL + * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, + * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A + * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN + * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR + * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR + * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR + * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR + * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE + * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, + * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF + * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + * + * You acknowledge that this software is not designed or intended for use + * in the design, construction, operation or maintenance of any nuclear + * facility. + * + * Sun gratefully acknowledges that this software was originally authored + * and developed by Kenneth Bradley Russell and Christopher John Kline. + */ + +package com.sun.opengl.util.packrect; + +import java.util.*; + +/** Manages a list of Levels; this is the core data structure + contained within the RectanglePacker and encompasses the storage + algorithm for the contained Rects. */ + +public class LevelSet { + // Maintained in sorted order by increasing Y coordinate + private List/*<Level>*/ levels = new ArrayList/*<Level>*/(); + private int nextAddY; + private int w; + private int h; + + /** A LevelSet manages all of the backing store for a region of a + specified width and height. */ + public LevelSet(int w, int h) { + this.w = w; + this.h = h; + } + + public int w() { return w; } + public int h() { return h; } + + /** Returns true if the given rectangle was successfully added to + the LevelSet given its current dimensions, false if not. Caller + is responsible for performing compaction, expansion, etc. as a + consequence. */ + public boolean add(Rect rect) { + if (rect.w() > w) + return false; + + // Go in reverse order through the levels seeing whether we can + // trivially satisfy the allocation request + for (int i = levels.size() - 1; i >= 0; --i) { + Level level = (Level) levels.get(i); + if (level.add(rect)) + return true; + } + + // See whether compaction could satisfy this allocation. This + // increases the computational complexity of the addition process, + // but prevents us from expanding unnecessarily. + for (int i = levels.size() - 1; i >= 0; --i) { + Level level = (Level) levels.get(i); + if (level.couldAllocateIfCompacted(rect)) + return false; + } + + // OK, we need to either add a new Level or expand the backing + // store. Try to add a new Level. + if (nextAddY + rect.h() > h) + return false; + + Level newLevel = new Level(w, rect.h(), nextAddY, this); + levels.add(newLevel); + nextAddY += rect.h(); + boolean res = newLevel.add(rect); + if (!res) + throw new RuntimeException("Unexpected failure in addition to new Level"); + return true; + } + + /** Removes the given Rect from this LevelSet. */ + public boolean remove(Rect rect) { + for (int i = levels.size() - 1; i >= 0; --i) { + Level level = (Level) levels.get(i); + if (level.remove(rect)) + return true; + } + + return false; + } + + /** Allocates the given Rectangle, performing compaction of a Level + if necessary. This is the correct fallback path to {@link + #add(Rect)} above. Returns true if allocated successfully, false + otherwise (indicating the need to expand the backing store). */ + public boolean compactAndAdd(Rect rect, + Object backingStore, + BackingStoreManager manager) { + for (int i = levels.size() - 1; i >= 0; --i) { + Level level = (Level) levels.get(i); + if (level.couldAllocateIfCompacted(rect)) { + level.compact(backingStore, manager); + boolean res = level.add(rect); + if (!res) + throw new RuntimeException("Unexpected failure to add after compaction"); + return true; + } + } + + return false; + } + + /** Indicates whether it's legal to trivially increase the height of + the given Level. This is only possible if it's the last Level + added and there's enough room in the backing store. */ + public boolean canExpand(Level level, int height) { + if (levels.isEmpty()) + return false; // Should not happen + if (levels.get(levels.size() - 1) == level && + (h - nextAddY >= height - level.h())) + return true; + return false; + } + + public void expand(Level level, int oldHeight, int newHeight) { + nextAddY += (newHeight - oldHeight); + } + + /** Gets the used height of the levels in this LevelSet. */ + public int getUsedHeight() { + return nextAddY; + } + + /** Sets the height of this LevelSet. It is only legal to reduce the + height to greater than or equal to the currently used height. */ + public void setHeight(int height) throws IllegalArgumentException { + if (height < getUsedHeight()) { + throw new IllegalArgumentException("May not reduce height below currently used height"); + } + h = height; + } + + /** Returns the vertical fragmentation ratio of this LevelSet. This + is defined as the ratio of the sum of the heights of all + completely empty Levels divided by the overall used height of + the LevelSet. A high vertical fragmentation ratio indicates that + it may be profitable to perform a compaction. */ + public float verticalFragmentationRatio() { + int freeHeight = 0; + int usedHeight = getUsedHeight(); + if (usedHeight == 0) + return 0.0f; + for (Iterator iter = iterator(); iter.hasNext(); ) { + Level level = (Level) iter.next(); + if (level.isEmpty()) { + freeHeight += level.h(); + } + } + return (float) freeHeight / (float) usedHeight; + } + + public Iterator iterator() { + return levels.iterator(); + } + + /** Visits all Rects contained in this LevelSet. */ + public void visit(RectVisitor visitor) { + for (Iterator iter = levels.iterator(); iter.hasNext(); ) { + Level level = (Level) iter.next(); + level.visit(visitor); + } + } + + /** Updates the references to the Rect objects in this LevelSet with + the "next locations" of those Rects. This is actually used to + update the new Rects in a newly laid-out LevelSet with the + original Rects. */ + public void updateRectangleReferences() { + for (Iterator iter = levels.iterator(); iter.hasNext(); ) { + Level level = (Level) iter.next(); + level.updateRectangleReferences(); + } + } + + /** Clears out all Levels stored in this LevelSet. */ + public void clear() { + levels.clear(); + nextAddY = 0; + } +} diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/Rect.java b/src/jogl/classes/com/sun/opengl/util/packrect/Rect.java new file mode 100755 index 000000000..2f12981a6 --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/Rect.java @@ -0,0 +1,170 @@ +/* + * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - Redistribution of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistribution in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * Neither the name of Sun Microsystems, Inc. or the names of + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * This software is provided "AS IS," without a warranty of any kind. ALL + * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, + * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A + * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN + * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR + * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR + * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR + * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR + * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE + * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, + * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF + * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + * + * You acknowledge that this software is not designed or intended for use + * in the design, construction, operation or maintenance of any nuclear + * facility. + * + * Sun gratefully acknowledges that this software was originally authored + * and developed by Kenneth Bradley Russell and Christopher John Kline. + */ + +package com.sun.opengl.util.packrect; + +/** Represents a rectangular region on the backing store. The edges of + the rectangle are the infinitely thin region between adjacent + pixels on the screen. The origin of the rectangle is its + upper-left corner. It is inclusive of the pixels on the top and + left edges and exclusive of the pixels on the bottom and right + edges. For example, a rect at position (0, 0) and of size (1, 1) + would include only the pixel at (0, 0). <P> + + Negative coordinates and sizes are not supported, since they make + no sense in the context of the packer, which deals only with + positively sized regions. <P> + + This class contains a user data field for efficient hookup to + external data structures as well as enough other hooks to + efficiently plug into the rectangle packer. */ + +public class Rect { + private int x; + private int y; + private int w; + private int h; + + // The level we're currently installed in in the parent + // RectanglePacker, or null if not hooked in to the table yet + private Level level; + + // The user's object this rectangle represents. + private Object userData; + + // Used transiently during re-layout of the backing store (when + // there is no room left due either to fragmentation or just being + // out of space) + private Rect nextLocation; + + public Rect() { + this(null); + } + + public Rect(Object userData) { + this(0, 0, 0, 0, userData); + } + + public Rect(int x, int y, int w, int h, Object userData) { + setPosition(x, y); + setSize(w, h); + setUserData(userData); + } + + public int x() { return x; } + public int y() { return y; } + public int w() { return w; } + public int h() { return h; } + public Object getUserData() { return userData; } + public Rect getNextLocation() { return nextLocation; } + + public void setPosition(int x, int y) { + if (x < 0) + throw new IllegalArgumentException("Negative x"); + if (y < 0) + throw new IllegalArgumentException("Negative y"); + this.x = x; + this.y = y; + } + + public void setSize(int w, int h) throws IllegalArgumentException { + if (w < 0) + throw new IllegalArgumentException("Negative width"); + if (h < 0) + throw new IllegalArgumentException("Negative height"); + this.w = w; + this.h = h; + } + + public void setUserData(Object obj) { userData = obj; } + public void setNextLocation(Rect nextLocation) { this.nextLocation = nextLocation; } + + // Helpers for computations. + + /** Returns the maximum x-coordinate contained within this + rectangle. Note that this returns a different result than Java + 2D's rectangles; for a rectangle of position (0, 0) and size (1, + 1) this will return 0, not 1. Returns -1 if the width of this + rectangle is 0. */ + public int maxX() { + if (w() < 1) + return -1; + return x() + w() - 1; + } + + /** Returns the maximum y-coordinate contained within this + rectangle. Note that this returns a different result than Java + 2D's rectangles; for a rectangle of position (0, 0) and size (1, + 1) this will return 0, not 1. Returns -1 if the height of this + rectangle is 0. */ + public int maxY() { + if (h() < 1) + return -1; + return y() + h() - 1; + } + + public boolean canContain(Rect other) { + return (w() >= other.w() && + h() >= other.h()); + } + + public String toString() { + return "[Rect x: " + x() + " y: " + y() + " w: " + w() + " h: " + h() + "]"; + } + + // Unclear whether it's a good idea to override hashCode and equals + // for these objects + /* + public boolean equals(Object other) { + if (other == null || (!(other instanceof Rect))) { + return false; + } + + Rect r = (Rect) other; + return (this.x() == r.x() && + this.y() == r.y() && + this.w() == r.w() && + this.h() == r.h()); + } + + public int hashCode() { + return (x + y * 13 + w * 17 + h * 23); + } + */ +} diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/RectVisitor.java b/src/jogl/classes/com/sun/opengl/util/packrect/RectVisitor.java new file mode 100755 index 000000000..8f395ed99 --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/RectVisitor.java @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - Redistribution of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistribution in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * Neither the name of Sun Microsystems, Inc. or the names of + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * This software is provided "AS IS," without a warranty of any kind. ALL + * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, + * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A + * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN + * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR + * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR + * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR + * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR + * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE + * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, + * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF + * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + * + * You acknowledge that this software is not designed or intended for use + * in the design, construction, operation or maintenance of any nuclear + * facility. + * + * Sun gratefully acknowledges that this software was originally authored + * and developed by Kenneth Bradley Russell and Christopher John Kline. + */ + +package com.sun.opengl.util.packrect; + +/** Iteration construct without exposing the internals of the + RectanglePacker and without implementing a complex Iterator. */ + +public interface RectVisitor { + public void visit(Rect rect); +} diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/RectanglePacker.java b/src/jogl/classes/com/sun/opengl/util/packrect/RectanglePacker.java new file mode 100755 index 000000000..51e6842c0 --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/RectanglePacker.java @@ -0,0 +1,306 @@ +/* + * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - Redistribution of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistribution in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * Neither the name of Sun Microsystems, Inc. or the names of + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * This software is provided "AS IS," without a warranty of any kind. ALL + * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, + * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A + * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN + * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR + * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR + * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR + * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR + * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE + * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, + * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF + * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + * + * You acknowledge that this software is not designed or intended for use + * in the design, construction, operation or maintenance of any nuclear + * facility. + * + * Sun gratefully acknowledges that this software was originally authored + * and developed by Kenneth Bradley Russell and Christopher John Kline. + */ + +package com.sun.opengl.util.packrect; + +import java.util.*; + +/** Packs rectangles supplied by the user (typically representing + image regions) into a larger backing store rectangle (typically + representing a large texture). Supports automatic compaction of + the space on the backing store, and automatic expansion of the + backing store, when necessary. */ + +public class RectanglePacker { + private BackingStoreManager manager; + private Object backingStore; + private LevelSet levels; + private float EXPANSION_FACTOR = 0.5f; + private float SHRINK_FACTOR = 0.3f; + + private int initialWidth; + private int initialHeight; + + private int maxWidth = -1; + private int maxHeight = -1; + + static class RectHComparator implements Comparator { + public int compare(Object o1, Object o2) { + Rect r1 = (Rect) o1; + Rect r2 = (Rect) o2; + return r2.h() - r1.h(); + } + + public boolean equals(Object obj) { + return this == obj; + } + } + private static final Comparator rectHComparator = new RectHComparator(); + + public RectanglePacker(BackingStoreManager manager, + int initialWidth, + int initialHeight) { + this.manager = manager; + levels = new LevelSet(initialWidth, initialHeight); + this.initialWidth = initialWidth; + this.initialHeight = initialHeight; + } + + public Object getBackingStore() { + if (backingStore == null) { + backingStore = manager.allocateBackingStore(levels.w(), levels.h()); + } + + return backingStore; + } + + /** Sets up a maximum width and height for the backing store. These + are optional and if not specified the backing store will grow as + necessary. Setting up a maximum width and height introduces the + possibility that additions will fail; these are handled with the + BackingStoreManager's allocationFailed notification. */ + public void setMaxSize(int maxWidth, int maxHeight) { + this.maxWidth = maxWidth; + this.maxHeight = maxHeight; + } + + /** Decides upon an (x, y) position for the given rectangle (leaving + its width and height unchanged) and places it on the backing + store. May provoke re-layout of other Rects already added. If + the BackingStoreManager does not support compaction, and {@link + BackingStoreManager#preExpand BackingStoreManager.preExpand} + does not clear enough space for the incoming rectangle, then + this method will throw a RuntimeException. */ + public void add(Rect rect) throws RuntimeException { + // Allocate backing store if we don't have any yet + if (backingStore == null) + backingStore = manager.allocateBackingStore(levels.w(), levels.h()); + + int attemptNumber = 0; + boolean tryAgain = false; + + do { + // Try to allocate + if (levels.add(rect)) + return; + + if (manager.canCompact()) { + // Try to allocate with horizontal compaction + if (levels.compactAndAdd(rect, backingStore, manager)) + return; + // Let the manager have a chance at potentially evicting some entries + tryAgain = manager.preExpand(rect, attemptNumber++); + } else { + tryAgain = manager.additionFailed(rect, attemptNumber++); + } + } while (tryAgain); + + if (!manager.canCompact()) { + throw new RuntimeException("BackingStoreManager does not support compaction or expansion, and didn't clear space for new rectangle"); + } + + compactImpl(rect); + + // Retry the addition of the incoming rectangle + add(rect); + // Done + } + + /** Removes the given rectangle from this RectanglePacker. */ + public void remove(Rect rect) { + levels.remove(rect); + } + + /** Visits all Rects contained in this RectanglePacker. */ + public void visit(RectVisitor visitor) { + levels.visit(visitor); + } + + /** Returns the vertical fragmentation ratio of this + RectanglePacker. This is defined as the ratio of the sum of the + heights of all completely empty Levels divided by the overall + used height of the LevelSet. A high vertical fragmentation ratio + indicates that it may be profitable to perform a compaction. */ + public float verticalFragmentationRatio() { + return levels.verticalFragmentationRatio(); + } + + /** Forces a compaction cycle, which typically results in allocating + a new backing store and copying all entries to it. */ + public void compact() { + compactImpl(null); + } + + // The "cause" rect may be null + private void compactImpl(Rect cause) { + // Have to either expand, compact or both. Need to figure out what + // direction to go. Prefer to expand vertically. Expand + // horizontally only if rectangle being added is too wide. FIXME: + // may want to consider rebalancing the width and height to be + // more equal if it turns out we keep expanding in the vertical + // direction. + boolean done = false; + int newWidth = levels.w(); + int newHeight = levels.h(); + LevelSet nextLevelSet = null; + int attemptNumber = 0; + boolean needAdditionFailureNotification = false; + + while (!done) { + if (cause != null) { + if (cause.w() > newWidth) { + newWidth = cause.w(); + } else { + newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR)); + } + } + + // Clamp to maximum values + needAdditionFailureNotification = false; + if (maxWidth > 0 && newWidth > maxWidth) { + newWidth = maxWidth; + needAdditionFailureNotification = true; + } + if (maxHeight > 0 && newHeight > maxHeight) { + newHeight = maxHeight; + needAdditionFailureNotification = true; + } + + nextLevelSet = new LevelSet(newWidth, newHeight); + + // Make copies of all existing rectangles + List/*<Rect>*/ newRects = new ArrayList/*<Rect>*/(); + for (Iterator i1 = levels.iterator(); i1.hasNext(); ) { + Level level = (Level) i1.next(); + for (Iterator i2 = level.iterator(); i2.hasNext(); ) { + Rect cur = (Rect) i2.next(); + Rect newRect = new Rect(0, 0, cur.w(), cur.h(), null); + cur.setNextLocation(newRect); + // Hook up the reverse mapping too for easier replacement + newRect.setNextLocation(cur); + newRects.add(newRect); + } + } + // Sort them by decreasing height (note: this isn't really + // guaranteed to improve the chances of a successful layout) + Collections.sort(newRects, rectHComparator); + // Try putting all of these rectangles into the new level set + done = true; + for (Iterator iter = newRects.iterator(); iter.hasNext(); ) { + if (!nextLevelSet.add((Rect) iter.next())) { + done = false; + break; + } + } + + if (done && cause != null) { + // Try to add the new rectangle as well + if (nextLevelSet.add(cause)) { + // We're OK + } else { + done = false; + } + } + + // Don't send addition failure notifications if we're only doing + // a compaction + if (!done && needAdditionFailureNotification && cause != null) { + manager.additionFailed(cause, attemptNumber); + } + ++attemptNumber; + } + + // See whether the implicit compaction that just occurred has + // yielded excess empty space. + if (nextLevelSet.getUsedHeight() > 0 && + nextLevelSet.getUsedHeight() < nextLevelSet.h() * SHRINK_FACTOR) { + int shrunkHeight = Math.max(initialHeight, + (int) (nextLevelSet.getUsedHeight() * (1.0f + EXPANSION_FACTOR))); + if (maxHeight > 0 && shrunkHeight > maxHeight) { + shrunkHeight = maxHeight; + } + nextLevelSet.setHeight(shrunkHeight); + } + + // If we temporarily added the new rectangle to the new LevelSet, + // take it out since we don't "really" add it here but in add(), above + if (cause != null) { + nextLevelSet.remove(cause); + } + + // OK, now we have a new layout and a mapping from the old to the + // new locations of rectangles on the backing store. Allocate a + // new backing store, move the contents over and deallocate the + // old one. + Object newBackingStore = manager.allocateBackingStore(nextLevelSet.w(), + nextLevelSet.h()); + manager.beginMovement(backingStore, newBackingStore); + for (Iterator i1 = levels.iterator(); i1.hasNext(); ) { + Level level = (Level) i1.next(); + for (Iterator i2 = level.iterator(); i2.hasNext(); ) { + Rect cur = (Rect) i2.next(); + manager.move(backingStore, cur, + newBackingStore, cur.getNextLocation()); + } + } + // Replace references to temporary rectangles with original ones + nextLevelSet.updateRectangleReferences(); + manager.endMovement(backingStore, newBackingStore); + // Now delete the old backing store + manager.deleteBackingStore(backingStore); + // Update to new versions of backing store and LevelSet + backingStore = newBackingStore; + levels = nextLevelSet; + } + + /** Clears all Rects contained in this RectanglePacker. */ + public void clear() { + levels.clear(); + } + + /** Disposes the backing store allocated by the + BackingStoreManager. This RectanglePacker may no longer be used + after calling this method. */ + public void dispose() { + if (backingStore != null) + manager.deleteBackingStore(backingStore); + backingStore = null; + levels = null; + } +} diff --git a/src/jogl/classes/com/sun/opengl/util/packrect/package.html b/src/jogl/classes/com/sun/opengl/util/packrect/package.html new file mode 100755 index 000000000..7f2522244 --- /dev/null +++ b/src/jogl/classes/com/sun/opengl/util/packrect/package.html @@ -0,0 +1,7 @@ +This package implements a rectangle packing algorithm suitable for +tracking the placement of multiple rectangles inside a larger one. It +is useful for cases such as placing the contents of multiple windows +on a larger backing store texture for a compositing window manager; +placing multiple rasterized strings in a texture map for quick +rendering to the screen; and many other situations where it is useful +to carve up a larger texture into smaller pieces dynamically. <P> |