درخت هشت‌تایی

درخت هشت‌تایی (به انگلیسی: Octree) یک داده‌ساختار درخت است که در آن هر گره داخلی دقیقاً هشت فرزند دارد. درخت‌های هشت‌تایی اغلب برای افراز کردن یک فضای سه‌بعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده می‌شوند. درخت‌های هشت‌تایی در واقع معادل چاردرخت در حالت سه بعدی اند. اسم این درخت از دو کلمه انگلیسی oct و tree تشکیل شده‌است، اما توجه کنید که این کلمه معمولاً به صورت octree فقط با یک حرف t نوشته می‌شود. درخت‌های هشت‌تایی غالباً در گرافیک سه‌بعدی رایانه‌ای و موتورهای بازی سه‌بعدی استفاده می‌شوند.

چپ: تقسیم بازگشتی یک مکعب به اکتان. راست: درخت هشت‌تایی معادل.

درخت‌های هشت‌تایی برای نمایش فضایی

هر گره در یک درخت هشت‌تایی فضا را به هشت اکتان تقسیم می‌کند. در یک درخت هشت‌تایی نقطه‌ای ناحیه‌ای، هر گره در واقع یک نقطه سه‌بعدی را نگه می‌دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت‌تایی نقطه‌ای که حول آن فضا تقسیم می‌شود به‌طور ضمنی مرکز قسمتی است که گره نمایش می‌دهد. گره ریشه از یک درخت هشت‌تایی PR می‌تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت‌تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت‌ هشت‌تایی با درخت کی‌دی متفاوت است. درخت‌های کی‌دی در راستای یک بعد تقسیم‌بندی انجام می‌دهند اما درخت‌های هشت‌تایی پیرامون یک نقطه (در راستای سه‌بعد) تقسیم‌بندی انجام می‌دهند. همچنین درخت‌های کی‌دی همواره دودویی‌اند که در مورد درخت‌های هشت‌تایی این گونه نیست. با به‌کارگیری جستجوی عمق اول (dfs) باید گره‌ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.

تاریخچه

درخت هشت‌تایی برای گرافیک سه‌بعدی رایانه‌ای اولین بار توسط دونالر میقر در مؤسسه پلی‌تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت‌های هشت‌تایی: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیلهٔ کامپیوتر"[1] آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ (با تاریخ اولویت ۱۹۸۴) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت‌تایی"[2] نیز بود.

کاربردهای رایج درخت هشت‌تایی

کاربرد در درجه‌بندی رنگ‌ها

الگوریتم درجه‌بندی رنگ در درخت هشت‌تایی توسط گرواتز و پورگاتوفر در سال ۱۹۸۸ ابداع شد. این الگوریتم داده‌های مربوط به رنگ یک تصویر را به صورت درخت هشت‌تایی درآورده و درخت را تا عمق ۹ سطح کدگذاری می‌کند. از آنجا که در سیستم رنگی آرجی‌بی سه مؤلفه رنگی وجود دارد و ۸=۳^۲ از درخت هشت‌تایی استفاده می‌شود. شماره مربوط به یک گره در سطح بالا با یک فرمول مشخص می‌شود که از پرارزش‌ترین بیت‌های مؤلفه‌های رنگی قرمز، سبز و آبی استفاده می‌کند، مثلاً 4r + 2g + b. سطح بعدی یا پایین‌تر از بیت‌های پرارزش بعدی استفاده می‌کند و به همین ترتیب جلو می‌رود. گاهی بیت‌های کم ارزش نادیده گرفته می‌شوند تا اندازه درخت کاهش یابد. این الگوریتم از لحاظ مصرف حافظه بسیار بهینه است چرا که اندازه درخت می‌تواند محدود باشد. سطح پایین یک درخت هشت‌تایی از برگ‌هایی که به داده‌های رنگی مربوطند و در درخت نمایش داده نمی‌شوند، تشکیل می‌گردد. این گره‌ها در ابتدا حاوی تک‌بیت‌ها هستند. اگر تعداد بیشتری از یک مقدار دلخواه رنگ از پالت‌ها وارد درخت شوند، اندازه درخت می‌تواند به صورت پیوسته کاهش یابد. این کار با دنبال کردن یک گره سطح پایین و افزایش میانگین مقدار بیتی آن تا رسیدن به برگ ادامه می‌یابد. در واقع به این ترتیب قسمتی از درخت هرس می‌شود. هنگامی که این کار به‌طور کامل انجام شود، با پیمایش همهٔ مسیرهای درخت تا برگ‌ها و در نظر گرفتن بیت‌ها در طول مسیر می‌توان به‌طور تقریبی تعداد رنگ‌های لازم را به دست آورد.

جستارهای وابسته
  • افراز فضای دودویی
  • درخت کی‌دی
  • چاردرخت
  • زیرفضا
  • محدود کردن سلسله مراتب وقفه
  • مسئله اندازه‌گیری Klee
  • درخت‌های هشت‌تایی خطی
  • مکعب ۲, موتور بازی سه بعدی که هندسه‌ آن به‌طور کامل برمبنای درخت هشت‌تایی است.
  • موتور ارائه گرافیکی شی‌گرا, یک پیاده‌سازی مدیریت صحنه درخت هشت‌تایی دارد.
  • ایرلیچت موتور, از گره‌های صحنهٔ درخت هشت‌تایی پشتیبانی می‌کند.
  • آی‌دی تک ۶ یک موتور بازی سه‌بعدی در حال توسعه که واکسل‌هایی را که در درخت هشت‌تایی استفاده می‌شوند به‌کار می‌گیرد.
  • واکسل

پانویس
  1. میقر, دونالد (October 1980). "درخت‌هشت‌تایی Encoding: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیلهٔ کامپیوتر". مؤسسه پلی‌تکنیک رنسلیر (گزارش فنی IPL-TR-80-111).
  2. میقر, دونالد. "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت‌تایی". یواس‌پی‌او. Retrieved 20 September 2012.
  3. هنینگ ابرهاردت، وسا کلومپ، یوه د. هانبک، "درخت‌های چگالی برای تخمین وضعیت بهینه غیرخطی"، مجموعه مقالات ۱۳امین کنفرانس بین‌المللی همجوشی اطلاعات، ادینبرگ، انگلیس، جولای، ۲۰۱۰.
  4. و. دروله، ل. جاولین و ب. زر، "شخصیت تضمین شدهٔ فضای کشف‌شده از روبات‌های موبایل به وسیله‌ی سابپوینگ"، ان‌او‌ال‌سی‌او‌اس ۲۰۱۳.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Octree». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۰ اردیبهشت ۱۳۹۳.

پیوند به بیرون
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.