Fak*_*ken 10 theory algorithm 3d
我有一个由三角形的表面表示描述的闭合对象(由三个顶点描述,形成右手规则,法线指向对象的"外部").我将一个半径的球体放置在靠近物体表面的某个3D空间中.我想确定球体是否与物体相交.
我想到了3种方法来确定这一点,但每种方法都有它们的缺点,而且没有一种方法是理想的.
1)I可确定"侧面"在其上球将被放置,从那里我可以从基准面计算距离的网格到其中第一次遇到物体的距离.我可以对球体的相对"侧面"做同样的事情,然后简单地检查到物体的距离是否总是大于到球体表面的距离.如果到对象的距离总是更大,则球体不会在网格上的任何点处与对象相交.
这样做的好处是它相当快,但由于我只计算谨慎点,所以它不是绝对的.如果我的网格的分辨率太高,则球体有可能在我的网格节点之间的点处相交.
2)我可以获取所有三角形的所有顶点,并根据我放置的球体方程检查它们.如果在球体内部检测到顶点,则球体将完全部分位于对象内部.
这样做的好处是它相当快,但也很容易出现故障.球体可以在三角形内与物体相交,并且一起错过所有顶点.
3)我可以计算球体表面上的点簇.然后,我可以检查每个点是否在对象内部(使用多边形算法内的点的3D版本).如果对象内有任何一个点,则球体的一部分位于对象内.
这样做的好处是它可以非常准确,这取决于我在球体表面上使用了多少点(更高的点密度=更高的精度).然而,对象算法内部的点相当昂贵,尤其是当三角形的数量增加时.这种方法最好(甚至可以告诉我球体与物体相交的确切位置和数量),但速度非常慢.
您是否有任何算法或方法可以解决这样的问题？我最重要的目标是准确性,我需要知道球体是否会接触物体.知道球体接触的位置或至少是一般区域也是很好的.最后速度总是一件好事.
谢谢
-Faken
这应该是你问题的完整答案.我没有给出实施,所以可能需要考虑避免不必要的划分等.请询问澄清是否有任何不清楚.我在CashCommons的想法中建立了John.
设c为半径为r的球体的中心.我们真正需要知道的是:三角形T(不仅仅是三个顶点)的任何一点都比r单位更接近于c？
有三种情况需要考虑:
我们定义了一些变量:
第1步:检查所有三角形顶点,以防我们在案例1中.
第2步:找到p,P中最接近c的点.这可以通过将c投影到P来完成.
第3步:如果我们在案例2中,我们基本上完成了.因此检查p是否在T中.(检查一个点是否在给定的三角形中相对容易,但我不知道最好的方法,所以我会把它留下来.)如果是,检查是否dist(p,c)> r,这会给你答案.
这只留下了案例3.所以,假设我们有p,并且p不在T中.现在,我们实际上从几何学中知道关于p的特定事物:线c - > p垂直于P.(如果它不是我们可以找到一个比p更接近c的点p'.由于这种垂直性,我们可以使用毕达哥拉斯定理:
Dist(c, z)^2 = Dist(c, z)^2 + D(p, z)^2
对于P.中的任何z.特别是对于z = t,这是正确的.
所以现在我们只需找到并检查是否:
D(p,t)^2 <= r^2 - D(c,p)^2
这是一个非常类似的问题,现在有两个方面.要做的是找到最接近p的T中的t,从而找到c.我们已经检查过t不在T的内部,或T的顶点之一.因此,它必须位于其中一个边上.所以,我们可以尝试在每个边缘找到它.如果t不在顶点,则线t - > p将垂直于边,因此它相当简单.
步骤4:对于三角形的每一侧v1 - > v2,执行以下操作:
4.1.从v1到v2的线段由下式给出
(x,y,z) = (v1x, v1y, v1z) + s * (v2x - v1x, v2y - v1y, v2z - v1z), 0 <= s <= 1
4.2我们想要一条位于平面P中的线,垂直于v1 - > v2,并且包含p.这一行将有表格
(px, py, pz) + s * (qx, qy, qz)
所以我们只需要选择一个与平面P平行且垂直于v1 - > v2的向量q.以
q = (p-->c) x (v1-->v2)
(即,交叉积)应该这样做,因为它将垂直于P的法线,因此平行于P,并垂直于v1 - > v2.
4.3求解方程组
(tx,ty,tz) = (v1x, v1y, v1z) + s1 * (v2x - v1x, v2y - v1y, v2z - v1z)
(tx,ty,tz) = (px, py, pz) + s2 * (qx, qy, qz)
找到两条线上的t.这真的只是意味着解决
v1x + s1 * (v2x - v1x) = px + s2 * qx
v1y + s1 * (v2y - v1y) = py + s2 * qy
v1z + s1 * (v2z - v1z) = pz + s2 * qz
对于s1和s2.
4.4.如果s1介于0和1之间,那么我们发现v1和v2之间的点t,应该检查它.
4.5.如果s1不在0和1之间,那么v1或v2中的一个最接近p,所以我们已经检查了它.