查看完整版本: [-- 如何判断椭圆与圆相交?激光弹问题..... --]

-> 同人游戏创作/Doujin Games Workshop -> 如何判断椭圆与圆相交?激光弹问题..... [打印本页] 登录 -> 注册 -> 回复主题 -> 发表主题

同意注册 2009-06-27 22:38

如何判断椭圆与圆相交?激光弹问题.....

这MS是一个数学和编程的问题...其实多半是数学....好吧我的数学是渣...所以发贴问吧....想不出来实在是....

情况是这样,想做激光弹,开始想的是矩形和圆形做碰撞检测,后来发现,好像不是很好判断的样子...数学渣的思路总是想找最简单的方法...

于是习惯成性的问管家大,管家大说可以试试用椭圆和圆相交判断,感觉这个好像应该比较和逻辑,但是...依然不知道怎么判断...数学上...

本来想如果只是半径的话也没啥...后来发现,好像还要做个旋转啥的,MS只是半径就不行了...于是再次数学渣...想不出来....

请问如何判断椭圆与圆相交,或者有其他的方法实现那个主角和激光条条的检测方法也好.

Z.Blade 2009-06-27 23:31
http://bbs.thproject.org/read.php?tid=57935

zavayev 2009-06-27 23:41
判断椭圆与圆相交……下意识的想法:
把圆心作为一个点投影到以椭圆的某根半轴作为极轴的极坐标系中,这样就可以得到圆心与原点连线交椭圆的点的坐标了……然后就可以根据距离来判断是否相交…………
不过这样会用到数次三角函数运算,如果是底层的算法的话不推荐使用…………

其他更优化的方法……暂时还没想到……

pkrs999 2009-06-28 00:14
把代表椭圆某个轴的向量单位化之后和圆心的坐标做点乘,就可以得到投影到极轴坐标系上的一维坐标,这个应该比三角函数快……

quifi 2009-06-29 12:47
我看还是尽量用矩形和圆吧。转一下就可以了。

h5nc 2009-06-29 16:48
矩形是比椭圆慢不少的。。。我是说矩形+椭圆同时存在。。
所以可以考虑屏蔽矩形。。。至少我没看到过歪的矩形弹出现在东方里。。。包括灵梦的符……

quifi 2009-06-29 17:47
那“灵梦的符”是什么形状的?

同意注册 2009-06-29 17:47
内啥,2楼3楼大能给个简单的图解或是代码试判断一下么,数学渣的联想能力也很渣....

另外图是这样的,发现这个激光条是一段一段的,如果自机撞上去后,激光条中间会少一条,看样子好像是按一定间隔排列的椭圆么??

[attachment=69256]

月下のzero 2009-08-26 20:56
问下H5大= =
红白的符是圆形的还是椭圆的?
---------------------------------------
我之前也一直以为那是矩形的= =

Wiksy 2009-08-27 11:44
难道不是矩形么@_@
不管怎么看,判断矩形——圆形相交在速度和复杂度上都比判断椭圆——圆形相交简单才对,尤其是二维情况下。

其实我建议用圆扫过区域(swept circle)来近似椭圆,至少这样算起来只要初等几何

h5nc 2009-08-27 11:44
圆的。请参考打飞机人士对YYC某八卦XXX符的研究

franniss 2009-08-27 23:32
矩形根本无法像东方那样擦弹。

h5nc 2009-08-28 07:38
圆形和圆形是最初等的运算,除非是正交矩形
如管家所说,要不是长到一定程度,矩形是无法擦弹玩的

同意注册 2009-08-30 22:36
那个....由于还是不知道怎么算,已经改用像素写了......

或者哪位扔个公式出来,感激不尽,子弹不太多的情况下,用像素到是很方便.

h5nc 2009-08-31 08:42


  1. bool checkCollisionEllipse(float aimx, float aimy, float rPrep, float rParal, float rotCos, float rotSin, float rOri)
    {
        float longr = rPrep > rParal ? rPrep : rParal;

        if((fabsf(x-aimx)>longr+rOri)||(fabsf(y-aimy)>longr+rOri))
            return false;

        float newx,newy;
        newx = (float)fabsf((rotSin*(aimx-x)-rotCos*(aimy-y)));
        newy = (float)fabsf((rotCos*(aimx-x)+rotSin*(aimy-y)));

        if(newx*newx*(rParal+rOri)*(rParal+rOri)+newy*newy*(rPrep+rOri)*(rPrep+rOri) <= (rPrep+rOri)*(rPrep+rOri)*(rParal+rOri)*(rParal+rOri))
            return true;

        return false;



懒得改or说明了……

月下のzero 2009-08-31 18:03
引用第10楼h5nc于2009-08-27 11:44发表的  :
圆的。请参考打飞机人士对YYC某八卦XXX符的研究


很无耻的求链接地址……

h5nc 2009-08-31 22:09
偶要是找到了早就贴出来了……

Wiksy 2009-09-02 07:20
引用第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 2009-09-02 08:17
引用第17楼Wiksy于2009-09-02 07:20发表的  :
如果没错的话这是相当于长短轴各加圆半径之后判断是否包含圆心吧。
问题在于这种方法只是近似——当短轴长度趋向于0的时候误差就会越来越大。


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

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

Wiksy 2009-09-02 10:18
引用第18楼h5nc于2009-09-02 08:17发表的  :
正椭圆和圆相交判定就索后半部分
并不仅是长短轴加半径,而是使用椭圆判定公式计算


问题就在于这个椭圆判定公式相当于判断点(newx, newy)是否在一个长轴长 = rPrep + rOri, 短轴长 = rParal + rOri的椭圆内……这是长短轴各加了圆半径长的椭圆没错吧...
这个公式就是在长轴长的时候会有误差的…… [attachment=71836]

h5nc 2009-09-02 15:17
我既证明不出来有问题也证明不出来没问题……………………数学问题交给ZB好了

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


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

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) )
算出圆心与椭圆中心所在直线上与椭圆交点到椭圆中心的长度,再与圆的半径相比较。这样也用不着旋转坐标轴什么的了。

  1. Vector2 vec1(x1-x0,y1-y0);    //圆心与椭圆中心连线
    Vector2 vec2(x2-x0;y2-y0);    //半轴A

    float L1 = vec1.Length;
    float L2 = vec2.Length;

    float cosP = vec1*vec2/(L1*L2);    //连线与半轴之间夹角P的余弦

    float L = a*b/sqrt(a*a + b*b*cosP*cosP - a*a*cosP*cosP);

    return ( L>(L1-R) ? true : false );


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

h5nc 2009-09-03 19:16
引用第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) )
算出圆心与椭圆中心所在直线上与椭圆交点到椭圆中心的长度,再与圆的半径相比较。这样也用不着旋转坐标轴什么的了。
.......


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

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

zavayev 2009-09-03 20:20
引用第22楼h5nc于2009-09-03 19:16发表的 :
不太理解,但椭圆和圆的切点不是圆心连线上的啊……
另一点就是,为了效率尽量少使用开方、三角函数才应用坐标变换的,使用向量类应用获得向量长度之类的运算我感觉都会增加很多复杂度的……
.......


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


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

Wiksy 2009-09-03 21:14
要真的算圆和椭圆相交的精确解的话,解四次方程是一定不可避免的(如同ZB上次所说,次数是一个不可改变的数值)

……所以我一直觉得需要用椭圆=设计有问题

h5nc 2009-09-04 10:56
引用第24楼Wiksy于2009-09-03 21:14发表的  :
要真的算圆和椭圆相交的精确解的话,解四次方程是一定不可避免的(如同ZB上次所说,次数是一个不可改变的数值)
……所以我一直觉得需要用椭圆=设计有问题

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

月下のzero 2009-09-04 18:11
引用第25楼h5nc于2009-09-04 10:56发表的  :
嘛……所以我现在深刻认为该判定区域是椭圆而已,视觉区域没必要是椭圆啊……
拿过BEAM的图来我也觉得是两头略窄的非椭圆形状,介于椭圆和菱形之间的形状
所以只要画成这样就好了嘛~
只要不是有棱角的判定区域都可以进行擦弹所以就这样吧……


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

To zavayev(21L):
你的这个办法和我以前想的完全一样,而且离心率不是很大的情况下还是可以用来凑合用的= =

h5nc 2009-09-04 23:07
引用第26楼月下のzero于2009-09-04 18:11发表的  :
两头略窄的非椭圆形状->米粒形?抑或说是梭形?
那种东西判定起来好像比椭圆还麻烦吧?
.......

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

月下のzero 2009-09-05 09:04
引用第27楼h5nc于2009-09-04 23:07发表的  :
请看第一句……………………………………………………
不管什么形状,命之判定区域为椭圆,故可用椭圆判定………………………………………………


囧- -
我看的那啥了= =

不过问一下,是不是东方系列里面所有的子弹的判定都是圆形或者椭圆的?
这样子的话,碰撞判定真的就只是不用太考虑的超小消耗了= =

h5nc 2009-09-05 09:33
引用第28楼月下のzero于2009-09-05 09:04发表的  :
囧- -
我看的那啥了= =
.......

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

隔壁的桌子 2009-09-06 00:23
嗯,确实没必要这么执着于这个问题。自机和子弹的位置本身就是很离散化的。比如,自机慢速的时候每帧大概也要移动两个像素左右,所以大概差不多就行了,没必要和4次方程过不去。

franniss 2009-09-06 02:26
[attachment=72016]


条激光每个片段的间距图示

h5nc 2009-09-06 09:28
相差一两个像素对高级玩家也是很致命的……
顺便管家这个我也有点问题,这个不一定是子弹构成的,而有可能是化为道具时先创造子弹再消除的效果,在YYC年代BEAM是可以逐12帧永久擦弹的,和子弹不同,所以一直觉得不会是子弹构成的……
但其实弹幕素材第一排貌似就是这东西……嘛……无视

隔壁的桌子 2009-09-06 12:20
你没明白我的意思。再高级的玩家他的自机和子弹也是一帧一帧移动的,他操控再精确也不能比两个像素更精确。由于判定算法带来的误差是远小于两个像素的,所以用近似算法就行了。 同理,激光弹也是,用椭圆用矩形区别都不大。

h5nc 2009-09-06 21:44
引用第33楼隔壁的桌子于2009-09-06 12:20发表的  :
你没明白我的意思。再高级的玩家他的自机和子弹也是一帧一帧移动的,他操控再精确也不能比两个像素更精确。由于判定算法带来的误差是远小于两个像素的,所以用近似算法就行了。 同理,激光弹也是,用椭圆用矩形区别都不大。

呐……正常的玩家是要计算偏移和提前偏移的……比如FTG的目押,部分STG要求更加苛刻……是移动与否的问题,而不是是否能移动的问题
如玩家速度3.6像素/帧,目测相距4~5像素,是否移动?
嘛,如果你说是人眼不可及,那是大脑跟不上身体的条件反射而已……
这个玩多了就有体会了……

隔壁的桌子 2009-09-07 00:46
我前面所说的始终都没有涉及到玩家个人能力的问题,或者可以认为玩家都是超人,或者认为游戏帧率是每秒1帧。
但是你的最小移动距离还是每次2个像素,而精确的和近似的椭圆-圆碰撞判定算法在正常的情况下,误差会远小于2个像素。

h5nc 2009-09-07 09:17
我承认误差小于2像素,但是不同意这个误差可以接受(虽然也不是有什么更好的方法)
我上次说的是移动精确的问题,使用最小移动距离是不可取的,09和095都需要部分时候高速精确移动,商业游戏更多……而且并不是每次你都和最大误差成正面交锋,你不知道一个斜向运动在什么时候会中弹,拿过replay来看发现完全没有碰上,这个就成一大问题了

我的观点在于,让判定区域精确,通过计算机模拟画出子弹真正的判定边缘(某未知四次曲线),再将此图当成BEAM原图放进游戏,这样永远玩家看到什么就是什么

隔壁的桌子 2009-09-07 10:14
哦,好吧,那是我没明白你。你是想要一个所见即所得的绝对精确的系统,把事情交给能够一劳永逸就解决问题的美工是个好办法。
如果真的要那么精确的话,还有个问题,自机判定大小不一样怎么办?
还有,只是为了BEAM的话用矩形判定不就行了么。仍是先算出来newx,newy,再将他们取绝对值,然后
return ((newx<a+r0ri)&&(newy<b))||((newx<a)&&(newy<b+r0ri))||((newx-a)^2+(newy-b)^2<r0ri^2);
如果矩形判定的情况仅仅是激光才有的话,可以更简易(因为矩形都连在一起,四个角上可以不管)
return (newx<a+r0ri)&&(newy<b+r0ri);

h5nc 2009-09-07 12:48
平方和计算加减代价差不了多少吧…………………………………………但是矩形还要求边上的那个突兀的尖……
你的意思是不是<================>
=是矩形,然后两个三角?
自机判定大小确实有不同的,但判定点大小相同,灵梦的例子是给容易失误的玩家爽的,如果真想设计成高级玩家的玩法(除了固定放置位,YYCEX),那肯定视觉区域不一样,就是判定点的图也不同,至少缩放不同
至今东方系列没出现过不同的时候,所以我也不考虑……

以上全是个人观点,我自己也和自己较劲过很久……嘛……和谐……

隔壁的桌子 2009-09-07 15:03
引用第38楼h5nc于2009-09-07 12:48发表的 :
你的意思是不是<================>
=是矩形,然后两个三角?
.......

嗯,差不多。我的想法是激光的一端用那个发光的球球封住,另一端在屏幕外。
至于消耗,我觉得这些都是微不足道的。你的算法里也体现了,距离较远的不可能碰撞的都直接return false;了,真正做判定的没多少子弹。
如果要“所见即所得”的话还是矩形好,要不激光都成了糖葫芦形状了?
个人意见

h5nc 2009-09-07 15:57
大复活是矩形…………………………………………因为尖被更大的尖盖住了

水月 2009-09-24 11:14
感觉不是椭圆啊,橄榄圆,想做的好,参数曲线,切线采样投影。这样速度很费。
用多边形逼近,做多边形碰撞,其实也很费。如果配合好的广义剔除法开销就会在可以接受的范围内。
偶法则是能用多边形就用多边形,实在不行的地方才用曲线
激光,中间是矩形,两头是三角,对缝合边标记一下,看起来就是和椭圆差不多

bdnbioaoi 2013-01-07 11:29
Most estate agents in the UK advise that it takes between four and six weeks to receive the first offer on a property,abercrombie. When the first offer comes in,hollister, it is important that they let you know of it, even if far short of the asking price.
When they call to advise the offer, they will let you know all the basic details of the seller, their position in the market and, importantly, the value of the offer tabled,hollister co. Rather than look at the amount offered and make a decision,jordan, what counts is the position the buyer's are in.
For example,hollister outlet, the best placed people are usually first time buyers and those with no property of their own to sell. Buyers that have sold subject to contracts being exchanged are also good,hollister deutschland, whilst investment buyers can also move quickly. If an offer comes in from those in such a position, it is worth considering taking the property off the market.
In many cases though,hollister, offers will come from those still in the process of selling,franklin marshall, so the best estate agents will always provide their expertise and guidance into the situation. One thing that is essential,jordan pas cher, is that the property continue to be marketed, viewings conducted and further bids offered.
No matter what the position the buyer is in, it is generally good not to accept the first offer if below the asking price,hollister brazil. This is the time for negotiation and the buyer would have been advised to go in with a low bid,air jordan. As such,abercrombie france, it is good to counter the offer with a slightly adjusted price or,loubouttin pas cher, if confident, maintain the asking price.
As can be seen with our customer reviews at meetmyagent.co,hollister france.uk, the best estate agents will provide vital support and assistance at this time, and ensure the financial position of the buyer has been validated. All these details taken care of, the sale can be completed.
相关的主题文章:

  
   http://sisl.rites.uic.edu/blueprint/wiki/User:Bvjklxbho#The_Most_Effective_Internet_Marketing_for_Small_Business_Tec
  
   http://www.043211.com/a/zhuangbanlei/20120607/20.html
  
   http://ku18.cn/yinshi/shuiguo/201207/1192.html
  

The Voice over IP trade is developing and establishing swiftly as well. Using this type of, plenty of business options for compact or significant businessmen are emerging. One of several hottest VoIP companies currently certainly is the Voice over IP provider business enterprise.

geminilan 2013-03-21 13:34
我这样做是不是在挖坟...我不懂编程...会一点数学,先假定椭圆中心(x0,y0)
用极坐标,y=y0+bsinθ,x=x0+acosθ,dy/dx=-b/a*tanθ(即椭圆切线斜率)则对应圆相切点半径斜率为a*tanθ/b,可算出相切时圆心轨迹...若圆心落在此范围内则相交...
嘛...若是不懂装懂的话敬请见谅...什么算式废速度什么的完全不知道呢...

翔輪 2013-06-30 23:40
重新看了一下这个问题,从图像处理的角度来说,假设圆的半径是10像素,对椭圆进行一个最简单的腐蚀运算就可以得到了相交区域了,腐蚀运算强度为当前圆的半径,得到结果为0的区域如果包含圆心则相交,当然前提是把椭圆内所有数据置0,椭圆外所有数据置1,可用1bit的bmp图来储存这个图像(也可以用膨胀来做,椭圆内数据置1,椭圆外数据置0就是膨胀了)。
一般机子CPU的DSP 处理速度都还行吧,移植到掌机平台也可以这么干,只要有DSP处理能力的MCU就行。


查看完整版本: [-- 如何判断椭圆与圆相交?激光弹问题..... --] [-- top --]


Powered by phpwind v8.7 Code ©2003-2011 phpwind
Time 0.030243 second(s),query:2 Gzip enabled