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