• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx

      基于文件內(nèi)存映射和多線程的三角網(wǎng)格模型快速拓撲重構(gòu)

      2022-05-12 09:25:18陳義明張應(yīng)中羅曉芳
      現(xiàn)代計算機 2022年5期
      關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu)線程頂點

      陳義明,張應(yīng)中,羅曉芳

      (大連理工大學機械工程學院,大連 116023)

      0 引言

      隨著三維數(shù)字掃描技術(shù)的發(fā)展,很多復雜的實體對象,例如復雜零部件、大型建筑物和地理場景等,通過數(shù)字掃描獲取其三維數(shù)字模型,通常會將掃描的點云模型轉(zhuǎn)換成三角網(wǎng)格模型,并且隨著模型的精度的提高,由此產(chǎn)生的三角網(wǎng)格規(guī)模非常龐大,三角面數(shù)量達到幾百萬或者上千萬,其結(jié)果是文件大小常常達到了幾百MB 甚至數(shù)GB。此外,目前三角網(wǎng)格模型采用STL 格式存儲,STL 三角網(wǎng)格文件僅僅是一個三角面集的排列,包含大量的重復頂點,缺乏三角面、邊頂點之間的拓撲關(guān)系,三角網(wǎng)格模型的進一步應(yīng)用需要進行拓撲關(guān)系的重構(gòu)。因此如此大數(shù)據(jù)量的三角網(wǎng)格文件,若采用傳統(tǒng)的文件處理技術(shù)進行三角網(wǎng)格數(shù)據(jù)的讀取及重構(gòu),勢必模型的處理效率較低,等待的時間過長。

      目前對于提高大型數(shù)據(jù)文件處理效率主要途徑是采用文件內(nèi)存映射技術(shù)加快讀取速度,該方法通過將文件的全部或部分內(nèi)容映射到進程的虛擬內(nèi)存之中,減少了磁盤的I/O 操作,使應(yīng)用程序可以通過內(nèi)存直接訪問位于磁盤上的文件數(shù)據(jù)。在大規(guī)模計算方面,主要采用并行計算處理技術(shù),對于現(xiàn)代多核計算機,多線程技術(shù)由于其高效的處理效率,已經(jīng)成為多任務(wù)處理中的主流方式。但在三角網(wǎng)格模型拓撲重構(gòu)方面,基于文件內(nèi)存映射和并行重構(gòu)研究較少。本文考慮到STL 網(wǎng)格文件中各個面的數(shù)據(jù)相互獨立的特點,多線程技術(shù)可以有效運用于文件處理操作中,融合內(nèi)存映射和多線程技術(shù),實現(xiàn)了對大規(guī)模三角網(wǎng)格模型快速重構(gòu),通過計算機多核多線程處理數(shù)據(jù)的優(yōu)勢,模型數(shù)據(jù)的重構(gòu)效率得到較大的提升。

      1 三角網(wǎng)格模型重構(gòu)總體方案

      1.1 STL三角網(wǎng)格模型重構(gòu)需求

      STL文件存儲了三維網(wǎng)格模型中三角形面的幾何信息,包括面的法向量及該面的三個頂點坐標。STL三角網(wǎng)格文件格式簡單,但僅僅是一個三角面集的排列,包含大量的重復頂點,并且缺乏三角面、邊頂點之間的拓撲關(guān)系。如果三角網(wǎng)格模型需要進一步應(yīng)用,例如網(wǎng)格幾何運算、網(wǎng)格修復和網(wǎng)格特征識別等,重構(gòu)其拓撲關(guān)系是必要的。

      STL三角網(wǎng)格模型重構(gòu)需求就是將無序的三角面集按照一個三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)重新進行組織,構(gòu)建三角面、邊和頂點之間的拓撲關(guān)系,為后續(xù)網(wǎng)格模型應(yīng)用提供支撐。

      1.2 基于面的三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)

      為了表示三角網(wǎng)格模型面、邊和頂點之間的拓撲關(guān)系,一個緊湊有效的拓撲數(shù)據(jù)結(jié)構(gòu)是必要的。三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)有很多,典型代表是半邊數(shù)據(jù)結(jié)構(gòu),但傳統(tǒng)半邊數(shù)據(jù)結(jié)構(gòu)占用較大的內(nèi)存,如果三角形頂點個數(shù)為,則需要180個字節(jié),本文采用文獻提出的基于面的數(shù)據(jù)結(jié)構(gòu),該數(shù)據(jù)結(jié)構(gòu)通過面和頂點表示一個三角形拓撲信息,僅占用52個字節(jié)(32 位編程),并且能夠表示流形和非流形三角網(wǎng)格信息,提供三角拓撲信息訪問機制,保證重構(gòu)后的網(wǎng)格數(shù)據(jù)能夠?qū)崿F(xiàn)高效的拓撲信息的查詢。該數(shù)據(jù)結(jié)構(gòu)如圖1所示。

      圖1 基于面的三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)

      主要內(nèi)容如下:

      頂點類中用3個float變量存儲三角面三個頂點坐標,使用一個面類的指針指向該點所在的三角形面,通過該指針,可以訪問該點引用的三角面信息。頂點類的編碼如下:

      面的結(jié)構(gòu)中包含存儲面的法向量,存儲該面的三個頂點指針,存儲該面與相鄰的其它3個面的指針,面類的編碼如下:

      1.3 文件內(nèi)存映射及多線程并行處理

      文件內(nèi)存映射技術(shù)是Windows 系統(tǒng)及Linux系統(tǒng)中廣泛使用的大文件讀寫技術(shù),該技術(shù)通過將文件的全部或部分內(nèi)容映射到進程的虛擬內(nèi)存之中,減少了數(shù)據(jù)的拷貝操作,提高了讀取速度。映射過程中沒有數(shù)據(jù)的實際拷貝操作,文件只是邏輯上存在于進程的虛擬內(nèi)存之中,系統(tǒng)通過缺頁中斷機制訪問位于磁盤上的文件數(shù)據(jù)。由于不再需要執(zhí)行文件的I/O 操作,并且讀取過程中系統(tǒng)不用再為文件申請并分配緩存,使得內(nèi)存映射技術(shù)能夠有效提高大文件的讀取速度。

      多線程并行處理技術(shù)是指從軟件或者硬件上實現(xiàn)多個線程并發(fā)執(zhí)行的技術(shù)。通常在一個Windows程序中,一個獨立運行的程序片段稱為“線程”(Thread),同時采用多個線程處理同一問題,稱為多線程處理。現(xiàn)代計算機通過軟硬件的配合能夠并行的運行多個線程,使計算機的整體性能得到較大提高。目前大部分計算機系統(tǒng)都有多核心處理器或同時多線程處理器,為開展多線程并行重構(gòu)三角網(wǎng)格模型提供條件。

      1.4 三角網(wǎng)格模型拓撲重構(gòu)總體方案設(shè)計

      基于上述分析,為了更高效地重構(gòu)三角網(wǎng)格模型,本文提出如圖2所示的STL三角網(wǎng)格模型多線程并行拓撲重構(gòu)總體方案。該方案主要包括如下3個步驟。

      圖2 STL三角網(wǎng)格拓撲并行重構(gòu)總體方案

      首先通過Windows 系統(tǒng)提供的文件內(nèi)存映射機制,將要重構(gòu)的三角網(wǎng)格文件映射到應(yīng)用進程的虛擬內(nèi)存中,映射過程中沒有數(shù)據(jù)的實際拷貝操作,文件只是邏輯上存在于進程的虛擬內(nèi)存之中,系統(tǒng)通過缺頁中斷機制訪問位于磁盤上的文件數(shù)據(jù)。

      對于大型網(wǎng)格模型文件采用多線程并行分段處理可以大大提高拓撲重構(gòu)效率。線程的數(shù)量需要綜合考慮CPU 核的數(shù)量及要處理文件的大小,通過實驗確定出一個性能較優(yōu)化的線程數(shù)量,再依據(jù)線程數(shù)量確定文件分割的段數(shù),使每一個線程對應(yīng)一個內(nèi)存映射文件的分段。

      將拓撲重構(gòu)任務(wù)分配給多個處理線程,每個線程讀取內(nèi)存映射文件的一個分段,共同并行地完成三角網(wǎng)格模型的拓撲重構(gòu)。

      2 STL三角網(wǎng)格文件映射分段及多線程設(shè)計

      2.1 STL三角網(wǎng)格文件映射分段

      本文采用Windows 提供用于大型文件內(nèi)存映射機制的API函數(shù)實現(xiàn)STL三角網(wǎng)格文件映射分段,具體實現(xiàn)過程如下。

      首先使用CreateFile 函數(shù)創(chuàng)建文件內(nèi)核對象,得到文件內(nèi)核對象的句柄Handle,然后將該句柄傳入CreateFileMapping 函數(shù)中創(chuàng)建文件映射內(nèi)核對象,該函數(shù)用于指定文件的尺寸及訪問文件的方式,并返回映射對象的句柄MapHandle。

      將上述文件映射對象句柄作為MapViewOf?File函數(shù)的參數(shù),該函數(shù)負責將文件的全部或部分內(nèi)容映射到進程的虛擬內(nèi)存中,若映射成功,返回一個LPVOID 類型的指針,這是一個無類型的指針,通常將該指針強制轉(zhuǎn)換成char*類型的指針,使其指向文件映射的起始位置。最后當不再需要使用該映像數(shù)據(jù)時,通過Un?mapViewOfFile 函數(shù)卸載映射,文件讀取結(jié)束時,使用CloseHandle函數(shù)關(guān)閉文件映射對象。

      由于STL 文件的數(shù)據(jù)規(guī)??赡芎艽?,按照上述總體方案設(shè)計,需要對三角網(wǎng)格文件進行分段映射處理。由于Windows 操作系統(tǒng)通常按頁存取數(shù)據(jù),并且系統(tǒng)中頁的分配粒度為64 kB,因此分段偏移地址必須取為64 kB的整數(shù)倍。但這樣的分段方式容易使一個完整的三角面數(shù)據(jù)被分在兩個不同的段中,導致該面的數(shù)據(jù)無法得到正常讀取。為解決此問題,本文提出如圖3所示的分段方法。

      圖3 STL文件分段內(nèi)存映射

      具體分段步驟如下:

      (1)確定分段數(shù)量。按照總體方案設(shè)計,分段數(shù)量取決于選擇的線程數(shù)量。具體線程數(shù)量選擇在下一節(jié)介紹。

      (2)計算跨界長度。二進制的STL 文件中每個三角形的幾何信息由固定的字節(jié)數(shù)表示。開頭的84個字節(jié)用于描述模型的文件信息,其中80個字節(jié)是文件頭,用于存儲零件名,剩下的4字節(jié)為一個整數(shù),用于存儲文件中包含的三角形數(shù)量,之后用固定的字節(jié)數(shù)表示三角形的幾何信息,每個三角形數(shù)據(jù)占用50字節(jié)。如果,為自然整數(shù),則跨界長度按如下公式計算:

      (3)向后偏移跨界長度映射下一個分段。因為上一個分段一次性將64000*字節(jié)映射到內(nèi)存,在讀取最后一個三角面時,與映射數(shù)據(jù)相差一個跨界長度,因此從第2個分段開始,映射開始地址在前一分段結(jié)束位置處向后偏移一個跨界長度。

      2.2 多線程設(shè)計

      隨著CPU 多核技術(shù)的出現(xiàn),多線程并行讀取文件和信息處理可以獲得較好的操作性能。但是線程的數(shù)量也不是越多越好,因為線程間的切換和調(diào)度會消耗CPU 資源和時間,如果設(shè)置線程數(shù)量過大,會影響處理性能,一個合適的線程數(shù)量設(shè)置是有必要的。在本文提出的方法中,線程數(shù)量設(shè)置主要考慮如下因素。

      如果文件長度小于8 M,即采用單線程,否則采用多線程,線程數(shù)量由以下因素確定。

      線程的執(zhí)行是由CPU 進行調(diào)度的,一個CPU 在同一時刻只會執(zhí)行一個線程,如果多個線程,操作系統(tǒng)一般采用時間片輪轉(zhuǎn)的方式,任務(wù)的切換會導致額外的開銷。本文涉及的重構(gòu)計算主要依賴于CPU,因此選擇線程數(shù)量=CPU核數(shù)+1。

      如果工作任務(wù)是高強度計算,則要適當降低線程數(shù)量,否則如果工作任務(wù)是事務(wù)性的工作,有等待時間,可以適當提高線程數(shù)量。

      3 基于多線程的三角網(wǎng)格模型并行拓撲重構(gòu)

      3.1 三角網(wǎng)格模型拓撲重構(gòu)算法分析

      按照上述重構(gòu)總體方案設(shè)計,拓撲重構(gòu)模型是采用文獻[6]給出的基于面的拓撲數(shù)據(jù)結(jié)構(gòu)。文獻[6]還給出了面向STL 文件的拓撲重構(gòu)算法,如圖4所示。從給出的算法看,拓撲重構(gòu)過程主要分為如下3個操作。

      圖4 基于面的拓撲重構(gòu)算法[6]

      (1)創(chuàng)建三角面對象。每讀取一個三角面數(shù)據(jù),就創(chuàng)建一個三角面對象,并加入到重構(gòu)的三角網(wǎng)格模型中。

      (2)查找或者創(chuàng)建新的頂點。由于STL 網(wǎng)格文件包含大量的重復頂點,因此創(chuàng)建一個新的頂點對象前要查詢在該頂點位置是否已經(jīng)創(chuàng)建頂點,如果有就直接引用該頂點,否則創(chuàng)建新頂點。一個大型的三角網(wǎng)格模型包含上百萬個頂點,查找的效率非常重要,采用文獻[6]給出的Hash表查找。

      (3)查找相鄰三角面。頂點對象完成后,通過頂點對象對面的引用,查找三角面的三個相鄰面,一次操作可能完成不了,在所有面完成后還需要執(zhí)行一遍這樣的操作。需要有一個共有的三角面表容器。

      3.2 三角網(wǎng)格模型拓撲并行重構(gòu)策略

      根據(jù)上述三角網(wǎng)格模型拓撲重構(gòu)算法分析,可以看出重構(gòu)過程主要由一系列的重復操作組成,完全可以將重復操作分配給多個線程完成。為此提出如下并行重構(gòu)策略。

      (1)設(shè)置共享數(shù)據(jù)區(qū)。每個線程僅需要對部分三角面并行執(zhí)行相同三角面重構(gòu)操作,構(gòu)造生成的頂點和三角面對象存儲在共同的Hash 點表和三角面表中,將共同的Hash 點表和三角面表設(shè)置為共享區(qū)域。

      (2)設(shè)置共享數(shù)據(jù)區(qū)域加鎖保護機制。在多線程重構(gòu)過程中,為了保證處理數(shù)據(jù)的安全,可以通過對共享區(qū)域加鎖,保證同一時刻只有一個線程對共享數(shù)據(jù)區(qū)域進行修改操作。為此設(shè)置一個公有的可操作標志,當一個線程在進行頂點或者面創(chuàng)建操作時,可操作標志為0,操作完成后置為1。只有當可操作標志為1 時,線程的所有操作才可進行。這種加鎖解鎖機制有效實現(xiàn)了線程間的互斥訪問,保證了程序運行的穩(wěn)定性。

      3.3 三角網(wǎng)格模型拓撲并行重構(gòu)實現(xiàn)

      基于上述STL 文件分段操作和并行重構(gòu)策略,本文基于文獻[6]給出的三角網(wǎng)格拓撲重構(gòu)算法基礎(chǔ)上,實現(xiàn)了網(wǎng)格模型拓撲并行重構(gòu),主要操作步驟如下。

      (1)創(chuàng)建并行重構(gòu)線程。根據(jù)設(shè)置的線程數(shù)量,創(chuàng)建并行重構(gòu)線程。創(chuàng)建之前文件內(nèi)存映射分段完畢,每一個線程設(shè)置讀取相應(yīng)的文件分段的偏移長度,偏移長度按照3.1給出的方法計算。

      (2)啟動并行重構(gòu)算法各個線程。每個線程基本上并行執(zhí)行相同的操作,其中線程執(zhí)行過程如圖5所示。

      圖5 三角網(wǎng)格并行拓撲重構(gòu)算法流程

      (3)讀取文件分段中的三角面片。每讀取一個三角面數(shù)據(jù),開始構(gòu)建頂點對象和面對象,在操作前檢查公有標志:opFlag,只有當opFlag等于1時才執(zhí)行操作,如果要執(zhí)行頂點對象或者面對象的插入,首先將opFlag 置為0,待插入操作完成后,將opFlag 再置為1。因此當一個線程在執(zhí)行插入寫操作時,其它所有線程的操作被等待,直到opFlag變回到1。

      (4)一個三角面的三個頂點都處理完成后,將讀取下一個三角面,如果三角面讀取處理完成,子線程結(jié)束,否則轉(zhuǎn)上面第(3)步。

      (5)主線程等待所有子線程讀取結(jié)束,文件處理完成,主線程結(jié)束。

      由于文件已經(jīng)被映射到內(nèi)存中,讀取文件幾乎和內(nèi)存操作速度相當,沒必要單獨為未重構(gòu)的模型分配內(nèi)存,節(jié)省了內(nèi)存空間。

      4 重構(gòu)實驗

      本文在Windows 10 操作系統(tǒng)上采用Visual C++和OpenGL 編程進行快速重構(gòu)實驗,實驗計算機配置i5 2.5 GHz CPU、4 G內(nèi)存。依次選用箱體模型、端蓋模型及馬的模型的STL文件為讀取對象,模型重構(gòu)后OpenGL顯示如圖6所示。

      圖6 STL三維網(wǎng)格文件模型顯示

      對以上模型采用普通單線程方法、單線程內(nèi)存映射方法以及多線程內(nèi)存映射方法依次讀取文件并重構(gòu)網(wǎng)格數(shù)據(jù)。由于系統(tǒng)CPU 為雙核處理器,故多線程內(nèi)存映射方法中的線程數(shù)確定為三個,經(jīng)實驗驗證,三個線程的讀取效率最高。從STL 網(wǎng)格文件開始讀取到網(wǎng)格數(shù)據(jù)拓撲關(guān)系的重構(gòu),記錄系統(tǒng)總的運行時間,表1為三種方法對不同數(shù)據(jù)量的三角網(wǎng)格文件的讀取及重構(gòu)時間:

      表1 三種方法重構(gòu)網(wǎng)格數(shù)據(jù)的時間對比

      通過時間對比可以看到,內(nèi)存映射技術(shù)能有效提高文件讀取速度,平均的讀取效率比普通單線程提高15%以上。在內(nèi)存映射的基礎(chǔ)上使用多線程技術(shù),由于利用了CPU 并行處理文件的優(yōu)勢,使得讀取和重構(gòu)效率比單線程的內(nèi)存映射提高20%以上。綜合分析,多線程內(nèi)存映射在讀取大規(guī)模的三角網(wǎng)格文件時,比起傳統(tǒng)的單線程方法效率提升顯著。

      5 結(jié)語

      三角網(wǎng)格文件的快速拓撲重構(gòu)對后續(xù)的網(wǎng)格應(yīng)用至關(guān)重要。針對大數(shù)據(jù)量的網(wǎng)格文件占用空間大,重構(gòu)速度慢的問題,本文提出了一種基于內(nèi)存映射和多線程的三角網(wǎng)格模型快速重構(gòu)方法,通過對大型STL 三角網(wǎng)格文件內(nèi)存分段映射,采用多線程并行對文件分段內(nèi)容分別進行網(wǎng)格數(shù)據(jù)重構(gòu),重構(gòu)出基于面的三角網(wǎng)格模型拓撲數(shù)據(jù)結(jié)構(gòu),與傳統(tǒng)的重構(gòu)方法相比,重構(gòu)效率得到了明顯提升,實驗表明了該方法的可行性。

      猜你喜歡
      數(shù)據(jù)結(jié)構(gòu)線程頂點
      過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應(yīng)用(下)
      關(guān)于頂點染色的一個猜想
      山東科學(2018年6期)2018-12-20 11:08:58
      淺談linux多線程協(xié)作
      “翻轉(zhuǎn)課堂”教學模式的探討——以《數(shù)據(jù)結(jié)構(gòu)》課程教學為例
      高職高專數(shù)據(jù)結(jié)構(gòu)教學改革探討
      中國市場(2016年45期)2016-05-17 05:15:48
      TRIZ理論在“數(shù)據(jù)結(jié)構(gòu)”多媒體教學中的應(yīng)用
      《數(shù)據(jù)結(jié)構(gòu)》教學方法創(chuàng)新探討
      河南科技(2014年5期)2014-02-27 14:08:57
      Linux線程實現(xiàn)技術(shù)研究
      么移動中間件線程池并發(fā)機制優(yōu)化改進
      數(shù)學問答
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      404 Not Found

      404 Not Found


      nginx
      台南市| 苗栗市| 北辰区| 禹州市| 富阳市| 凤凰县| 宝山区| 张家港市| 瑞昌市| 衡阳市| 陈巴尔虎旗| 平原县| 大方县| 双流县| 福贡县| 阳东县| 湘西| 保山市| 保靖县| 汉阴县| 观塘区| 河北区| 乌恰县| 张家界市| 都昌县| 固镇县| 朝阳县| 深圳市| 漠河县| 荥阳市| 阆中市| 丹棱县| 中西区| 九江县| 余姚市| 巩留县| 出国| 屏东市| 宣恩县| 乡宁县| 台湾省|