0

コードにかなり厳密に従って、 Randy Gaul の C++ Impulse Engineに基づいて円と多角形の間の衝突検出を実装しようとしましたが、アルゴリズムは決して true を返しません。

これがJSFiddleです。(便宜上、本文は HTML5 Canvas API を使用してレンダリングされます)

コードのスニペット (衝突検出のみ):

const circPoly = (a, b) => {
  let data = {},
    center = a.pos;
  data.contacts = [];
  center = b.mat.clone().trans().mult(center.clone().sub(b.pos));
  let sep = -Number.MAX_VALUE,
    faceNorm = 0;
  for (let i = 0; i < b.verts2.length; ++i) {
    let sep2 = b.norms[i].dot(center.clone().sub(b.verts2[i]));
    if (sep2 > a.radius) return data;
    if (sep2 > sep) { sep = sep2; faceNorm = i; }
  }
  let v1 = b.verts2[faceNorm],
    v2 = b.verts2[faceNorm + 1 < b.verts2.length ? faceNorm + 1 : 0];
  if (sep < 0.0001) {
    data.depth = a.radius;
    data.norm = b.mat.clone().mult(b.norms[faceNorm]).neg();
    data.contacts[0] = data.norm.clone().vmult(a.pos.clone().sadd(a.radius));
    return data;
  }
  let dot1 = center.clone().sub(v1).dot(v2.clone().sub(v1)),
    dot2 = center.clone().sub(v2).dot(v1.clone().sub(v2));
  data.depth = a.radius - sep;
  if (dot1 <= 0) {
    if (center.dist2(v1) > a.radius * a.radius) return data;
    let norm = v1.clone().sub(center);
    norm = b.mat.clone().mult(norm);
    norm.norm();
    data.norm = norm;
    v1 = b.mat.clone().mult(v1.clone().add(b.pos));
    data.contacts[0] = v1;
  } else if (dot2 <= 0) {
    if (center.dist2(v2) > a.radius * a.radius) return data;
    let norm = v2.clone().sub(center);
    norm = b.mat.clone().mult(norm);
    norm.norm();
    data.norm = norm;
    v2 = b.mat.clone().mult(v2.clone().add(b.pos));
    data.contacts[0] = v2;
  } else {
    let norm = b.norms[faceNorm];
    if (center.clone().sub(v1).dot(norm) > a.radius) return data;
    norm = b.mat.clone().mult(norm);
    data.norm = norm.clone().neg();
    data.contacts[0] = data.norm.clone().vmult(a.pos.clone().sadd(a.radius));
  }
  return data;
};

b.verts2は、現実世界の座標でのポリゴンの頂点を指すことに注意してください。

Vector クラスに問題がないことはわかっていますが、変換行列の経験があまりないため、そのクラスがこれらのエラーの原因である可能性がありますが、そのコードはほぼ完全にから派生しています。 Impulse Engine も同様に動作するはずです。前述のように、衝突が実際に発生した場合でも、アルゴリズムは常に false を返します。ここで何が間違っていますか？初期のリターンを取り出してみましたが、負の座標を持つ接触点などの奇妙な結果が返されるだけで、明らかに正しくありません。

編集: ベクトル クラスの垂直関数をインパルス エンジンと同じように動作するように変更しました (どちらの方法も正しいですが、一方は時計回りでもう一方は反時計回りだと思います。反時計回りを反映するように頂点も変更しました)。残念ながら、それでもテストに失敗します。

https://jsfiddle.net/khanfused/tv359kgL/4/

4

1 に答える 1

2

多くの問題があり、複雑すぎるように見えるため、あなたが何をしようとしているのか本当にわかりません。たとえば、なぜ行列にはtrans???があるのですか? そして、なぜ変換の座標系として Y アップ スクリーンを使用しているのですか ??? （修辞的な）

最初のループで。

  • 1 つ目は、各頂点の法線ベクトルの距離をテストしていることです。頂点の位置をテストする必要があります。
  • また、距離vec.dotの二乗を返す関数を使用して距離を求めています。ただし、半径をテストする場合は、テストする必要がありますif(sep2 < radius * radius)
  • そして、あなたは間違った方法で比較を行っており、半径の2乗より小さいかどうかをテストする必要があります（大きくない）
  • data.contacts次に、半径内の頂点を検出すると、データ オブジェクトを返しますが、円の内側で見つかった頂点を配列に配置するのを忘れます。
  • 最も遠い vect のインデックスを保持する意図が何であるかはわかりませんが、関数の残りの部分は私にはまったく意味がありません???? :(そして私はそれを理解しようとしました。

あなたがする必要があるのは、

ポリゴン上のいずれかの頂点が半径よりも近いかどうかを確認します。そうであれば、インターセプトがあります (または完全に内側にあります)。

次に、各線分の距離を確認する必要があります

切片が必要ない場合は次のように（または切片が必要な場合はそれ以下）、どちらか一方のみを使用して、各線分に対して実行できます。

// circle is a point {x:?,y:?}
// radius = is the you know what
// p1,p2 are the start and end points of a line
        checkLineCircle = function(circle,radius,p1,p2){
            var v1 = {};
            var v2 = {};
            var v3 = {};
            var u;
            // get dist to end of line
            v2.x = circle.x - p1.x;
            v2.y = circle.y - p1.y;
            // check if end points are inside the circle
            if( Math.min(
                    Math.hypot(p2.x - circle.x, p2.y - circle.y),
                    Math.hypot(v2.x, v2.y)
                ) <= radius){
                return true;
            }
            // get the line as a vector
            v1.x = p2.x - p1.x;
            v1.y = p2.y - p1.y;
            // get the unit distance of the closest point on the line
            u = (v2.x * v1.x + v2.y * v1.y)/(v1.y * v1.y + v1.x * v1.x);
            // is this on the line segment
            if(u >= 0 && u <= 1){
                v3.x = v1.x * u;  // get the point on the line segment
                v3.y = v1.y * u;
                // get the distance to that point and return true or false depending on the 
                // it being inside the circle
                return (Math.hypot(v3.y - v2.y, v3.x - v2.x) <= radius);
            }
            return false; // no intercept
      }

時間を節約するには、ポリゴン上の各ポイントを変換するのではなく、円の中心をポリゴン ローカルに変換します。

交点が必要な場合は、次の関数を使用します

// p1,p2 are the start and end points of a line
 // returns an array empty if no points found or one or two points depending on the number of intercepts found
 // If two points found the first point in the array is the point closest to the line start (p1)
 function circleLineIntercept(circle,radius,p1,p2){
        var v1 = {};
        var v2 = {};
        var ret = [];
        var u1,u2,b,c,d;
        // line as vector
        v1.x = p2.x - p1.x;
        v1.y = p2.y - p1.y;
        // vector to circle center
        v2.x = p1.x - circle.x;
        v2.y = p1.y - circle.y;
        // dot of line and circle
        b = (v1.x * v2.x + v1.y * v2.y) * -2;
        // length of line squared * 2
        c = 2 * (v1.x * v1.x + v1.y * v1.y);
        // some math to solve the two triangles made by the intercept points, the circle center and the perpendicular line to the line.
        d = Math.sqrt(b * b - 2 * c * (v2.x * v2.x + v2.y * v2.y - radius * radius));
        // will give a NaN if no solution
        if(isNaN(d)){ // no intercept
            return ret;
        }
        // get the unit distance of each intercept to the line
        u1 = (b - d) / c;
        u2 = (b + d) / c;

        // check the intercept is on the line segment
        if(u1 <= 1 && u1 >= 0){  
            ret.push({x:line.p1.x + v1.x * u1, y : line.p1.y + v1.y * u1 });
        }
        // check the intercept is on the line segment
        if(u2 <= 1 && u2 >= 0){  
            ret.push({x:line.p1.x + v1.x * u2, y : line.p1.y + v1.y * u2});
        }
        return ret;
    }

ポリゴンの反復処理はあなたに任せます。

于 2016-06-11T00:02:12.647 に答える