使用立方體圖的實時多解析度3d衝突檢測的製作方法
2023-10-06 00:07:59 2
專利名稱：使用立方體圖的實時多解析度3d衝突檢測的製作方法
使用立方體圖的實時多解析度3D衝突檢測
背景技術：
在三維(3D)圖形中的衝突檢測是確定兩個對象是否彼此接觸的處理 過程，其中這兩個對象通常是包括連結的多個多邊形(例如三角形)的剛 性體。通常，這通過使處理器執行算法以計算一個對象的三角形是否在空 間上與另一個對象的三角形相衝突來實現。儘管存在針對這個問題的多種
方案，但所有標準解決方案都使用處理器來執行包括以下步驟的計算使 用空間數據結構，例如八叉樹，來測試對象到對象的衝突；並隨後執行一 系列幾何計算，來為其包圍體(bounding volume)顯示為是相交候選的那 些對象評價多面體到多面體的衝突。
當在諸如中央處理單元(CPU)之類的處理器中執行時，用於衝突檢 測的這些常規方案會佔用相當大的計算資源，這些資源在進行諸如物理計 算之類的CPU專用任務或執行人工智慧例程時能夠得到更好的利用，尤其 是在3D遊戲背景中。而且，通過在CPU中而不是在諸如圖形處理單元 (GPU)之類的專用圖形處理器中執行衝突檢測，常規方案不能利用由現 代圖形紋理採樣硬體所支持的硬體圖元。
包含在說明書中，並組成其一部分的附圖示出了與本發明原理相一致 的一個或多個實施方式，附圖與本發明的說明一起解釋這些實施方式。附 圖並非一定是按照比例繪製的，相反地，重點在於示出本發明的原理。在 附圖中，
圖1示出了根據本發明一些實施方式的3D渲染引擎或裝置的多個部
分；
圖2是示出根據本發明一些實施的一個處理過程的流程圖； 圖3是示出根據本發明一些實施的一個處理過程的流程圖； 圖4-7示出了多個實例方案，用於論述圖2和3中的處理過程；及圖8示出了根據本發明一些實施方式的一個系統。
具體實施例方式
以下說明參考了附圖。在不同附圖中相同的參考數字標記用於標識相 同或相似的元件。儘管以下說明通過闡述特定細節，例如具體結構、架構、 接口、技術等，提供了對所聲明的發明的不同方面的全面理解，但此類細 節是為了解釋的目的而提供的，不應視為限制性的。而且，按照本公開內 容，本領域技術人員會意識到，可以在脫離這些特定細節的其它實例或實 施方式中實現所聲明的發明的各種方面。在以下的公開內容中的某些時機， 省略了對公知的裝置、電路和方法的說明，以避免由於不必要的細節而使 本發明的說明不清楚。
圖1是根據所聲明的發明的一些實施方式的3D渲染引擎100的多個部 分的簡化框圖。弓l擎100包括衝突檢測算法102、紋理採樣器104、和紋 理存儲器106。本領域技術人員會認識到，3D渲染引擎可以包括其它組件 (例如鑲嵌單元(tessellation unit)，頂點著色器等)，已經從圖1排除了這 些組件，以便不會混淆本發明的實施。另外，儘管本發明不限於這一點， 圖1包括像素著色器108，其可以將算法102耦合到紋理採樣器104。而且， 儘管圖1示出了一個紋理採樣器104，但是本領域技術人員會認識到，在不 脫離所聲明的發明的範圍和精神的情況下，可以實現一個以上的紋理採樣 器，和/或這些紋理採樣器耦合到衝突檢測算法102和/或存儲器106。
衝突檢測算法102可以包括檢測例程，所述檢測例程包括可以用於檢 測對象之間的衝突的軟體和/或固件的任何組合。為此，算法102可以為紋 理採樣器104提供一個或多個査詢索引。可替換地，算法102可以為著色 器108提供一個或多個查詢索引，並且著色器108可以將這些索引傳送到 紋理採樣器104。採樣器104隨後可以使用這些索引來訪問在紋理存儲器 106中保存或存儲的紋理圖的相應紋理地址處所存儲的距離數據，所述距離 數據以下會更詳細解釋。本領域技術人員會認識到，算法102可以包括衝 突檢測核，其由在支持引擎100的計算系統上執行的3D圖形應用程式(未 示出)產生。可替換地，算法102可以包括由像素著色器108產生的衝突 檢測核。本領域技術人員還會認識到，術語對象、幾何結構、多邊形、體和多面體可以互換地使用。
紋理採樣器104可以是能夠根據由算法102提供的一個或多個查詢索 引來訪問存儲器106中的紋理數據的任何紋理採樣邏輯，包括硬體、軟體 和域固件的任何組合。根據本發明的一些實施方式，存儲在存儲器106中 並由採樣器104訪問的紋理數據可以包括紋理圖，例如立方體圖，其包括 存儲距離值的像素(或"紋理像素(texds)")陣列，所述距離值以下會更 詳細解釋。採樣器104隨後可以使用由算法102提供的索引來確定用於訪 問存儲和/或保存在存儲器106中的相應距離值的相關紋理地址。採樣器104 隨後可以使用這些距離值產生插值的距離值，並可以將這些插值距離值提 供給算法102，如以下會更詳細說明的。可替換地，採樣器104可以將這些 距離值提供給著色器108，著色器108可以產生插值距離值，並將這些插值 距離值提供給算糹去102。
紋理存儲器106可以包括適合於存儲和/或保存一個或多個紋理圖(例 如一個或多個立方體圖)的任何存儲裝置或機構，並指定了紋理像素數據， 例如距離值。儘管存儲器106可以包括任何易失性或非易失性存儲技術， 例如隨機存取存儲器(RAM)存儲器或快閃記憶體，但是本發明決不受所使用的 用作存儲器106的存儲器類型的限制。
圖2是示出根據本發明一些實施方式的處理處理過程200的流程圖。 儘管為了易於解釋，可以針對圖1的引擎100來說明處理過程200，但所要 求發明不限於這一點，由根據所聲明的發明的適當裝置支持的其它處理過 程或方案也是可行的。
處理過程200可以開始於第一多面體的接收[動作202]和第二多面體的 接收[動作204]。根據一些實施方式，動作202和204例如可以包括衝突檢 測算法102接收第一和第二三角形的頂點坐標，例如，在這裡相對於可由 3D圖形應用程式(未示出)實現的一個模型坐標系來定義這些坐標。這個 3D圖形應用程式可以產生算法102，並可以為算法102提供幾何圖元，例 如三角形。
本領域技術人員會認識到，作為總衝突檢測過程的一部分，算法102 在動作202和204之前可能已經使用空間數據結構(例如八叉樹或kd樹) 使3D圖形對象經過了瑣碎拒絕階段(trivial reject phase)。在如此進行時，算法102可能已經確定了兩個對象， 一個包括動作202的第一多面體，另 一個包括動作204的第二多面體，已經通過了這個瑣碎拒絕階段，從而這 兩個對象是進一步衝突檢測測試的候選。與進行衝突檢測過程的瑣碎拒絕 階段的各種方法有關的細節超出了所聲明的發明的範圍，並且是本領域公 知的。
處理過程200還可以包括產生用於存儲距離值的紋理圖[動作206〗。 根據本發明的一些實施方式，可以在處理過程200中任何其它步驟之前進 行的預處理階段中，由應用軟體來進行動作206。在本發明的其它實施方式 中，可以在與處理過程200的其它動作同時的運行時間中，由應用軟體來 進行動作206。無論如何，本發明不受何時進行動作206的限制。
圖3是示出了處理過程300的流程圖，根據本發明一些實施，可以進 行處理過程300來產生根據處理過程200的動作206的用於存儲距離值的 紋理圖。儘管為了易於解釋，可以針對圖1的引擎IOO來說明處理過程300， 但所聲明的發明不限於這一點，由根據所聲明的發明的適當裝置支持的其 它處理過程或方案也是可行的。
圖4示出了一個代表性的立方體圖標記方案400，雖然該方案400有助 於對處理過程300和/或相關處理過程的論述，但是其決不應解釋為限制所 聲明的發明。方案400顯示了3D立方體元402,如本領域技術人員會 認識到的，圖元402可以對應於如由公知的3D圖形應用程式(例如DirectX) 所定義的標準立方體元，儘管本發明並不限於具體的立方體元。 圖402可以由6個二維(2D)紋理圖404-409組成，這些紋理圖被排列為 立方體的面，其中，圖404-409每一個都可以包括8X8的像素陣列，並且 其中，圖404-409中的每一個像素都能夠存儲浮點距離值，如以下會更詳細 解釋的。然而，本發明並不限於圖404-409的特定解析度，且本發明也不限 於在圖404-409中的像素位置上所存儲的數據類型。而且，本領域技術人員 會認識到，3D立方體圖402的2D圖404-409每一個都可以被視為是數值 的査詢表，這些數值可以通過使用指定圖404-409的具體像素的索引來訪 問。
如本領域技術人員會認識到的，2D圖404-409中的每一個像素的坐標 都可以由3D方向向量410來索引，該方向向量以立方體圖402的原點412為起點。在本發明的一些實施方式中，原點412可以對應於對象(例如多 面體)的質心，如以下會更詳細解釋的。然而，本發明不限於如何定義原 點412，因此，例如，原點412可以包括對象的外心。本領域技術人員還會 認識到，可以定義一組唯一的方向向量，以使得這組向量中的每一個向量 都穿過一個2D圖404-409中的相應像素。例如，向量410穿過圖408中的 像素414，在此圖408對應於立方體圖402的+X面，並且在此像素414可 以對應於圖402的一個具體的(u，v)紋理坐標對。因此，向量410可以由原 點412和對應於像素414的紋理坐標對來定義。
根據本發明的一些實施方式，原點412可以是對象的質心或對象的外 心。然而本發明不限於這一點，因此原點412可以包括位於對象內的任何 點。而且，儘管在處理過程200和300中所用的紋理圖元可以包括立方體 元，但本發明不限於這一點，因此，例如，可以使用其它3D紋理圖元 來進行處理過程200和300，例如採用了多於6個2D面的紋理圖元，或者 例如拋物面或球面紋理圖元。
處理過程300可以開始於對第一多面體的原點的確定[動作302]，在此 該多面體與在處理過程200的動作202中所接收的多面體是同一個多面體。 本領域技術人員會將用於確定多面體的包圍球(bounding sphere)的公知技 術認知為根據動作302確定多面體原點的一種方式。為了論述的原因，圖5 示出了方案500，其用於根據動作302的一些實施方式確定包圍球。儘管為 了說明的目的，圖5以2D形式示出了包圍球502和相關的多面體504，但 可以在產生3D包圍球的3D多面體上進行動作302的實施。
本領域技術人員會認識到，包圍球502表示一個假定球面，該假定球 面包圍多面體504，從而使球面502的標量半徑505定義了從該球的中心 506到多面體504任意點的最大距離。當如此定義時，球502的中心506表 示多面體504的質心。因此，作為動作302的結果，可以確定第一多面體 的原點，例如質心。然而，如上指出的，本發明並不限於如何確定或定義 對象的原點。因此，根據本發明，可以使用任一任意手段來確定要由處理 過程300處理的3D對象的原點。
處理過程300可以繼續進行到接收立方體元[動作304]，在此該圖 元包括6個2D紋理像素陣列。如上所述，立方體圖是公知的3D圖形圖元類型。處理過程300隨後可以繼續到確定從第一多面體的原點沿著以該原 點為起點並穿過立方體圖的像素的方向，到與第一多面體的面的交點之間 的距離值[動作306]。
圖6示出了方案600，用於根據動作306的一些實施確定距離值。圖6 顯示了多面體602和立方體圖604的2D橫截面。儘管為了說明的目的，圖 6示出了多面體602和圖604的2D橫截面，但可以對3D多面體進行動作 306的執行，導致了相對於3D立方體圖的距離值的確定。圖6顯示了圖604 的一個面608的像素Pl-P7的一個行606，在此，根據動作306的一些實施， 可以沿8個唯一方向612確定距離值，在此每一個方向612都在多面體602 的原點614開始，並穿過像素606之中單獨的一個。因此，例如，穿過像 素P7的方向616具有與多面體602的一個面的交點618和距離值620，距 離值620定義為在原點614與像素P7的位置之間以紋理空間單位計的距離。 以類似的方式，可以為圖6中的所有方向612，以及為立方體圖604的剩餘 像素的所有其它方向(未示出)，確定根據動作306的距離值。
儘管圖6顯示了立方體圖604的橫截面，在此圖604的每一面都可以 包括8X8像素陣列，從而使立方體圖604可以包括總共144個像素，但是 本發明並不限於在處理過程200和300中所用的立方體圖的具體解析度。 因此，例如，可以對在處理過程300中所處理的每一個多面體以不同分辨 率的立方體圖來進行動作306。例如，在動作302中接收的立方體圖可以包 括6個2D 16X16像素陣列，從而使得在處理過程200和300中所用的立 方體圖可以包括總共1,536個像素。可替換地，在動作302中接收的立方體 圖可以包括6個2D 4X4像素陣列，從而使得在處理過程200和300中所 用的立方體圖可以包括總共96個像素。而且，本領域技術人員會認識到， 可以通過僅沿方向的一個子集(例如僅沿方向612的子集)確定距離值並 且由在動作306中所確定的距離值對之間的線性內插值來確定剩餘的距離 值，來進行動作306。
處理過程300可以繼續進行到將距離值存儲為立方體圖的像素值[動作 308]。根據本發明的一些實施方式，動作308可以包括將在動作306中確定 的每一個距離值存儲為位於與該距離值相關的方向上的像素的像素值。例 如，如果動作306包括確定與方向616相關的距離值620，那麼動作308就
ii可以包括將距離值620存儲為位於方向616上的像素P7的像素值。在本發 明的一些實施方式中，在動作306中確定且在動作308中存儲的那些距離 值可以包括浮點值，儘管本發明不限於具有特定數據格式的距離值。
而且，儘管在此提供的詳細說明指的是凸多面體，例如多面體504或 多面體602，但本發明並不限於這一點，在處理過程200/300中也可以使用 凹多面體。本領域技術人員會認識到，可以將凸多面體定義為這樣的一個 對象，即其中，連接該對象的任意兩點的任何完整直線段都完全包含在該 對象內，而可以將凹多面體定義為這樣的一個對象，即其中，可以找到連 接該對象的兩個點的一條完整直線段，其中該線段並不完全包含在該對象 內。
為了在處理過程200/300中使用凹多面體，可以確定與凹多面體的凸包 (convexhull)的包圍體，在此該凸包包圍體所具有的標量半徑對應於該對 象的原點與該對象的任意點之間的最大距離值。隨後可以在動作302中使 用這個凸包包圍體。可替換地，可以使用凸分解技術將凹幾何體劃分為更 小的凸幾何體。隨後可以使用處理過程200/300來檢測在這些凸子幾何體之 間的衝突。凸包包圍體和凸分解技術是本領域公知的，在此不再更詳細論 述。
再次參考處理過程200，在本發明的一些實施方式中，應用程式，例如 3D圖形應用程式，可以進行處理過程300在預處理階段中的所有動作(即 在進行處理過程200之前)，並在動作206中向算法102提供產生的紋理圖。 可替換地，在本發明的其它實施方式中，算法102可以響應於在由引擎100 執行的3D渲染期間發生的每一個衝突檢測事件，以動態方式進行處理過程 300。此外，對於在動作202中接收的每一個多面體，可能已經在處理過程 300中產生了 (即在動作206中產生了 )用於存儲該多面體的距離值的相關 立方體圖，並且可以在處理過程300的進一步動作中使用，如在以下更詳 細解釋的。根據本發明的一些實施方式，處理過程300可以產生立方體圖， 其保存或存儲在存儲器106中，在此，該立方體圖存儲了特定多面體的距 離值。
處理過程200可以繼續進行到確定從第一多面體的原點到第二多面體 的頂點的第一距離值[動作208]，在此第一距離沿著從第一多面體的原點延伸到第二多面體的頂點的方向向量。圖7示出了方案700,用於根據動作 208的一些實施方式來確定第一距離值。
圖7顯示了第一多面體702和第二多面體704，在此，根據動作208的 一些實施方式，可以在多面體702的原點706與多面體704的頂點708之 間沿方向向量710確定第一距離值705，方冋向量710從原點706開始並穿 過頂點708。類似地，例如，動作208可以包括確定在原點706與多面體 704的頂點714之間沿方向向量715的第一距離值712，方向向量715從原 點706開始並穿過頂點714。儘管為了說明的目的，圖7示出了多面體702 和704的2D橫截面，但可以針對3D多面體來進行動作208的執行，其導 致沿著由3D坐標定義的方向向量的第一距離值的確定。在本發明的一些實 施方式中，可以在相應的動作202和204中接收到第一和第二多面體之後， 由算法102來進行動作208。
處理過程200隨後可以繼續進行到通過執行對紋理圖的一個或多個查 詢，來確定沿方向向量從第一多面體的原點到第一多面體的一個面的第二 距離[動作210]。再次參考圖7，在本發明的一些實施方式中，動作210可 以包括確定例如沿方向向量710從原點706到多面體702的面722的第二 距離720。在該實例中，確定第二距離720可以包括査詢在動作206中所 產生的紋理圖的像素725和726 (即動作308中)處存儲的距離值(即在 306中確定的)，並隨後在這些距離值之間進行線性內插值，以便在動作210 中獲得第二距離720。
類似地，例如，動作210可以包括確定沿方向向量715從原點706到 面722的第二距離724。然後，在該實例中，確定第二距離724可以包括 查詢在動作206中所產生的紋理圖的像素727和728處存儲的距離值，隨 後在這些距離值之間進行線性內插值，以便在動作210中獲得第二距離724。 在本發明的一些實施方式中，動作210可以包括算法102為紋理採樣器104 提供像素相關的查詢索引(例如像素725和726或像素727和728)。採樣 器104隨後可以使用這些索引來產生相應的存儲器地址，用於訪問在存儲 器106中所存儲的立方體圖的相應像素的距離值。採樣器104隨後可以在 這些距離值之間進行線性內插值，並向算法102提供產生的插值距離值。 可替換地，採樣器104可以向算法102提供距離值，算法102可以在這些值之間進行線性內插值，以便在動作210中確定第二距離。
儘管在圖7中將每一個方向向量710和715都顯示為經過或指定了分 別位於像素725和726及像素727和728之間的紋理坐標對，但本發明並 不限於圖7中所示的2D表示。因此，例如，方向向量710和715任何一個 都可以經過或指定位於立方體圖的一個面的兩個像素行或列之間的紋理坐 標對。因此，動作210可以包括使用4個查詢索引來訪問在約束該紋理 坐標對的這4個像素處存儲的距離值，並隨後在這4個距離值之間進行雙 線性內插值，以獲得第二距離值。然而，本發明不限於線性內插值(雙線 性、三線性或其它的)。因此，例如，可以使用從紋理圖獲得的距離值的最 近的點採樣來進行動作210。
在本發明的其它實施方式中，動作210可以包括算法102,算法102為 像素著色器108提供了與像素(例如像素725和726或像素727和728)相 關的查詢索引，並且著色器108可以將這些索引傳送到紋理採樣器104。採 樣器104隨後可以使用這些索引來產生相應的存儲器地址，用於訪問在存 儲器106中所存儲的立方體圖的相應像素的距離值，並將這些距離值提供 給著色器108。著色器108隨後可以在這些距離值之間進行線性內插值，並 將產生的插值距離值提供給算法102。可替換地，著色器108可以將距離值 提供給算法102，算法102可以在這些值之間進行線性內插值，以便在動作 210中確定第二距離。
處理過程200可以隨後繼續進行到比較第一距離值與第二距離值[動作 212]，如果第二距離大於或等於第一距離，就檢測到在第一和第二多面體之 間的衝突[動作216]。再次參考圖7，動作212例如可以包括沿方向向量710 比較第一距離705與第二距離720。在此情況下，第一距離705大於第二距 離720，將不會檢測到衝突。然而，對於另一個實例，動作212可以包括沿 方向向量715比較第一距離712和第二距離724。在此情況下，第二距離 724大於第一距離712，因此在動作216中檢測到衝突。在本發明的一些實 施方式中，算法102可以進行動作212的比較，並且如果第二距離大於或 等於第一距離，則在動作216中確定發生衝突。
儘管如上所述的動作208和210分別指的是確定第一和第二距離，且 儘管動作212指的是相互比較這兩個距離，但在本發明其它實施方式中，處理過程200可以包括確定這些距離的平方的動作，隨後在動作212中相 互比較這些距離的平方值。因此，在這些實施方式中，動作214可以包括 確定第二距離的平方是否大於或等於第一距離的平方。然而，本發明不限 於在動作212中比較距離或比較距離的平方。因此，例如，處理過程200 可以包括確定這些距離的平方根的動作，隨後在動作212中相互比較這些 距離的平方根值。
不必按所示的順序執行在圖2和3中所示的動作；也不必執行所有的 動作。此外，那些不依賴於其它動作的動作可以與所述其它動作並行地執 行。例如，可以並行地進行動作202和204。可替換地，可以將動作202和 204合併到單一動作中。換句話說，可以在單一動作中進行對第一和第二多 面體的接收。另外，如上指出的，動作206，即根據本發明一些實施方式的 立方體圖的產生，可以在處理過程200的所有其它動作之前進行，或者可 替換地，動作206可以在動作202或204之後進行或與其並行進行。此外， 在該附圖中的至少一些動作可以實現為指令或指令組，所述指令或指令組 在機器可讀介質中實現。
在本發明的一些實施方式中，在處理過程200和/或300中所用的算法 102可以包括以下偽代碼
Collision—Detection_Using_Cubemaps(...) bool Collision = false; Foreach vertex V2j of polygon P2 { Direction Vector = V2j — Ci; dl =texCube (DirectionVector}; d2 = distance (C! ， V2J}; if(dl 〉= d2){ Collision = true; break; 〃衝突
If (Collision) {
//對衝突的相應進行建模} else {
〃無衝突，繼續進行，以評估下一對幾何體的衝突檢測
在本發明的其它實施方式中，在處理過程200和/或300中所用的算法 102可以由引擎100的像素著色器108產生或與其相關聯，並可以包括以下 高級著色語言(shading language)像素著色器代碼 PS—OUTPUT CollisionDetectionPS ( VS—OUTPUT In,
uniform bool bTexture)
PS_OUTPUT Output; int Index = 0; float sum = 0.0;
float fActualDist， fCubeMapDist;
float4 temp = (0， 0， 0， 1);
float4 ^VorldPos， M^orldCentroid, dir;
bool collision = false;
float2 tex;
//bool results[115];
int trouble = 0;
Output.RGBColor.r = Output.RGBColor.g = Output.RGBColor.b = Output.RGBColor.a = 0.0;
〃這些是用於索引像素中心並訪問對象的位置數據的紋理(u,v)坐標
float disp = 0.5/g一iNumVertices[l]; tex.y = 0.5
//對象O的重心的全局位置
WorldCentroid = mul (g—vCentroids[O], g_mWorldMat0);〃經過對象1的所有頂點的射線
for( Index = 0; Index < g一iNumVertices[l]; Index++)
tex.x = Index/g—iNumVertices[l] + disp;
//得到在紋理中存儲的對象1的頂點位置 WorldPos = tex2D (g一samPositionsl， tex);
//轉換到全局空間
WorldPos = mul (WorWPos， g一mWor畫atl); dir = WorldPos - WorldCentroid;
fActualDist = sqrt (dir.x*dir.x + dir.y*dir.y + dir.z*dir.z);
〃將方向轉換回通過與對象o的全局矩陣的逆相乘產生立方體圖的空間
dir = mul (dir， g一mWorldMatOInv); dir = normalize(dir);
temp = texCUBE(g一samCubeMapDistanceO， dir); fCubeMapDist = temp.x;
if (fCubeMapDist〉 fActualDist) { collision = true;
〃進行與以上相同的計算，但是切換對象。從而現在循環遍歷對象O的頂點 disp = 0.5/g_iNumVertices
;
WorldCentroid = mul(g一vCentroids[l], g—mWorldMatl); for( Index = 0; Index < g—iNumVertices[O]; Index++ )
17tex.x = Index/14.0 + disp;
WorldPos = tex2D (g—samPositionsO, tex);
WorldPos = mul (WorldPos， g_mWorldMatO);
dir = WorldPos - WoridCentroid;
fActualDist = sqrt (dir.x*dir.x + dir.y*dir.y + dir.z*dir.z);
dir = mul (dir, g—mWorldMatllnv); dir = normalize (dir);
temp = texCUBE (g_samCubeMapDistancel， dir); fCubeMapDist = temp.x; if (fCubeMapDist > fActualDist) { collision = true;
if (collision = true) {
OutputRGBColor.r = Output.RGBColor.g = Output RGBColor.b = 1.0;
Output.RGBColor.a= 1.0;
return Output;
圖8示出了根據本發明一些實施方式的實例系統800。系統500可以包 括具有兩個或更多個處理內核803的主處理器802、圖形處理器804、存儲 器806和808 (例如動態隨機存取存儲器(DRAM)、靜態隨機存取存儲器 (SRAM)、非易失性存儲器等)、總線或通信通路810，網絡接口814 (例 如有線和/或無線區域網(LAN)和/或廣域網(WAN)和/或個域網(PAN)， 和/或其它有線和/或無線網絡接口)、以及顯示處理器和/或控制器816。系統800還可以包括天線815 (例如偶極天線，窄帶曲折線型天線(MLA)， 寬帶MLA,倒"F"型天線，平面倒"F"型天線，Goubau天線，貼片天 線(Patch antenna)等)，其耦合到網絡接口 814。系統800可以是適合於處 理3D圖形數據並以光柵化形式提供該數據的任何系統，光柵化形式的數據 適合於在顯示裝置(未示出)上的呈現，列舉幾個實例，所述顯示裝置例 如為液晶顯示器(LCD)、或陰極射線管(CRT)顯示器。
系統800可以採取多種物理實現方式。例如，系統800可以在個人計 算機(PC)、聯網的PC、伺服器計算系統、手持計算平臺(例如個人數字 助理(PDA))、遊戲系統(可攜式的或其它形式的)，3D蜂窩電話手機等 中實現。而且，儘管可以在單個裝置中實現系統800的所有組件，例如芯 片上系統(SOC)集成電路(IC)，但系統800的組件也可以分布在多個IC 或裝置中。例如，可以將主處理器802連同組件806和814實現為包含在 單個PC內的多個IC，而圖形處理器804及組件808和816可以在一個分 離的裝置中實現，例如通過通信通路810耦合到主處理器802及組件806 和814上的電視機或其它顯示器。
主處理器802可以包括專用或通用處理器，其包括能夠為圖形處理器 504提供3D圖形數據和/或指令的任何控制和/或處理邏輯、硬體、軟體和/ 或固件。處理器802可以執行各種3D圖形計算，例如3D坐標變換等，其 結果可以通過總線810提供給圖形處理器804，和/或可以存儲在存儲器806 和/或808中用於由處理器804最終使用。在本發明的一些實施方式中，主 處理器802可以是中央處理單元(CPU)。
在一個實施方式中，主處理器802能夠執行支持或實現使用立方體圖 的實時的、多解析度的3D衝突檢測的任何數量的任務。支持的任務例如可 以包括向圖形處理器804提供3D圖形數據；在存儲器808中設置一個或 多個紋理圖，例如立方體圖；將微代碼(經由天線815和接口 814)下載到 處理器804;初始化和/或配置處理器804中的寄存器；中斷服務；以及提
供總線接口，用於上載和/或下載3D圖形數據，儘管本發明並不限於這一 點。在可替換的實施方式中，可以由圖形處理器804執行這些功能中的一 些或全部。儘管圖5將主處理器802和圖形處理器804顯示為不同組件， 但本發明不限於這一點，本領域技術人員會認識到，除了系統800的其它
19組件之外，處理器802和804也可以在單一 IC內實現。
根據本發明的一些實施方式，每一個內核803都可以使用衝突檢測算 法102的不同實現針對不同多面體對並行地執行處理過程200/300。可替換 地，這種並行處理方案可以由圖形處理器804來實現。
圖形處理器804可以包括能夠處理圖形數據的任何處理邏輯、硬體、 軟體和/或固件。在一個實施方式中，圖形處理器804可以實現能夠根據一 個或多個標準化渲染應用編程接口 (API)來處理圖形數據的3D圖形架構， 列舉幾個實例，所述標準化渲染應用編程接口 (API)例如為OpenGL2.0 ("The OpenGL Graphics System: A Specification" (2.0版；2004年10月22 日))和DirectX9.W(9.0c版；2004年8月8日)，儘管本發明不限於這一點。 圖形處理器804可以處理由主處理器802提供的、保存或存儲在存儲器806 和/或808中的、和/或由系統800外部的源提供並通過總線810從接口 814 獲得的3D圖形數據。
圖形處理器804可以接收3D場景數據形式的3D圖形數據，並處理該 數據，以便以合適的形式提供圖像數據，該形式適於由顯示處理器816轉 換為顯示器專用數據。另外，除了類似於紋理採樣器104的一個或多個紋 理採樣器之外，圖形處理器804還可以實現多種3D圖形處理組件和/或級 (未示出)，例如光柵化器級。由圖形處理器804實現的紋理採樣器可以讀 取或訪問在存儲器806和808的任意一個或二者中以立方體圖形式存儲或 保存的紋理數據。此外，根據本發明的一些實施方式，圖形處理器804可 以實現能夠使用存儲在一個或多個立方體圖中的距離值來以並行方式對多 對多面體進行衝突檢測的兩個或更多個紋理採樣器。
總線或通信通路810可以包括用於在系統800的任意元件之間傳送信 息(例如圖形數據、指令等)的任何機制。例如，通信通路810可以包括 能夠在處理器802與處理器804之間傳送例如指令(例如宏代碼)的多用 途總線，儘管本發明不限於這一點。可替換地，通路810可以包括無線通 信通路。
顯示處理器816可以包括能夠將由圖形處理器804提供的光柵化圖像 數據轉換為適於驅動顯示器的格式(即顯示器專用數據)的任何處理邏輯、 硬體、軟體和/或固件。例如，處理器804可以將圖像數據以特定顏色數據格式提供給處理器816，例如以壓縮的紅-綠-藍(RGB)格式，並且處理器 816可以通過產生例如相應的LCD驅動數據級等來處理此類RGB數據，盡 管本發明並不限於這一點。儘管圖8將處理器804和816顯示為不同的組 件，但本發明不並限於這一點，本領域技術人員會認識到，例如顯示處理 器816的一部分功能或全部功能可以由圖形處理器804和/或主處理器802 來執行。
因此，通過利用硬體圖元，例如立方體圖，根據本發明的衝突檢測算 法可以完全在圖形處理器(例如處理器804)上執行，該情況(有可能)排 除了處理過程300的預處理，處理過程300的預處理可以對每一個多面體 執行一次並且可以在處理過程200之前進行。此外，根據本發明的衝突檢 測算法能夠平衡(leverage)高級八叉樹結構，以使得對象-對象檢測最小化， 並且對於由八叉樹數據結構確認為候選的對象-對象交互，可以依賴於立方 體圖。因此，通過將衝突檢測算法移到圖形處理器(例如處理器804)，可 以釋放CPU (例如主處理器802)來承擔其它任務。儘管如此，根據本發 明的衝突檢測算法也可以在CPU上執行。而且，使用諸如立方體圖之類的 硬體圖元來檢測衝突會實現每一個衝突的數學運算的相當大的減少(可能 多達三倍的減少)，並且由於執行完全獨立於衝突檢測測試這一能力，因此 能夠進行多處理內核實現(例如使用內核803)。
儘管與所聲明的發明一致的一個或多個具體實例的在前說明提供了對 本發明的例證和說明，但是其意圖不是窮舉性的或將本發明的範圍限制為 所公開的具體實施方式
。明確而言，按照以上的教導，可以有多種修改和 變化，或者可以從本發明的各種實施方式的實現中獲得多種修改和變化。 例如，儘管圖1和附屬的文字顯示並說明了耦合到單一紋理存儲器106的 單一紋理採樣器104，但本領域技術人員會認識到，根據本發明的數據處理 器可以包括採用多個紋理採樣器的渲染引擎，每一個紋理採樣器都按照本 發明進行操作，並耦合到一個或多個紋理存儲器。明確而言，可以使用許 多其它實施方式來提供根據本發明的使用立方體圖的實時的、多解析度的 3D衝突檢測。
在本申請的說明中闡述的裝置、元件、動作、數據類型、指令等都不 應解釋為對本發明是關鍵性或不可缺少的，除非明確表述為如此。此外，如在此所用的，冠詞"一"意圖包括一個或多個項。而且，當在此或附帶 的權利要求中使用諸如"耦合的"或"響應的"或"與……通信"之類的 術語或短語時，這些術語意圖是作最廣泛的理解。例如短語"耦合到"可 以指的是按照對於使用該短語的上下文適當的方式可通信地、電氣地、和/ 或可操作地進行耦合。在實質上不脫離本發明的精神和原理的情況下，可 以對所聲明的發明的上述實施方式做出多種改變和修改。所有此類修改和 改變都意圖在此包括在本公開內容的範圍內，並受到附帶的權利要求的保 護。
權利要求
1、一種方法，包括接收第一多面體；接收第二多面體；及使用存儲在存儲器中的紋理圖來檢測在所述第一多面體和所述第二多面體之間的衝突。
2、 如權利要求l所述的方法，其中，所述紋理圖包括立方體圖，其存儲在所述第一多面體的原點與所述第一多面體的所有面之間的距離。
3、 如權利要求2所述的方法，其中，所述第一多面體的所述原點是所述第一多面體的包圍球的質心或所述第一多面體的外心兩者中的一個。
4、 如權利要求2所述的方法，其中，使用所述紋理圖來檢測在所述第一多面體和所述第二多面體之間的衝突的步驟包括確定第一距離，該第一距離對應於從所述原點到所述第二多面體的頂點的距離，所述第一多面體的所述原點與所述第二多面體的所述頂點定義了方向向量；通過使用對所述立方體圖的紋理地址的查詢，沿著所述方向向量確定第二距離，該第二距離對應於從所述第一多面體的所述原點到所述第一多面體的面的距離；及比較所述第一距離與所述第二距離。
5、 如權利要求4所述的方法，其中，比較所述第一距離與所述第二距離的步驟包括比較所述第一距離的平方與所述第二距離的平方。
6、 如權利要求4所述的方法，還包括如果所述第二距離大於或等於所述第一距離，則在所述第一多面體和所述第二多面體之間檢測到衝突。
7、 如權利要求l所述的方法，還包括藉助於以下步驟來產生所述紋理圖確定所述第一多面體的質心；確定從所述質心到所述第一多面體的所有面的多個距離，其中，沿著多個向量中的相應向量確定所述多個距離中的每一個距離，所述多個向量中的每一個向量都從所述質心開始並穿過所述紋理圖的相應元素；及將所述多個距離中的每一個距離存儲為所述紋理圖中所述相應元素的值。
8、 一種產品，包括機器可訪問介質，具有存儲在其上的指令，該指令當由機器執行時，使得所述機器接收第一多面體；接收第二多面體；及使用存儲在存儲器中的紋理圖來檢測在所述第一多面體和所述第二多面體之間的衝突。
9、 如權利要求8所述的產品，其中，所述紋理圖包括立方體圖，其存儲在所述第一多面體的原點與所述第一多面體的所有面之間的距離。
10、 如權利要求8所述的產品，其中，所述第一多面體的所述原點是所述第一多面體的包圍球的質心或所述第一多面體的外心兩者中的一個。
11、 如權利要求8所述的產品，其中，用於使用所述紋理圖來檢測在所述第一多面體和所述第二多面體之間的衝突的所述指令當由機器執行時，使得所述機器確定第一距離，該第一距離對應於從所述原點到所述第二多面體的頂點的距離，所述第一多面體的所述原點與所述第二多面體的所述頂點定義了方向向量；通過使用對所述立方體圖的紋理地址的查詢，沿著所述方向向量確定第二距離，該第二距離對應於從所述第一多面體的所述原點到所述第一多面體的面的距離；及比較所述第一距離與所述第二距離。
12、 如權利要求ll所述的產品，還包括存儲在其上的指令，該指令當由機器執行時，使得所述機器如果所述第二距離大於或等於所述第一距離，則在所述第一多面體和所述第二多面體之間檢測到衝突。
13、 如權利要求8所述的產品，還包括存儲在其上的指令，該指令當由機器執行時，使得所述機器藉助於以下步驟來產生所述紋理圖確定所述第一多面體的質心；確定從所述質心到所述第一多面體的所有面的多個距離，其中，沿著多個向量中的相應向量確定所述多個距離中的每一個距離，所述多個向量中的每一個向量都從所述質心開始並穿過所述紋理圖的相應元素；及將所述多個距離中的每一個距離存儲為所述紋理圖中所述相應元素的值。
14、 一種裝置，包括存儲器，其存儲紋理圖，所述紋理圖包括存儲距離值的像素；紋理採樣邏輯，其接收一個或多個查詢索引，所述一個或多個査詢索引由衝突檢測算法確定，所述查詢索引指定所述紋理圖的像素，所述紋理採樣邏輯根據所述一個或多個查詢索引而獲得所述距離值。
15、 如權利要求14所述的裝置，其中，所述距離值包括在第一多面體的原點與所述第一多面體的面之間的距離。
16、 如權利要求15所述的裝置，其中，所述紋理圖是立方體圖，並且其中，所述衝突檢測算法通過確定從所述第一多面體的原點到第二多面體的頂點的方向向量來確定所述一個或多個查詢索引，所述方向向量指定了 所述立方體圖的坐標對，所述一個或多個查詢索引指定了 一個或多個立方 體圖像素的紋理坐標，該一個或多個立方體圖像素圍繞由所述方向向量指 定的所述立方體圖的所述坐標對。
17、 如權利要求14所述的裝置，其中，所述存儲器包括以下之一動 態隨機存取存儲器(DRAM)、靜態隨機存取存儲器(SRAM)、或非易失性 存儲器。
18、 如權利要求14所述的裝置，還包括天線，用於接收所述衝突檢測 算法。
19、 如權利要求18所述的裝置，其中，所述天線包括以下之一偶極 天線、窄帶曲折線型天線(MLA)、寬帶MLA、倒"F"型天線、平面倒"F" 型天線、Goubau天線、或貼片天線。
全文摘要
公開了使用立方體圖進行實時的、多解析度的3D衝突檢測的裝置、系統和方法。例如，公開了一種方法，包括接收第一多面體；接收第二多面體，隨後使用存儲在存儲器中的紋理圖檢測在第一和第二多面體之間的衝突。還公開了其它實施方式。
文檔編號G06T15/00GK101496067SQ200780027890
公開日2009年7月29日 申請日期2007年7月12日 優先權日2006年7月28日
發明者A·T·萊克, R·P·薩特 申請人:英特爾公司