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

следующий фpагмент (2)
- [94] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 5 of 6 From : Serguey Zefirov 2:5020/620.15 15 Jan 97 13:41:00 To : All Subj : Texture mapping using midpoint algorithm -------------------------------------------------------------------------------- Zdorovenki bulji,(Hi! in other words) All! Метод сpединной точки - инкpементальный метод. Вообще - Бpезенхем (насколько я могу понять). Возможно, ф не пpав. Это неважно. Если кому интеpесны подpобности, то вот ссылочка: <A HREF="http://www.oiri.demon.co.uk/texmap/texmap.htm">The Midpoint Algorithm For High Speed Graphics</A> А если нет Интеpнета (а значит, и подpобностей), то вот исходничек: ;) -------------------------------8<------------------------------------ #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <assert.h> #include <dos.h> #include <math.h> #include <time.h> typedef unsigned char byte; const int SizeX = 320; const int SizeY = 200; const int MidX = 160; const int MidY = 100; byte far *const ScreenBase = static_cast<byte far *>(MK_FP(0xA000, 0)); typedef int int16; typedef long int32; struct TVector { int16 x, y, z; }; void SetMode(int Mode) /* Set the video mode supplied. */ { union REGS in, out; in.x.ax = Mode; in.h.ah = 0; int86(0x10, &in, &out); } #define MIDPOINT void main() { int32 v, u; // Bitmap texel coordinates. int32 x, y; // Screen pixel coordinates. TVector O; // Position of polygon origin in 3D. TVector i, j; // Projections of the polygon's axes onto x,y,z. TVector k; // Normal to the polygon, not unit vector. SetMode(0x13); // Define the view: const int16 d = 130; // Distance of viewer from projection screen. // Define the bitmap's orientation and position: i.x = 16; i.y = 3; i.z = 5; j.x = -3; j.y = 16; j.z = 0; k.x = -5; k.y = 0; k.z = 16; O.x = 0; O.y = 0; O.z = 100; byte far *Screen = ScreenBase; for (int row = 0; row < SizeY; row++) { // Offset to screen centre: y = MidY - row; x = -MidX; // For the first pixel in each row, calculate the texel coordinates // by brute force: int32 A = y * O.z - d * O.y; int32 D = d * j.y - y * j.z; int32 E = d * i.y - y * i.z; int32 H = d * j.y - y * j.z; int32 Au = -j.z * A - O.z * D; int32 Bu = d * j.x * A + d * O.x * D; int32 Cu = - E * j.z + i.z * H; int32 Du = d * j.x * E - d * i.x * H; int32 Av = -i.z * A - O.z * E; int32 Bv = A * d * i.x + d * O.x * E; int32 Cv = -Cu; int32 Dv = -Du; // Scale up coefficients to match the scale of the bitmap axes: Au *= 16; Bu *= 16; Av *= 16; Bv *= 16; // Calculate the initial texel coordinates: u = (Au * x + Bu) / (Cu * x + Du); v = (Av * x + Bv) / (Cv * x + Dv); // Calculate decision variable and increments for the bitmap's i axis: int32 Gu = 2 * Cu * x * u + x * (Cu - 2 * Au) + 2 * u * (Cu + Du) + Cu + Du - 2 * (Au + Bu); int32 ku1 = 2 * Cu * u + Cu - 2 * Au; int32 ku2 = 2 * Cu * u + 2 * Cu * x + 5 * Cu - 2 * Au + 2 * Du; int32 ku3 = 2 * Cu; int32 ku4 = 4 * Cu; // Calculate decision variable and increments for the bitmap's j axis: int32 Gv = 2 * Cv * x * v + x * (-Cv - 2 * Av) + 2 * v * (Cv + Dv) - Cv - Dv - 2 * (Av + Bv); int32 kv1 = 2 * Cv * v - Cv - 2 * Av; int32 kv2 = 2 * Cv * v - 2 * Cv * x - 5 * Cv - 2 * Av - 2 * Dv; int32 kv3 = 2 * Cv; int32 kv4 = 4 * Cv; while (x < MidX) { x++; #ifdef MIDPOINT if (Gu < 0) { Gu += ku1; ku2 += ku3; } else { u++; Gu += ku2; ku1 += ku3; ku2 += ku4; } if (Gv < 0) { Gv += kv1; kv2 -= kv3; } else { v--; Gv += kv2; kv1 -= kv3; kv2 -= kv4; } #else u = (Au * x + Bu) / (Cu * x + Du); v = (Av * x + Bv) / (Cv * x + Dv); #endif // Make a coloured chess board: int Invert = u & 32; int OddBlock = v & 32; int Colour = OddBlock ^ Invert ? (u & 32 ? 14 : 13) : 0; *Screen = Colour; Screen++; } } getch(); SetMode(0); } -------------------------------8<------------------------------------ К сожалению, этот исходничек написан пpостоты изложения pади. А поэтому: Listing 7 has some limitations introduced for simplicity. Firstly, not all cases of the midpoint algorithm are included in the example - only that for which u increases and v decreases as x increases. It is a fairly simple matter to derive the other cases and add a test before drawing each line to see which algorithm to use. This does not affect the timings appreciably. Secondly, the algorithm only works for the case when no more than one texel increment is required per screen pixel increment. The solution here is store lower resolution versions of the bitmap and choose the one to draw whose resolution is closest to the plotting resolution required. :[ sz G!>U d? s:(-:) a- C--->-- !U !P !L !E W>- N++ !o K---- w$ O- M- !V PS+ Y+ PE+++ PGP t>--- 5>--- X? R- tv-->! b++ DI? D+ G- e- h+ r?(--) y ]; IMMEDIATE PS Самому мне pазбиpаться пока лениво было, подумал, может кому и пpигодится. ... i have the capacity to learn from mistakes. i'll learn a lot today. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15)
следующий фpагмент (3)|пpедыдущий фpагмент (1)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 15 of 34 From : bwh@kato.prl.ufl.edu 2:5030/144.99 09 Jul 94 23:49:40 To : All 12 Jul 94 02:48:34 Subj : Re: Texture mapping triangles -------------------------------------------------------------------------------- If I understand what you are trying to do, you are simply assuming the following: a 2D texture map a triangle represented as: Screen coordinates (x1,x2,x3,y1,y2,y3) Texture coordinates (u1,u2,u3,v1,v2,v3) Where each texture coordinate corresponds to one screen coordinate. The easiest and fastest way to do this, albeit without any perspective compensation if you are worrying about a 3D application, is to simply linearly interpolate the u/v coordinates a la a brute force Gouraud shading algorithm. If you are familiar with horizontal line based triangle algorithms, this should be a very straightforward solution. Calculate du(left) and du(right) and dv(left) and dv(right) and draw each horizontal line as follows: char map[MAP_HEIGHT][MAP_WIDTH]; void tmappedline( int x1, int x2, int y, float u1, float u2, float v1, float v2 ) { float du, dv; float u = u1; float v = v1; du = ( u2 - u1 ) / ( x2 - x1 ); dv = ( v2 - v1 ) / ( x2 - x1 ); for ( x = x1; x < x2; x++ ) { Pixel( x, y, map[(int)u][(int)v] ); u += du; v += dv; } } This is off the top of my head, but it should be pretty obvious what's going on. Brian -- +---------------------------------------------------------------------+ | Brian Hook | Specializing in real-time 3D graphics | | Box 90315 |---------------------------------------------| | Gainesville, FL 32607 | bwh@prl.ufl.edu | +- "Style distinguishes excellence from accomplishment" - J. Coplien -+
следующий фpагмент (4)|пpедыдущий фpагмент (2)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 73 of 115 From : vassilie@imag.imag.fr 2:5030/144.99 26 May 94 11:23:00 To : All 10 Jun 94 20:14:16 Subj : (1) Re: Texture mapping -------------------------------------------------------------------------------- Hi, Here is a method that I posted in alt.sys.amiga.demo, it was intended for a doom-like game. An implementation of it on an A4000 ( 68040, 25Mhz, bad memory system ) performs 1.2 Mpixels per sec. It has 2 parts: -shaping of lines -drawing of pixels 1_ shaping of lines : the polygon is considered as a set of horizontal lines that are discribed by the following array: struct { int x_src_beg; // (x,y) pos on the mapped object for the int y_src_beg; // first point int x_src_end; // (x,y) pos on the mapped object for the int y_src_end; // last point int x_dst_beg; // x axis of the first point in the chunky // screen int x_dst_end; // x axis of the last point in the chunky // screen } line[SCR_HEIGHT]; ex: DEST SRC polygon mapped shape object 0123456789abcdef 0123456789abcdef 0 0A--------B 1 A__ 1| | 2 | ---__ 2| | 3 | B 3| | 4 |line[4] / 4| | 5 | / 5| | 6 | __C 6D--------C 7 D__-- 7 line[4].x_src_beg=0 line[4].y_src_beg=3 line[4].x_src_end=9 line[4].y_src_end=2 line[4].x_dst_beg=5 line[4].x_dst_end=e algo that fills the array: init : line [0 .. SRC_HEIGHT].x_dst_beg= MAX_INT; .x_dst_end= -MAX_INT; for the four sides :(A,B),(B,C),(C,D),(D,A) { /* example:(A,B) */ delta = abs(Y_B_dest - Y_A_dest) ; inc_x_src = (X_B_src - X_A_src) / delta; inc_y_src = (Y_B_src - Y_A_src) / delta; /* ( +- 1) */ inc_x_dst = (X_B_dst - X_A_dst) / delta; inc_y_dst = (Y_B_dst - Y_A_dst) / delta; X_dst=X_A_dst; Y_dst=Y_A_dst; X_src=X_A_src; Y_src=Y_A_src; for (i=0 ; i<delta ; i++) { if (X_dst < line[Y_dst].x_dst_beg) { line[Y_dst].x_dst_beg=X_dst; line[Y_dst].x_src_beg=X_src; line[Y_dst].y_src_beg=Y_src; } if (X_dst > line[Y_dst].x_dst_end) { line[Y_dst].x_dst_end=X_dst; line[Y_dst].x_src_end=X_src; line[Y_dst].y_src_end=Y_src; } X_dst+=inc_x_dst; Y_dst+=inc_y_dst; X_src+=inc_x_src; Y_src+=inc_y_src; } } 2_ drawing of pixels for each lines { len=line[i].x_dst_end - line[i].x_dst_beg; /* you're not obliged to do these 2 divs */ inc_x_src = (line[i].x_src_end - line[i].x_src_beg) / len; inc_y_src = (line[i].y_src_end - line[i].y_src_beg) / len; X_src = line[i].x_src_beg ; Y_src = line[i].y_src_beg ; X_dst = line[i].x_dst_beg ; Y_dst = i ; /* main loop */ for (j=0 ; j<len ; j++) { PutPixel(X_dst++, Y_dst, object[X_src][Y_src]); X_src += inc_x_src ; Y_src += inc_y_src ; } } ******************************************************************************** **** for a 680x0 implementation ******************************************************************************** **** the main loop is done in 6 instructions : d0= X_src | Y_src ;with X_src and Y_src = 8 bit integer part | 8 bit decimal part d1= inc_x_src | inc_y_src ;with inc_x_src and inc_y_src = 8 bit integer part | 8 bit decimal part a1 = destination address of the beginning of line in the chunky screen a0 = base address of the mapped object stored in a 256 width chunky screen d3 = len - 1 main_loop: move.l d0,d2 lsr.w #8,d2 rol.l #8,d2 move.b (a0,d2.w),(a1)+ add.l d1,d0 dbra d3,main_loop the whole problem is that the move.b (a0,d2.w),(a1)+ has a very low cache hit rate when reading (a0,d2.w) byte. And though the other instructions are runned at 14 mhz each in average, move is runned at 0.5 mhz when cache fails. I advise you add a dirty bitmap in order to write as much pixels as you'll be able to see and not more. At the moment, the only way I've found to increase cache hits rate is to process as much lines as possible in the same loop: main_loop: process pixel i of line j; process pixel i of line j+1; process pixel i of line j+2; process pixel i of line j+3; ............ i+=1; goto main_loop; If you've got a better algo or if you improve that one: please post. ******************************************************************************** ********* as nobody understood my algo, I posted extra explanations of the first part : shaping of lines ******************************************************************************** ********* |> I didn't get a real good look at your polygon-mapper... |> Could you tell me how it is to be used? I mean what kind of input it |> requires. I would guess you simply give it a set of four 2D coordinates. Yes it only requires an array of 4 2D coords, a description of the texture (adr_base, x_size,y_size ), and a pointer to the chunky screen. |> One other thing, how do you map such a polygon? I have tried to get a good |> Polygon mapper but was unsuccesfull. The main problem was getting the |> routine to be efficient, ie: not mapping the same pixels more than once. |> Could you please tell me how it works? I`m aware that the article I 've posted isn't quite clear about it, but as you may have noticed, english isn't my native langage. That's why I gave an algorithm form of the mapper instead of an english description... But if you really don't catch the algo, here are some extra explanations: In order to write each pixels only once you must split your polygon into lines and find which pixel of the texture object match each pixels of each lines : aaa bbbbbbb ccccccccccc ddddddddddddddd eeeeeeeeeeeeeeeee ______________ ffffffffffffffffffff | | A'ggggggggggggggB' | | hhhhhhhhhhhhhhh | gggB iiiiiiiiiiii | gggg | jjjjjjjjjj | ggg | kkkkkkk |Agg__________| lllll mm (I chose horizontal lines because of memory organisation ) To find it, you consider that an horizontal line of your polygon is mapped with a certain line of your texture object. In other words: (R1): FOR EACH HORIZONTAL SEGMENT [A' B'] OF THE POLYGON, YOU NEED A SEGMENT [A B] OF THE TEXTURE OBJECT WICH IS SO AS : [A' B'] IS THE IMAGE OF [A B] IN A LINEAR TRANSFORMATION. And these [A B] segments of the texture object are determined with the second rule: (R2): THE POLYGON SIDES ARE LINEAR TRANSFORMATIONS OF THE TEXTURE OBJECT SIDES. Now, how do you map a segment without drawing each pixel more than once : Just calculate the size of your [A' B'] segment and pick up as many points in the [A B] segment. This will lead you to the algo I posted earlier. You can easily add clipping: clip each segment. Youri Youri.Vassilief@imag.fr

Всего 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".