|
|
|
|
Канал Игры Мечты: «Алгоритмические вопросы.» |
|
|
|
БулерМэн
 420 EGP
  
Рейтинг канала: 2(21)
Репутация: 68
Сообщения: 1580
Откуда: Гороховец
Зарегистрирован: 07.02.2006
   |
|
Вопрос: по какому алгоритму рисуются трехмерные сетки состоящие из треугольников?
То есть допустим есть большой квадрат, который состоит из 64 квадратных ячеек, и соответственно 128 треугольников.
Как соединяются вершины, чтобы не было дыр?
Можно конечно сделать в максе нужный квадрат, с нужным количеством ячеек и просмотреть последовательность соединения точек - но это чрезвычайно долго...
|
|
|
|
Sh.Tac.
151 EGP
Рейтинг канала: 5(108)
Репутация: 14
Сообщения: 1426
Зарегистрирован: 27.07.2005
|
|
| БулерМэн : |
|
Вопрос: по какому алгоритму рисуются трехмерные сетки состоящие из треугольников?
|
насколько я в курсе есть два алгоритма закраски треугольников, half-spaces и scanlines, хотя придёт Jurec и скажет что это позапрошлый век и софтверной растеризацией уже никто не занимается 
_________________
This is what you get ...
(c) Radiohead |
|
|
|
БулерМэн
420 EGP
Рейтинг канала: 2(21)
Репутация: 68
Сообщения: 1580
Откуда: Гороховец
Зарегистрирован: 07.02.2006
|
|
| Sh.Tac. : |
|
закраски треугольников
|
Не, я не про растеризацию говорю, а про построение самой сетки.
Дело в том, что любой 3d-редактор умеет сохранять полигональный объект, в том числе "plane" состоящий из нескольких десятков треугольников, соединенных между собой определенным образом так, что плоскости, образуемые тремя точками никогда не образуют "дыр" и "перехлестов" линий соединения точек или вершин.
В OpenGL, как мне помнится, отрисовка геометрии треугольниками приводила к тому же эффекту: объект созданный вручную по точкам обязательно в каком-либо месте образовывал плоскость не там где надо и получалось месево.
Проблемы нет создать готовый "plane" с нужными точками в правильных координатах. Проблема есть в обновлении координаты Y каждой точки "на лету", а для этого хотелось бы разобраться в алгоритме построения фигур состоящих из треугольных плоскостей, "triangles".
Пробовал сравнить алгоритм построения plane'а из 8-ми треугольников и из 18-ти треугольников через разбор координат точек и связей из готовой геометрии (плоскость 2x2 квадрата или 8 треугольников и плоскость 3x3 квадрата или 18 треугольников).
Понятнее не стало: два совершенно разных алгоритма соединения вершин.
Последний раз редактировалось: БулерМэн (18:12 01-01-2016), всего редактировалось 1 раз |
|
|
|
Криптон
 995 EGP
   
Рейтинг канала: 3(44)
Репутация: 164
Сообщения: 2665
Откуда: Москва
Зарегистрирован: 05.04.2008
|
|
| БулерМэн : |
|
Как соединяются вершины, чтобы не было дыр?
|
Когда-то я решал похожую задачу. На вход подавалось N точек (число произвольное, но тестировалось на относительно небольшом количестве - несколько десятков). У точек были координаты x,y и результат измерения некой величины в этой точке. Также на вход подавалась форма поверхности, на которую надо спроецировать точки (были реализованы плоскость и полусфера), и набор базовых точек, ограничивающих фигуру. В итоге нужно было соорудить градиентный переход от одной точки с результатами измерения к другой.
(не уверен, что получилось понятно изложить...)
Реализовано это всё было именно через постройку нужного набора треугольников. Есть исходники и исполняемый файл.
|
Пример результатов работы программы (кликните здесь для просмотра)
|
если это близко к тому, что тебе надо получить, могу предоставить исходники. И могу составить описание алгоритма (я там уже многое подзабыл, надо в коде покопаться, чтобы вспомнить)
добавлено спустя 1 минуту:
Реализовано было на Delphi + OpenGL
добавлено спустя 7 минут:
24 исходные точки с измерениями, 36 точек, ограничивающих полусферу. Промежуточные точки вычислены автоматически.
добавлено спустя 1 минуту:
В дело, кстати, алгоритм так и не пошёл.
Последний раз редактировалось: Криптон (18:19 01-01-2016), всего редактировалось 3 раз(а) |
|
|
|
БулерМэн
420 EGP
Рейтинг канала: 2(21)
Репутация: 68
Сообщения: 1580
Откуда: Гороховец
Зарегистрирован: 07.02.2006
|
|
| Криптон : |
|
если это близко к тому, что тебе надо получить, могу предоставить исходники.
|
Хм. А твои треугольники имеют постоянное расположение, то есть единожды запрограммированы или все таки динамически изменяются в зависимости от значений поданных на вход программы? Рисунок сетки меняется?
добавлено спустя 2 минуты:
| Криптон : |
|
24 исходные точки с измерениями, 36 точек, ограничивающих полусферу.
|
36 точек построены по алгоритму или взяты из болвана полученного в 3d-редакторе?
Последний раз редактировалось: БулерМэн (18:24 01-01-2016), всего редактировалось 3 раз(а) |
|
|
|
Криптон
995 EGP
Рейтинг канала: 3(44)
Репутация: 164
Сообщения: 2665
Откуда: Москва
Зарегистрирован: 05.04.2008
|
|
| БулерМэн : |
|
А твои треугольники имеют постоянное расположение, то есть единожды запрограммированы или все таки динамически изменяются в зависимости от значений поданных на вход программы? Рисунок сетки меняется?
|
Одному и тому же набору входных данных всегда соответствует один набор треугольников. Если входные данные меняются, то и набор треугольников меняется.
|
картинка с двумя другими наборами данных (случайно сгенерированными) (кликните здесь для просмотра)
|
Причём координаты x,y "опорных" точек оставались постоянными (эти точки довольно чётко видно). Менялось только значение "измеряемой величины". Но если координаты x,y меняются, то алгоритм это тоже переваривает, но картинка слегка странная получается
|
20 опорных точек со случайными координатами (кликните здесь для просмотра)
|
добавлено спустя 3 минуты:
| БулерМэн : |
|
36 точек построены по алгоритму или взяты из болвана полученного в 3d-редакторе?
|
Эти точки - просто окружность на плоскости. Вычисляются по элементарнейшему алгоритму. То есть они не формируют полусферу, они формируют ту линию, где полусфера заканчивается.
добавлено спустя 38 секунд:
Реализации проекции на произвольную поверхность, заданную точками, не было, если ты об этом спрашиваешь.
Последний раз редактировалось: Криптон (18:36 01-01-2016), всего редактировалось 3 раз(а) |
|
|
|
БулерМэн
420 EGP
Рейтинг канала: 2(21)
Репутация: 68
Сообщения: 1580
Откуда: Гороховец
Зарегистрирован: 07.02.2006
|
|
| Криптон : |
|
Эти точки - просто окружность на плоскости. Вычисляются по элементарнейшему алгоритму. То есть они не формируют полусферу, они формируют ту линию, где полусфера заканчивается.
|
То есть в итоге получается нечто вроде такого на виде сверху, так?
|
Cкрытый текст (кликните здесь для просмотра)
|
| Криптон : |
|
Реализации проекции на произвольную поверхность, заданную точками, не было, если ты об этом спрашиваешь.
|
Нужен алгоритм, который соединяет точки в сплошную плоскость.
Если допустить, что у меня фигура состоит из 6-ти точек - то логично было бы ее разделить на прямоугольники. А прямоугольники на треугольники. Но потом возникает проблема - в какой последовательности соединять уже существующие точки, чтобы получилась сплошная поверхность.
Пример:
|
Cкрытый текст (кликните здесь для просмотра)
|
Почему я пытаюсь окучить этот простейший квадрат: движок игры умеет рисовать готовую 3d-плоскость полученную из файла.
Но редактировать отдельные точки загруженной плоскости - я не могу и движок это не позволяет.
Однако, я могу рисовать сами вершины и указывать, какие три или четыре вершины будут являться плоскостью, и так до тех пор пока сетка не будет отрисована целиком.
Почему вопрос в данной теме: я пытаюсь отрисовку данной плоскости (с большим числом треугольников) записать в алгоритм, который позволял бы изменять координаты отдельных точек.
"Реинжиниринг" готовой плоскости я могу сделать, но подумалось, что кто-то уже делал такое или знает по какому алгоритму соединяются эти самые вершины в плоскость
| Криптон : |
если ты об этом спрашиваешь.
|
То есть твой алгоритм создает в существующей сетке из точек один треугольник, потом делит его еще на несколько треугольников и так далее?
добавлено спустя 5 минут:
ЗЫ Хотя судя по тому, что от точек на ребрах идут следующие ребра - не все так просто...
Последний раз редактировалось: БулерМэн (20:54 01-01-2016), всего редактировалось 2 раз(а) |
|
|
|
Криптон
995 EGP
Рейтинг канала: 3(44)
Репутация: 164
Сообщения: 2665
Откуда: Москва
Зарегистрирован: 05.04.2008
|
|
| БулерМэн : |
|
То есть в итоге получается нечто вроде такого на виде сверху, так?
|
Почти.
|
Проекция на плоскость вместо полусферы. Красные вершины - 36 ограничивающих, зелёные - 24 с ''данными''. Без построения дополнительных треугольников. (кликните здесь для просмотра)
|
|
Алгоритм может работать и с другими точками. Например, четыре граничных, четыре с данными, проекция на плоскость. Без построения дополнительных треугольников. (кликните здесь для просмотра)
|
| БулерМэн : |
|
Нужен алгоритм, который соединяет точки в сплошную плоскость.
|
Покопался таки в своём коде, вот примерный алгоритм:
0. (следует помнить, что алгоритм двумерный - оперирует точками на плоскости).
1. Все точки (и "граничные", и "с данными") добавляются в общий список.
2. Создаётся список возможных рёбер (то есть пары точек, каждая с каждой).
3. Возможные рёбра отсортировываются по длине.
4. Выкидываются лишние рёбра. Лишними считаются совпадающие и пересекающиеся. Из пересекающихся выкидывается то, что длиннее. Помню, что изрядно намучился, прежде чем удалось заставить это работать.
5. Строятся дополнительные треугольники - для образования градиентного перехода цветов через все нужные ступени. (Тебе, полагаю, этот пункт не нужен). (Кстати, только что обнаружил баг в реализации этого пункта - иногда делает лишние треугольники).
6. Делается проекция на нужную поверхность (например, полусферу) (то есть, подсчитывается координата Z).
7. Формируются списки треугольников (блоков по три соседние точки) для передачи в OpenGL.
8. Готовые треугольники используются для отрисовки сцены.
При большом количестве исходных точек алгоритм может быть весьма ресурсозатратен - потому что сначала строятся все возможные рёбра, а потом выкидываются лишние.
добавлено спустя 1 минуту:
Описание файла не влезло.
Дублирую:
Экзешник. Делался как демонстратор возможностей, а не конечный продукт. Простейший способ использования: на первой вкладке ткнуть "Сгенерировать точки", на второй вкладке ткнуть "Сгенерировать точки", на третьей ткнуть "Сгенерировать цвета", ткнуть кнопку "Показать" внизу окна. Все таблицы можно редактировать с клавиатуры. В 3D-окне картинку можно крутить левой и средней кнопками мыши.
добавлено спустя 4 минуты:
Исходники не хочу выкладывать в открытый доступ. Если нужны, вышлю в личку.
| prColors.zip |
| Описание: |
| Экзешник. Делался как демонстратор возможностей, а не конечный продукт. Простейший способ использования: на первой вкладке ткнуть "Сгенерировать точки", на второй вкладке ткнуть "Сгенерировать точки", на третьей ткнуть "Сгенериров |
|
| Имя файла: |
prColors.zip |
| Размер файла: |
726.63 KB |
| Скачано: |
433 раз(а) |
Последний раз редактировалось: Криптон (22:15 01-01-2016), всего редактировалось 2 раз(а) |
|
|
|
БулерМэн
420 EGP
Рейтинг канала: 2(21)
Репутация: 68
Сообщения: 1580
Откуда: Гороховец
Зарегистрирован: 07.02.2006
|
|
| Криптон : |
|
7. Формируются списки треугольников (блоков по три соседние точки) для передачи в OpenGL.
|
Вот этот пункт интересен - как ты определяешь какие точки являются соседними? Если можно этот блок кода вышли, если конечно он не завязан на весь проект.
Если невозможно вычленить только эту операцию - кидай весь проект, дельфи есть, посмотрю.
Кстати, для твоей программы неплохо было бы сделать TurboSmooth А то геометрия полусферы в итоге кривая.
добавлено спустя 7 минут:
ЗЫ Вполне возможно, что для твоей задачи подошло бы автосглаживание по принципу наименьшей удаленности между соседними точками. Но тогда придется научить программу строить не лоуполи-сетку, а полноценную с максимально равным шагом ячеек.
Программа создает равномерную сетку с шагом равным минимальному расстоянию между соседними точками. В случае полусферы - было бы наверное проще сдвинуть наиболее близкую вершину в новой сетке к целевой, изменив ей Z в соответствии с координатами X,Y.
В идеале получится сфера.
Только для чего это все я так и не понял
Последний раз редактировалось: БулерМэн (01:59 02-01-2016), всего редактировалось 1 раз |
|
|
|
Криптон
995 EGP
Рейтинг канала: 3(44)
Репутация: 164
Сообщения: 2665
Откуда: Москва
Зарегистрирован: 05.04.2008
|
|
| БулерМэн : |
|
Только для чего это все я так и не понял
|
Предполагалось использовать для визуализации показаний акселерометров, размещённых на куполе ледового дворца. Но не сложилось.
Писалось это два года назад. Задача давно уже не актуальна, что-либо улучшать в программе нет смысла.
Ссылку на исходники сейчас отправлю в личку.
|
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Не понял что именно нужно описать. Как из 3д (3д модель из макса/майи) всё попадает на экран в 2д (экран)?
Или как растеризация треугольника происходит?
Или в как делать индекс буфер?
Объясни плиз
добавлено спустя 41 секунду:
| Sh.Tac. : |
насколько я в курсе есть два алгоритма закраски треугольников, half-spaces и scanlines, хотя придёт Jurec и скажет что это позапрошлый век и софтверной растеризацией уже никто не занимается
|
Занимаются. Даже в баттлфилде есть софт растеризатор для occlusion culling'a
_________________
MOV topka, C++
Последний раз редактировалось: Jurec (22:18 02-01-2016), всего редактировалось 1 раз |
|
|
|
БулерМэн
420 EGP
Рейтинг канала: 2(21)
Репутация: 68
Сообщения: 1580
Откуда: Гороховец
Зарегистрирован: 07.02.2006
|
|
| Jurec : |
|
Не понял что именно нужно описать.
|
Процесс соединения triangle_strip в плоскость с заданными размерами. Плоскость имеет свойство изменять свою геометрию, то есть координата Z каждой точки может быть изменена в любой момент времени.
|
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Порядок соединения интересует? При изменении только z - не вижу смысла его менять. Разово подготавливаешь индекс буфер и всё.
Еще конкретнее надо
_________________
MOV topka, C++ |
|
|
|
Криптон
995 EGP
Рейтинг канала: 3(44)
Репутация: 164
Сообщения: 2665
Откуда: Москва
Зарегистрирован: 05.04.2008
|
|
О, я и не знал, что такой есть 
Да, он должен, по идее, решить проблему.
|
|
|
|
Sh.Tac.
151 EGP
Рейтинг канала: 5(108)
Репутация: 14
Сообщения: 1426
Зарегистрирован: 27.07.2005
|
|
| Jurec : |
|
Еще конкретнее надо
|
мне кажется БулерМэн и буфер вершин не хочет менять, но хочет менять у вершин высоту, типа для волн
_________________
This is what you get ...
(c) Radiohead |
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
| Sh.Tac. : |
мне кажется БулерМэн и буфер вершин не хочет менять, но хочет менять у вершин высоту, типа для волн
|
Можно рисовать просто сетку с одинаковой высотой (плоский меш), а в вершинном шейдере читать высоту из текстуры и сдвигать вершину
_________________
MOV topka, C++ |
|
|
|
Diff
708 EGP
   
Рейтинг канала: 2(11)
Репутация: 44
Сообщения: 4179
Откуда: Сферическая Земля в вакууме.
Зарегистрирован: 04.07.2003
|
|
Во, и сюда запощу.
http://www.elite-games.ru/conference/viewtopic.php?p=3407877#3407877
_________________
Конец света в конце тоннеля |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Алгоритмические вопросы.» |
|
|
