Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Брезенхейм, Рисуем линию

Поиск:
Low-Level Optimizations
Low-level optimizations are somewhat dubious, because they depend on understanding various machine details. Because machines vary, the accuracy of these low-level assumptions can sometimes be questioned.

Typically, a set of general rules can be determined that are more-or-less consistent across machines. Here are some examples:
- Addition and Subtraction are generally faster than Multiplication.
-Multiplication is generally faster than Division.
-Using tables to evaluate discrete functions is faster than computing them
-Integer caluculations are faster than floating-point calculations.
-Avoid unnecessary computation by testing for various special cases.
-The intrinsic tests available to most machines are greater than, less than, greater than or equal, and less than or equal to zero (not an arbitrary value).


None of these rules are etched in stone. Some of these rules are becoming less and less valid as time passes. We'll address these issues in more detail later.

For our line drawing algorithm we'll investigate applying several of these optimizations. The incremental calculation effectively removed multiplications in favor of additions. Our next optimization will use three of the mentioned methods. It will remove floating-point calculations in favor of integer operations, and it will remove the single divide opertaion (it makes a difference on short lines), and it will normalize the tests to tests for zero.

Notice that the slope is always rational (a ratio of two integers).

m = (y1 - y0) / (x1 - x0)

Also note that the incremental part of the algorthim never generates a new y value that is more than one unit away from the old one, because the slope is always less than one (this assured by our improved algorithm).

y[i+1] = y[i] + m

Thus, if we maintained the only the only fractional part of y we could still draw a line by noting when this fraction exceeded one. If we initialize fraction with 0.5, then we will also handle the rounding correctly as in our DDA routine.

Код

fraction += m
if (fraction[i+1] >= 1) { y = y +1; fraction -= 1; }


Note that the y variable is now an integer. Next we discuss how to retain the fraction as an integer. After we draw the first pixel (which happens outside our main loop) the correct fraction value is:

fraction = 1/2 + dy / dx

If we scale the fraction by 2*dx the following expression results:

scaledFraction = dx + 2*dy,

and the incremental update becomes:

scaledFraction += 2*dy,

and our test must be modified to reflect the new scaling

Код

if (scaledFraction >= 2*dx) { ... }.


This test can be made a test against a value of zero if the inital value of scaledFraction has 2*dx subtracted from it. Giving outside the loop:

OffsetScaledFraction = dx + 2*dy - 2*dx = 2*dy - dx,

and the inner loop becomes

Код

OffsetScaledFraction += 2*dy
if (OffsetScaledFraction >= 0) { y = y +1; fraction -= 2*dx; }


The net result is that we might as well double the values of dy and dx (this can be accomplished with either an add or a shift). The result ing method is known as Bresenham's line drawing algorithm. The code is shown below.
Код

public void lineBresenham(int x0, int y0, int x1, int y1, Color color)
   {
       int pix = color.getRGB();
       int dy = y1 - y0;
       int dx = x1 - x0;
       int stepx, stepy;

       if (dy < 0) { dy = -dy;  stepy = -1; } else { stepy = 1; }
       if (dx < 0) { dx = -dx;  stepx = -1; } else { stepx = 1; }
       dy <<= 1;                                                  // dy is now 2*dy
       dx <<= 1;                                                  // dx is now 2*dx

       raster.setPixel(pix, x0, y0);
       if (dx > dy) {
           int fraction = dy - (dx >> 1);                         // same as 2*dy - dx
           while (x0 != x1) {
               if (fraction >= 0) {
                   y0 += stepy;
                   fraction -= dx;                                // same as fraction -= 2*dx
               }
               x0 += stepx;
               fraction += dy;                                    // same as fraction -= 2*dy
               raster.setPixel(pix, x0, y0);
           }
       } else {
           int fraction = dx - (dy >> 1);
           while (y0 != y1) {
               if (fraction >= 0) {
                   x0 += stepx;
                   fraction -= dy;
               }
               y0 += stepy;
               fraction += dx;
               raster.setPixel(pix, x0, y0);
           }
       }
   }
user posted image
Автор: PILOT
Сайт: http://www.sinichka.ru






Просмотров: 3611

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную