X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scenegraph%2Fsrc%2Forg%2Fsimantics%2Fscenegraph%2Fg2d%2Fnodes%2Fspatial%2FRTreeNode.java;fp=bundles%2Forg.simantics.scenegraph%2Fsrc%2Forg%2Fsimantics%2Fscenegraph%2Fg2d%2Fnodes%2Fspatial%2FRTreeNode.java;h=1429bbbe6f692e2ff4bfe68e7e52eea2bf55244f;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.scenegraph/src/org/simantics/scenegraph/g2d/nodes/spatial/RTreeNode.java b/bundles/org.simantics.scenegraph/src/org/simantics/scenegraph/g2d/nodes/spatial/RTreeNode.java new file mode 100644 index 000000000..1429bbbe6 --- /dev/null +++ b/bundles/org.simantics.scenegraph/src/org/simantics/scenegraph/g2d/nodes/spatial/RTreeNode.java @@ -0,0 +1,358 @@ +/******************************************************************************* + * Copyright (c) 2007, 2010 Association for Decentralized Information Management + * in Industry THTH ry. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * VTT Technical Research Centre of Finland - initial API and implementation + *******************************************************************************/ +package org.simantics.scenegraph.g2d.nodes.spatial; + +import gnu.trove.TIntObjectHashMap; +import gnu.trove.TIntProcedure; + +import java.awt.Graphics2D; +import java.awt.RenderingHints; +import java.awt.Shape; +import java.awt.geom.AffineTransform; +import java.awt.geom.Rectangle2D; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashSet; +import java.util.Properties; +import java.util.Set; + +import org.simantics.scenegraph.g2d.G2DParentNode; +import org.simantics.scenegraph.g2d.IG2DNode; +import org.simantics.scenegraph.g2d.events.Event; +import org.simantics.scenegraph.g2d.events.EventTypes; +import org.simantics.scenegraph.g2d.events.INodeEventHandlerProvider; +import org.simantics.scenegraph.g2d.events.NodeEventHandler; +import org.simantics.scenegraph.utils.GeometryUtils; +import org.simantics.scenegraph.utils.NodeUtil; + +import com.infomatiq.jsi.Rectangle; +import com.infomatiq.jsi.rtree.RTree; + +/** + * A G2D scene graph node that spatially decomposes all of its immediate child + * nodes into an R-Tree structure to optimize the painting of its direct child + * based on whether they are visible in the current clip-bounds or not. + * + *

+ * The clipping boundary, i.e. the current viewport is retrieved from + * {@link Graphics2D#getClip()}. + *

+ * + *

+ * {@link #setDirty()} will mark the whole r-tree invalid meaning it will be + * reconstructed from scratch when it is needed again. + *

+ * + * TODO: + * + * + * @author Tuukka Lehtonen + */ +public class RTreeNode extends G2DParentNode implements INodeEventHandlerProvider { + + private static final boolean DISABLE_RTREE = false; + + private static final boolean DEBUG_SHRINK_CLIP_RECT = false; + + private static final long serialVersionUID = 8988645670981494042L; + + /** + * A container for everything related to the R-tree based spatial + * decomposition. + */ + private static class Tree { + public final RTree rtree; + + /** + * Bounds of the whole R-tree. + */ + public final Rectangle bounds; + + /** + * May be null. + */ + public final ArrayList boundlessNodes; + + /** + * Map from R-tree rectangle ID's to scene graph nodes. + */ + public final TIntObjectHashMap toNodes; + + /** + * Map from R-tree rectangle ID's to current scene graph node bounds. + * This prevents the need to unnecessarily recalculate the node bounds + * in the node selection loop. + */ + public final TIntObjectHashMap toBounds; + + public Tree(RTree rtree, ArrayList boundlessNodes, TIntObjectHashMap toNodes, TIntObjectHashMap toBounds) { + this.rtree = rtree; + this.bounds = rtree.getBounds(); + this.boundlessNodes = boundlessNodes; + this.toNodes = toNodes; + this.toBounds = toBounds; + } + } + + private transient volatile Tree tree = null; + private transient ArrayList collected = new ArrayList(); + private transient Set simplified = new HashSet(); + + @Override + public void render(Graphics2D g) { + if (DISABLE_RTREE) { + super.render(g); + return; + } + + AffineTransform ot = null; + if (!transform.isIdentity()) { + ot = g.getTransform(); + g.transform(transform); + } + + try { + // Get transformed clip bounds + Shape clipShape = g.getClip(); + Rectangle2D bounds = null; + if (clipShape instanceof Rectangle2D) + bounds = (Rectangle2D) clipShape; + else if (clipShape != null) + bounds = clipShape.getBounds2D(); + + // Calculate values to optimize rendering based on view scale + final double viewScale = GeometryUtils.getScale(g.getTransform()); + if (Math.abs(viewScale) <= Double.MIN_VALUE) + return; + final double unitsPerPixel = 1.0 / viewScale; + //final double simplificationUnitsPerPixelLimit = 4*unitsPerPixel; + //System.out.println("view scale: " + viewScale + " - " + unitsPerPixel + " - " + simplificationUnitsPerPixelLimit); + + // A bit of added margin for the clipping to + // prevent the system from clipping symbols too + // early in case they have out-of-bounds decorations. + if (bounds != null) + GeometryUtils.expandRectangle(bounds, 5); + + // !DEBUG! + if (DEBUG_SHRINK_CLIP_RECT) { + GeometryUtils.expandRectangle(bounds, -100.0*unitsPerPixel); + g.draw(bounds); + } + + // Make sure that a spatial decomposition exists. + final Tree tree = getSpatialDecomposition(); + + if (bounds == null || tree.bounds == null || containedBy(tree.bounds, bounds)) { + // Direct render if no pruning can be done. + for (IG2DNode node : getSortedNodes()) { + if (node.validate()) { + node.render(g); + } + } + } else { + final Object render = g.getRenderingHint(RenderingHints.KEY_RENDERING); + + collected.clear(); + + if (tree.boundlessNodes != null) { + for (int i = 0, n = tree.boundlessNodes.size(); i < n; ++i) + collected.add(tree.boundlessNodes.get(i)); + } + + tree.rtree.intersects(toRectangle(bounds), new TIntProcedure() { + + @Override + public boolean execute(int value) { + //System.out.println("exec: " + value); + IG2DNode node = tree.toNodes.get(value); + //System.out.println(" node: " + node); + if (node == null || !node.validate()) + return true; + + if (render != RenderingHints.VALUE_RENDER_QUALITY) { + Rectangle2D r = tree.toBounds.get(value); + if (r == null) + return true; + + double w = r.getWidth(); + double h = r.getHeight(); + + //System.out.println("size: " + w + " x " + h); + if (w < unitsPerPixel && h < unitsPerPixel) { + //System.out.println("Skipping node: " + node); + return true; + } + +// if (w < simplificationUnitsPerPixelLimit && h < simplificationUnitsPerPixelLimit) { +// //System.out.println("simplifying node: " + node); +// simplified.add(node); +// } + } + + collected.add(node); + return true; + } + }); + Collections.sort(collected, G2DParentNode.G2DNODE_Z_COMPARATOR); + //System.out.println("rendering " + collected.size() + "/" + getNodeCount() + " children, " + simplified.size() + " as simplified"); + if (simplified.isEmpty()) { + for (IG2DNode node : collected) + if (node.validate()) + node.render(g); + } else { + for (IG2DNode node : collected) { + if (node.validate()) { + if (simplified.contains(node)) { + g.draw(node.getBoundsInLocal()); + } else { + node.render(g); + } + } + } + simplified.clear(); + } + } + +// // !DEBUG / PROFILING! +// g.setStroke(new BasicStroke(0.25f)); +// drawTree(g, tree.rtree); + + } finally { + if (ot != null) + g.setTransform(ot); + } + } + +// private void drawTree(final Graphics2D g, RTree rtree) { +// final Rectangle2D r = new Rectangle2D.Double(); +// tree.rtree.traverse(new IRectangleTraverseProcedure() { +// @Override +// public void call(double x0, double y0, double x1, double y1, int level, Object value) { +// r.setFrameFromDiagonal(x0, y0, x1, y1); +// g.setColor(getLevelColor(level)); +// g.draw(r); +// } +// +// private Color getLevelColor(int level) { +// switch (level) { +// case 0: return Color.DARK_GRAY; +// case 1: return Color.RED; +// case 2: return Color.PINK; +// case 3: return Color.BLUE; +// case 4: return Color.ORANGE; +// default: return Color.BLACK; +// } +// } +// }); +// } + + @ClientSide + public void setDirty() { + tree = null; + } + + private Tree getSpatialDecomposition() { + Tree t = tree; + if (t == null) { + t = decompose(); + tree = t; + } + return t; + } + + Properties props = new Properties(); + + private Tree decompose() { + RTree rtree = new RTree(); + rtree.init(props); + IG2DNode[] nodes = getSortedNodes(); + TIntObjectHashMap toNodes = new TIntObjectHashMap(nodes.length); + TIntObjectHashMap toBounds = new TIntObjectHashMap(nodes.length); + int rid = 0; + ArrayList boundlessNodes = null; + for (IG2DNode node : nodes) { + Rectangle2D bounds = node.getBounds(); + if (bounds != null) { + Rectangle r = toRectangle(bounds); + int id = ++rid; + rtree.add(r, id); + toNodes.put(id, node); + toBounds.put(id, bounds); + } else { + if (boundlessNodes == null) + boundlessNodes = new ArrayList(); + boundlessNodes.add(node); + } + } + return new Tree(rtree, boundlessNodes, toNodes, toBounds); + } + + /** + * @param rect + * @return + */ + public static Rectangle toRectangle(Rectangle2D rect) { + return new Rectangle((float) rect.getMinX(), (float) rect.getMinY(), (float) rect.getMaxX(), (float) rect.getMaxY()); + } + + /** + * Determine whether this rectangle is contained by the passed rectangle + * + * @param contained the rectangle tested to see if it contained by container + * @param container The rectangle that might contain this rectangle + * + * @return true if the container contains contained, + * false if it does not + */ + public static boolean containedBy(Rectangle contained, Rectangle2D container) { + return container.getMaxX() >= contained.maxX && container.getMinX() <= contained.minX + && container.getMaxY() >= contained.maxY && container.getMinY() <= contained.minY; + } + + @Override + public void init() { + super.init(); + //addEventHandler(this); + } + + @Override + public void cleanup() { + //removeEventHandler(this); + super.cleanup(); + } + + @Override + public int getEventMask() { + return EventTypes.MouseMask; + } + + @Override + public boolean handleEvent(Event e) { + // Propagate mouse events to children based on bounds. + //System.out.println("R-TREE HANDLE EVENT: " + e); + return false; + } + + @Override + public NodeEventHandler getEventHandler() { + // TODO: add an event handler here and propagate mouse events spatially + return NodeUtil.getNodeEventHandler(this); + } + +}