1 B-rep स्ट्रीम्स (B-rep Streams)
किसी मानक बहुभुज प्रारूप (Standard Polygonal Format) द्वारा बाह्य रूप से परिभाषित B-rep को आयात करने के लिए एक निर्माता प्रक्रिया (Producer Process) स्थापित करना स्पष्ट रूप से कहा गया है, उदाहरण के लिए वेव फ्रंट (Wave Front) या Java3D obj फ़ाइल, को हमारे ज्यामितीय पाइपलाइन (Geometric Pipeline) के लिए एक इनपुट स्ट्रीम में। बहुभुज और नॉर्मल द्वारा प्रदान की गई बाउंड्री प्रतिनिधित्व (Boundary Representation) सुसंगत रूप से उन्मुख (Coherently Oriented) होनी चाहिए। आमतौर पर कंप्यूटर ग्राफिक्स में प्रयुक्त ज्यामितीय मॉडलों के लिए इनपुट फ़ाइल को नॉन-प्लेनर बहुभुज (Nonplanar Polygons) और अन्य ज्यामितीय अशुद्धियों से निपटने के लिए फ़िल्टर करना आवश्यक हो सकता है। सुसंगत रूप से उन्मुख त्रिकोणों (Coherently-Oriented Triangles) का आउटपुट स्ट्रीम, फिर नीचे वर्णित एल्गोरिदमिक चरणों द्वारा हमारे ट्विन प्रोग्रेसिव-BSP (बाइनरी सर्च पार्टीशनिंग) ट्रीज़ में परिवर्तित किया जाता है।
2 B-rep से BSP एल्गोरिदम रूपरेखा (B-rep to BSP Algorithm Outline)
हमारी विधि की एक बुनियादी प्रक्रिया प्रत्येक त्रिकोण के पूर्व-गणना जड़ता (Pre-computed Inertia) के संकुचन (Contraction) द्वारा त्रिकोण उपसमुच्चयों (Triangle Subsets) की जड़ता की गणना है, और त्रिकोण उपसमुच्चयों की जड़ता के आइजन विघटन (Eigen Decomposition) द्वारा उनके आकार को इष्टतम रूप से और पुनरावर्ती रूप से बांधना है।
d-आयामी मामले में, आकार कारावास (Shape Confinement) यूलर मैट्रिक्स (Euler Matrix) के प्रत्येक d आइजनवेक्टर्स (Eigenvectors) के लिए 2 चरम स्पर्श हाइपरप्लेन्स (Extremal Tangent Hyperplanes) को लागू करके प्राप्त किया जाता है। संबंधित 2d हाइपरस्पेस का प्रतिच्छेदन वर्तमान सेल में शामिल बाउंड्री उपसमुच्चय का सर्वोत्तम-फिटिंग (हाइपर) पैरेललपाइपेड (Best-fitting (Hyper)parallelepiped) बनाता है। 3-आयाम में, ऐसे 6 = 2×3 प्लेन होते हैं।
आरंभीकरण (Initialization)
- प्रत्येक इनपुट त्रिकोण के एफाइनली विस्तारित यूलर टेंसर्स (Affinely Extended Euler Tensors) की गणना पहले की जाती है (रैखिक समय में)।
- इनपुट त्रिकोणों का पूरा सेट BSP रूट के साथ जुड़ा होता है।
- संपूर्ण E3 स्पेस (जो कन्वेक्स है) को रूट से जोड़ा जाता है।
- रूट लेबल को FUZZY पर सेट किया जाता है।
पुनरावर्ती मामला (Recursive Case)
- वर्तमान FUZZY सेल को अधिकतम 6 लंबवत हाइपरप्लेन्स द्वारा विभाजित किया जाता है जो वर्तमान त्रिकोण उपसमुच्चय के यूलर टेंसर के मैट्रिक्स प्रतिनिधित्व के आइजनवेक्टर्स के लंबवत होते हैं।
- ऐसे प्लेन वर्तमान त्रिकोण उपसमुच्चय के वर्टेक्स v पर रैखिक फंक्शन w = a • v के निम्नतम और उच्चतम मान के माध्यम से गणना की जाती है, जहां a को वर्तमान आइजनवेक्टर दर्शाया जाता है।
- प्रत्येक आइजनवेक्टर के लिए, दो मैक्स-मिन समानांतर हाइपरप्लेन्स द्वारा अधिकतम तीन कन्वेक्स सेल उत्पन्न होते हैं, जो या तो {OUT, FUZZY, IN} या {OUT, FUZZY, OUT} होते हैं।
- प्रत्येक FUZZY सेल को अधिकतम आइजनवेक्टर से जुड़े प्रमुख हाइपर-प्लेन द्वारा आगे विभाजित किया जाता है।
- उनके वर्टेक्स के कंटेनमेंट टेस्ट (Containment Test) के माध्यम से त्रिकोणों का एक छोटा उपसमुच्चय प्रत्येक विभाजित सेल से जुड़ा होता है।
- विभाजन प्लेन को पार करने वाले त्रिकोण विभाजित होते हैं, और (सब) त्रिकोण नोड सबट्रीज़ को असाइन किए जाते हैं।
आधार मामला (Base Case)
जड़ता-आधारित पुनरावर्ती विभाजन तब रुकता है जब वर्तमान सेल में केवल बाउंड्री त्रिकोणों की एक छोटी संख्या होती है। बाउंड्री त्रिकोणों के प्लेन को लागू करके एक अंतिम सेल विभाजन निष्पादित किया जाता है।
