With extensive help from Phil Race and Chris Campbell from the Java 2D

team, added a TextRenderer class which enables high-performance
rendering of bitmapped Java 2D fonts, with full Unicode support, into
arbitrary OpenGL drawables using a simple API. Builds on top of the
TextureRenderer class and its associated functionality; added
createAlphaOnlyRenderer() and other methods to enable the TextRenderer.
Caches rendering results on a string-by-string basis in an OpenGL
texture using a fully automatic least-recently-used algorithm for good
efficiency when rendering the same string or strings multiple times.
Uses a rectangle packing algorithm, currently housed in
com.sun.opengl.impl.packrect, for managing the positions of cached
strings on a larger OpenGL texture to avoid OpenGL pipeline state
changes. Added a TestTextRenderer demo which simply adds a moving text
string and frames-per-second counter to the Gears demo; more
sophisticated examples to come. (Some commented-out debugging code is
being temporarily left in the new demo, to be removed in the next
checkin, in order to have it in the version history.)


git-svn-id: file:///usr/local/projects/SUN/JOGL/git-svn/svn-server-sync/jogl/trunk@1067 232f8b59-042b-4e1e-8c03-345bb8c30851

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>