nyaload

Журнал Пушыстого

Журнал Пушыстого

Entries by tag: geom-prog

Квадратные дырки треугольным сверлом
nyaload
_winnie
ТРЕУГОЛЬНЫМ сверлом можно сверлить КВАДРАТНЫЕ дырки:



На этом видео настоящее сверло, а не 3d-графика:



( via aruslan )

Старые студенческие работы.
nyaload
_winnie
У меня есть какие-то старые студенческие поделки про компьютерную графику, выкладываю что бы не потерялось и показать :)

Например, Часы Зла. Можно вращать, можно правой кнопкой мыши щелкать по глазам и бубену.
Скачать (1 мегабайт).

Ещё всякое такое можно посмотреть на http://dobrokot.ru/opengl-demos/

упаковка float 01 <-> byte
nyaload
_winnie
Часто значения float из промежутка [0, 1] хранят в виде байта или в двух байтах, для экономии места.

Когда незадумчивые программисты пишут код конвертации float2byte и byte2float, возникают следующие ошибки:

1) float2byte( byte2float (X) ) != X
2) float2byte( 1.0 ) отображается в 256, то есть в байт 0.
3) float2byte( byte2float (X) + небольшой шум ) != X
4) часто важно что бы byte2float(255) == 1.0 и byte2float(0) == 0.0
5) множества float соответствующие значению байта - имеют разный размер. Напр. 0 и 255 отображаются в промежутки длины 1/510, а 1,2,..254 - в промежутки 1/255

1,2 - тупо багло. 3,4,5 - важны, но иногда можно пожертвовать, например часто забивают на 5 без особых проблем, или даже с пользой если есть выход за пределы [0..1] в промежуточных вычислениях.

Формулы которые пишут незадумчиво с налёту - это обычно {b=int(f*255.0), f=b/255.0}, {b=min(int(f*256.0),255), f=b/256.0} и тп.

Получают небольшие изменения яркости при каждом save/load, странные шумы, превращение 255 в 254, белый цвет умноженый на белый - даёт не белый, и тп.

Что бы избежать этих ошибок, надо представлять себе такую картинку: делим отрезок [0..1] на 256 равных отрезков (полуоткрытых интервалов). Байты должны превращаться в серединки или другие внутренности этих отрезков, а эти отрезки - в байты, взаимно однозначно. Вариант: промежутки для 1,2,..254 одинаковые, а для 0 и 255 - в два раза меньше.

Примеры устойчивых упаковок:

byte2float:
   f = (b/255.0f - чуть меньше устойчиво к шуму, max-шума=1/(255*256). Зато 0 и 255 превращаются в 0.0f и 1.0f.
   или f = (b + 0.5f)/256.0f - устойчиво к шуму, max-шума=1/(2*256), но 255 отображается в 511.0/512.0 а не в 1.0. Белый цвет умноженый на белый много раз станет серым.

float2byte:
   b = min( int(f*256), 255 )
   или b = int(f*255.9999f)

И ещё вариант, классический, спасибо zeux за его комментарий (рекомендую, если сомневаетесь что выбрать):

byte2float:
   f = b/255.0f
float2byte:
   b = int(f*255 + 0.5)
Хорош всем, только интервалы для 0 и 255 в два раза меньше чем для 1,2,..,254.



Увы, многие библиотеки об этом не задумываются. Если у вас есть многократный save load с преобразованием float/byte, сделайте code review в этом месте. Это могут быть упакованые анимации, heighmap ландшафтов, очевидно текстуры, веса костей для скелетной анимации, всякие веса смешиваний и долей. В базах данных тоже любят оптимизировать такие float.

Read more...Collapse )

проверка пересечения: сведение к меньшим размерностям
nyaload
_winnie
Для объектов A и B со связной границей утверждение "А пересекается с B" эквивалентно "границы А и B пересекаются || A вложен в B || B вложен в А"

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

А и B должны быть со связной границей ( это ограничение самое важное при прикладном применении ). А так же замкнутыми, непустыми, и должны существовать точки вне A и B ( A|B не должно покрывать целиком всё пространство ).

Для полосок на торе, шайб-колец в 2d, отрезков на одномерной прямой, утверждение не сработает, так как их граница не связна.
Условие что есть точки вне A и B тоже необходимо, иначе можно привести антипример A={(x,y)|x2+y2 <= 2}, B={(x,y)|x2+y2 >= 1} или арбуз упакованный в два презерватива.

Кстати, теорему придумал сам, но наверное тоже баян, так как учебников по топологии не читал.

operator*(const float3 &, const float3 &)
nyaload
_winnie
overloaded операция '*' для векторов a,b должна делать покомпонентное умножение, (a.x*b.x, a.y*b.y, a.z*b.z). Ибо вот.

Так сделано в шейдерных языках со встроенной математикой (HLSL в D3D, GLSL в OpenGL, ). Это удобно: часто хочется сделать что-то вроде
(a + float2(-1, 1)*b)
(a + float2(0, -1)*b)
(a + float2(screenWidth, screenHeight)*b)
light_color * surface_diffuse_color


Если сделали у вектора конструктор из float* - не забудьте сделать его explicit.
Не делайте у векторов неявного преобразования в float*. Сделайте явное, типа float* ptr(). Это не так часто нужно, что бы создавать грабли с неявными преобразованиями. Не потому что "так правильно", а потому что бьёт по лбу даже в домашних микропроектах.

Оператор нормализации вектора должен давать детерменированный результат на невалидном векторе нулевой длины. Например, (0,0,1) во всех конфигурациях. И ещё assert в debug. Не оставляете недетерменированный результат даже в release билде, намучаетесь с NaN в рендере, экспорте, физике, игровой логике и везде.

Прежде чем делать 1001-ю библиотеку для 2d/3d/4d математики - посмотрите на HLSL/GLSL, что бы быть ближе к классике.

Попадание точки в многоугольник. Количество заныриваний не равно количеству выныриваний.
nyaload
_winnie
Есть точка O, есть многоугольник A[n] на плоскости. Надо выяснить, попадает ли точка в многоугольник.

Основа алгоритма описывается очень просто: давайте возмём бесконечный горизонтальный луч из точки направо. Если луч пересекает границу четное число раз (в том числе 0 раз) , то точка вне многоугольника. Если нечетное число раз - то внутри.



Затем программист пытается обработать хитрые случаи: луч проходит через вершину многоугольника, сторона многоугольника совпадает с лучом. В коде возникают какие-то if, какие-то EPSILON..., молитвы о том, что редкие случаи когда две точки на расстоянии EPSILON но луч между ними - не существуют, насильно изгонясь из сознания Read more...Collapse )

Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Пересечение двух отрезков

Угол между двумя векторами:
nyaload
_winnie
Угол между векторами: atan2( length(cross(a, b)), dot(a,b) ). atan2 - из стандартной мат-библиотеки языка. cross - векторное произведение, dot - скалярное.
В двухмерном случае length(cross(a,b)) заменяется на axby - bxay, и угол считается проще, atan2(axby - bxay, axbx + ayby). Угол даже со знаком получается (против/по часовой стрелке).

А то часто заморачиваются с аркосинусами, получают сложный некрасивый код и падают при попытке взять аркосинус(1.0001235) после ошибок округления.

Очень часто угол вообще излишен, достаточно только косинуса угла ( dot(a, b) ), а угол считают зря. Напр. выражение для сравнения угла с константой:
angle(a, b) < 45°
можно записать как
cos(angle(a, b)) > cos(45°)
dot(a, b)/(length(a)*length(b)) > cos(45°)
dot(a, b)2 > 0.5*length2(a)*length2(b).
0.5 здесь взялся как cos2(45°). И ещё надо не забыть условие dot(a, b) > 0. length2 - это sqrt(x2+y2+z2)2, то есть (x2+y2+z2), без извлечения корня.

В результат код без делений, без квадратных корней, без тригонометрических функций, что может ускорить его в десятки раз. Если вектора единичные (заранее отнормировали), то вообще замечательно. Можно не ломать голову, как корректно возвести длину в квадрат.

PS. Если в коде +10% понятности значимей, чем ускорение в 20 раз, лучше писать по-человечески, как мыслишь. Только всё равно в функции angle замените аркосинусы на atan2. И проще, и безопасней.

Смотри ещё: • Пересечение двух отрезков
Смотри ещё: • Проверка точки внутри многоугольника

Structure Synth
nyaload
_winnie
http://structuresynth.sourceforge.net ( програмка, что бы скриптом в несколько строчек замутить какую-нибудь абстрактную фрактальную мего-хреновину )

Вот примеры сгенерированного арта - http://flickr.com/groups/structuresynth/pool/
и под катомCollapse )
Если вы хоть чуть-чуть знаете геометрию или раньше делали всякие снежинки-деревья при помощи рекурсии - то можете побаловаться сделать что-то своё. Если нет - можно просто повращать сгенерированные фигурки :)

Геометрические Алгоритмы. Пересечение двух отрезков на плоскости.
nyaload
_winnie
Пусть есть два отрезка A,B и C,D. Надо понять, пересекаются ли они, и если да, то где именно. Во всех исходниках и книжках, которые я смотрел, это было сделано с кучей ненужного мусора, не смотря на то, что вроде бы очень простая и распространённая задача. Read more...Collapse )

Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Проверка точки внутри многоугольника

?

Log in

No account? Create an account