在虛擬空間內判斷碰撞及判斷碰撞點的處理方法
2023-10-08 22:18:44 1
專利名稱：在虛擬空間內判斷碰撞及判斷碰撞點的處理方法
技術領域：
本發明有關於一種在虛擬空間內判斷碰撞及判斷碰撞點的處理方法，特別是電腦所模擬出的三維虛擬空間內，判斷出兩個物件是否發生碰撞，以及在發生碰撞之後決定出碰撞點的方法及系統。
目前由於微處理器的速度提高以及各種顯示技術的逐漸成熟和普及，將3D(3維)甚至虛擬實鏡(virtual reality，VR)等等技術應用在電腦遊戲中已經是相當普遍。在一般3D的遊戲中的所有遊戲角色，例如玩家所控制的主角或者是由電腦所控制的敵人，大都是許多個物件所構成。而實際上的每個物件都代表了整個物體內的一個部分，這些部分在物體移動旋轉時做為一個整體，一起移動旋轉，例如人體上的頭部、胸部等等。然而，這些物件也各自有其與其他物件不同的特性。例如人體上的手部可以擺動。如此，即構成一個3D空間上的物體模型。
在一般的3D遊戲中，特別是屬於3D類型的格鬥遊戲，經常需要使用到物體之間的碰撞判斷。然而對於大部分呈現不規則形狀的3D物體而言，要能夠精確地判斷出是否發生碰撞是一件相當複雜的工作。因此，一般的作法是將構成3D物體的每個物件利用一個立體的矩形範圍框加以涵蓋，再對矩形框進行碰撞的判斷，以其結果作為物體之間是否發生碰撞的判斷基準。
圖1表示在一般3D虛擬空間中物體間發出碰撞的示意圖。圖中，對打的雙方分別為利用多邊形所構成的甲方12和乙方14。甲方12上所具有的劍部分，是由矩形範圍框12a所包圍，用以定義此劍部分的範圍。另外，乙方14上所具有的腰部，則是由矩形範圍框14a所包圍，用以定義乙方14的腰部。至於其餘部分的範圍框則加以省略不予標示。如圖所示，當甲方12揮動劍擊向乙方14的腰部時，判斷是否發生碰撞的標準是根據矩形範圍框12a是否切入矩形範圍框14a而決定。當矩形範圍框12a被判斷出已經切入矩形範圍框14a時，表示發生了碰撞。接著遊戲程序可以決定出碰撞點，並且在該處產生預設特效，如爆炸效果等等。
一般的矩形範圍框在3D空間內可以利用兩個坐標點，亦即最大端點(maximum end-point)和最小端點(manimum end-point)來加以表示。最大端點是表示在該矩形的所有點中，其坐標值(包括X坐標值、Y坐標值和Z坐標值)皆為最大，最小端點是表示在該矩形的所有點中，其坐標值皆為最小。圖2表示在3D空間中一物件和其矩形範圍框的示意圖。物件20是由矩形範圍框10所包圍，做為其判斷碰撞時的基準點。在矩形範圍框10的八個端點上，分別標示為這、P2、P3、P4、P5、P6、P7、P8，其坐標分別為(3，3，3)、(6，3，3)、(6，3，6)、(3，3，6)、(3，6，3)、(6，6，3)、(6，6，6)、(3，6，6)。根據圖中所示的坐標(X軸、Y軸、Z軸)，各坐標軸的箭點部分均表示坐標值增加的方向。因此，在矩形範圍框10中的端點P1即為最小端點，坐標值為(3，3，3)，在矩形範圍框10中的端點P7即為最大端點，坐標值為(6，6，6)。
以下配合
習知技術中判斷是否發生碰撞以及在碰撞後決定碰撞點的處理方法。圖3表示在3D空間中兩物件的矩形範圍框發生碰撞的第一例示意圖。在圖3中，矩形範圍框10a和10b分別表示3D空間中兩個物件的矩形範圍框。矩形範圍框10a上具有端點P11、P12、P13、P14、P15、P16、P17、P18，矩形範圍框10b上則具有端點P21、P22、P23、P24、P25、P26、P27、P28。以下為方便說明，將3D空間上各點的坐標值分別以下列方式標示點P的X坐標值表示為P.X，Y坐標值表示為P.Y，Z坐標值表示為P.Z。另外，如前所述，每一個矩形範圍框可以利用其最大端點和最小端點來定出其範圍，例如範圍框10a中的端點P11和P17分別為其最小端點和最大端點，範圍框10b中的端點P21和P29分別為其最小端點和最大端點。
習知的第一種判斷碰撞方法是將第一個矩形範圍框的8個端點分別與第二個矩形範圍框的範圍進行比較，如果有任何一個或是多個端點落在該範圍內，就認定兩個矩形範圍框所代表的物件發生了碰撞；如果沒有任何一個端點落在該範圍內，則認定兩者間沒有發生碰撞。以圖3為例，第一種習知判斷碰撞方法可以根據端點P18落在矩形範圍框10b而決定兩者發生碰撞，或是根據端點P22落在矩形範圍框10a而決定兩者發生碰撞。其詳細的判斷方式如下所述。
當利用矩形範圍框10a的8個端點與矩形範圍框10b的範圍進行比較時，必須依序對8個點進行判斷。以端點P11為例，點P11要落在範圍框10b的充分必要條件為P21.X＜P11.X＜P27.X (1a)P21.Y＜P11.Y＜P27.Y (1b)P21.Z＜P21.Z＜P27.Z (1c)
因此，對於每一個端點而言，都需要進行6次的比較運算。以兩個矩形範圍框來說，就需要進行6×16＝96次的比較運算。
另外，第一種習知判斷碰撞處理方法尚有缺點，即比較的結果較不準確。圖4表示在3D空間中兩物件的矩形範圍框發生碰撞的第二例示意圖，利用第一種習知判斷碰撞處理方法來決定圖4所示情況時，便會出現錯誤的判斷。在圖4中，矩形範圍框10c和10d分別表示3D空間中兩個物件的矩形範圍框，而兩者間是呈現貫穿狀態。矩形範圍框10c上具有端點P41、P42、P43、P44、P45、P46、P47、P58，矩形範圍框10d上則具有端點P31、P32、P33、P34、P35、P36、P37、P38。其中，範圍框10c中的端點P41和P47分別為其最小端點和最大端點，範圍框10d中的端點P31和P37分別為其最小端點和最大端點。
由圖4可以清楚地了解，任何一個矩形範圍框的端點，都不會落入另一個矩形範圍框的範圍內。換言之，利用第一種習知判斷方法對圖4的貫穿情況進行判斷時，根本無法判斷出實際發生碰撞的情況。要對此種情況做出正確的判斷，就必須利用以下所述的第二種習知判斷方法。
第二種習知判斷方法則遠較第一種來得複雜，其主要是利用矩形框邊的12條邊線是否穿過另一個矩形加以判斷，同樣地，每條邊線也是要進行多次的比較判斷運算。以矩形範圍框10d的邊線L1為例，其兩端點分別為端點P31和端點P35。其中，端點P31和端點P35的X坐標值和Z坐標值是相同的，差別是在於其中的Y坐標值。若是相同的X和Z坐標值在矩形範圍框10c的最小端點P41和最大端點47所定義的範圍內，才能可能會通過矩形範圍框10c中。換言之，其條件為P41.X＜P31.X(或P35.X)＜P47.X (2a)P41.Z＜P31.Z(或P35.Z)＜P47.Z (2a)然而，利用公式(2a)和(2b)並無法決定邊線L1必定通過矩形範圍框10d。舉例來說，當圖4中的矩形範圍框1c向下(即負Y方向)平移並且脫離矩形範圍框10d時，仍然可以滿足公式(2a)和(2b)的條件，但是實際此時兩者並未發了碰撞。因此，尚需要對於邊線L1是否真的通過端點P41和端點P47所在平面進行檢驗。
實際判斷時，有三種情況可以會發生。第一種即邊線L1的情況，此時邊線L1會貫穿上、下表面，代表矩形範圍框10d的對應物件為貫穿形狀。第二種即線段L2的情況，其兩端點分別為端點PL21和端點PL22，其中端點PL21是位於矩形範圍框10d的內部，代表矩形範圍框10d所對應物件系以上半部插入。第三種即線段L3的情況，其兩端點分別為端點PL31和端點PL32，其中端點PL32是位於矩形範圍框10d的內部，代表矩形範圍框10d所對應物件系以下半部插入。根據以上所述，要符合線段L1(即貫穿情況)狀態的條件為P35.Y＞P47.Y且P31.Y＜P41.Y(3a)要符合線段L2(即插進上半部)狀態的條件為PL21.Y＞P47.Y且PL22.Y＜P41.Y (3b)要符合線段L3(即插進下半部)狀態的條件為PL31.Y＞P47.Y且PL32.Y＜P41.Y (3c)至於其他情況，就表示兩者沒有發生碰撞。因此，在公式(3a)、(3b)、(3c)中無論在何種情況下，最少要經過兩次的判斷運算。所以，在加上公式(2a)和(2b)中對於X坐標值和Z坐標值中進行的4次判斷運算，總共至少要6次的判斷。再加以兩個矩形範圍框的24條邊線，一共需要有144次的判斷運算。如此龐大數量的運算需要，會耗費相當大的處理器時間，同時也會降低遊戲進行時的流暢性。
無論是第一種或是第二種習知判斷碰撞的方法，都需要使用到相當數量的判斷運算，可以想像要在具有許多物件的3D物體間，判斷出是否發生任何的碰撞，是非常費時的，尤其是第二種的習知判斷方式。而且，第一種的判斷方式在某些情況下仍有可能會發生錯誤。由此可知，習知的判斷方法並非有效率且無錯誤的碰撞判斷方法，所以在實務上實有必要提出一種新的替代方案。
另外，目前亦沒有提出過任何一種方法能夠有效的計算出正確的碰撞點。對於某些情況而言，得到正確的碰撞點是必要的，例如在遊戲軟體中需要使用到碰撞點，來播放各種特效或是其他的處理。目前的作法大多是以碰撞面為準(以第二種習知判斷方法可以獲得)，而以此碰撞面的中點來模擬碰撞點。然而，這種方法實際上是存在有很大誤差。
有鑑於此，本發明的主要目的在於提出一種在虛擬空間內，特別是虛擬3D空間內，來判斷碰撞的處理方法，能夠利用很少數量的運算，藉以獲得快速並且準確的判斷結果。
本發明的另一目的在於提出一種在虛擬空間內判斷碰撞點的處理方法，能夠以更為精確的位置模擬出碰撞點，藉以提高後續處理時的真實程度。
根據以上所述，本發明提出一種在虛擬空間內判斷碰撞的處理方法，特別是用以判斷在3D虛擬空間內判斷第一物件和第二物件之間是否發生碰撞。每一物件具有範圍框，分別由最小端點和最大端點加以定義，做為判斷碰撞的基準。此方法是藉由兩物件範圍框是否有重疊體積來判斷兩物件是否有碰撞。處理方法是首先將對應第一物件和第二物件的最小端點和最大端點的坐標值儲存在存儲器內，構成在虛擬空間內判斷兩物件間發生碰撞的判斷範圍。接著分別兩物件的兩個最小端點的對應坐標值取出比較，再將對應坐標值中較大者組合成第一個判斷端點。同樣地，分別將兩物件的兩個最大端點的對應坐標值取出比較，再將對應坐標值中較小者組合成第二個判斷端點。最後，分別比較第一判斷端點和第二判斷點的對應坐標值，當第二判斷端點的坐標值均分別大於或等於第一判斷端點的對應坐標值時，表示第一物件和第二物件發生碰撞。反之，當第二判斷點的坐標值之任一者小於第一判斷端點的對應坐標值時，表示第一物件和第二物件未發生碰撞。
另外，本發明亦提供一種在虛擬空間內判斷碰撞點的處理方法，用以判斷第一物件和第二物件之間發生碰撞的碰撞點。首先，在判斷出兩者發生碰撞之後，決定對應兩物件的範圍框的中心點，此中心點可以是範圍框的質心。接著，決定出兩範圍框的一種特徵值，例如對角線長度。最後，利用此特徵值的比例來分別兩個中心點所構成的連接線，決定出分割點，此分割點即做為兩物件間的碰撞點。
為使本發明上述目的、特徵和優點能更明顯易懂，下文特舉一較佳實施例，並配合附圖，作詳細說明如下圖1表示在一般3D虛擬空間中物體間發生碰撞的示意圖。
圖2表示在3D空間中一物件和其矩形範圍框的示意圖。
圖3表示在3D空間中兩物件的矩形範圍框發生碰撞的第一例示意圖。
圖4表示在3D空間中兩物件的矩形範圍框發生碰撞的第二例示意圖。
圖5表示應用本實施例的判斷碰撞和判斷碰撞點的系統方塊圖。
圖6表示在本實施例中用以說明判斷碰撞處理方法的3D示意圖。
圖7表示在本實施例中用以說明判斷碰撞點處理方法的3D示意圖。
圖8表示本實施例中的3D格鬥遊戲的控制流程圖。
圖9表示在圖8所示的流程圖中，用以判斷是否發生碰撞的步驟的詳細流程圖。
圖10表示在圖8所示的流程圖中，用以判斷碰撞點位置的步驟的詳細流程圖。
本發明針對在虛擬三維空間內的兩個物件，提出一種新的判斷碰撞以及判斷碰撞點的處理方法及系統。同樣地，此兩個物件的範圍亦是由矩形範圍框來界定，而此矩形範圍框則可以利用最小端點(坐標值相加所得最小之值)和最大端點(坐標值相加所得最大之值)來加以描述。以下以一實施例來詳細描述本發明，此實施例所採用的操作環境為一種3D格鬥遊戲，類似於圖1所示的情況。以下先就本發明判斷碰撞以及判斷碰撞點的技術部分加以說明，接著再詳細說明本實施例的執行步驟。
圖5表示本發明實施例中的硬體結構方塊圖。如圖所示，系統硬體結構中包括了中央處理器1、數學邏輯運算單元3、儲存裝置5、輸入裝置7和顯示裝置9。中央處理器1為系統的中央控制單元，用以執行遊戲主程序，同時也包括控制本實施例中判斷碰撞和判斷碰撞點的處理程序。數學邏輯運算單元3則是可以用來執行數學運算和邏輯運算，例如本實施例中所進行的判斷運算，在部分系統中，數學邏輯運算單元3可以併入中央處理器1，執行相同的功能。儲存裝置5則可利用DRAM等存儲器加以實施，用以儲存進行的遊戲程序，同時也包括3D物件的矩形範圍框的最小端點和最大端點。輸入裝置7則是提供使用者進行遊戲的操作控制，如滑鼠、鍵盤和搖杆等等。顯示器9則是用來顯示3D虛擬空間上的物體。在遊戲程序進行的過程中，顯示器9上會出現操作者所控制的3D物體。上述本實施例系統的硬體結構，可以採用一般個人電腦，或是特定規格的電視遊戲器來加以實施。
圖6表示在本實施例中用以說明判斷碰撞處理方法的3D示意圖。在圖6中，矩形範圍框40和50分別表示3D空間中兩個物件的矩形範圍框。矩形範圍框40上具有端點P51、P52、P53、P54、P55、P56、P57、P58，矩形範圍框50上則具有端點P61、P62、P63、P64、P65，P66、P67、P68。其中，矩形範圍框40中的端點P51和P57分別為其最小端點和最大端點，矩形範圍框50中的端點P61和P67分別為其最小端點和最大端點。
在本發明中判斷碰撞的觀念，是源自於兩矩形範圍框發生碰撞時，必定會出現體積重疊的現象而產生。兩個矩形範圍框一旦發生碰撞，如圖6所示的情況，便會出現碰撞區域30。因此，要判斷是否發生碰撞，只需要檢驗出是否真的出現了所示的碰撞區域30。以下詳述本實施例中檢驗是否出現碰撞區域的方式，然而，本實施例的檢驗方式並非用以限定本發明，熟知此技藝者亦可以依據不同的實際應用環境來調整所採用的方法，仍不脫離本發明之範圍。
在本實施例中，要決定是否發生碰撞區域，首先必須決定出此碰撞區域的最小端點和最大端點。如圖6所示，利用矩形範圍框40的最小端點P51和矩形範圍框50的最小端點P61，可以決定出此碰撞區域的最小端點MIN。詳言之，將X座標值的P51.X和P61.X進行比較，決定出較大值，以圖6為例，較大值為P51.X。接著，將Y座標值的P51.Y和P61.Y進行比較，決定出較大值，以圖6為例，較大值為P61.Y。最後，將Z坐標值的P51.Z和P61.Z進行比較，決定出較大值，以圖6為例，較大值為P61.Z。再將這些最大值組合成該碰撞區域的最小端點，即MIN(P51.X，P61.Y，P61.Z)。此一步驟總共進行了3個比較運算。
另一方面，利用矩形範圍框40的最大端點P57和矩形範圍框50的最大端點P67，可以決定出此碰撞區域的最大端點MAX。詳言之，將X坐標值的P57.X和P67.X進行比較，決定出較小值，以圖6為例，較小值為P67.X。接著，將Y坐標值的57.Y和P67.Y進行比較，決定出較小值，以圖6為例，較小值為P57.Y。最後，將Z坐標值的P57.Z和P67.Z進行比較，決定出較小值，以圖6為例，較小值為P57.Z。再將這些最大值組合成該碰撞區域的最小端點，即MAX(P67.X，P57.Y，P57.Z)。此一步驟中亦進行了3個比較運算。
最後，利用所得的MIN和MAX，可以決定出是否存在此一碰撞區域。要存在碰撞區域30的充分必要條件是端點MAX的所有坐標值，都必須大於或等於端點MIN的對應坐標值。亦即MAX.X≥MIN.X (4a)MAX.Y≥MIN.Y (4b)MAX.Z≥MIN.Z (4c)換言之，只要端點MAX有任何一個坐標值是小於端點MIN的對應坐標值，便可以判斷出不存在此一碰撞區域。此一部分可以輕易地由一般幾何圖形加以驗證，此處不再贅述。在此一步驟中，同樣也只需要使用到3次的比較運算。因此，利用碰撞區域的最小端點和最大端點以及公式(4a)、(4b)、(4c)，即可判斷出兩個矩形範圍框是否發生了碰撞，而所需要的判斷運算，總共只需要6次。
利用上述的本實施例判斷碰撞方法，可以用以檢查圖4的碰撞情況。圖中的碰撞區域即為其中的虛線框部分，利用P31和P41的最大端點以及P37和P47的最小端點，即可得到此虛線部分的最小端點和最大端點。而其最大端點和最小端點是可以滿足公式(4a)、(4b)、(4c)，因此正確判斷現兩者發生了碰撞。由此可知，利用本實施例的判斷方法，的確可以正確地判斷出碰撞的情況。
圖7則是在本實施例中用以說明判斷碰撞點處理方法的3D示意圖。圖中，矩形範圍框60的最小端點MIN1的坐標值為(4，0，1)，最大端點MAX1的坐標值為(8，4，5)。另外，矩形範圍框70的最小端點MIN2的坐標值為(0，3，0)，最大端點MAX2的坐標值為(4，7，4)。首先，判斷兩個矩形範圍框是否發生碰撞。利用MINI和MIN2，可以得到碰撞區域的端點MIN(4，3，1)。利用MAXI和MAX2，可以得到碰撞區域的端點MAX(4，4，4)。其符合公式(4a)、(4b)、(4c)的判斷式，因此已發生了碰撞。必須注意的是，利用其中的X坐標可知，此時兩者實際的碰撞區域體積為零。
接著，要決定兩者間的碰撞點。首先分別決定矩形範圍框60的中心點C1，其坐標值為((4+8)/2，(0+4)/2，(1+5)/2)＝(6，2，3)，以及矩形範圍框70的中心點C2，其坐標值為((0+4)/2，(3+7)/2，(0+4)/2)＝(2，5，2)。本實施例中所設定的碰撞點，即位於中心點C1和C2之間的連線L4上。接著，是利用兩個矩形範圍框的特徵值來決定碰撞點。在本實施例中，此特徵值為其最小端點至最大端點的線段長度，亦即此矩形範圍框的最大對角線長度。以矩形範圍框60為例，其對角線長度為4×sqrt(3)，其中sqrt(.)表示平方根。同樣的，矩形範圍框70的對角線長度亦為4×sqrt(3)。此時利用兩者的對角線長度比例，來分割連線L4，取得一分割點CP。此分割點CP的坐標值為(2，5，2)+((6-2)，(2-5)，(3-2))×4×sqrt(3)/(4×sqrt(3)+4×sqrt(3))＝(4，3.5，2.5)。此時，設定此分割點為碰撞點，可以較精確地決定出兩者碰撞的位置。
利用以上所述的判斷碰撞以及判斷碰撞點的處理方式，以下詳細描述本實施例的細部操作流程。圖8示出本實施例中的3D格鬥的控制流程圖。首先，中央處理器1的遊戲主程序會先在顯示裝置8上畫出打鬥角色的3D模型圖像(S1)，同時也在儲存裝置5中建立了此3D模型物體的各構成物件的矩形範圍框。矩形範圍框的數量愈多愈線，代表所能夠檢查出的碰撞現象更精緻。接著，遊戲主程序會依據使用者通過輸入裝置7所輸出的指令，來進行遊戲(步驟S2)。在遊戲進行過程中，遊戲主程序會持續地判斷是否打鬥角色間發出了碰撞(步驟S3)。如果沒有，則回到步驟S2繼續進行遊戲。但是如果發生了碰撞，接著就必須決定出對打角色之間的碰撞點位置(步驟S4)。利用步驟S4所得到的碰撞點，即可以在碰撞點的位置上畫出預設的碰撞特效，例如爆炸等等(步驟S5)。最後，由於碰撞會使得打鬥角色位置發生變化，因此有必要重新計算碰撞之後打鬥角色的位置並重畫在顯示器9上(步驟S6)。隨後，再回到步驟S2繼續進行遊戲。由於本實施例主要是針對步驟S3的判斷碰撞方法以及步驟S4的判斷碰撞點方法加以改進，因此，以下即詳細說明步驟S3和步驟S4的詳細處理流程。
圖9表示在圖8所示的流程圖中，用以判斷是否發生碰撞的步驟S3的詳細流程圖。首先必須選擇所欲判斷是否發生碰撞的對打角色的特定物件(步驟S31)。如前所述，3D物體是由多個物件所構成，因此，對打角色中的每個物件都有機會發生碰撞。接著從儲存裝置5中，讀取第一角角所選擇欲判斷碰撞的特定物件的範圍框最小端點MIN1和最大端點MAX1，同時讀取第二角色所選擇欲判斷碰撞的特定物件的範圍框最小端點MIN2和最大端點MAX2(步驟S32)。接著，利用以上所述方式，比較MIN1和MIN2之間對應坐標值，分別取其中較高者，產生MIN。同時，比較MAX1和MAX2之間對應坐標值，分別取其中較高者，產生MAX(步驟S33)。其中的MIN和MAX即代表碰撞區域的最小端點和最大端點。此時，利用MIN和MAX即可判斷出兩者是否發生碰撞，亦即，當MAX中的所有坐標值均分別大於或等於MIN中的所有對應坐標值(步驟S34)，即表示兩者發生了碰撞(步驟S35)，否則若MAX中的任一個坐標值是小於MIN中對應的坐標值時，即表示兩者未發生碰撞(步驟S36)。最後，返回圖8所示的主控制程序。
圖10則是表示在圖8所示的流程圖中，用以判斷碰撞點位置的步驟S4的詳細流程圖。在判斷出兩個矩形範圍框已經發生碰撞之後(步驟S3)，即進入圖10所示的步驟S4。首先，分別計算發生碰撞的兩個矩形範圍框的中心點(步驟S4)，而碰撞點即在兩中心點的邊線上。接著，分別計算矩形範圍框的對角線長度(步驟S42)，做為分割中心點連續的標準。依據所得的對角線長度之比例，分割兩個矩形範圍框中心點的連線，並以此分割點做為兩個物件之間的碰撞點(步驟S43)。最後，並將此碰撞點送出主控制程序中，而進行之後的碰撞效果處理(步驟S44)以及碰撞後位置修正處理(步驟S45)。
由以上所述可知，利用本實施例的判斷碰撞方法，在對兩個物件的範圍框進行碰撞判斷時，只需要進行6次的比較運算。相較於習知技術重輒數十次甚至上百次的比較，本發明可以達到更有效率的效果。此外，本實施例的判斷方法亦不會在某些情況下發生錯誤的判斷，因此極具有應用上的價值。
本發明雖以一較佳實施例揭示如上，然其並非用以限定本發明，任何熟習此項技術者，在不脫離本發明的精神和範圍內，當可做些許的更動與潤飾，例如將本發明的技術應用在2D的環境下，或是應用在不同於較佳實施例所揭示3D格鬥遊戲，因此本發明的保護範圍當視所附權利要求所界定者為準。
權利要求
1.一種在虛擬空間內判斷碰撞的處理方法，用以在上述虛擬空間內判斷第一物件和第二物件之間是否發生碰撞，上述第一物件具有第一範圍框，其由第一最小端點和第一最大端點所定義，上述第二物件具有第二範圍框，其由第二最小端點和第二最大端點所定義，其特徵在於，包括下列步驟儲存上述第一最小端點、第一最大端點、第二最小端點、第二最大端點的坐標值，藉以構成在上述虛擬空間內上述第一物件和上述第二物件的碰撞判斷範圍；分別擷取且比較上述第一最小端點和上述第二最小端點的對應坐標值，將其中對應坐標值較大者組合成第一判斷端點；分別擷取且比較上述第一最大端點和上述第二最大端點的對應坐標值，將其中對應坐標值較小者組合成第二判斷端點；以及分別比較上述第一判斷端點和上述第二判斷端點的對應坐標值，當上述第二判斷端點的坐標值均分別大於或等於上述第一判斷端點的對應坐標值時，表示上述第一物件和上述第二物件發生碰撞，當上述第二判斷端點的坐標值的任一者小於上述第一判斷端點的對應坐標值時，表示上述第一物件和上述第二物件未發生碰撞。
2.如權利要求1所述的處理方法，其特徵在於，上述虛擬空間為一虛擬三維空間，每一端點的坐標值分別具有X坐標值、Y坐標值和Z坐標值。
3.如權利要求1所述的處理方法，其特徵在於，上述虛擬空間為一虛擬二維空間，每一端點的坐標值分別具有X坐標值和Y坐標值。
4.如權利要求1所述的處理方法，其特徵在於，上述第一範圍框為一櫃形，上述第一最小端點為上述矩形中各點的各坐標值相加具有最小值的點，上述第一最大端點為上述矩形中各點的各坐標值相加具有最大值的點。
5.如權利要求1所述的處理方法，其特徵在於，上述第二範圍框為一矩形，上述第二最小端點為上述矩形中各點的各坐標值相加具有最小值的點，上述第二最大端點為上述矩形中各點的各坐標值相加具有最大值的點。
6.一種在虛擬空間內判斷碰撞點的處理方法，用以判斷在上述虛擬空間內判斷第一物件和第二物件之間發生碰撞的碰撞點，上述第一物件具有第一範圍框，上述第二物件具有第二範圍框，其特徵在於，包括下列步驟提供上述第一範圍框的範圍值，以及上述第二範圍框的範圍值，儲存於一存儲器內，藉以構成在上述虛擬空間內上述第一物件和上述第二物件的碰撞判斷範圍；判斷上述第一物件和上述第二物件是否發生碰撞；當發生碰撞時，決定上述第一範圍框的第一中心點和上述第二範圍框的第二中心點；決定上述第一範圍框的第一特徵值和上述第二範圍框的第二特徵值；利用上述特徵值和上述第二特徵值的比例，分割上述第一中心點和上述第二中心點的連接線，決定一分割點；以及設定上述分割點為上述第一物件和上述第二物件的碰撞點。
7.如權利要求6所述的處理方法，其特徵在於，上述第一範圍框為一矩形，其範圍值由第一最小端點和第一最大端點所定義，上述第一最小端點為上述矩形中各點的各坐標值相加具有最小值的點，上述第一最大端點為上述矩形中各點的各坐標值相加具有最大值的點。
8.如權利要求6所述的處理方法，其特徵在於，上述第二範圍框為一矩形，其範圍值由第二最小端點和第二最大端點所定義，上述第二最大端點為上述矩形中各點的各坐標值相加具有最小值的點，上述第二最大端點為上述矩形中各點的各坐標值相加具有最大值的點。
9.如權利要求6所述的處理方法，其特徵在於，上述虛擬空間為一虛擬三維空間。
10.如權利要求6所述的處理方法，其特徵在於，上述虛擬空間為一虛擬二維空間。
11.如權利要求6所述的處理方法，其特徵在於，上述第一中心點和上述第二中心點為對應的上述第一範圍框和上述第二範圍框的質心位置。
12.如權利要求6所述的處理方法，其特徵在於，上述第一特徵值和上述第二特徵值為對應的上述第一範圍框和上述第二範圍框的最長對角線長度。
13.如權利要求6所述的處理方法，其特徵在於，上述第一物件和上述第二物件是否發生碰撞的步驟中，上述第一範圍框由第一最小端點和第一最大端點所定義，上述第二範圍框由第二最小端點和第二最大端點所定義，其包括下列步驟比較上述第一最小端點和上述第二最小端點的對應坐標值，將其中對應坐標值較大者組合成第一判斷端點；比較上述第一最大端點和上述第二最大端點的對應坐標值，將其中對應坐標值較小者組合成第二判斷端點；以及分別比較上述第一判斷端點和上述第二判斷端點的對應坐標值，當上述第二判斷端點的坐標值均分別大於或等於上述第一判斷端點的對應坐標值時，表示上述第一物件和上述第二物件發生碰撞。
14.一種在虛擬空間內判斷碰撞的處理方法，用以判斷在上述虛擬空間內判斷第一物件和第二物件之間是否發生碰撞，上述第一物件具有第一範圍框，上述第二物件具有第二範圍框，其特徵在於，包括下列步驟提供上述第一範圍框的範圍值，以及上述第二範圍框的範圍值，儲存於一存儲器，藉以構成在上述虛擬空間內上述第一物件和上述第二物件的碰撞判斷範圍；根據儲存於上述存儲器中的上述第一範圍框的範圍值以及上述第二範圍框的範圍值，判斷上述第一範圍框和上述第二範圍框是否有相疊區域；以及當存在上述相疊區域時，表示上述第一物件和上述第二物件發生碰撞，當不存在上述相疊區域時，表示上述第一物件和上述第二物件未發生碰撞。
全文摘要
一種在虛擬空間內判斷碰撞和判斷碰撞點的處理方法。在判斷碰撞處理方法中,先比較兩物件的兩個最小端點的對應坐標值,再將對應坐標值中較大者組合成第一個判斷端點。同樣地,分別比較兩物件的兩個最大端點的對應坐標值,再將對應坐標值中較小者組合成第二個判斷端點。如果第二判斷端點的坐標值均分別大於或等於第一判斷端點之對應坐標值時,即表示兩個物件發生碰撞。本發明還提供一種判斷碰撞點的方法。
文檔編號G06F17/00GK1245934SQ9811863
公開日2000年3月1日 申請日期1998年8月20日 優先權日1998年8月20日
發明者溫世義, 詹浩博, 徐志剛 申請人:英業達股份有限公司