_winnie, posts by tag: geom-prog - LiveJournal

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



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



( via aruslan )

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

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

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

Часто значения 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.

( Collapse )

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

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

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

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

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

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, что бы быть ближе к классике.

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

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



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

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

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

А то часто заморачиваются с аркосинусами, получают сложный некрасивый код и падают при попытке взять аркосинус(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)² > 0.5*length²(a)*length²(b).
0.5 здесь взялся как cos²(45°). И ещё надо не забыть условие dot(a, b) > 0. length² - это sqrt(x²+y²+z²)², то есть (x²+y²+z²), без извлечения корня.

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

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

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

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

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

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

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