Рисование закрашенного треугольника

 
0
 
Алгоритмы
ava
nns2009 | 05.03.2010, 21:13
Решил заняться разработкой 3d движка(на ActionScript 3.0(Язык разработки для Adobe flash)).
На удивление, с преобразованием координат из 3d в 2d проблем не возникло(проверял, создав простенькую функцию для рисования треугольника средствами ActionScript 3.0). Программа просто летала, но была проблема: нарисованные треугольники хаотично перекрывали друг друга!

Тогда я решил заняться z-буфером(для определения более ближнего к камере объекта), и сразу возникла проблема:
т. к. каждой точке, кроме цвета, надо поставить в соответсвие дополнительную характеристику "глубина", нельзя сразу нарисовать фигуру на экран, а нужно поначалу нарисовать фигуру в массив(screen[width][height]) размером с экран(элементы которого содержат по 2 характеристики(глубина и цвет)), при этом рисование должно производиться поточечно: если у данной точки треугольника глубина меньше, чем в соответсвующей точке массива(то есть треугольник ближе, чем самый близкий объект, нарисованный до этого), то заменить цвет точки в массиве на цвет треугольника.
В конце концов нужно поточечно отобразить элементы массива.

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

Пусть

screen - массив, в который всё нужно нарисовать
width - ширина экрана
height - высота экрана
у каждого элемента массива 2 свойства: depth и color
функция для отрисовки называется draw2DTriangleToArray(color:uint, x1:Number, y1:Number, z1:Number, x2:Number, y2:Number, z2:Number, x3:Number, y3:Number, z3:Number)

Подскажите реализацию этой функции или более эффективный метод(желательно на ActionScript или на C++).
Ответы (11)
ava
Pavia | 05.03.2010, 22:13 #
nns2009,
По поводу 1 000 000 треугольников. Достигается это припомощи отсечения. Оптимизация, оптимизация и еще раз оптимизация.
По мимо z - буфера есть и другие методы. Возможно стоит обратить на них внимание. Правда они не такие хорошии как z-буфер. Звто можно будет использовать вывод 2d треугольника не проверяя каждый пиксель.
Алгоритм художника, алгоритм витвей и границ и др.

И еще привиди свой код.
ava
Чупакабро | 05.03.2010, 22:18 #
Скорость рисования зависит не только от способа нахождения z-координаты пикселя, но и от того, как ты передаешь значения массива screen на экран...
Если вызываешь функцию рисования для каждого пикселя, то это очень тормозно.
Ну и инетересно, как ты все-таки определяешь z-координату.
Я делал как сумму z-координаты одной из трех вершин и произведений приращений координаты пикселя по осям x и y на частные производные z по этим осям. делал на Delphi, рисовалось довольно быстро, но я использовал функцию Win API setdibitstodevice
ava
nns2009 | 06.03.2010, 19:52 #
Цитата (Чупакабро @ 5.3.2010, 22:18 findReferencedText)
Скорость рисования зависит не только от способа нахождения z-координаты пикселя, но и от того, как ты передаешь значения массива screen на экран...

Если вызываешь функцию рисования для каждого пикселя, то это очень тормозно.

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


Цитата (Чупакабро @ 5.3.2010, 22:18 findReferencedText)
Ну и инетересно, как ты все-таки определяешь z-координату.

Я определяю z-координату, не для конкретной точки, а при полной отрисовке треугольника, для каждой точки входящей в его состав: вычисляю z-координату и если она меньше, чем значение screen[x][y].depth, то screen[x][y].color = цветТреугольника.
В ближайшее время выложу код.



Цитата (Чупакабро @ 5.3.2010, 22:18 findReferencedText)
Я делал как сумму z-координаты одной из трех вершин и произведений приращений координаты пикселя по осям x и y на частные производные z по этим осям. делал на Delphi, рисовалось довольно быстро, но я использовал функцию Win API setdibitstodevice

Честно говоря, я ничего не понял. Можешь привести соответсвующий код(только желательно не на Delphi, т.к. он очень сильно отличается от всех остальных языков программирования и будет сложно разобраться).
ava
Чупакабро | 06.03.2010, 22:28 #

//находим частные производные z по х и у
getroots(p2.x-p1.x,p2.y-p1.y,p3.x-p1.x,p3.y-p1.y,triangle.p2.z-triangle.p1.z,triangle.p3.z-triangle.p1.z,dzdx,dzdy);

for (j=round(bottom) ;j> round(top);j++)
//от минимального значения координаты у треугольника до максимального
{
for (i=round(left);i> round(right);i++)
//от минимального значения координаты х треугольника до максимального
{
if (intriangle(i,j,p1.x,p1.y,p2.x,p2.y,p3.x,p3.y)==true)
//если текущая точка находится внутри треугольника
{
k=i+j*clientwidth;//номер текущей точки в буфере кадра и z-буфере
rz=(i-p1.x)*dzdx+(j-p1.y)*dzdy+triangle.p1.z;//координата z для текущего пикселя (в мировых координатх)
}
}
}
.
Перевел, как мог на С, заранне извиняюсь за ошибки, неграмотный я...
p1, p2, p3 - вершины треугольника (экранные координаты)
triangle.p1, triangle.p2, triangle.p3 - вершины треугольника в мировых координатах
i,j координаты текущего пикселя
функция intriangle проверяет принадлежность пикселя (i,j) треугльнику (p1,p2,p3)
clientwidth - ширина экрана
функция getroots решает систему уравнений:
triangle.p2.z=(p2.x-p1.x)*dzdx+(p2.y-p1.y)*dzdy+triangle.p1.z
triangle.p3.z=(p3.x-p1.x)*dzdx+(p3.y-p1.y)*dzdy+triangle.p1.z

-находим dzdx - скорость приращения z по х
и dzdy - скорость приращения z по y

В общем, смысл такой: при увеличении координаты Х пикселя треугольника на 1, его координата Z изменяется на некоторую постоянную величину, то же самое при изменении координаты У.
И если известна координата Z хотя бы одного пикселя треугольника, то для любого другого пикселя мы можем ее посчитать, прибавив к этому начальному значению два приращения: от изменения координаты Х и от изменения координаты У.
ava
nns2009 | 07.03.2010, 15:26 #
В общем код понятен, только есть несколько вопросов:
1) Функция getroots() ничего не возвращает. Насколько я понял она вычисляет dzdx и dzdy?
2) Все координаты, к моменту когда мы доходим до функции draw2DTriangleToArray() уже переведены в экранные(с z-координатой, обозначающей дальность точки до экрана), мне кажется лучше было бы, что бы функция getroots() решала такую систему:

p2.z=(p2.x-p1.x)*dzdx+(p2.y-p1.y)*dzdy+p1.z
p3.z=(p3.x-p1.x)*dzdx+(p3.y-p1.y)*dzdy+p1.z

Тогда мы сразу бы получили приращения z-координаты(глубины) в экранных координатах. И тогда в цикле:

if (intriangle(i,j,p1.x,p1.y,p2.x,p2.y,p3.x,p3.y)) //если текущая точка находится внутри треугольника
{
rz=(i-p1.x)*dzdx+(j-p1.y)*dzdy+p1.z;//координата z для текущего пикселя (в экранных координатх)
if (rz < screen[i][j].depth)
{
screen[i][j].color = triangleColor
screen[i][j].depth = rz
}
}
ava
Чупакабро | 07.03.2010, 17:16 #
Цитата (nns2009 @ 7.3.2010, 15:26 findReferencedText)
Функция getroots() ничего не возвращает. Насколько я понял она вычисляет dzdx и dzdy?

Ага

Цитата (nns2009 @ 7.3.2010, 15:26 findReferencedText)
Все координаты, к моменту когда мы доходим до функции draw2DTriangleToArray() уже переведены в экранные(с z-координатой, обозначающей дальность точки до экрана), мне кажется лучше было бы, что бы функция getroots() решала такую систему

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

По поводу тормозов. Я не знаком с ActionScript, но мне кажется там плохо сделана работа с массивами, отсюда и тормоза. А может я ошибаюсь
ava
nns2009 | 07.03.2010, 17:31 #
А как выглядит изнутри intriangle() ?

Цитата (Чупакабро @ 7.3.2010, 17:16 findReferencedText)
По поводу тормозов. Я не знаком с ActionScript, но мне кажется там плохо сделана работа с массивами, отсюда и тормоза. А может я ошибаюсь

Сам язык медленнее, чем C++ и т.п., так как исполняется не непосредственно Windows, а средой выполнения Flash.
ava
nns2009 | 07.03.2010, 19:10 #
После некоторых раздумий, я решил, что будет лучше отказаться от z-буфера и использовать алгоритм художника(поначалу рисовать дальние объекты, а потом, поверх них - ближние), не только из-за производительности, но и из-за того, что при использовании z-буфера, я рисую треугольник не сглаживая и он получается не очень красивый.
Но тогда возникает новая проблема: как произвести сортировку треугольников по удалённости?
Предположим у нас есть массив triangles в котором 100 элементов. Если поначалу пройтись по нему с тем, чтобы найти самый дальний элемент, затем заново пройтись в поисках элемента поближе, то получится очень долго. Как его отсортировать?
ava
Чупакабро | 07.03.2010, 22:42 #
для сортировки треугольников создаешь массив структур из двух полей:
- расстояние от экрана до треугольника
- номер треугольника в массиве triangles
сортируешь массив и все! перебираешь его с конца, в текущем элементе записан номер треугольника, который надо вывести.

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



function intriangle(x,y,x1,y1,x2,y2,x3,y3:single):bool;
//функция определяет, принадлежит ли точка с координатами x,y треугольнику с вершинами (x1,y1) (x2,y2) (x3,y3) - на плоскости
var
s,s1,s2,s3:single;//площади треугольников
//s-площадь исходного треугольника, s1,s2,s3- площади трегольников, образованных точкой (x,y) и каждыми двумя из вершин треугольника
dlt:single;//допускаемая погрешность определения площади
begin
intriangle:=false;
s:=0.5*abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)); // площадь треугольника (х1,у1)(х2,у2)(х3,у3)
s1:=0.5*abs((x2-x)*(y3-y)-(x3-x)*(y2-y)); // площадь треугольника (х,у)(х2,у2)(х3,у3)
s2:=0.5*abs((x-x1)*(y3-y1)-(x3-x1)*(y-y1)); // площадь треугольника (х1,у1)(х,у)(х3,у3)
s3:=0.5*abs((x2-x1)*(y-y1)-(x-x1)*(y2-y1)); // площадь треугольника (х1,у1)(х2,у2)(х,у)
dlt:=s*0.000001;//величина погрешности подобрана экспериментально
if abs(s-(s1+s2+s3))<dlt then intriangle:=true; // если площадь исходного треугольника равна (с некоторой погрешностью dlt)
//сумме площадей треугольников, образованных каждыми двумя вершинами и точкой (x,y), то эта точка внутри треугольника
end;



int intriangle(float x,y,x1,y1,x2,y2,x3,y3);
//функция определяет, принадлежит ли точка с координатами x,y треугольнику с вершинами (x1,y1) (x2,y2) (x3,y3) - на плоскости
{
float s,s1,s2,s3;//площади треугольников
//s-площадь исходного треугольника, s1,s2,s3- площади трегольников, образованных точкой (x,y) и каждыми двумя из вершин треугольника
int res;
res=false;
s=0.5*abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)); // площадь треугольника (х1,у1)(х2,у2)(х3,у3)
s1=0.5*abs((x2-x)*(y3-y)-(x3-x)*(y2-y)); // площадь треугольника (х,у)(х2,у2)(х3,у3)
s2=0.5*abs((x-x1)*(y3-y1)-(x3-x1)*(y-y1)); // площадь треугольника (х1,у1)(х,у)(х3,у3)
s3=0.5*abs((x2-x1)*(y-y1)-(x-x1)*(y2-y1)); // площадь треугольника (х1,у1)(х2,у2)(х,у)
dlt=s*0.000001;//величина погрешности подобрана экспериментально
if (abs(s-(s1+s2+s3))<dlt) {res=1} // если площадь исходного треугольника равна (с некоторой погрешностью dlt)
//сумме площадей треугольников, образованных каждыми двумя вершинами и точкой (x,y), то эта точка внутри треугольника
return res;
}
ava
nns2009 | 08.03.2010, 23:21 #
Я попробовал реализовать что-то подобное, но получилось не очень хорошо: получается неправильная разрисовка, что в принципе можно было бы исправить, если бы вся конструкция не тормозила из-за 6 треугольников! Я пожалуй забуду про z-буфер(его на ассемблере наверное надо программировать чтобы он нормальную скорость выдавал!) и перейду к алгоритму художника.
ava
nns2009 | 14.03.2010, 17:47 #
Реализовал алгоритм художника. Разработка движка постепенно продвигается. Всем спасибо.
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить