diff options
Diffstat (limited to 'src/classes/com/sun/opengl/impl')
7 files changed, 893 insertions, 0 deletions
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..ba4b0cf30 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java @@ -0,0 +1,64 @@ +/* + * 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 movement is starting + public void beginMovement(Object oldBackingStore, Object newBackingStore); + + // Can the backing stores be identical? I think so, in the case of + // compacting the existing backing store as opposed to 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..e7eab9ca7 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/packrect/Level.java @@ -0,0 +1,243 @@ +/* + * 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/*<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); + } + + if (freeList.isEmpty()) + freeList = null; + + 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(); + + // Now try to coalesce additional free space at the end of the + // free list + if (freeList != null) { + boolean found = true; + while (found) { + found = false; + for (Iterator iter = freeList.iterator(); iter.hasNext(); ) { + Rect cur = (Rect) iter.next(); + if (cur.maxX() + 1 == nextAddX) { + nextAddX -= cur.w(); + found = true; + freeList.remove(cur); + break; + } + } + } + if (freeList.isEmpty()) + freeList = null; + } + + return true; + } + + // Else, add the space consumed by this rectangle to the free list + if (freeList == null) { + freeList = new ArrayList/*<Rect>*/(); + } + freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null)); + return true; + } + + /** 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; + 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); + } + } +} 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..561a3fe14 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java @@ -0,0 +1,174 @@ +/* + * 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/*<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); + } + + 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(); + } + } +} 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). <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/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..453f5e1e2 --- /dev/null +++ b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java @@ -0,0 +1,188 @@ +/* + * 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; + + 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); + } + + public Object getBackingStore() { + if (backingStore == null) { + backingStore = manager.allocateBackingStore(levels.w(), levels.h()); + } + + return backingStore; + } + + /** 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()); + + // Try to allocate + if (levels.add(rect)) + return; + + // Try to allocate with compaction + if (levels.compactAndAdd(rect, backingStore, manager)) + return; + + // Have to expand. 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; + while (!done) { + if (rect.w() > newWidth) { + newWidth = rect.w(); + } else { + newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR)); + } + 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; + } + } + } + // 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; + // 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); + } + + /** Disposes the backing store allocated by the + BackingStoreManager. This RectanglePacker may no longer be used + after calling this method. */ + public void dispose() { + 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. <P> |