ѧ
JOURNAL OF SOFTWARE
1999 10 12  Vol.10 No.12 1999



ȷģ͵Ĳ
ơ顡־
ժҪΪ˼ǿϵͳıʵֶ߿ģ͡ģͺʵģ͵ͳһʾͲĲ÷ȷģΪζʾݽṹӦĲʵ㷨ڱ֤Чʺ;ȷԵͬʱȷ³㷨Ŀ.Ϊһϵͳļκģ㷨ѾڻNTƽ̨ϵͳGS-CAD98ʵ.
ؼʡģͣüƬ³.
ͼšTP391
Boolean Operation of Non-Regular Precise Geometric Models
TANG Min DONG Jin-xiang LI Hai-long HE Zhi-jun
(State Key Laboratory of CAD & CG Zhejiang University Hangzhou 310027)
(Artificial Intelligence Institute Zhejiang University Hangzhou 310027)
Abstract To enhance the geometric ability of current modeling system, the non-regular precise geometric model is used as the unified data structure to represent and manipulate the wire-frame models, the surface models and the solid models in the algorithms. The authors present the data structure and Boolean operation in this paper. For Boolean operation, accuracy, efficiency and robustness are the main consideration. As the geometric kernel of a feature based modeling system, the algorithm has been implemented in a feature based modeling system named GS-CAD98 on NT platform.
Key wordsNon-Regular geometric model, Boolean operation, trimmed patches, robustness.
ͼķٷչǶԼϵͳĵҪҲһ.ֵֻ֧һʵģ͵ͺ¼ܵս14ݣ
(1) ȱģͣ޷ȷرͲض״ĵƬ
(2) ԲͬӦã״ӦÿԱΪά߿ȣ
(3) ״Ӧ߿ʵʽڣΪڸƽ׶ΣҪʵģͣ
(4) ھȷʵģ͵³Ч;ȷĲĿǰƿ.
Ϊ˽߿ʵıʾͲͳһϵṹ£ǲ÷ȷģʾģ.ϸʵֲĹΪ˴ﵽ³Ч;ȷĿõһЩ.ģ͵ľȷϢòüƬʾҲƹ㵽.Ϊ˵õȷļν㷨ѡǹؼ.󽻵㷨ҪΪӷַ.Ŀǰڲķϻ⡢֧ԾѾ³ؼ˻󽻣58ݵ.
ڼԪʱǲ˲󽻵ķ.ԭһ棬ɷģе˲νṹģһΪάԪصı߽ͨάԪ壬Ӷ˷ֱʱڼԼɵĲһ.󽻵˻粿ص߽ͨ潻ҳֱӶص󽻣ӶϵͳĿɿ.һؼǽ߸٣ڼ󽻵ĹУģ͵ϢҳڵпཻļԪضԣ¼ٽ߷֧Ӷڿ˷ڽ߲նʧܵ.
1 ȷģͱʾ
ڷģУ9ݣһʾΪάԪأӦR1еһλʸһ߱ʾΪһͨġнһάԪأӦڲϵһ˵㣻һʾΪһͨġнĶάԪأӦڲϵһ򣬲߽綥ͱߣһʾΪһͨġнάԪأ߽ķӦR3ϵһռ򣬲߽ϵĶ㡢ߺ.
ͼ1˷ȷģ͵ݽṹͼϽΪϢΪϢͼ߿ʵģͳһ(solid)Ľṹ.ÿģ塢ǡ߿桢ߡ㡢ɣһɰ߹ɣÿ߷ΪһԷ෴İ.Ϣɷֱ𸽼桢ߡϵĲü桢ռߺͿռϢ.

ͼ1ȷģ͵ݱʾ
ģļϢΪһŲü棬ߵļϢΪһR3ϵĿռΪ˱ڽ涨ϵı߽.ļϢΪR3ϵһλʸ.
Ϊ˾ȷر棬ÿļϢͨһüƬ壬BzierF(s,t)ʾÿƬ

Vij=(xij,yij,zij)ΪƬĿƶ㣬ΪBernsteinʽ.F(s,t)ɿɴӲռ(s,t)ƽ浽άռR3һӳ.üͨԭռ估ϵĲü߶.üһǸ߽ߣܾȷ.òϵķֶƱʾõĲüΪϵĶ.Ϊ˱ʾգһΧƸ߽׽ߣ,üͨϵһ.
2 㷨
㷨Ϊ󽻼⡢Ƭ󽻺ͷָ10׶.
(1) 󽻼.ȶļԪ:㡢ߺ棬ðΧвԺԹ滮ȥཻ¼ཻԪض.
(2) Ƭ󽻺ͷָ.󽻼¼ĿཻԪضԣն㡢ߡĲιϵм󽻣Vertex-Vertex,Vertex-Edge,Vertex-Face,Edge-Edge,Edge-Face,Face-FaceĴȷ˷ָһ.ΪٶȺȶԣཻзõĽи.󽻹Уʵ¶ͱߣָƬƬõĽ߰մ¼ڽ.
(3) .ڲμӲսգһõĽȻ߽ϵһϵбջǰ廮Ϊı߽粿.бÿ߽粿һ߽in-outϵȻݲ,ѡʵı߽粿Ž߻б߽ճϣɽ.
ͼ2еԲͷвΪȽ󽻼⣬ҳཻSolid AеǰƽSolid BеԲ棬Ȼ󽻺ͷָ.Solid ASolid Bֱ𻮷Ϊ(a),(b)(c),(d)ٽ࣬Solid AвSolid BĲ(a)Solid BвSolid AĲ(c)ҳؽճγɽ.

ͼ2ԲͷĲĹ
3 Ƭ󽻺ͷָ
3.1 ཻ
ÿƬԼİΧ.Bzier͹ԣ11ݿ֪ƶ͹ȫ棬ˣͨΧвԿԹ˵󲿷ֲཻȻԹ滮.Թ滮ΪƬһƽ棬ǲཻ.ˣƵ㼯һָ棬ƬԲཻ.ʵSeidel12ݵԹ滮㷨.ַͨǼ¼ཻ.
3.2 Ƭ߼
ʹһڼͼѧͼоĲĿǰд.÷·Ϊӷַ13ݡ14,5ݡ󽻣15ݡ16,17ݺͲ1820.µļ˲ͬ,ͳΪ㷨21.
ϵͳ˽ͲϵķѽߵͶӰΪһƽֵ.㷨þٽߣǼβͨƽ߽˼θӶ.ϵͳõĸ㷨ڸٽ׶μĴڣӶȷЧصõ.
ƬĽ߿ԿǲϵĿͱջͼ3еll.ڿȻ߽һ㣬ϽĲ󽻼Edge-Faceеߺ󽻵õǽΪٵĳʼ.ڱջHohmeyer6ݵĻGaussͼĻ㷨бȻӷ֣ת.ȷеFace-FaceཻʱγɻǿԲý߸ٷָ󽻽м.

ͼ3߻llֱӦڲϵĿͱջ 
3.3 
УάԪصı߽ͨάԪ.ˣ󽻹ӦɵάԪؼ󽻷ָȻɸάԪؼ󽻣̳Ϊ.,һһ󽻵Ľ붨ıߺͶཻĽ.,άÿ߻ά󽻣ظĽ㣬ʱָĲһ.ͼ4ʾS1S2ֱS0󽻣߽ռC0S0󽻣𽻵P0P1C0S0ָһ.ˣǲ˲󽻵㷨󽻰Vertex-Vertex󽻡Vertex-Edge󽻡Edge-Edge 󽻺Vertex-Face󽻡Edge-Face󽻡Face-Face󽻵Ĵ.ֱЩ.

ͼ4S1S2ֱS0󽻣𽻵
P0P1C0S0ָһ
(1) Vertex-Vertex.ⶥǷغϣغ,ӺVertex-Vertex, Vertex-EdgeVertex-Faceɾ.
(2) Vertex-Edge.ж϶㵽ߵľ룬Χڣ¶㽫߷ѣԭ¶ΪغϣٲμӺ󽻣±߲μӺ.
(3) Edge-Edge .Χڽĳ㣬߷ѣ¶ΪغϣٲμӺ󽻣²ı߲μӺ.
(4) Vertex-Face.Χϣϲһڻԭ¶Ϊغ.
(5) Edge-Face.ڱߵĶ˵ѾVertex-Face󽻣غ϶Ϊ0,1,2.Ϊ2һߺغϲԣغϣ±ָ߲.
(6) Face-Face.вƬ󽻣ѲĵڻѲ,ݽ߲±,зָ.
3.4 ߸ٷָ
ϽFace-Faceཻ潻ߵĻϣǲ˽߸ٷָ.󽻵Ĺ̿ԿҳƬĽ߶εḶ́Խʽ󽻣ǵеļܴʧܣӶ˷Ƿ壬ǲ˽߸ٵķ.ĲϿǽߵɷΪ¼ջѾһųͼ5ʾ.

ͼ5
1´μΪ(S1,S2),(S2,S1).
2´μΪ(S1,S2),(S1,S2).
3´μΪ(S1,S2),(S1,S2).
ʵ󽻵£Ԥܲʵ㷨˻Ϊٷ.
ٷָ㷨£
(1) (fi,fj)ΪཻпཻԣfjSB,fiSAӺѡԻȡ(fi,fj)
(2) (fi,fj)Ľ߼Cij٦ת(6)
(3) CijգCij뽻Уת(6)򣬼
(4) Cij벻սĳCijCij벻սУת(6)
(5) CijգCij뽻УCij벻սУ
(6) fi,fjϢн߸٣ºѡԻأ
(7) ѡԻطǿգӺѡԻȡ(fi,fj)ת(2)򷵻أ󽻽ڽ.
4 ˻
󽻹̵Ľǵõ߻ͱָı߽粿磬ͼ2У鱻Ϊ(a)(b)ԲΪ(c)(d).Ҫÿ߽粿зԣٸضĲ;ñ߽粿Ƿ壬£A,BΪμӲ壬

Ա߽粿зԵĹ̳Ϊ.սգ߽粿ϵһһⲿ߽粿һⲿ֮Ȼ.
жһǷһһܷʱĲҪӸõһ彻ĸڲⲿ.漰/󽻣临ӶȶĴ.ʵϣϢǿԵõ߽粿ڽӹϵÿֻһԾͿ.߽һ߽粿߻ڽӱ߽粿ʱһϵȡ.ͨȷһ߽粿ķԣȻͨ߻ɢб߽粿.
˻ʵϵͳԵ⣬ڴϵͳУ˻ᵼʧܻ˳.ף12ݣ˻Ϊ㡢Ӵߺغ3.ڲ˲󽻺͸ٷָǵʵܽϺõشǰԼƬغ߽߱޶ʱ.ѾܹϺõʵҪ.
5 ʵֺͽ
ѾNTƽ̨Cʵ˸㷨.ϵͳGS-CAD98Ǵӹվƽ̨ϵZD-MCADIIϵͳݻ.ԭϵͳZD-MCADIIõǶģͣǵӦڸ߾ؼӹѧƵҪ˷ȷģͣһҪֶ.ͼ6ʵУҶ֣13棬ÿ涼һʵģģͣôΪƽ棩Ĳ.ͼ6·Ϊ13صͼϷΪеһ.ͼ7Ϊ߿ģƽཻĽؽ.£Ƭཻʱ㷨ĸӶΪO(mn)mnֱΪеƬ.ʵ,ͨĲԣ㷨ƽӶΪO(k)kΪʵཻƬ.

ͼ6Ҷֽʵ

ͼ7߿ʵ
*оõȻѧ𡢹863߿ƼĿ㽭ѧCAD&CGصʵҿſ.
߼飺1974ʿʦҪоΪͼѧ븨ƣ.飬1945ڣʿʦҪоΪͼѧCADȽ켼ԶDBMS.
1970ʿʦҪоΪCAD.
־1923ڣʿʦҪоΪ˹ܣCAD&CG.
ͨѶϵ:310027,㽭ѧ1549
ߵλ㽭ѧCAD&CGصʵҡݡ310027
㽭ѧ˹оݡ310027
E-mail: tang-m@netease.com
ο
1Hoffman C H. Geometric and Solid Modeling. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1989
2Masuda H. Topological operators and Boolean operations for complex-based nonmanifold geometric models. Computer Aided Design, 1993,25(2):119129
3Wiler Kenin J. Edge-based data structures for solid modeling in curved-surface environments. IEEE Computer Graphics and Applications, 1985,5(1):2140
4Stroud I. Modeling with degenerate objects. Computer Aided Design, 1990,22(6):344351
5Hu Chun-yi, Maekawa Takashi, Patrikalakis N M et al. Robust interval algorithm for surface intersections. Computer Aided Design, 1997,29(9):617627
6Hohmeyer M E. Robust and efficient intersection for solid modeling Ph.D. Thesis. Berkeley: University of California, 1992
7Krishnan S, Manocha D. An efficient surface intersection algorithm based on the lower dimensional formulation. Technical Report, TR94-064, University of North Carolina, 1994
8Sederberg T W, Nishita T. Geometric hermite approximation of surface patch intersection curves. Computer Aided Geometric Design, 1991,8:97114
9Gursoz E L, Choi Y, Friedrich B P. Boolean set operations on non-manifold boundary representation objects. Computer Aided Design, 1991,23(1):3339
10Crocker G A, Reinke W F. An enditable nonmanifold boundary representation. IEEE Computer Graphics & Application, 1991. 3951
11Farin G. Curves and surfaces for computer aided geometric design: a practical guide. New York, NY: Academic Press Inc., 1993
12Seidel R. Linear programming and convex hulls made easy. In: Proceedings of the 6th Annual ACM Conference on Computational Geometry. Berkeley, 1990. 211215. http://www-tcs.cs.uni-sb.de/seidel/index.en.html
13Lane J M, Riesenfeild R F. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980,2(1):150159
14Snyder J. Interval arithmetic for computer graphics. In: Proceedings of ACM Siggraph. 1992. 121130. http://www.gg.caltech.edu/papers/intervalabstract.html
15Rossignac J R, Requicha A A G. Piecewise-circular curves for geometric modeling. IBM Journal of Research and Development, 1987,31(3):296313
16Sederberg T W. Implicit and Parametric Curves and Surfaces, Ph.D. Thesis. Prude University, 1983
17Sarraga R F. Algebraic methods for intersection. Computer Vision, Graphics and Image Processing, 1983,22:222238
18Farouki R T. The characterization of parametric surface sections. Computer Vision, Graphics and Image Processing, 1986,33:209236
19Bajaj C L, Hoffmann C M, Hopcroft J E H. Tracing surface intersections. Computer Aided Geometric Design, 1988,5:285307
20Kriezis G A, Patrikalakis N M, Wolter F E. Topological and differential equation method for surface intersections. Computer Aided Design, 1992,24(1):4155
21Krishnan S, Gopi M, Manocha D et al. Interactive boundary computation of boolean combinations of sculptured solids. Computer Graphics Forum, 1997,16(3):6778
1998-09-11յԭ,1999-01-11յ޸ĸ
