diff options
5 files changed, 450 insertions, 84 deletions
diff --git a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java index ba4b0cf30..0c4636063 100755 --- a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java +++ b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java @@ -49,16 +49,37 @@ public interface BackingStoreManager { public Object allocateBackingStore(int w, int h); public void deleteBackingStore(Object backingStore); - // Notification that movement is starting + /** 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); - // Can the backing stores be identical? I think so, in the case of - // compacting the existing backing store as opposed to reallocating it... + /** 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 + /** 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 index e7eab9ca7..12a09cd9a 100755 --- a/src/classes/com/sun/opengl/impl/packrect/Level.java +++ b/src/classes/com/sun/opengl/impl/packrect/Level.java @@ -129,8 +129,7 @@ public class Level { freeList.add(candidate); } - if (freeList.isEmpty()) - freeList = null; + coalesceFreeList(); return true; } @@ -148,38 +147,22 @@ public class Level { // 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; + } else { + if (freeList == null) { + freeList = new ArrayList/*<Rect>*/(); } - - return true; + freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null)); + coalesceFreeList(); } - // 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 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) { @@ -211,6 +194,7 @@ public class Level { nextCompactionDest += cur.w(); } nextAddX = nextCompactionDest; + freeList.clear(); manager.endMovement(backingStore, backingStore); } @@ -240,4 +224,52 @@ public class Level { 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 index 561a3fe14..97a1f2e74 100755 --- a/src/classes/com/sun/opengl/impl/packrect/LevelSet.java +++ b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java @@ -149,6 +149,39 @@ public class LevelSet { 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(); } @@ -171,4 +204,10 @@ public class LevelSet { 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/RectanglePacker.java b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java index 453f5e1e2..6057f7bb9 100755 --- a/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java +++ b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java @@ -52,6 +52,13 @@ public class RectanglePacker { 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) { @@ -71,6 +78,8 @@ public class RectanglePacker { int initialHeight) { this.manager = manager; levels = new LevelSet(initialWidth, initialHeight); + this.initialWidth = initialWidth; + this.initialHeight = initialHeight; } public Object getBackingStore() { @@ -81,6 +90,16 @@ public class RectanglePacker { 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. */ @@ -89,29 +108,89 @@ public class RectanglePacker { if (backingStore == null) backingStore = manager.allocateBackingStore(levels.w(), levels.h()); - // Try to allocate - if (levels.add(rect)) - return; + 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); + } - // Try to allocate with compaction - if (levels.compactAndAdd(rect, backingStore, manager)) - return; + /** 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(); + } - // 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. + /** 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 (rect.w() > newWidth) { - newWidth = rect.w(); - } else { - newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR)); + 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 @@ -138,7 +217,42 @@ public class RectanglePacker { 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 @@ -162,19 +276,11 @@ public class RectanglePacker { // 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); + /** Clears all Rects contained in this RectanglePacker. */ + public void clear() { + levels.clear(); } /** Disposes the backing store allocated by the diff --git a/src/classes/com/sun/opengl/util/j2d/TextRenderer.java b/src/classes/com/sun/opengl/util/j2d/TextRenderer.java index 027f857fe..7f47c011a 100755 --- a/src/classes/com/sun/opengl/util/j2d/TextRenderer.java +++ b/src/classes/com/sun/opengl/util/j2d/TextRenderer.java @@ -54,6 +54,13 @@ import javax.media.opengl.*; import javax.media.opengl.glu.*; import com.sun.opengl.impl.packrect.*; +// For debugging purposes +import java.awt.EventQueue; +import java.awt.Frame; +import java.awt.event.*; +import com.sun.opengl.impl.*; +import com.sun.opengl.util.*; + /** Renders bitmapped Java 2D text into an OpenGL window with high performance, full Unicode support, and a simple API. Performs appropriate caching of text rendering results in an OpenGL texture @@ -94,11 +101,14 @@ import com.sun.opengl.impl.packrect.*; */ public class TextRenderer { + private static final boolean DEBUG = Debug.debug("TextRenderer"); + private Font font; private boolean antialiased; private boolean useFractionalMetrics; private RectanglePacker packer; + private boolean haveMaxSize; private TextureRenderer cachedBackingStore; private Graphics2D cachedGraphics; private FontRenderContext cachedFontRenderContext; @@ -116,8 +126,11 @@ public class TextRenderer { // Every certain number of render cycles, flush the strings which // haven't been used recently - private static final int CYCLES_PER_FLUSH = 200; + private static final int CYCLES_PER_FLUSH = 100; private int numRenderCycles; + // The amount of vertical dead space on the backing store before we + // force a compaction + private static final float MAX_VERTICAL_FRAGMENTATION = 0.7f; // Current text color private float r = 1.0f; @@ -148,6 +161,9 @@ public class TextRenderer { void clearUsed() { used = false; } } + // Debugging purposes only + private boolean debugged; + /** Creates a new TextRenderer with the given font, using no antialiasing or fractional metrics. Equivalent to <code>TextRenderer(font, false, false)</code>. @@ -214,6 +230,23 @@ public class TextRenderer { return normalize(gv.getPixelBounds(frc, 0, 0)); } + /** Returns the Font this renderer is using. */ + public Font getFont() { + return font; + } + + /** Returns a FontRenderContext which can be used for external + text-related size computations. This object should be considered + transient and may become invalidated between {@link + #beginRendering beginRendering} / {@link #endRendering + endRendering} pairs. */ + public FontRenderContext getFontRenderContext() { + if (cachedFontRenderContext == null) { + cachedFontRenderContext = getGraphics2D().getFontRenderContext(); + } + return cachedFontRenderContext; + } + /** Begins rendering with this {@link TextRenderer TextRenderer} into the current OpenGL drawable, pushing the projection and modelview matrices and some state bits and setting up a @@ -229,8 +262,22 @@ public class TextRenderer { @throws GLException If an OpenGL context is not current when this method is called */ public void beginRendering(int width, int height) throws GLException { + if (DEBUG && !debugged) { + debug(); + } + getBackingStore().beginOrthoRendering(width, height); GL gl = GLU.getCurrentGL(); + + if (!haveMaxSize) { + // Query OpenGL for the maximum texture size and set it in the + // RectanglePacker to keep it from expanding too large + int[] sz = new int[1]; + gl.glGetIntegerv(GL.GL_MAX_TEXTURE_SIZE, sz, 0); + packer.setMaxSize(sz[0], sz[0]); + haveMaxSize = true; + } + // Change texture environment mode to MODULATE gl.glTexEnvi(GL.GL_TEXTURE_ENV, GL.GL_TEXTURE_ENV_MODE, GL.GL_MODULATE); // Change text color to last saved @@ -344,24 +391,10 @@ public class TextRenderer { getBackingStore().endOrthoRendering(); if (++numRenderCycles >= CYCLES_PER_FLUSH) { numRenderCycles = 0; - final List/*<Rect>*/ deadRects = new ArrayList/*<Rect>*/(); - // Iterate through the contents of the backing store, removing - // text strings that haven't been used recently - packer.visit(new RectVisitor() { - public void visit(Rect rect) { - TextData data = (TextData) rect.getUserData(); - if (data.used()) { - data.clearUsed(); - } else { - deadRects.add(rect); - } - } - }); - for (Iterator iter = deadRects.iterator(); iter.hasNext(); ) { - Rect r = (Rect) iter.next(); - packer.remove(r); - stringLocations.remove(((TextData) r.getUserData()).string()); + if (DEBUG) { + System.err.println("Clearing unused entries in endRendering()"); } + clearUnusedEntries(); } } @@ -421,13 +454,6 @@ public class TextRenderer { return cachedGraphics; } - private FontRenderContext getFontRenderContext() { - if (cachedFontRenderContext == null) { - cachedFontRenderContext = getGraphics2D().getFontRenderContext(); - } - return cachedFontRenderContext; - } - private int getSpaceWidth() { if (spaceWidth < 0) { Graphics2D g = getGraphics2D(); @@ -470,7 +496,48 @@ public class TextRenderer { } } - static class Manager implements BackingStoreManager { + private void clearUnusedEntries() { + final List/*<Rect>*/ deadRects = new ArrayList/*<Rect>*/(); + // Iterate through the contents of the backing store, removing + // text strings that haven't been used recently + packer.visit(new RectVisitor() { + public void visit(Rect rect) { + TextData data = (TextData) rect.getUserData(); + if (data.used()) { + data.clearUsed(); + } else { + deadRects.add(rect); + } + } + }); + for (Iterator iter = deadRects.iterator(); iter.hasNext(); ) { + Rect r = (Rect) iter.next(); + packer.remove(r); + stringLocations.remove(((TextData) r.getUserData()).string()); + + if (DEBUG) { + Graphics2D g = getGraphics2D(); + g.setColor(TRANSPARENT_BLACK); + g.fillRect(r.x(), r.y(), r.w(), r.h()); + g.setColor(Color.WHITE); + } + } + + // If we removed dead rectangles this cycle, try to do a compaction + float frag = packer.verticalFragmentationRatio(); + if (!deadRects.isEmpty() && frag > MAX_VERTICAL_FRAGMENTATION) { + if (DEBUG) { + System.err.println("Compacting TextRenderer backing store due to vertical fragmentation " + frag); + } + packer.compact(); + } + + if (DEBUG) { + getBackingStore().sync(0, 0, getBackingStore().getWidth(), getBackingStore().getHeight()); + } + } + + class Manager implements BackingStoreManager { private Graphics2D g; public Object allocateBackingStore(int w, int h) { @@ -479,6 +546,9 @@ public class TextRenderer { // store (i.e., non-default Paint, foreground color, etc.), but // for now, let's just be more efficient TextureRenderer renderer = TextureRenderer.createAlphaOnlyRenderer(w, h); + if (DEBUG) { + System.err.println(" TextRenderer allocating backing store " + w + " x " + h); + } return renderer; } @@ -486,6 +556,43 @@ public class TextRenderer { ((TextureRenderer) backingStore).dispose(); } + public boolean preExpand(Rect cause, int attemptNumber) { + // Only try this one time; clear out potentially obsolete entries + + // NOTE: this heuristic and the fact that it clears the used bit + // of all entries seems to cause cycling of entries in some + // situations, where the backing store becomes small compared to + // the amount of text on the screen (see the TextFlow demo) and + // the entries continually cycle in and out of the backing + // store, decreasing performance. If we added a little age + // information to the entries, and only cleared out entries + // above a certain age, this behavior would be eliminated. + // However, it seems the system usually stabilizes itself, so + // for now we'll just keep things simple. Note that if we don't + // clear the used bit here, the backing store tends to increase + // very quickly to its maximum size, at least with the TextFlow + // demo when the text is being continually re-laid out. + if (attemptNumber == 0) { + if (DEBUG) { + System.err.println("Clearing unused entries in preExpand(): attempt number " + attemptNumber); + } + clearUnusedEntries(); + return true; + } + + return false; + } + + public void additionFailed(Rect cause, int attemptNumber) { + // Heavy hammer -- might consider doing something different + packer.clear(); + stringLocations.clear(); + + if (DEBUG) { + System.err.println(" *** Cleared all text because addition failed ***"); + } + } + public void beginMovement(Object oldBackingStore, Object newBackingStore) { TextureRenderer newRenderer = (TextureRenderer) newBackingStore; g = newRenderer.createGraphics(); @@ -523,4 +630,65 @@ public class TextRenderer { newRenderer.sync(0, 0, newRenderer.getWidth(), newRenderer.getHeight()); } } + + //---------------------------------------------------------------------- + // Debugging functionality + // + + private void debug() { + Frame dbgFrame = new Frame("TextRenderer Debug Output"); + GLCanvas dbgCanvas = new GLCanvas(new GLCapabilities(), null, GLContext.getCurrent(), null); + dbgCanvas.addGLEventListener(new DebugListener(dbgFrame)); + dbgFrame.add(dbgCanvas); + final FPSAnimator anim = new FPSAnimator(dbgCanvas, 10); + dbgFrame.addWindowListener(new WindowAdapter() { + public void windowClosing(WindowEvent e) { + // Run this on another thread than the AWT event queue to + // make sure the call to Animator.stop() completes before + // exiting + new Thread(new Runnable() { + public void run() { + anim.stop(); + } + }).start(); + } + }); + dbgFrame.setSize(256, 256); + dbgFrame.setVisible(true); + anim.start(); + debugged = true; + } + + class DebugListener implements GLEventListener { + private GLU glu = new GLU(); + private Frame frame; + + DebugListener(Frame frame) { + this.frame = frame; + } + + public void display(GLAutoDrawable drawable) { + GL gl = drawable.getGL(); + gl.glClear(GL.GL_DEPTH_BUFFER_BIT | GL.GL_COLOR_BUFFER_BIT); + TextureRenderer rend = getBackingStore(); + final int w = rend.getWidth(); + final int h = rend.getHeight(); + rend.beginOrthoRendering(w, h); + rend.drawOrthoRect(0, 0); + rend.endOrthoRendering(); + if (frame.getWidth() != w || + frame.getHeight() != h) { + EventQueue.invokeLater(new Runnable() { + public void run() { + frame.setSize(w, h); + } + }); + } + } + + // Unused methods + public void init(GLAutoDrawable drawable) {} + public void reshape(GLAutoDrawable drawable, int x, int y, int width, int height) {} + public void displayChanged(GLAutoDrawable drawable, boolean modeChanged, boolean deviceChanged) {} + } } |