Шектелетін интервалдық иерархия - Bounding interval hierarchy

A шекаралық интервал иерархиясы (BIH) бөлу болып табылады мәліметтер құрылымы сол сияқты көлемдік иерархиялар немесе кд-ағаштар. Шектелген интервалдық иерархияларды жоғары өнімділікте (немесе нақты уақытта) пайдалануға болады сәулелік бақылау және әсіресе динамикалық көріністер үшін пайдалы болуы мүмкін.

BIH алғаш рет SKD-Trees атауымен ұсынылды,[1] Ooi және басқалар ұсынған және BoxTrees,[2] Закман өз бетінше ойлап тапқан.

Шолу

Шектелген интервалдық иерархиялар (BIH) екеуінің де көптеген қасиеттерін көрсетеді көлемдік иерархиялар (BVH) және кд-ағаштар. BIH-дің құрылысы мен сақталуы BVH-мен салыстыруға болатын болса, BIH-нің өтуі осыған ұқсас. кд-ағаштар. Сонымен қатар, BIH бар екілік ағаштар kd-ағаштар сияқты (және олардың түпнұсқалары, BSP ағаштары ). Сонымен, BIH оның ата-бабалары сияқты ось бойынша тураланған, бірақ BIH-ді жалпы оське сәйкес келтірмеген түрде жүзеге асыру мүмкін болуы керек (тегістелмеген жазықтықтарды қолданатын BSP ағашына ұқсас), бұл, әрине, онша қажет болмай қалады сандық тұрақтылықтың төмендеуіне және сәуленің өтуінің күрделілігінің жоғарылауына дейін.

BIH басты ерекшелігі - бір түйінге 2 жазықтықты сақтау (кд ағашы үшін 1-ден және тураланған осьтен 6-ға қарағанда) қорап бір-бірімен қабаттасуға мүмкіндік беретін иерархия (BVH сияқты), бірақ сонымен бірге балаларға бір өлшем / ось бойынша тапсырыс беру (мысалы, kd ағаштары үшін).

Сондай-ақ, BIH деректер құрылымын құрылыс кезеңі үшін қолдануға болады, бірақ ағашты дәстүрлі осьпен тураланған шектеу қораптарының иерархиясы жүргізеді. Бұл үлкен сәулелер байламы үшін жылдамдықты жеңілдетуге мүмкіндік береді[3] сақтау кезінде жады /кэш пайдалану төмен.

Шектеу интервалды иерархиялардың кейбір жалпы атрибуттары (және BIH-ге қатысты әдістер) сипатталғандай[4] мыналар:

  • Өте жылдам құрылыс уақыты
  • Жады төмен із
  • Қарапайым және жылдам жүру
  • Өте қарапайым құрылыс және өтпелі алгоритмдер
  • Құрылыс және жүру кезінде жоғары сандық дәлдік
  • Kd ағаштарымен салыстырғанда тегіс ағаш құрылымы (ағаштың тереңдігі төмендеген)

Операциялар

Құрылыс

Кез келгенін салу кеңістікті бөлу құрылымының кейбір нысандары эвристикалық әдетте қолданылады. Бұл үшін беткейлік аймақ эвристикалық, әдетте көптеген бөлу схемаларында қолданылады, мүмкін үміткер. Тағы бір қарапайым, эвристикалық - суреттелген «жаһандық» эвристика[4] бұл тек қажет ось бойынша тураланған шекті қорап примитивтердің толық жиынтығынан гөрі оны жылдам құрылыс үшін әлдеқайда қолайлы етеді.

BIH үшін жалпы құрылыс схемасы:

  • көріністі шектейтін қорапты есептеңіз
  • бір осьті және осы оське перпендикуляр сплит жазықтығын таңдау үшін эвристикалық әдісті қолданыңыз
  • объектінің шекара қорабына байланысты (тек қана) объектілерді солға немесе оңға қарай сұрыптау (сплит жазықтығымен қиылысатын нысандар баланың көлемімен немесе кез-келген басқа эвристикамен қабаттасуымен сұрыпталуы мүмкін екенін ескеріңіз)
  • сол жақтағы барлық объектілердің максималды шектеу мәнін және сол ось үшін оң жақтағылардың ең төменгі шектік мәнін есептеу (кейбір эвристика үшін алдыңғы қадаммен біріктірілуі мүмкін)
  • бөлінген осьті жаңа түйінде кодтайтын 2 битпен бірге осы 2 мәнді сақтаңыз
  • балаларға арналған 2-қадаммен жалғастырыңыз

Ұшаққа бөлінген кандидатты іздеудің ықтимал эвристикасы:

  • Классикалық: ең осьті және сол осьте түйінді шектейтін қораптың ортасын таңдаңыз
  • Классикалық: объектілердің медианасы арқылы ең ұзын осьті және бөлінген жазықтықты таңдаңыз (нәтижесінде сол жақтағы ағаш пайда болады, бұл сәулені іздеу үшін өте өкінішті)
  • Жаһандық эвристикалық: сплит жазықтығын ғаламдық критерий негізінде тұрақты тор түрінде таңдаңыз (қажет емес бөлінулерден аулақ болыңыз және түйін көлемін мүмкіндігінше текше етіп ұстаңыз)
  • Эвристикалық беттік аймақ: барлық ықтимал сплиттік үміткерлердің жиынтығы бойынша екі баланың беткі қабатын және объектілерінің санын есептеп шығарыңыз, содан кейін ең аз шығындарды таңдаңыз (оңтайлы деп есептелінеді, дегенмен шығын функциясы дәлелдеу үшін ерекше талаптар қояды) өмірде орындала алмайтын формула, сонымен қатар бағалау өте баяу эвристикалық)

Сәулені кесу

Траверсаль фазасы кд-ағашының траверсалына өте ұқсас: төрт қарапайым жағдайды ажырату керек, мұнда сәуле

  • сол жақ баланы кесіп өтеді
  • тек дұрыс баланы қиып өтеді
  • екі баланы да қиып өтеді
  • баланың екеуін де қиып өтпейді (жалғыз жағдай kd өту кезінде мүмкін емес)

Үшінші жағдайда, ағымдағы түйіннің бөлінген осіне тең компоненттің сәулелену бағытына (теріс немесе оң) байланысты (х, у немесе z), өтпелі қозғалыс алдымен солға (оң бағытқа) немесе оңға (теріс) жалғасады бағыт) бала, ал екіншісі а-ға итеріледі стек кейінге қалдырылған потенциал үшін.

Траверсаль жапырақ түйіні табылғанша жалғасады. Жапырақтағы заттарды қиып өткеннен кейін стекстен келесі траверс элементі шығады. Егер стек бос болса, барлық тесілген жапырақтардың ең жақын қиылысы қайтарылады. Егер қойылған элемент толығымен қазіргі жақын қиылыстың шегінен асып кетсе, оның өтпесі өткізіп жіберіледі.

Сондай-ақ, бесінші траверсальды жағдайды қосуға болады, бірақ бұл сәл күрделі құрылыс кезеңін қажет етеді. Түйіннің сол және оң жазықтығының мағыналарын ауыстыра отырып, түйіннің екі жағындағы бос орынды кесіп тастауға болады, бұл өту кезінде бұл ерекше жағдайды анықтау үшін түйінде сақталатын қосымша бит қажет. Бұл жағдайды траверсаль фазасында өңдеу сәуле сияқты қарапайым

  • тек ағымдағы түйіннің немесе жалғыз туындысын қиып өтеді
  • ештеңені қиып өтпейді

Қасиеттері

Сандық тұрақтылық

Үшбұрыштарды иерархия құру / сұрыптау кезіндегі барлық операциялар мин / макс-амалдар және салыстыру болып табылады. Осылайша, үшбұрышты кесу қажет емес, өйткені kd-ағаштардағыдай және түйінді сәл қиып өтетін үшбұрыштар үшін қиындық тудыруы мүмкін. Kd орындалуы мұқият жазылған болса да, сандық қателіктер анықталмаған қиылысқа әкеліп соқтыруы мүмкін және осылайша жіберілген сәулелер мен объектілер қиылысына байланысты қателер (геометриядағы тесіктер) пайда болуы мүмкін.

Кеңейтімдер

Геометрияны бөлу үшін бір түйінге екі жазықтықты пайдаланудың орнына, n-ary BIH құру үшін кез-келген жазықтық санын қолдануға немесе стандартты екілік BIH-да бірнеше жазықтықты қолдануға болады (бір түйінге бір және төрт жазықтық ұсынылған болатын)[4] содан кейін дұрыс бағаланады[5]) объектіні жақсы бөлуге қол жеткізу.

Сондай-ақ қараңыз

Әдебиеттер тізімі

Қағаздар

  1. ^ Нам, Беомсок; Сусман, Алан. Көп өлшемді ғылыми деректер жиынтығы үшін кеңістіктік индекстеу әдістерін салыстырмалы түрде зерттеу
  2. ^ Закманн, Габриэль. Қақтығысты минималды иерархиялық анықтау Мұрағатталды 2007-02-10 Wayback Machine
  3. ^ Уалд, Инго; Булос, Сүлеймен; Шерли, Питер (2007). Динамикалық шектеу көлемінің иерархияларын қолдана отырып, деформацияланатын көріністерді бақылау
  4. ^ а б c Вахтер, Карстен; Келлер, Александр (2006). Лездік сәулелерді іздеу: шекаралық интервал иерархиясы
  5. ^ Вахтер, Карстен (2008). Квази-Монте-Карло жеңіл көлікті тиімді сәулелендіру арқылы модельдеу

Сыртқы сілтемелер