Виртуальная триангуляция

@Igor3D · Регистрация: 01.10.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте

Есть 3D модель(и) состоящая (для простоты) только из треугольников. Есть значения освещенности в каждом из 3 вертексов каждого тр-ка. На рендере в каждой точке поверхности освещенность рассчитывается интерполяцией значений в вертексах. Когда тр-ки "достаточно малы" - все хорошо, но вот когда велики - плохо. Очевидное решение "давайте разобьем все большие тр-ки на достаточно мелкие" ведет к быстрому исчерпанию ресурсов. Нужно создавать новые вертексы, а они имеют кучу всего (до десятка атрибутов).

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

Псевдокод интерполяции для тр-ка

C++
1
2
3
4
Color Interpolate( const Vertex * ver[3], double alpha, double beta )
{
 return ver[0]->color * (1 - alpga - beta) + ver[1]->color * alpha + ver[2]->color * beta;
}

С уважением
Игорь

@Massaraksh7 · 24.09.2017, 16:11

Не совсем понятно - не проводить триангуляцию, но проводить триангуляцию. Чем одна триангуляция от другой (виртуальной) должна отличаться? Сформулируйте почётче.

@Excalibur921 · 24.09.2017, 16:45

Наверно это методы пространственной интерполяции.
Учитывать N вершин в неком радиусе от точки поверхности + нелинейная функция веса каждой от расстояния. Может играть с формой этой функции задать ее некой редактируемой кривой и смотреть на результаты. Этих методов наверно целая куча в геодезии и в них черт ногу сломит.
https://desktop.arcgis.com/ru/... -works.htm

@Igor3D · 25.09.2017, 07:26 **[ТС]**

Сообщение от Massaraksh7

Не совсем понятно - не проводить триангуляцию, но проводить триангуляцию. Чем одна триангуляция от другой (виртуальной) должна отличаться? Сформулируйте почётче.

В 2 словах - (гораздо) меньшим объемом данных. Пример:

- обычная триангуляция, напр есть тр-к, рекурсивно разбиваем его на 2 новых. В точке разбиения создаем новый вертекс. Он имеет позицию (3 double), нормаль (3 float) + ....+ (еще много чего) + наконец сама освещенность (8 байт). Ну и сами новые тр-ки (индексы) тоже надо хранить. Все работает, но зачем мы храним кучу всего если на шейдинге нужна только освещенность? Но "просто так" мы не можем хранить только ее - ведь нужны позиция и нормаль чтобы ее посчитать.

Это часто называют "baking" (запекание)

@woldemas · 25.09.2017, 07:30

Сообщение от Igor3D

Нужно построить такую структуру данных которая бы обеспечивала интерполяцию освещенности с заданным (достаточно малым) шагом.

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

@Igor3D · 25.09.2017, 08:28 **[ТС]**

Сообщение от woldemas

Или необходимо передавать методу интерполяции какую-то функцию которая нелинейно вычисляет освещенность в точке (например вычисляющую нормаль поверхности и по ней уже освещенность).

Виртуально или нет - в любом случае создаются новые вертексы в которых считается освещенность. На момент расчета надо иметь позицию и нормаль. Вычисленные освещенности используются на этапе интерполяции, для этого нужно знать в какой из тр-ков попала текущая точка. Для обычной триангуляции рендер сразу дает коэффициенты alpha и beta, для виртуальной их надо пересчитать

@woldemas · 25.09.2017, 08:59

Igor3D, А почему нельзя интерполировать по эти коэффициентам (alpha и betta) саму позицию и/или нормаль и вычислять уже по ним освещенность в точке?

@Igor3D · 25.09.2017, 09:21 **[ТС]**

Сообщение от woldemas

Igor3D, А почему нельзя интерполировать по эти коэффициентам (alpha и betta) саму позицию и/или нормаль и вычислять уже по ним освещенность в точке?

Расчет дорогой, поэтому и затевается вся песня с запеканием

Не по теме:

Ну вот, хоть до одного что-то дошло - уже хорошо :) Задача трудная (не для нерадивых студентов)

@woldemas · 25.09.2017, 09:29

Igor3D, то есть задачу можно сформулировать так: для каждого треугольника хранить набор заранее вычисленных в некоторых его точках значений освещенности, которые в дальнейшем использовать для интерполяции освещенности произвольной точки внутри этого треугольника? Я правильно понимаю?

@Igor3D · 25.09.2017, 11:32 **[ТС]**

Сообщение от woldemas

Igor3D, то есть задачу можно сформулировать так: для каждого треугольника хранить набор заранее вычисленных в некоторых его точках значений освещенности, которые в дальнейшем использовать для интерполяции освещенности произвольной точки внутри этого треугольника? Я правильно понимаю?

Да, верно. Ну конечно одними значениями освещенности не отделаться, неизбежны еще какие-то управляющие данные, но их должно быть минимум

@woldemas · 25.09.2017, 14:33

Igor3D, если доступны двумерные координаты вершин (параметры поверхности, текстурные координаты) я бы попытался просчитанные заранее данные (нормали, освещенности) записать в двумерный массив по типу текстуры, потом по alpha и betta получал двумерную текстурную координату и из массива доставал по этому адресу. На мой взгляд, это самое быстрое, что можно сделать.

@Igor3D · 25.09.2017, 15:05 **[ТС]**

Сообщение от woldemas

Igor3D, если доступны двумерные координаты вершин (параметры поверхности, текстурные координаты) я бы попытался просчитанные заранее данные (нормали, освещенности) записать в двумерный массив по типу текстуры, потом по alpha и betta получал двумерную текстурную координату и из массива доставал по этому адресу. На мой взгляд, это самое быстрое, что можно сделать.

Это "запекание в текстуру", там свои заморочки/проблемы. Простой пример виртуальной триангуляции:

- находим наибольшую сторону тр-ка и создаем новый вертекс на ее середине. Записываем:
1) индекс стороны (2 бита)
2) индекс созданного вертекса (4 байта)
3) саму освещенность (8 байт)
Итого всего 13 байт - неплохо. Имея эти данные (+ конечно исходный тр-к) мы можем восстановить как позицию и нормаль (для просчета освещенности), так и найти 2 новых тр-ка. Правда это всего одно разбиение, а их может потребоваться куда больше - неясно как организовать данные. Да и с alpha/beta надо что-то делать на интерполяции

Вот (примерно) такие вещи я хотел бы пообсуждать

@Massaraksh7 · 25.09.2017, 17:24

До конца всё равно не понял.
Допустим, у нас есть "большой" треугольник, и значения освещённости в каждой его вершине. Понятно, что он в 3-хмерном пространстве, но разбивать его мы будем всё равно ведь в его плоскости?
Нам надо разбить его так, чтобы мы получили значения освещённости в промежуточных точках, правильно?
Почему нельзя это сделать "на лету"? Там линейная функция, никаких сложных вычислений. Или даже эти простые вычисления будут тормозить?
Если всё же требуется создать массив значений, посчитанных заранее, то почему бы не сделать это "по сетке"? Это будет равномерней.
Если так уж нужны именно треугольники, то можно после этого провести триангуляцию Делоне (хотя, это может быть неприемлемо долго).

@Igor3D · 26.09.2017, 08:19 **[ТС]**

Сообщение от Massaraksh7

Понятно, что он в 3-хмерном пространстве, но разбивать его мы будем всё равно ведь в его плоскости?

Можно и на плоскости, можно и в пр-ве, здесь это роли не играет. Просто (x, y, z) вместо (x, y)

Сообщение от Massaraksh7

Нам надо разбить его так, чтобы мы получили значения освещённости в промежуточных точках, правильно?

Да

Сообщение от Massaraksh7

Почему нельзя это сделать "на лету"? Там линейная функция, никаких сложных вычислений. Или даже эти простые вычисления будут тормозить?

На каком "лету"? Рендер дает точку на поверхности исходного тр-ка, откуда взять промежуточные точки для оценки освещенности? Считать их снова и снова? Это будет сутки, (если не недели)

Сообщение от Massaraksh7

то почему бы не сделать это "по сетке"? Это будет равномерней.

Есть такой вариант, но уж очень корявенький
- Точка попадает в квадрат сетки, есть 4 угла, одни внутри исходного тр-ка, другие снаружи (освещенность в них вообще неизвестна). Ваши действия?
- Интерполировать по 4 далеко не так приятно как по 3.
- Размер массива промежуточных точек по меньшей мере вдвое больше используемого
- И, может самое главное, нет расширяемости, "constrain" не воткнуть.

Сообщение от Massaraksh7

то можно после этого провести триангуляцию Делоне

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

Не по теме:

Сообщение от Massaraksh7

Если всё же ..
Если так уж..

Не надо мне делать одолжений - я об этом не просил :)

@Massaraksh7 · 26.09.2017, 15:21

- Точка попадает в квадрат сетки, есть 4 угла, одни внутри исходного тр-ка, другие снаружи (освещенность в них вообще неизвестна). Ваши действия?
- Интерполировать по 4 далеко не так приятно как по 3.
- Размер массива промежуточных точек по меньшей мере вдвое больше используемого
- И, может самое главное, нет расширяемости, "constrain" не воткнуть.

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

@Massaraksh7 · 26.09.2017, 15:29

Есть ещё такие варианты (один из них вы сами предложили) , но по сетке, мне кажется, лучше.

@Massaraksh7 · 26.09.2017, 15:36

Хотя, возможно, я чего-то и не понял из ваших объяснений. Тогда разъясните.

Сообщение от Igor3D

На каком "лету"? Рендер дает точку на поверхности исходного тр-ка, откуда взять промежуточные точки для оценки освещенности?

А в углах этого треугольника разве не значения освещённости?

@Igor3D · 27.09.2017, 09:27 **[ТС]**

Сообщение от Massaraksh7

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

А тогда как хранить оставшиеся и как по ним интерполировать?

Не по теме:

Т.к. читают последний пост, повторю Вашу картинку

@Igor3D · 27.09.2017, 09:33 **[ТС]**

Сообщение от Massaraksh7

Есть ещё такие варианты

С самой триангуляцией проблем нет - напр устроит примитивное разбиение большей стороны пополам, можно придумать что-то и получше

Вопрос (проблема, тема) в другом - как это хранить и использовать? Напр рендер знает/видит только исходный (регулярный) тр-к, как найти в какой из созданных (виртуальных) мы попали?

@woldemas · 27.09.2017, 12:41

Сообщение от Igor3D

как найти в какой из созданных (виртуальных) мы попали?

Перебором всех и плоской проверкой принадлежности точки треугольнику используя ее барицентрические координаты альфа и бета, что весьма долго.
Единственный способ - строить триангуляцию так, чтобы по альфа и бета легко находился треугольник которому принадлежит точка (что-то вроде аналог разбиения по осям на плоскости), но что-то я не соображу как это в барицентрических координатах будет выглядеть. Наверное, разбивать отрезками параллельными сторонам треугольника как на одном из рисунков выше.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Massaraksh7 Айлурофил 514 / 447 / 112 Регистрация: 27.05.2017 Сообщений: 2,688 Записей в блоге: 5
	24.09.2017, 16:11
	Не совсем понятно - не проводить триангуляцию, но проводить триангуляцию. Чем одна триангуляция от другой (виртуальной) должна отличаться? Сформулируйте почётче. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	24.09.2017, 16:45
	Наверно это методы пространственной интерполяции. Учитывать N вершин в неком радиусе от точки поверхности + нелинейная функция веса каждой от расстояния. Может играть с формой этой функции задать ее некой редактируемой кривой и смотреть на результаты. Этих методов наверно целая куча в геодезии и в них черт ногу сломит. https://desktop.arcgis.com/ru/... -works.htm 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	25.09.2017, 08:59
	Igor3D, А почему нельзя интерполировать по эти коэффициентам (alpha и betta) саму позицию и/или нормаль и вычислять уже по ним освещенность в точке? 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	25.09.2017, 09:29
	Igor3D, то есть задачу можно сформулировать так: для каждого треугольника хранить набор заранее вычисленных в некоторых его точках значений освещенности, которые в дальнейшем использовать для интерполяции освещенности произвольной точки внутри этого треугольника? Я правильно понимаю? 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	25.09.2017, 14:33
	Igor3D, если доступны двумерные координаты вершин (параметры поверхности, текстурные координаты) я бы попытался просчитанные заранее данные (нормали, освещенности) записать в двумерный массив по типу текстуры, потом по alpha и betta получал двумерную текстурную координату и из массива доставал по этому адресу. На мой взгляд, это самое быстрое, что можно сделать. 0

@Massaraksh7 Айлурофил 514 / 447 / 112 Регистрация: 27.05.2017 Сообщений: 2,688 Записей в блоге: 5
	25.09.2017, 17:24
	До конца всё равно не понял. Допустим, у нас есть "большой" треугольник, и значения освещённости в каждой его вершине. Понятно, что он в 3-хмерном пространстве, но разбивать его мы будем всё равно ведь в его плоскости? Нам надо разбить его так, чтобы мы получили значения освещённости в промежуточных точках, правильно? Почему нельзя это сделать "на лету"? Там линейная функция, никаких сложных вычислений. Или даже эти простые вычисления будут тормозить? Если всё же требуется создать массив значений, посчитанных заранее, то почему бы не сделать это "по сетке"? Это будет равномерней. Если так уж нужны именно треугольники, то можно после этого провести триангуляцию Делоне (хотя, это может быть неприемлемо долго). Миниатюры 0

@Massaraksh7 Айлурофил 514 / 447 / 112 Регистрация: 27.05.2017 Сообщений: 2,688 Записей в блоге: 5
	26.09.2017, 15:29
	Есть ещё такие варианты (один из них вы сами предложили) , но по сетке, мне кажется, лучше. Миниатюры 0