Като се има предвид набор от повърхности в триизмерно пространство, аз се опитвам да присвоя всяка повърхност на зона, отнасяща се до най-малката 3D област, която наборът обхваща, или без зона, ако това не е приложимо. Също така искам да определя дали една повърхност е интерфейс между две зони. Така, например, ако имаме 11 повърхности, представляващи два куба, подредени един върху друг, повърхностите в горния куб ще бъдат в една и съща зона, а повърхностите в долния ще бъдат в различна зона (като интерфейсната повърхност е и в двете зони).
Като пример, искам да взема набор от повърхности като тази и да го превърна в това. Всеки цвят тук представлява зона, като сивото не е свързана зона (както в капака в долната част).
Направих известно търсене наоколо, опитвайки се да намеря дали някой вече е измислил алгоритъм за това, но не намерих нищо (повечето изглежда идентифицират региони, вместо да свързват повърхности с региона, който обхващат). Като такъв се опитвам да измисля свой собствен алгоритъм и се чудя дали има други алтернативи или дали моят метод ще работи.
Предполагам, че всички повърхности са свързани.
Идеята ми е следната:
- Изберете произволна повърхност, всяка от страните на която докосва точно една друга повърхност, и добавете това към зона 1.
- Добавете всяка свързана повърхност към зона 1, при условие че всяка от нейните страни докосва точно една друга повърхност.
- За онези свързани повърхности, които докосват повече от една повърхност от поне една от страните си, добавете ги към списъка „може би“.
- За всяка нова повърхност в зона 1 повторете стъпки 2-3.
- След като дадена повърхност бъде добавена към списъка „може би“ два пъти, добавете я към зона 1 и я премахнете от списъка „може би“. Маркирайте тази повърхност като зонален интерфейс.
- Добавете интерфейса на зона към зона 2.
- Изберете една произволна повърхност от списъка „може би“ и я задайте на зона 2 и изчистете списъка „може би“.
- Повторете стъпки 2-7 (разбира се, като актуализирате номера на зоната), докато няма неназначени повърхности.
Това изглежда работи за прости сценарии (напр. две кубчета, подредени един върху друг), но не съм сигурен дали има някакви трудни условия, за които трябва да внимавам, или ако се разпада, след като има повече от две зони които споделят една страна.
Всяко подобрение на моя груб алгоритъм/алтернативни идеи за изпълнение ще бъде оценено. Благодаря!
РЕДАКТИРАНЕ: Ето някои повече подробности в отговор на някои коментари. Зоната според моето определение е просто група от повърхности, които напълно ограничават 3D област без празнини. Така че, ако имах два куба, A и B, които не се докосват, щях да имам две зони: едната се състои от всички повърхности на куб A, а другата от всички повърхности на куб B. Ако имах куб, който липсва от една страна, няма да има зона, свързана с тези повърхности.
Крайната ми цел е да направя автоматизиран процес за групиране на повърхности в инструмент за моделиране, който създавам. Спецификите са класифицирани, но по същество се занимавам с модели, при които определени свойства са общи само между повърхности в една и съща „зона“, както е описано по-горе. Искам да направя автоматизиран процес, който създава тези зони, така че потребителят да може да приложи тези свойства към всички повърхности в зоната наведнъж, вместо да го прави ръчно.
По същество проблемът се свежда до намирането на най-малките 3D региони, които са напълно затворени от произволен набор от повърхности, и проследяване кои повърхности към кои региони принадлежат. Надявам се това да направи въпроса ми по-ясен.
