Закраска треугольника по Гуро

heilong · 16.05.2006, 13:33

Сейчас изучаю возможности Flash 8 по текстурированию и закраске треугольников. В перспективе - идея сделать несложный 3d engine с текстурами и нормальным (не flat, а Gouraud) светом (что отсутствует в большинстве даже продвинутых flash 3d engines).

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

С текстурированием всё довольно просто, с помощью MovieClip.attachBitmap и MovieClip.transform.matrix а также mask по форме нужного треугольника все неплохо работает, и даже скорость вполне сносная.

С освещением сложнее, быстрого и некривого решения пока не нашёл. Итак, сразу сформулирую вопрос:

Имеется треугольник с вершинами A (0, 0); B (256, 0); C (0, 256).
Для каждой вершины задан свой цвет, например A - красный, B - зелёный, C - синий.
Нужно проинтерполировать цвет по всей площади треугольника.
То есть закрасить его так чтобы в каждой его точке цвет определялся в зависимости от расстояния от каждой вершины. Другими словами, нужен градиент не linear, а с тремя вершинами. При этом важно чтобы это работало быстро. Какие есть идеи?

Теперь варианты как это делал я:
1)

Код:

Делается BitmapData(256, 256), присоединяется к нужному клипу. 
for (y = 0; y < 256; ++y) {
  // линейная интерполяция по катету AC, для r, g, b
  цвет1_r = цвет_в_А_r * (256 - y) / 256 +  цвет_в_C_r * y / 256;
  ...
  такая же интерполяция по гипотенузе BC...
  цвет2_r = ...
  for (x = 0; x < 256; ++x) {
    // интерполяция между цвет1 и цвет 2, для r, g, b
    цвет_r = цвет_1_r * ( 256 - x) / 256 + цвет_2_r * x /256;
    ..
    setPixel(x, y, (цвет_r << 16) + (цвет << 8) + цвет_b);
  }
}

Типичный растровый вариант, показывающий что надо сделать. В компилируемом языке пишется на асме (вместе с текстурой), всячески оптимизируется, на Flash-е же безбожно тормозит. По качеству получается ровно то что нужно.

2)

Код:

Делается BitmapData(2, 2). 
setPixel(0, 0, цветА)
setPixel(1, 0, цветB)
setPixel(0, 1, цветC)
цветD = ... // посчитать средний по компонентам r,g,b цвет между цветB и цветC
setPixel(1, 1, цветD)
Дальше BitmapData присоединяется к клипу с опцией smoothing = true и 
клип увеличивается (с помощью MovieClip.transform.matrix) до 256х256. 
В итоге flash сглаживает картинку и получается приблизительно то что нужно.
Правда по качесту далеко не идеально потому что вокруг середины гипотенузы
получается пятно от пиксела (1, 1). Хорошо заметно, если цветB=цветC=зелёный
(например). По скорости работает очень неплохо.

Качество можно несколько улучшить если соединить способы 1) и 2) и делать битмап не 2х2 а, например, 4х4. При этом к сожаления все равно не идеальное качество, а при увеличении размера скорость падает довольно ощутимо.
Ещё думал, как бы это реализовать с помощью градиента(нескольких градиентов), но так и не придумал.

Можно поиграться с моим кодом: http://heilong.oceanography.ru/flash/lab/
Для наглядности в нём можно закомментировать текстурирование (строка 22), преобразования на плоскости (строка 111) и произвольные цвета вершин (строки 51-59), тогда как раз будет заметно неидеальное качество. Чтобы было лучше видно, можно поставить посильнее увеличение (строка 44).

Кто осилил мои "много букв", милости прошу к обсуждению/идеям.

iLeon · 25.05.2006, 10:09

Уважаемый heilong.
Просмотрела вашу идею расчета цвета. Вы можете набросать Ваше решение освещения? У меня есть реализация этой проблемы, но боюсь, что сильно кривая и медленная. Вкратце суть такова: считается скалярное произведение вектора освещения (длины не более 1) на нормаль к грани (тоже единичной длины), и расчитывается цвет способом перемножения полученного числа на цветовые копмоненты. Обязательно учитывается знак этого скалярного произведения. Но я не умею работать с цветом в числовом формате, только в текстовом, поэтому сложные фигуры (более 40 граней) заметно тормозят при их вращении. Неведимые грани я отсекаю, что ускоряет визуализацию, но это помогает слабо.
Реализована библиотека простых фигур - шар, пирамида,конус, тор, цилиндр, правильные многогранники, при инициализации фигуры сразу формируется массив нормалей к граням. Плохо, что при количестве граней, превышающем 100, заметна пауза при формировании фигуры.
Если Вас интересует мой способ решения освещения граней, я с удовольствием его Вам вышлю. Очень хотелось бы выслушать Ваши идеи по оптимизации вычислений, как Вы их реализуете.
В данный момент ломаю голову над математической моделью пересечения тел. В плане реализовать зеркальное отражение на гранях многогранников. К сожалению, почти нет литературы на эту тему. То что мне доступно на данный момент, трудно переводится на алгоритмы. Может, у Вас имеется литература - математическое описание процесса визуализации?

iLeon · 25.05.2006, 10:15

Здесь фигура.

heilong · 25.05.2006, 11:42

Уважаемая iLeon, давай на ты.
Я гляжу ты в теории понимаешь, поэтому о цвете скажу в двух словах. Цвет во flash-е, как и много где, это просто 24-битное число, необязательно его записывать в 16-ричной системе счисления. старшие 8 бит - r, средник - g, младшие - b.
Сделать цвет из компонентов:
color = (r << 16) + (g << 8) + b; // see docs on "<<". parentheses *REQUIRED*
Достать компоненты из цвета:
r = color >> 16;
g = (color >> 8) & 0xff; // "& 0xff" to filter out the remaining red component
b = color & 0xff; // "& 0xff" to filter out the remaining red & green

Твой код: сотри функцию Stringer и поменяй

Код:

		if (LightFace[i]>=0) {
			a = int(LightFace[i]*256);
			b = Stringer(a);
			faceColor = b+"FF"+b;
		} else {
			a = int((1+LightFace[i])*256);
			b = Stringer(a);
			faceColor = "00"+b+"00";
		}
		color = "0x"+faceColor;
		box.beginFill(color, 100);

на

Код:

    var faceColor;
		if (LightFace[i]>=0) {
			a = Math.round(LightFace[i]*255);
			faceColor = (a << 16) + 0xff00 + a;
		} else {
			a = Math.round((1+LightFace[i])*255);
			faceColor = a << 8;
		}
		box.beginFill(faceColor,100);

FPS это увеличивает несильно. Про скалярное произведение - это ведь просто косинус угла так считается удобно и быстро. Освещение - по закону Ламберта.
У тебя тип закраски - flat, т.е. вся грань красится в один цвет. Я интересуюсь gouraud (Гуро это фамилия автора) закраской, когда цвет свой у каждой вершины грани (треугольника) и плавные переходы на всей грани. Это выглядит много лучше. А работаю я пока вообще на плоскости, т.е. меня пока интересует заполнение конкретных треугольников. Смогу это сделать достаточно быстро работающим - тогда уже 3d engine можно мастерить. Такой у меня здесь bottom-up approach. А весь мой код (предпоследняя версии, сейчас есть ещё один вариант, но он работает даже помедленнее первого, пока не понял как это ускорить) лежит у меня на сайте:
http://heilong.oceanography.ru/flash/lab/texmap.fla.gz
Текстуру в коде лучше закомментировать чтобы лучше был видна закраска.

Не очень понятно, почему у тебя работает медленно, вроде закраска одним цветом во flash-е быстрая операция. Надо искать куда время уходит - с помощью функции getTimer посчитать, где больше всего времени тратится. Потом думать почему и как это исправить. Плохо, что нет во Flash-e profiler-а, придётся самому это делать.

Из книжек могу посоветать Шикина и Борескова "Компьютерная графика" (довольно старая, уже не достать, думаю) и их новую книгу "Компьютерная графика: полигональные модели", по-моему есть на ozon.ru
Очень хорошие книги с алгоритмами и их реализациями (на C).

iLeon · 30.05.2006, 10:06

heilong, спасибо за совет.
Применю этот способ для своих фигур, проверю, насколько увеличится скорость. Кстати, нашла у себя серъезную логическую ошибку - каждый раз просчитывала нормали к граням. Гораздо рациональнее повернуть готовые нормали, т.к. матрицы преобразований требуют меньше вычислений. Это я уже применила к генераторам фигур. Если тебе нужно, могу их выслать, много места они не занимают, т.к. реализованы классами. Боюсь, что сделаны они топорно, но я еще только учусь, вообще flash'ем занимаюсь немногим больше года.
Не совсем понимаю принцип закраски треугольника от углов. У тебя должна высчитываться освещенность каждой вершины? Тогда для каждой из них нужно определять расстояние до источника света, угол падения света.
Что если считать расстояние до самой грани (подумаю, как - принцип расчета расстояния от точки до плоскости, заданной тремя точками где-то у меня есть) - оно определит силу освещенности (если не ошибаюсь, по квадратичному закону от расстояния), поворот грани относительно источника света - задает положение, размер и деформацию градиентной радиальной заливки. Пространственный центр заливки придется на пересечение поверхности и нормали, проходщей через источник света.
Правильно ли я понимаю поставленную задачу?
Графику я изучаю по книге Иванова и Батракова, тоже древняя, но очень хорошая книга.
heilong, планируешь ли ты заниматься вопросом пересечения и зеркального отражения фигур? У меня тут есть кое-какие идеи по реализации проблемы зеркального отражения, пока только в виде принципиальных схем.
В данный момент серъзно занимаюсь обучающими и тестовыми программами во flash'е, в том числе и сетевыми с сохранением результатов (все-таки я учитель, ничего не поделаешь, хотя некоторые решаемые вопросы очень и очень интересны). Приходится учиться еще и в этом направлении. Поэтому мои работы в области 3D-графики продвигаются медленно. Сами принципы моделирования пытаюсь объяснить студентам, возможно, поэтому сама начинаю неплохо понимать их.

heilong · 30.05.2006, 11:00

Нет, спасибо, я фигуры собираюсь делать сам. Собственно, у меня из 3d пока одно желание - сделать земной шар, чтобы его можно было вращать, приближать/удалять (как в старой игре UFO / X-COM). Посмотреть, каково это выйдет по скорости. Желательно с рельефом, обязательно с текстурой и освещением.
Насчёт алгоритмов советую не заморчиваться, пытаясь заново изобрести велосипед (хотя это и интересно), а использовать те, что уже давно есть.
Книга Иванова и Батракова у меня была, и я её выкинул: моё мнение - слишком устаревшая, слишком занудная, слишком много теории (во многом устаревшей), мало практики и конкретных алгоритмов. Многих алгоритмов вообще нет, многие - устаревшие. Короче - слишком старая книга. Шикин и Боресков - на порядки лучше и полезнее. Советую купить, стоит она рублей 150 по-моему.
Пересечением заниматься не собираюсь пока, для земного шара это не нужно. Под зеркальным отражением ты имеешь в виду построение симметричной фигуры или отражение света? Если второе - насколько я знаю, без ray tracing-а тут не обойтись (на flash-е - нереально сделать по скорости).
Учить - это хорошо. А где/кого учишь?

heilong · 30.05.2006, 11:01

Я кстати flash-ем занимаюсь с декабря (программирую на других языках уже давно).

heilong · 31.05.2006, 14:18

Вчера получилось добиться хороших успехов в закрашивании треугольника с помощью градиентов. Изначально мой первый (кривоватый) алгоритм рисовал ~31000 треугольников за 5 секунд. Когда у меня таки получилось (с помощью форума по flash-у на adobe.com) сделать это с градиентом (идеальное качество), скорость была 6800 треугольников за 5 секунд. мдаа, негусто. Долго оптимизировал, в итоге кривоватый алгоритм тоже немного ускорил - до 36000, а с градиентами - до 80000! Т.е. оптимизацией добился более чем 10-кратного прироста скорости.
Что в процессе выяснилось:
если есть

Код:

var m = new Matrix();

то

Код:

m.createGradientBox(...)

- на удивление очень тормозная операция!
я делал 3 таких операции на треугольник, при этом всегда одинаковые.
вынес эти вызовы вовне и сохранил 3 матрицы в переменных, итог:
скорость выросла с 7000 до 24000 за 5с.

теперь colorTransform. я делал как написано в help-e:

Код:

// tri1.l.l1 is a MovieClip
var ct = tri1.l.l1.transform.colorTransform;
ct.redMultiplier = r1;
ct.greenMultiplier = g1;
ct.blueMultiplier = b1;
tri1.l.l1.transform.colorTransform = ct;

первая строчка этого кода реально тормозит! оптимальный вариант:

Код:

// outside the triangle loop
tri1.ct1 = new ColorTransform();
...
// inside the triangle loop
var ct = tri1.ct1;
ct.redMultiplier = r1;
..
tri1.l.l1.transform.colorTransform = ct;

замена трёх комплектов colorTransform-ов прибавила скорости с 25000 до 33000.

или например вот это:

Код:

var matrix = tri1.transform.matrix;
matrix.a = ....
tri1.transform.matrix = matrix;

заменяю на

Код:

// outside the loop
tri1.matrix = new Matrix();
...
// inside the loop
var matrix = tri1.matrix;
matrix.a = ...
tri1.transform.matrix = matrix;

скорость выросла с 33000 до 37000

ещё кое-какие алгоритмические улучшения увеличили скорость до 48000. потом я вообще офигел... сделал так:

Код:

// outside the loop
var ttfm = tri1.transform;
var l1tfm = tri1.l.l1.transform;
var l2tfm = tri1.l.l2.transform;
var l3tfm = tri1.l.l3.transform;
...
// inside the loop
...
// everywhere, use ttfm and l?tfm instead of tri1.transform etc.
l1tfm.colorTransform = ct;
...
ttfm.matrix = matrix;

скороть выросла с 48000 до 76000! а вот например такое известное для интерпретируемых языков ухищрение как максимальное укорачивание имён переменных не даёт вообще никакого результата. я на 95% уверен, что flash-евский компилятор автоматически переименовывает переменные.

p.s. всё вышесказанное относится к flash 8 only.

iLeon · 31.05.2006, 15:23

Зеркальное отражение в смысле взгляда на фигуру со стороны плоскости зеркала, то есть то, что мы реально видим в зеркале - другую сторону фигуры. Способ реализации - расчет новой системы координат, визуализация этой фигуры в этой новой системе. Отображение результата на зеркальной поверхности под маской.
Реализация на уровне разработки схем, расчета центра и поворота новой системы.
Работаю в техникуме, преподаю flash рекламщикам как приложение для рисования роликов, программистам как среду разработки.
Программированием занимаюсь около пяти, немного на VBA, чуть-чуть на JavaScriptе.

iLeon · 31.05.2006, 15:31

Кстати, вопрос: flash может или не может напрямую сохранять данные, например, в XML-файл?
Во всех книгах, что мне попадались, имеется "деловое предложение" либо самому написать программы на перле, php, cgi и т.п. либо обратится к программисту. Локальный метод flush не подходит для сетевых программ тестирования (тесты по английскому языку).