How I Almost Real-Time Race Trails in 1997
I would like to share my memories of my attempts to make the “3D graphics engine” “do-it-yourself” almost in the pre-Internet era (as if it was already somewhere there, of course, but I actually didn’t have it). No America could be discovered, the revolution did not happen either, but there was a lot of effort, torment and fan. Over the years, the memory of many events is erased, details disappear, impressions fade - with numerous trips, the diskette box was lost and there were no artifacts from the events described.
The last 4 years of schooling took place in the Omsk physical education school, where a child (except physical education and a swear) was taught the C language, which, overlapping with the interest in graphics in games, allowed me to write something myself, trying to realize what I saw in games of that time . It was already difficult to surprise with 2D graphics, but Wolf 3D put me at a standstill for some time. Someone from the senior comrades said “yes, everything is on the bars”, and this allowed me to move from the dead point. Then I realized that the Bresenham algorithm can be applied to scaling the image column and some kind of parody on Wolf3D started to work out. I didn’t at all strive to create something playable (what a banality!), I liked the process of implementing graphical algorithms itself, the feeling that you know how it is done and can do it. At the final exams, I chose to take informatics and presented the “theoretical” part to teachers, greatly surprised them by the presence of a practical one. But a week before the exam, I saw Descent - a real three-dimensional game with textures. It was something impossible, I knew that 3DS existed, but there to render a cartoon a lot of time was needed, and then it flew right before our eyes.
At the graduation, instead of thumping like all normal children, I discussed with friends Duke Nukem (he is also a columnist), who I really liked with his humor and variety. And then one guy told me “look at Quake.” When I looked at the kwaku, I decided that it’s enough to endure it, it’s impossible, it’s real 3D graphics, no columns - and I absolutely don’t understand how this is done.
Now you can find any information in 5 minutes, but what to do then? I had books on 3D graphics, but they did not clarify the question at all. In the “Duma”, all faces turn on the screen in a trapezoid, pulling the texture is done by stretching the columns. But at the same time, I lost sight of the fact that horizontal non-linearity occurs, and in fact, the picture in the Duma is not completely realistic. So I missed the main principle of 3D graphics, discovered by Newton - " linearize it ." What will become the source of all subsequent problems and throwings.
Since we already know how to draw a trapezoid, let's draw on the screen each triangular facet. Yes, it cannot be painted over with columns, but geometry is not a very difficult thing, let's pass a beam through the camera’s every pixel and find where it intersects the face. This is practically ray tracing, only lite! Any student will write this formula in 5 minutes. The equation of the line:
Where , these are the coordinates of the pixel on the screen plane, this is the distance from the camera to the screen plane (camera at zero of the reference system), - parameter
The equation of the plane:
where n is normal, then the parameter (and therefore the coordinates) is easy to find:
Well, how easy it is, come to the realm of thepain of division. The computer folds well, multiplies reasonably (it's nothing more than additions and shifts), but division ... Division on my Pentium took 46 clock cycles. Even if 320 to 200, even if nothing more, then for every frame you need 3 million measures. And there are only 100 of my hemp, which means you can’t get faster than 30 fps in principle. And if the resolution is increased by 2 times? 7 fps? But the young enthusiast was not embarrassed.
Well, let's say we calculated the intersection point with the face, then we need to solve two problems:
Of course, I knew about the Z-buffer. But believe me, 99% of people who know the Z-buffer incorrectly imagine it, just like I incorrectly imagined it (there will be an explanation). In any case, I wanted to avoid unnecessary calculations (divisions are too hard), so I decided to use another technique read in the book - trees of a binary partition of space, they are also a BSP-tree. I always loved trees, the method of sorting by a tree always fascinated me with its magic, and here was its variation - I was debugging for 8 hours continuously, but I could!
The method allowed sorting the faces (at the same time, some faces were cut into parts) so that when displaying, “near” faces were drawn first, then distant ones. Therefore, if, when drawing the face, I saw that the pixel was already taken, then you can safely move on to the next pixel, the order problem is solved, it remains to pull the textures.
Glue
U, V coordinates? No, I have not heard. But do not blame me, because when you glue the wallpaper, you don’t think the same about them. You think that here you have one edge of the wallpaper (horizontal texture vector), here you have the other edge of the wallpaper (texture vertical vector), you lay them on the wall! So I, for each face, started 2 vectors for the edges of the texture and knowing the intersection point, I found the coordinates inside the texture.
Rendering earned, although not fast, but earned! I was able to 3D graphics! But what will we render? We need some kind of plot, some models, we need some kind of sound.
A walker or a flyer? This walker went and does not allow to feel all 3D beauty, definitely a fly! There will be our Descent.
I made a platform, put several buildings on it, pulled textures with windows on them, made a fountain of faces (it seemed like cool). What are we going to shoot? They shot nails in a quake, it wasn’t cool. For some reason unknown to culturologists, at that moment the word “bolt” (which needs to be hammered) was popular, and I realized that we would shoot with bolts - it turned out that they were screws - the slots looked very nice on the bolts driven into the building ".
Enemy? Well, I couldn’t make models of people, I did ... a flying ambulance, almost cubic, just slightly tilted her windshield. But the texture saved.
Sounds. The sounds of gunfire and explosions and the cry I got a flying machine I took from warcraft, the soundtrack was played by the acoustic The man who sold the world - I myself listened to metal, but I felt sorry for my parents, who had to listen to the same thing in the evenings while I was debugging.
In Windows 95, the sounds were not mixed, but it, the benefit of the university, the teacher told me about multithreading and I wrote the mixer in a separate stream - another success (windows 98 will be released in a year, where the sounds are mixed and this secret skill will become useless).
Is it possible to do better? I decided to rediscover the linearization and thought, what will happen if we precisely find the texture coordinates for the edges of the line, and the inside is crazy? I tried it - everything began to work many times faster, but serious distortions began near the buildings - like in a room of crooked mirrors. Correction of perspective - no, I have not heard.
Well, since I haven’t heard, then there’s nothing to do with it and I rejected this option.
Toward the end of the first year, I deigned to attend a special course on computer graphics and showed everything that was to the teacher. Probably we were equally surprised with him when he explained the linear interpolation of texture coordinates and normals, the approximate calculation of illumination, the estimation of the perspective error and its correction, and I showed him something that really worked.
In the second year, I tried to redo everything on the basis of new knowledge, but the default year was 98, and I saw the second quake on the 3D accelerator - it was fabulously beautiful. Then there was no money from the word at all, the accelerator was like a spaceship, for some reason I decided that I would not have it in the near future. And the interest in graphics programming began to fade away rapidly - but I got excited about the idea of ​​processing sound. But that's another story
PS Real texture coordinates change nonlinearly, for speed they are replaced by linear ones. But what happens to the Z-coordinate, and why is it turned over during the Z transformation? The answer to this question is given by the Z-buffer.
Background
The last 4 years of schooling took place in the Omsk physical education school, where a child (except physical education and a swear) was taught the C language, which, overlapping with the interest in graphics in games, allowed me to write something myself, trying to realize what I saw in games of that time . It was already difficult to surprise with 2D graphics, but Wolf 3D put me at a standstill for some time. Someone from the senior comrades said “yes, everything is on the bars”, and this allowed me to move from the dead point. Then I realized that the Bresenham algorithm can be applied to scaling the image column and some kind of parody on Wolf3D started to work out. I didn’t at all strive to create something playable (what a banality!), I liked the process of implementing graphical algorithms itself, the feeling that you know how it is done and can do it. At the final exams, I chose to take informatics and presented the “theoretical” part to teachers, greatly surprised them by the presence of a practical one. But a week before the exam, I saw Descent - a real three-dimensional game with textures. It was something impossible, I knew that 3DS existed, but there to render a cartoon a lot of time was needed, and then it flew right before our eyes.
At the graduation, instead of thumping like all normal children, I discussed with friends Duke Nukem (he is also a columnist), who I really liked with his humor and variety. And then one guy told me “look at Quake.” When I looked at the kwaku, I decided that it’s enough to endure it, it’s impossible, it’s real 3D graphics, no columns - and I absolutely don’t understand how this is done.
I was skilled in geometry
Now you can find any information in 5 minutes, but what to do then? I had books on 3D graphics, but they did not clarify the question at all. In the “Duma”, all faces turn on the screen in a trapezoid, pulling the texture is done by stretching the columns. But at the same time, I lost sight of the fact that horizontal non-linearity occurs, and in fact, the picture in the Duma is not completely realistic. So I missed the main principle of 3D graphics, discovered by Newton - " linearize it ." What will become the source of all subsequent problems and throwings.
Since we already know how to draw a trapezoid, let's draw on the screen each triangular facet. Yes, it cannot be painted over with columns, but geometry is not a very difficult thing, let's pass a beam through the camera’s every pixel and find where it intersects the face. This is practically ray tracing, only lite! Any student will write this formula in 5 minutes. The equation of the line:
Where , these are the coordinates of the pixel on the screen plane, this is the distance from the camera to the screen plane (camera at zero of the reference system), - parameter
The equation of the plane:
where n is normal, then the parameter (and therefore the coordinates) is easy to find:
Well, how easy it is, come to the realm of the
Well, let's say we calculated the intersection point with the face, then we need to solve two problems:
- decide whether to draw a face in this pixel, or if another face overlaps it
- find texture coordinates
Sort tree
Of course, I knew about the Z-buffer. But believe me, 99% of people who know the Z-buffer incorrectly imagine it, just like I incorrectly imagined it (there will be an explanation). In any case, I wanted to avoid unnecessary calculations (divisions are too hard), so I decided to use another technique read in the book - trees of a binary partition of space, they are also a BSP-tree. I always loved trees, the method of sorting by a tree always fascinated me with its magic, and here was its variation - I was debugging for 8 hours continuously, but I could!
The method allowed sorting the faces (at the same time, some faces were cut into parts) so that when displaying, “near” faces were drawn first, then distant ones. Therefore, if, when drawing the face, I saw that the pixel was already taken, then you can safely move on to the next pixel, the order problem is solved, it remains to pull the textures.
Glue wallpaper texture
U, V coordinates? No, I have not heard. But do not blame me, because when you glue the wallpaper, you don’t think the same about them. You think that here you have one edge of the wallpaper (horizontal texture vector), here you have the other edge of the wallpaper (texture vertical vector), you lay them on the wall! So I, for each face, started 2 vectors for the edges of the texture and knowing the intersection point, I found the coordinates inside the texture.
We need a plot and effects.
Rendering earned, although not fast, but earned! I was able to 3D graphics! But what will we render? We need some kind of plot, some models, we need some kind of sound.
A walker or a flyer? This walker went and does not allow to feel all 3D beauty, definitely a fly! There will be our Descent.
I made a platform, put several buildings on it, pulled textures with windows on them, made a fountain of faces (it seemed like cool). What are we going to shoot? They shot nails in a quake, it wasn’t cool. For some reason unknown to culturologists, at that moment the word “bolt” (which needs to be hammered) was popular, and I realized that we would shoot with bolts - it turned out that they were screws - the slots looked very nice on the bolts driven into the building ".
Enemy? Well, I couldn’t make models of people, I did ... a flying ambulance, almost cubic, just slightly tilted her windshield. But the texture saved.
Sounds. The sounds of gunfire and explosions and the cry I got a flying machine I took from warcraft, the soundtrack was played by the acoustic The man who sold the world - I myself listened to metal, but I felt sorry for my parents, who had to listen to the same thing in the evenings while I was debugging.
In Windows 95, the sounds were not mixed, but it, the benefit of the university, the teacher told me about multithreading and I wrote the mixer in a separate stream - another success (windows 98 will be released in a year, where the sounds are mixed and this secret skill will become useless).
Is it possible to do better? I decided to rediscover the linearization and thought, what will happen if we precisely find the texture coordinates for the edges of the line, and the inside is crazy? I tried it - everything began to work many times faster, but serious distortions began near the buildings - like in a room of crooked mirrors. Correction of perspective - no, I have not heard.
Well, since I haven’t heard, then there’s nothing to do with it and I rejected this option.
Almost the end of the story
Toward the end of the first year, I deigned to attend a special course on computer graphics and showed everything that was to the teacher. Probably we were equally surprised with him when he explained the linear interpolation of texture coordinates and normals, the approximate calculation of illumination, the estimation of the perspective error and its correction, and I showed him something that really worked.
In the second year, I tried to redo everything on the basis of new knowledge, but the default year was 98, and I saw the second quake on the 3D accelerator - it was fabulously beautiful. Then there was no money from the word at all, the accelerator was like a spaceship, for some reason I decided that I would not have it in the near future. And the interest in graphics programming began to fade away rapidly - but I got excited about the idea of ​​processing sound. But that's another story
PS Real texture coordinates change nonlinearly, for speed they are replaced by linear ones. But what happens to the Z-coordinate, and why is it turned over during the Z transformation? The answer to this question is given by the Z-buffer.
All Articles