/*******************************************************************************
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management
+ * Copyright (c) 2007, 2018 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
*
* Contributors:
* VTT Technical Research Centre of Finland - initial API and implementation
+ * Semantum Oy - gitlab #66 - parallel/spatial optimization
*******************************************************************************/
package org.simantics.g2d.diagram.handler.impl;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.HashSet;
import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
import org.simantics.g2d.diagram.DiagramHints;
import org.simantics.g2d.diagram.IDiagram;
import org.simantics.g2d.diagram.handler.PickRequest;
import org.simantics.g2d.diagram.handler.PickRequest.PickPolicy;
import org.simantics.g2d.element.ElementClass;
+import org.simantics.g2d.element.ElementHints;
import org.simantics.g2d.element.ElementUtils;
import org.simantics.g2d.element.IElement;
import org.simantics.g2d.element.handler.ElementLayers;
import org.simantics.g2d.element.handler.Pick2;
import org.simantics.g2d.element.handler.Transform;
import org.simantics.g2d.layers.ILayers;
+import org.simantics.g2d.scenegraph.SceneGraphConstants;
import org.simantics.g2d.utils.GeometryUtils;
+import org.simantics.scenegraph.INode;
+import org.simantics.scenegraph.g2d.IG2DNode;
+import org.simantics.scenegraph.g2d.nodes.spatial.RTreeNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
/**
* @author Toni Kalajainen
+ * @author Jani Simomaa
+ * @author Tuukka Lehtonen
*/
public class PickContextImpl implements PickContext {
public static final PickContextImpl INSTANCE = new PickContextImpl();
+ private static final Logger LOGGER = LoggerFactory.getLogger(PickContextImpl.class);
+
+ private static final boolean PERF = false;
+
+ private static final ThreadLocal<Rectangle2D> perThreadElementBounds = ThreadLocal.withInitial(() -> new Rectangle2D.Double());
+
+ private boolean useRTree;
+
+ public PickContextImpl() {
+ this(false);
+ }
+
+ public PickContextImpl(boolean useRTree) {
+ this.useRTree = useRTree;
+ }
+
@Override
public void pick(
IDiagram diagram,
assert(request!=null);
assert(finalResult!=null);
- ILayers layers = diagram.getHint(DiagramHints.KEY_LAYERS);
+ long startTime = PERF ? System.nanoTime() : 0L;
+
+ List<IElement> result = pickElements(diagram, request);
- Collection<IElement> result = finalResult;
- if (request.pickSorter != null) {
- // Need a temporary List<IElement> for PickSorter
- result = new ArrayList<IElement>();
+ if (PERF) {
+ long endTime = System.nanoTime();
+ LOGGER.info("[picked {} elements @ {}] total pick time {} ms", result.size(), request.pickArea, ((endTime - startTime)*1e-6));
}
- Rectangle2D elementBounds = new Rectangle2D.Double();
- nextElement:
- for (IElement e : diagram.getSnapshot())
- {
+
+ if (!result.isEmpty()) {
+ if (request.pickSorter != null) {
+ List<IElement> elems = new ArrayList<>(result);
+ request.pickSorter.sort(elems);
+ finalResult.addAll(elems);
+ } else {
+ finalResult.addAll(result);
+ }
+ }
+ }
+
+ private static class PickFilter implements Predicate<IElement> {
+
+ private final PickRequest request;
+ private final ILayers layers;
+ private final boolean checkLayers;
+
+ public PickFilter(PickRequest request, ILayers layers) {
+ this.request = request;
+ this.layers = layers;
+ this.checkLayers = layers != null && !layers.getIgnoreFocusSettings();
+ }
+
+ @Override
+ public boolean test(IElement e) {
// Ignore hidden elements.
if (ElementUtils.isHidden(e))
- continue;
+ return false;
ElementClass ec = e.getElementClass();
-
- if(layers != null && !layers.getIgnoreFocusSettings()) {
+
+ if (checkLayers) {
ElementLayers el = ec.getAtMostOneItemOfClass(ElementLayers.class);
- if(el != null) {
- if(!el.isFocusable(e, layers)) continue;
- }
- }
-
- if (request.pickFilter!=null && !request.pickFilter.accept(e)) continue;
-
- Transform t = e.getElementClass().getSingleItem(Transform.class);
- AffineTransform canvasToElement = t.getTransform(e);
- if (canvasToElement==null) continue;
- double det = canvasToElement.getDeterminant();
- if (det == 0) {
- // Singular transform, just reset the rotation/scaling part to
- // allow picking to proceed.
- // TODO: this may modify the internal transform value of an element which is not intended
- canvasToElement.setToTranslation(
- canvasToElement.getTranslateX(),
- canvasToElement.getTranslateY());
+ if (el != null && !el.isFocusable(e, layers))
+ return false;
}
- // Get bounds, ignore elements that have no bounds
- InternalSize b = e.getElementClass().getAtMostOneItemOfClass(InternalSize.class);
- if (b==null) continue;
- elementBounds.setFrame(Double.NaN, Double.NaN, Double.NaN, Double.NaN);
- b.getBounds(e, elementBounds);
- if (Double.isNaN(elementBounds.getWidth()) || Double.isNaN(elementBounds.getHeight()))
- continue;
-
- Shape elementBoundsOnCanvas = GeometryUtils.transformShape(elementBounds, canvasToElement);
- if (elementBoundsOnCanvas instanceof Rectangle2D)
- elementBoundsOnCanvas = elementBoundsOnCanvas.getBounds2D();
- elementBoundsOnCanvas = elementBoundsOnCanvas.getBounds2D();
- org.simantics.scenegraph.utils.GeometryUtils.expandRectangle((Rectangle2D)elementBoundsOnCanvas, 1e-3, 1e-3, 1e-3, 1e-3);
-
+ if (request.pickFilter != null && !request.pickFilter.accept(e))
+ return false;
+
+ // Get InternalSize for retrieving bounds, ignore elements that have no bounds
+ InternalSize b = ec.getAtMostOneItemOfClass(InternalSize.class);
+ if (b == null)
+ return false;
+
+ // Anything that is without a transformation is not pickable
+ AffineTransform canvasToElement = getTransform(e);
+ if (canvasToElement == null)
+ return false;
+
+ Rectangle2D elementBoundsOnCanvas = getElementBounds(e, b, canvasToElement);
+ if (elementBoundsOnCanvas == null)
+ return false;
+
// Pick with pick handler(s)
- List<Pick> pickHandlers = e.getElementClass().getItemsByClass(Pick.class);
- if (!pickHandlers.isEmpty())
- {
- // Rough filtering with bounds
+ List<Pick> pickHandlers = ec.getItemsByClass(Pick.class);
+ if (!pickHandlers.isEmpty()) {
+ // Rough filtering with bounds
if (!GeometryUtils.intersects(request.pickArea, elementBoundsOnCanvas)) {
-// System.out.println("Element bounds discards " + e.getElementClass());
- continue;
+ // System.out.println("Element bounds discards " + e.getElementClass());
+ return false;
}
-
- // Convert pick shape to element coordinates
-// AffineTransform elementToCanvas;
-// try {
-// elementToCanvas = canvasToElement.createInverse();
-// } catch (NoninvertibleTransformException e1) {
-// throw new RuntimeException(e1);
-// }
-// Shape pickShapeInElementCoords = GeometryUtils.transformShape(request.pickArea, elementToCanvas);
- for (Pick p : pickHandlers)
- {
- if (p instanceof Pick2) {
- Pick2 p2 = (Pick2) p;
- //if (p2.pick(e, pickShapeInElementCoords, request.pickPolicy, result) > 0)
- if (p2.pick(e, request.pickArea, request.pickPolicy, result) > 0)
- continue nextElement;
- } else {
- //if (p.pickTest(e, pickShapeInElementCoords, request.pickPolicy)) {
- if (p.pickTest(e, request.pickArea, request.pickPolicy)) {
- result.add(e);
- continue nextElement;
- }
+
+ // NOTE: this doesn't support Pick2 interface anymore
+ for (Pick p : pickHandlers) {
+ if (p.pickTest(e, request.pickArea, request.pickPolicy)) {
+ return true;
}
}
- continue nextElement;
+ return false;
}
-
- // Pick with shape handler(s)
- List<Outline> shapeHandlers = e.getElementClass().getItemsByClass(Outline.class);
- if (!shapeHandlers.isEmpty())
- {
- // Rough filtering with bounds
- if (!GeometryUtils.intersects(request.pickArea, elementBoundsOnCanvas)) continue;
-
- // Convert pick shape to element coordinates
- AffineTransform elementToCanvas;
- try {
- elementToCanvas = canvasToElement.createInverse();
- } catch (NoninvertibleTransformException e1) {
- throw new RuntimeException(e1);
+
+ // Pick with Outline handler(s)
+ List<Outline> outlineHandlers = ec.getItemsByClass(Outline.class);
+ if (!outlineHandlers.isEmpty())
+ return pickByOutline(e, request, elementBoundsOnCanvas, canvasToElement, outlineHandlers);
+
+ // Finally, pick by rectangle
+ return pickByBounds(e, request, elementBoundsOnCanvas);
+ }
+
+ }
+
+ private static Rectangle2D toBoundingRectangle(Shape shape) {
+ if (shape instanceof Rectangle2D)
+ return (Rectangle2D) shape;
+ else
+ return shape.getBounds2D();
+ }
+
+ private List<IElement> pickElements(IDiagram diagram, PickRequest request) {
+ ILayers layers = diagram.getHint(DiagramHints.KEY_LAYERS);
+
+ // Get the scene graph nodes that intersect the pick-requests pick shape
+ INode spatialRoot = useRTree && request.pickContext != null
+ ? request.pickContext.getSceneGraph().lookupNode(SceneGraphConstants.SPATIAL_ROOT_NODE_ID)
+ : null;
+
+ if (spatialRoot instanceof RTreeNode) {
+ // Optimized picking version that no longer supports Pick2 interface
+ // and therefore doesn't support connections modelled as
+ // branchpoint/edge subelements of connection elements.
+
+ RTreeNode rtree = (RTreeNode) spatialRoot;
+ Map<INode, IElement> nodeToElement = diagram.getHint(DiagramHints.NODE_TO_ELEMENT_MAP);
+ if (nodeToElement != null) {
+ // The most optimized version
+ return rtree.intersectingNodes(toBoundingRectangle(request.pickArea), new ArrayList<>())
+ .stream()
+ .parallel()
+ .map(nodeToElement::get)
+ .filter(Objects::nonNull)
+ .filter(new PickFilter(request, layers))
+ .collect(Collectors.toList());
+ } else {
+ // Slower version for when DiagramHints.NODE_TO_ELEMENT_MAP is not used
+ Set<IG2DNode> nodes =
+ new HashSet<>(
+ rtree.intersectingNodes(
+ toBoundingRectangle(request.pickArea),
+ new ArrayList<>())
+ );
+
+ return diagram.getSnapshot().stream()
+ .parallel()
+ // Choose only elements that are under the pick region bounds-wise
+ .filter(e -> {
+ INode node = e.getHint(ElementHints.KEY_SG_NODE);
+ return nodes.contains(node);
+ })
+ // Perform comprehensive picking
+ .filter(new PickFilter(request, layers))
+ .collect(Collectors.toList());
+ }
+
+ } else {
+
+ // Fall-back logic that ends up processing everything.
+ // This still supports all the old logic and the Pick2
+ // interface in element classes.
+ List<IElement> result = new ArrayList<>();
+ boolean checkLayers = layers != null && !layers.getIgnoreFocusSettings();
+
+ // Do not do this in parallel mode to keep results in proper Z order
+ diagram.getSnapshot().stream().forEachOrdered(e -> {
+ // Ignore hidden elements.
+ if (ElementUtils.isHidden(e))
+ return;
+
+ ElementClass ec = e.getElementClass();
+
+ if (checkLayers) {
+ ElementLayers el = ec.getAtMostOneItemOfClass(ElementLayers.class);
+ if (el != null && !el.isFocusable(e, layers))
+ return;
}
- Shape pickShapeInElementCoords = GeometryUtils.transformShape(request.pickArea, elementToCanvas);
-
- // Intersection with one shape is enough
- if (request.pickPolicy == PickPolicy.PICK_INTERSECTING_OBJECTS)
- {
- for (Outline es : shapeHandlers)
- {
- Shape elementShape = es.getElementShape(e);
- if (elementShape==null) continue nextElement;
- if (GeometryUtils.intersects(pickShapeInElementCoords, elementShape))
- {
- result.add(e);
- continue nextElement;
+
+ if (request.pickFilter != null && !request.pickFilter.accept(e))
+ return;
+
+ // Get InternalSize for retrieving bounds, ignore elements that have no bounds
+ InternalSize b = ec.getAtMostOneItemOfClass(InternalSize.class);
+ if (b == null)
+ return;
+
+ // Anything that is without a transformation is not pickable
+ AffineTransform canvasToElement = getTransform(e);
+ if (canvasToElement == null)
+ return;
+
+ Rectangle2D elementBoundsOnCanvas = getElementBounds(e, b, canvasToElement);
+ if (elementBoundsOnCanvas == null)
+ return;
+
+ // Pick with pick handler(s)
+ List<Pick> pickHandlers = ec.getItemsByClass(Pick.class);
+ if (!pickHandlers.isEmpty()) {
+ // Rough filtering with bounds
+ if (!GeometryUtils.intersects(request.pickArea, elementBoundsOnCanvas)) {
+ // System.out.println("Element bounds discards " + e.getElementClass());
+ return;
+ }
+
+ for (Pick p : pickHandlers) {
+ if (p instanceof Pick2) {
+ Pick2 p2 = (Pick2) p;
+ if (p2.pick(e, request.pickArea, request.pickPolicy, result) > 0)
+ return;
+ } else {
+ if (p.pickTest(e, request.pickArea, request.pickPolicy)) {
+ result.add(e);
+ return;
+ }
}
}
- continue nextElement;
+ return;
}
-
- // Contains of all shapes is required
- if (request.pickPolicy == PickPolicy.PICK_CONTAINED_OBJECTS)
- {
- for (Outline es : shapeHandlers)
- {
- Shape elementShape = es.getElementShape(e);
- if (!GeometryUtils.contains(pickShapeInElementCoords, elementShape))
- continue nextElement;
+
+ // Pick with shape handler(s)
+ List<Outline> outlineHandlers = ec.getItemsByClass(Outline.class);
+ if (!outlineHandlers.isEmpty()) {
+ if (pickByOutline(e, request, elementBoundsOnCanvas, canvasToElement, outlineHandlers)) {
+ result.add(e);
}
- result.add(e);
- continue nextElement;
+ return;
}
- continue nextElement;
- }
-
- // Pick by rectangle
- if (request.pickPolicy == PickPolicy.PICK_INTERSECTING_OBJECTS)
- {
- if (GeometryUtils.intersects(request.pickArea, elementBoundsOnCanvas))
+
+ // Finally, pick by bounding rectangle
+ if (pickByBounds(e, request, elementBoundsOnCanvas))
result.add(e);
+ });
+
+ return result;
+
+ }
+ }
+
+ private static AffineTransform getTransform(IElement e) {
+ // Anything that is without a transformation is not pickable
+ Transform t = e.getElementClass().getSingleItem(Transform.class);
+ AffineTransform canvasToElement = t.getTransform(e);
+ if (canvasToElement == null)
+ return null;
+
+ double det = canvasToElement.getDeterminant();
+ if (det == 0) {
+ // Singular transform, only take the translation from it to move on.
+ canvasToElement = AffineTransform.getTranslateInstance(canvasToElement.getTranslateX(), canvasToElement.getTranslateY());
+ }
+
+ return canvasToElement;
+ }
+
+ private static Rectangle2D getElementBounds(IElement e, InternalSize b, AffineTransform transform) {
+ Rectangle2D elementBounds = perThreadElementBounds.get();
+ elementBounds.setFrame(Double.NaN, Double.NaN, Double.NaN, Double.NaN);
+ b.getBounds(e, elementBounds);
+ if (Double.isNaN(elementBounds.getWidth()) || Double.isNaN(elementBounds.getHeight()))
+ return null;
+
+ // Get optionally transformed axis-aligned bounds of the element,
+ // expanded by 1mm in each direction.
+ Rectangle2D transformedBounds = transform != null
+ ? toBoundingRectangle(GeometryUtils.transformShape(elementBounds, transform))
+ : elementBounds;
+ return org.simantics.scenegraph.utils.GeometryUtils.expandRectangle(transformedBounds, 1e-3);
+ }
+
+ private static boolean pickByOutline(IElement e, PickRequest request, Rectangle2D elementBoundsOnCanvas, AffineTransform canvasToElement, List<Outline> outlineHandlers) {
+ // Rough filtering with bounds
+ if (!GeometryUtils.intersects(request.pickArea, elementBoundsOnCanvas))
+ return false;
+
+ // Convert pick shape to element coordinates
+ AffineTransform elementToCanvas;
+ try {
+ elementToCanvas = canvasToElement.createInverse();
+ } catch (NoninvertibleTransformException ex) {
+ throw new RuntimeException(ex);
+ }
+ Shape pickShapeInElementCoords = GeometryUtils.transformShape(request.pickArea, elementToCanvas);
+
+ // Intersection with one shape is enough
+ if (request.pickPolicy == PickPolicy.PICK_INTERSECTING_OBJECTS) {
+ for (Outline es : outlineHandlers) {
+ Shape elementShape = es.getElementShape(e);
+ if (elementShape == null)
+ return false;
+ if (GeometryUtils.intersects(pickShapeInElementCoords, elementShape)) {
+ return true;
+ }
}
-
- else
-
- if (request.pickPolicy == PickPolicy.PICK_CONTAINED_OBJECTS)
- {
- if (GeometryUtils.contains(request.pickArea, elementBoundsOnCanvas))
- result.add(e);
+ return false;
+ }
+
+ // Contains of all shapes is required
+ if (request.pickPolicy == PickPolicy.PICK_CONTAINED_OBJECTS) {
+ for (Outline es : outlineHandlers) {
+ Shape elementShape = es.getElementShape(e);
+ if (!GeometryUtils.contains(pickShapeInElementCoords, elementShape))
+ return false;
}
-
+ return true;
}
- if (request.pickSorter != null) {
- request.pickSorter.sort((List<IElement>) result);
- finalResult.addAll(result);
+ return false;
+ }
+
+ private static boolean pickByBounds(IElement e, PickRequest request, Rectangle2D elementBoundsOnCanvas) {
+ if (request.pickPolicy == PickPolicy.PICK_INTERSECTING_OBJECTS) {
+ if (GeometryUtils.intersects(request.pickArea, elementBoundsOnCanvas))
+ return true;
+ } else if (request.pickPolicy == PickPolicy.PICK_CONTAINED_OBJECTS) {
+ if (GeometryUtils.contains(request.pickArea, elementBoundsOnCanvas))
+ return true;
}
+ return false;
}
}