ऑक्टेवस का उपयोग कंप्यूटर ग्राफिक्स में अनुकूलन, विज़ुअलाइज़ेशन से संबंधित कई समस्याओं को हल करने के लिए किया जाता है, और न केवल। उदाहरण के लिए, प्रसिद्ध और प्रिय idSoftware, कंप्यूटर ग्राफिक्स तकनीक का प्रमुख और कंप्यूटर गेम से जुड़ी हर चीज, अपने नए और निश्चित रूप से, अभिनव स्पार्स वोक्सल ऑक्ट्री तकनीक के साथ उच्च तकनीक आईडी टेक 6 इंजन को लागू करता है, जो पर आधारित है एक अष्टमुखी वृक्ष है। सप्तक आपको पूरी तरह से विनाशकारी मॉडल ज्यामिति बनाने की अनुमति देता है, जैसा कि ड्यूकनेकम 3 डी इंजन के मुख्य प्रोग्रामर ने एक बार किया था, इस रचना को लिखा था। जब अनुकूलन की बात आती है, तो इस संरचना का उपयोग भौतिकी मॉडलिंग इंजनों में किया जाता है, जिससे पत्थर का काम बहुत आसान हो जाता है। खैर, यह किरण अनुरेखण के बिना नहीं करेगा, ऑक्टो-पेड़ों का उपयोग यहां भी किया जाता है।

कटौती के तहत यातायात का एक बहुत!

एक ऑक्ट्री ट्री एक पेड़ की तरह, पुनरावर्ती डेटा संरचना है, जिसके प्रत्येक नोड में आठ वंशज हैं। इसे तीन आयामी घन ( स्वर ) के रूप में दर्शाया जा सकता है, जो तीन विमानों द्वारा ललाट, क्षैतिज और प्रोफ़ाइल विमानों के समानांतर विभाजित किया जाता है और घन के ज्यामितीय केंद्र से होकर गुजरता है। नतीजतन, हमें आठ क्यूब्स मिलते हैं जो एक ऑक्ट्री ट्री नोड के वंशज हैं, अर्थात्। हमारे बड़े घन।
नीचे ओकट्री के पेड़ तत्वों की खोज, बायपास और हटाने के लिए सरल एल्गोरिदम प्रस्तुत किए जाएंगे।

1 एक पेड़ को खोजने और बनाने के लिए एल्गोरिदम

एक पेड़ बनाएँ। नोड में हम voxel के ज्यामितीय मापदंडों को दर्ज करेंगे, हाइलाइटिंग के लिए इसका रंग। जैसी संरचना दिखेगी

struct octTree { mid midle; //   float lenght; //   char novusial; //  : / RGB_color color;//   octTree* up; //    octTree* t1; //  octTree* t2; octTree* t3; octTree* t4; octTree* t5; octTree* t6; octTree* t7; octTree* t8; }; struct mid //   { float x; float y; float z; }; struct RGB_color //  { float R; float G; float B; }; 

अगला, खरोंच से पूरी संरचना बनाएं। Dscr - घन का संकल्प (ओक्ट्री ट्री), पूरे पेड़ के सबवोक्सल्स की संख्या। Descr 8. का एक मल्टीपल होना चाहिए। मिड मिडल - इसके केंद्र के निर्देशांक, फ्लोट लेन - क्यूब के किनारे की लंबाई, ओकट्री * अप - पेरेंट नोड, फ़ंक्शन के पहले भाग में, रूट डालें। रूट, ऑक्टट्री ** एल - एक पॉइंटर को बनाया नोड को बचाने के लिए एक सूचक जहां पहला रन, रूट एड्रेस ** रूट का एड्रेस डालें।

 // . dscr -    el . void OctObject::makeTr(octTree** el,int dscr,mid midle,float len,octTree* up) { mid setmidle; //        / if(*el==NULL) { (*el)=new octTree; (*el)->lenght=len; (*el)->midle=midle; (*el)->novusial=0; (*el)->color.B=(*el)->color.G=(*el)->color.R=1; // . null(*el); (*el)->up=up; if(!(dscr%8)) { (*el)->novusial=1;//    . //      //    ,   setmidle.x=(*el)->midle.x-(*el)->lenght/4; /// 1 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t1),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 2 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t2),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 3 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t3),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 4 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t4),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 5 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t5),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 6 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t6),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 7 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t7),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 8 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t8),dscr/8,setmidle,(*el)->lenght/2,(*el)); } } else if(*el==root) //     { setmidle.x=root->midle.x-root->lenght/4; /// 1 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t1),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 2 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t2),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x-root->lenght/4;/// 3 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t3),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 4 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t4),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x-root->lenght/4;/// 5 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t5),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 6 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t6),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x-root->lenght/4;/// 7 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t7),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 8 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t8),dscr/8,setmidle,root->lenght/2,root); } return; } 

जैसा कि आप देख सकते हैं, फ़ंक्शन पुनरावर्ती है।
जब कैमरे को घुमाया जाता है तो सबवोक्सेल को नेत्रहीन रूप से उजागर करने के लिए, हम ऑक्ट्री में एक तत्व की खोज के लिए एक एल्गोरिथ्म बनाएंगे।

स्वर को उजागर करने के लिए, आपको इसे खोजने की आवश्यकता है, इसके लिए हम स्क्रीन के केंद्र से सीधे किरण अनुरेखण विधि को त्रि-आयामी दृश्य की गहराई में लागू करते हैं, और स्वर के स्वयं प्राप्त करने के लिए स्वर के साथ किरण के पाए गए प्रतिच्छेदन बिंदु का उपयोग करते हैं।

एक्स, वाई, जेड - वर्तमान समय में किरण वेक्टर के निर्देशांक। octTree * el - वह नोड जिसमें हम एक चौराहे की तलाश कर रहे हैं।

 //    ,   . octTree* OctObject::seach(float x, float y, float z,octTree *el) { if(el->t1==NULL) if(el->novusial!=1) //       ,    . return el; else return NULL; else { if(((el->midle.z+el->lenght/2)>=z)&&(el->midle.z<=z))//1 -   oz -  { if(((el->midle.y+el->lenght/2)>=y)&&(el->midle.y<=y))// 1-    oy-  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t1); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t2); } else return NULL; //   } else { if(((el->midle.y-el->lenght/2)<=y)&&(el->midle.y>=y))// 2-   oy -  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t3); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t4); } else return NULL; //   } else return NULL; //   } } else { if(((el->midle.z-el->lenght/2)<=z)&&(el->midle.z>=z))//2 -   oz -  { if(((el->midle.y+el->lenght/2)>=y)&&(el->midle.y<=y))// 1-    oy-  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t5); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t6); } else return NULL; //   } else { if(((el->midle.y-el->lenght/2)<=y)&&(el->midle.y>=y))// 2-   oy -  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t7); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t8); } else return NULL; //   } else return NULL; //   } } else return NULL; //  } } } 

हम इस फ़ंक्शन को कीबोर्ड और माउस हैंडलर से स्पेस बार दबाकर या स्वर को हटाने के लिए स्क्रॉल करके कॉल करेंगे। यहां हम अपने बीम का पता लगाएंगे।

 //    ,         . octTree* OctObject::FindVoxeloutside(float a, float b,float c) { float x,y,z; octTree *ret; z=(fabs(x=(fabs(a)>=fabs(b) ? a : b))>=fabs(c) ? x : c);//      ,  ,,    . if(z==a) { x=a; //   do{ if(fabs(a)>=fabs(x)) { y=x/a*b; z=x/a*c;//   .        . if((ret=seach(x,y,z,root))!=NULL) { return ret; } x+=eps*(a>0 ? -1 : 1); }else return NULL; }while(true); } else if(z==b) { y=b; //   do{ if(fabs(b)>=fabs(y)) { x=y/b*a; z=y/b*c;//   .        . if((ret=seach(x,y,z,root))!=NULL) { return ret; } y+=eps*(b>0 ? -1 : 1); }else return NULL; }while(true); } else if(z==c) { z=c; //   do{ if(fabs(c)>=fabs(z)) { x=z/c*a; y=z/c*b;//   .        . if((ret=seach(x,y,z,root))!=NULL) { return ret; } z+=eps*(c>0 ? -1 : 1); }else return NULL; }while(true); } return NULL; } 

2 एक नोड हटाएं

मेरे मामले में, संरचना से नोड को पूरी तरह से हटाना वांछनीय नहीं है, और यह महंगा है। हम हटाए गए ध्वज के साथ हटाए गए तत्व को चिह्नित करेंगे ताकि ओपेनगेल पाइपलाइन को इसके कोने न भेजें और इसके चेहरे को प्रदर्शित न करें। यहां एक विलंबित पुनर्निर्माण करना संभव होगा, जो एक निश्चित घटना के पूरा होने पर या एक विशिष्ट समय अंतराल पर, पूरे पेड़ को फिर से बनाएगा, जिसमें मेमोरी से चिह्नित नोड्स और सबनॉड्स को छोड़कर और हटा दिया जाएगा।

 //   (  6   6  ""   ). void OctObject::del(octTree *el) { if(el==NULL) { return; } else { el->novusial=1;//    (). if(el->up==NULL)//  . return; if(el->up->novusial)//  /     el, return; // novusial==1,   ,    novusial==1, ..   . del(el->up); } return;} 

इसके अलावा, मुझे उम्मीद है, "भाग 2" में मैं बताऊंगा और दिखाऊंगा कि ओपनगैल पर यह सब कैसे हलचल करना है।

आप इस कोड को ओपनजीएल में घूमने वाले बाकी कोड, बायनेरिज़ और पूरी परियोजना को यहाँ देख सकते हैं ।