3d stuff
Now this is some 3d stuff I thought I would share with you all. Some of this sort of popped up in my mind for no real reason, all the more since I'm currently developing a 2d board game, so I'm not sure what I'm doing thinking of this. Oh well...
* Perspective
Nowadays when you say 3d you think Perspective. Isometric and ortographic projections aren't found often (although most RTS's (Starcraft, Red Alert) use Isometric or 2d which looks a lot like Isometric). So how in all possible worlds do you do Perspective?
Okay, first. The origin must start with you. So point 0,0,0 is in fact our view point. Second, the center of the viewing area is the viewpoint. The viewing area is your screen, or whatever part of the screen you use for the 3d stuff. Now, when you need the view x and y coordinates (call them vx and vy), and you call your 3d coords ax, ay, and az (for actual x, actual y, actual z), use the following formulae:
vx = (ax * SX) / (az + SZ)
vy = (ay * SY) / (az + SZ)
where SX, SY, and SZ are scaling factors. In general you want SX=SY, and you want SZ to be pretty near SX and SY. SZ is needed to make the display less weird when you do rotations. Weird, you say? Well, if you've seen Windows 95's Maze screen saver, you'll notice that when you turn, the graphics seem to get sucked into the corners of the screen. Larger values of SZ help minimize that, but higher values of SZ require higher values of SX and SY, and a greater chance of OVERFLOW
* Surfaces
To plot a surface, merely project each corner using the above formula, then plot using your favorite fillpoly function. If you don't have access to a decent fillpoly function, and can't write your own, well... There are ways.
Now, a surface is merely a plane, and a plane can be defined by a set of three points not on a straight line. So you can greatly simplify your life by insisting that every surface be divided into triangles. And writing a filltriangle function isn't very hard...
Here's a sample triangle:
- P1
--
----
-----
P2 -------
------
-----
----
---
--
- P3
Now, let's think of a triangle as being composed of several horizontal lines. The ends of these lines are bounded by the three lines P1-P2, P2-P3, and P1-P3. So to fill a triangle, we only draw horizontal lines. We divide the triangle into two portions:
- P1
--
----
-----
P2 -------
and
P2 -------
------
-----
----
---
--
- P3
Each portion has a separate way of solving. In the upper portion, you solve the boundaries of each horizontal line by solving the x-coord on line P1-P3 for every y-coord from P1[y] to P2[y], and solving the x-coord of line P1-P2 for every y-coord from P1[y] to P2[y]. In the lower portion, you solve the boundaries of each horizontal line by solving the x-coord on line P1-P3 for every y-coord from P2[y] to P3[y], and solving the x-coord on line P2-P3 for every y-coord from P2[y] to P3[y]. What's more, for many graphics systems, drawing horizontal lines are faster than drawing other types of lines, so you have a "not bad" fillpoly function, albeit one limited to triangles.
* Hiding hidden areas
Now, one thing about 3d is that something that is in front hides something at the back. There are many ways of implementing this, the simplest being the so-called Painter's Algorithm. In this algorithm, you arrange the surface to be drawn from farthest to nearest. So when something in front is drawn, it overwrites everything in the back, therefore hiding them. Now the problem with this is that the PC's graphics system is so darn slow, even if you're already using a VLB (which has a max speed of 33 MHz I think). So you draw something which ends up being overwritten, taking time away from something which could have been written right in the first place. So the Painter's algorithm isn't very useful, right?
Wrong!
What's wrong is the way we thought of it! We thought that painters would draw the background, then draw over the background with the foreground. Which isn't very correct since trying to draw over could cause the background pigment to mix with the foreground pigment. What painters did was to draw the foreground, then draw the background in the holes in the foreground.
So what we do is to draw the surfaces nearest to farthest. Then we have a secondary buffer in main memory which flags which pixels have been drawn already and which have not been. Now, if you've implemented your own graphics system (you should, it's not that bad) you'll know that there are 8 pixels per byte written to the video system. So we can actually pack the secondary buffer to have 8 pixels per byte, with a set bit indicating that the pixel has been drawn, and a reset bit to indicate that the pixel is still not drawn. So what you do is, when you need to write a byte to the video system, you first get the equivalent byte in the secondary buffer, NOT it, then AND that byte with the byte to be written. This masks out parts which have been drawn already. If the result is a zero, there is no longer any need to write it, so you can skip the slow video system. Otherwise, write it to the system, and OR it to the secondary buffer to set the pixels you've just drawn.
Now this is some 3d stuff I thought I would share with you all. Some of this sort of popped up in my mind for no real reason, all the more since I'm currently developing a 2d board game, so I'm not sure what I'm doing thinking of this. Oh well...
* Perspective
Nowadays when you say 3d you think Perspective. Isometric and ortographic projections aren't found often (although most RTS's (Starcraft, Red Alert) use Isometric or 2d which looks a lot like Isometric). So how in all possible worlds do you do Perspective?
Okay, first. The origin must start with you. So point 0,0,0 is in fact our view point. Second, the center of the viewing area is the viewpoint. The viewing area is your screen, or whatever part of the screen you use for the 3d stuff. Now, when you need the view x and y coordinates (call them vx and vy), and you call your 3d coords ax, ay, and az (for actual x, actual y, actual z), use the following formulae:
vx = (ax * SX) / (az + SZ)
vy = (ay * SY) / (az + SZ)
where SX, SY, and SZ are scaling factors. In general you want SX=SY, and you want SZ to be pretty near SX and SY. SZ is needed to make the display less weird when you do rotations. Weird, you say? Well, if you've seen Windows 95's Maze screen saver, you'll notice that when you turn, the graphics seem to get sucked into the corners of the screen. Larger values of SZ help minimize that, but higher values of SZ require higher values of SX and SY, and a greater chance of OVERFLOW
* Surfaces
To plot a surface, merely project each corner using the above formula, then plot using your favorite fillpoly function. If you don't have access to a decent fillpoly function, and can't write your own, well... There are ways.
Now, a surface is merely a plane, and a plane can be defined by a set of three points not on a straight line. So you can greatly simplify your life by insisting that every surface be divided into triangles. And writing a filltriangle function isn't very hard...
Here's a sample triangle:
- P1
--
----
-----
P2 -------
------
-----
----
---
--
- P3
Now, let's think of a triangle as being composed of several horizontal lines. The ends of these lines are bounded by the three lines P1-P2, P2-P3, and P1-P3. So to fill a triangle, we only draw horizontal lines. We divide the triangle into two portions:
- P1
--
----
-----
P2 -------
and
P2 -------
------
-----
----
---
--
- P3
Each portion has a separate way of solving. In the upper portion, you solve the boundaries of each horizontal line by solving the x-coord on line P1-P3 for every y-coord from P1[y] to P2[y], and solving the x-coord of line P1-P2 for every y-coord from P1[y] to P2[y]. In the lower portion, you solve the boundaries of each horizontal line by solving the x-coord on line P1-P3 for every y-coord from P2[y] to P3[y], and solving the x-coord on line P2-P3 for every y-coord from P2[y] to P3[y]. What's more, for many graphics systems, drawing horizontal lines are faster than drawing other types of lines, so you have a "not bad" fillpoly function, albeit one limited to triangles.
* Hiding hidden areas
Now, one thing about 3d is that something that is in front hides something at the back. There are many ways of implementing this, the simplest being the so-called Painter's Algorithm. In this algorithm, you arrange the surface to be drawn from farthest to nearest. So when something in front is drawn, it overwrites everything in the back, therefore hiding them. Now the problem with this is that the PC's graphics system is so darn slow, even if you're already using a VLB (which has a max speed of 33 MHz I think). So you draw something which ends up being overwritten, taking time away from something which could have been written right in the first place. So the Painter's algorithm isn't very useful, right?
Wrong!
What's wrong is the way we thought of it! We thought that painters would draw the background, then draw over the background with the foreground. Which isn't very correct since trying to draw over could cause the background pigment to mix with the foreground pigment. What painters did was to draw the foreground, then draw the background in the holes in the foreground.
So what we do is to draw the surfaces nearest to farthest. Then we have a secondary buffer in main memory which flags which pixels have been drawn already and which have not been. Now, if you've implemented your own graphics system (you should, it's not that bad) you'll know that there are 8 pixels per byte written to the video system. So we can actually pack the secondary buffer to have 8 pixels per byte, with a set bit indicating that the pixel has been drawn, and a reset bit to indicate that the pixel is still not drawn. So what you do is, when you need to write a byte to the video system, you first get the equivalent byte in the secondary buffer, NOT it, then AND that byte with the byte to be written. This masks out parts which have been drawn already. If the result is a zero, there is no longer any need to write it, so you can skip the slow video system. Otherwise, write it to the system, and OR it to the secondary buffer to set the pixels you've just drawn.