bundles/org.simantics.scenegraph/src/org/simantics/scenegraph/g2d/nodes/spatial/RTreeNode.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.scenegraph.g2d.nodes.spatial;\r
  13 \r
  14 import gnu.trove.TIntObjectHashMap;\r
  15 import gnu.trove.TIntProcedure;\r
  16 \r
  17 import java.awt.Graphics2D;\r
  18 import java.awt.RenderingHints;\r
  19 import java.awt.Shape;\r
  20 import java.awt.geom.AffineTransform;\r
  21 import java.awt.geom.Rectangle2D;\r
  22 import java.util.ArrayList;\r
  23 import java.util.Collections;\r
  24 import java.util.HashSet;\r
  25 import java.util.Properties;\r
  26 import java.util.Set;\r
  27 \r
  28 import org.simantics.scenegraph.g2d.G2DParentNode;\r
  29 import org.simantics.scenegraph.g2d.IG2DNode;\r
  30 import org.simantics.scenegraph.g2d.events.Event;\r
  31 import org.simantics.scenegraph.g2d.events.EventTypes;\r
  32 import org.simantics.scenegraph.g2d.events.INodeEventHandlerProvider;\r
  33 import org.simantics.scenegraph.g2d.events.NodeEventHandler;\r
  34 import org.simantics.scenegraph.utils.GeometryUtils;\r
  35 import org.simantics.scenegraph.utils.NodeUtil;\r
  36 \r
  37 import com.infomatiq.jsi.Rectangle;\r
  38 import com.infomatiq.jsi.rtree.RTree;\r
  39 \r
  40 /**\r
  41  * A G2D scene graph node that spatially decomposes all of its immediate child\r
  42  * nodes into an R-Tree structure to optimize the painting of its direct child\r
  43  * based on whether they are visible in the current clip-bounds or not.\r
  44  * \r
  45  * <p>\r
  46  * The clipping boundary, i.e. the current viewport is retrieved from\r
  47  * {@link Graphics2D#getClip()}. \r
  48  * </p>\r
  49  * \r
  50  * <p>\r
  51  * {@link #setDirty()} will mark the whole r-tree invalid meaning it will be\r
  52  * reconstructed from scratch when it is needed again.\r
  53  * </p>\r
  54  * \r
  55  * TODO:\r
  56  * <ul>\r
  57  * <li>Add interface for marking children added/removed/changed to optimize\r
  58  * updates</li>\r
  59  * <li>With incremental updating, make sure that the r-tree is rebuilt every\r
  60  * once in a while. Updates will most likely cause r-tree performance to slowly\r
  61  * deteriorate.</li>\r
  62  * </ul>\r
  63  * \r
  64  * @author Tuukka Lehtonen\r
  65  */\r
  66 public class RTreeNode extends G2DParentNode implements INodeEventHandlerProvider {\r
  67 \r
  68     private static final boolean DISABLE_RTREE = false;\r
  69 \r
  70     private static final boolean DEBUG_SHRINK_CLIP_RECT = false;\r
  71 \r
  72     private static final long serialVersionUID = 8988645670981494042L;\r
  73 \r
  74     /**\r
  75      * A container for everything related to the R-tree based spatial\r
  76      * decomposition.\r
  77      */\r
  78     private static class Tree {\r
  79         public final RTree                          rtree;\r
  80 \r
  81         /**\r
  82          * Bounds of the whole R-tree.\r
  83          */\r
  84         public final Rectangle                      bounds;\r
  85 \r
  86         /**\r
  87          * May be null.\r
  88          */\r
  89         public final ArrayList<IG2DNode>            boundlessNodes;\r
  90 \r
  91         /**\r
  92          * Map from R-tree rectangle ID's to scene graph nodes.\r
  93          */\r
  94         public final TIntObjectHashMap<IG2DNode>    toNodes;\r
  95 \r
  96         /**\r
  97          * Map from R-tree rectangle ID's to current scene graph node bounds.\r
  98          * This prevents the need to unnecessarily recalculate the node bounds\r
  99          * in the node selection loop.\r
 100          */\r
 101         public final TIntObjectHashMap<Rectangle2D> toBounds;\r
 102 \r
 103         public Tree(RTree rtree, ArrayList<IG2DNode> boundlessNodes, TIntObjectHashMap<IG2DNode> toNodes, TIntObjectHashMap<Rectangle2D> toBounds) {\r
 104             this.rtree = rtree;\r
 105             this.bounds = rtree.getBounds();\r
 106             this.boundlessNodes = boundlessNodes;\r
 107             this.toNodes = toNodes;\r
 108             this.toBounds = toBounds;\r
 109         }\r
 110     }\r
 111 \r
 112     private transient volatile Tree       tree       = null;\r
 113     private transient ArrayList<IG2DNode> collected  = new ArrayList<IG2DNode>();\r
 114     private transient Set<IG2DNode>       simplified = new HashSet<IG2DNode>();\r
 115 \r
 116     @Override\r
 117     public void render(Graphics2D g) {\r
 118         if (DISABLE_RTREE) {\r
 119             super.render(g);\r
 120             return;\r
 121         }\r
 122 \r
 123         AffineTransform ot = null;\r
 124         if (!transform.isIdentity()) {\r
 125             ot = g.getTransform();\r
 126             g.transform(transform);\r
 127         }\r
 128 \r
 129         try {\r
 130             // Get transformed clip bounds\r
 131             Shape clipShape = g.getClip();\r
 132             Rectangle2D bounds = null;\r
 133             if (clipShape instanceof Rectangle2D)\r
 134                 bounds = (Rectangle2D) clipShape;\r
 135             else if (clipShape != null)\r
 136                 bounds = clipShape.getBounds2D();\r
 137 \r
 138             // Calculate values to optimize rendering based on view scale\r
 139             final double viewScale = GeometryUtils.getScale(g.getTransform());\r
 140             if (Math.abs(viewScale) <= Double.MIN_VALUE)\r
 141                 return;\r
 142             final double unitsPerPixel = 1.0 / viewScale;\r
 143             //final double simplificationUnitsPerPixelLimit = 4*unitsPerPixel;\r
 144             //System.out.println("view scale: " + viewScale + " - " + unitsPerPixel + " - " + simplificationUnitsPerPixelLimit);\r
 145 \r
 146             // A bit of added margin for the clipping to\r
 147             // prevent the system from clipping symbols too\r
 148             // early in case they have out-of-bounds decorations.\r
 149             if (bounds != null)\r
 150                 GeometryUtils.expandRectangle(bounds, 5);\r
 151 \r
 152             // !DEBUG!\r
 153             if (DEBUG_SHRINK_CLIP_RECT) {\r
 154                 GeometryUtils.expandRectangle(bounds, -100.0*unitsPerPixel);\r
 155                 g.draw(bounds);\r
 156             }\r
 157 \r
 158             // Make sure that a spatial decomposition exists.\r
 159             final Tree tree = getSpatialDecomposition();\r
 160 \r
 161             if (bounds == null || tree.bounds == null || containedBy(tree.bounds, bounds)) {\r
 162                 // Direct render if no pruning can be done.\r
 163                 for (IG2DNode node : getSortedNodes()) {\r
 164                     if (node.validate()) {\r
 165                         node.render(g);\r
 166                     }\r
 167                 }\r
 168             } else {\r
 169                 final Object render = g.getRenderingHint(RenderingHints.KEY_RENDERING);\r
 170 \r
 171                 collected.clear();\r
 172 \r
 173                 if (tree.boundlessNodes != null) {\r
 174                     for (int i = 0, n = tree.boundlessNodes.size(); i < n; ++i)\r
 175                         collected.add(tree.boundlessNodes.get(i));\r
 176                 }\r
 177 \r
 178                 tree.rtree.intersects(toRectangle(bounds), new TIntProcedure() {\r
 179 \r
 180                     @Override\r
 181                     public boolean execute(int value) {\r
 182                         //System.out.println("exec: " + value);\r
 183                         IG2DNode node = tree.toNodes.get(value);\r
 184                         //System.out.println("  node: " + node);\r
 185                         if (node == null || !node.validate())\r
 186                             return true;\r
 187 \r
 188                         if (render != RenderingHints.VALUE_RENDER_QUALITY) {\r
 189                             Rectangle2D r = tree.toBounds.get(value);\r
 190                             if (r == null)\r
 191                                 return true;\r
 192 \r
 193                             double w = r.getWidth();\r
 194                             double h = r.getHeight();\r
 195 \r
 196                             //System.out.println("size: " + w + " x " + h);\r
 197                             if (w < unitsPerPixel && h < unitsPerPixel) {\r
 198                                 //System.out.println("Skipping node: " + node);\r
 199                                 return true;\r
 200                             }\r
 201 \r
 202 //                        if (w < simplificationUnitsPerPixelLimit && h < simplificationUnitsPerPixelLimit) {\r
 203 //                            //System.out.println("simplifying node: " + node);\r
 204 //                            simplified.add(node);\r
 205 //                        }\r
 206                         }\r
 207 \r
 208                         collected.add(node);\r
 209                         return true;\r
 210                     }\r
 211                 });\r
 212                 Collections.sort(collected, G2DParentNode.G2DNODE_Z_COMPARATOR);\r
 213                 //System.out.println("rendering " + collected.size() + "/" + getNodeCount() + " children, " + simplified.size() + " as simplified");\r
 214                 if (simplified.isEmpty()) {\r
 215                     for (IG2DNode node : collected)\r
 216                         if (node.validate())\r
 217                             node.render(g);\r
 218                 } else {\r
 219                     for (IG2DNode node : collected) {\r
 220                         if (node.validate()) {\r
 221                             if (simplified.contains(node)) {\r
 222                                 g.draw(node.getBoundsInLocal());\r
 223                             } else {\r
 224                                 node.render(g);\r
 225                             }\r
 226                         }\r
 227                     }\r
 228                     simplified.clear();\r
 229                 }\r
 230             }\r
 231 \r
 232 //        // !DEBUG / PROFILING!\r
 233 //        g.setStroke(new BasicStroke(0.25f));\r
 234 //        drawTree(g, tree.rtree);\r
 235 \r
 236         } finally {\r
 237             if (ot != null)\r
 238                 g.setTransform(ot);\r
 239         }\r
 240     }\r
 241 \r
 242 //    private void drawTree(final Graphics2D g, RTree rtree) {\r
 243 //        final Rectangle2D r = new Rectangle2D.Double();\r
 244 //        tree.rtree.traverse(new IRectangleTraverseProcedure() {\r
 245 //            @Override\r
 246 //            public void call(double x0, double y0, double x1, double y1, int level, Object value) {\r
 247 //                r.setFrameFromDiagonal(x0, y0, x1, y1);\r
 248 //                g.setColor(getLevelColor(level));\r
 249 //                g.draw(r);\r
 250 //            }\r
 251 //\r
 252 //            private Color getLevelColor(int level) {\r
 253 //                switch (level) {\r
 254 //                    case 0: return Color.DARK_GRAY;\r
 255 //                    case 1: return Color.RED;\r
 256 //                    case 2: return Color.PINK;\r
 257 //                    case 3: return Color.BLUE;\r
 258 //                    case 4: return Color.ORANGE;\r
 259 //                    default: return Color.BLACK;\r
 260 //                }\r
 261 //            }\r
 262 //        });\r
 263 //    }\r
 264 \r
 265     @ClientSide\r
 266     public void setDirty() {\r
 267         tree = null;\r
 268     }\r
 269 \r
 270     private Tree getSpatialDecomposition() {\r
 271         Tree t = tree;\r
 272         if (t == null) {\r
 273             t = decompose();\r
 274             tree = t;\r
 275         }\r
 276         return t;\r
 277     }\r
 278 \r
 279     Properties props = new Properties();\r
 280 \r
 281     private Tree decompose() {\r
 282         RTree rtree = new RTree();\r
 283         rtree.init(props);\r
 284         IG2DNode[] nodes = getSortedNodes();\r
 285         TIntObjectHashMap<IG2DNode> toNodes = new TIntObjectHashMap<IG2DNode>(nodes.length);\r
 286         TIntObjectHashMap<Rectangle2D> toBounds = new TIntObjectHashMap<Rectangle2D>(nodes.length);\r
 287         int rid = 0;\r
 288         ArrayList<IG2DNode> boundlessNodes = null;\r
 289         for (IG2DNode node : nodes) {\r
 290             Rectangle2D bounds = node.getBounds();\r
 291             if (bounds != null) {\r
 292                 Rectangle r = toRectangle(bounds);\r
 293                 int id = ++rid;\r
 294                 rtree.add(r, id);\r
 295                 toNodes.put(id, node);\r
 296                 toBounds.put(id, bounds);\r
 297             } else {\r
 298                 if (boundlessNodes == null)\r
 299                     boundlessNodes = new ArrayList<IG2DNode>();\r
 300                 boundlessNodes.add(node);\r
 301             }\r
 302         }\r
 303         return new Tree(rtree, boundlessNodes, toNodes, toBounds);\r
 304     }\r
 305 \r
 306     /**\r
 307      * @param rect\r
 308      * @return\r
 309      */\r
 310     public static Rectangle toRectangle(Rectangle2D rect) {\r
 311         return new Rectangle((float) rect.getMinX(), (float) rect.getMinY(), (float) rect.getMaxX(), (float) rect.getMaxY());\r
 312     }\r
 313 \r
 314     /**\r
 315      * Determine whether this rectangle is contained by the passed rectangle\r
 316      * \r
 317      * @param contained the rectangle tested to see if it contained by container\r
 318      * @param container The rectangle that might contain this rectangle\r
 319      * \r
 320      * @return <code>true</code> if the container contains contained,\r
 321      *         <code>false</code> if it does not\r
 322      */\r
 323     public static boolean containedBy(Rectangle contained, Rectangle2D container) {\r
 324         return container.getMaxX() >= contained.maxX && container.getMinX() <= contained.minX\r
 325         && container.getMaxY() >= contained.maxY && container.getMinY() <= contained.minY;\r
 326     }\r
 327 \r
 328     @Override\r
 329     public void init() {\r
 330         super.init();\r
 331         //addEventHandler(this);\r
 332     }\r
 333 \r
 334     @Override\r
 335     public void cleanup() {\r
 336         //removeEventHandler(this);\r
 337         super.cleanup();\r
 338     }\r
 339 \r
 340     @Override\r
 341     public int getEventMask() {\r
 342         return EventTypes.MouseMask;\r
 343     }\r
 344 \r
 345     @Override\r
 346     public boolean handleEvent(Event e) {\r
 347         // Propagate mouse events to children based on bounds.\r
 348         //System.out.println("R-TREE HANDLE EVENT: " + e);\r
 349         return false;\r
 350     }\r
 351 \r
 352     @Override\r
 353     public NodeEventHandler getEventHandler() {\r
 354         // TODO: add an event handler here and propagate mouse events spatially \r
 355         return NodeUtil.getNodeEventHandler(this);\r
 356     }\r
 357 \r
 358 }\r