论坛风格切换切换到宽版
  • 14208阅读
  • 44回复

如何判断椭圆与圆相交?激光弹问题..... [复制链接]

上一主题 下一主题
发帖
306
樱饼
0
博丽神社的喝茶券(威望)
0
春度
44
交易币
0
只看该作者 15楼 发表于: 2009-08-31
引用第10楼h5nc于2009-08-27 11:44发表的  :
圆的。请参考打飞机人士对YYC某八卦XXX符的研究


很无耻的求链接地址……
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 16楼 发表于: 2009-08-31
偶要是找到了早就贴出来了……

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
离线Wiksy
发帖
170
樱饼
0
博丽神社的喝茶券(威望)
1
春度
7
交易币
0
只看该作者 17楼 发表于: 2009-09-02
引用第14楼h5nc于2009-08-31 08:42发表的  :
[code]
bool checkCollisionEllipse(float aimx, float aimy, float rPrep, float rParal, float rotCos, float rotSin, float rOri)
{
    float longr = rPrep > rParal ? rPrep : rParal;
.......


如果没错的话这是相当于长短轴各加圆半径之后判断是否包含圆心吧。
问题在于这种方法只是近似——当短轴长度趋向于0的时候误差就会越来越大。
よろしい、ならば麻雀だ!
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 18楼 发表于: 2009-09-02
引用第17楼Wiksy于2009-09-02 07:20发表的  :
如果没错的话这是相当于长短轴各加圆半径之后判断是否包含圆心吧。
问题在于这种方法只是近似——当短轴长度趋向于0的时候误差就会越来越大。


可惜不是这样的
前半部分旋转坐标轴使椭圆中心位于原点,长短轴分别在XY轴
正椭圆和圆相交判定就索后半部分
并不仅是长短轴加半径,而是使用椭圆判定公式计算
如果你确定要判断的是纯几何的椭圆的话,这个计算方法的误差仅来自于IEEE
在我的系统中的BEAM判定都是用这个的,长宽比很高的都没啥问题

顺便,这个不是一般椭圆的最佳判定方法,考虑到STG中大多出现长椭圆,所以忽略了内包围盒的剔除,没测过但感觉多少会增加一点点消耗

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
离线Wiksy
发帖
170
樱饼
0
博丽神社的喝茶券(威望)
1
春度
7
交易币
0
只看该作者 19楼 发表于: 2009-09-02
引用第18楼h5nc于2009-09-02 08:17发表的  :
正椭圆和圆相交判定就索后半部分
并不仅是长短轴加半径,而是使用椭圆判定公式计算


问题就在于这个椭圆判定公式相当于判断点(newx, newy)是否在一个长轴长 = rPrep + rOri, 短轴长 = rParal + rOri的椭圆内……这是长短轴各加了圆半径长的椭圆没错吧...
这个公式就是在长轴长的时候会有误差的…… [attachment=71836]
よろしい、ならば麻雀だ!
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 20楼 发表于: 2009-09-02
我既证明不出来有问题也证明不出来没问题……………………数学问题交给ZB好了

但我可以这么说,考虑三种极端情况,长轴=0,长轴=短轴,长轴=无穷,这三种情况下,直线、圆和直线,我的式子都成立,如果你说因为长轴长而产生的误差,则这就证明你的假设不准,虽说有可能是长轴在一定范围内有误差,但我想不出来什么在椭圆上的特殊点或特殊角能达到两个或两个以上临界变化……
以上,期待驳论


嘛……好吧……程序模拟了一下,我那样索不精确的……
但顺便得出了如下的结论
1、计算与椭圆的相切是非常麻烦的,那牛顿算法也很诡异
2、我所用的方法,在判定点为1像素or类似的状况下,长椭圆的误差保持在1像素内……即是观测不能……
3、最终解释:BEAM不是椭圆,而是以椭圆为判定边界的椭圆内切圆圆心组成的轨迹(某未知四次方程,请美工们加油)
[ 此帖被h5nc在2009-09-02 17:44重新编辑 ]

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
离线zavayev
发帖
392
樱饼
0
博丽神社的喝茶券(威望)
1
春度
12
交易币
0
只看该作者 21楼 发表于: 2009-09-03
已知椭圆中心坐标(x0,y0),圆心坐标(x1,y1),圆半径R,椭圆半轴A焦距a,半轴B焦距b,半轴A上一个点的坐标(x2,y2)。

由椭圆极坐标方程:r = a·b/sqrt( a^2 + b^2·(cosθ)^2 - a^2·(cosθ)^2) )
算出圆心与椭圆中心所在直线上与椭圆交点到椭圆中心的长度,再与圆的半径相比较。这样也用不着旋转坐标轴什么的了。

  1. Vector2 vec1(x1-x0,y1-y0);    //圆心与椭圆中心连线
  2. Vector2 vec2(x2-x0;y2-y0);    //半轴A
  3. float L1 = vec1.Length;
  4. float L2 = vec2.Length;
  5. float cosP = vec1*vec2/(L1*L2);    //连线与半轴之间夹角P的余弦
  6. float L = a*b/sqrt(a*a + b*b*cosP*cosP - a*a*cosP*cosP);
  7. return ( L>(L1-R) ? true : false );


未经测试,只是说明一下思路,不能保证正确性。


吾辈还是太普通了……

THP_Wiki:东方求闻史纪 龟速填坑中……
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 22楼 发表于: 2009-09-03
引用第21楼zavayev于2009-09-03 18:59发表的  :
已知椭圆中心坐标(x0,y0),圆心坐标(x1,y1),圆半径R,椭圆半轴A焦距a,半轴B焦距b,半轴A上一个点的坐标(x2,y2)。
由椭圆极坐标方程:r = a·b/sqrt( a^2 + b^2·(cosθ)^2 - a^2·(cosθ)^2) )
算出圆心与椭圆中心所在直线上与椭圆交点到椭圆中心的长度,再与圆的半径相比较。这样也用不着旋转坐标轴什么的了。
.......


不太理解,但椭圆和圆的切点不是圆心连线上的啊……
另一点就是,为了效率尽量少使用开方、三角函数才应用坐标变换的,使用向量类应用获得向量长度之类的运算我感觉都会增加很多复杂度的……

(虽说貌似游戏中椭圆判定应该没多少吧……)

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
离线zavayev
发帖
392
樱饼
0
博丽神社的喝茶券(威望)
1
春度
12
交易币
0
只看该作者 23楼 发表于: 2009-09-03
引用第22楼h5nc于2009-09-03 19:16发表的 :
不太理解,但椭圆和圆的切点不是圆心连线上的啊……
另一点就是,为了效率尽量少使用开方、三角函数才应用坐标变换的,使用向量类应用获得向量长度之类的运算我感觉都会增加很多复杂度的……
.......


貌似没错…………(爆)
但是误差不会特别大,用来作近似运算的话还凑合…………


这里面三角函数运算可以通过向量点积来避免,开方的话倒是必须要用到一次…………


吾辈还是太普通了……

THP_Wiki:东方求闻史纪 龟速填坑中……
离线Wiksy
发帖
170
樱饼
0
博丽神社的喝茶券(威望)
1
春度
7
交易币
0
只看该作者 24楼 发表于: 2009-09-03
要真的算圆和椭圆相交的精确解的话,解四次方程是一定不可避免的(如同ZB上次所说,次数是一个不可改变的数值)

……所以我一直觉得需要用椭圆=设计有问题
よろしい、ならば麻雀だ!
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 25楼 发表于: 2009-09-04
引用第24楼Wiksy于2009-09-03 21:14发表的  :
要真的算圆和椭圆相交的精确解的话,解四次方程是一定不可避免的(如同ZB上次所说,次数是一个不可改变的数值)
……所以我一直觉得需要用椭圆=设计有问题

嘛……所以我现在深刻认为该判定区域是椭圆而已,视觉区域没必要是椭圆啊……
拿过BEAM的图来我也觉得是两头略窄的非椭圆形状,介于椭圆和菱形之间的形状
所以只要画成这样就好了嘛~
只要不是有棱角的判定区域都可以进行擦弹所以就这样吧……

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
发帖
306
樱饼
0
博丽神社的喝茶券(威望)
0
春度
44
交易币
0
只看该作者 26楼 发表于: 2009-09-04
引用第25楼h5nc于2009-09-04 10:56发表的  :
嘛……所以我现在深刻认为该判定区域是椭圆而已,视觉区域没必要是椭圆啊……
拿过BEAM的图来我也觉得是两头略窄的非椭圆形状,介于椭圆和菱形之间的形状
所以只要画成这样就好了嘛~
只要不是有棱角的判定区域都可以进行擦弹所以就这样吧……


两头略窄的非椭圆形状->米粒形?抑或说是梭形?
那种东西判定起来好像比椭圆还麻烦吧?

To zavayev(21L):
你的这个办法和我以前想的完全一样,而且离心率不是很大的情况下还是可以用来凑合用的= =
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 27楼 发表于: 2009-09-04
引用第26楼月下のzero于2009-09-04 18:11发表的  :
两头略窄的非椭圆形状->米粒形?抑或说是梭形?
那种东西判定起来好像比椭圆还麻烦吧?
.......

请看第一句……………………………………………………
不管什么形状,命之判定区域为椭圆,故可用椭圆判定………………………………………………

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
发帖
306
樱饼
0
博丽神社的喝茶券(威望)
0
春度
44
交易币
0
只看该作者 28楼 发表于: 2009-09-05
引用第27楼h5nc于2009-09-04 23:07发表的  :
请看第一句……………………………………………………
不管什么形状,命之判定区域为椭圆,故可用椭圆判定………………………………………………


囧- -
我看的那啥了= =

不过问一下,是不是东方系列里面所有的子弹的判定都是圆形或者椭圆的?
这样子的话,碰撞判定真的就只是不用太考虑的超小消耗了= =
离线h5nc
发帖
2724
樱饼
0
博丽神社的喝茶券(威望)
2
春度
738
交易币
0
只看该作者 29楼 发表于: 2009-09-05
引用第28楼月下のzero于2009-09-05 09:04发表的  :
囧- -
我看的那啥了= =
.......

其实从YYM开始我有些觉得东方里只有圆形了……
比如那魂之类的……全部圆形组成……
正交方形也许有吧,一时没想到什么例子

0x073《東方弾置場》开发版即将问世
【Leah】引擎问世
同人STG《叛境东方游》已经腰斩
《叛之境界无双篇》已死
快速回复
限100 字节
 
上一个 下一个