首页 > 代码库 > ray与triangle/quad求交二三事
ray与triangle/quad求交二三事
引擎中,ray与quad求交,算法未细看,但有求解二次方程,不解。
ray与triangle求交,使用的是97年经典算法,仔细看过论文,多谢小武同学指点,用到了克拉默法则求解线性方程组。
想模仿该方法,做ray与quad的求交,发现方程里不仅有u和v,还有uv,没法变换成线性方程组的形式。
本以为引擎中quad中四个点可以不共面,看过接口,不然,“不共面和退化的多边形不保证正确结果“。
而后又有两个问题,一是,与一个quad求交比与两个三角形求交快吗?二是,如果前面的问题答案为否,即两个三角形更快,为何不用两个三角形代替一个quad进行求交。
第一个问题,粗略计算了一下,quad不比两个triangle快(引擎中是这样)
第二个问题,quad有存储上的优势,首先索引值的存储,一个quad小于两个triangle,其次,mesh中,对于facevarying的变量,一个quad有四个,两个triangle有六个。
查阅资料,http://www.realtimerendering.com/intersections.html,这基本是比较全的求交算法集合。
链接里有与plane求交,但不够详细。
与quad求交的比较直接的办法,先求与面的交点,6次乘法求法向N,6次乘法求参数t。然后求出交点P(3次乘法),判断P是否在quad内部,最初使用的是http://www.cnblogs.com/graphics/archive/2010/08/05/1793393.html里面的重心法,判断点P是否是两个三角形内部。而后发现需要求交点的uv值,需要inverse bilinear interpolation(小武想到的关键词),找到方法http://stackoverflow.com/questions/808441/inverse-bilinear-interpolation,里面有求解二次方程(与前面所述引擎中类似),但目前还没遇到有两个解的情形。(乘法次数待统计)
最后,想到前面的三角形的uv值,论文中给出的是barycentric coordinates,而以前得出的结论是三角形uv值本质是退化的四边形的uv值(v从0到1的一条边退化成点),难道barycentric coordinates可以与之转化?
经验证以及阅读分析代码,发现三角形求交算法,将barycentric coordinates转化成了退化的四边形uv值,转化方法:u = u+v, v = u/(u+v)。