Выбор стратегии трасировки пространства для создания 3D модели

Вот скажем есть программа в которой генерируется виртуальное пространство с ландшафтом, зданиями, разными объектами.
Требуется с заданным разрешением составить меш (mesh) этого пространства для последующего использования в 3D редакторах и т.п.
Из доступных инструментов - только пускать лучи трассировки:
- задаем координаты начала луча и его направление и получаем координаты точки куда уперся луч, или узнаем что луч уходит в бесконечность.

Гарантируется что мы знаем координаты как минимум одной точки где в виртуальном мире есть непустое пространство.
Гарантируется что размеры непустого пространства не бесконечно, но заранее границы не известны.
Предполагается что нет далеко отстоящих друг от друга "островков" непустого пространства или такие островки, которые далеко от начальной точки, не будут нам интересны.
Поверхности могут быть односторонними - например, сверху поверхность трассировкой детектируется, а снизу - нет.


Вопрос же у меня такой:
какую стратегию обхода здесь лучше всего применить?

пока что придумал что можно делать трассировку вдоль 3D сетки в шести направлениях (верх/низ/слева/справа/спереди/сзади) расширяясь от начальной точки через обход в ширину
т.е.:
начинаем с трех линий сетки проходящих через известную начальную точку, добавляем их в очередь обработки по два раза чтобы пройти по одной линии в двух направлениях
берем непройденную линию сетки, пускаем луч из бесконечности по этой линии, если уперся куда-то, то (а) записываем найденную точку, (б) берем ближайший узел сетки и добавляем в очередь 6 направлений по 3 линиям сетки этого узла если такие направления не были пройдены ранее, (в) запускаем новый луч от ближайшего узла сетки стоящего за найденной точкой вдоль текущего направления, и так пока не уйдем в бесконечность
после запуска луча также добавляем в очередь обработки 4 ближайшие луча-соседа по тому же направлению, если такие лучи не были пройдены ранее
если луч сразу ушел в бесконечность, то от него соседей не добавляем.


Есть еще проблема подбора алгоритма формирования меша по точкам, но пока не буду тут его поднимать - задача вроде бы "типовая" и готовые реализации данного алгоритма, думаю, я смогу найти сам.

0

Сообщение от wingblack программа в которой генерируется виртуальное пространство с ландшафтом, зданиями, разными объектами.

Наверно лучше всего генерировать их красиво сразу(минимум граней в нужных местах и т.п). Тогда только экспорт. Будет скорость работы, точность поверхности, минимум полигонов что важно для 3д игр и вкусно редакторам...наверно только это оптимум. Другой метод будет муторный.

Сообщение от wingblack только пускать лучи трассировки

Так куча деталей не будет видно с одного ракурса. Значит нужно будет летать камерой по сцене +куча дублирования вершин+ продумывать траекторию. Зачем 3д редактору 300 000 вершин для сферы? Значит нужно будет делать оптимизатор количества вершин поверхности, делать меру точности аппроксимации поверхности, писать хитрый фильтр убирающий вершины на одной плоскости…это адская работа =).

Как вариант:
Можно взять визуализацию неявных поверхностей Implicit surface.
Все сложные поверхности начальной сцены излучают некое поле электрического заряда, визуализируем это поле полученное одной из кучи формул одним из кучи методов.
Формул заряда если погуглить качественно вроде есть штук 15, например тут вроде только 4
http://paulbourke.net/geometry/implicitsurf/
В некоторых формулах что давно попадались можно настройками менять характер поля и финальной формы поверхности.

Есть также несколько методов визуализации Implicit surface, наверно самый известный шагающие кубы
https://ru.wikipedia.org/wiki/Marching_cubes
Мера точности аппроксимации это очевидно размер кубов+будет равномерность плотности аппроксимации треугольниками. Наверно есть куча готовых методов\софтов по оптимизации меша геометрии построенной как Implicit surface.

0

Сообщение от Excalibur921 Наверно лучше всего генерировать их красиво сразу(минимум граней в нужных местах и т.п). Тогда только экспорт. Будет скорость работы, точность поверхности, минимум полигонов что важно для 3д игр и вкусно редакторам...наверно только это оптимум. Другой метод будет муторный.

На данный момент считается что доступа к внутренностям 3D мира нет, а есть лишь возможность нативными методами запускать команду трассировки посредство скрипта, который, например, может общаться с внешним миров через базу данных.
У меня есть подозрения что можно залезть в живые кишки OpenGL / Direct3D и попытаться вытащить информацию о мешах оттуда, но тут есть много моментов от, собственно, как это сделать, до моментов типа "если это не видно то этого нет" и уменьшение детализации мешов с расстоянием.
Да, детализация при ручной трассировке может пострадать, но это допустимо.

Сообщение от Excalibur921 Так куча деталей не будет видно с одного ракурса

Как отрабатывает команда трассировки я точно не уверен, но человек который её использовал для других нужд в той же программе не говорил что моя затея не сработает.
Летать камерой не надо, трассировка, запускается самим движком программы, и, как я понял, может быть сделана в любом месте мира не зависимо от отрисовки мира камерой.
И я не собираюсь в 3D редактор передавать данные типа сферы из 300к точек. Думаю какой-нибудь готовый алгоритм уменьшения количества вершин меша задействовать. Хотя о самостоятельном написании алгоритма для кучи точек на одном треугольнике я тоже подумывал.

Implicit surface - я так понял это уже про генерацию меша по найденным точкам ?

0

Сообщение от wingblack что можно залезть в живые кишки OpenGL

Есть проги фоткают меш c текстурами с direct и gl приложения. Гуглить Opengl 3d rip.

Сообщение от wingblack а "если это не видно то этого нет"

Опция отключения отбрасывания невидимых поверхностей\кусков мира индивидуальна для каждого движка и на совести разработчика. Например в Сs 1.6 это можно офнуть.

Сообщение от wingblack Implicit surface - я так понял это уже про генерацию меша по найденным точкам ?

Ненужно искать никаких точек. Все поверхности мира задать аналитически а не треугольниками и построить Implicit surface.

Сообщение от wingblack готовый алгоритм уменьшения количества вершин

Наверняка есть в любом приличном 3д пакете. В 3d Studio max вроде называлось optimize.

0

Сообщение от Excalibur921 Ненужно искать никаких точек. Все поверхности мира задать аналитически а не треугольниками и построить Implicit surfac

Никак не подходит, программа с миром - чужая и нужно работать с тем что есть. И, если что, мир состоит из мешей.

Сообщение от Excalibur921 Наверняка есть в любом приличном 3д пакете. В 3d Studio max вроде называлось optimize.

ну чтобы не заваливать 3D редактор миллионами точек можно же сначала со своей стороны немного прибраться

Сообщение от Excalibur921 Гуглить Opengl 3d rip.

Оу, спасибо, потыкаю.

0

Решил усложнить себе жизнь и реализовать через трассировку лучей внутри программы.
Пока в качестве пробы работает следующий алгоритм:
пространство виртуально делится на кубы одинакового размера и рассматриваются центры кубов как узлы сетки.
процесс начинается из одного выбранного узла, выбираются соседние узлы, включая текущий и диагональные (3*3*3 узлов), из каждого узла строятся лучи трассировки параллельно осям в двух направлениях (2*3)
для каждого найденного удара лучом сохраняются координаты удара, ищется ближайший узел сетки, и если это первый удар возле него - аналогичным образом строятся новые лучи

Плюсом такого подхода считаю что в таком случае соседние точки будут примерно на одинаковом расстоянии R (шаг сетки) друг от друга и максимальное расстояние между точками не более 2R для соседей крест-накрест, и не более 2.5R (R*√6) для соседей по диагонали. И этот факт можно использовать для упрощения генерации треугольников.
Минусом в данной реализации вижу, скорее всего, излишние количество трассировок повторных или дающих очевидно одинаковый результат.

Далее идет задача построения треугольников.
Я пока не смог найти действительно подходящей реализации алгоритмов для моего случая.
Универсальные методы, типа Bowyer–Watson для случая 3D требуют чтобы треугольники были на одной плоскости. А триангуляция Делоне для 3D делает только тетраэдры.
Пока что в качестве тестирования использую триангуляция Делоне и выкидываю треугольники у которых длинна сторон больше чем требуется. Работает не очень быстро и результат не идеальный.

0

Как можно переделать подобный алгоритм обхода чтобы он не "перешагивал" через поверхность, а шел только с одной стороны ?

0