用於操縱三維對象的數字表示的方法和系統的製作方法
2023-06-21 08:59:26
專利名稱：用於操縱三維對象的數字表示的方法和系統的製作方法
技術領域：
本發明涉及操縱三維對象的數字表示。本發明尤其涉及由計算機實現的、依靠二維光標移動對三維虛擬積木模型所進行的操縱，虛擬積木模型包括多個虛擬積木式組件，每一塊虛擬積木式組件包括許多連接元件，這些連接元件用於根據一組連接規則將虛擬積木組件與其它虛擬積木組件連接起來。
背景技術：
虛擬實境的計算機輔助建模的任務是創建物理對象模型、操縱模型，此外在計算機系統中處理物理對象的模型。
從第一觀點，虛擬實境的建模是令人感興趣的主題，因為它使得可能當概念在現實世界中真正實現之前就將概念形象化。假如虛擬實境模型很容易修改，在與在現實世界中實現同樣過程相比，能夠在開發和改進物理對象的過程節約大量時間。在現實世界裡給對象上色這樣簡單的任務可能就輕易花去幾個小時，而計算機能夠在幾毫秒或幾秒內就給模型塗上新顏色。
從第二觀點，虛擬實境建模是令人感興趣的，因為它使得可能創建現實世界中存在的對象模型，以及通過計算機來形象化和操縱模型。因此，可以存儲對象模型以用於不同的目的，例如用於高級文檔編制的目的。
儘管存在大量用於計算機輔助虛擬實境建模的可能應用，但一個特殊應用是將虛擬實境建模用於娛樂或教育。
物理建構玩具組的不同類型的建模思想同樣是已知的。特別是，使用組合式或半組合式概念的思想是非常流行的。典型地，這些思想提供了一組預製元件，這些元件能夠根據預製元件的模塊以某種預定方式彼此互聯。這種建構玩具組的一個實例是名為LEGO的塑料玩具建構元件。
當在計算機上操縱三維(3D)對象或場景的表示時，通常的問題在於，對象在3D中的定位、選擇或移動是藉助於工作在二維中的輸入設備來執行的，例如計算機滑鼠在滑鼠墊上的二維(2D)移動。此外，計算機的顯示區域也是二維的。特別地，計算機屏幕的2D顯示區域上的每一個選定的位置對應於3D空間內的多個位置，3D空間具有對應於所選定的2D位置的到2D顯示區域的投影。問題在於確定可能符合用戶意圖的其中一個位置。
儘管已經進行了相當地努力來開發更適於操縱3D計算機圖像中的對象的計算機接口設備，但是這種工具沒有被廣泛使用，特別是沒有與用於家庭娛樂、教育等的計算機系統相關。
已知的定位虛擬積木式組件的建構遊戲典型地在對象的移動和旋轉自由度或者將它們與其他對象連接的方式方面受到限制。
美國專利6,426,745描述了一種用滑鼠操縱3D圖形對象的方法，其中3D中的移動是通過在某個時刻把移動限制在一個平面或一個方向上來實現的，從而把3D移動用一系列受限的移動來實現，例如在3D坐標系中的X方向、隨後在y方向、最後在Z方向上的一系列移動。
上述現有技術的系統的問題在於，用傳統的用戶接口來把積木式組件放置在3D場景中以及它們與3D結構的連接是個麻煩的過程，這個過程需要高水平的技巧和訓練。尤其是在兒童及十幾歲的青少年的娛樂和教育的環境中，這是個問題，因為兒童通常還沒有發展出足夠的肌肉運動技巧或者執行冗長操縱過程所需的耐性。因此，他們可能很快就喪失對虛擬建構遊戲的興趣。
發明內容
上述問題及其他問題將通過由計算機實現的方法來解決，這種方法依靠二維的光標移動來操縱三維虛擬積木模型，虛擬積木模型包括多個虛擬積木式組件，每塊虛擬積木式組件包括許多連接元件，連接元件用於根據一組連接規則將虛擬積木式組件與其它虛擬積木式組件相連接，該方法包括-為結構的數字表示提供三維坐標系中的許多所述虛擬積木式組件；-藉助於光標在表示所述結構的投影的二維計算機顯示區域中的運動來定位第一虛擬積木式組件的二維投影，以使其連接到結構上，從而產生二維位置坐標；-根據二維位置坐標確定第一虛擬積木式組件在三維坐標系中的許多三維候選位置；以及-基於連接規則和一組預定的位置分級(position rating)規則來選擇所述候選位置中的一個；以及-在選定的候選位置上將第一積木式組件連接到所述結構。
因此，提供了用於操縱三維對象的數字表示的有效方法，這種方法以對於用戶直觀的方式將2D顯示區域中的位置轉變(resolve)為相應的3D位置，因此使得用戶很容易操縱3D虛擬結構。用戶可以簡單地在2D屏幕區域中定位新的積木式組件，因而只固定新積木式組件在兩個方向上的坐標。隨後根據許多連接規則以及一組位置分級規則，自動確定多個符合2D放置的可能3D位置中適當的一個。
特別地，通過根據一組預定的位置分級規則選擇許多候選位置中的一個，處理導致的結果是把積木式組件定位在3D場景中可能符合用戶意圖的位置上。
進一步的優點在於，不符合用於連接元件的連接規則的位置被拒絕。例如，建構系統中可能有很多種不同的連接元件，例如不同形狀和/或尺寸的突出物以及不同類型的、用於與相應一種突出物結合的孔洞。
假設新積木式組件被放置在符合2D放置的候選3D位置，通過選擇靠近新積木式組件上連接元件的候選連接元件，並且通過檢查與候選連接元件的有效連接是否可能，從而將計算機屏幕上新積木式組件的2D放置正確地轉變為3D模型中的3D位置。此外，避免了根據一組連接規則可能導致無效連接的2D到3D轉變，例如突出物與不同類型孔洞的連接。
因此，優點在於，虛擬積木式組件與相應的實物建構組的物理限制一致，從而提高了虛擬建構遊戲的教育價值。特別地，虛擬建構隨後可以通過用相同類型的積木式組件建構物理模型而被變換成物理模型。
進一步的優點在於，本方法提供了大的移動和連接自由度。例如，積木式組件可以在任意方向上被定位和連接。特別地，在水平和垂直面上都可能連接到其他積木式組件。此外，即使積木式組件被旋轉，例如圍繞垂直軸或水平軸旋轉，也能正確地定位它們。
優選地，通過經由諸如指針設備之類的適當輸入設備從用戶處接收到的控制命令來控制圖形表示的定位。例如，定位可以作為標準光標操縱技術而被執行執行，諸如「拖放」操作，「單擊-拖動-鬆開」操作及其他類似操作。
在一個優選實施例中，確定許多三維候選位置的步驟進一步包括確定第一虛擬積木式組件在三維坐標系中的許多候選位置。通過旋轉第一積木式組件以獲得旋轉後的積木式組件的候選位置，將用戶控制的2D位置轉變為3D放置以及三個維度上的定向，從而只基於2D屏幕區域中的單個光標控制就確定3D場景中放置的全部六個自由度。當第一積木式組件的旋轉被限制在用戶選定定向周圍的預定空間角度時，避免了諸如積木的完全翻轉(complete flipping around)之類的令人混淆的旋轉，從而避免了用戶的迷惑(disorientation)。在該實施例中，可以通過允許用戶選擇虛擬積木式組件的定向來獲得更多的定向。
在一個優選實施例中，方法進一步包括-確定所述結構的許多候選連接元件，每個候選連接元件具有第一虛擬積木式組件的連接元件的投影周圍的預定鄰域內二維顯示區域中的投影；
-基於連接規則和該組預定的位置分級規則，選擇所述候選連接元件中的一個；以及-如果根據該組連接規則，第一虛擬積木式組件和所述結構之間的連接是有效的，則通過至少一個選定的候選連接元件將第一虛擬積木式組件與結構連接。
因此，提供了檢測候選位置的計算有效方法，因為檢測只依賴於單獨連接元件的位置和屬性。此外，提供了有效的選擇機制，用於選擇最可能符合用戶意圖的3D位置。
當分級包含一個或多個下述分級規則時，提供了特別有利的連接元件分級-關於它們到虛擬攝像頭位置的距離地對候選連接元件進行分級；-丟棄從當前虛擬攝像頭位置看不到的候選連接元件；以及-關於它們的二維投影到第一虛擬積木式組件的相應連接元件的二維投影的距離地對候選連接元件進行分級。
特別地，當分級規則是基於到虛擬攝像頭位置的距離組合以及基於他們的二維投影與第一虛擬積木式組件的相應連接元件的二維投影的相應間距時，獲得了可靠的3D定位。
在一個優選實施例中，對於每個虛擬積木式組件，所述結構的數字表示包括對應於虛擬積木式組件的至少一個表面的許多規則的柵格，每個規則的柵格包括許多柵格點，每個柵格點代表一個連接元件。因此，提供了系統化的框架，其允許3D位置的正確轉變以及大量不同積木式組件的正確互聯，即使積木式組件具有大量連接元件，甚至不同類型的連接元件。
優選地，所述第一虛擬積木式組件的連接元件的投影周圍的所述預定鄰域具有對應於相應規則柵格的相鄰柵格點之間距離的線性標註(linear dimension)，諸如直徑。因此，提供了一種由用戶控制的精確細緻的放置，其產生3D解析度和對於用戶可預測的、透明的積木式組件連接。
進一步的優選實施例在從屬權利要求中被公開。
本發明可以以不同的方式來實現，包括上述的以及下文中的方法、數據處理系統以及其他產品裝置，其中每一種方式都產生一個或多個結合第一被提到的方法描述的好處和優點，並且每一種途徑都具有對應於結合第一被提到的方法描述的優選實施例的一個或多個優選注意，上述以及下文中的方法的特徵可以在軟體中實現，並且可以在數據處理系統或其他處理裝置中通過執行計算機可執行指令而實現。指令可以是從存儲介質或通過計算機網絡從另一臺計算機加載到諸如RAM之類的存儲器中的程序代碼單元。可選地，所述特徵可以通過硬布線電路來實現，而不是通過軟體或者結合軟體來實現。
本發明還涉及包括程序代碼單元的電腦程式，當所述程序在計算機中運行時，程序代碼單元用於執行上述以及下文中的方法的所有步驟。電腦程式可以被實現為計算機可讀存儲介質，數據信號被實現為載波，等等。
本發明還涉及包含存儲在計算機可讀介質上的程序代碼單元的電腦程式產品，當所述電腦程式運行在計算機上時，程序代碼單元用於執行上述以及下文中的方法。
以下將結合優選實施例，並參照附圖來更為完整地闡明本發明，其中附圖1a-b表示用於生成和操縱幾何對象的計算機可讀取模型的數據處理系統；附圖2表示虛擬積木系統的圖形用戶界面；附圖3a-d闡明了積木式組件及其連接元件的實例；附圖4a-b闡明了物理積木式組件的數字表示的實施例；附圖4c闡明了連接點周圍的體積元素(volume element)的實例；附圖5表示在3D場景中定位積木式組件並且將它連接到已存在於場景中的積木式組件的結構上的處理的流程圖；附圖6a-b闡明了將新積木式組件定位在先前放置的積木式組件頂部上的實例；附圖7a-b闡明了由於屏幕上圖形表示的略微不同的2D放置所導致的積木式組件的兩個位置；附圖8表示在試驗性的3D放置中，新積木式組件的連通性驗證子程序的實施例的流程圖；附圖9a-b闡明了包含了旋轉的積木式組件的連接。
具體實施例方式
附圖1a-b表示用於生成和操縱幾何對象的計算機可讀取模型的數據處理系統；附圖1a表示計算機系統實例的示意圖。計算機系統包括被適當編程的計算機101，例如個人計算機，計算機101包括顯示器120、鍵盤121以及計算機滑鼠122和/或另一指針設備，諸如觸摸板、軌跡球、光筆、觸控螢幕等。
標號為101的計算機系統適用於促進設計、存儲、操縱以及共享虛擬積木式組件模型。計算機系統101可以用作單機系統或者客戶端/伺服器系統中的客戶端。
附圖1b表示用於生成和操縱計算機可讀取的虛擬積木模型的數據處理系統的方框圖。計算機101包括存儲器102，存儲器可以部分被實現為易失性存儲裝置，並且部分被實現為非易失性存儲裝置，例如隨機存取存儲器(RAM)和硬碟。存儲器具有存儲在其上的模型代碼解釋器107、模型代碼產生器108、UI事件處理程序109以及建模應用110，其中每一個都可由中央處理單元103執行。而且，存儲器具有存儲在其中的模型數據111，即代表物理對象的數字表示的一組數據結構，例如虛擬積木模型。用於存儲虛擬積木模型的數據格式的一個實例在美國專利6,389,375中被公開了。
代碼解釋器107適用於讀取和解釋定義模型的代碼，即代表模型的積木式組件的數據結構的代碼。在優選實施例中，代碼解釋器適用於讀取模型並將這種模型轉換為已知圖片格式，用於在計算機顯示器上顯示。
UI事件處理程序109適用於將用戶與用戶接口的交互轉換為代碼發生器108可識別的適當的用戶命令。一組可能的並且可識別的命令可包括從元件庫獲取積木式組件，放置積木式組件以連接到另一積木式組件，分離積木式組件，丟棄積木式組件，例如通過發起旋轉等來操縱積木式組件或一組積木式組件等等。每一個命令可以與一組相應的參數相關聯，例如相對於顯示器坐標系的光標坐標、積木式組件的類型等。
代碼解釋器108適用於響應於用戶的命令修改模型的數據結構。作為同時的或後續的任務，可以執行代碼解釋器，用於表示代碼產生器的結果。
建模應用110適用於控制存儲器、文件、用戶接口等。
用戶105能夠藉助於用戶接口106與計算機系統101進行交互，用戶接口106優選地包括顯示在計算機屏幕上的圖形用戶界面，以及一個或多個諸如鍵盤和/或指針設備的輸入設備。
為了加載、存儲或傳遞模型、幾何描述或其他數據，計算機系統包括輸入/輸出單元(I/O)104。輸入/輸出單元可以用作與不同類型存儲介質和不同類型計算機網絡，例如網際網路，的接口。此外，輸入/輸出單元(I/O)104可以被用於例如交互地與其他用戶交換模型。
藉助於數據總線112實現存儲器102、中央處理單元(CPU)103、用戶接口(UI)106以及輸入/輸出單元104之間的數據交換。
附圖2表示了虛擬積木系統的圖形用戶界面。
用戶界面包括顯示區域201，用於顯示具有底盤202以及包含許多互聯的虛擬積木式組件204的3D結構203的3D場景視圖。從預定的觀察點顯示場景。以下，這個觀察點也被稱為(虛擬)攝像頭位置，因為它對應於這樣一個位置，從這個位置上攝像頭記錄對應於顯示區域中所示圖形圖像的實際結構的圖像。
每個積木式組件204對應於圖形用戶界面中的活性元件，例如通過用計算機滑鼠點擊可以將其激活，從而選擇該積木式組件。在一個實施例中，被選中的虛擬積木式組件改變了外觀。例如，被選中的積木式組件可以改變顏色、紋理等；可以通過在被選中的積木周圍顯示有邊界框等來加亮這個積木。用戶可以操縱被選中的積木式組件，例如改變其屬性，例如其顏色、將其刪除、執行複製和粘貼操作、將其拖放到不同位置等。
用戶界面還包括選項面板(palette panel)205，選項面板205包括許多可以被用戶選擇的不同積木式組件206。例如，用戶可以用滑鼠在其中一個積木式組件206上點擊，從而選擇積木式組件，以及將被選中的積木式組件拖進顯示區域201，以將它連接到結構203或者連接到底盤202。
用戶界面還包括菜單欄207，菜單欄包含許多用於啟動各種功能或工具的菜單按鈕208。例如，工具欄可以包括用於改變虛擬攝像頭位置的旋轉工具，從而允許用戶從不同方向觀察構造區域。菜單欄可以進一步包括用於放大和縮小3D場景的縮放工具。工具的其他實例包括用於選擇不同選項面板205的選項面板工具，其中每個選項面板包括不同的積木式組件組合、用於為結構的部分上色的上色工具、用於擦除積木式組件的橡皮擦工具等。
菜單欄207可以進一步提供標準功能，諸如用於保存模型的功能、用於打開以前保存的模型的功能、用於列印模型圖像的功能、幫助功能等。
附圖3a-d闡明了積木式組件及其連接元件的實例。
附圖3a表示積木式組件301的透視圖。積木式組件301的上表面302帶有8個突起303a-h，這些突起能夠與另一積木式組件的相應孔眼，例如另一積木式組件底面上的孔眼，結合。相應地，積木式組件301包括帶有相應孔眼的底面(未表示)。積木式組件301還包括不包含任何連接元件的側面304。
通常，連接元件可以被分組為不同種類的連接元件，例如連接件、接受件以及混合元件。連接件是可以被另一積木式組件的接受件接納以提供積木式組件之間連接的連接元件。例如，連接件可以容納在另一組件的部分之間、插入孔眼內等等。接受件是能夠接納另一積木式組件的連接件的連接元件。混合元件是既能充當連接件又能充當接受件的部分，這通常取決於另一積木的合作連接元件的類型。
附圖3b表示從底部觀察積木式組件310的透視圖。積木式組件310具有非矩形的頂面和底面。底面包括用於接納一個或多個其他積木式組件，例如附圖3a中的積木式組件301，的相應突起的孔眼311、312以及313。孔眼由邊沿314、由二級銷柱(secondary pin)315以及拐角316和317限定。因此，所有上述元件的屬性決定了積木式組件310底面的連接屬性。
附圖3c闡明了積木式組件320與積木式組件321連接，從而形成組合的積木式組件。積木式組件320在其上表面上包含突起322，突起322容納到另一積木式組件的相應孔眼中。然而，如附圖3c中所闡述的，也可以實現其他類型的連接。突起之間的間隙323充當其他連接件，諸如積木式組件321的側面324，的接受件。對於物理積木式組件，這種屬性由間隙的尺寸以及積木式組件321的尺寸，即它的側面寬度325，決定。然而，在數字表示中，通過規則的柵格上的連接點的相應屬性來表示這些屬性，如在下文中更為詳細地闡述。
附圖3d表示兩個積木式組件331和332。積木式組件331是磚形的，在它的上表面上具有4個突起333，在底面(未表示)上具有4個相應的孔眼。磚形物332是具有包含不相互正交的平面的表面的積木式組件實例。特別地，積木式組件332具有斜面334。如附圖3d所闡明的那樣，在當前位置，積木式組件331和332不連接，因為在所示的位置上沒有任何彼此結合的連接元件。
應該理解，上述積木式組件僅僅用作可能的積木式組件的實例。
附圖4a-c闡明了物理積木式組件的數字表示的一個實施例。物理積木式組件的數字表示包括存儲在計算機存儲器中的數據結構，其中數字表示代表該積木式組件的屬性。根據該實施例，積木式組件的連接元件可以在種類(nature)、外形、連接屬性等方面各不相同。然而，他們在積木式組件上的位置遵循一組規則。
積木式組件具有許多與它相關的平面，例如由積木式組件的有邊界框的表面所定義的平面。積木式組件的連接元件位於這些平面內，使得每個連接元件具有與其相關的軸。相同平面內所有連接元件的軸對應於規則的柵格，例如正交的柵格，的相應柵格點，所謂的節點，並且鄰近柵格點之間的間距是固定的。優選地，與積木式組件關聯的平面成對地彼此平行，例如通過定義一組對應於積木式組件的上表面和底面的水平平面以及許多對應於積木式組件側面的垂直平面。優選地，在所有水平平面上，相鄰柵格點之間的間距是相同。在一個實施例中，垂直平面中相鄰柵格點之間的間距與水平平面中相鄰柵格點之間的間距不相等。
附圖4a-b示意性地闡明了數據結構的實施例如何描述附圖3a的積木式組件301的屬性。在附圖4a-b中，顯示了積木式組件301及其上表面和底面各自的相應正交柵格405和406。附圖4a表示積木式組件的透視圖，而附圖4b表示積木式組件的頂視圖。在附圖4a-b中，沒有表示積木式組件301側面上的柵格。積木式組件的某些實例，例如積木式組件301，在某些面上，例如在側面上，沒有任何連接元件。積木式組件的其他實例可能在所有側面上具有連接元件。
正交柵格也被稱為連通性柵格，柵格點也被稱為連接點。用如圓周407a-k所示例的圓周來闡明連接點。因此，連接點407a-h分別對應於突起303a-h。由於側面304沒有任何連接元件，因此不需要為它們定義任何連接柵格。在可選實施例中，可以為側面定義只包含虛接受件的連接柵格，即既不連接也不抵制其他連接元件的接受件。
相對於內部右手坐標系408描述積木式組件的數字表示。應該理解，坐標系的選擇，特別是其原點的位置和坐標軸的方向，可以根據任意適當的慣例來選擇。因此，在相應的數據結構中，積木式組件在3D場景中的位置和定向可以由坐標系408相對於外部坐標系，例如另一積木式組件的坐標系或全局「世界」坐標系，的原點坐標以及坐標軸的方向來表示。
正如從附圖4a中所能看到的那樣，通過置於規則柵格中的連接點來表示積木式組件的連接元件就將某些約束強加在物理積木式組件上的連接元件的物理放置上。柵格405位於突起303從其延伸的積木式組件上表面的平面內。
在附圖4a-b的實例中，柵格點被放置在正方形柵格內，其中每個正方形的尺寸為5*5個的任意長度單位(LU)。因此，在這個幾何裡，連接元件也被放置在相應的正方形柵格上，並且積木式組件的平面內連接元件之間的間距為10LU的倍數。在附圖4的實例中，積木式組件的上表面和下表面是矩形的，其尺寸為20LU*40LU，並且相鄰連接元件的空間距離為10LU。另一方面，在垂直方向上，連接元件的空間距離為12LU。
相對於積木式組件的內部坐標系408來定義連接點的位置。每個柵格點還具有與其相關聯的方向，指示連接元件在哪個方向上可以與相應的連接元件結合。柵格點的方向垂直於平面，並且指向有邊界框的外部，即在附圖4b中指向圖中平面的外部。
在一個實施例中，對於每個連接點，代表連接點的柵格的數據結構包括連接點相對於坐標系408的坐標，連接元件的方向，以及連接類型。
在一個實施例中，代表積木式組件的數據結構包括積木式組件ID(識別符)，描述積木式組件的有邊界框的位置、定向以及尺寸的數據結構，以及描述各個柵格以及它們的相應連接點的許多數據結構。代表連接點的柵格的數據結構包括-用作局部柵格坐標系原點的柵格點相對於坐標系408的坐標。在柵格405的例子中，柵格點307i被作為原點，坐標為P0＝(-5，12，-15)，單位為LU。
-連接元件的方向。在柵格405的例子中，這為(0，1，0)，即坐標系408的Y軸方向。
-X和Z方向上柵格點的數量。在柵格405的例子中，分別是nx＝9和nz＝5。
-nx*nz數據結構的陣列，每個包括相應的連接點的連接屬性。每個柵格點的數據結構包括連接點的連接類型，例如「孔眼」、「邊」、「突起」等等。
在一個實施例中，每個連接點還具有與之相關的體積元素，定義了該連接點周圍的鄰域。
附圖4c闡明了連接點周圍的體積元素的實例。在一個實施例中，每個連接點具有與之相關聯的球形，其中心位於連接點上。在附圖4c中，這是通過上述積木式組件301的連接柵格405的連接點407g和407j來示例的。對於連接點407g和407j，分別示出了相應的球形410g和410j。球形的半徑等於相鄰連接點之間間距的一半，例如在附圖4a-b的實例中為2.5LU。應該了解，在可選實施例中，球形可以更小或更大，即它們可以交叉或者在相鄰球形的球面之間可以有間隙，從而允許相對於小誤放的定位方法的靈敏度控制。
還應該理解，也可以使用不同類型的體積元素。例如體積元素可以是包圍連接元件的圓柱體，如包圍連接點407c的圓柱體410c所示例。在這個實例中，圓柱體的半徑為2.5LU並且高度為5LU。體積元素的其他實例包括正方體、橢圓體等。
還應該理解，在某些實施例中不同類型的連接元件可以與不同體積元素相關聯，例如不同尺寸，例如不同半徑和/或不同高度，的體積元素，或者甚至不同幾何形狀。在這種實施例中，代表連接點的數據結構可以還包括一個或多個用於識別相關聯的體積元素的類型和/或尺寸的參數。
應該理解，當在顯示器，例如計算機屏幕，上圖形表示積木式組件時，邊界範圍(bounding volume)、坐標系、體積元素以及柵格不需要被顯示。優選地，圖形表示只包括積木式組件自身的圖形描述。
以下將更加詳細地描述把新積木式組件放入包含3D結構的場景的過程。將參照附圖5和6a-b。
附圖5表示把積木式組件定位在3D場景並且將它連接到已經出現在場景中的積木式組件結構上的過程的流程圖。
在步驟501中，新積木式組件被放置在場景中，例如通過選擇選項面板上的積木式組件並且根據滑鼠移動將積木式組件的圖形表示拖到2D顯示區域中用戶所選定的位置，其中2D顯示區域表示3D場景的2D投影。在一個實施例中，當滑鼠的移動至少停止了一個預定時間，例如GUI事件處理程序所檢測到的，時，程序進入步驟503。
附圖6a-b闡明了將新積木式組件定位在先前放置的積木式組件的頂部的實例。新積木式組件601被圖示為有邊界框620，有邊界框620具有上表面621和底面622，每一面包括許多如上所述的連接柵格的連接點，其一般地由603標示。類似地，先前放置的積木式組件602具有許多連接點，其一般地用604標示。在附圖6a中沒有表示積木式組件601和602的側面的連接柵格和連接點。在這個實例中，3D場景只包括一個先前放置的積木式組件602。
附圖6a闡明了在計算機屏幕的2D顯示區域600中看到的積木式組件601和602的2D投影，其對應於2D顯示坐標系630。
附圖6b闡明了顯示區域600中的2D投影和積木式組件601和602在3D坐標系640中的3D位置之間的關係。當新積木式組件601被放置在屏幕600上時，只確定了它在2D坐標系630中的坐標，並且，如虛線投影線631所述，產生投影601a的任何3D位置符合這個投影。因此，由用戶控制的將積木式組件放置於屏幕上並沒有提供關於垂直於顯示區域的第三維的信息。在附圖6b中，投影是平行投影，即投影線631彼此平行，相當於虛擬攝像頭位置632距離投影平面600無限遠。
再次參照附圖5，在步驟503中，處理確定了，對於新積木式組件的每個連接點，是否存在屬於已經存在於場景中的任何積木式組件(或，如果存在，屬於底盤)的連接點，其具有在新積木式組件的該連接點投影的預定鄰域內的2D投影。在一個實施例中，對於新積木式組件的每一個連接元件，確定顯示區域內包圍連接元件的圓周。類似地，確定已經存在於場景中的連接元件的相應圓周。如果這些圓周中的任何圓周與新積木式組件的連接元件的圓周重疊，則選擇相應的連接元件作為候選的連接元件。
在附圖6a中，用新積木式組件601的連接點605來闡明這個步驟。標號606標示了包圍連接元件605的圓周。類似地，標號608、610和612分別標示了積木式組件602的連接元件607、609和611的圓周，這些圓周與圓周605交疊。因此，在這個實例中，連接元件607、609和611被確定為候選連接元件。應該理解，在這個實例中，可以選擇進一步的連接元件。然而，它們的圓周在附圖6b中沒有被表示。
應該注意，圓周606、608、610和612分別對應於包圍連接元件605、607、609和611的相應球形的投影。應該理解，在可選實施例中，為了確定哪些連接元件具有在新積木式組件的連接元件的鄰域之內的投影，可以使用不同類型體積元素的投影。結合上述附圖4c已經描述了體積元素的更多實例。當使用球形時，相應投影的確定尤為有效，因為球形的投影始終是圓，而與視點無關。
在一個優選實施例中，圓周的直徑對應於每個柵格中相鄰連接點之間的間距。
應該進一步理解，在某些實施例中，候選連接元件的搜索可以被限制在已經存在於場景中的積木式組件的連接元件的子集內，從而減少完成搜索所需要的時間以及候選連接元件的結果列表的大小。例如，搜索可以被限制在還沒有連接到另一連接元件的連接元件。在一個實施例中，搜索被限制在具有合適連接屬性的連接元件，即能夠被實際連接到新積木式組件的連接元件上的連接元件，如下文中將更詳細地描述的。
步驟530產生已經存在於場景中的積木式組件的候選連接元件的列表520。因此，候選連接元件的3D坐標是已知的。在一個實施例中，列表520中的每個條目包括已經存在於場景中的積木式組件的候選連接點的3D坐標，識別相應積木式組件的標識符，以及識別新積木式組件的相應連接元件的標識符和/或坐標。
在步驟505中，通過根據預定的一組分級規則對候選連接元件進行分級來對候選連接元件的列表520排序。
在一個實施例中，候選連接元件是根據他們與虛擬攝像頭的距離，即它們與對應於顯示區域600的投影平面的相對距離，以及根據候選位置和用戶選定放置之間的2D距離，即候選位置在顯示區域中的投影與新積木式組件的圖形的位置的位移，而被分級。例如，候選位置對於其更靠近攝像頭位置的連接元件可以被分集為更高，即更可能符合用戶所想要的位置。同樣，在3D中與用戶選定位置的位移對於其是高的候選連接點可以被分集為更低。
在某些實施例中，作為上述條件的附加或替代，根據其他標準執行排序。這種位置分級規則的實例可以包括以下一條或多條-與攝像頭位置的相對距離；-與用戶選定的2D位置的位移；-積木式組件所需旋轉的角度，以便允許與候選連接元件的連接；-可見性檢測，例如候選連接元件從當前攝像頭位置上是否可見。在某些實施例中，從列表中丟棄從當前攝像頭位置不可見的候選連接元件。
在某些實施例中，上述標準中的幾個或者全部可被組合運用，例如通過定義上述條件的價值函數，可選地具有相應的加權因子。在其他實施例中，首先根據上述規則其中之一，例如所需的2D位移，執行分級。如果兩個或多個候選連接元件具有相同的分級，可以用另一規則來區分它們，例如與攝像頭的相對距離、所需的旋轉等。
因此，完成了對所確定的候選連接元件的分級，並且有序列表520根據上述分級對應於有序列表。在此，有序列表520包括基於上述位置分級規則沒有被丟棄的所有候選連接點。
在步驟508中，確定有序列表520是否為空。如果列表為空，即沒有任何連接元件具有與新積木式組件的連接元件的足夠小的投影距離，則3D放置被拒絕(步驟509)，即處理終止；否則，處理前進到步驟510。
如果處理通過拒絕3D放置(步驟509)而終止，則優選地將其指示給用戶，例如通過提供可視的指示。例如，可以以指示積木式組件還沒有被放置的形式顯示響應於滑鼠移動而被移動的積木式組件的圖形表示。僅當發現3D放置時，圖形表示切換，從而向用戶指示放置已經完成。例如，只要3D放置沒有成功完成，積木式組件可以被顯示為透明和/或具有可視的有邊界框和/或閃爍和/或任何其他適當的形式。
在步驟510中，選擇具有最高分級的候選連接元件，並且新積木式組件被放置在3D坐標系中，使得選中的候選連接點的坐標和新積木式組件的相應連接點的坐標相一致。因此，選擇根據最高分級的候選位置。應該理解，該放置只是試驗性的，即仍然沒有被顯示在計算機屏幕上。
在步驟511中，處理驗證連接是否符合預定的一組連接規則，例如，在新積木式組件的這些和其他連接點上的連接元件是否允許與新積木式組件要連接到的積木式組件的連接元件的連接。這個其實施例將在下文中更詳細描述的檢查也將被稱為連通性驗證。在優選實施例中，處理進一步驗證新積木式組件在連接到候選連接元件時從攝像頭位置上是否可見，或者其是否被存在的結構完全遮擋(obstruct)。如果連接被拒絕或者積木式組件將是不可見的，則試驗性的3D放置被拒絕，並且處理前進到步驟512；否則，如果處理成功地驗證了連接，則處理前進到步驟513。
在步驟512中，連接對於其被拒絕的候選連接點被從有序列表520中移除，並且處理返回步驟508，即如果存在，則選擇下一個候選連接點。
在步驟513中，即如果連接檢查是成功的，則3D放置被接受，即通過在被接受的位置上「咬住」新積木式組件以及通過改變積木式組件的外觀來更新結構的圖形表示。在一個實施例中，用戶可以接受位置，例如通過用滑鼠在積木式組件上點擊，從而完成放置處理。如果用戶希望把積木式組件放置在另一位置，那麼用戶可以簡單地移動滑鼠，而不需要在積木式組件上點擊，從而把新積木式組件的外觀變回最初的外觀，並且把積木式組件移動到2D顯示區域的另一位置。
處理保持一組數據結構，每個數據結構表示放置在3D場景中的積木式組件，例如如結合附圖4a-b所描述。當接受新積木式組件的3D放置時，處理通過增加對應於新積木式組件的數據結構的新實例作為數據結構組的一部分來更新該數據結構組。
附圖7a-b闡明了由屏幕上圖形表示的略微不同的2D放置所導致的附圖6a-b的新積木式組件的兩個位置。在附圖7a中，積木式組件701被放置在結構702的頂部。另一方面，在附圖7b中，積木式組件701被定位在結構702後面在底盤703上。因此，新積木式組件的2D位置的小調整允許用戶區分3D場景中的兩種相當不同的放置。附圖7a-b進一步闡明了新積木式組件701當其被用戶操縱時與結構702的積木式組件704相比的不同外觀。
附圖8表示在試驗性的3D放置中新積木式組件的連通性驗證子處理511的實施例流程圖。由此，處理驗證新積木式組件是否能夠被連接到現有結構的至少一個其他積木式組件上。該其他積木式組件被稱為第二積木式組件。
在初始步驟801中，處理執行衝突檢測和可視性檢查，即檢測新積木式組件是否與已經存在於場景中的任何其他積木式組件相交，以及檢查新積木式組件是否將被已存在的結構完全遮擋並因此從當前攝像頭位置是不可見的。衝突檢測可以通過任何適當的衝突檢測方法來執行，優選為基於積木式組件的邊界範圍的衝突檢測方法。這種算法的實例被公開在例如David H.Eberly的「3D Game Engine Design」，Morgan Kaufmann，2001中。同樣，可視性檢查可以通過本技術領域中已知的任何適當的方法來執行。如果檢測到無效的交點，即如果積木式組件的邊界範圍相交，或者如果積木式組件從當前攝像頭位置將是不可見的，則拒絕在這個位置和定向上放置積木式組件；否則，如果積木式組件將是至少部分可見的以及如果檢測到有效的交點，即如果至少部分有邊界框表面相交但它們的體積不相交，則處理進入步驟802。
在步驟802中，確定新積木式組件和第二積木式組件的屬於所檢測到的有邊界框表面交點的所有連接點。只有那些還沒有被連接的連接點需要被考慮；這些連接點將被稱為相關連接點。
在步驟803中，選擇新積木式組件的第一相關連接點，例如任意選擇的連接點。
在步驟804中，對於新積木式組件的選定連接點，處理檢查是否存在任何坐標與所選中的連接點相同的第二積木式組件的相關連接點。在一個實施例中，其中積木式組件被放置在離散的體積參考柵格中，並且所有坐標都是任意長度單元的倍數，可能需要坐標的精確匹配。在連續或準連續的參考坐標系中，可能需要柵格點在預定限制中一致。
如果沒有發現這種匹配連接點，那麼處理進入步驟814。
在步驟814中，檢測在被選中的連接點的預定鄰域內是否存在任何其他相關連接點。例如，在其中相鄰的兩個連接元件之間的間距為10LU的實施例中，可以選擇預定鄰域為包圍著被選中的、位於(x，y，z)的連接點的立方體(x±5LU，y±5LU，z±5LU)。如果在被選中的連接點的預定鄰域之內存在任何其他相關連接點，那麼兩個積木式組件的連接被拒絕(步驟811)並且算法終止。因此，當該實施例中的連接點被放置在規則的柵格上時，積木式組件的無效放置可以被有效地檢測如果對於新積木式組件的相關連接點中的一個，發現與第二積木式組件的相關連接點不匹配，則不需要檢測新積木式組件的剩餘連接點，從而提高了檢測處理的速度。
如果在步驟814中沒有找到任何衝突的相關連接點，則處理進入步驟809。
如果在步驟804中找到匹配的連接點，那麼處理進入步驟805，其中檢測在被選中的連接點的預定鄰域內是否存在任何其他相關連接點，例如如上所述，在包圍著被選中的、位於(x，y，z)的連接點的立方體(x±5LU，y±5LU，z±5LU)之內。如果在預定鄰域內找到另一連接點，那麼拒絕位置(步驟811)；否則，程序進入步驟806。
在可選實施例中，上述約束可能是不希望的。而且，在再一實施例中，上述約束可能被限制到某些連接類型。
在步驟806中，處理檢測被選中的連接點以及被檢測到的匹配的連接點是否具有相反的方向，即它們的關聯軸是否沿同一直線但在相反定向上。因此，只接受定位在適合他們結合的相關定向上的連接元件。
應該注意，在可選實施例中，這種限制可以被放鬆，例如通過在其中連接元件接受一個定向範圍的實施例中接受一定定向範圍。
如果連接點的相對方向被接受，那麼處理進入步驟807，否則，這個位置被拒絕(步驟811)。
在步驟807中，比較被選中的連接點以及相應的被檢測到的匹配連接點的連接類型。在一個實施例中，每個連接點都具有相關聯的連接類型，例如「突起」、「孔眼」、「邊」、「拐角」、「合葉」、「銷」、「細銷」等。處理存取存儲在存儲器中的連接表813。連接表包括所有連接類型對的連通性類型，指示特定連接類型對如何影響兩個積木式組件的連接。例如，每對連接類型可以被關聯到連通性類型「真」、「假」或「空」。連通性類型「真」指示連接是有效的，並且相應連接元件結合以連接兩個積木式組件，例如突起與相應的孔眼結合。連通性類型「假」指示連接不被允許。例如，突起與突起之間的連接是不可能的它們不僅不結合以提供連接，而且它們甚至妨礙/牴觸，使得連接不可能。最後，連通性類型「空」指示沒有任何阻止連接的東西，也沒有任何實際連接的東西。例如，孔眼和孔眼就是這樣的例子。因此，對於給定的一對連接點，處理能夠從所存儲的連接表813中檢索相應的連通性類型。
在隨後的步驟808中，檢查連通性結果是否為「假」，即在相應的連接類型之間不可能有任何有效的連接。如果連通性結果為「假」，那麼新積木式組件的位置被拒絕(步驟811)，否則存儲連通性結果，並且處理進入步驟809。
在步驟809中，檢查新積木式組件的所有相關連接點是否都已經被處理。如果沒有，則選擇仍然沒有被處理的相關連接點(步驟812)，並且通過執行上述步驟804、805、806、807以及808來處理當前選中的連接點。
如果新積木式組件的所有相關連接點都已經被處理，並且位置也沒有被拒絕，則接受這個位置並且處理進入步驟810。在步驟810中，基於存儲的連通性結果確定積木式組件如何連接，以及相應地更新它們各自的數據結構。
起初，檢驗是否所有連通性結果為「空」。如果是，即如果沒有任何東西阻止積木式組件的位置，但是也沒有任何連接元件實際結合以連接積木式組件，則允許新積木式組件處於其當前位置。在一個實施例中，附加的算法可以決定，例如基於邊界範圍，被放置在這個位置上的物理積木式組件是否會掉落、傾斜等，並相應地允許或拒絕這個位置。
否則，即如果一個或多個連通性結果為真，則處理確定積木式組件如何被連接，即它們是否被剛性連接或者連接是否允許相對旋轉、轉換和/或類似操作。
一旦數據結構被更新，則子處理終止並且返回到附圖5的總處理。
附圖9a-b闡明了包含旋轉的積木式組件的連接。在某些實施例中，只對屏幕上可見的新積木式組件的定向，即用戶選定的定向或預設定向，檢查連接點。當用戶希望在積木式組件旋轉之後連接新積木式組件時，可以通過適當的用戶接口控制來控制定向，例如藉助於可以在圖形用戶界面的菜單中選擇的旋轉工具、藉助於鍵盤命令等。例如，用戶可以控制新積木式組件的定向，使逐步遍歷(step through)離散定向序列，例如對應於圍繞不同軸線的90度旋轉。例如，在附圖9a和9b中，積木式組件901根據積木式組件901的用戶選定定向以不同的方式被連接到結構902中。在附圖9a中，積木式組件901被連接到結構902的頂部。在附圖9b中，積木式組件901被連接到結構902中位於垂直平面上的突起903上。
在一個可選實施例中，允許積木式組件的自動重定向。例如，當在附圖5的步驟510和511中分析候選位置時，可以考慮新積木式組件的不同旋轉作為附加的候選位置，並且根據所實現的分級和隨後的連通性驗證來分析其。例如，當新積木式組件要在某任意角度上被連接到合葉上時，用戶不必精確地將新積木式組件對準到合葉的軸上。處理將估計旋轉後的位置並在旋轉之後連接新積木式組件。在某些實施例中，自動重定向被限制到預定的空間角度，例如45度、30度等，因而避免了大的旋轉，大的旋轉可能使用戶混淆並導致意外的結果。
上述處理的另一個優點在於，用戶接收到關於新積木式組件將被放置和連接到何處的清晰的指示。而且，考慮了由用戶控制的、屏幕上新積木式組件的2D位置的細小修正，從而提供了流暢自然的工作流程印象。
應該理解，本領域熟練技術人員可以在本發明的範圍之內實現上述方法的變型。例如，某些上述步驟的順序可以被改變，步驟可能被結合等。
例如，當新積木式組件已經被放置到3D場景之後，用戶可以啟動搜索工具以搜索類似的位置。在一個實施例中，搜索工具可以允許用戶逐步遍歷附圖5的有序列表520的所有位置，從而允許用戶選擇其中一個可能的位置。
術語「操縱」對象的數字表示是用來代表對於數字表示的任何受用戶控制的操作，例如新積木式組件的連接，把現存積木式組件從一個位置移動到另一個位置，或者任何改變積木式組件在3D場景中的位置的其他操作。
權利要求
1.一種由計算機實現的、藉助於二維光標移動來操縱三維虛擬積木模型的方法，所述虛擬積木模型包括多個虛擬積木式組件，其中每個虛擬積木式組件包括許多用於根據一組連接規則連接所述虛擬積木式組件和另一虛擬積木式組件的連接元件，所述方法包括-提供結構在三維坐標系中的數字表示，其中所述結構包括許多所述虛擬積木式組件；-藉助於光標在代表所述結構的投影的二維計算機顯示區域中的移動來定位要被連接到所述結構的第一虛擬積木式組件的二維投影，從而產生二維位置坐標；-根據所述二維位置坐標確定所述第一虛擬積木式組件在所述三維坐標系中的許多三維候選位置；-基於所述連接規則和一組預定的位置分級規則來選擇所述候選位置中的一個；以及-在所述選定候選位置上將所述第一積木式組件連接到所述結構。
2.根據權利要求1所述的方法，其中所述確定許多三維候選位置的步驟進一步包括確定所述第一虛擬積木式組件在所述三維坐標系中的許多候選定向。
3.根據權利要求1或2所述的方法，進一步包括-確定所述結構的許多候選連接元件，其中每個所述候選連接元件所述二維顯示區域內在所述第一虛擬積木式組件的連接元件的投影周圍的預定鄰域內具有投影；-基於所述連接規則和所述一組預定位置分級規則來選擇所述候選連接元件中的一個；以及-如果根據所述一組連接規則，所述第一虛擬積木式組件和所述結構之間的連接是有效的，則至少通過所選定的候選連接元件連接所述第一虛擬積木式組件與所述結構。
4.根據權利要求3所述的方法，其中所述選擇候選連接元件中一個的步驟進一步包括對所述候選連接元件進行分級，其中所述分級對於它們與虛擬攝像頭位置的距離來進行。
5.根據權利要求3或4所述的方法，其中所述選擇候選連接元件中一個的步驟進一步包括丟棄從當前虛擬攝像頭位置不可見的候選連接元件。
6.根據權利要求3到5中任一項所述的方法，其中所述選擇候選連接元件中一個的步驟進一步包括對所述候選連接元件進行分級，其中所述分級是對於它們的二維投影與所述第一虛擬積木式組件的相應連接元件的二維投影的距離來進行的。
7.根據權利要求3到6中任一項所述的方法，其中對於每個虛擬積木式組件，所述結構的數字表示包括許多對應於所述虛擬積木式組件至少一個表面的規則的柵格，其中每個規則的柵格包括許多柵格點，每個柵格點代表連接元件。
8.根據權利要求7所述的方法，其中所述第一虛擬積木式組件的連接元件的投影周圍的預定鄰域的直徑對應於所述相應規則柵格的相鄰柵格點之間的間距。
9.根據權利要求1到8中任一項所述的方法，其中所述確定許多候選位置的步驟進一步包括旋轉所述第一積木式組件以獲得旋轉後的積木式組件的候選位置。
10.根據權利要求9所述的方法，其中所述第一積木式組件的旋轉被限制到用戶選定的定向周圍的預定空間角度。
11.根據權利要求1到10中任一項所述的方法，進一步包括接收控制所述第一虛擬積木式組件的用戶選定定向的用戶命令。
12.根據權利要求11所述的方法，其中所述用戶選定定向被限制到一組離散定向中的一個。
13.根據權利要求1到12中任一項所述的方法，其中所述二維投影是平行投影。
14.一種包括存儲介質的數據處理系統，其中在所述存儲介質上存儲有包括程序代碼單元的電腦程式，當所述程序在所述數據處理系統上運行時，所述程序代碼單元用於執行權利要求1到13中任一項的所有步驟。
15.一種包含程序代碼單元的電腦程式，當所述程序在計算機上運行時，所述程序代碼單元用於執行權利要求1到13中任一項的所有步驟。
16.一種包含程序代碼單元的電腦程式產品，所述程序代碼單元存儲在計算機可讀取介質上，當所述電腦程式產品被運行在計算機上時，所述程序代碼單元用於執行權利要求1到13中任一項的方法。
17.一種在其上存儲有包含電腦程式單元的電腦程式的計算機可讀取存儲介質，當所述程序被運行在計算機上時，所述程序代碼單元用於執行權利要求1到13中任一項的所有步驟。
18.一種被實現為載波的數據信號，所述數據信號包括程序代碼單元，其中當所述程序代碼單元被運行在計算機上時，所述程序代碼單元用於執行權利要求1到13中任一項的所有步驟。
全文摘要
依靠二維光標移動來操縱三維虛擬積木模型的方法，虛擬積木模型包括許多虛擬積木式組件，每塊虛擬積木式組件包括許多用於根據一組連接規則連接該虛擬積木式組件與另一虛擬積木式組件的連接元件，該方法包括依靠光標在代表該模型二維投影的計算機顯示區域中的移動來定位要被連接到結構的第一虛擬積木式組件的二維投影，得到該虛擬積木式組件的二維位置；由該二維位置確定第一虛擬積木式組件在三維坐標系中的許多候選位置；根據連接規則和一組預定的位置分級規則來選擇候選位置其中之一；以及在選定候選位置上將第一積木式組件連接到結構。
文檔編號G06F3/0484GK1791850SQ200480013672
公開日2006年6月21日 申請日期2004年5月13日 優先權日2003年5月20日
發明者龍尼·謝勒, 奧爾加·提姆森科, 內奧米·克拉克, 彼得·阿克 申請人:英特萊格公司