多边形相交失败,碰撞“大小”太大了
好的,所以我正在尝试制作一个简单的小行星克隆。除了碰撞检测之外,一切正常。
我有两个不同的版本,第一个使用 java.awt.geom.Area:
// polygon is a java.awt.Polygon and p is the other one
final Area intersect = new Area();
intersect.add(new Area(polygon));
intersect.intersect(new Area(p.polygon));
return !intersect.isEmpty();
这就像一个魅力......如果你不关心仅 120 个小行星的 40% CPU :(
所以我在网上搜索了著名的分离轴定理,因为我不太擅长数学,所以我从 中获取了实现这里并将其转换为适合我的Java需求:
public double dotProduct(double x, double y, double dx, double dy) {
return x * dx + y * dy;
}
public double IntervalDistance(double minA, double maxA, double minB,
double maxB) {
if (minA < minB) {
return minB - maxA;
} else {
return minA - maxB;
}
}
public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) {
double dotProduct = dotProduct(ax, ay, x[0], y[0]);
double min = dotProduct;
double max = dotProduct;
for (int i = 0; i < p; i++) {
dotProduct = dotProduct(x[i], y[i], ax, ay);
if (dotProduct < min) {
min = dotProduct;
} else if (dotProduct > max) {
max = dotProduct;
}
}
return new double[] { min, max };
}
public boolean PolygonCollision(Asteroid ast) {
int edgeCountA = points;
int edgeCountB = ast.points;
double edgeX;
double edgeY;
for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
if (edgeIndex < edgeCountA) {
edgeX = xp[edgeIndex] * 0.9;
edgeY = yp[edgeIndex] * 0.9;
} else {
edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9;
edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9;
}
final double x = -edgeY;
final double y = edgeX;
final double len = Math.sqrt(x * x + y * y);
final double axisX = x / len;
final double axisY = y / len;
final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp,
yp);
final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points,
ast.xp, ast.yp);
if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) {
return false;
}
}
return true;
}
它有效......实际上,使用这段代码时,小行星的“碰撞外壳”似乎太大了,它就像小行星大小的1.2倍。 。我不知道为什么,
这是两张图片进行比较:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png
如您所愿看,图一中的小行星比图二中使用 SAT 代码的小行星密度大得多。
那么有什么想法吗?或者有谁知道我可以使用的具有交叉测试功能的 Java 多边形实现?
OK, so I'm trying to make a simple asteroids clone. Everything works fine, except for the collision detection.
I have two different versions, the first one uses java.awt.geom.Area:
// polygon is a java.awt.Polygon and p is the other one
final Area intersect = new Area();
intersect.add(new Area(polygon));
intersect.intersect(new Area(p.polygon));
return !intersect.isEmpty();
This works like a charm... if you don't care about 40% CPU for only 120 asteroids :(
So I searched the net for the famous separating axis theorem, since I'm not thaaaaaat good a the math I took the implementation from here and converted it to fit my Java needs:
public double dotProduct(double x, double y, double dx, double dy) {
return x * dx + y * dy;
}
public double IntervalDistance(double minA, double maxA, double minB,
double maxB) {
if (minA < minB) {
return minB - maxA;
} else {
return minA - maxB;
}
}
public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) {
double dotProduct = dotProduct(ax, ay, x[0], y[0]);
double min = dotProduct;
double max = dotProduct;
for (int i = 0; i < p; i++) {
dotProduct = dotProduct(x[i], y[i], ax, ay);
if (dotProduct < min) {
min = dotProduct;
} else if (dotProduct > max) {
max = dotProduct;
}
}
return new double[] { min, max };
}
public boolean PolygonCollision(Asteroid ast) {
int edgeCountA = points;
int edgeCountB = ast.points;
double edgeX;
double edgeY;
for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
if (edgeIndex < edgeCountA) {
edgeX = xp[edgeIndex] * 0.9;
edgeY = yp[edgeIndex] * 0.9;
} else {
edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9;
edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9;
}
final double x = -edgeY;
final double y = edgeX;
final double len = Math.sqrt(x * x + y * y);
final double axisX = x / len;
final double axisY = y / len;
final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp,
yp);
final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points,
ast.xp, ast.yp);
if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) {
return false;
}
}
return true;
}
It works... kinda. Actually it seems that the "collision hull" of the asteroids is too big when using this code, it's like 1.2 times the size of the asteroid. And I don't have any clue why.
Here are two pictures for comparison:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png
As you can hopefully see, the asteroids in picture one are much denser than the ones in picture 2 where is use the SAT code.
So any ideas? Or does anyone knows a Polygon implementation for Java featuring intersection tests that I could use?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
看起来您的第二个结果是进行碰撞检测,就好像多边形是圆形,其半径设置为多边形距中心最远的点。我见过的大多数碰撞检测工具都会创建一个简单的边界框(圆形或矩形),多边形可以放入其中。仅当两个边界框相交(计算更简单)时,您才继续进行更详细的检测。也许适当的算法仅用作边界框计算器?
编辑:
另外,来自维基百科
图像中的许多小行星都有凹面。
It looks like your second result is doing collision detection as if the polygons were circles with their radius set to the most distant point of the polygon from the center. Most collision detection stuff I've seen creates a simple bounding box (either a circle or rectangle) into which the polygon can fit. Only if two bounding boxes intersect (a far simpler calculation) do you continue on to the more detailed detection. Perhaps the appropriated algorithm is only intended as a bounding box calculator?
EDIT:
Also, from wikipedia
Many of the asteroids in your image have concave surfaces.