Построение треугольников.Новый алгоритм заполнения

New filler algorithm - Новый алгоритм заполнения

Until now, the algorithm we have used were scan-buffers. This is the easiest way of doing fillers, but not as fast as we might want. Now, lets take a look at how we could make our fillers diffrent. Lets start with the basics, what a triangle really are.

До сих пор, алгоритм, который мы использовали, был с буфером развертки. Это самый простой способ выполнения заполнения, но не с такой скоростью какой мы могли бы хотеть. Теперь, давайте посмотрим на то, как мы могли бы делать наше заполнение по-другому. Давайте начнем с основ,, каков треугольник действительно.

For a start, we know that a triangle would look something like.   This is of course only one possibility out of many, but the princip turns out to be the same. We can see that the triangle are made of two triangles, one from 1 to 2 and the other from 2 to 3. Now, if we wanted to draw the top triangle we need to have to slopes we increase constantly, one from 1 to 2 and one from 1 to 3. We see, that if we want to draw the lower triangle too, we need to keep our position on the right side of the triangle, which means same slope, but we need to calculate a new slope to the leftside, namely from 2 to 3. Actually this isn't hard to make at all, and in the end, it might turn out more simple than our old method. Lets go through it all again, this time in code, only the top triangle.

Для начала, мы знаем, как выглядит треугольник. Это конечно только одна возможность из множества, но принцип, тот же самый. Мы можем видеть, что треугольник сделан из двух треугольников, один из 1 до 2 и другого из 2 до 3. Теперь, если мы хотим рисовать верхний треугольник, мы должны иметь наклоны, которые мы увеличиваем постоянно, один от 1 до 2 и другой от 1 до 3. Мы видим, что, если мы хотим рисовать более низкий треугольник также, мы должны сохранить нашу позицию справа от треугольника, которая означает тот же самый наклон, но мы должны вычислить новый наклон на левой стороне, а именно от 2 до 3. Фактически это не должно быть трудно сделать вообще, и в конце, это могло бы собираться более проще, чем наш старый метод. Давайте пройдем это все снова, на этот раз в коде, только для верхнего треугольника.

xslope1 = (x2-x1)/(y2-y1);

xslope2 = (x3-x1)/(y3-y1);

leftx=x1;

rightx=x1;

for (y=y1;y< y2;y++)

{

leftx+=xslope1;

rightx+=xslope2;

for (x=leftx;x<=rightx;x++)

BufPixel(x,y,color);

}

Now, the above code works in princip, but we see that there are alot of stuff we still need to correct. For a start, we dont know that the left side varies from x1 to x2 or that the right side turns out to be the longest of the three. Therefore we need a checking which goes something like:

Теперь, вышеупомянутый код работает в принципе, но мы видим, что имеются много наполнения, которое все еще должны исправить. Для начала, мы не знаем, что левая сторона изменяется от x1 до x2 или что правая сторона, окажется,  самая длинная из трех. Следовательно, мы нуждаемся в проверке:

if (leftx>rightx)

{

temp = leftx;

leftx = rightx;

rightx = leftx;

}

This should do the trick, but of course this is a bit easier in assembler, and doesnt take as many cycles (but lets not get into that optimizing buisness yet). What we also have to do is, to correct our coordinate value so that y1 are smaller than y2 and y2 smaller than y3. Also we need to change the x values with them, so that x1 wont be x coordinate to y3. Lets see how this is done:

Это должно сделать трюк, но конечно это немного проще на ассемблере, и не берет так много циклов (но давайте не будем о оптимизации). Что мы также должны делать, исправлять наше значение координаты так, чтобы y1 был меньше, чем y2 и y2 меньше чем y3. Также мы должны изменить значение x с этим, так, чтобы x1 не была координатой x y3. Давайте посмотрим, как это выполняется:

if (y1>y2)

{

temp = y1;

y1 = y2;

y2 = temp;

temp = x1;

x1 = x2;

x2 = temp;

}

if (y2>y3)

{

temp = y2;

y2 = y3;

y3 = tem3;

temp = x2;

x2 = x3;

x3 = temp;

}

if (y1>y3)

{

temp = y1;

y1 = y3;

y3 = temp;

temp = x1;

x1 = x3;

x3 = temp;

}

This also turns out easier in assembler due to the fast xchg command, since the above code, watcom would threat as mov's and thats slower than an xchg, of course depending on the machine and the values you need to exchange (eg. xchg eax,ebx turns out fast than xchg y1,eax).

Это также выполняется проще на ассемблере из-за быстрой команды xchg, так как вышеупомянутый код, делает через mov's и что медленнее чем xchg, конечно в зависимости от машины и значений которые надо поменять ( т.е. xchg eax, ebx выполняется быстрее, чем xchg y1, eax).

Now, we do the same with the lower part of the polygon as with the upper, all we have to do here, is to calculate the new slope slopex2x3.

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