Scream #02
29 января 2002 |
|
Tutorials - coding: the effect of the implementation of "Mirror rotator" (article is intended for quite prepared demo coder).
| Coding | Vivid / / brainwave I would like to first make a digression. Some of you have probably read zero release Kovrov e Newspaper Kosme, let the group Placebo (ex-Eternity Industry). The newspaper contained articles coder'a main groups, Sairoos'a of the demoscene. Let me just say that I, as a coder, in many respects solidarity with Cyrus. In many respects, but not in all. Namely, I was incomprehensible to his wild reaction to our DeMouy Tryptomine Dream. And if a personal dislike for multicolor Cyrus, I can still understand (me, for example, chunks do not really like), then his words of which explicitly or implicitly followed the conclusion that almost all in Tryptomine Dream done with animation, even calculate in advance, could not vizvat in my soul storm indignation. Of course, we are with him in person at CC'01 figured out all the misunderstandings, but some readers Kosme after this article may already formed a negative opinion about the group Brainwave and demah. After CC, I tried to connect with Placebo via e-mail'a requesting a rebuttal of negative words he addressed to us, but had still not received response. So we have to do their own refutation. ;) Taking this opportunity I can safely say the entire Spectrum demoscene: "In all demah issued under label Brainwave no animation in the conventional sense the word! "That is no pre-loaded sequence of frames in our demah was not there and, hopefully, will not. Pre-calculated animation (ie animation, footage of which calculated during dekryanchinga, and then just output) in us demah also been applied. True, it was in the 4k Marazm advance calculated chess heart, but it's been a long time, and excuses for idiocy two-year statute of limitations I have not going, besides it's an isolated case. Now, the question of terminology. Clear separation between animation and realtime not. More on CC'01 I had a dispute with Flying ^ DR and Sair00s ^ PCB on this topic. Say, can we consider 3d animation output facility beforehand a calculated coordinates its vertices? And using the Look Up Tables (Bump mapping, Sphere mapping, Tunnel ,...)? And the use of sine tables when calculate 3d instead of an honest calculation of sines formula Taylor? Everyone in this respect his opinion. So, something I afield in the wrong direction. I'm, like, going to write about the coding article. These and loans. It is assumed that the article is designed to fairly prepared a demo coder, which has a base set knowledge. Mirror rotator. It first appeared on the Spectrum in Deme Refresh and GOA4k, written Exploder ^ Extreme, then reincarnated in our Deme Tryptomine Dream in Multicolor implementation. By the way, Cyrus his accepted for prekalkuleyting (see, confused multicolor, 25fps (Which he felt for 50) and podzagruzka in front of him). Immediately the algorithm of its own implementation. I have a texture of size 128 * 128 pixels. And in druh identical copies. In the center of each texture is so called the View port, the size of the screen (in my case 64 * 48). To get the effect you just use the normal Rotate-Zoomer, using a pattern from the first buffer to output Viewport into the second buffer. Further, the pattern of the second buffer spreads on the screen. When drawing the next frame is the role of texture of the source performs a second buffer, and the role teksturypriemnika - the first. This is a general algorithm. Now the details of my implementation. Rotozumer - pretty zhruschy effect, so use classic 60 innerlupa clock is too slow to resolve 64 * 48. Therefore been made simplification (by the way, the Refresh and GOA was the same): Using the tangent of the sine instead, limiting the angle of rotation from-pi / 4 to + pi / 4. This gave the opportunity to move on texture along the X axis with step 1, and the axis Y - a step tg (alfa). Lack of - Zuming itself depends only on the angle and its be flexible to change. Dignity - the calculation of the color of one point it takes only 20 cycles: ldi; toss the point and, simultaneously, shifts in X nop; here in decrunching'a substituted Team ; Nop, inc h or dec h for the need to shift , Y-axis in the texture Further, direct that for which it was implemented: multicolor himself. The effect is calculated in parallel with the withdrawal multicolor. Advantage: rational use time processor. Disadvantage: difficult to write, although it can be. In order to create a multicolor 4 * 4, it is necessary (in my implementation), so that even lines stored on a single screen and odd - on the other. Thus it is necessary to switch from screen to screen through 224 * 4 = 896 cycles (hereafter assumed Timing under the Pentagon-128). On the calculation of one row vysheupomnutym innerlupom takes 20 * 64 +? cycles, ie 1300 cycles. It turns out that to calculate a single line of 896 beats impossible. Hence we have two choices: 1. Calculate the start of the line, switch the screen calculate the remainder of the line, to make the delay to 896 * 1792 cycles do not forget to switch the screen. In this case, we lose just so about 500 cycles. I think, Full Screen 25 fps Mirror rotator in this case is not done. 2. I chose this way, although it is more laborious. Must switch screens through 896 cycles, without pausing between calculations rows. This is a fairly trivial task, since the nature of innerlupa (need recalculated team standing after ldi, for each frame again) does not allow razdekryanchit this code on all the available memory. In addition, this remaining memory remains relatively small (32 kilobytes is texture, 8 kilobytes of the screen and the variables of Basic, plus the code needed More and other things). Only one way out: subverted with dynamic breakpoints. Talk about this only briefly (for details, already rusty, because more than a year. Who's supposed to, can see source). In general, the main loop looks like this: org # ed00; why # ed00, learn more ld bc, # 7ffd ld de, # 1018 ld h, # ed exx ... ld sp, AddTab loop: calculate the address of the current row, etc. rept 64 ldi: nop endr calculation addresses the underlying string ret exit: One would think, why are ret? And here is why: 1. when necessary, performs the role of team djnz, only holds for 10 cycles instead of 13;) 2. when necessary, removes the address of a small protsedurki type: exx ld l, xx ld (hl), # c9; command code ret , Set a breakpoint on the location code # ED ; Team ldi exx ret; go to top of the loop Once this ret we turn to a procedure similar to the following read: exx out (c), d; or out (c), d, depending on whether ; What screen should include ld (hl), h; restore code # ed team ldi ; This is where that innerluprazmeschen on ; At # ed00;) ld l, xx ld (hl), # c9; put a new breakpoint exx ret; exit from the breakpoint AdrTab table contains the addresses to go to these protsedurki and addresses out of the breakpoints. The table is compiled so that swapping screens do not occur during the upper and lower border, saving precious cycles. Once the picture is rendered in the buffer in the form Munk'ov (Short Multicolor Chunk, invented by me for denote elements of the image is one byte, and non-color code), it is necessary to bring it (buffer) on the screen in as attributes. This is a very simple operation, and Pasha. Munk'i have the numbers to, say, # f8 on # ff. In the address # f8f8 # ffff is the table of the form: # F8f8: 00 01 02 03 04 05 06 07 # F9f8: 08 ... 0f ... # Fff8: 38 39 3a 3b 3c 3d 3e 3f To brighten the table must contain the numbers from # 40 to # 7f. Conversion Munk'ov to attributes is satisfied innerlupom: ; Sp-munky buffer ; De-screen address (attr) rept 32 pop hl ldi endr 26 cycles for a couple of lures. The effect is ready. I hope that someone understood something. One frame multicolor Mandelbrot fractal zoom. It can contemplate at least in our Deme Stellar Contour for CC'01. Many mistook it for an animation, thinking that Spectrum such work can not do. It turned out that at some wit and dexterity, can be done using code. First, briefly about the algorithm for drawing a fractal Mandelbrot: We have a complex plane (or plane complex numbers). That over the complex plane (or plane of complex numbers)? Those in the know, can skip the next couple of paragraphs. Let it be known that the root of a negative number you can still learn, except that the resulting number is not real (Real) (1, 2, 5.6523) and imaginary (Image). Ie For example: sqrt (-9) = sqrt (-1 * 9) = sqrt (-1) * sqrt (9). The square root of -1 is called the imaginary unit and denoted by the letter i (in some literature, the letter j). Hence, the root of -9 is: sqrt (-1) * sqrt (9) = i * 3. Complex is the number of Z = A + i * B, where A and B - real numbers, i - imaginary unit. In this case, A - real part (denoted by Re (Z)), B - the imaginary part (Denoted by Im (Z)). The complex plane - it ploskot, Po horizontal axis which defers the actual component of a complex number, and the vertical axis - imaginary. For example, a complex number of the form Z = 3 + 5 * i on the complex plane will be the point with coordinates (3, 5). Since complex numbers are numbers, then for them determined by the arithmetic (and not only the operation). We are interested in primarily the operations of addition and squaring: Build: C1 = A + i * B; the first number C2 = X + i * Y; the second number C3 = C1 + C2 = A + X + i * (B + Y); ie real numbers are added separately, imaginary - separately. Squaring: (A + i * B) ^ 2 = A ^ 2 + 2 * A * i * B + i ^ 2 * B ^ 2 = (taking into account the fact that i ^ 2 =- 1) = A ^ 2 - B ^ 2 + i * 2 * A * B Each complex number is characterized by a modular approach, deystvitelnynm number equal to its distance from the beginning coordinates: R = | Z | = sqrt ((Re (Z)) ^ 2 + (Im (Z)) ^ 2) So, with compl. ploskotyu understood, it remains to deal with algorithm for drawing the Mandelbrot fractal. So, we have plane of complex numbers, every point of which is painted in certain color. Sovokoupnost these points as time and forms Mandelbrot fractal. How to determine the color point of knowing her coordinates? Here's how: C = X + i * Y - a complex number, or, roughly speaking, our point on the plane with coordinates (X, Y) We have some complex number Z, which was originally set to 0 (or 0 + i * 0). So, we calculate the loop following formula rekurentnuyu Z (k) = (Z (k-1)) ^ 2 + C up until the module Z (k) becomes a very large number (About 10E100) or until the loop is not executed for some number of iterations (about 100-10000). How many times execute cycle, will depend on the color of our point. Software can implement something like this: Input: X0, Y0 - coordinates of the point corresponding to the upper left corner Screen cpl. plane. SCALE - scale. (The smaller the greater the degree of magnification). SCRX, SCRY - the size of the window, which will be painted on the fractal. double yy = Y0; / / Y coordinate of the upper corner of the screen / / Cpl. plane for (int Y = 0, / / loop through the rows Y0)''(Re2 + Im2 <1e100); PutPixel (X, Y, color); / / draw point in the buffer } } Everything would be fine, except that danna program, being running on a Pentium-233, will draw in the window 128 * 64 8 colors of each frame somewhere along the half-second. What to say about Speccy our poor thing: (. Yet all is not as bad as it seems. The first thing that might come to mind, because it put the steam pisyuk for 5 minutes, so we figured that a few hundred frames size, say 64 * 32, and we then ask them to Speccy somehow draw. And you can apply the delta-packing (stored only difference between adjacent frames, the rest remains unchanged). Data is stored as follows: first there is a stream of bits, each set in one bit of which indicates that that the corresponding byte of attributes (we're in a multicolor do) you need to change, and thrown in zero indicates that should leave it unchanged. rl e; 8 jr nc, pausa0; 15/20 ld a, (hl); 22 ld (bc), a; 29 inc l, c; 33 jr next1; 45 pausa0: or (hl); 27 or (hl); 34 or (hl); 41 nop next1: .... Total 41 cycles per 1 byte. A string of 32 bytes takes about 1300 cycles. But, since we need to keep multicolor have done at the end of the line delay to 1792 cycles (during this time pentagon has time to display eight rows). All is good, only I frame compression more than 8 times, not receive, and other ways of packing for a multicolor problematic. But the real picture will be compressed somewhere 4 times or 5, that the amount of frame-buffer 1964 * 32 will make semolina about 250 bytes per frame. It turns out that for some 5 seconds zuming we will take more than 60 kilobytes of RAM. Given that the demo - is, above all, demonstrate the possibilities of computer it turns out that only on the spectral Galimov anime several seconds to turn. That is why I strongly rejected this leymovogo ways to implement a fractal zoom. Realizing that assume a fractal in real-time on the Spectrum - the idea Of course, the heroic, but no one party will not wait 5 minutes, while our hero Speccy render another frame, it was necessary act cleverly and with the help of PCs. Since the soundtrack in Stellar Contour comes with a 3 rate, and under zuming scheduled to take four pattern of 64 notes (768 Mounting), it was decided to implement effect as follows: I'm using this prog to render to the HRC 27 phases fractal zoom, each of which represents an increase the same area of the fractal 2-fold greater than in previous phase. Each frame was to render 128 * 64 (Output planned to make the window 60 * 32) in 8 colors, and occupied, respectively, of 4096 bytes. The algorithm is as follows: for Interrupt hanging procedure that gently (up to 28 frames) increases (right on the screen, without any additional buffers) the current phase of fractal image dvuhkrantogo reduce to normal size, while the other buffer and burn the next phase. The idea is good, but 4k * 27 phases - Is 108 kilobytes! Worse than that is the case with anime. The solution came quickly - to keep in mind these 27 intermediate phases in packed condition, and unpack them at the time zuming the previous phase. Heh, clever idea. Here are just zuming eats about 60,000 cycles, leaving about 11 free thousand. 11 000 cycles * 28 = Mounting approximately 300,000 cycles, ie Roughly speaking, I should have time to unpack 4 kilobytes to 4 Inta! Crunching and hrum not good because of insufficient speed unpacking. So I had to write your own pakovschy and extractor, which would combine a decent degree of compression and I unpack the required speed. Given the nature of pakuemyh data (bytes from 0 to 63), it was decided to write a wrapper, sharpened under the packing is of such data. Algorithm for extracting (According to him, by the way, it becomes clear packing algorithm): * Codes # 00 to # 3f: just write the byte. * Codes # 40 to # bf: for example, popallos number # ad, then write # 0d +2 = 15 bytes with the code # 36 (inc = # A-4 = 6, paper = 6) * Codes # c0 on # cf: repeat the last byte of decompressed (N-# be) again. * Codes # d0 to # fe: toss n - # cd bytes of the following the input stream are stored packed by 6 bits. Allows saving of 2 bits in one byte nepakuyuschemsya * Code # ff - a sign of the end of the block. Packer, written by me on some frames to yield results Even better than hrust 1.3 (natural comparison was made without taking into account the lengths unpackers). By the way, he squeezed every frame faster than a second. That's what packer, sharpened under compression of a particular type of data. In my case - an 8-color texture. Unpacking, of course, fit into the bounding boxes with a small margin. As a result, the output began to occupy about 28-29 kilobytes instead of 108. After compression Khrust already packed Data managed to win some kilobytes. Now calculate the total ratio: During his tenure, is generated 28 * 27 = 756 frames size 30 * 32 = 960 bytes. Ie More than 700 kilobytes. Takes it all farm of about 30 kilobytes. There is a compression somewhere in the 24-fold. Call this an animation effect or not? No brainer, that even in name and contains the word Fractal Zoom, the calculation of the fractal is not attending at all. But zuming realtaymovy. Well, those intermediate 27 staff of 756 - want to count the animation, you want - do not count. Now a few words about zuming. Here, too, had to think (it think, not s3.1415zdit from somewhere) algorithm sharper larger bitmap. Feature of the first: he zumit image stored in compressed form (2 munk'a in one byte) and directly to the attributes (also sealed format). The problem arises fast transcoding back and forth. I solved this problem with using tables, which allow you to extract individual munk from bytes from the source and move it to either the left or the right half of the byte the receiver. TBL2L TBL2R TBR2L TBR2R L R L R L R L R V V V V L R L R To improve the speed, I duplicated one of these tables, and tables themselves placed in memory as follows TBL2R equ xxxx TBL2L equ TBL2R + # 100 TBR2R equ TBL2L + # 100 TBR2L equ TBR2R + # 100 TBL2R_ equ TBR2L + # 100 Innerlup for each phase of scaling had razdekryanchit advance on the whole line. For example innerlup to increase to 1 just looks like this: pop de; take 2 bytes of image ld l, e ld h, TBL2L/256 ld a, (hl); extract from the left half of the bytes in the left inc h; move to TBR2R or (hl); combine with the right half of byte ld (bc), a inc c ld l, d ld h, TBL2L/256 ld a, (hl) inc h; move to TBR2R or (hl) ld (bc), a inc c Naturally, at the end of each line must be provided delay for the entire innerlup executed exactly 1792 cycles. There. Reveal the secret of another effect. Multicolor Doom. Well, Doom - it loudly. Most likely, Wolf. This effect - my pride. Even after CC'000 I had an idea implement something in multicolor, at first glance unrealizable in it. And so, at a cost of business more than a month coding, I wrote to this effect. Brief technical Features: Resolution: 64 * 32 Number of colors: 8 multicolor Frames per second: 16.7 (!). One frame is rendered in 3 Inta. Map Size: 32 * 32 Texture Size: 16 * 32 Number of textures: 32 Additional features: there was an opportunity to put more on Bottom Border to scroll type RAGE'ovskogo. However, due to lack of Time had to scroll to score. Especially because not scroll quite fit in with doom'om. Well, yes and God bless him. I must say that this effect is completely realtaymovy. No prekalkuleytinga Image not available. To prove that I have in Peter compile this effect by adding to it control of the keyboard and added to the resulting surrogate As a bonus to Deme;). So that all non-believers may simply steer on the map by pressing Q, A, O, P, L, Enter. Applied the following "distorted": 1. Realtaymovaya ray tracing. 2. Realtaymovy scaling textures. 3. Inside innerlupa multicolor, the procedure of multiplication bytes per word. 4. Innerlup contains a bunch of branches. While each branch were counted manually. 5. All calculations are, of course, conducted in parallel with the withdrawal multicolor. Thus, the general idea of the effect. I must say I have used is not quite correct algorithm. In fact, it is done without ray tracing. First, it somewhat faster, and, secondly, to avoid errors calculations. However, the multicolor-free way to implement trace in parallel with the withdrawal of multicolor impossible. Thus, the essence of the trace: We have a center of the chamber (indicated by a symbol "o"), the camera direction (axis z). Plane of the screen: (denoted by AB). Plane of the screen is divided into 64 columns (Each column width of 1 munk). We call their clusters (I do not care how they called, I'll call them clusters). Carried out a ray from the center chamber through each cluster to collision with the wall (in the figure is a ray of oD) or until exceeded the maximum length of the ray (I have it, as far as I remember it 7 blocks of cards). The coordinate of intersection determined which column in the texture should draw, and on length of the projection beam to the axis direction is determined by the height this column. It remains only to draw it into the buffer. Hehe, it's not so easy as we would like. If you approach the matter bluntly, the rate will be very small. Firstly, in I move around the map is not pixel by pixel, and immediately block by block. Secondly, all the bias and the coefficients for each angle (0 .. pi / 4) and each cluster is calculated in advance (hence the pause somewhere in the 10 seconds at dekryanchinge). Third, to find a point intersection of the procedure byte multiplication on the floor, which had razdekryanchit 256 times that it was done always for 204 cycles (with the CALL and RET). In addition, it was necessary also razdekryanchit procedure of scaling of textures and trace rays. As a result, the size of the source is around 90 KBytes format ZXAsm. Perhaps it is wrong. But write and 90 kilobytes of source code to debug procedures similar to me pokazalo easier than to write and debug dekryancher that himself would have done the job. Okay, more importantly, what works and like, not buggy. Describe here all details is not desirable. Therefore, the study source. Free Directional Tunnel. This can be seen in Baidu Deme Dogma by Eternity Industry. Let's just say I was fascinated by the courage of Cyrus that implemented this effect on the Spectrum. However, I believe that this effect is still not for the Speccy, since its implementation in chunk will be seen the error of computation, so this article I shall confine ourselves algorithm that can easy to implement on a more powerful machine is not particularly izgolyayas with assembler. This effect is realized on the principle of ray tracing drawn from the camera focus to its intersection with the wall of the tunnel. Thus, the tunnel is the usual infinite cylinder radius R0. To simplify the formulas we assume that the camera can only move in a straight line is the axis of the Cylinder: =========== P ====================================== ============ < / ^ X or Y / R0 / O *> Z U > ================================================== ============ The texture is superimposed on the cylinder as follows: U coordinate in the texture changes as well as Z, ie along walls of the tunnel. V coordinate in the texture izmenyaets uniformly circumference of the tunnel. In this case, the camera can only move along the axis Z. So, you need to find a point of intersection of the ray OP (x, y, z) with wall of the tunnel. Coordinate Zi intersection points from the condition: R1 z z * R0 - = - => Zi = ----- R0 Zi R1 Here: R1 = sqrt (x ^ 2 + y ^ 2). Knowing Zi can define U: U = Zi * k + U0, here k - a rate from which depends on how the texture is stretched along the axis Z. Can, in Basically, take it to 1, U0 - basic coordinates in texture, changing which can create the illusion of camera movement along the axis of the tunnel. Coordinate of V is determined from the condition that it is linearly varies around the circumference of the tunnel. Ie knowing the angle between vertical and the vector (x, y, 0) we can calculate the coordinates of V: arctan2 (x, y) * N V = --------------- 2 * PI Function arctan2 (x, y) returns the arctangent value (X / y), if y <> 0, and 0 otherwise. If the texture has dimensions Un x Vn, then N = Vn. Thus, the formula for finding the coordinates in the texture we have left to decide what to do with them. I hope that the reader knows the formula of rotation around the axis point. If not, just case of recall: Around the axis x: x '= x y '=-sa * y + ca * z z '= sa * z + ca * y Around the axis y: x '=-sa * x + ca * z y '= y z '= sa * z + ca * x Around the axis z: x '=-sa * x + ca * y y '= sa * y + ca * x z '= z x ', y', z '- Tochni coordinates (x, y, z) after rotation. sa - the sine of the angle of rotation around this axis ca - cosine of the angle of rotation around this axis The camera we have the following parameters: SX - width in pixels SY - height in pixels SC - distance from the focus of the camera to the plane of the screen. From this parameter depends on the angle of the camera. It is equal to: angle = arctan ((SX / 2) / SC) * 360/PI - angle camera on X. Usually prinimat Scale equal to SX / 2. In this case, the viewing angle is 90 degrees. With viewing angle of 120-130 degrees, and more becomes apparent prospect of an unnatural image. So, now we know the camera parameters and 3D rotation formula. Now we just turn a mere 3 points the camera: ULC (-sx / 2,-sy / 2, SC) - upper left corner of the screen URC (sx / 2,-sy / 2, SC) - upper right corner of the screen DLC (sx / 2, sy / 2, SC) - lower left corner of the screen After turning obtain points: ULC '(x0, y0, z0) URC '(x1, y1, z1) DLC '(x2, y2, z2) Knowing them, we can find two vectors: VX = (URC'-ULC ') / SX = ((x1-x0) / SX, (y1-y0) / SX, (z1-z0) / SX) VY = (DLC'-ULC ') / SY = ((x2-x0) / SY, (y2-y0) / SY, (z2-z0) / SY) VX - a vector, which moves in the 3D coordinate of a point rotated the plane of the screen when you shift to a single pixel on Horizontal VY - the same thing, but vertically. Why do we have these vectors? And then, knowing them, we can harvested from 3-m points easily find the coordinates of each pixel rotated the plane of the screen, and it is nothing like coordinate of the ray drawn from the focus of the camera at a given pixel screen. Here's something for him and find the coordinates by the formulas intersection with the wall of the tunnel. Of course, honestly cheat each pixel of the screen the above formula - a very laborious exercise, even for fairly powerful machines, not to mention the Speccy, so it is usually is calculated by these formulas in the texture coordinates for each of the 8th (or 16th) of every 8th (or 16th) line, ie in grid nodes, and then linearly interpolate them within each square 8 * 8 (or 16 * 16). Thus it is possible to achieve significant gain in speed with passable image quality. Similarly, by the way, you can create and the effect of rotation camera inside the sphere, only the formulas for ray tracing will somewhat different. I suggest the reader to take them, as well as improved algorithms for ray tracing inside the tunnel for that the camera could be not only on its axis, but any point inside the tunnel. For those interested in 3d graphics, I can recommend to read Demo.Design 3d programming FAQ, which once could find www.enlight.ru. There, he set out the basic minimum without knowledge and understanding of which work properly with 3D graphics quite problematic.
Other articles:
Similar articles:
В этот день... 24 November