I had a question about how to do edge tracing for use in collision detection for a game - think 'Asteroids'. I couldn't frame the question clearly so I did some R&D. The question I had in mind was 'how can I detect the edges of non-geometric shapes in a way that is pragmatic, fast and simple'. The reading I did before I rolled up my sleeves seemed to be leading down the road of using a minimal bounding rectangle around whatever object is to be collision detected. I wanted more accuracy, and since my game will be using the HTML canvas....
I am posting this in case it is of use to other people and as an answer to my own question. I would be interested to know if this is a standard technique, which I am sure it must be, and if there are some standard ways to improve it.
The approach in this code is to copy the shape into a canvas, then grab the pixel array for the smallest bounding rectangle. The canvas pixel array is a continuous 1D array with slots 0,1,2,3 containing the R, G, B, and Alpha values for the pixel. So the array is 4 times the size of the w x h. That's not so important, but useful to know.
We traverse the array to run 4 line-scans scans, effectively running a finger along the canvas from left-right, top - bottom, right - left, bottom - top, looking for the edge pixels.
Say we are scanning left to right - we start on line 1 and inspect each pixels alpha value in turn. If the value is non-zero we know we have found a pixel on the boundary of the shape. We don't care about the details of the pixel colour or any pixels after this on line 1 so we move on to line 2 and repeat. If you do this left to right, right to left, top down and bottom up, the conclusion is a set of x,y points that represent a fair guess at the edges of the shape. It is not perfect as there is a 'shadow' effect as illustrated by the edge trace snippet (add square and star).
Negatives - clearly there could be a lot of pixels to scan, But on the positive side, you will only scan once, and you can store the results that you know are not going to change as part of your app data!
Consider an asteroids game - you could have 30 different asteroid shapes, well possibly really only 10 with the additional 20 being scaled versions of the 10. So you scan those and save the edge data. From there on, edge detection is a matter of rectangle comparison with some common sense techniques to avoid too much overhead.
Todo: For efficiency later the list of points needs to be sorted, and possibly collected into a tree structure, combined with a larger sector-grid and some code to identify which objects are in which sectors, and we need a process that works for when the objects are rotated.
The snippet lets you add some shapes to the left-hand canvas, and visualizes the edge trace on the right-hand side.
// add a stage
var s1 = new Konva.Stage({container: 'container', width: 800, height: 600});
var s2 = new Konva.Stage({container: 'container2', width: 800, height: 600});
// Add a layer and group to draw on
var l1 = new Konva.Layer({});
s1.add(l1);
var g1 = null;
// Add a display layer and group to draw on - only used to visualise what is going on
var l2 = new Konva.Layer({});
s2.add(l2);
var g2 = new Konva.Group({});
// this function is called from the buttons to throw some interesting shapes onto the canvas for tracing
var makeShape = function(opts){
var x = opts.x + opts.w;
var y = opts.y + opts.w;
// if the main group is not defined do it now.
if (!g1){
g1 = new Konva.Group({x: opts.x, y: opts.y, width: opts.w, height: opts.w});
l1.add(g1);
}
// Draw the requested shape.
switch (opts.type){
case "circle":
var c=new Konva.Circle({
x: opts.x + opts.w, y: opts.y + opts.w,
radius: opts.w/2,
fill: 'white',
stroke: 'black',
strokeWidth: 4,
listening: true
});
g1.add(c);
break;
case "square":
var r = new Konva.Rect({ x: opts.x, y: opts.y, width: opts.w, height: opts.w, stroke: 'black' });
g1.add(r);
break;
case "star":
var star = new Konva.Star({
x: opts.x + opts.w + 30, y: opts.y + opts.w,
numPoints: 6,
innerRadius: 40,
outerRadius: 70,
fill: 'yellow',
stroke: 'black',
strokeWidth: 4
});
// add the shape to the layer
g1.add(star);
break;
case "blob":
var blob = new Konva.Line({
points: [23, 20, 23, 160, 70, 93, 150, 109, 290, 139, 270, 93],
fill: '#00D2FF',
stroke: 'black',
strokeWidth: 5,
closed : true,
tension : 0.3
});
g1.add(blob);
break;
case 'rocket':
var rocket = new Konva.Image({
x: 50,
y: 50,
image: img,
width: 106,
height: 118
});
g1.add(rocket);
break;
}
l1.draw();
// and lets draw it all
s1.draw()
}
// This is what this is all about !
function scanForEdges(){
// get the imageData
var c = l1.getCanvas();
var ctx = c.getContext();
// Now we have the inageData - this is a one-D array with a four-step sequence
// where 1=R, 2=G, 3=B and 4=A. So positions 1-4 give RBBA values of pixel 1.
// A lot of examples walk the entire array to flip colours, but we need to walk
// a line-scan to find the outer edge of the shape by looking for any of the A
// values not being zero. This is because A=0 is invisible
// and all other values ARE a visible pixel. We only need to scan left to right
// until the first hit, then right to left the same, then the top & bottom scans. As
// long as the rect we select is not overly gappy around the shape then it
// 'should' be quick.
// Get the width and height of the box to scan,
var gsz = g1.getClientRect();
var x = 0, y = 0, w = gsz.x + gsz.width, h = gsz.y + gsz.height;
// get the pixel data for that box
var imgData = ctx.getImageData(x, y, w, h);
var data = imgData.data;
// console.log('h=' + h + ' w=' + w + ' data len=' + data.length);
var pxWidth = w * 4, xStep = 1, yStep = 1; // steps > 1, like 3 or 7 can speed up the scan but they can miss edges of squares.
// you can set these false to see the effect of each scan - all true for live.
var doWEScan = true, doEWScan = true, doNSScan = true, doSNScan = true;
var plotRects = []; // this is where we collect the boundary points
if (doWEScan){
// walk the Alpha pixels West to East.
for (var y = 0; y < h; y = y + yStep){
for (var x = 0; x < w; x = x + xStep){
pxNo = (y * pxWidth) + (x * 4)
if ( data[pxNo + 3] > 0){
xStep1 = xStep
plotRects.push({x:x, y: y, w: 4, h:4, pxNo: pxNo});
break;
}
}
}
}
if (doEWScan){
// walk the Alpha pixels East to West.
for (var y = 0; y < h; y = y + yStep){
for (var x = w; x >=0; x = x - xStep){
pxNo = (y * pxWidth) + (x * 4)
if ( data[pxNo + 3] > 0){
plotRects.push({x: x, y: y, w: 4, h:4, pxNo: pxNo});
break;
}
}
}
}
if (doNSScan){
// walk the pixels N to S.
for (var x = 0; x < w; x = x + xStep){
for (var y = 0; y < h; y = y + yStep){
pxNo = (y * pxWidth) + (x * 4)
if ( data[pxNo + 3] > 0){
plotRects.push({x: x, y: y, w: 4, h:4, pxNo: pxNo});
break;
}
}
}
}
if (doSNScan){
// walk the pixels S to N.
for (var x = 0; x < w; x = x + xStep){
for (var y = h; y >= 0; y = y - yStep){
pxNo = (y * pxWidth) + (x * 4)
if ( data[pxNo + 3] > 0){
plotRects.push({x: x, y: y, w: 4, h:4, pxNo: pxNo});
break;
}
}
}
}
// So now we have the results stored in plotRects[] - we are going to visualise then on another canvas
// but in live use you would use this array for hit-detection processing.
// clear the visualisation group & layer
g2.destroyChildren();
g2.destroy;
s2.clear()
// Addrect just...adds rects !
var addRect = function(x,y,w,h){
w=1;h=1;
var r = new Konva.Rect({
x: x, y:y, width: w, height: h, strokeWidth:0.1, stroke: 'red', fill: 'red'
});
l2.add(g2)
g2.add(r);
}
var c2 = l2.getCanvas();
var ctx2 = c2.getContext();
ctx2.putImageData(imgData, 0, 0);
ctx2.drawImage(c2._canvas, 0, 0);
for (var i = 0; i < plotRects.length; i = i + 1){
var r = plotRects[i];
addRect(r.x, r.y, r.w, r.h)
}
l2.draw();
//console.log('Done - calculated ' + plotRects.length + ' pts')
}
// Events for the buttons
$('.addShape').click(function(e){
var type = $(this).prop('id');
makeShape({w:120, x: 4, y: 4, type: type});
scanForEdges();
})
$('#reset').click(function(e){
g1.destroyChildren();
g1.destroy()
g1=null;
l1.clear();
s1.clear();
})
// fluff to get the svg image into the canvas.
var svg = document.querySelector('svg');
var img = document.querySelector('img');
// get svg data
var xml = new XMLSerializer().serializeToString(svg);
// make it base64
var svg64 = btoa(xml);
var b64Start = 'data:image/svg+xml;base64,';
// prepend a "header"
var image64 = b64Start + svg64;
// set it as the source of the img element
img.src = image64;
setTimeout(function(){
// something to get is started
$('#rocket').trigger('click');
},
500
)p
{
padding: 5px;
}
.container
{display: inline-block;
width: 250px;
height: 300px;
background-color: transparent;
overflow: scroll;
border: 1px solid red;
}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="https://cdn.rawgit.com/konvajs/konva/1.6.5/konva.min.js"></script>
<div>
<button id='square' class='addShape'>Add square</button>
<button id='circle' class='addShape'>Add circle</button>
<button id='star' class='addShape'>Add star</button>
<button id='blob' class='addShape'>Add blob</button>
<button id='rocket' class='addShape'>Add rocket ship</button>
<button id='reset'>Reset</button>
</div>
<div id='container' class='container'></div>
<div id='container2' class='container'></div>
<p>
<span id='text'>Issue: Shadowing effect.</span>
</p>
<div style='display: none;'>
<img />
<svg id='rocketship' version="1.1" id="Capa_1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px"
viewBox="0 0 309.133 309.133" style="enable-background:new 0 0 309.133 309.133;" xml:space="preserve" width='200' height='200'>
<g>
<path d="M30.078,172.934c23.695-34.108,37.633-56.082,47.795-72.321c-39.053,3.454-76.486,52.048-76.486,52.048l25.777,25.776
C27.912,176.531,28.867,174.68,30.078,172.934z"/>
<path d="M130.723,281.997l25.76,25.759c0,0,48.592-37.43,52.047-76.482c-16.234,10.158-38.201,24.091-72.32,47.792
C134.484,280.264,132.644,281.242,130.723,281.997z"/>
<path d="M91.549,268.678c-4.422,1.787-8.768,3.686-13.299,5.2c-12.102,4.045-24.566,6.778-37.203,8.522
c-5.297,0.731-10.643,1.351-15.998,1.757c0.051-0.661,0.1-1.323,0.156-1.983c1.105-12.876,3.064-25.685,6.229-38.223
c1.525-6.051,3.471-11.933,5.56-17.807c1.299-3.652,2.92-7.147,4.555-10.642l-2.834-2.832c-6.303,4.234-11.785,9.584-16.437,15.637
c-6.887,8.963-12.049,19.117-15.658,29.817c-3.877,11.489-6.189,23.657-6.549,35.787c-0.051,1.704-0.168,3.445,0.096,5.136
c0.34,2.184,1.299,4.251,2.74,5.926c1.426,1.657,3.303,2.908,5.383,3.579c1.746,0.563,3.502,0.573,5.313,0.559
c11.012-0.092,22.195-2.005,32.736-5.137c19.279-5.728,38.742-16.504,50.15-33.532l-2.758-2.756
C93.008,268.026,92.283,268.359,91.549,268.678z"/>
<path d="M306.004,3.149c0,0-0.002-0.001-0.004-0.003c-2.006-2.005-4.725-3.128-7.555-3.128c-0.07,0-0.141,0.001-0.211,0.002
c-34.41,0.675-119.307,7.111-164.393,52.199c-20.467,20.467-27.119,31.121-41.699,54.469c-10.5,16.81-24.875,39.835-51.147,77.649
c-2.951,4.25-2.438,10.003,1.221,13.66l68.928,68.929c2.068,2.069,4.807,3.133,7.564,3.133c2.119,0,4.248-0.628,6.096-1.911
c37.828-26.278,60.844-40.65,77.648-51.146c23.346-14.579,34.002-21.233,54.473-41.702c45.166-45.168,51.557-130.009,52.205-164.39
C309.187,8.007,308.057,5.205,306.004,3.149z M226.187,133.206c-13.877,13.876-36.373,13.876-50.25,0
c-13.879-13.877-13.877-36.372,0.002-50.248c13.875-13.877,36.371-13.879,50.248-0.003
C240.06,96.831,240.062,119.331,226.187,133.206z"/>
</g>
</svg>
</div>
