Воксельное октодерево

Тема в разделе "C/C++/C#", создана пользователем Vendigo, 14 апр 2011.

  1. Vendigo

    Vendigo Гость

    Октодерево — тип древовидной структуры данных, в которой у каждого внутреннего узла есть до восьми потомков. Деревья октантов чаще всего используются для разделения трёхмерного пространства, рекурсивно разделяя его на восемь октантов. Каждый узел представляет собой кубическое подмножество 3х мерного объема.

    Каждый узел обозначается как:
    1) Черный. Если куб полностью принадлежит объекту
    2) Белый. Если куб не имеет пересечений с объектом, то есть принадлежит фону
    3) Серый. Если куб частично принадлежит объекту. В этом случае узел имеет 8 потомков ( октантов), представляющих собой 8 одинаковых по размеру кубов

    Алгоритм построения следующий
    1) Сборка начального восьмеричного дерева, содержащего один единственный корневой узел с пометкой "черный"). Этот узел на уровне 0. Установить текущий уровень 0.
    2) Все черные узлы текущего уровня находятся в связанном списке. Установить текущий узел первым узлом в списке.
    3) Текущий узел проецируется на изображения и определяется его метка (этот метод написан)
    4) Если узел отмечен серым , на следующем уровне он порождает восемь потомков, каждый из которых будет черным
    5) Если есть еще узлы в списке текущего уровня то переходим к след. Узлу и переходим к шагу 3. Если все узлы текущего уровня обработаны, уровень увеличивается и переходим к шагу 2
    6) Процесс продолжается пока не достигнут заданный максимальный уровень

    Не могу написать алгоритм рекурсивного построения такого дерева. Пишу на C#, хотя буду рад помощи на любом языке
    Структура следующая
    Код (C++):
    class octree
    {      
    public voxel Data; //данные узла(текущий куб)
    public octree[] Branchs; //массив из 8 потомков
    int level;   //уровень
    NodeMark mark; //метка узла       
    }
     
  2. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0

    Вложения:

    • octree_code.zip
      Размер файла:
      26,6 КБ
      Просмотров:
      8
  3. Vendigo

    Vendigo Гость

    Смотрел раньше и то и другое.
    Первое - для рендера сцен, второе - близко, но там не реализован приведенный мной алгоритм построения.
    Мне нужна помощь в реализации именно этого алгоритма, а не ссылки на левые примеры, ибо октодеревья применяются для решения широкого круга задач
     
  4. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Ну извини что дал тебе левые ссылки. Я так понимаю все ссылки в интернете ты уже облазил... Скажи, а ты сам пробовал что-нибудь сделать не считая того что написал структуру? Или ты думаешь за тебя сейчас все быстренько сделают другие?
     
  5. Vendigo

    Vendigo Гость

    Да я тебя в принципе и не упрекаю, неужели так задело слово "левые"? Написал его во избежание того, чтобы не давали ссылки из гугла по запросу "воксельное октодерево". Вроде приведен достаточно конкретный алгоритм построения...
    Меня ставит в тупик, что деревья обычно строятся в глубину, а в приведенном алгоритме - по уровням ( в ширину)
    P.S. Основная задача - 3D - реконструкция по фото, сомневаюсь, что ее кто -то за меня выполнит, а тем более быстренько :)
     
  6. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Меня скорее задело то что ты и сам ничего не написал, и любой помощи на любом языке не рад. Если честно то вряд ли кто-то станет думать над этой задачей более углубленно без твоего содействия) Ты задал слишком непростую задачу слишком простым языком)
     

Поделиться этой страницей