Line and bitmap collision detection

Question

I am trying to implement an efficient collision detection between a line joining two points and a bitmap mask.

Example:

bitmap and two points

Currently I am using Bresenham's line drawing algorithm to draw each pixel of the line between the two points and comparing that pixel with the bitmap (If the pixel is black return true else continue drawing the line).

collision(x0,y0,x1,y1) {
 let dx = Math.abs(x1 - x0),
 dy = Math.abs(y1 - y0),
 sx = (x0 < x1) ? 1 : -1,
 sy = (y0 < y1) ? 1 : -1,
 err = dx - dy,
 e2
 // loop through line drawing
 while (!((x0 == x1) && (y0 == y1))) {
 e2 = err << 1;
 // check line point x,y against bitmap
 if (bitmap[x0][y0] == 1) {
 return 1;
 }
 if (e2 > -dy) {
 err -= dy;
 x0 += sx;
 }
 if (e2 < dx) {
 err += dx;
 y0 += sy;
 }
 }
 // If looped through whole line and not returned collision return false
 return 0
}

Is this a good/efficient approach? Or is there a set method or better approach for this problem?

Thanks in advance.

• Regis Portalez: You might want to have a look at plucker coordinates to implement bresenham’s algorithm without if. This is quite an improvement since branch prediction can’t work well on that code.

Answer 1

Performance review

Your code.

You have a few inefficiencies. When implementing the same function many times with many iterations within the function, reducing the number of steps will provide worth while performance gains.

Some suggestions.

Use === rather than == as it is a little quicker

Change the sign of dy, that means that the test if(e2 > -dy) can be changed to if(e2 > dy) saving the need to negate dy each step.

Change the lines

 // Change
 dy = Math.abs(y1 - y0)
 // to 
 dy = -Math.abs(y1 - y0)
 // Change
 err = dx - dy;
 // to
 err = dx + dy
 // Change
 if (e2 > -dy) {
 err -= dy;
 x0 += sx;
 }
 // to
 if (e2 > dy) { // removes the - operation
 err += dy; 
 x0 += sx;
 }

Remove the double array index and use a column reference for the bitmap

// just before the loop
var column = bitmap[x0];
// then in the loop you only need to index the row
if (column[y0] === 1) {
 return 1;
}
if (e2 > dy) {
 err += dy;
 x0 += sx;
 column = bitmap[x0]; // and update the column only when x0 changes.
}

Not a performance thing, just a style note. You have left out the ; after the return 0 and the locals declaration e2.

Better yet

You could also flatten the bitmap array and use an index rather than a coordinate. You change the y step to a modulo size. This reduces the number of tests and eliminates the need to index into a 2D array.

// using bitmap as a flat array with width as the pixel width
// Assuming coords are ints
function collision(x0, y0, x1, y1, width) {
 const dx = Math.abs(x1 - x0);
 const dy = -Math.abs(y1 - y0); 
 const sx = x0 < x1 ? 1 : -1;
 const sy = y0 < y1 ? width : -width;
 const endIndex = x1 + y1 * width;
 var e2, err = dx + dy;
 var index = x0 + y0 * width;
 
 // loop through line drawing
 while (index !== endIndex) {
 if (bitmap[index] === 1) { return 1 }
 e2 = err << 1;
 if (e2 > dy) {
 err += dy;
 index += sx;
 }
 if (e2 < dx) {
 err += dx;
 index += sy;
 }
 }
 return 0;
}

Peformance

The function is out of context so performance improvements can not be suggested.

As a random line an improvement would be to step over a quad tree. But this would be a very complex bit of code and would depend on the content of the bitmap and how many pixels you are sampling. It would make major improvements when the ratio of "on" pixels is low and clumped, but poor as the ratio of "on" pixels approaches 50% and the distribution is non clumpy.

The are many other solutions but they all depend on what the line is looking for, how one line is related to the rest, and the distribution and content of the bitmap.