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

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