From 9fc74686947d23bdd715580ad2ad2d74de24c8a0 Mon Sep 17 00:00:00 2001 From: Kenneth Russel Date: Wed, 16 Jul 2008 06:22:49 +0000 Subject: Moved rectangle packer out of AWT-specific sub-package to make it more obvious that it can be reused on mobile devices git-svn-id: file:///usr/local/projects/SUN/JOGL/git-svn/svn-server-sync/jogl/branches/JOGL_2_SANDBOX@1722 232f8b59-042b-4e1e-8c03-345bb8c30851 --- .../impl/awt/packrect/BackingStoreManager.java | 85 ------ .../com/sun/opengl/impl/awt/packrect/Level.java | 275 ------------------- .../com/sun/opengl/impl/awt/packrect/LevelSet.java | 213 --------------- .../com/sun/opengl/impl/awt/packrect/Rect.java | 170 ------------ .../sun/opengl/impl/awt/packrect/RectVisitor.java | 47 ---- .../opengl/impl/awt/packrect/RectanglePacker.java | 295 --------------------- .../com/sun/opengl/impl/awt/packrect/package.html | 7 - .../opengl/impl/packrect/BackingStoreManager.java | 85 ++++++ .../com/sun/opengl/impl/packrect/Level.java | 275 +++++++++++++++++++ .../com/sun/opengl/impl/packrect/LevelSet.java | 213 +++++++++++++++ src/classes/com/sun/opengl/impl/packrect/Rect.java | 170 ++++++++++++ .../com/sun/opengl/impl/packrect/RectVisitor.java | 47 ++++ .../sun/opengl/impl/packrect/RectanglePacker.java | 295 +++++++++++++++++++++ .../com/sun/opengl/impl/packrect/package.html | 7 + .../sun/opengl/util/awt/gl2/GL2TextRenderer.java | 2 +- 15 files changed, 1093 insertions(+), 1093 deletions(-) delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/BackingStoreManager.java delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/Level.java delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/LevelSet.java delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/Rect.java delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/RectVisitor.java delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/RectanglePacker.java delete mode 100755 src/classes/com/sun/opengl/impl/awt/packrect/package.html create mode 100755 src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java create mode 100755 src/classes/com/sun/opengl/impl/packrect/Level.java create mode 100755 src/classes/com/sun/opengl/impl/packrect/LevelSet.java create mode 100755 src/classes/com/sun/opengl/impl/packrect/Rect.java create mode 100755 src/classes/com/sun/opengl/impl/packrect/RectVisitor.java create mode 100755 src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java create mode 100755 src/classes/com/sun/opengl/impl/packrect/package.html (limited to 'src') diff --git a/src/classes/com/sun/opengl/impl/awt/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/awt/packrect/BackingStoreManager.java deleted file mode 100755 index acff0aa79..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/BackingStoreManager.java +++ /dev/null @@ -1,85 +0,0 @@ -/* - * 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.impl.awt.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); - - /** 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. */ - public void 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/classes/com/sun/opengl/impl/awt/packrect/Level.java b/src/classes/com/sun/opengl/impl/awt/packrect/Level.java deleted file mode 100755 index 2ef6cb989..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/Level.java +++ /dev/null @@ -1,275 +0,0 @@ -/* - * 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.impl.awt.packrect; - -import java.util.*; - -public class Level { - private int width; - private int height; - private int yPos; - private LevelSet holder; - - private List/**/ rects = new ArrayList/**/(); - private List/**/ 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/**/(); - } - 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/classes/com/sun/opengl/impl/awt/packrect/LevelSet.java b/src/classes/com/sun/opengl/impl/awt/packrect/LevelSet.java deleted file mode 100755 index 724af27e0..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/LevelSet.java +++ /dev/null @@ -1,213 +0,0 @@ -/* - * 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.impl.awt.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/**/ levels = new ArrayList/**/(); - 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/classes/com/sun/opengl/impl/awt/packrect/Rect.java b/src/classes/com/sun/opengl/impl/awt/packrect/Rect.java deleted file mode 100755 index c3b6be6da..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/Rect.java +++ /dev/null @@ -1,170 +0,0 @@ -/* - * 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.impl.awt.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).

- - 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.

- - 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/classes/com/sun/opengl/impl/awt/packrect/RectVisitor.java b/src/classes/com/sun/opengl/impl/awt/packrect/RectVisitor.java deleted file mode 100755 index 9fd253d43..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/RectVisitor.java +++ /dev/null @@ -1,47 +0,0 @@ -/* - * 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.impl.awt.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/classes/com/sun/opengl/impl/awt/packrect/RectanglePacker.java b/src/classes/com/sun/opengl/impl/awt/packrect/RectanglePacker.java deleted file mode 100755 index f795fe00a..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/RectanglePacker.java +++ /dev/null @@ -1,295 +0,0 @@ -/* - * 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.impl.awt.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. */ - public void add(Rect rect) { - // 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; - - // 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++); - } while (tryAgain); - - 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/**/ newRects = new ArrayList/**/(); - 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/classes/com/sun/opengl/impl/awt/packrect/package.html b/src/classes/com/sun/opengl/impl/awt/packrect/package.html deleted file mode 100755 index 7f2522244..000000000 --- a/src/classes/com/sun/opengl/impl/awt/packrect/package.html +++ /dev/null @@ -1,7 +0,0 @@ -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.

diff --git a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java new file mode 100755 index 000000000..0c4636063 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java @@ -0,0 +1,85 @@ +/* + * 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.impl.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); + + /** 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. */ + public void 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/classes/com/sun/opengl/impl/packrect/Level.java b/src/classes/com/sun/opengl/impl/packrect/Level.java new file mode 100755 index 000000000..12a09cd9a --- /dev/null +++ b/src/classes/com/sun/opengl/impl/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.impl.packrect; + +import java.util.*; + +public class Level { + private int width; + private int height; + private int yPos; + private LevelSet holder; + + private List/**/ rects = new ArrayList/**/(); + private List/**/ 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/**/(); + } + 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/classes/com/sun/opengl/impl/packrect/LevelSet.java b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java new file mode 100755 index 000000000..97a1f2e74 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/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.impl.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/**/ levels = new ArrayList/**/(); + 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/classes/com/sun/opengl/impl/packrect/Rect.java b/src/classes/com/sun/opengl/impl/packrect/Rect.java new file mode 100755 index 000000000..f47660e94 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/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.impl.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).

+ + 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.

+ + 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/classes/com/sun/opengl/impl/packrect/RectVisitor.java b/src/classes/com/sun/opengl/impl/packrect/RectVisitor.java new file mode 100755 index 000000000..6474f204e --- /dev/null +++ b/src/classes/com/sun/opengl/impl/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.impl.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/classes/com/sun/opengl/impl/packrect/RectanglePacker.java b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java new file mode 100755 index 000000000..3a77b3bd1 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java @@ -0,0 +1,295 @@ +/* + * 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.impl.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. */ + public void add(Rect rect) { + // 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; + + // 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++); + } while (tryAgain); + + 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/**/ newRects = new ArrayList/**/(); + 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/classes/com/sun/opengl/impl/packrect/package.html b/src/classes/com/sun/opengl/impl/packrect/package.html new file mode 100755 index 000000000..7f2522244 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/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.

diff --git a/src/classes/com/sun/opengl/util/awt/gl2/GL2TextRenderer.java b/src/classes/com/sun/opengl/util/awt/gl2/GL2TextRenderer.java index 3527936b8..57cced512 100755 --- a/src/classes/com/sun/opengl/util/awt/gl2/GL2TextRenderer.java +++ b/src/classes/com/sun/opengl/util/awt/gl2/GL2TextRenderer.java @@ -39,7 +39,7 @@ package com.sun.opengl.util.awt.gl2; import com.sun.opengl.impl.*; -import com.sun.opengl.impl.awt.packrect.*; +import com.sun.opengl.impl.packrect.*; import com.sun.opengl.util.*; import com.sun.opengl.util.io.*; import com.sun.opengl.util.texture.*; -- cgit v1.2.3