[問題] 三維空間物體與圓柱碰撞測試

[noodleT (麵T)]

目前我的物體是 stl 的三角網格檔，與空間中有限長度的圓柱要做碰撞測試。

目前的做法是將 stl 檔的三角形再劃分成 n 個小三角形，使得這些頂點的密度滿足：
若圓柱跟物體碰撞，則圓柱必定也至少跟一個定點碰撞。

然後利用 kd tree 將頂點排序，
最後在圓柱中心線上取 m 個點，做 kd tree 的最鄰演算。


在圓柱上取 m 個點是沒什麼問題，但將 stl 再分割成小三角型就出現了分割效率不佳的
問題

我目前分割stl的方法是：
若三角形邊長大於閥值
則將該邊一分為二，並遞迴

總之還是嫌整體效率不佳，
又要分割三角形，多出一堆頂點。

想請問有沒有其他更合適的演算法？

謝謝

--
Sent from my Android

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.150.99
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1433605016.A.890.html
→ longlongint: 線段跟圓柱的距離?
不是圓柱中心線跟圓柱的距離，是圓柱中心線跟三角面的距離，

最終目的是想知道圓柱跟三角面是否發生碰撞

→ longlongint: bounding box, BVH tree
包圍體是每個三角面建立一個包圍體嗎？

還是說可以一組 N 個三角面建立一個包圍體？
※ 編輯: noodleT (39.14.137.41), 06/15/2015 17:33:21
→ longlongint: 看你要怎麼切囉  然後三角面撞圓柱在邊角我還在想
→ longlongint: 若撞到bounding box 則 往下檢查小bounding box
→ longlongint: 到分割結束之後再跑精細的檢查
→ longlongint: 如果把圓柱轉成mesh用AABB包起來就簡單了XD
→ longlongint: 用圓柱公式啥的 變成要參數化 看解的space有沒有交
→ longlongint: 集(無限圓柱&圓柱上下界)
→ longlongint: http://www.realtimerendering.com/intersections.ht
→ longlongint: ml
→ longlongint: 我沒空幫你看 所以用猜的  給你資料自己看吧