DEMO.DESIGN
Frequently Asked Questions
 
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
- Personal mail (2:5030/84) ------------------------------------ >RIPPED_MAIL - Msg : 316 of 316 Rcv From : Alex Fefilov 2:5003/15.119 05 Dec 97 12:08:34 To : Peter Sobolev 09 Dec 97 02:36:40 Subj : Алгоpитм Бpезенхейма 4 d.d.FAQ ------------------------------------------------------------------------------- Coбcтвeннo caбж дoвoльнo чacтo вoзникaeт в paзнom видe в пpoгpammepcкиx эxax. B литepaтype вcтpeчaeтcя mнoгo oпиcaний нo я дoлгo нe moг ocoзнaть этoгo meтoдa, пoльзoвaлcя кaк ecть. Ho в oднoй книгe ( Ф. Mapтинec "Cинтeз изoбpaжeний" глaвкy пpивoжy нижe) нaшлocь oпиcaниe, кoтopoe дaжe я пoнял! алгоритм Брезенхэма При совмещении начала координат с одним из концов отрезка имеем три возможные оси симметрии и достаточно рассмотреть половину одного квадранта, например ту, для которой dx >= dy >= 0. Уравнение прямой описывающее отрезок: dy y = ---- * x или y*dx - x*dy = 0 dx ^^^^^^^^^^^^^представляет собой _функцию_ошибок_ , которая должна быть минимизирована по абсолютной величине в процессе генери- рования. Оно становится равным нулю, когда точка находится на прямой. Пусть E = y*dx - x*dy. (1) Если за исходную точку принять начало координат, то достаточно двух элементарных движений, чтобы с их помощью перемещаться вдоль отрезка. Движение A: увеличение x x = x + 1; в результате согласно (1) ошибка уменьшается на величину dy: E = E - dy; Движение B: увеличение x и y x = x + 1; y = y + 1; приводит в соответствии с (1) к возрастанию E на величину (dx - dy), име- ющую положительное значение в рассматриваемой половине квадранта: E = E + dx - dy; исходя из этих соображений построен итерационный алгоритм минимизации ошибки при котором на каждом шаге выбирается соответствующее движение: E = 0 y = y0 x = x0 dx = xe - x0 dy = ye - y0 da = -dy db = dx - dy while x < xe x = x + 1 if E < 0 ( движение B ) y = y + 1 E = E + db else ( движение A ) E = E + da end if point x, y end while Этот алгоритм имеет два недостатка: 1. первое движение выбирается произвольно (здесь движение b) 2. ошибка изменяется от db до da ( dx-dy и -dy ) и случайным образом большинство точек может расположиться выше или ниже истинного отрезка. Обе проблемы отпадают, если центрировать функцию ошибки относительно нуля, начиная с величины dy - dx/2: E = dy - dx/2. Пример Брезенхэма из Аммерала: void line(int xBeg, int yBeg, int xEnd, int yEnd, char clr) { int x, y, T, E, dx, dy, denom, xInc=1, yInc=1, vLng=0, tmp; dx = xEnd - xBeg; dy = yEnd - yBeg; if(dx < 0) { xInc = -1; dx = -dx; } if(dy < 0) { yInc = -1; dy = -dy; } if(dy > dx) { vLng = 1; tmp=dx; dx=dy; dy=tmp;} denom = dx << 1; T = dy << 1; E = -dx; x = xBeg; y = yBeg; while(dx-- >= 0 { pset(x, y, clr); if((E+=T)>0) { if(vLng) x += xInc; else y += yInc; E -= denom; } if(vLng) Y += yInc; else x += xInc; } } C yв. Gluck
следующий фpагмент (3)|пpедыдущий фpагмент (1)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 38 of 59 From : jflore@asictest.sc.ti.com 2:5030/315 28 Nov 95 15:11:06 To : All 30 Nov 95 06:51:30 Subj : Re: Drawing lines on a PC with ASM -------------------------------------------------------------------------------- X-RealName: Jose Flores Bressenham is a *sorry* choice for line drawing on 32-bit machines ESPECIALLY those with sophisticated pipelining such as 486+. A simple fixed point line works much much much better...look: If u don't have a 32-bit compiler like watcom this is gonna be slower than your bressenham, if not my C code is almost for sure faster than your assembly code. void Line ( char *Where, short x1, short y1, short x2, short y2, char color){ #define lfs 16 #define LScreen(x,y) Where[ ((y)<<6) + ((y)<<8) + (x) ] //--------Below is a nice way to avoid having to round the 16.16 number #define HalfLinePixel (1 << (lfs-1) ) register long incX,incY; register long x = x1; register long y = y1; long dx = x2 - x1; long dy = y2 - y1; if ( (dx==0) && (dy==0) ) return; if (abs(dx) > abs(dy) ) { y <<= lfs; y += HalfLinePixel; if (y1 < y2) incY = abs( (dy << lfs) / dx); else incY = -abs( (dy << lfs) / dx); if (x1 < x2) incX = 1; else incX = -1; while (x != x2){ LScreen(x,y >> lfs) = color; x += incX; y += incY; } LScreen(x,y >> lfs) = color; } else{ x <<= lfs; x += HalfLinePixel; if (x1 < x2) incX = abs( (dx << lfs) / dy); else incX = -abs( (dx << lfs) / dy); if (y1 < y2) incY = 1; else incY = -1; while (y != y2){ LScreen( x >> lfs, y) = color; x += incX; y += incY; } LScreen( x >> lfs, y) = color; } } -- http://www.asic.sc.ti.com/~jflore/whoami.html http://www.utexas.edu/~flores "All I want is a warm bed and a kind word and unlimited power" -- Ashleigh Brilliant
следующий фpагмент (4)|пpедыдущий фpагмент (2)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 12 of 38 From : eberly@cs.unc.edu 2:5030/144.99 29 Jul 94 17:49:38 To : All 31 Jul 94 01:06:30 Subj : (1) Re: 3D Breshenhame lines? -------------------------------------------------------------------------------- In article <319d28$ata@desiree.teleport.com>, <zuberm@teleport.com> wrote: > >> I posted code for a 3d all integer bresenham line drawer in, I think, >> comp.sources.unix or something like that 2 or 3 years ago. Send me >> personal email and I'll try to dig out a copy for you. >> >> It turns out that Bresenham's line algorithm generalizes to >> N-dimensions trivially. > >Could you post this please? I'm very interested in this generalized >algorithm. Better yet, could you e-mail it to zuberm@teleport.com? >Also, any source code implementations of this above 2-dimensions. Here is code for 2D and 3D line drawing. Extending the code to higher dimensions is a straightforward generalization. Dave Eberly eberly@cs.unc.edu ------------------------------------------------------------------------------ void line2D (int x0, int y0, int x1, int y1) { // starting point of line register int x = x0, y = y0; // direction of line int dx = x1-x0, dy = y1-y0; // increment or decrement depending on direction of line register int sx = (dx > 0 ? 1 : (dx < 0 ? -1 : 0)); register int sy = (dy > 0 ? 1 : (dy < 0 ? -1 : 0)); // decision parameters for voxel selection dx = abs(dx); dy = abs(dy); register int ax = 2*dx, ay = 2*dy; register int decx, decy; // determine largest direction component, single-step related variable int max = dx, var = 0; if ( dy > max ) { max = dy; var = 1; } // traverse Bresenham line switch ( var ) { case 0: // single-step in x-direction for (decy=ay-dx; ; x += sx, decy += ay) { // routine for displaying (x,y,z) goes here // take Bresenham step if ( x == x1 ) break; if ( decy >= 0 ) { decy -= ax; y += sy; } } break; case 1: // single-step in y-direction for (decx=ax-dy; ; y += sy, decx += ax) { // routine for displaying (x,y,z) goes here // take Bresenham step if ( y == y1 ) break; if ( decx >= 0 ) { decx -= ay; x += sx; } } break; } } ------------------------------------------------------------------------------ void line3D (int x0, int y0, int z0, int x1, int y1, int z1) { // starting point of line register int x = x0, y = y0, z = z0; // direction of line int dx = x1-x0, dy = y1-y0, dz = z1-z0; // increment or decrement depending on direction of line register int sx = (dx > 0 ? 1 : (dx < 0 ? -1 : 0)); register int sy = (dy > 0 ? 1 : (dy < 0 ? -1 : 0)); register int sz = (dz > 0 ? 1 : (dz < 0 ? -1 : 0)); // decision parameters for voxel selection dx = abs(dx); dy = abs(dy); dz = abs(dz); register int ax = 2*dx, ay = 2*dy, az = 2*dz; register int decx, decy, decz; // determine largest direction component, single-step related variable int max = dx, var = 0; if ( dy > max ) { max = dy; var = 1; } if ( dz > max ) { max = dz; var = 2; } // traverse Bresenham line switch ( var ) { case 0: // single-step in x-direction for (decy=ay-dx, decz=az-dx; ; x += sx, decy += ay, decz += az) { // routine for displaying (x,y,z) goes here // take Bresenham step if ( x == x1 ) break; if ( decy >= 0 ) { decy -= ax; y += sy; } if ( decz >= 0 ) { decz -= ax; z += sz; } } break; case 1: // single-step in y-direction for (decx=ax-dy, decz=az-dy; ; y += sy, decx += ax, decz += az) { // routine for displaying (x,y,z) goes here // take Bresenham step if ( y == y1 ) break; if ( decx >= 0 ) { decx -= ay; x += sx; } if ( decz >= 0 ) { decz -= ay; z += sz; } } break; case 2: // single-step in z-direction for (decx=ax-dz, decy=ay-dz; ; z += sz, decx += ax, decy += ay) { // routine for displaying (x,y,z) goes here // take Bresenham step if ( z == z1 ) break; if ( decx >= 0 ) { decx -= az; x += sx; } if ( decy >= 0 ) { decy -= az; y += sy; } } break; } }

Всего 3 фpагмент(а/ов) |пpедыдущий фpагмент (3)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".