[發(fā)明專利]一種無(wú)冗余計(jì)算的高效Marching Cubes等值面提取方法與系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201910290205.0
• 申請(qǐng)日: 2019-04-11
• 公開(kāi)（公告）號(hào): CN110021059B
• 公開(kāi)（公告）日: 2023-02-07
• 發(fā)明（設(shè)計(jì)）人: 王文珂;吳誠(chéng)竹;張瀟;朱小謙;鄒丹;吳亞剛;陸麗娜;夏飛
• 申請(qǐng)（專利權(quán)）人: 中國(guó)人民解放軍國(guó)防科技大學(xué)
• 主分類號(hào): G06T15/08
• 分類號(hào): G06T15/08;G06T17/10
• 代理公司: 長(zhǎng)沙國(guó)科天河知識(shí)產(chǎn)權(quán)代理有限公司 43225
• 代理人: 邱軼

1.一種無(wú)冗余計(jì)算的高效Marching Cubes等值面提取方法，其特征在于，利于額外的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)立方體中能夠重復(fù)利用的邊上的插入頂點(diǎn)的坐標(biāo)，以及用一個(gè)數(shù)組存儲(chǔ)立方體中八個(gè)頂點(diǎn)的最大值、最小值，在比較時(shí)先分別比較最大值、最小值與等值面的值的關(guān)系；

具體包括以下步驟：

第一步：申請(qǐng)包含兩個(gè)int類型的變量的結(jié)構(gòu)體，分別存儲(chǔ)單個(gè)立方體中的最大值和最小值；

第二步：以先X方向再Y方向，最后Z方向遍歷所有的立方體以減少冗余計(jì)算，根據(jù)以上遍歷方式將所有的立方體分成八種情形：①：x＝y(tǒng)＝0，z＝0、②：x≥1，y＝0，z＝0、③：x＝0，y≥1，z＝0、④：x≥1，y≥1，z＝0、⑤：x＝y(tǒng)＝0，z≥1、⑥：x≥1，y＝0，z≥1、⑦：x＝0，y≥1，z≥1、⑧：x≥1，y≥1，z≥1；

申請(qǐng)數(shù)組來(lái)存儲(chǔ)能夠減少冗余計(jì)算的邊上的插入點(diǎn)，對(duì)于以上八種情形有以下的存儲(chǔ)結(jié)構(gòu)：

情形一：用三個(gè)數(shù)據(jù)結(jié)構(gòu)分別存儲(chǔ)X(4,5,6,7),Y(0,4,8,9),Z(3,7,8,11)方向上的四個(gè)邊上的插入點(diǎn)；

情形二：用情形一X方向上的數(shù)據(jù)結(jié)構(gòu)繼續(xù)存4,5,6,7邊上的插入點(diǎn)，再用一個(gè)大小為X方向立方體個(gè)數(shù)減一的一維數(shù)組存儲(chǔ)該方向上每個(gè)立方體0,4,8,9邊上的插入點(diǎn)；

情形三：用情形一Y方向上的數(shù)據(jù)結(jié)構(gòu)繼續(xù)存0,4,8,9邊上的插入點(diǎn)，再用一個(gè)大小為Y方向立方體個(gè)數(shù)減一的一維數(shù)組存儲(chǔ)該方向上每個(gè)立方體4,5,7邊上的插入點(diǎn)；

情形四：用情形二中的一維數(shù)組存儲(chǔ)0,4,8,9邊上的插入點(diǎn)，用情形三中的一維數(shù)組存儲(chǔ)4,5,7邊上的插入點(diǎn)，再用一個(gè)大小為X方向立方體個(gè)數(shù)減一乘以Y方向立方體個(gè)數(shù)減一大小的二維數(shù)組存儲(chǔ)7,8邊上的插入點(diǎn)；

情形五：用情形一Z方向上的數(shù)據(jù)結(jié)構(gòu)存3,7,8,11邊上的插入點(diǎn)；

情形六：在情形二存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上再用一個(gè)大小為X方向立方體數(shù)減一的一維數(shù)組存儲(chǔ)7,8,11邊上的插入點(diǎn)；

情形七：在情形三存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上再用一個(gè)大小為Y方向立方體數(shù)減一的一維數(shù)組存儲(chǔ)3,7,8邊上的插入點(diǎn)；

情形八：存儲(chǔ)結(jié)構(gòu)與情形四一樣；

第三步：遍歷所有立方體，將每個(gè)立方體的最大值、最小值存儲(chǔ)在固定的數(shù)據(jù)結(jié)構(gòu)中；

第四步：在計(jì)算與等值面相交的點(diǎn)之前利用第二步存儲(chǔ)的最大值、最小值判斷該立方體中是否存在與等值面的交點(diǎn)，如果存在交點(diǎn)則執(zhí)行第五步，否則繼續(xù)對(duì)下一個(gè)立方體從第三步開(kāi)始進(jìn)行判斷；

第五步:情形一、二、三、四依次處理完各個(gè)數(shù)據(jù)，情形五、六、七、八放在一個(gè)大循環(huán)中處理；

第五步中，對(duì)每種情形中的每個(gè)立方體的處理步驟為：

Ⅰ、判斷各個(gè)情形的數(shù)據(jù)中每個(gè)立方體頂點(diǎn)的值與閾值的大小關(guān)系進(jìn)而得到一個(gè)索引值，之后根據(jù)索引值查找情形二、情形五、情形六的一維數(shù)組，獲取立方體12條邊中具有交點(diǎn)的邊；

Ⅱ、獲取立方體12條邊中具有交點(diǎn)的邊后：

對(duì)于情形一中的立方體，每條邊都要計(jì)算；

對(duì)于情形二中的立方體，第0,1,2,3,條邊上的插入點(diǎn)的值可以從前面的提到的存儲(chǔ)4,5,6,7邊結(jié)構(gòu)中取出，不用計(jì)算，其它邊照常計(jì)算；

對(duì)于情形三中的立方體，第2,6,10,11邊上的插入點(diǎn)的值從存儲(chǔ)0,4,8,9邊結(jié)構(gòu)中取出，不用計(jì)算，其它邊照常計(jì)算；

對(duì)于情形四中的立方體，第2,6,10,11邊上的插入點(diǎn)的值從存儲(chǔ)0,4,8,9邊結(jié)構(gòu)中取出，第0,1,3邊上的值從存儲(chǔ)4,5,7邊結(jié)構(gòu)中取出，不用計(jì)算，其它邊照常計(jì)算；

對(duì)于情形五中的立方體，第1,5,9,10邊上的插入點(diǎn)的值從存儲(chǔ)3,7,8,11邊結(jié)構(gòu)中取出；

對(duì)于情形六中的立方體，第0,1,2,3邊上的插入點(diǎn)從存儲(chǔ)4,5,6,7邊結(jié)構(gòu)中取出，第5,9,10邊上的插入點(diǎn)從存儲(chǔ)7,8,11邊結(jié)構(gòu)中取出，不用計(jì)算，其它邊照常計(jì)算；

對(duì)于情形七中的立方體，第2,6,10,11邊上的插入點(diǎn)的值從存儲(chǔ)0,4,8,9邊結(jié)構(gòu)中取出，第1,5,9邊上的插入點(diǎn)從存儲(chǔ)3,7,8邊結(jié)構(gòu)中取出，不用計(jì)算，其它邊照常計(jì)算；

對(duì)于情形八中的立方體，第2,6,10,11邊上的插入點(diǎn)的值從存儲(chǔ)0,4,8,9邊結(jié)構(gòu)中取出，第0,1,3邊上的值從存儲(chǔ)4,5,7邊結(jié)構(gòu)中取出，第5,9邊上的插入點(diǎn)的值從存儲(chǔ)7,8邊結(jié)構(gòu)中取出，不用計(jì)算，其它邊照常計(jì)算；

Ⅲ、處理完立方體的每條邊后，按照第一步提到的把每種情形中后面能夠利用的邊上的插入點(diǎn)的值再存儲(chǔ)到對(duì)應(yīng)結(jié)構(gòu)中；

Ⅳ、查找情形二、情形五、情形六的二維數(shù)組，提取每種情形的等值面，繪制成圖像。

2.一種無(wú)冗余計(jì)算的高效Marching Cubes等值面提取系統(tǒng)，其特征在于，包括存儲(chǔ)器和處理器，所述存儲(chǔ)器存儲(chǔ)有計(jì)算機(jī)程序，所述處理器執(zhí)行所述計(jì)算機(jī)程序時(shí)實(shí)現(xiàn)權(quán)利要求1所述方法的步驟。