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