If I have two partially transparent images (GIF, PNG, SVG etc.), how do I check if the non-transparent areas of the images intersect?
I'm fine with using canvas if it's necessary. The solution needs to work with all image formats that support transparency. No jQuery please.
By using the 2D context globalCompositeOperation you can greatly increase the speed of pixel pixel overlap test.
The comp operation "destination-in" will only leave pixels that are visible on the canvas and the image you draw on top of it. Thus you create a canvas, draw one image, then set the comp operation to "destination-in" then draw the second image. If any pixels are overlapping then they will have a non zero alpha. All you do then is read the pixels and if any of them are not zero you know there is an overlap.
Testing all the pixels in the overlapping area will be slow. You can get the GPU to do some math for you and scale the composite image down. There is some loss as pixels are only 8bit values. This can be overcome by reducing the image in steps and rendering the results several times. Each reduction is like calculating a mean. I scale down by 8 effectively getting the mean of 64 pixels. To stop pixels at the bottom of the range disappearing due to rounding I draw the image several times. I do it 32 time which has the effect of multiplying the alpha channel by 32.
This method can easily be modified to allow both images to be scaled, skewed and rotated without any major performance hit. You can also use it to test many images with it returning true if all images have pixels overlapping.
Pixels are small so you can get extra speed if you reduce the image size before creating the test canvas in the function. This can give a significant performance boost.
There is a flag reuseCanvas that allows you to reuse the working canvases. If you use the test function a lot (many times a second) then set the flag to true. If you only need the test every now and then then set it to false.
This method is good for large images that need occasional tests; it is not good for small images and many tests per frame (such as in games where you may need to test 100's of images). For fast (almost perfect pixel) collision tests see Radial Perimeter Test.
// Use the options to set quality of result
// Slow but perfect
var slowButPerfect = false;
// if reuseCanvas is true then the canvases are resused saving some time
const reuseCanvas = true;
// hold canvas references.
var pixCanvas;
var pixCanvas1;
// returns true if any pixels are overlapping
// img1,img2 the two images to test
// x,y location of img1
// x1,y1 location of img2
function isPixelOverlap(img1,x,y,img2,x1,y1){
var ax,aw,ay,ah,ctx,canvas,ctx1,canvas1,i,w,w1,h,h1;
w = img1.width;
h = img1.height;
w1 = img2.width;
h1 = img2.height;
// function to check if any pixels are visible
function checkPixels(context,w,h){
var imageData = new Uint32Array(context.getImageData(0,0,w,h).data.buffer);
var i = 0;
// if any pixel is not zero then there must be an overlap
while(i < imageData.length){
if(imageData[i++] !== 0){
return true;
}
}
return false;
}
// check if they overlap
if(x > x1 + w1 || x + w < x1 || y > y1 + h1 || y + h < y1){
return false; // no overlap
}
// size of overlapping area
// find left edge
ax = x < x1 ? x1 : x;
// find right edge calculate width
aw = x + w < x1 + w1 ? (x + w) - ax : (x1 + w1) - ax
// do the same for top and bottom
ay = y < y1 ? y1 : y;
ah = y + h < y1 + h1 ? (y + h) - ay : (y1 + h1) - ay
// Create a canvas to do the masking on
if(!reuseCanvas || pixCanvas === undefined){
pixCanvas = document.createElement("canvas");
}
pixCanvas.width = aw;
pixCanvas.height = ah;
ctx = pixCanvas.getContext("2d");
// draw the first image relative to the overlap area
ctx.drawImage(img1,x - ax, y - ay);
// set the composite operation to destination-in
ctx.globalCompositeOperation = "destination-in"; // this means only pixels
// will remain if both images
// are not transparent
ctx.drawImage(img2,x1 - ax, y1 - ay);
ctx.globalCompositeOperation = "source-over";
// are we using slow method???
if(slowButPerfect){
if(!reuseCanvas){ // are we keeping the canvas
pixCanvas = undefined; // no then release referance
}
return checkPixels(ctx,aw,ah);
}
// now draw over its self to amplify any pixels that have low alpha
for(var i = 0; i < 32; i++){
ctx.drawImage(pixCanvas,0,0);
}
// create a second canvas 1/8th the size but not smaller than 1 by 1
if(!reuseCanvas || pixCanvas1 === undefined){
pixCanvas1 = document.createElement("canvas");
}
ctx1 = pixCanvas1.getContext("2d");
// reduced size rw, rh
rw = pixCanvas1.width = Math.max(1,Math.floor(aw/8));
rh = pixCanvas1.height = Math.max(1,Math.floor(ah/8));
// repeat the following untill the canvas is just 64 pixels
while(rw > 8 && rh > 8){
// draw the mask image several times
for(i = 0; i < 32; i++){
ctx1.drawImage(
pixCanvas,
0,0,aw,ah,
Math.random(),
Math.random(),
rw,rh
);
}
// clear original
ctx.clearRect(0,0,aw,ah);
// set the new size
aw = rw;
ah = rh;
// draw the small copy onto original
ctx.drawImage(pixCanvas1,0,0);
// clear reduction canvas
ctx1.clearRect(0,0,pixCanvas1.width,pixCanvas1.height);
// get next size down
rw = Math.max(1,Math.floor(rw / 8));
rh = Math.max(1,Math.floor(rh / 8));
}
if(!reuseCanvas){ // are we keeping the canvas
pixCanvas = undefined; // release ref
pixCanvas1 = undefined;
}
// check for overlap
return checkPixels(ctx,aw,ah);
}
The demo lets you compare the two methods. The mean time for each test is displayed. (will display NaN if no tests done)
For the best results view the demo full page.
Use left or right mouse buttons to test for overlap. Move the splat image over the other to see overlap result. On my machine I am getting about 11ms for the slow test and 0.03ms for the quick test (using Chrome, much faster on Firefox).
I have not spent much time testing how fast I can get it to work but there is plenty of room to increase the speed by reducing the number of time the images are drawn over each other. At some point faint pixels will be lost.
// Use the options to set quality of result
// Slow but perfect
var slowButPerfect = false;
const reuseCanvas = true;
var pixCanvas;
var pixCanvas1;
// returns true if any pixels are overlapping
function isPixelOverlap(img1,x,y,w,h,img2,x1,y1,w1,h1){
var ax,aw,ay,ah,ctx,canvas,ctx1,canvas1,i;
// function to check if any pixels are visible
function checkPixels(context,w,h){
var imageData = new Uint32Array(context.getImageData(0,0,w,h).data.buffer);
var i = 0;
// if any pixel is not zero then there must be an overlap
while(i < imageData.length){
if(imageData[i++] !== 0){
return true;
}
}
return false;
}
// check if they overlap
if(x > x1 + w1 || x + w < x1 || y > y1 + h1 || y + h < y1){
return false; // no overlap
}
// size of overlapping area
// find left edge
ax = x < x1 ? x1 : x;
// find right edge calculate width
aw = x + w < x1 + w1 ? (x + w) - ax : (x1 + w1) - ax
// do the same for top and bottom
ay = y < y1 ? y1 : y;
ah = y + h < y1 + h1 ? (y + h) - ay : (y1 + h1) - ay
// Create a canvas to do the masking on
if(!reuseCanvas || pixCanvas === undefined){
pixCanvas = document.createElement("canvas");
}
pixCanvas.width = aw;
pixCanvas.height = ah;
ctx = pixCanvas.getContext("2d");
// draw the first image relative to the overlap area
ctx.drawImage(img1,x - ax, y - ay);
// set the composite operation to destination-in
ctx.globalCompositeOperation = "destination-in"; // this means only pixels
// will remain if both images
// are not transparent
ctx.drawImage(img2,x1 - ax, y1 - ay);
ctx.globalCompositeOperation = "source-over";
// are we using slow method???
if(slowButPerfect){
if(!reuseCanvas){ // are we keeping the canvas
pixCanvas = undefined; // no then release reference
}
return checkPixels(ctx,aw,ah);
}
// now draw over its self to amplify any pixels that have low alpha
for(var i = 0; i < 32; i++){
ctx.drawImage(pixCanvas,0,0);
}
// create a second canvas 1/8th the size but not smaller than 1 by 1
if(!reuseCanvas || pixCanvas1 === undefined){
pixCanvas1 = document.createElement("canvas");
}
ctx1 = pixCanvas1.getContext("2d");
// reduced size rw, rh
rw = pixCanvas1.width = Math.max(1,Math.floor(aw/8));
rh = pixCanvas1.height = Math.max(1,Math.floor(ah/8));
// repeat the following untill the canvas is just 64 pixels
while(rw > 8 && rh > 8){
// draw the mask image several times
for(i = 0; i < 32; i++){
ctx1.drawImage(
pixCanvas,
0,0,aw,ah,
Math.random(),
Math.random(),
rw,rh
);
}
// clear original
ctx.clearRect(0,0,aw,ah);
// set the new size
aw = rw;
ah = rh;
// draw the small copy onto original
ctx.drawImage(pixCanvas1,0,0);
// clear reduction canvas
ctx1.clearRect(0,0,pixCanvas1.width,pixCanvas1.height);
// get next size down
rw = Math.max(1,Math.floor(rw / 8));
rh = Math.max(1,Math.floor(rh / 8));
}
if(!reuseCanvas){ // are we keeping the canvas
pixCanvas = undefined; // release ref
pixCanvas1 = undefined;
}
// check for overlap
return checkPixels(ctx,aw,ah);
}
function rand(min,max){
if(max === undefined){
max = min;
min = 0;
}
var r = Math.random() + Math.random() + Math.random() + Math.random() + Math.random();
r += Math.random() + Math.random() + Math.random() + Math.random() + Math.random();
r /= 10;
return (max-min) * r + min;
}
function createImage(w,h){
var c = document.createElement("canvas");
c.width = w;
c.height = h;
c.ctx = c.getContext("2d");
return c;
}
function createCSSColor(h,s,l,a) {
var col = "hsla(";
col += (Math.floor(h)%360) + ",";
col += Math.floor(s) + "%,";
col += Math.floor(l) + "%,";
col += a + ")";
return col;
}
function createSplat(w,h,hue, hue2){
w = Math.floor(w);
h = Math.floor(h);
var c = createImage(w,h);
if(hue2 !== undefined) {
c.highlight = createImage(w,h);
}
var maxSize = Math.min(w,h)/6;
var pow = 5;
while(maxSize > 4 && pow > 0){
var count = Math.min(100,Math.pow(w * h,1/pow) / 2);
while(count-- > 0){
const rhue = rand(360);
const s = rand(25,75);
const l = rand(25,75);
const a = (Math.random()*0.8+0.2).toFixed(3);
const size = rand(4,maxSize);
const x = rand(size,w - size);
const y = rand(size,h - size);
c.ctx.fillStyle = createCSSColor(rhue + hue, s, l, a);
c.ctx.beginPath();
c.ctx.arc(x,y,size,0,Math.PI * 2);
c.ctx.fill();
if (hue2 !== undefined) {
c.highlight.ctx.fillStyle = createCSSColor(rhue + hue2, s, l, a);
c.highlight.ctx.beginPath();
c.highlight.ctx.arc(x,y,size,0,Math.PI * 2);
c.highlight.ctx.fill();
}
}
pow -= 1;
maxSize /= 2;
}
return c;
}
var splat1,splat2;
var slowTime = 0;
var slowCount = 0;
var notSlowTime = 0;
var notSlowCount = 0;
var onResize = function(){
ctx.font = "14px arial";
ctx.textAlign = "center";
splat1 = createSplat(rand(w/2, w), rand(h/2, h), 0, 100);
splat2 = createSplat(rand(w/2, w), rand(h/2, h), 100);
}
function display(){
ctx.clearRect(0,0,w,h)
ctx.setTransform(1.8,0,0,1.8,w/2,0);
ctx.fillText("Fast GPU assisted Pixel collision test using 2D API",0, 14)
ctx.setTransform(1,0,0,1,0,0);
ctx.fillText("Hold left mouse for Traditional collision test. Time : " + (slowTime / slowCount).toFixed(3) + "ms",w /2 , 28 + 14)
ctx.fillText("Hold right (or CTRL left) mouse for GPU assisted collision. Time: "+ (notSlowTime / notSlowCount).toFixed(3) + "ms",w /2 , 28 + 28)
if((mouse.buttonRaw & 0b101) === 0) {
ctx.drawImage(splat1, w / 2 - splat1.width / 2, h / 2 - splat1.height / 2)
ctx.drawImage(splat2, mouse.x - splat2.width / 2, mouse.y - splat2.height / 2);
} else if(mouse.buttonRaw & 0b101){
if((mouse.buttonRaw & 1) && !mouse.ctrl){
slowButPerfect = true;
}else{
slowButPerfect = false;
}
var now = performance.now();
var res = isPixelOverlap(
splat1,
w / 2 - splat1.width / 2, h / 2 - splat1.height / 2,
splat1.width, splat1.height,
splat2,
mouse.x - splat2.width / 2, mouse.y - splat2.height / 2,
splat2.width,splat2.height
)
var time = performance.now() - now;
ctx.drawImage(res ? splat1.highlight: splat1, w / 2 - splat1.width / 2, h / 2 - splat1.height / 2)
ctx.drawImage(splat2, mouse.x - splat2.width / 2, mouse.y - splat2.height / 2);
if(slowButPerfect){
slowTime += time;
slowCount += 1;
}else{
notSlowTime = time;
notSlowCount += 1;
}
if(res){
ctx.setTransform(2,0,0,2,mouse.x,mouse.y);
ctx.fillText("Overlap detected",0,0)
ctx.setTransform(1,0,0,1,0,0);
}
//mouse.buttonRaw = 0;
}
}
// Boilerplate code below
const RESIZE_DEBOUNCE_TIME = 100;
var w, h, cw, ch, canvas, ctx, mouse, createCanvas, resizeCanvas, setGlobals, globalTime = 0, resizeCount = 0;
var firstRun = true;
createCanvas = function () {
var c,
cs;
cs = (c = document.createElement("canvas")).style;
cs.position = "absolute";
cs.top = cs.left = "0px";
cs.zIndex = 1000;
document.body.appendChild(c);
return c;
}
resizeCanvas = function () {
if (canvas === undefined) {
canvas = createCanvas();
}
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
ctx = canvas.getContext("2d");
if (typeof setGlobals === "function") {
setGlobals();
}
if (typeof onResize === "function") {
if(firstRun){
onResize();
firstRun = false;
}else{
resizeCount += 1;
setTimeout(debounceResize, RESIZE_DEBOUNCE_TIME);
}
}
}
function debounceResize() {
resizeCount -= 1;
if (resizeCount <= 0) {
onResize();
}
}
setGlobals = function () {
cw = (w = canvas.width) / 2;
ch = (h = canvas.height) / 2;
}
mouse = (function () {
function preventDefault(e) {
e.preventDefault();
}
var mouse = {
x : 0,
y : 0,
buttonRaw : 0,
over : false,
bm : [1, 2, 4, 6, 5, 3],
active : false,
bounds : null,
mouseEvents : "mousemove,mousedown,mouseup,mouseout,mouseover".split(",")
};
var m = mouse;
function mouseMove(e) {
var t = e.type;
m.bounds = m.element.getBoundingClientRect();
m.x = e.pageX - m.bounds.left;
m.y = e.pageY - m.bounds.top;
m.alt = e.altKey;
m.shift = e.shiftKey;
m.ctrl = e.ctrlKey;
if (t === "mousedown") {
m.buttonRaw |= m.bm[e.which - 1];
} else if (t === "mouseup") {
m.buttonRaw &= m.bm[e.which + 2];
} else if (t === "mouseout") {
m.buttonRaw = 0;
m.over = false;
} else if (t === "mouseover") {
m.over = true;
}
e.preventDefault();
}
m.start = function (element) {
if (m.element !== undefined) {
m.removeMouse();
}
m.element = element === undefined ? document : element;
m.mouseEvents.forEach(n => {
m.element.addEventListener(n, mouseMove);
});
m.element.addEventListener("contextmenu", preventDefault, false);
m.active = true;
}
m.remove = function () {
if (m.element !== undefined) {
m.mouseEvents.forEach(n => {
m.element.removeEventListener(n, mouseMove);
});
m.element = undefined;
m.active = false;
}
}
return mouse;
})();
resizeCanvas();
mouse.start(canvas, true);
window.addEventListener("resize", resizeCanvas);
function update1(timer) { // Main update loop
if(ctx === undefined){
return;
}
globalTime = timer;
display(); // call demo code
requestAnimationFrame(update1);
}
requestAnimationFrame(update1);