Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 994
1

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

24.05.2018, 18:29. Просмотров 472. Ответов 6
Метки нет (Все метки)

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

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


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

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


Есть еще проблема подбора алгоритма формирования меша по точкам, но пока не буду тут его поднимать - задача вроде бы "типовая" и готовые реализации данного алгоритма, думаю, я смогу найти сам.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.05.2018, 18:29
Ответы с готовыми решениями:

Какая прога нужна для создания 3D модели машины?
Добрый день! Очень бы хотелось узнать какая программа нужна для создания 3D автомобиля? Я слышал...

Программки для создания 3D модели дома и рассчета кол-ва материалов
Ребята подскажите программки в которым можно создать 3d модель дома и произвести расчет, сколько...

Выбор стратегии работы с БД
Доброго времени суток! Подскажите пожалуйста какую стратегию применить при разработке простой...

Выбор в таблице данных модели ссылки на экземпляр связанной модели
Есть ли какой-то автоматизированный способ вывести на страницу таблицу с записями модели, одно из...

6
1026 / 658 / 109
Регистрация: 12.10.2013
Сообщений: 4,275
25.05.2018, 10:30 2
Цитата Сообщение от 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
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 994
25.05.2018, 12:08  [ТС] 3
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Наверно лучше всего генерировать их красиво сразу(минимум граней в нужных местах и т.п). Тогда только экспорт. Будет скорость работы, точность поверхности, минимум полигонов что важно для 3д игр и вкусно редакторам...наверно только это оптимум. Другой метод будет муторный.
На данный момент считается что доступа к внутренностям 3D мира нет, а есть лишь возможность нативными методами запускать команду трассировки посредство скрипта, который, например, может общаться с внешним миров через базу данных.
У меня есть подозрения что можно залезть в живые кишки OpenGL / Direct3D и попытаться вытащить информацию о мешах оттуда, но тут есть много моментов от, собственно, как это сделать, до моментов типа "если это не видно то этого нет" и уменьшение детализации мешов с расстоянием.
Да, детализация при ручной трассировке может пострадать, но это допустимо.

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

Implicit surface - я так понял это уже про генерацию меша по найденным точкам ?
0
1026 / 658 / 109
Регистрация: 12.10.2013
Сообщений: 4,275
25.05.2018, 15:27 4
Цитата Сообщение от wingblack Посмотреть сообщение
что можно залезть в живые кишки OpenGL
Есть проги фоткают меш c текстурами с direct и gl приложения. Гуглить Opengl 3d rip.
Цитата Сообщение от wingblack Посмотреть сообщение
а "если это не видно то этого нет"
Опция отключения отбрасывания невидимых поверхностей\кусков мира индивидуальна для каждого движка и на совести разработчика. Например в Сs 1.6 это можно офнуть.
Цитата Сообщение от wingblack Посмотреть сообщение
Implicit surface - я так понял это уже про генерацию меша по найденным точкам ?
Ненужно искать никаких точек. Все поверхности мира задать аналитически а не треугольниками и построить Implicit surface.
Цитата Сообщение от wingblack Посмотреть сообщение
готовый алгоритм уменьшения количества вершин
Наверняка есть в любом приличном 3д пакете. В 3d Studio max вроде называлось optimize.
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 994
25.05.2018, 18:29  [ТС] 5
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Ненужно искать никаких точек. Все поверхности мира задать аналитически а не треугольниками и построить Implicit surfac
Никак не подходит, программа с миром - чужая и нужно работать с тем что есть. И, если что, мир состоит из мешей.
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Наверняка есть в любом приличном 3д пакете. В 3d Studio max вроде называлось optimize.
ну чтобы не заваливать 3D редактор миллионами точек можно же сначала со своей стороны немного прибраться
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Гуглить Opengl 3d rip.
Оу, спасибо, потыкаю.
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 994
15.07.2018, 16:09  [ТС] 6
Решил усложнить себе жизнь и реализовать через трассировку лучей внутри программы.
Пока в качестве пробы работает следующий алгоритм:
пространство виртуально делится на кубы одинакового размера и рассматриваются центры кубов как узлы сетки.
процесс начинается из одного выбранного узла, выбираются соседние узлы, включая текущий и диагональные (3*3*3 узлов), из каждого узла строятся лучи трассировки параллельно осям в двух направлениях (2*3)
для каждого найденного удара лучом сохраняются координаты удара, ищется ближайший узел сетки, и если это первый удар возле него - аналогичным образом строятся новые лучи

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

Далее идет задача построения треугольников.
Я пока не смог найти действительно подходящей реализации алгоритмов для моего случая.
Универсальные методы, типа Bowyer–Watson для случая 3D требуют чтобы треугольники были на одной плоскости. А триангуляция Делоне для 3D делает только тетраэдры.
Пока что в качестве тестирования использую триангуляция Делоне и выкидываю треугольники у которых длинна сторон больше чем требуется. Работает не очень быстро и результат не идеальный.
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 994
17.07.2018, 22:30  [ТС] 7
Как можно переделать подобный алгоритм обхода чтобы он не "перешагивал" через поверхность, а шел только с одной стороны ?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.07.2018, 22:30

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Выбор стратегии продвижения нового сайта
Приступаю к продвижению нового сайта, причем частота ключевиков варьируется от 10 до 61 609...Время...

Многопоточность и вычисления: выбор оптимальной стратегии
Есть некоторый массив float acc Нужно произвести модификацию элементов этого массива, путём...

УТ: Выбор стратегии списания товаров пользователем
Коллеги, подскажите пожалуйста, как лучше реализовать в УТ возможность при реализации товаров дать...

Выбор формата модели для Unity
Я занимаюсь Unity, не знаю какой формат модели лучше(OBJ, FBX, Collada или посоветуйте свой)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.