javascript - How to detect collision between object made of bezier curves and a circle? - Stack Overflow

admin管理员组

文章数量:1292300

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 es 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:

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.

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 es 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.

• javascript
• performance
• html5-canvas
• collision-detection
• game-physics

Share Improve this question Follow edited Jun 20, 2020 at 9:12 CommunityBot 111 silver badge asked Dec 30, 2017 at 13:35 Michael KurowskiMichael Kurowski 19011 silver badge88 bronze badges 4

• but that would cause a big performance issue -> a modern gpu draws at 60fps... – Jonas Wilms Commented Dec 30, 2017 at 13:56
• 2 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. – Michael Kurowski Commented Dec 30, 2017 at 13:59
• maybe related thread – Jonas Wilms Commented Dec 30, 2017 at 14:02
• 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 – Blindman67 Commented Dec 30, 2017 at 14:46

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 11

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 plex 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 pared 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/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>

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./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!

本文标签： javascriptHow to detect collision between object made of bezier curves and a circleStack Overflow