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