How to detect collision between object made of bezier curves and a circle?

Question

So I've wrote a microbe animation. It's all cool, but I think that it would be even better, if the microbe would be able to eat diatoms, and to destroy bubbles.

The issue is that the microbe is made of bezier curves. I have no idea how to check collision between object made of bezier curves, and a circle in a reasonable way. The only thing that comes to my mind, is to paint the microbe shape and bubbles a hidden canvas, and then check if they paint to the same pixels. But that would cause big performance issues IMHO.

Code: https://codepen.io/michaelKurowski/pen/opWeKY

class Cell is the cell, while class CellWallNode is a node of bezier curve, in case if somebody needs to look up the implementation.

The bubbles and diatoms can be easily simplified to circles.

Chasse

but that would cause a big performance issue -> a modern gpu draws at 60fps... – Goudy

The issue is that 2D canvas API calls are very slow (as for animation drawing standards), so I'd like to avoid calling it whenever it's a possibility. – Chasse

maybe related thread – Goudy

Use an approximation by dividing the bezier into line segments and start with a bounding circle test then check the line segments. Line segments can be a projection from cell center so that the object being tested direction from the cell is used to index into the segment map. A test can then be made very quickly with many simple collision objects, and you only need to update the line segments once a frame – Jujitsu

Answer 1

Solution to bounds testing object defined by beziers

Below is an example solution to finding if a circle is inside an object defined by a center point and a set of beziers defining the perimeter.

The solution has only been tested for non intersecting cubic beziers. Also will not work if there are more than two intercepts between the object being tested and the center of the cell. However all you need to solve for the more complex bounds is there in the code.

The method

1. Define a center point to test from as a 2D point
2. Define the test point as a 2D point
3. Define a line from the center to the test point
4. For each bezier
5. Translate bezier so first point is at start of line
6. Rotate the bezier such that the line is aligned to the x axis
7. Solve the bezier polynomials to find the roots (location of x axis intercepts)
8. Use the roots to find position on bezier curve of line intercept.
9. Use the closest intercept to the point to find distance from center to perimeter.
10. If perimeter distance is greater than test point distance plus radius then inside.

Notes

The test is to a point along a line to the center not to a circle which would be a area defined by a triangle. As long as the circle radius is small compared to the size of the beziers the approximation works well.

Not sure if you are using cubic or quadratic beziers so the solution covers both cubic and quadratic beziers.

Example

The snippet creates a set of beziers (cubic) around a center point. the object theBlob holds the animated beziers. The function testBlob tests the mouse position and returns true if inside theBlob. The object bezHelper contains all the functionality needed to solve the problem.

The cubic root solver was derived from github intersections cube root solver.

const bezHelper = (()=>{
    // creates a 2D point
    const P2 = (x=0, y= x === 0 ? 0 : x.y + (x = x.x, 0)) => ({x, y});
    const setP2As = (p,pFrom) => (p.x = pFrom.x, p.y = pFrom.y, p);
    // To prevent heap thrashing close over some pre defined 2D points
    const v1 = P2();
    const v2 = P2();
    const v3 = P2();
    const v4 = P2();
    var u,u1,u2;
    
    // solves quadratic for bezier 2 returns first root
    function solveBezier2(A, B, C){ 
        // solve the 2nd order bezier equation.
        // There can be 2 roots, u,u1 hold the results;
        // 2nd order function a+2(-a+b)x+(a-2b+c)x^2
        a = (A - 2 * B + C);
        b = 2 * ( - A + B);
        c = A;
        a1 = 2 * a;
        c = b * b - 4 * a * c;
        if(c < 0){ 
            u = Infinity;       
            u1 = Infinity;       
            return u;
        }else{
            b1 = Math.sqrt(c);
        }
        u = (-b + b1) / a1;
        u1 = (-b - b1) / a1;
        return u;
    
    }
    // solves cubic for bezier 3 returns first root
    function solveBezier3(A, B, C, D){  
        // There can be 3 roots, u,u1,u2 hold the results;
        // Solves 3rd order a+(-2a+3b)t+(2a-6b+3c)t^2+(-a+3b-3c+d)t^3 Cardano method for finding roots
        // this function was derived from http://pomax.github.io/bezierinfo/#intersections cube root solver
        // Also see https://en.wikipedia.org/wiki/Cubic_function#Cardano.27s_method

        function crt(v) {
          if(v<0) return -Math.pow(-v,1/3);
          return Math.pow(v,1/3);
        }                
        function sqrt(v) {
          if(v<0) return -Math.sqrt(-v);
          return Math.sqrt(v);
        }        
        var a, b, c, d, p, p3, q, q2, discriminant, U, v1, r, t, mp3, cosphi,phi, t1, sd;
        u2 = u1 = u = -Infinity;
        d = (-A + 3 * B - 3 * C + D);
        a = (3 * A - 6 * B + 3 * C) / d;
        b = (-3 * A + 3 * B) / d;
        c = A / d;
        p = (3 * b - a * a) / 3;
        p3 = p / 3;
        q = (2 * a * a * a - 9 * a * b + 27 * c) / 27;
        q2 = q / 2;
        a /= 3;
        discriminant = q2 * q2 + p3 * p3 * p3;
        if (discriminant < 0) {
            mp3 = -p / 3;
            r = sqrt(mp3 * mp3 * mp3);
            t = -q / (2 * r);
            cosphi = t < -1 ? -1 : t > 1 ? 1 : t;
            phi = Math.acos(cosphi);
            t1 = 2 * crt(r);
            u = t1 * Math.cos(phi / 3) - a;
            u1 = t1 * Math.cos((phi + 2 * Math.PI) / 3) - a;
            u2 = t1 * Math.cos((phi + 4 * Math.PI) / 3) - a;
            return u;
        }
        if(discriminant === 0) {
            U = q2 < 0 ? crt(-q2) : -crt(q2);
            u = 2 * U - a;           
            u1 = -U - a;            
            return u;
        }                
        sd = sqrt(discriminant);
        u = crt(sd - q2) - crt(sd + q2) - a; 
        return u;      
    }    
    
    
    
    
    // get a point on the bezier at pos ( from 0 to 1 values outside this range will be outside the bezier)
    // p1, p2 are end points and cp1, cp2 are control points.
    // ret is the resulting point. If given it is set to the result, if not given a new point is created
    function getPositionOnBez(pos,p1,p2,cp1,cp2,ret = P2()){
        if(pos === 0){
            ret.x = p1.x;
            ret.y = p1.y;
            return ret;
        }else
        if(pos === 1){
            ret.x = p2.x;
            ret.y = p2.y;
            return ret;
        }                
        v1.x = p1.x;
        v1.y = p1.y;
        var c = pos;
        if(cp2 === undefined){
            v2.x = cp1.x;
            v2.y = cp1.y;
            v1.x += (v2.x - v1.x) * c;
            v1.y += (v2.y - v1.y) * c;
            v2.x += (p2.x - v2.x) * c;
            v2.y += (p2.y - v2.y) * c;
            ret.x = v1.x + (v2.x - v1.x) * c;
            ret.y = v1.y + (v2.y - v1.y) * c;
            return ret;
        }
        v2.x = cp1.x;
        v2.y = cp1.y;
        v3.x = cp2.x;
        v3.y = cp2.y;
        v1.x += (v2.x - v1.x) * c;
        v1.y += (v2.y - v1.y) * c;
        v2.x += (v3.x - v2.x) * c;
        v2.y += (v3.y - v2.y) * c;
        v3.x += (p2.x - v3.x) * c;
        v3.y += (p2.y - v3.y) * c;
        v1.x += (v2.x - v1.x) * c;
        v1.y += (v2.y - v1.y) * c;
        v2.x += (v3.x - v2.x) * c;
        v2.y += (v3.y - v2.y) * c;
        ret.x = v1.x + (v2.x - v1.x) * c;
        ret.y = v1.y + (v2.y - v1.y) * c;
        return ret;  
    }
    const cubicBez = 0;
    const quadraticBez = 1;
    const none = 2;
    var type = none;
    
    // working bezier
    const p1 = P2();
    const p2 = P2();
    const cp1 = P2();
    const cp2 = P2();
    // rotated bezier
    const rp1 = P2();
    const rp2 = P2();
    const rcp1 = P2();
    const rcp2 = P2();
    // translate and rotate bezier
    function transformBez(pos,rot){
        const ax = Math.cos(rot);
        const ay = Math.sin(rot); 
        var x = p1.x - pos.x;
        var y = p1.y - pos.y;
        rp1.x = x * ax - y * ay;
        rp1.y = x * ay + y * ax;
        x = p2.x - pos.x;
        y = p2.y - pos.y;
        rp2.x = x * ax - y * ay;
        rp2.y = x * ay + y * ax;
        x = cp1.x - pos.x;
        y = cp1.y - pos.y;
        rcp1.x = x * ax - y * ay;
        rcp1.y = x * ay + y * ax;       
        if(type === cubicBez){
            x = cp2.x - pos.x;
            y = cp2.y - pos.y;
            rcp2.x = x * ax - y * ay;
            rcp2.y = x * ay + y * ax;       
        }
    }
    function getPosition2(pos,ret){
        return getPositionOnBez(pos,p1,p2,cp1,undefined,ret);
    }
    function getPosition3(pos,ret){
        return getPositionOnBez(pos,p1,p2,cp1,cp2,ret);
    }
    const API = {
        getPosOnQBez(pos,p1,cp1,p2,ret){
            return getPositionOnBez(pos,p1,p2,cp1,undefined,ret);
        },
        getPosOnCBez(pos,p1,cp1,cp2,p2,ret){
            return getPositionOnBez(pos,p1,p2,cp1,cp2,ret);
        },
        set bezQ(points){
            setP2As(p1, points[0]);
            setP2As(cp1, points[1]);
            setP2As(p2, points[2]);
            type = quadraticBez;
        },
        set bezC(points){
            setP2As(p1, points[0]);
            setP2As(cp1, points[1]);
            setP2As(cp2, points[2]);
            setP2As(p2, points[3]);
            type = cubicBez;
        },
        isInside(center, testPoint, pointRadius){
            drawLine(testPoint , center);
            v1.x = (testPoint.x - center.x);
            v1.y = (testPoint.y - center.y);
            const pointDist = Math.sqrt(v1.x * v1.x + v1.y * v1.y)
            const dir = -Math.atan2(v1.y,v1.x);
            transformBez(center,dir);
            if(type === cubicBez){
                solveBezier3(rp1.y, rcp1.y, rcp2.y, rp2.y); 
                if (u < 0 || u > 1)  { u = u1 }
                if (u < 0 || u > 1)  { u = u2 }
                if (u < 0 || u > 1)  { return }
                getPosition3(u, v4);
            }else{
                solveBezier2(rp1.y, rcp1.y, rp2.y);   
                if (u < 0 || u > 1)  { u = u1 }
                if (u < 0 || u > 1)  { return }
                getPosition2(u, v4);
                
            }
            drawCircle(v4);
            const dist = Math.sqrt((v4.x - center.x) ** 2 + (v4.y - center.y) ** 2);
            const dist1 = Math.sqrt((v4.x - testPoint.x) ** 2 + (v4.y - testPoint.y) ** 2); 
            return dist1 < dist && dist > pointDist - pointRadius;
        }
    }
                
                
                
    return API;        
})();                














const ctx = canvas.getContext("2d");
const m  = {x : 0, y : 0};
document.addEventListener("mousemove",e=>{
	var b = canvas.getBoundingClientRect();
	m.x = e.pageX - b.left - scrollX - 2;
	m.y = e.pageY - b.top - scrollY - 2;
});   
function drawCircle(p,r = 5,col = "black"){
    ctx.beginPath();
    ctx.strokeStyle = col;
    ctx.arc(p.x,p.y,r,0,Math.PI*2)
    ctx.stroke();
}
function drawLine(p1,p2,r = 5,col = "black"){
    ctx.beginPath();
    ctx.strokeStyle = col;
    ctx.lineTo(p1.x,p1.y);
    ctx.lineTo(p2.x,p2.y);
    ctx.stroke();
}

const w = 400;
const h = 400;
const diag = Math.sqrt(w * w + h * h);
// creates a 2D point
const P2 = (x=0, y= x === 0 ? 0 : x.y + (x = x.x, 0)) => ({x, y});
const setP2As = (p,pFrom) => (p.x = pFrom.x, p.y = pFrom.y, p);
// random int and double
const randI = (min, max = min + (min = 0)) => (Math.random()*(max - min) + min) | 0;
const rand = (min = 1, max = min + (min = 0)) => Math.random() * (max - min) + min;

const theBlobSet = [];
const theBlob = [];
function createCubicBlob(segs){
  const step = Math.PI / segs;
  for(var i = 0; i < Math.PI * 2; i += step){
    const dist = rand(diag * (1/6), diag * (1/5));
    const ang = i + rand(-step * 0.2,step * 0.2);
    
    const p = P2(
      w / 2 + Math.cos(ang) * dist,
      h / 2 + Math.sin(ang) * dist
    );  
    theBlobSet.push(p);
    theBlob.push(P2(p));
  }
  theBlobSet[theBlobSet.length -1] = theBlobSet[0];
  theBlob[theBlobSet.length -1] = theBlob[0];
}
createCubicBlob(8);
function animateTheBlob(time){
  for(var i = 0; i < theBlobSet.length-1; i++){
    const ang = Math.sin(time + i) * 6;
    theBlob[i].x = theBlobSet[i].x + Math.cos(ang) * diag * 0.04;
    theBlob[i].y = theBlobSet[i].y + Math.sin(ang) * diag * 0.04;
  }
}

function drawTheBlob(){
  ctx.strokeStyle = "black";
  ctx.lineWidth = 3;
  ctx.beginPath();
  var i = 0;
  ctx.moveTo(theBlob[i].x,theBlob[i++].y);
  while(i < theBlob.length){
    ctx.bezierCurveTo(
      theBlob[i].x,theBlob[i++].y,
      theBlob[i].x,theBlob[i++].y,
      theBlob[i].x,theBlob[i++].y
    );
  }
  ctx.stroke();
}
var center = P2(w/2,h/2);
function testBlob(){
  var i = 0;
  while(i < theBlob.length-3){
    bezHelper.bezC = [theBlob[i++], theBlob[i++], theBlob[i++], theBlob[i]];
    if(bezHelper.isInside(center,m,6)){
      return true;
    }
  }
  return false;
}


// main update function
function update(timer){
    ctx.clearRect(0,0,w,h);
    animateTheBlob(timer/1000)
    drawTheBlob();
    
    if(testBlob()){
        ctx.strokeStyle = "red";
    }else{
       ctx.strokeStyle = "black";
    }
    ctx.beginPath();
    ctx.arc(m.x,m.y,5,0,Math.PI*2)
    ctx.stroke();
    requestAnimationFrame(update);
}
requestAnimationFrame(update);

canvas { border : 2px solid black; }

<canvas id="canvas" width = "400" height = "400"></canvas>

Jujitsu

+1 An alternative could be to use the curve/curve intersection algorithm and, if necessary, convert the circle to a bezier (which could possibly be optimized knowing one of the curves is a circle). – Blenny

Wow, this is an answer – Chasse

Answer 2

I had created an animation of bubbles in which al the circle will expand which are 50px neer to the mouse. so here is the trick. you can just simply change mouseX,mouseY with your microbe's X and Y coordinates and 50 to the radius of your microbe. And when my bubbles get bigger, so there you can destroy you air bubbles. here is the link to my Animation. https://ankittorenzo.github.io/canvasAnimations/Elements/Bubbles/

here is the link to my GitHub Code. https://github.com/AnkitTorenzo/canvasAnimations/blob/master/Elements/Bubbles/js/main.js

Let Me Know if you have any problem.

• This does not answer the question at all. This is code for checking how far a point is from a circle. This is not code for checking how far a point is from a bezier curve, as requested. Indeed this has nothing at all to do with calculating collisions between bezier curves except for a terrible brute force approach where you just go point-by-point on the bezier curve checking each distance. pitiful answer!

Ref

The difference between my microbe and your bubbles is that a microbe can't be simplified as an object with a radius as it have a very irregular shape. – Chasse

yes, that is correct. from what your microbe made of? – Ref

you have that spikes at the parameters of your microbe. So here you can just use a loop and check that the bubble is neer to any of the spike's x,y and then you can simply remove the bubble . – Ref

Correct me if I'm wrong: You suggest to qunatize my microbe into a group of circles, and just change their size together with microbe's movement, and use them as hitboxes? I think that it would cause weird collision artifacts. – Chasse

imgur.com/a/3N7vR no I'm telling that you have those legs or some sort of spikes as I shown in above picture of yours so that you can check their x and y position and if the air bubble anywhere neer to them you can pop them. – Ref

Oh, it's just being created by canvas API. I've just changed a normal line, into dashed one. Those are not real objects. – Chasse

what does the CellWallNodes for? what are they. – Ref