Someone asked about shape-point collision detection for the point under the mouse in a case where there are many shapes on the stage, and how to improve performance in relation to the Stage.getAllIntesections(), Stage.getIntersection() and Shape.intersects() methods. Here’s my explanation of those functions and an approach to improving hit detection.
Just to be clear – this is not about shape-to-shape intersection, it is about answering the question ‘does this point (x,y) hit any shapes on the stage?’
TLDR: See the sample code here.
The problem
Stepping back from Konva for a moment, I wanted to talk about the challenge here. First a few ground rules:
- Konva is a wrapper for the html5 canvas and its drawing functions.
- Konva adds a massive amount of features over the raw canvas functionality, but it is restricted by the fundamental capabilities of the canvas element.
- The HTML5 canvas uses vector drawing commands. Vector drawing is quick, efficient, and the drawing instructions are compact to store.
- Vector drawing uses math to describe geometric shapes – rect, circle, ellipse, path, etc.
- These shapes are then stroked and filled to produce the pixel images that we see on the canvas.
So back to the problem – deciding if a point is on a shape is actually a math problem, because the shapes are drawn by math. This is workable up to a point – checking a point hit on a rect is easy, it is simply is the x of this point within the left & right of the rect, and is the y of this point within the bottom and top?
The math continues to be straightforward for circles. Then it starts to become harder for triangles, hexagons, etc. And these are just the geometric shapes. When they are what Konva calls ‘custom shapes’, or even images, then math has no answer.
Which is a shame because math is very quick on computers.
The solution?
Then how can we get a reliable answer to the question?
Ultimately we have to check the pixels in the canvas. The HTML5 canvas provides a method to get an array of pixels from any rectangular area upon it. The pixels array gives the red, green, blue and alpha value for each pixel. Getting the whole pixel array for a large canvas is a performance consideration. But what we can do is to get the single pixel info for the point we need to check – if there is any color value and the alpha is > 0 then we have a hit!
But a hit on what? Maybe there are 100 shapes on the canvas – we don’t know whether we hit a single shape alone or some combination of shapes.
Aside: I can hear your mind whirring….maybe if the shapes were each given individual color or alpha values then we could check the color value under the point and look up the color value and know the shape we hit? Oh no, that won’t work if there are multiple shapes as their colors will blend if the alpha allows it, and it not then we will only ‘see’ the top-most shape. Sad face!
But you have just struck upon the approach behind the Stage.getAllIntersections(), Stage.getIntersection() and Shape.intersects() methods. What these methods actually do is use a second hidden canvas, draw a shape on it, and get the pixel data at the point of interest and look for any color – yes any color because we only have one shape on the canvas so any color under the point means we have a hit. [A note about antialiasing – which cannot be turned off – actually Konva DOES take into consideration a hit on an anti-aliased color – it uses a spiral search when it hits an antialiased pixel, because the actual shape pixels must be very nearby. Effectively this mean it checks the 8 pixels surrounding the initial pixel to get an answer that ignores antialiasing – clever Konva!]
The Stage.getIntersection() method works down the listening layers from topmost to bottom, and returns the first visible shape, and the Stage.getAllIntersections() does the same but does not stop at the first hit – it inspects all visible shapes on all visible layers and returns a list of the hits. To do this, it uses the steps to clear hidden stage, draw shape with single color, check point colors,…repeat for all shapes. Meanwhile the Shape.intersects() does the same process for the given point and shape only. Just to be clear, when Konva is operating on the hidden canvas the shapes can be drawn in any color without alpha because this does not affect the visible canvas in any way – it just needs to know to recognise a pixel is part of the shape and not a part of the antialiasing.
Knowing this we can understand why these methods have a performance overhead – all that clearing the canvas, drawing a shape, shovelling pixels into the display, then grabbing one from the array will hurt performance to some extent.
But, on balance, we have to recognise that the only way to be sure of a hit is to inspect pixels. So – could we have some hybrid solution where we can use math to find shapes that we suspect are under the target point, then use the more expensive canvas pixel checks to confirm actual hits? Yes !
Finding suspects – the isPointInRectangle function
This function will detect if a point is within a rectangle.
// rectangle objects: {x:, y:, width:, height: }
// var rect={x:10, y:15, width:25, height:20}
// Return true if the x,y point is inside the rectangle
function isPointInRectangle(x,y,rect){
return(
x>rect.x && x<rect.x+rect.width && y>rect.y
&& y<rect.y+rect.height);
}
Simple as it is, this is the answer to the question of using math-based check to spot suspect shape hits. All we need to do is decide what rectangle to check for each shape.
We could try using Shape.getSelfRect(). Every shape has the notion of a surrounding rectangle. Draw commands for most shapes refer to the top-left and the shape has a width and height that we can see on the canvas. However, this method does NOT take into account and transformations – rotating or scaling the shape will mean the sefRect is no longer a reliable statement of the rect that the shape occupies. Instead we need to use the Shape.getClientRect() method which will give the minimal sized bounding rect that will enclose the shape as you see it on the canvas.
So – we can get the rect for any shape via getClientRect(). We can then pass that and the point into the isPointInRectangle() function and know if we have a suspect hit. Let me stress that all we know based on this is that the point is in the rect surrounding the shape as we see it. But it does NOT confirm that the point is ‘touching’ the shape. For example, if the shape is a circle and the point is in the top-left of the rect, then isPointInRectangle() will show a hit but actually the point is outside the shape we see.
The diagram below illustrates, for a rectangle shape, the selfRect and the clientRect acheived by rotating by +45 degrees then scaling in the x-axis by 50%. As you can see, the point to check is inside the client rect, so being a suspect from the math-based check, but needs to be confirmed as a definite miss by a more accurate means.
Confirming hits – the Shape.intersects() method
Once we have a suspected hit on a shape we can commit to the more expensive Konva process that checks the color value of the actual pixel at the point of interest. This final check will confirm if the point is actually ON the shape as opposed to being in the rect but outside the shape itself.
In code:
function getAllHits(pt){
const layers = stage.children,
len = layers.length,
end = len - 1,
list = [];
for (let n = end; n >= 0; n--) {
for (let shape of layers[n].children){
if (isPointInRectangle(pt.x, pt.y, shape.getClientRect()) ){
// only handle suspected hits
if (shape.intersects(pt)){
// we now have a confirmed hit!
list.push(shape);
}
}
}
}
return list;
}
// rectangle objects: {x:, y:, width:, height: }
// var rect={x:10, y:15, width:25, height:20}
// Return true if the x,y point is inside the rectangle
function isPointInRectangle(x,y,rect){
return(x>rect.x && x<rect.x+rect.width && y>rect.y && y<rect.y+rect.height);
}
Further improvements
Gridding
We could also improve this approach by breaking the stage into a grid of large rects. – for example a grid of 4 or 9. At first drawing and any movements of each shape, use rect-overlap math of the corners of the shape.clientRect to store a note of any grid square a shape overlaps. Now when you need to detect intersections you can first find the grid-square that the point is in, then cycle through the rects in that square using the function as above to find intersecting shapes. If you break the stage into a 2 x 2 grid you have one quarter the space to check, if its 3 x 3 you have one ninth, so the more grid squares the more efficient your process becomes.
Throttling events
If you are working on checking the point under the mouse as the user moves it across the stage then you will be using a mousemove or drag listener. These are triggered on each cycle of the movement process – potentially many times a second. If your hit-detection code runs on every move then that will be a heavy load for the processor on most devices. Instead, consider throttling the event – so only reacting to it every quarter second or so.
var timesPerSecond = 10; // how many times to fire the event per second
var wait = false;
stage.on('mousemove', function (event) {
// don't handle events when one has just occurred
if (!wait) {
// fire the event
const pt = stage.getPointerPosition();
const hitList = getAllHits(pt);
$('#info').html('Point (' + pt.x + ', ' + pt.y + ') Hit count ' + hitList.length);
// stop any further events
wait = true;
// after a fraction of a second, allow events again
setTimeout(function () {
wait = false;
}, 1000 / timesPerSecond);
}
});
Summary
We’ve looked at the challenge of point-on-shape hit detection, looked at what Konva has to offer, and worked out an optimised approach. We also looked at optimising that with the grid approach and by throttling the triggering event.
Thanks for reading
VW July 2022
Coding for the long view 