1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
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
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.scenegraph.g2d.nodes.spatial;
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;
24 import java.util.Properties;
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;
38 import com.infomatiq.jsi.Rectangle;
39 import com.infomatiq.jsi.rtree.RTree;
41 import gnu.trove.TIntObjectHashMap;
42 import gnu.trove.TIntProcedure;
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.
50 * The clipping boundary, i.e. the current viewport is retrieved from
51 * {@link Graphics2D#getClip()}.
55 * {@link #setDirty()} will mark the whole r-tree invalid meaning it will be
56 * reconstructed from scratch when it is needed again.
61 * <li>Add interface for marking children added/removed/changed to optimize
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
68 * @author Tuukka Lehtonen
70 public class RTreeNode extends G2DParentNode implements INodeEventHandlerProvider {
72 private static final boolean DISABLE_RTREE = false;
74 private static final boolean DEBUG_SHRINK_CLIP_RECT = false;
76 private static final long serialVersionUID = 8988645670981494042L;
79 * A container for everything related to the R-tree based spatial
82 private static class Tree {
83 public final RTree rtree;
86 * Bounds of the whole R-tree.
88 public final Rectangle bounds;
93 public final ArrayList<IG2DNode> boundlessNodes;
96 * Map from R-tree rectangle ID's to scene graph nodes.
98 public final TIntObjectHashMap<IG2DNode> toNodes;
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.
105 public final TIntObjectHashMap<Rectangle2D> toBounds;
107 public Tree(RTree rtree, ArrayList<IG2DNode> boundlessNodes, TIntObjectHashMap<IG2DNode> toNodes, TIntObjectHashMap<Rectangle2D> toBounds) {
109 this.bounds = rtree.getBounds();
110 this.boundlessNodes = boundlessNodes;
111 this.toNodes = toNodes;
112 this.toBounds = toBounds;
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>();
121 protected Map<String, INode> createChildMap() {
122 return super.createChildMap(1 << 15);
126 public void render(Graphics2D g) {
132 AffineTransform ot = null;
133 if (!transform.isIdentity()) {
134 ot = g.getTransform();
135 g.transform(transform);
138 g.setRenderingHint(G2DRenderingHints.KEY_TRANSFORM_UNDER_SPATIAL_ROOT, g.getTransform());
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();
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)
153 final double unitsPerPixel = 1.0 / viewScale;
154 //final double simplificationUnitsPerPixelLimit = 4*unitsPerPixel;
155 //System.out.println("view scale: " + viewScale + " - " + unitsPerPixel + " - " + simplificationUnitsPerPixelLimit);
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.
161 GeometryUtils.expandRectangle(bounds, 5);
164 if (DEBUG_SHRINK_CLIP_RECT) {
165 GeometryUtils.expandRectangle(bounds, -100.0*unitsPerPixel);
169 // Make sure that a spatial decomposition exists.
170 final Tree tree = getSpatialDecomposition();
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()) {
180 final Object render = g.getRenderingHint(RenderingHints.KEY_RENDERING);
184 if (tree.boundlessNodes != null) {
185 for (int i = 0, n = tree.boundlessNodes.size(); i < n; ++i)
186 collected.add(tree.boundlessNodes.get(i));
189 tree.rtree.intersects(toRectangle(bounds), new TIntProcedure() {
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())
199 if (render != RenderingHints.VALUE_RENDER_QUALITY) {
200 Rectangle2D r = tree.toBounds.get(value);
204 double w = r.getWidth();
205 double h = r.getHeight();
207 //System.out.println("size: " + w + " x " + h);
208 if (w < unitsPerPixel && h < unitsPerPixel) {
209 //System.out.println("Skipping node: " + node);
213 // if (w < simplificationUnitsPerPixelLimit && h < simplificationUnitsPerPixelLimit) {
214 // //System.out.println("simplifying node: " + node);
215 // simplified.add(node);
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)
230 for (IG2DNode node : collected) {
231 if (node.validate()) {
232 if (simplified.contains(node)) {
233 g.draw(node.getBoundsInLocal());
243 // // !DEBUG / PROFILING!
244 // g.setStroke(new BasicStroke(0.25f));
245 // drawTree(g, tree.rtree);
248 g.setRenderingHint(G2DRenderingHints.KEY_TRANSFORM_UNDER_SPATIAL_ROOT, null);
254 // private void drawTree(final Graphics2D g, RTree rtree) {
255 // final Rectangle2D r = new Rectangle2D.Double();
256 // tree.rtree.traverse(new IRectangleTraverseProcedure() {
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));
264 // private Color getLevelColor(int 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;
278 public void setDirty() {
282 private Tree getSpatialDecomposition() {
291 Properties props = new Properties();
293 private Tree decompose() {
294 RTree rtree = new RTree();
296 IG2DNode[] nodes = getSortedNodes();
297 TIntObjectHashMap<IG2DNode> toNodes = new TIntObjectHashMap<IG2DNode>(nodes.length);
298 TIntObjectHashMap<Rectangle2D> toBounds = new TIntObjectHashMap<Rectangle2D>(nodes.length);
300 ArrayList<IG2DNode> boundlessNodes = null;
301 for (IG2DNode node : nodes) {
302 Rectangle2D bounds = node.getBounds();
303 if (bounds != null) {
304 Rectangle r = toRectangle(bounds);
307 toNodes.put(id, node);
308 toBounds.put(id, bounds);
310 if (boundlessNodes == null)
311 boundlessNodes = new ArrayList<IG2DNode>();
312 boundlessNodes.add(node);
315 return new Tree(rtree, boundlessNodes, toNodes, toBounds);
322 public static Rectangle toRectangle(Rectangle2D rect) {
323 return new Rectangle((float) rect.getMinX(), (float) rect.getMinY(), (float) rect.getMaxX(), (float) rect.getMaxY());
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()) {
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())
347 Collections.sort(result, G2DParentNode.G2DNODE_Z_COMPARATOR);
352 * Determine whether this rectangle is contained by the passed rectangle
354 * @param contained the rectangle tested to see if it contained by container
355 * @param container The rectangle that might contain this rectangle
357 * @return <code>true</code> if the container contains contained,
358 * <code>false</code> if it does not
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;
368 //addEventHandler(this);
372 public void cleanup() {
373 //removeEventHandler(this);
378 public int getEventMask() {
379 return EventTypes.MouseMask;
383 public boolean handleEvent(Event e) {
384 // Propagate mouse events to children based on bounds.
385 //System.out.println("R-TREE HANDLE EVENT: " + e);
390 public NodeEventHandler getEventHandler() {
391 // TODO: add an event handler here and propagate mouse events spatially
392 return NodeUtil.getNodeEventHandler(this);