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