設計由深度元素表示的建模體的製作方法

2023-05-28 01:13:46 3

設計由深度元素表示的建模體的製作方法
【專利摘要】提供一種用於設計建模體的計算機實現的方法。該方法包括提供表示所述建模體的一組深度元素(S10)，每個深度元素包括表示線和所述建模體之間的交叉的至少一條線段的組，其中所述一組深度元素被劃分割為鄰近深度元素群組，其中給每個群組分配依賴於包括在該群組中的每個深度元素中的線段的最大數量的存儲空間；提供對所述建模體的造型操作(S20)；以及響應於所述造型操作更新(S30)所述一組深度元素。這種方法改善了一組深度元素組所表示的建模體的設計。
【專利說明】設計由深度元素表示的建模體
【技術領域】
[0001]本發明涉及電腦程式及系統領域，更特別地涉及用於設計由一組深度元素表示的建模體的方法、系統和程序。
【背景技術】
[0002]在市場上提供了許多用於對象設計、工程和製造的系統和程序。CAD是計算機輔助設計的首字母縮略詞，例如其涉及用於設計對象的軟體解決方案。CAE是計算機輔助工程的首字母縮略詞，例如其涉及用於仿真未來產品的物理行為的軟體解決方法。CAM是計算機輔助製造的首字母縮略詞，例如其涉及用於定義製造處理和操作的軟體解決方案。在這種系統中，圖形用戶界面(⑶I)在技術效率方面發揮了重要的作用。這些技術可嵌入產品生命周期管理(PLM)系統中。PLM指的是這樣一種經營策略:在擴展企業的概念上幫助公司在產品的從概念到其生命期終止的開發中共享產品數據、應用通用處理並利用共同知識。
[0003]Dassault Systemes 提供的 PLM 解決方案(商標為 CATIA、EN0VIA 以及 DELMIA)提供了組織產品工程知識的工程中心、管理製造工程知識的製造中心，以及使得企業能夠集成並連接到工程中心和製造中心的企業中心。系統一起傳送連結產品、處理、資源的開放對象模型，以實現驅動優化產品定義、製造預備、生產和服務的動態的基於知識的產品創建和決策支持。
[0004]這些系統中的一些允許用一組深度元素表示建模體。一些論文或專利文獻特別提出使用深度元素表示進行加工仿真或交互造型。
[0005]這些文獻的例子是:
[0006]—Computer-Aided Design and Applications,2009 中 Xiaobo Peng 和 WeihanZhang 的題為 「A Virtual Sculpting System Based on Triple DexelModels withHaptics」的論文；
[0007]--Proceedings of the 21st annual conference on Computer graphicsandinteractive techniques,1994 中 Yunching Huang 和 James H.0liver 的題為「NCMilling Error Assessment and Tool Path Correction，，的論文；
[0008]—SM，03Proceedings of the eighth ACM symposium on Solid modelingandapplications 中 Heinrich Muller, Tobias Surmann, Marc Stauter, FrankAlbersmann,Klaus Weinert 的「Online Sculpting and Visualization ofMult1-Dexel Volumes」；
[0009]—Virtual and Physical Prototyping,2006 中 Yongfu Ren, Susana K.LaiYuen以及 Yuan-Shin Lee 的題為「Virtual prototyping and manufacturingplanning by usingtr1-dexel models and haptic force feedback，，的論文；
[0010]--The International Journal of Advanced Manufacturing Technology,1995中 Sabine Stifter 的題為 「Simulation of NC machining based on the dexelmodel:Acritical analysis，，的論文；
[0011]--Computer Graphics International, 1998.Proceedings 中 Konig, A.H.以及Groller, E.的題為「Real time simulation and visualization of NC mi I lingprocessesfor inhomogeneous materials on low-end graphics hardware，，的論文；
[0012]—美國專利5，710，709 ;
[0013]—美國專利7,747,418。
[0014]GPGPU(圖形處理單元上的通用計算)是使用圖形處理單元(GPU)的技術，所述圖形處理單元典型地僅處理計算機圖形的計算，以在傳統上由中央處理單元(CPU)處理的應用程式中執行計算。一些論文考慮將現代圖形處理單元(GPU)的計算能力用於深度元素表示。這些論文使用LDNI (分層的標準深度圖像)算法，其與特定存儲器模型相關聯。
[0015]這些論文的例子是:
[0016]--CCP:94:Proceedings of the Seventh International ConferenceonEngineering Computational Technology 中 B.Tukora和 T.Szalay 的題為「GPGPU-basedMaterial Removal Simulation and Cutting Force Estimation」 的論文；
[0017]--Proceedings of ASME international design engineeringtechnicalconferences.Brooklyn (NY)中 Charlie C.L.Wang和 Yong Chen 的題為「LayeredDepth-Normal Images:a Sparse Implicit Representation of SoIidModeIs^ 的論文。
[0018]然而，尤其從存儲器性能的角度以及用戶使用的角度來看，以上列出的解決方案缺乏效率。在此上 下文中，仍然需要改良用於設計由一組深度元素表示的建模體的解決方案。

【發明內容】

[0019]因此，根據一個方案，提供了一種用於設計建模體的計算機實現的方法。該方法包括:提供表示建模體的一組深度元素。每個深度元素包括表示線和建模體之間的交叉的至少一條線段的組。所述一組深度元素被劃分為鄰近深度元素的群組。並且給每個群組分配依賴於包括在該群組中的每個深度元素中的線段的最大數量的存儲空間。該方法還包括提供對建模體的造型操作，以及響應於所述造型操作更新所述一組深度元素。
[0020]該方法可包括下述中的一個或多個:
[0021]-更新所述一組深度元素包括確定受所述造型操作影響的鄰近深度元素的群組，以及更新所確定的群組中的每一個群組；
[0022]-更新所確定的群組中的每一個群組包括:對於相應群組，通過並行處理更新所述相應群組中的深度元素；
[0023]-更新所述相應群組中的深度元素包括:對於所述相應群組中的相應深度元素，評價造型操作對所述相應深度元素的影響，並從而修改所述相應深度元素；
[0024]-評價造型操作對所述相應深度元素的影響包括:評價造型操作對所述相應深度元素的線段的影響；
[0025]-更新所述相應群組中的深度元素是由SMD(單指令多數據)並行處理執行的。
[0026]-所述方法進一步包括:當包括在更新後的群組中的每個深度元素中的線段的最大數量被修改時，調整分配給所述更新後的群組的存儲空間；
[0027]-所述一組深度元素被劃分為鄰近像素的群組以適應執行所述方法採用的硬體和/或造型上下文；[0028]進一步提出一種用於設計建模體的系統，其中該系統包括在其上記錄有用於執行上述方法的指令的存儲器，以及與存儲器耦合用於執行指令的至少一處理器。
[0029]所述處理器是大型並行處理單元。所述系統包括適於啟動指令的執行的至少一個⑶I。所述⑶I可包括GPU，所述處理器是GPU。
[0030]進一步提出一種包括用於執行上述方法的指令的電腦程式。
[0031 ] 進一步提出一種其上記錄有上述電腦程式的計算機可讀存儲介質。
【專利附圖】

【附圖說明】
[0032]現在將通過非限定性例子並參考附圖來描述本發明的實現例，其中:
[0033]—圖1示出了方法的例子的流程圖；
[0034]—圖2示出了圖形用戶界面的例子；以及
[0035]-圖3示出了客戶端計算機系統的例子；
[0036]—圖4_圖8和圖14不出了方法的例子；
[0037]—圖9-圖13示出了現有技術。
[0038]具體實現方式
[0039]圖1示出了用於設計建模體的計算機實現的方法(此後稱為該方法)的例子的流程圖。該方法包括提供一組深度元素(Sio)。所述一組深度元素表示建模體。(一組深度元素中的)每個深度元素包括至少一條線段的組。這種線段表示線和建模體之間的交叉。所述一組深度元素被化分為鄰近深度元素的群組。給每個群組分配依賴於包括在所述群組中的每個深度元素中的線段的最大數量的存儲空間。所述方法還包括提供對建模體的造型操作(S20)。所述方法進一步包括響應於造型操作來更新(S30)所述一組深度元素。這種方法改進了對由一組深度元素表示的建模體的設計。
[0040]還提供有由一組深度元素表示的建模體，其中(一組深度元素中的)每個深度元素包括至少一條線段的組。這種線段表示線和建模體之間的交叉。所述一組深度元素被劃分為鄰近深度元素的群組。給每個群組分配依賴於包括在所述群組中的每個深度元素中的線段的最大數量的存儲空間。下面描述的方法的特徵和例子同樣應用到這種建模體。
[0041 ] 還提供有用於通過一組深度元素表示建模體的編碼方案。該編碼方案包括提供體的定義。編碼方案接著定義一組線並計算所述一組線與體的交叉，並確定相應的深度元素。該編碼方案進一步將所述一組深度元素分為鄰近深度元素的群組，並給每個群組分配依賴於包括在所述群組中的每個深度元素中的線段的最大數量的存儲空間。提供一組深度元素的步驟(SlO)可實現該編碼方案。以下描述的方法的特徵和例子也可應用於這種編碼方案。
[0042]該方法可以包括在設計CAD建模對象的處理中。「設計CAD建模對象」是指詳細描述建模對象的處理的至少一部分的任意動作或動作序列。因此，該方法可以包括從草圖(scratch)開始創建CAD建模對象。可替換地，該方法可以包括提供之前創建的CAD建模對象，接著修改所述CAD建模對象。無論如何，該方法設計的建模體可表示CAD建模對象或CAD建模對象的至少一部分，例如CAD建模對象佔用的3D空間。由於該方法改善了由一組深度元素表示建模體的設計，所以該方法也改善了 CAD建模對象的設計。
[0043]建模對象是由存儲在計算機系統的存儲器中的數據所定義的任何對象。通過擴展，「建模對象」的表述是指數據本身。CAD建模對象是由在CAD系統的存儲器中存儲的數據所定義的任何對象。根據系統的類型，建模對象可由不同類型的數據所定義。CAD系統是至少適合於基於建模對象的圖形表示設計建模對象的任何系統，例如CATIA。因此，定義CAD建模對象的數據包括允許表示建模對象的數據(例如幾何數據,如包括空間中的相對位置)。
[0044]該方法可包括在製造處理中，製造處理可以包括:在執行該方法之後，產生與建模體相對應的物理產品。無論如何，該方法設計的建模體可以表示製造對象。因此，建模體可為建模固體(即，表示固體的建模對象)。製造對象可為產品，例如零件或零件的組件。由於該方法改善了建模體的設計，所以該方法也改進了產品的製造，並因此增加了製造處理的生產率。可使用例如DELMIA之類的CAM系統來實現該方法。CAM系統是至少適於定義、仿真和控制製造處理和操作的任何系統。
[0045]該方法是計算機實現的。這意味著該方法在至少一個計算機或任何類似的系統上執行。除非另有說明，否則該方法的所有步驟由計算機執行，即無需用戶的幹涉。例如，更新步驟(S30)可由單獨計算機執行，而提供一組深度元素的步驟(SlO)和提供造型操作的步驟(S20)可由單獨計算機執行或通過用戶交互執行。事實上，提供一組深度元素的步驟(SlO)可由用戶發起。因此，該方法允許基於用戶可能提供的造型操作來自動更新(S30)表示建模體的一組深度元素。還值得一提的是，該方法的步驟可允許用戶的介入。例如，用戶可介入例如修改由計算機運行的算法的結果，例如修改已經被更新(S30)的一組深度元素。這相當於修改所更新的一組深度元素的步驟，在更新步驟(S30)之後執行該修改步驟。
[0046]該方法的計算機實現的典型例子是使用適合此目的的系統執行該方法。該系統可包括其上記錄有用於執行該方法的指令的存儲器。換句話說，軟體已經在存儲器上準備好以立即使用。該系統因此適於執行該方法而不需要安裝任何其它軟體。這樣的系統也可包括用於執行指令的與存儲器耦合的至少一處理器。換句話說，該系統包括在耦合到處理器的存儲器上編碼的指令，所述指令提供用於執行該方法的模塊。這種系統是用於設計建模體的有效工具。
[0047]這種系統可以是CAD系統。該系統也可以是CAE和/或CAM系統，並且CAD建模對象也可以是CAE建模對象和/或CAM建模對象。事實上，CAD、CAE以及CAM系統並非彼此排他的，這是因為建模對象可由與這些系統的任何組合相對應的數據定義。
[0048]系統可包括用於例如由用戶發起指令的執行的至少一個⑶I。尤其是，⑶I可以允許用戶通過以下操作來發起提供一組深度元素的步驟(Sio):通過根據草圖設計這樣的一組深度元素，或者從系統的存儲器中或在系統的外部但耦合到該系統(例如通過網絡服務)的存儲器中獲取一組深度元素。GUI也可以允許用戶提供造型操作(S20)。Gn可以包括GPU。在這種情況下，處理器可以是GPU。換句話說，執行該方法的至少部分步驟(特別是執行更新(S30)步驟)的處理器可以是GPU。這種系統是用戶設計建模體的有效工具。由於基於深度元素的算法很好地適於大規模並行硬體，所以很自然地想到使用現代圖形處理單元(GPU)的計算能力。
[0049]建模體可為3D (即三維)。這意味著建模體是由允許其3D表示的數據定義的。3D表示允許從所有角度查看所表示的體。例如，當使用3D表示時，可以處理建模體並可以圍繞著建模體的任何軸或圍繞在其上顯示所述表示的屏幕中的任何軸轉動該建模體。這特別地排除了不是3D建模的2D圖標。3D表示的顯示有利於設計(即，提高了設計者統計地完成其任務的速度)。這加速了工業的製造過程，這是因為產品的設計是製造處理的一部分。
[0050]圖2示出了代表性的CAD系統的⑶I的例子。
[0051]⑶I 2100可以是代表性的類CAD界面，具有標準的菜單欄2110、2120以及底部和側面工具欄2140、2150。本領域公知的是，這樣的菜單欄和工具欄包括一組用戶可選圖標，每一圖標與一個或多個操作或功能相關聯。這些圖標中的一些與軟體工具相關聯，適用於對在⑶I 2100上顯示的3D建模對象2000進行編輯和/或在其上工作。軟體工具可分組為工作檯。每一工作檯包括軟體工具的子集。特別地，工作檯之一是編輯工作檯，適用於編輯建模產品2000的幾何特徵。在操作中，例如，設計者可預先選擇對象2000的一部分，並接著通過選擇合適的圖標來發起操作(例如造型操作、或任何其它操作，例如改變維度、顏色等等)或編輯幾何約束。例如，典型的CAD操作是對在屏幕上顯示的3D建模對象的衝壓或摺疊進行建模。
[0052]⑶I可以例如顯示與被顯示的產品2000相關的數據2500。在圖2的例子中，顯示為「特徵樹」的數據2500及其3D表示2000屬於包括制動鉗和盤的制動組件。GUI可進一步示出例如有助於對象的3D定向、觸發所編輯的產品的操作的仿真的各種類型的圖形工具2130、2070、2080，或呈現所顯示的產品2000的各種屬性。指針2060可由觸覺裝置控制以允許用戶與圖形工具交互。
[0053]圖3示出了作為客戶端計算機系統(例如，用戶的工作站)的系統架構的例子。
[0054]客戶端計算機包括連接到內部通信總線1000的中央處理單元(CPU) 1010、也連接到總線的隨機存取存儲器(RAM) 1070。客戶端計算機還設置有圖形處理單元(GPU) 1110，該圖形處理單元1110與連接到總線的視頻隨機存取存儲器1100相關聯。視頻RAM 1110在本領域內可稱為幀緩衝器。大容量存儲裝置控制器1020管理對大容量存儲裝置(例如，硬碟驅動器1030)的訪問。適於有形地體現電腦程式指令和數據的大容量存儲裝置包括所有形式的非易失性存儲器，舉例來說包括半導體存儲裝置，例如EPROM、EEPROM以及快閃記憶體裝置；磁碟，例如內部硬碟以及可移動磁碟；磁光碟；以及⑶-ROM盤1040。前述提及的任何裝置可由特殊設計的ASIC (專用集成電路)補充或集成在ASIC中。網絡適配器1050管理對網絡1060的訪問。客戶端計算機也可包括觸覺裝置1090，例如指針控制裝置、鍵盤等等。如參考圖2所提及的，指針控制裝置用在客戶端計算機內，以允許用戶將指針選擇性地定位在屏幕1080的任何期望的位置。對於屏幕，其意味著可以在其上執行顯示的任何支持設備，例如計算機監視器。另外，指針控制裝置允許用戶選擇各種命令，和輸入控制信號。指針控制裝置包括向系統輸入控制信號的若干信號生成裝置。典型地，指針控制裝置可為滑鼠、用於產生信號的滑鼠按鈕。
[0055]為了使得該系統執行該方法，提供包括用於由計算機執行的指令的電腦程式。所述指令包括用於此目的的模塊。該程序可以例如在數字電子電路中實現，或在計算機硬體、固件、軟體或其組合中實現。本發明的裝置可以用電腦程式產品實現，該電腦程式產品有形地體現在機器可讀存儲裝置中並由可編程處理器執行；本發明的方法步驟可由通過操作輸入數據並生成輸出執行指令程序以實現本發明功能的可編程處理器執行。指令可有利地在一個或多個電腦程式中實現，所述一個或多個電腦程式在可編程系統上是可執行的，該可編程系統包括耦合來從數據存儲系統接收數據和指令並向數據存儲系統傳輸數據和指令的至少一個可編程處理器、至少一個輸入裝置和至少一個輸出裝置。應用程式可使用高級過程程式語言或面向對象程式語言實現，或者如果希望的話使用彙編語言或機器語言實現；無論如何，語言可以是編譯語言或解釋型語言。程序可以是完整安裝程序或更新程序。在後一種情況下，程序將現有的CAD系統更新到使該系統適於執行該方法的狀態。
[0056]該方法包括提供表示建模體的一組深度元素(SlO)。這允許建模體的輕度表示(換句話說，可使用很少的存儲空間表示建模體)。這也使得建模體的表示更易於處理。尤其是，在建模體由深度元素組表示時，由於深度元素組的數據結構，可以十分有效地執行建模體的設計操作。事實上，可以以高響應和高魯棒性執行設計操作。
[0057]術語「深度元素(dexel) 」眾所周知是「深度元素(cbpth element) 」的縮略(就像術語「像素(Pixel)」是「圖像元素(picture element) 」的縮略一樣)。深度元素的概念在大量的研究論文中均有提及。在該方法的上下文中，深度元素包括至少一條線段(即一對3D點)的組。在例子中，建模體包括至少一個深度元素，該深度元素包括至少兩條線段的組。如果深度元素的線段是幾個的話，則深度元素的線段可為有序的(在這種情況下，深度元素是列表)或是無序的。深度元素的線段表示線和建模體的交叉。換句話說，考慮到虛擬線和建模體交叉，深度元素是來源於給定線的線段的組並且由交叉的計算產生。因此提供一組深度元素(SlO)可包括計算這種交叉，例如通過追蹤虛擬線並計算其與建模體的交叉，該建模體初始可由B-Rep或任何其它體表示所表示。因此所述一組深度元素表示建模體。
[0058]值得重視的是，一組深度元素被提供(SlO)為計算機實現的數據。因此，在以上和以下提供的關於建模體的任何表示的定義具有來自數據結構角度的含義。例如，線段可以被提供為一對3D位置(例如，彼此連結的兩個3D位置)。3D位置本身可以被提供為與參考3D框架相關聯的三個坐標(例如，浮點)的列表。深度元素是線段的組，這意味著線段是在組結構中連結在一起的。一組深度元素中的深度元素也可連結到一起。由一組深度元素表示建模體(所述深度元素本身包括至少一條線段的組)允許建模體的快速更新(S30)。
[0059]現在參考圖4-圖6示出深度元素的概念，圖4-圖6呈現了將一組深度元素作為深度元素結構67提供的步驟(SlO)的例子。
[0060]給定建模體和給定無限線，深度元素是表示無限線和建模體的交叉的線段(或間隔)的組。在存儲器中，將線段的該組捕獲為每條線段的一組邊界點。深度元素結構是被組織(例如，被在直角坐標網上排序)的一組深度元素(每個包括一組線段)。圖4和圖5示出了建模體40以及10X10網格線50。如圖4所示出的，本例子的方法包括提供建模體40，例如B-R印。如圖5所示，本例子的方法接著包括定義與建模體40 (至少部分)交叉的IOX 10網格線50。如圖6所示出的，本例子的方法接著包括計算包括線段60和/或線段62的組的深度元素65。在圖上圈出一個深度元素65。深度元素65可包括幾條線段60或一條線段62，這取決於線50與建模體40是在一個點上還是在幾個分開的點處交叉。當然，可替換地，該方法可以從存儲器獲取深度元素65。無論如何，都因而提供了深度元素結構67。
[0061]圖6示出了獲得的深度元素結構67。值得注意的是，不是所有的線50都與建模體40交叉(在例子中，只有五十二條線與建模體40交叉)，從而產生出許多深度元素65 (不與建模體40交叉的線事實上可被丟棄並且不產生深度元素)。此外，一些線50通過一條線段62與建模體40交叉(例如，深度元素(2，3)或深度元素(9，6))，而其它線通過幾條線段60與建模體40交叉，例如通過兩條線段(例如深度元素(7，7)或深度元素(4，7))，或通過三條線段(深度元素(2，8)或深度元素(5，8))，或通過四條線段(深度元素(2，9)或深度元素(4，9))。獲得的深度元素結構67包括五十二個深度元素65，該五十二個深度元素65包括具有一條線段62的三十六個深度元素65、具有兩條線段60的六個深度元素65、具有三條線段60的五個深度元素65以及具有四條線段60的五個深度元素。
[0062]在(SlO)提供的一組深度元素可為三維深度元素(tridexel)結構。三維深度元素結構是通過包括三個深度元素結構定義的，典型地，一個深度元素結構平行於X軸，一個深度元素結構平行於I軸，並且一個深度元素結構平行於Z軸。該方法可包括在任何時間(例如，在提供(S20)和更新(S30)期間)顯示建模體的圖形表示。此顯示可基於一組深度元素。由於三維深度元素結構較少依賴於「觀察方向」，所以三維深度元素結構提供良好的顯示。尤其當用戶改變視角時，三維深度元素結構提供更精確的顯示。
[0063]圖6-圖8中的每個代表表示相同建模體的深度元素結構。換句話說，可由三維深度元素數據定義建模體，該三維深度元素數據包括圖6-圖8的三個深度元素結構。圖6示出了沿著y軸的深度元素結構67。圖7示出了沿著X軸的深度元素結構68。圖8示出了沿著z軸的深度元素結構69。在每個圖中，深度元素的線平行於各自的軸。
[0064]在數據中也可以提供在線段的端點處建模體的邊界的外部法向量。這允許更精細地呈現建模體。
[0065]該方法還包括提供對建模體的造型操作(S20)。造型操作是系統提供的用於對建模體進行造型的任何操作。通過對建模體造型，意味著通過布爾運算從建模體增加和/或移除體。因此，造型操作是建模體上的至少一個體布爾運算的任意組合。例如，局部體移除和局部體增加是造型操作，而表面的擠壓不是造型操作，這是因為其不基於任何布爾運算。造型處理是具有至少一個造型操作的任何序列。在例子中，造型操作是一系列連續的布爾運算，其涉及在持續時間段內被增加到建模體(或從其減去)的連續體(即，非間斷的)。例如，造型操作表示機械加工。
[0066]因此，一組深度元素可表示任何固體，該方法可仿真固體的真正造型。特別的，利用計算機輔助設計系統或計算機輔助製造系統可將該方法包括在實時加工仿真中。換句話說，固體可為原料，而該方法可顯示由切削刀具虛擬加工的原料的形狀。在這種情況下，建模體表示原料，而操作是切削操作。此例子可推廣到向零件增加材料的其他製造處理，例如在虛擬粘土上的合成製造和形狀造型。也可推廣到所有的傳統固體建模應用，包括機械設計、形狀設計、建築結構等等。最後，由於其工作能力，該方法可處理更加高級的應用，例如交互式3D造型。更通用地，造型操作可表示加工操作。在這種情況下，建模體可表示經歷加工操作的工件，因此該方法改善了工件加工的仿真。從而該方法可以作為測試虛擬加工處理的良好的基礎。
[0067]事實上，該方法進一步包括響應於(即根據)造型操作更新(S30)(即修改)一組深度元素。換句話說，該方法將造型處理應用到初始提供(Sio)的一組深度元素。更新後的一組深度元素表示造型(例如加工)之後的對象。
[0068]每個深度元素包括一組線段。與建模體交叉的線的所有線段被分組為一個深度元素。例如由於其允許並行處理，因而允許對建模體的逐線的以及因此更有效率的處理。此夕卜，將所述一組深度元素化分為鄰近深度元素的群組。當深度元素之間的距離在預定閾值之下時，這些深度元素被稱為鄰近的。因此，一組深度元素可被化分(即，劃分為深度元素的不相交子集，這些子集的重組構成深度元素的整個組)為鄰近深度元素(即，一群組內的兩個深度元素必須是鄰近的)。第一深度元素和第二深度元素之間的距離是第一深度元素的線和第二深度元素的線之間的距離。第一線和第二線之間的距離可為測量第一線距離第二線有多遠的任意距離。例如，如果線是平行的，則所述距離可為第一線的點和第二線的點之間的最小歐幾裡德距離。如果線不是平行的，則所述距離可為第一線的點和第二線的點之間的最小歐幾裡德距離，所述的兩個點屬於一組深度元素的凸包。
[0069]給每個群組分配依賴於包括在所述群組中的每個深度元素中的線段的最大數量的存儲空間。換句話說，分配給一個群組的存儲空間是包括在所述群組中的每個深度元素中的線段的最大數量的函數，該函數是遞增函數，可以是線性函數。這允許最優地利用分配給一組深度元素的存儲空間。事實上，造型操作(尤其是表示加工操作的那些造型操作)通常對建模體具有局部影響。將深度元素分組為鄰近群組允許在更新(S30)時對所述一組深度元素進行逐群組處理。因此，如將參考例子所描述的，可以在逐群組的基礎上分配存儲器並優化全局分配的存儲器。
[0070]將一組深度元素劃分為鄰近深度元素的群組，以適應執行所述方法所應用的硬體和/或造型上下文(sculpting context)。換句話說,調整所述劃分以適應於(即可依賴於)用於執行該方法的硬體(例如處理器和/或存儲器)和/或造型上下文(即關於方法的上下文的信息)。例如，在一群組內的鄰近深度元素的最大數量可為處理器可以執行的並行線程的數量的遞增函數。造型上下文可包括關於建模體和/或造型操作的信息。例如，造型上下文可測量建模體的複雜度(例如，其不規則程度的度量)和/或造型操作的複雜度(例如，虛擬地用於執行造型操作的工具的幾何體)。造型上下文也可包括關於這種工具的尺寸的信息。例如，在一個群組內的鄰近深度元素的最大數量可為建模體的複雜度、造型操作的複雜度的遞減函數，和/或造型工具尺寸的遞增函數。
[0071]現在討論現有技術以突出該方法的優勢。
[0072]在現有技術中公知的是，LDNI實現的決定性弱點是達到給定精確級別所必需的存儲器的大小。已知的LDNI實現利用「幀緩衝器」和「層」，並通過利用OpenGL和Shaders編程的GPU處理表示建模體的一組深度元素。「幀緩衝器」是位於GPU中的存儲空間，其初始專用於以像素的二維陣列存儲圖像。GPGPU技術利用這種幀緩衝器來存儲深度間隔(S卩，深度元素的線段)的二維陣列。必須理解的是，幀緩衝器的每個元件僅包括一個線段。「層」按如下所定義。在每個深度元素中，根據深度順序對線段排序。「層」是具有相同深度順序的所有線段的組。
[0073]使用OpenGL和Shaders編程的現有技術計算要求整個幀緩衝器存儲每個層。因此，給定深度元素結構和記錄深度元素的間隔的最大數量Nmax，接著計算Nmax個層並將其存儲在一樣多的幀緩衝器中。即使大部分所計算的幀緩衝器是非常稀疏的，出於性能的目的，在該上下文中的嚴格的存儲器管理按照人們所期望地在GPU板上保存整個建模常駐程序(resident)。因此，如果所述一組深度元素包括Nx*Ny個深度元素，則板上存儲器必須保留大小為Nx*Ny*Nmax的緩衝器。這參考圖9-圖13示出。
[0074]對於圖6的深度元素結構67，根據10*10的網格線，幀緩衝器的大小是Nx*Ny =10*10。如圖9所示，由於至少一個深度元素(例如圖6中圈出的深度元素65)包括四條線段60，所以由深度元素定義了四層(72、74、76、78)。現在還參考圖10-圖13，圖10-圖13將幀緩衝器表示為大小為10*10的網格，在該網格的框中，當幀緩衝器存儲針對該網格上的與所述框相對應的位置的和與該幀緩衝器相對應的層的深度元素線段時，呈現叉號。第一幀緩衝器82存儲第一層72線段；第二幀緩衝器84存儲第二層74線段；第三幀緩衝器86存儲第三層76線段；第四幀緩衝器88存儲第四層78線段。圖10-圖13的表格示出了幀緩衝器82-88中已使用和未使用的存儲器插槽。標記為X的框87存儲一條線段，空白框89是未使用的存儲器。必須理解的是，所有四個幀緩衝器(82、84、86、88)是分配的存儲器，其示出了大量未使用的存儲器。
[0075]對於現有技術的該例子，分配的存儲器與已使用的存儲器的平衡如下。所有四個幀緩衝器所需要的存儲器的大小是Nx*Ny*Nmx = 10*10*4 = 400，而已使用的存儲器是深度元素的間隔的數量:83。另外，LDNI幀緩衝器的稀疏數據表示將不會直接從通用的稀疏矩陣表示推導出，例如層的連結列表或在深度元素/線程級別的間接表。事實上，這樣的技術並不適合大規模並行硬體結構和相應的程序設計抽象，從而將導致低效率的執行速度和數據流。
[0076]與現有技術相反，該方法允許快速且魯棒的更新(S30)，同時使用相對較少的存儲空間。事實上，被組織為一組深度元素(每個深度元素包括至少一條線段的組)的數據結構允許並行處理。劃分為鄰近深度元素的群組和分配依賴於包括在群組中的每個深度元素中的線段的最大數量的存儲空間允許基於逐群組地執行並行處理。由於造型操作通常具有局部影響，所以這允許獲得並行處理的優點，同時避免現有技術中佔據的存儲器大小方面的不便。
[0077]更新(S30)所述一組深度元素可包括確定受造型操作影響的鄰近深度元素的群組以及更新每個所確定的群組。換句話說，更新(S30)對在更新時實際上要被被修改的群組進行修改，以便獲得效率。事實上，可能有用的是預測造型操作影響鄰近深度元素的哪個群組，例如以加速計算。
[0078]更新每個確定的群組可包括:對於相應群組，通過並行處理更新所述相應群組中的深度元素。這允許更快速的更新(S30)，因此，如果顯示了所述一組深度元素，則這允許對提供造型操作的用戶動作的快速響應。
[0079]並行處理由系統同時執行多個任務所組成。在該方法的情況下，對相應群組中的深度元素進行更新可包括在相應群組中的每個深度元素上運行單一的指令線程。因此，更新相應群組中的深度元素可由SMD(單指令多數據)並行處理執行。特別地，執行該方法的系統的處理器可為大規模並行處理單元，例如如果所述系統聯網有10個或100個以上的處理器。
[0080]對於每個深度元素，通用建模操作符(例如布爾運算、偏移或衝突探測)歸結為其一維的對應部分，也就是線段上的簡單操作。由於對一個深度元素的計算和更新不依賴於對其它深度元素的相應操作，所以該模型很好地適用於大規模並行處理。
[0081]現在討論和示出工作群組和單指令多數據執行。該方法可通過工作組和單指令多數據執行。鄰近深度元素的群組可構成工作群組，更新步驟(S30)可包括被確定為受造型操作影響的每個群組上的SMD執行(所述確定可為SMD執行的第一步)。[0082]工作群組和SMD (單指令多數據)執行是OpenCL概念。也就是，屬於相同工作群組的所有線程根據「單指令多數據」的方式運行。舉例而言，現在考慮輸出兩個輸入數字中最大數的非常簡單的程序:即max(a，b)，其中a和b是兩個輸入數字。
[0083]所述程序可包括下述指令:
[0084]01 if (a > b) then
[0085]02 c: = a
[0086]03 else
[0087]04 c:= b
[0088]05 end if
[0089]06 return c
[0090]此程序包括六條指令。現在考慮下述「Test」程序，其通過三次調用「max」程序而計算三對數字中的最大數。
[0091]程序Test
[0092]X:= max(5,4)
[0093]y: = max(2,6)
[0094]z: = max (3, 3)
[0095]end.[0096]「Test」程序的順序運行是計算機連續執行第一次調用的指令1、2、5、6，接著第二次調用的指令1、3、4、5、6，以及第三次調用的指令1、3、4、5、6。這導致了執行十四條指令。
[0097]現在，屬於相同工作群組的三個線程可執行「Test」程序。根據SMD策略，每個線程運行對「max」程序的一次調用。這意味著「同時」執行對「max」程序的所有三次調用的指令，雖然它們處理的是不同的數據集。更精確地，表1示出了逐步的處理。
[0098]
【權利要求】
1.一種用於設計建模體的計算機實現的方法，其中所述方法包括: 提供表示所述建模體的一組深度元素(Sio)，每個深度元素包括表示線和所述建模體之間的交叉的至少一條線段的組，其中所述一組深度元素被劃分為鄰近深度元素群組，其中給每個群組分配依賴於包括在該群組中的每個深度元素中的線段的最大數量的存儲空間； 提供對所述建模體的造型操作(S20);以及 響應於所述造型操作更新(S30)所述一組深度元素。
2.如權利要求1所述的方法，其中更新所述一組深度元素包括:確定受所述造型操作影響的鄰近深度元素群組，以及更新每個所確定的群組。
3.如權利要求2所述的方法，其中更新每個所確定的群組包括:對於相應群組，通過並行處理更新所述相應群組中的深度元素。
4.如權利要求2或3所述的方法，其中更新所述相應群組中的深度元素包括:對於所述相應群組中的相應深度元素，評價所述造型操作對所述相應深度元素的影響，並從而修改所述相應深度元素。
5.如權利要求4所述的方法，其中評價所述造型操作對所述相應深度元素的影響包括:評價所述造型操作對所述相應深度元素的線段的影響。
6.如權利要求5所述的方法，其中更新所述相應群組中的深度元素是由SMD(單指令多數據)並行處理執行的。
7.如權利要求2-6的任一項所述的方法，其中所述方法進一步包括:當包括在所更新的群組中的每個深度元素中的線段的最大數量被修改時，調整分配給所更新的群組的存儲空間。
8.如權利要求1-7的任一項所述的方法，其中所述一組深度元素被劃分為鄰近像素群組以適應執行所述方法所採用的硬體和/或造型上下文。
9.一種用於設計建模體的系統，其中所述系統包括在其上記錄有用於執行如權利要求1-8的任一項所述的方法的指令的存儲器，以及與所述存儲器耦合用於執行所述指令的至少一個處理器。
10.如權利要求9所述的系統，其中所述處理器是大規模並行處理單元。
11.如權利要求9或10所述的系統，其中所述系統包括適於啟動所述指令的執行的至少一個⑶I。
12.如權利要求11所述的系統，其中所述⑶I包括GPU，所述處理器是所述GPU。
13.—種包括用於執行如權利要求1-8的任一項所述的方法的指令的電腦程式。
14.一種其上記錄有根據權利要求13所述的電腦程式的計算機可讀存儲介質。
【文檔編號】G06F17/50GK103631981SQ201210585587
【公開日】2014年3月12日 申請日期:2012年11月2日 優先權日:2011年11月3日
【發明者】N·蒙塔那, M·蒙泰伊, R·諾森佐, A·利厄捷 申請人:達索系統公司