[程式] 想請問一下關於3D的Picking實現方式

[xtxml (赤木巧☠)]

先說說谷狗+自己目前的所知道的狀況。

1.純數學手段：ray picking(射線去遍歷所有三角型)

自己有寫好一套實現的代碼，但似乎無法靠顯卡來加速，
尤其是碰到有bone的模型，矩陣運算我都盡可能交給顯卡處理，
要去做picking等於要再重算所有點，開始覺得不太可行。


2.open gl/DirectX特殊的處理法。

open gl可以用selection mode，做一次假rendering，
然後判定每個點的深度來做到picking的效果。
DirectX則感覺很麻煩，雖然可以用D3DXIntersect來做到，
但是他提供的函式界面實在不好操作，綁死DX系統，很難做整合。




3.算出涵蓋模型範圍的長方體，用這個長方體做picking。

雖然犧牲掉精度，但可以接受。
碰到難處的部分一樣是有bone的模型，這個長方體是否該隨時去更新？
感覺一直去比對好像也是很蠢的做法。



評估了以上3種方法，感覺好像都有不太理想的地方...
因此想請教一下，真正遊戲會實作的方式是如何？
或者美術輸出模型的時候會帶有哪些特殊的資料，以供picking使用？
還請各位前輩指教，感謝。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.163.46
→ azureblaze:一般是2.的gl方法 DX應該也有一樣的東西
→ azureblaze:然後他不是用深度判斷，而是給不同物件不同顏色
→ azureblaze:最後看那個點是哪個物件的顏色
→ azureblaze:不過用2.之前通常會用3.挑掉不可能被選到的物件
→ azureblaze:3.可以google看看dynamic octree
哦哦，十分感謝，那我先去查一下這部分的內容...

您的回應速度快到讓我嚇到@@  (沒想到深夜冷門板會這麼快得到回覆XD)
推 cjcat2266:可以用broad phase先快速篩選掉AABB沒有跟ray相交的物件
→ cjcat2266:然後再用narrow phase選出真正的相交物件
→ cjcat2266:我蠻多同學都使用dynamic AABB tree架構的，可以試試看
→ cjcat2266:Box2D有2D版的dynamic AABB tree程式碼供參考
還沒實際建立過AABB tree，相關的演算法我會去了解一下，感謝您:)
※ 編輯: xtxml           來自: 123.193.163.46       (04/08 07:35)
推 Killercat:其實用1 配上AABB 不會很痴效能
→ Killercat:另外AABB不算tree啦 不過就是一種BB的做法而已
推 cjcat2266:Dynamic AABB tree是tree結構，存放不同階層的AABB
→ cjcat2266:是用來實作broad phase的一種spacial partition結構
→ silveriii:bounding volume hierarchy + space partition
推 lovesnake:樓上正名。