--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
+ * in Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.scenegraph.g2d.nodes.spatial;\r
+\r
+import gnu.trove.TIntObjectHashMap;\r
+import gnu.trove.TIntProcedure;\r
+\r
+import java.awt.Graphics2D;\r
+import java.awt.RenderingHints;\r
+import java.awt.Shape;\r
+import java.awt.geom.AffineTransform;\r
+import java.awt.geom.Rectangle2D;\r
+import java.util.ArrayList;\r
+import java.util.Collections;\r
+import java.util.HashSet;\r
+import java.util.Properties;\r
+import java.util.Set;\r
+\r
+import org.simantics.scenegraph.g2d.G2DParentNode;\r
+import org.simantics.scenegraph.g2d.IG2DNode;\r
+import org.simantics.scenegraph.g2d.events.Event;\r
+import org.simantics.scenegraph.g2d.events.EventTypes;\r
+import org.simantics.scenegraph.g2d.events.INodeEventHandlerProvider;\r
+import org.simantics.scenegraph.g2d.events.NodeEventHandler;\r
+import org.simantics.scenegraph.utils.GeometryUtils;\r
+import org.simantics.scenegraph.utils.NodeUtil;\r
+\r
+import com.infomatiq.jsi.Rectangle;\r
+import com.infomatiq.jsi.rtree.RTree;\r
+\r
+/**\r
+ * A G2D scene graph node that spatially decomposes all of its immediate child\r
+ * nodes into an R-Tree structure to optimize the painting of its direct child\r
+ * based on whether they are visible in the current clip-bounds or not.\r
+ * \r
+ * <p>\r
+ * The clipping boundary, i.e. the current viewport is retrieved from\r
+ * {@link Graphics2D#getClip()}. \r
+ * </p>\r
+ * \r
+ * <p>\r
+ * {@link #setDirty()} will mark the whole r-tree invalid meaning it will be\r
+ * reconstructed from scratch when it is needed again.\r
+ * </p>\r
+ * \r
+ * TODO:\r
+ * <ul>\r
+ * <li>Add interface for marking children added/removed/changed to optimize\r
+ * updates</li>\r
+ * <li>With incremental updating, make sure that the r-tree is rebuilt every\r
+ * once in a while. Updates will most likely cause r-tree performance to slowly\r
+ * deteriorate.</li>\r
+ * </ul>\r
+ * \r
+ * @author Tuukka Lehtonen\r
+ */\r
+public class RTreeNode extends G2DParentNode implements INodeEventHandlerProvider {\r
+\r
+ private static final boolean DISABLE_RTREE = false;\r
+\r
+ private static final boolean DEBUG_SHRINK_CLIP_RECT = false;\r
+\r
+ private static final long serialVersionUID = 8988645670981494042L;\r
+\r
+ /**\r
+ * A container for everything related to the R-tree based spatial\r
+ * decomposition.\r
+ */\r
+ private static class Tree {\r
+ public final RTree rtree;\r
+\r
+ /**\r
+ * Bounds of the whole R-tree.\r
+ */\r
+ public final Rectangle bounds;\r
+\r
+ /**\r
+ * May be null.\r
+ */\r
+ public final ArrayList<IG2DNode> boundlessNodes;\r
+\r
+ /**\r
+ * Map from R-tree rectangle ID's to scene graph nodes.\r
+ */\r
+ public final TIntObjectHashMap<IG2DNode> toNodes;\r
+\r
+ /**\r
+ * Map from R-tree rectangle ID's to current scene graph node bounds.\r
+ * This prevents the need to unnecessarily recalculate the node bounds\r
+ * in the node selection loop.\r
+ */\r
+ public final TIntObjectHashMap<Rectangle2D> toBounds;\r
+\r
+ public Tree(RTree rtree, ArrayList<IG2DNode> boundlessNodes, TIntObjectHashMap<IG2DNode> toNodes, TIntObjectHashMap<Rectangle2D> toBounds) {\r
+ this.rtree = rtree;\r
+ this.bounds = rtree.getBounds();\r
+ this.boundlessNodes = boundlessNodes;\r
+ this.toNodes = toNodes;\r
+ this.toBounds = toBounds;\r
+ }\r
+ }\r
+\r
+ private transient volatile Tree tree = null;\r
+ private transient ArrayList<IG2DNode> collected = new ArrayList<IG2DNode>();\r
+ private transient Set<IG2DNode> simplified = new HashSet<IG2DNode>();\r
+\r
+ @Override\r
+ public void render(Graphics2D g) {\r
+ if (DISABLE_RTREE) {\r
+ super.render(g);\r
+ return;\r
+ }\r
+\r
+ AffineTransform ot = null;\r
+ if (!transform.isIdentity()) {\r
+ ot = g.getTransform();\r
+ g.transform(transform);\r
+ }\r
+\r
+ try {\r
+ // Get transformed clip bounds\r
+ Shape clipShape = g.getClip();\r
+ Rectangle2D bounds = null;\r
+ if (clipShape instanceof Rectangle2D)\r
+ bounds = (Rectangle2D) clipShape;\r
+ else if (clipShape != null)\r
+ bounds = clipShape.getBounds2D();\r
+\r
+ // Calculate values to optimize rendering based on view scale\r
+ final double viewScale = GeometryUtils.getScale(g.getTransform());\r
+ if (Math.abs(viewScale) <= Double.MIN_VALUE)\r
+ return;\r
+ final double unitsPerPixel = 1.0 / viewScale;\r
+ //final double simplificationUnitsPerPixelLimit = 4*unitsPerPixel;\r
+ //System.out.println("view scale: " + viewScale + " - " + unitsPerPixel + " - " + simplificationUnitsPerPixelLimit);\r
+\r
+ // A bit of added margin for the clipping to\r
+ // prevent the system from clipping symbols too\r
+ // early in case they have out-of-bounds decorations.\r
+ if (bounds != null)\r
+ GeometryUtils.expandRectangle(bounds, 5);\r
+\r
+ // !DEBUG!\r
+ if (DEBUG_SHRINK_CLIP_RECT) {\r
+ GeometryUtils.expandRectangle(bounds, -100.0*unitsPerPixel);\r
+ g.draw(bounds);\r
+ }\r
+\r
+ // Make sure that a spatial decomposition exists.\r
+ final Tree tree = getSpatialDecomposition();\r
+\r
+ if (bounds == null || tree.bounds == null || containedBy(tree.bounds, bounds)) {\r
+ // Direct render if no pruning can be done.\r
+ for (IG2DNode node : getSortedNodes()) {\r
+ if (node.validate()) {\r
+ node.render(g);\r
+ }\r
+ }\r
+ } else {\r
+ final Object render = g.getRenderingHint(RenderingHints.KEY_RENDERING);\r
+\r
+ collected.clear();\r
+\r
+ if (tree.boundlessNodes != null) {\r
+ for (int i = 0, n = tree.boundlessNodes.size(); i < n; ++i)\r
+ collected.add(tree.boundlessNodes.get(i));\r
+ }\r
+\r
+ tree.rtree.intersects(toRectangle(bounds), new TIntProcedure() {\r
+\r
+ @Override\r
+ public boolean execute(int value) {\r
+ //System.out.println("exec: " + value);\r
+ IG2DNode node = tree.toNodes.get(value);\r
+ //System.out.println(" node: " + node);\r
+ if (node == null || !node.validate())\r
+ return true;\r
+\r
+ if (render != RenderingHints.VALUE_RENDER_QUALITY) {\r
+ Rectangle2D r = tree.toBounds.get(value);\r
+ if (r == null)\r
+ return true;\r
+\r
+ double w = r.getWidth();\r
+ double h = r.getHeight();\r
+\r
+ //System.out.println("size: " + w + " x " + h);\r
+ if (w < unitsPerPixel && h < unitsPerPixel) {\r
+ //System.out.println("Skipping node: " + node);\r
+ return true;\r
+ }\r
+\r
+// if (w < simplificationUnitsPerPixelLimit && h < simplificationUnitsPerPixelLimit) {\r
+// //System.out.println("simplifying node: " + node);\r
+// simplified.add(node);\r
+// }\r
+ }\r
+\r
+ collected.add(node);\r
+ return true;\r
+ }\r
+ });\r
+ Collections.sort(collected, G2DParentNode.G2DNODE_Z_COMPARATOR);\r
+ //System.out.println("rendering " + collected.size() + "/" + getNodeCount() + " children, " + simplified.size() + " as simplified");\r
+ if (simplified.isEmpty()) {\r
+ for (IG2DNode node : collected)\r
+ if (node.validate())\r
+ node.render(g);\r
+ } else {\r
+ for (IG2DNode node : collected) {\r
+ if (node.validate()) {\r
+ if (simplified.contains(node)) {\r
+ g.draw(node.getBoundsInLocal());\r
+ } else {\r
+ node.render(g);\r
+ }\r
+ }\r
+ }\r
+ simplified.clear();\r
+ }\r
+ }\r
+\r
+// // !DEBUG / PROFILING!\r
+// g.setStroke(new BasicStroke(0.25f));\r
+// drawTree(g, tree.rtree);\r
+\r
+ } finally {\r
+ if (ot != null)\r
+ g.setTransform(ot);\r
+ }\r
+ }\r
+\r
+// private void drawTree(final Graphics2D g, RTree rtree) {\r
+// final Rectangle2D r = new Rectangle2D.Double();\r
+// tree.rtree.traverse(new IRectangleTraverseProcedure() {\r
+// @Override\r
+// public void call(double x0, double y0, double x1, double y1, int level, Object value) {\r
+// r.setFrameFromDiagonal(x0, y0, x1, y1);\r
+// g.setColor(getLevelColor(level));\r
+// g.draw(r);\r
+// }\r
+//\r
+// private Color getLevelColor(int level) {\r
+// switch (level) {\r
+// case 0: return Color.DARK_GRAY;\r
+// case 1: return Color.RED;\r
+// case 2: return Color.PINK;\r
+// case 3: return Color.BLUE;\r
+// case 4: return Color.ORANGE;\r
+// default: return Color.BLACK;\r
+// }\r
+// }\r
+// });\r
+// }\r
+\r
+ @ClientSide\r
+ public void setDirty() {\r
+ tree = null;\r
+ }\r
+\r
+ private Tree getSpatialDecomposition() {\r
+ Tree t = tree;\r
+ if (t == null) {\r
+ t = decompose();\r
+ tree = t;\r
+ }\r
+ return t;\r
+ }\r
+\r
+ Properties props = new Properties();\r
+\r
+ private Tree decompose() {\r
+ RTree rtree = new RTree();\r
+ rtree.init(props);\r
+ IG2DNode[] nodes = getSortedNodes();\r
+ TIntObjectHashMap<IG2DNode> toNodes = new TIntObjectHashMap<IG2DNode>(nodes.length);\r
+ TIntObjectHashMap<Rectangle2D> toBounds = new TIntObjectHashMap<Rectangle2D>(nodes.length);\r
+ int rid = 0;\r
+ ArrayList<IG2DNode> boundlessNodes = null;\r
+ for (IG2DNode node : nodes) {\r
+ Rectangle2D bounds = node.getBounds();\r
+ if (bounds != null) {\r
+ Rectangle r = toRectangle(bounds);\r
+ int id = ++rid;\r
+ rtree.add(r, id);\r
+ toNodes.put(id, node);\r
+ toBounds.put(id, bounds);\r
+ } else {\r
+ if (boundlessNodes == null)\r
+ boundlessNodes = new ArrayList<IG2DNode>();\r
+ boundlessNodes.add(node);\r
+ }\r
+ }\r
+ return new Tree(rtree, boundlessNodes, toNodes, toBounds);\r
+ }\r
+\r
+ /**\r
+ * @param rect\r
+ * @return\r
+ */\r
+ public static Rectangle toRectangle(Rectangle2D rect) {\r
+ return new Rectangle((float) rect.getMinX(), (float) rect.getMinY(), (float) rect.getMaxX(), (float) rect.getMaxY());\r
+ }\r
+\r
+ /**\r
+ * Determine whether this rectangle is contained by the passed rectangle\r
+ * \r
+ * @param contained the rectangle tested to see if it contained by container\r
+ * @param container The rectangle that might contain this rectangle\r
+ * \r
+ * @return <code>true</code> if the container contains contained,\r
+ * <code>false</code> if it does not\r
+ */\r
+ public static boolean containedBy(Rectangle contained, Rectangle2D container) {\r
+ return container.getMaxX() >= contained.maxX && container.getMinX() <= contained.minX\r
+ && container.getMaxY() >= contained.maxY && container.getMinY() <= contained.minY;\r
+ }\r
+\r
+ @Override\r
+ public void init() {\r
+ super.init();\r
+ //addEventHandler(this);\r
+ }\r
+\r
+ @Override\r
+ public void cleanup() {\r
+ //removeEventHandler(this);\r
+ super.cleanup();\r
+ }\r
+\r
+ @Override\r
+ public int getEventMask() {\r
+ return EventTypes.MouseMask;\r
+ }\r
+\r
+ @Override\r
+ public boolean handleEvent(Event e) {\r
+ // Propagate mouse events to children based on bounds.\r
+ //System.out.println("R-TREE HANDLE EVENT: " + e);\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public NodeEventHandler getEventHandler() {\r
+ // TODO: add an event handler here and propagate mouse events spatially \r
+ return NodeUtil.getNodeEventHandler(this);\r
+ }\r
+\r
+}\r