3d拾取演算法都有哪些？它們的主要演算法思想是什麼？
計算機圖形學中有哪些3d拾取的演算法，儘可能多幾種，謝謝！
三維拾取（picking）在圖形學裡主要是指用戶對三維場景做交互時，從二維屏幕坐標找出點擊中的三維物體，其主要可分為兩類：基於光柵化的方法、幾何演算法。
基於光柵化的方法中，通常是在光柵過程中，把物體的標識符（identity，例如每個物體唯一的顏色）渲染至一個渲染目標，然後再回讀緩存中的數據。理論上可以把場景獨立渲染至所需位置的 1x1 渲染目標便可，但這樣需要再跑一次大部分渲染管道（例如提交 drawcall 和光柵化開銷）。所以通常是直接在渲染場景時同時渲染此數據。在一些平台上可使用 stencil 去存儲此數據。其優點是像素級精確，也可處理含不透明度材質的情況。
幾何方法就是把二維屏幕坐標，利用攝像機的視錐，轉換成三維射線（3D ray，即 ），然後和場景做相交測試，並找出最接近（
為最小）的物體。為了加速性能，需要場景管理的數據結構去快速找到潛在相交的物體，然後再做細緻的（如逐三角形）的細緻檢測。其優點是和屏幕分辦率無關，可在CPU上實現（也可利用GPU光線追蹤）。但缺點是實現相對光柵化複雜，如果要考慮透明材質還需CPU方的紋理採樣。
這問題比你想像的要複雜很多
http://www.realtimerendering.com/intersections.html
本人水平比較菜，不怎麼會用專業術語，不扯理論，只談工程。
- 在渲染流程走光柵化的時候，給每個頂點加一個標誌位，例如，場景中有一個椅子，一個桌子。在把頂點信息傳入顯卡中時，除了xyz信息再增添一個int信息，比如桌子是0，椅子是1。那麼，通過渲染管線的各個流程後，這個信息還仍然是保留的，最後的fragment/pixel階段就可以讀出當前像素所拾取的幾何體了。
- 在渲染流程走光線追蹤或者光柵化時，把場景組織成一顆八叉樹或者BVH樹，然後從像素髮射射線，隨後遍歷場景中的圖元，求交，最後找到深度值最近的圖元即可。
- 事實上在走光柵化的時候，會有大量的圖元是被遮擋住的，可以在進行視錐體剔除的時候就直接順便把拾取給完成了。
-----------------------------------------------------------------
一般來說是兩類
一類是利用射線拾取 也就是從滑鼠點向平面內的方向發一條射線 通過幾何計算相交行找出射線相交的三角面 點等信息 這類一般是CPU拾取 大場景下費CPU 所以要配合八叉樹 bvh樹等數據結構優化拾取效率
第二類是GPU拾取，一般做法是給每個mesh一種顏色 然後繪製一遍，滑鼠點所在的位置readPixel讀取像素顏色 反推對應的mesh 好處是演算法簡單 但是會增加drawcall 費GPU
物理方式簡單就打條射線，判斷相交
渲染方式，就是屏幕空間打射線判斷顏色
物理引擎很成熟了
你可以參考下機器人抓取領域的一些總結：Tom Hardy：機器人抓取匯總|涉及目標檢測、分割、姿態識別、抓取點檢測、路徑規劃
一開口就知道老南郵了
推薦閱讀：
