基于BNF的3DS文件格式規范化描述①

陳 蕾,趙正旭

(石家莊鐵道大學 信息科學與技術學院,石家莊 050043)

基于BNF的3DS文件格式規范化描述①

陳 蕾,趙正旭

(石家莊鐵道大學 信息科學與技術學院,石家莊 050043)

3DStudio(3DS)是3dsMax用來保存模型信息的一種文件結構,是業界的通用標準格式之一.為了使不同星系之間的模型可以被自由調用,解決可視化系統中模型格式不兼容的問題,減小3DS文件的存儲空間,提出使用巴克斯范式(BNF)規范化描述3DS文件.描述了BNF的特點和對3DS文件結構進行表述和分析的使用方法,并以土衛三模型的3DS文件為例,使用BNF對其進行形式化定義,從而形成了統一的規范化管理格式,以利于搜索引擎的檢索和應用.

3DS;BNF;形式化語言;規范化

隨著虛擬現實技術的發展,基于三維模型的深空探測實時三維可視化技術需求越來越大,對三維模型的需求也隨之增大.目前,常用的三維建模軟件包括AutoCAD[1]、3DS Max[2]、Autodesk Maya[3]、Zbrush[4]等,不同的三維建模軟件適用于不同的應用領域,生成的模型格式也各種各樣.在深空探測實時三維可視化系統中,需要存儲成千上萬的三維模型,由于模型的數據格式和文件結構不同,可能會導致各個星系互不兼容,使得這些三維模型不能在同一實時系統中同時被調用,導致在深空探測實時可視化系統中不能快速精確地調用目標模型.如果對系統中三維模型的文件格式和描述方式制定統一的規范,對三維模型文件進行標準化和規范化處理,就會大大提高系統的效率.

文件標準化和規范化是實現三維模型資源共享與重用的前提條件,在資源建設中占有極其重要的地位.規范化管理三維模型的途徑之一就是將模型的文件結構“標準化”.首先統一三維模型的文件格式,本文選擇3DS[5]格式的三維模型,它是一種比較通用的保存三維模型信息的文件格式.其次需要對3DS文件進行規范化描述,制定一個統一的描述規則.目前對于3DS的文件格式和塊結構都是以樹狀圖或自然語言描述,必須用自然語言加以說明才能將3DS的文件結構描述清楚.這些圖表和自然語言計算機識別不了,現有的文本描述方式和自然語言解釋方式存在二義性等弱點,因此必須尋找一種規范化的形式將其描述.

描述文件數據結構的常用語言有XML(eXtensible Markup Language)[6]、 JSON(JavaScript Object Notation)[7]、Z語言[8,10]、BNF[11].XML具有文檔結構清晰、容易閱讀等優點,但其文件尺寸一般都比較大,因此在現有的網絡條件下傳輸文件效率較低[12].JSON采用完全獨立于語言的文本格式,易于人閱讀和編寫,同時也易于機器解析和生成.Z語言是一種用“數學文字”或“數學符號”來描述計算機系統的規范化語言,是軟件工程中編碼之前的規格說明語言.BNF是一種上下文無關文法的符號集,由于其簡潔、明了和科學而被廣泛接受[13,14].

經過比較,BNF具有簡單易學、開放、易于擴展、分析效率高等優點,相對于其它形式化語法,在描述文件格式方面具有更好的適用性.因此,本文使用BNF描述3DS文件結構,統一描述文件格式,以一種計算機可識別的文法將其規范化描述,將3DS文件變為“標準”格式,建立一種專有的數據格式,使其更加通用.

1 3 DS文件解析

3DS文件是樹狀結構的二進制文件,基本單位是塊,每個塊都有各自的用途.所有塊都是以樹形結構組織的,以一個主塊開始,以嵌套的形式構成.

文件的主塊ID是Ox4D4D,這可以判斷一個文件是否是3DS文件.3DS文件的每個塊都是一個層次結構,每一部分都有各自特有的ID號,圖1表示了3DS文件中塊的存在結構及位置(文件太長,只畫出文件前幾個塊,其他不再贅述).

圖1 3DS文件結構和塊

這些“塊”描述了3DS文件的數據信息,由塊頭和數據兩部分組成.塊頭包括ID和長度兩項,共占6位,長度指得是整個塊的長度,而不只是數據的長度.每一個“塊”都是以2個字節的ID開始,緊接著是4個字節的塊長度信息,緊接著是塊數據信息[15,16],如圖2所示.

圖2 3DS文件塊的嵌套

從圖1和圖2可以看出,3DS文件是一層套一層的 樹狀結構,而且這個樹狀結構是一個無比龐大的家族,每一個塊都包含著自己的子塊,子塊接著包含子塊,如此下去.

2 3 DS文件的BNF文法表示

2.1 BNF范式

BNF就是使用一種類似的形式來描述一個問題,讓所有參與者都能明白他們對哪一方面能夠達成一致意見.也就是對于某個問題制定一個統一的標準,為某個符號賦予一個特定的意義,在某個領域內它就只能是這個意思,別人在了解這個標準和所制定的規則之后,就能理解使用這種符號集的表達方式和內容.

BNF被廣泛應用于編程語句,也可以用來規范自然語言[17,18].BNF非常精確,在語法上沒有歧義;形式簡單易學,便于使用者和計算機處理;開放、易于擴展、表達能力較強,能充分表達出描述者意圖.而用普通語言描述的語法不僅冗長,而且會造成理解上的歧義;用BNF表示的語法是數學產物,可以被計算機理解,因此選擇BNF描述文件語法結構.

2.2 塊結構描述

文章上一節中,使用自然語言和圖表的形式對3DS的文件結構進行了描述,這種方式雖然通俗易懂,但是由于結構比較繁雜,沒有形成一個統一的形式.如果使用BNF制定一種通用的文法,結果會更加一目了然,計算機也更容易識別.對圖1和圖2中的3DS文件結構制定BNF文法,則表示為:

(1)首先對一些專業術語作以下定義:

塊 ::=chunk

子塊 ::=sub-chunk

塊頭 ::=head

數據 ::=data

長度 ::=size

(2)句子文法如下:

由于3DS文件的塊ID是由十六進制數表示的,2個字節,一共四位;size表示的是整個塊的長度,也是用十六進制數表示的,所以其BNF表示文法如下:

BNF范式中有不定循環的規則[19],格式為:*Rule,即在元素前加操作符*表示重復,完整形式為: *element,例如:3*3表示該元素只允許3次,所以塊ID和size可以簡化為:

ID::=“Ox”,4*4(ID是兩個字節,4位表示,即重復4次)

size::=“Ox”,8*8(size是四個字節, 8位表示,即重復8次)

每一個塊的ID都不一樣,都有自己的專屬表示,比如主塊ID是Ox4D4D,編輯塊是Ox3D3D,具體塊的ID只需要根據實際情況靈活替換即可.

通過上述幾個文法表示,采用遞歸法可以簡潔地表示出3DS文件中塊與塊的包含關系和樹狀結構.這種使用字母和符號表達的文法沒有二義性,計算機更容易識別,更通用.

2.3 文件描述

在描述3DS文件的時候,如果單純從實體外觀上描述,可能會因為一些語言共識或者描述方式的不同,造成理解上的歧義.另一方面,每個3d模型都有自己的特點,都描述出來就會出現很多語句,這些語句可能只是換了一個形容詞,或者只是換了一個名詞而已,這樣就會做許多重復的工作.如果,現在用一種規范定義出3DS文件的描述形式,那就會省很多工作量,只需要套用形式就行.

通過上述3DS文件的描述,我們可以了解到3DS文件數據格式是由“塊”組成的,它是一個樹形層級結構,主塊包含子塊的關系.

首先,一個 3DS文件的開始是主塊MAIN3DS,其ID是Ox4D4D,它是基本信息塊,所以在一個3DS文件中,主塊是必選項,它總是以主塊Ox4D4D開始的.其次是一級子塊,版本信息塊VERSION,ID是Ox0002,編輯信息塊EDIT3DS,ID是Ox3D3D,關鍵幀信息塊KEY3DS,ID是OxB000.

最基本的語句規范描述如下:

因為一個3DS文件總是以主塊開始的,所以是必選項,用尖括號括住以表示必選.緊接著是版本信息塊、編輯信息塊和關鍵幀塊.關鍵幀信息塊是關于幀動畫信息的數據,所以這一部分內容不是必須存在的,所以用[]括起來表述可選項內容.

編輯塊的父塊是 Ox4D4D,其主要子塊是EDIT_MATERIAL 材 質 塊 ,ID 是 OxAFFF; EDIT_OBJECT對象塊,ID是Ox4000.

EDIT_UNKNWN、OBJ_UNKNWN等指的是一些未知信息塊,它可以有多個,也可以沒有,所以用花括號括起來,表示重復0到無數次.

主編輯塊的子塊雖然是按照一定的次序存放,但其中有些塊并不是一定存在的,比如:如果你沒有定義材質,使用缺省材質,這里將不存在材質塊.

2.4 文件數據結構描述

2.4.1 宏定義

在一個3DS文件中,使用宏定義來定義文件中的塊:

#define MAIN3DS 0x4D4D //定義主塊

使用BNF統一描述為:

Macro definition::=“#define”, //具體塊的Name根據實際情況替換即可

2.4.2 定義數據結構

在3DS文件中,保存塊信息的結構如下:

3 實例分析

3.1 土衛三.3DS文件數據格式解析

許多文獻已經介紹過,3DS文件的二進制位存儲順序是Intel式的[20],低字節在前,高字節在后,所以在讀取3DS數據文件的時候必須考慮這個規則.下面通過一個具體實例對3DS文件的數據格式進行詳細解析:首先,通過3DSMax2010創建土衛三的三維模型,以.3DS的格式導出并保存,如圖3所示.

圖3 3dsMax打開土衛三.3DS的三維模型

通過工具C32asm讀取圖3中.3DS的土衛三文件,得到其十六進制數據列表,如圖4所示.圖中所顯示的數據以兩個字節的塊ID開始,之后是四個字節的塊的長度信息.從數據中提取到標志性的塊ID,比如Ox4D4D(主塊)、Ox3D3D(編輯塊)及OxAFFF(材質塊)等,它們是兩個字節的塊ID,后面緊跟4個字節該塊的長度信息.

圖4 3DS格式的土衛三十六進制數據

從土衛三3DS文件中截取一組數據如下:

4D 4D CA C9 09 00 02 00 0A 00 00 00 03 00 00 00 3D 3D DE C8 09 00......

(1)首先,4D4D是該文件的主塊ID,占兩個字節.

(2)之后的4個字節保存的是主塊的長度信息,也就是整個文件的長度.由于3DS二進制數據是按低位在前、高位在后存儲的,所以主塊的長度為Ox0009C9CA.

(3)接著是該 3DS文件的第一個子塊的ID, Ox0002.子塊的長度是Ox0000000A. (4)之后的塊ID未知,歸為未知信息,可以跳過(5)Ox3D3D是主編輯塊的ID.該塊的長度為Ox0009C8DE.

(6)之后的字節的讀取規則按如上步驟.

3.2 土衛三3DS文件的BNF描述

根據以上的研究內容,運用BNF描述土衛三.3DS文件結構,具體內容如下:

根據式①和圖4中土衛三3DS文件的十六進制序列,其BNF描述規范如下:

根據式②和③擴展如下:

(1)基本塊的表示:

(2)版本塊的表示:

(3)編輯塊的表示:

(4)材質塊的表示:

(5)綜合以上所有式子,總式表示為:

由于3DS文件是嵌套結構,因此以上是通過遞歸的方式表示3DS的BNF描述方法,先用非終結符一層一層表示,直到結構最中心再用終結符一層一層替換.由于土衛三.3DS文件塊結構特別龐大,其中有許多未知塊和不重要的塊,文章不再贅述,只選取了其中比較重要的塊.上述所用數據是從土衛三.3DS文件的十六進制數據序列中摘取,數據屬實.

從上述式子可以看出,這種描述方法與圖4中文件的十六進制數據相比,更清晰、更簡潔.省去了沒有用的信息之后,所有表述的都是模型文件必要的特征信息,減小了文件存儲空間.

4 結論與展望

如何將知識提煉成規則,需要用到統一的文法.文法最吸引人的特性,是它們自然地描述了所定義語言句子的分層語法結構.基于BNF的3DS文件文法表示,可以更科學地描述文件的結構,更加簡潔、通用.

在深空探測三維可視化系統中,將模型文件格式統一,保證在各個星系之間模型可以被自由調用,解決了不同星系系統中模型格式不兼容的問題.使用巴克斯范式描述3DS文件,可以縮小文件長度,同時在描述過程中,把文件中不重要的部分省略,描述文件的必要信息,在不影響模型正常顯示的情況下,將文件描述到最簡,這不僅有助于計算機快速讀取,也方便使用者識別.

文章為更好地管理和使用3DS文件提出一種新思路,希望能對改進3DS文件的存儲空間和傳送速率起到一定的借鑒作用.接下來,需要對深空探測系統中大量天體模型的具體描述,在應用中完善該描述方法,能夠進一步促進航天事業的發展.另外,計劃在3DS文件分類過程中使用BNF描述代碼,制定統一的描述規范,如何利用BNF對3DS文件制定分類規范也是下一步要進行的研究工作.

1百度百科.AutoCAD.http://baike.baidu.com/view/25199.htm. [2016-07-27].

2百度百科.3dsmax.http://baike.baidu.com/view/11137.htm# reference-[1]-11137-wrap.[2016-08-01].

3 百 度 百 科 .Autodesk Maya.http://baike.baidu.com/view/ 6463073.htm?fromtitle=maya&fromid=38497&type=syn. [2016-07-15].

4百度百科.ZBrush.http://baike.baidu.com/view/165599.htm. [2016-08-05].

5杜琳,蔣輝.VC++中利用DirectX實現3DS文件的讀取和控制.計算機時代,2010,01:41–43.

6搜狗百科.XML.http://baike.sogou.com/v34402.htm?fromTitle= XML.[2016-07-26].

7 百度百 科 .JSON.http://baike.baidu.com/view/136475.htm. [2016-07-27].

8趙正旭,溫晉杰,趙衛華.Z規范及其使用方法.北京:科學出版社,2015.

9 Wen JJ,Guo Y,Zhao ZX.Representation of raspberry PI practice in Z notation.British Journal of Applied Science& Technology,2016,(4):2231–0843.

10趙正旭,溫晉杰.Z規格說明自動生成器.計算機系統應用,2016,25(4):148–155.

11百度百科.BNF.http://baike.baidu.com/view/1137652.htm. [2016-07-24].

12程小東,張宇.X3D文件轉換為JSON的方法.池州學院學報,2009,23(3):29–30.

13 Zhao W,Xia CH,Luo Y,Liu XC,Wu WK.An approach for description of computer network defense scheme and its simulation verification.Journal of Computers,2014,(2): 388–398.

14羅晨,鮑廣宇,劉曉明,袁黎苗.基于改進BNF的作戰管理語言語法形式化方法.計算機科學,2012,39(4):189–192.

15劉芳,劉賢梅.3DS文件讀取、繪制與控制方法的研究與應用.計算機工程與設計,2009,30(19):4575–4578.

16百度文庫.Autodesk公司官方 3ds文件格式介紹. http://download.csdn.net/detail/whucv/4851225.[2015-11-15].

17 Xiong W,Jin YH,Liu ZY.Recognizing Chinese number and quantifier prefix to enhance statistical parser in machine translation.Journal of Computers,2014,(4):867–874.

18 Laros JFJ,Blavier A,den Dunnen JT,Taschner PEM.A formalized description of the standard human variant nomenclaturein Extended Backus-NaurForm.BMC Bioinformatics,2011,(12):S5.

19綠色背影.巴科斯范式.http://xl-feng1314.blog.163.com/ blog/static/4450715220080196551349/.[2016-05-15].

20劉爽,張恒博.三維建模軟件3dsMax數據文件3ds的解析.大連民族學院學報,2012,14(3):260–264.

3DS File Format Specification Based on BNF

CHEN Lei,ZHAO Zheng-Xu

(School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China)

3DStudio（3DS）is a file structure of 3dsMax used to store model information,which is one of the industry’s standard format in 3D software.In order to ensure the models of different system can be called freely,to solve the problem that the different model format is not compatible in visual system,and to reduce the storage space of 3DS file, this paper proposes to use the Backus-Naur Form(BNF)specification to describe the 3DS file.This paper describes the characteristics of the BNF and the method of describing and analyzing the 3DS file structure,and takes the 3DS file of Tethys model as an example,using BNF to formally definite it,thus forms a unified format of standardization management,which facilitates retrieval and application of search engine.

3DS;BNF;Formal language;specification

河北省高層次人才科學研究項目(GCC2014010)

2016-08-10;收到修改稿時間:2016-09-13

10.15888/j.cnki.csa.005721