Reprinted from http://www.gameres.com
3D Introduction We first start from the coordinate system. You may know that in 2D we often use the ren? Cartesian coordinate system to identify points on a plane. We use two-dimensional (x, y): x representation of horizontal axis coordinates, Y represents longitudinal axis coordinates. In the 3-dimensional coordinate system, we increase Z, generally used it to represent depth. So in order to represent a point of three-dimensional coordinate system, we use three parameters (x, y, z). There are different Cartesian three-dimensional systems here available. But they are all left-handed spirals or right hand spirals. The right hand spiral is the curl direction of the right hand finger points to the Z-axis positive direction, and the thumb is directed to the X-axis positive direction. The left hand spiral is the curved direction of the left hand finger to the Z-axis negative direction. In fact, we can rotate these coordinate systems in any direction, and they still maintain their own characteristics. In computer graphics, common coordinate systems are left-handed coordinate systems, so we also use it. :
The x positive axis is in the right y positive axis z positive axis points to the screen
Vector what is a vector? A few words, it is a collection of coordinates. First we start from two-dimensional vectors, (x, y): For example, vector P (4, 5) (general, we use -> represent vector). We believe that the vector P represents points (4, 5), which is an arrow from the origin pointing (4, 5). We talk about the length of the vector refers to the distance from the origin to this point. The two-dimensional distance calculation formula is | P | = SQRT (X ^ 2 y ^ 2) There is an interesting fact: at 1D (point on a single coordinate axis), square root is an absolute value. Let us discuss 3D vectors: P (4, -5, 9), its length is | P | = SQRT (x ^ 2 y ^ 2 z ^ 2) It represents a point in the 3D space in Cartesi . Or an arrow from the origin to this point represents the vector. In the relevant operational section, we discuss more knowledge.
The matrix starts, we started from simple start: We use the 2D matrix 4 by 4 matrices, why is 4 multi 4? Because we are in a three-dimensional coordinate system and we need additional rows and columns to complete the calculation work. In the two-dimensional coordinate system, we need 3 multiplication 3 matrices. It means that we have 4 horizontal parameters and 4 vertical parameters in 3D, a total of 16. For example: 4x4 unit matrix | 1 0 0 0 || 0 1 0 0 || 0 0 1 0 || 0 0 0 1 | Because any other matrix does not change, it is called a unit array. Another example, matrix is as follows: | 10 -7 22 45 || sin (a) cos (a) 34 32 || -35 28 17 6 || 45 -99 32 16 |
We have already introduced some very simple basic concepts, then what is the relationship between the above knowledge and 3D graphics? This section introduces the basic knowledge of 3D transformation and some of the other concepts. It is still mathematical knowledge. We want to discuss relevant vector and matrix operations. Let us start from two vectors and start:
(x1, y1, z1) (x2, y2, z2) = (x1 x2, y1 y2, z1 z2)
Very simple, now multiply the vector:
K? (x, y, z) = (kx, ky, kz) can be referred to as a point of the formula, as follows: (x1, y1, z1)? (x2, y2, z2) = x1x2 y1y2 Z1Z2 actually, the bottlement of the two vectors is removed by the multiplication of their mold, equal to the cosine of the two vector angles. So COS (v ^ w) = v? W / | V | | W |
Note "^" does not represent an index but is an angle of two vectors. The points can be used to calculate the angle of the light in the plane, and we will discuss in detail in the computing shadow section. Now discuss the fork:
(x1, y1, z1) x (x2, y2, z2) = (Y1Z2 - Z1Y2, Z1X2 - X1Z2, X1Y2 - Y1x2)
Force is very useful for the method of calculating the computing screen.
OK, we have finished the basic concept of the vector. We started two matrices and. It is very similar to the vector, and it will not be discussed here. Set i is a line of matrix, J is a column of the matrix, (i, j) is an element of the matrix. We discuss the important matrices related to 3D transformations. Two matrices are multiplied, and M x n <> N x M. For example: A 4x4 matrix multiply formula If A = (aij) 4x4, b = (bij) 4x4, then a x b = | s> A1JBJ1 S> A1JBJ2 S> A1JBJ3 S> A1JBJ4 | | || S> A2JBJ1 S> A2JBJ2 S> A2JBJ3 S> A2JBJ4 | | || S> A3JBJ1 S> A3JBJ2 S> A3JBJ3 S> A3JBJ4 | | || S> A4JBJ1 S> A4JBJ2 S> A4JBJ3 S> A4JBJ4 |
Where J = 1, 2, 3, 4
And if we can write under a line: CIK = S> 4, J = 1 Aijbjk (A1, A2, A3) x b = (SUM (Aibi1) B4, 1, SUM (Aibi2 B4, 2, SUM (Aibi3) B4, 3)
Now, we can try to multiply some matrices to understand the nature of matrix multiplication in units. We combine the matrix with the vector. There is a formula to multiply 3D vector by a 4x4 matrix (get another three-dimensional vector) if b = (bij) 4x4, then: (A1, A2, A3) x b = (S> Aibi1 B4, 1, S> AIBI2 B4, 2, S> Aibi3 B4, 3)>
This is the vector and matrix operation formula. From here, the connection between code and mathematics begins to be clear.
Transform We have seen this formula: T (TX, TY): (x, y) ==> (x TX, Y TY)
This is a panning equation in the two-dimensional card coordinate system. The following is a zoom formula:
s (k): (x, y) ==> (kx, ky)
Rotating equation: R (q): (x, y) ==> (x COS (q) - y sin (q), x sin (q) y cos (q)) The above is a two-dimensional formula, The form of a three-dimensional formula is still very similar. Translation Formula: T (TX, TY, TZ): (X, Y, Z) ==> (x TX, Y TY, Z TZ) Scaling Formula: (x, y, z) ==> (kx, ky, kz) Rotate formula (surrounding Z axis): R (q): (x, y, z) ==> (x COS (q) - y sin (q), x sin (q) ) Y COS (q), z) so we can write the same transformation formula as in two weeks. We get new vectors by multiplying the transformation matrix, the new vector will point to the transformation point. Here is all three-dimensional transform matrices:
Matrix of translation (TX, TY, TZ)
| 1 0 0 0 | | 0 1 0 0 || 0 0 1 0 || TX TY TZ 1 |
Zoom (SX, SY, SZ) matrix | SZ 0 0 0 || 0 SY 0 0 || 0 0 SX 0 || 0 0 0 1 | Matrix of X-axis rotation angle Q | 1 0 0 0 || COS (q) sin (q) 0 || 0 -sin (q) COS (Q) 0 || 0 0 0 1 |
Matrix of Y-axis rotating angle Q: | COS (q) 0 -sin (q) 0 || 0 1 0 0 | SIN (q) 0 COS (Q) 0 || 0 0 0 1 |
Matrix with Z-axis rotating angle Q: | COS (q) sin (q) 0 0 0 || -sin (q) cos (q) 0 0 || 0 0 1 0 || 0 0 0 1 |
So we can end the part about the transformation. We can perform any transformations for three-dimensional points through these matrices.
The plane and normal plane is flat, unlimited, pointing to the surface of a particular direction, can define the plane as follows: AX by CZ D = 0
Where a, b, and c is called a plane method, D is the distance from the plane to the origin. We can get the plane method by calculating two vectors on the plane. We need three points for these two vectors. P1, P2, P3 counterclockwise, you can get: vector 1 = p1 - p2
with
Vector 2 = P3 - P2
Calculation vector: method vector = vector 1 x Vector 2
Put D to the right of the equation: D = - (AX BY CZ)
or
D = - (a ?? 1.x b ?? 2.y c ?? 3.z)>
Or simpler:
D = - NORMAL? P1>
But for calculation of A, B, C components. The operation can be simplified as follows: A = Y1 (Z2 - Z3) Y2 (Z3 - Z1) Y3 (Z1 - Z2) B = Z1 (X2 - X3) Z2 (X3 - X1) Z3 (x1 - X2) C = x1 (Y2 - Y3) X2 (Y3 - Y1) x3 (Y1 - Y2) D = - X1 (Y2Z3 - Y3Z2) - X2 (Y3Z1 - Y1Z3) - X3 (Y1Z2 - Y2Z1)
Three-dimensional transform storage coordinates Implementation Matrix System Implementation Triangle System Create Transformation Matrix How to create a perspective transformation object
Storage coordinates first can be written in the Star Simulation Code. So what is our basic structure? How is the description of each object store? To solve this problem, first we think about another question: What kind of coordinate system we need? The most obvious answer is: Screen coordinate system: 2D coordinate system relative to the origin of the display: 3D coordinate system relative to the origin of the object, but we don't forget the intermediate used coordinate system, for example: World Coordinate system: Alignment (viewpoint) coordinate system relative to the 3D world: the transformation of the world coordinate system, the position of the observer in the origin of the world coordinate system.
Below is the basic structure of the coordinate:
// 2D coordinate Typedef struct {short x, y;} _ 2D;
// 3D coordinate Typedef struct {float x, y, z;} _ 3d;
Here, we define the coordinate structure called vertices. Because the term "vertices" refers to the intersection of two or more rhombus. Our vertices can simply think that the vector describes different systems.
// Different coordinate system coordinate Typedef struct {_3d local; _3d world; _3d aligned;} Vertex_t;
Implementation Matrix System We need to store our matrix in the 4x4 floating point matrix. So when we need to do transformation, we define the following matrix: float matrix [4] [4]; then we define some functions to copy the temporary matrix to the global matrix: void Mat_copy (Float Source [4] [4], float dest [4 ] [4]) {INT I, J; For (i = 0; i <4; i ) for (j = 0; j <4; j ) dest [i] [j] = source [i] [j] }
Very simple! Now let's write a function of multiplying two matrices. It can also understood that some of the above-mentioned formulas of the matrix multiplied are as follows:
Void Mat_Mult (Float Mat1 [4] [4], Float Mat2 [4] [4], Float Dest [4] [4]) {INT I, J; For (i = 0; i <4; i ) for ( J = 0; j <4; j ) DEST [i] [j] = mat1 [i] [0] * mat2 [0] [j] mat1 [i] [1] * mat2 [1] [j] MAT1 [I] [2] * MAT2 [2] [J] MAT1 [I] [3] * mat2 [3] [j];} // mat1 ---- matrix 1 // mat2 ---- matrix 2 // dest ---- New matrix after multiplication
Do you understand now? Now we design the vector with the matrix multiplied formula. Void vec_multmatrix (_3d * Source, Float Mat [4] [4], _ 3D * DEST) {dest-> x = source-> x * mat [0] [0] Source-> Y * MAT [1] [0 ] Source-> Z * Mat [2] [0] MAT [3] [0]; dest-> y = source-> x * mat [0] [1] source-> y * mat [1] [1] Source-> Z * MAT [2] [1] MAT [3] [1]; DEST-> Z = Source-> x * Mat [0] [2] Source-> Y * MAT [ 1] [2] Source-> Z * MAT [2] [2] MAT [3] [2];} // Source ----- Source vector (coordinate) // Mat ------ - Transform matrix // DEST ------- Target matrix (coordinate)
We have got a matrix conversion function, yet! ! // Note that the matrix transform here is different from the matrix transformation we have learned. Y = Tx, T is the transformation matrix, here is Y = xt, // Due to the matrix T is 4X4 matrix
Realizing Almost every C compiler with a triangulation system has a math library with triangular functions, but we need to use them every time we need a simple triangle function. The calculation of the sinusoidal and cosine is a large number of steps and divisions. In order to improve the calculation speed, we build our own triangulation function table. First determine the number of the angle you need, then replace it in these places: float sintable [256], costable [256]; then use macro definition, it will turn every angle into positive value, and is greater than The 360-degree angle performs a periodic conversion and then returns the required value. If the number of angles required is 2 power, then we can use "&" instead "%", which makes the program faster. For example 256. So try to select 2 power in the program.
Triangle system: #define sin (x) sintable [ABS ((int) x & 255)] # define cos (x) costable [ABS ((int) x & 255)]
Once we have defined what you need, establish an initialization function and call macro in the program. Void m3d_init () {INT D; for (D = 0; D <256; D ) {sintable [d] = sin (d * pi / 128.0); costable [d] = COS (D * pi / 128.0);} }
Establish transform matrix code written under the transformation matrix
Float Mat1 [4] [4], MAT2 [4] [4];
Void Mat_Identity (Float Mat [4] [4]) {MAT [0] [0] = 1; MAT [0] [1] = 0; MAT [0] [2] = 0; MAT [0] [3] = 0; MAT [1] [0] = 0; MAT [1] [1] = 1; MAT [1] [2] = 0; MAT [1] [3] = 0; MAT [2] [0] = 0; MAT [2] [1] = 0; MAT [2] [2] = 1; MAT [2] [3] = 0; MAT [3] [0] = 0; MAT [3] [1] = 0; MAT [3] [2] = 0; MAT [3] [3] = 1;} // Define unit array
Void TR_Translate (Float Matrix [4] [4], Float TX, Float Ty, Float Tmat [4] [4]; TMAT [0] [0] = 1; TMAT [0] [1] = 0 ; TMAT [0] [2] = 0; TMAT [0] [3] = 0; TMAT [1] [0] = 0; TMAT [1] [1] = 1; TMAT [1] [2] = 0 ; TMAT [1] [3] = 0; TMAT [2] [0] = 0; TMAT [2] [1] = 0; TMAT [2] [2] = 1; TMAT [2] [3] = 0 ; TMAT [3] [0] = TX; TMAT [3] [1] = TY ;TMAT [3] [2] = Tz; TMAT [3] [3] = 1; MAT_MULT (Matrix, TMAT, MAT1); Mat_copy;} // TX, TY.TZ ------------------- "source matrix and target matrix // matrix flat function
Void TR_Scale (Float Matrix [4] [4], Float SX, Float Sy, Float SM) {FLOAT SMAT [4] [4]; SMAT [0] [0] = SX; SMAT [0] [1] = 0 ; SMAT [0] [2] = 0; SMAT [0] [3] = 0; SMAT [1] [0] = 0; SMAT [1] [1] = Sy; SMAT [1] [2] = 0 SMAT [1] [3] = 0; SMAT [2] [0] = 0; SMAT [2] [1] = 0; SMAT [2] [2] = SZ; SMAT [2] [3] = 0 SMAT [3] [0] = 0; SMAT [3] [1] = 0; SMAT [3] [2] = 0; SMAT [3] [3] = 1; MAT_MULT (Matrix, SMAT, MAT1); Mat_copy (MAT1, Matrix);} // Matrix Zoom
Void TR_ROTATE (Float Matrix [4] [4], Int Ax, Int Ay, INT AZ) {Float XMat [4] [4], YMAT [4] [4], ZMAT [4] [4]; xmat [0 ] [0] = 1; XMAT [0] [1] = 0; XMAT [0] [2] = 0; XMAT [0] [3] = 0;
XMAT [1] [0] = 0; XMAT [1] [1] = COS (AX); XMAT [1] [2] = sin (AX); XMAT [1] [3] = 0; xmat [2] [0] = 0; XMAT [2] [1] = - sin (AX); XMAT [2] [2] = COS (AX); XMAT [2] [3] = 0; xmat [3] [0] = 0; XMAT [3] [1] = 0; XMAT [3] [2] = 0; XMAT [3] [3] = 1;
YMAT [0] [0] = COS (AY); YMAT [0] [1] = 0; YMAT [0] [2] = - sin (AY); YMAT [0] [3] = 0; ymat [1 ] [0] = 0; YMAT [1] [1] = 1; YMAT [1] [2] = 0; YMAT [1] [3] = 0; YMAT [2] [0] = sin (ay); YMAT [2] [1] = 0; YMAT [2] [2] = COS (AY); YMAT [2] [3] = 0; ymat [3] [0] = 0; ymat [3] [1] = 0; YMAT [3] [2] = 0; YMAT [3] [3] = 1;
ZMAT [0] [0] = COS (AZ); ZMAT [0] [1] = sin (AZ); ZMAT [0] [2] = 0; ZMAT [0] [3] = 0; zmat [1] [0] = - sin (AZ); ZMAT [1] [1] = COS (AZ); ZMAT [1] [2] = 0; ZMAT [1] [3] = 0; zmat [2] [0] = 0; zmat [2] [1] = 0; zmat [2] [2] = 1; zmat [2] [3] = 0; zmat [3] [0] = 0; zmat [3] [1] = 0; zmat [3] [2] = 0; ZMAT [3] [3] = 1;
MAT_MULT (Matrix, YMAT, MAT1); MAT_MULT (MAT1, XMAT, MAT2); MAT_MULT (MAT2, ZMAT, MATRIX);} // AX ------ Angle around X-axis // AY ------ - A angle // matrix rotation of angle // AZ ----------------------------------------------------------------------------------------------
How to establish perspective how to build a stereoscopic vision of an object, that is, some things on the display look close to us, while others are far away from us. Perspective issues have always been a problem around us. There are many ways to be used. Our 3D world to 2D screen projection formula: P (f) :( x, y, z) ==> (f * x / z xorigin, f * y / z yorigin)
Where F is "focus distance", it represents the distance from the observer to the screen, typically between 80 and 200 cm. XORIGIN and YORIGIN are the coordinates of the screen, (x, y, z) on the alignment mark. So what should the projection function?
#define focal_distance 200 // Define Focus Distance Void Project (Vertex_t * Vertex) {if (! Vertex-> Aligned.z) Vertex-> ALIGNED.Z = 1; Vertex-> Screen.x = Focal_Distance * Vertex-> aligned. x / vertex-> aligned.z xorigin; vertex-> screen.y = focal_distance * vertex-> aligned.y / vertex-> aligned.z yorigin;} // Get projection coordinates on the screen because 0 can not do Therefore, it is determined to Z.
Since we have mastered all the tools of all transform vertices, you should understand the main steps that need to be executed. First, initialize the local coordinates of each vertex, set the global matrix as the unit array. According to the size of the object, the global matrix is screwed according to the object's angle, and the global matrix is moved according to the position of the object, and the local coordinates Take the global matrix to get the world coordinate system. Set the global matrix as a unit array. The negative matrix of the observer's position is translated. The global matrix is rotated with the negative value of the observer's angle. The world coordinate system is The global matrix will take the alignment coordinate system. The projection is aligned to get the screen coordinate: Local coordinate system -> World Coordinate System -> Align Sittingal System -> Screen Coordinate Polygon Filled Polygon Structure Discovery Triangle Draw triangles
How do we store our polygons? First, we must know that in this state, the polygon is a two-dimensional polygon, and because the initial polygon is three-dimensional, we only need a temporary two-dimensional polygon, so we can set the maximum number of two-dimensional top points as a constant, not Waste memory:
2D structure: typedef struct {_2d points [20]; int adjustscount; int texture;} Polygon2D_t;
3D structure: typedef struct {Int count; int * vertex; int texture;
Vertex_t p, m, n;} polygon_t;
Why is the vertex array contain an integer value? Carefully think, for example, in the cubic, three polygonal common same vertices, so store and transform the same vertices in three polygons, the same vertices are wasting memory and time. We are more willing to store them in an object structure, and in the polygon structure, we will place the index of the corresponding vertex. Please see the following structure: typedef struct; int polegoncount; vertex_t * vertex; polygon_t * polygon; _3d scaling; _3d position; _3d angle; int adj beedupdate;} Object_t;
Discover the triangle because drawing a triangle is simpler than drawing any polygon, so we divide the polygon into three vertices. This method is very simple and direct: void poly_d_t * polygon {_2D P1, P2, P3; INT I;
P1 = polygon-> Points [0]; for (i = 1; i
How to draw triangles now How to get a triangular function? How can we draw a straight line related to how to discover the starting and solid X coordinates of each line. We distinguish two points and two numbers by defining two simple and useful macro definitions:
#define min (a, b) ((a) :( b)) # define max (a, b) ((a): (a) :( b)) # define maxpoint A, b) ((aY> by)? A: b) #define minpoint (A, b) ((by> ay)? A: b)
Then we define three macros to distinguish three points:
#define maxpoint3 (a, b, c) maxpoint (MaxPoint (a, b), maxpoint (b, c)) # define midpoint3 (a, b, c) MaxPoint (MINPOINT (A, B), MINPOINT (A, C) ) # Define MinPoint3 (A, B, C) MINPOINT (MINPOINT (A, B), MINPOINT (B, C)) You may notice that MidPoint3 macro does not always work properly, depending on the order of three points, For example, A
Void poly_triangle (_2d p1, _2d p2, _2d p3, char c) {_2D P1D, P2D, P3D; INT XD1, YD1, XD2, YD2, I; INT LX, RX;
First we sort three points: P1D = minPoint3 (P1, P2, P3); P2D = MidPoint3 (P2, P3, P1); P3D = MaxPoint3 (P3, P1, P2);
Why is it a bit of order change when calling these macros? (Author is not clear) May be passed by counterclockwise. Trying to change these macros Your screen shows garbage! Now we are not sure the middle point, so we do some checks, and in this state, the middle point to get seems to be wrong, so we correct:
IF (p2.y XD1 = p2d.x-p1d.x; yd1 = p2d.y-p1d.y; xd2 = p3d.x-p1d.x; yd2 = p3d.y-p1d.y; OK, the first step has been completed, if there is increment Y: if (yd1) for (i = p1d.y; i <= p2d.y; i ) { We calculate the X value with the start coordinates of X, plus the increment y between the current point and the starting point, multiplied by the opposite of the slope (x / y). Lx = p1d.x ((i - p1d.y) * xd1) / yd1; rx = p1d.x (i - p1d.y) * xd2) / yd2; if it is not in the same point, draw line segments, press The order passes these two points: IF (lx! = rx) VID_HLINE (MIN (LX, RX), Max (LX, RX), I, C);} Now we recall the first increment, and calculate the second edge xd1 = p3d.x -p2d.x; yd1 = p3d.y-p2d.y; IF (yd1) for (i = p2d.y; i <= p3d.y; i ) {lx = p1d.x ((i - p1d.y) * xd2) / yd2; rx = p2d.x ((( I - p2d.y) * xd1) / yd1; if (lx! = rx) VID_HLINE (MIN (LX, RX), Max (LX, RX), I, C);}} We have got a polygon fill formula, which is more simple for plane fillers: Void Vid_hline (int X1, int x2, int y, char c) {int x; for (x = x1; x <= x2; x ) Putpixel (x, Y, c);} SUTHERLAND-HODGMAN clip Overview Z-Clip Screen Clipart Overview Generally, we are more willing to clip our polygons. Must be cliptied by the edge of the screen, but must also be in front of the observation (we don't need to draw things behind the observer, when Z is very small). When we scrapped a polygon, we don't consider whether every point is within the limit, and we are more willing to increase the necessary vertices, so we need a third polygon structure: typedef struct {int count; _3d vertex [20];} cpolygon_t ; Since we have additional vertices to projection, we no longer proceeds the vertex, but projected 3D polygons to 2D polygons. Void M3D_Project (cpolygon_t * polygon, polygon2d_t * clipped, int focaldistance) {int v; for (v = 0; v Z-Clip Stick First We define the macro that calculates between the first point and the second point and the Z increment in the first point and the minimum z value. Then, we calculate the ratio, be careful not to be divided. Word zmin = 20; #define init_zdeltas dold = v2.z-v1.z; DNEW = zmin-v1.z; #define init_zclip init_zdeltas if (Dold) m = DNEW / DOLD; We build a function that mainly scrapped the parameters of the polygon pointer (it will record the vertices of the result of the scrapped vertex), the first vertex (the beginning of our scrap) and the second vertex (final): void clip_front (CPOLYGON_T * Polygon, _3D V1, _3D V2) {Float Dold, DNEW, M = 1; Init_zclip Now we must detect whether the edge is completely in the viewport, leave or enter the vision. If the edge does not completely in the viewport, we calculate the intersection of the viewport and the edge, represented by the M value, calculate with init_zclip. If the edge is in the viewport: if ((v1.z> = zmin) && (v2.z> = zmin)) Polygon-> Vertex [POLYGON-> Count ] = V2; If the edge is away from the viewport: IF ((v1.z> = zmin) && (v2.z Now we can write a complete polygon Z-clipboard. To be representative, define a macro to find an appropriate polygonal vertex in an object structure. #define vert (x) Object-> Vertex [Polygon-> Vertex [x]] Below is its function: void clip_z (Polygon_t * Polygon, Object_t * Object, cpolygon_t * zclipped) {INT D, V; ZCLIPPED-> count = 0; for (v = 0; V This function is quite simple: it only calls the FrontClip function to do a vertex exchange. The edge of the scrap screen scrapbook is the same as Z-clip, but we have four edges instead of one. So we need four different functions. However, they need the same incremental initialization: #define init_deltas dx = v2.x-v1.x; dy = v2.y-v1.y; #define init_clip init_deltas if (dx) m = DY / DX; Edge is: _2D Topleft, DownRight; In order to further simplify the use of _2d and _3d structures, we define two useful functions: _2D P2D (short x, short y) {_2d temp; temp.x = x; Temp.y = Y; return temp;} _ 3d P3D (float x, float y, float z) {_3D Temp; Temp.x = x; Temp.y = Y; TEMP.Z = z; return temp; Then use these two functions to specify the viewport: Topleft = P2D (0, 0); DOWNRIGHT = P2D (319, 199); The following is four edge clipping functions: / * ======================= Scared left edge =============== ========= * / void clip_left (POLYGON2D_T * POLYGON, _2D V1, _2D V2) {Float DX, DY, M = 1; init_clip // *********** OK ************ IF ((v1.x> = Topleft.x) && (v2.x> = TOPLEFT.X)) Polygon-> Points [Polygon-> PointScount ] = V2; / / ********* Leaving ********* iv ((v1.x> = Topleft.x) && (v2.x Void Clip_right (POLYGON2D_T * POLYGON, _2D V1, _2D V2) {Float DX, DY, M = 1; init_clip // *********** ok *********** * IF ((v1.x <= downright.x) && (v2.x <= downright.x)) Polygon-> Points [Polygon-> PointScount ] = v2; // ******** Leaving ********** IF ((v1.x <= DOWNRIGHT.X) && (v2.x> downright.x)) {polygon-> points [polygon-> pointscount] .x = DOWNRIGHT.X Polygon-> Points [Polygon-> PointScount ]. Y = v1.y m * (DOWNRIGHT.X-V1.X);} // ******* Entering ******** * If ((v1.x> downright.x) && (v2.x <= downright.x)) {Polygon-> Points [Polygon-> PointScount] .x = DOWNRIGHT.X; POLYGON-> Points [polygon-> PointScount ]. Y = v1.y m * (downright.x-v1.x); polygon-> points [polygon-> pointscount ] = v2;}} / * ============ =========== Clipart edge ================================ * / void clip_top (polygon2d_t * polygon, _2d v1, _2d V2) {FLOAT DX, DY, M = 1; init_clip // ************** = ((v1.y> = topft. Y) && (v2.y> = Topleft.y))) Polygon-> Points [POLYGON-> Pointscoun T ] = v2; // ********* Leaving ********** if ((v1.y> = topflet.y) && (v2.y ] .y = topft.y;} // ******** Entering ********* if ((v1.y Void Clip_bottom (POLYGON2D_T * POLYGON, _2D V1, _2D V2) {Float DX, DY, M = 1; init_clip // ************************** * IF ((v1.y <= downright.y) && (v2.y <= downright.y)) Polygon-> Points [Polygon-> PointScount ] = v2; // ******** Leaving ********** i ((v1.y <= downright.y) && (v2.y> downright.y)) {if (dx) polygon-> points [polygon-> pointscount] .x = V1.X (DOWNRIGHT.Y-V1.Y) / M; Else Polygon-> Points [Polygon-> PointScount] .x = v1.x; polygon-> Points [Polygon-> PointScount ]. Y = DOWNRIGHT.Y } // ******** Entering ********* if ((v1.y> downright.y) && (v2.y <= downright.y)) {if (dx) Polygon-> Points [Polygon-> PointScount] .x = v1.x (downright.y-v1.y) / m; Else Polygon-> Points [POLYGON-> Pointscount] .x = v1.x; polygon-> Points [POLYGON-> PointScount ]. Y = DOWNRIGHT.Y; POLYGON-> Points [Polygon-> PointScount ] = V2;}} In order to get a complete polygonal clip function, we need to define an additional global variable: polygon2d_t tmpoly; Void Clip_polygon (POLYGON2D_T * POLYGON, POLYGON2D_T * CLIPPED) {INT V, D; Clipped-> PointScount = 0; tMPPOLY.POINTSCOUNT = 0; For (v = 0; v The core of the Dilemna Covert Elimination Z-Buffer The DileMNA The core is its HSR system, so we must consider the one. In general, the most popular algorithms are: Time grids need to grow faster (especially overlap test) Can not accurately sort complex scene byte space partition tree especially fast, it is only possible to sort static polygonal Tree Z-Cache requires time with the number of polygons to linearly rendering any scenarios in the polygon greater than 5000 speed than the drawing algorithm, even if it is logically incorrect, very easy to achieve simple need, a lot of memory is very slow, so our choice It is Z-cache. Of course, other algorithms can be selected. The bottom surface eliminates these methods, we can easily eliminate the back of the polygon to save a lot of calculation time. First we define some useful functions to calculate the plane and normal and fill. Then we add texture and shadow calculations to this function. These variables are global variables: Float A, B, C, D; BOOL Backface; below is our engine function, each coordinate is floating point variable: void eNG3D_setPlane (Polygon_t * Polygon, Object_t * Object) {float x1 = VERT (0) .aligned.x; float x2 = VERT (1) .aligned.x; float x3 = VERT (2) .aligned.x; float y1 = VERT (0) .aligned.y; float y2 = VERT (1 ) .Aligned.y; float y3 = VERT (2) .aligned.y; float z1 = vert (0) .aligned.z; float z2 = VERT (1) .aligned.z; float z3 = VERT (2). Aligned.z; then we calculate each member of the flat equation: a = Y1 * (Z2-Z3) Y2 * (Z3-Z1) Y3 * (Z1-Z2); b = z1 * (x2-x3) Z2 * (X3-X1) Z3 * (X1-x2); C = x1 * (Y2-Y3) x2 * (Y3-Y1) x3 * (Y1-Y2); D = -x1 * (Y2 * Z3-Y3 * Z2) -X2 * (Y3 * Z1-Y1 * Z3) -X3 * (Y1 * Z2-Y2 * Z1); Check if it faces us or the back: backface = d <0;} The Z-Cache Z-Cache is to keep the Z coordinates of each point on the screen in a huge array, and when we check if it is approaching the observer or is behind the observer. We only draw it in the first case. So we have to calculate the Z value of each point. But first, we define the global tree group and assign space for him. (Memory is equal to the product of the direction and horizontal direction): typedef long zbuftype; zbuftype * zbuffer; zbuffer = (zbuftype *) malloc (zbufty) * MemorySize; we use long shaping as the Z-cache type, because we want Use a fixed point. We must remember setting each Z coordinate to get faster speed: int C; for (c = 0; c The following is a mathematical formula. How can I find Z coordinates? We only define the vertices, not every point of the polygon. In fact, what we need to do is the anti-transform of projection, the projection formula is: u = f? X / z with v = f? y / z Where u is the coordinate of X on the screen, the minimum value is xorigin, V is the coordinate of Y, the minimum yorigin. The flat formula is: AX BY CZ D = 0 Once we have already got isolated x and y, there are: x = uz / f with Y = vz / f If we replace variables in planar equation, the formula becomes: A (uz / f) b (vz / f) CZ = -d We can extract Z components: z (a (u / f) b (v / f) c) = -d So we get z: z = -d / (a (u / f) b (v / f) c) but because we need to perform the above division for each pixel, calculating 1 / z will increase the speed of the program : 1 / z = - (A (U / F) B (V / F) C) / D 1 / z = - (A / (FD)) U - (B / (FD)) V - C / D So starting at the beginning of a pixel program: 1 / z = - (A / (FD)) U1 - (B / (FD)) V - C / D For each pixel, the increment is :-( A / (FD))> Below is the program: #define fixmul (1 << 20) INT Offset = Y * ModeInfo.xResolution X1; INT i = x1-Origin.x, j = y-origin.y; float z_, dz_; zbuftype Z, Dz; // Initialize 1 / Z value (z: 1 / z) DZ _ = ((a / (float) focal_distance) / - d); z _ = ((DZ_ * i) ((B * J / (FLOAT) FOCAL_DISTANCE C) / -d); dz = dz_ * fixmul; z = z_ * fixmul; Then, for each pixel, we simple calculations: if (z> zbuffer [offset]) {zBuffer [offset] = z; screenbuffer [offset] = color;} z = dz; 3D texture map Overview Magic Digital Texture Map Perspective Correction Overview The first consideration when making a texture map is to establish a texture array and an initializing 3D texture coordinate. Texture will be stored in: #define maxtextures 16bitmap_t textures [maxtextures]; we allocate and load texture from the PCX file. It is assumed here that the texture size is 64x64. We use the texture coordinates of the Polygon_t structure: Vertex_T P, M, N; We initialize texture in a function that is called after the polygon is established. P is the origin of the texture, M is the horizontal end of the texture, and n is the end of the vertical line. Void Tex_Setup (POLYGON_T * POLYGON, OBJECT_T * Object) {Polygon-> p.local = p3d (Vert (1) .local.x, Vert (1) .local.y, Vert (1) .local.z); polygon -> m.local = p3d (Vert (0) .local.x, Vert (0) .local.y, vert (0) .local.z); polygon-> n.local = p3d (Vert (2). Local.x, Vert (2) .local.y, vert (2) .local.z); We need to transform texture coordinates as the vertices of any other object, so we need to build a world transform and a alignment transform function: void tr_object (Object_t * Object, float matrix [4] [4]) {Int v, p; for (V = 0; V Magical number Since we have got a changing texture coordinate, our goal is to discover how the pixel levels and vertical coordinates on the texture bitmap are drawn on the screen. Texture coordinates are called U and V. The following formula gives coordinates: u = a * texture_size / c And v = b * texture_size / c A, B, C meet the following equation: a = OX VX J HX i B = OY VY J HY I C = OZ VZ J HZ I Where O, H, V is the number of magic. It is calculated from the texture coordinates according to the following formula: ox = nXPY - NYPXHX = NYPZ - NZPYVX = NZPX - NXPZOY = MXPY - MyPxHy = MyPZ - MZPYVY = MXPX - MXPZOZ = MYNX - MXNYHZ = MZNY - MYNZVZ = MXNZ - MZNX Here, We don't explain the cause of the magic number. It looks like a strange fork. Texture Mapping Perspective Correction O, H, V number of calculations require some correction, so we add the following to the following to the ENG3D_SETPLANE: // Used to correct the error when the number becomes too big #define fix_factor 1/640 // Initialized texture vector p = polygon-> p.aligned; m = vec_difference (polygon-> m.aligned, polygon-> p.aligned); n = vec_difference (polygon-> n.aligned, polygon-> p.aligned ); P.x * = focal_distance; p.y * = focal_distance; M.x * = focal_distance; m.y * = focal_distance; N.X * = focal_distance; n.y * = focal_distance; The following is the implementation of VEC_DIFCERENCE: _3D vec_difference (_3d vector1, _3d vector2) {return p3d (vector1.x-vector2.x, vector1.y-vector2.y);} Then calculate the number of magicals. _3D O, H, V; ENG3D_SETPLANE: HX = (NY * PZ-NZ * PY) * fix_factor; vx = (NZ * PX-NX * PZ) * fix_factor; ox = (nx * py-ny * px) * fix_factor ; H.z = (m.z * n.y-m.y * n.z) * fix_factor; v.x = (m.x * n.z-m.z * n.x) * fix_factor; o.z = (m.y * n.x-m.x * n.y) * fix_factor; Hy = (my * pz-mz * py) * fix_factor; VY = (MZ * PX-MX * PZ) * fix_factor; = (mx * py-my * px) * fix_factor; below TEX_HLINE changes VID_HLINE to use texture Map (difficult to understand), first we must initialize the magic number coordinate: a = - ((long) O. × ((long) VX * (long) j) ((long) HX * (long) i)) * 64L; b = ((long) O.Y ((long) VY * (long) j) ((long) HY * (long) i)) * 64L; c = ((long) O.Z ((( LONG) VZ * (long) J) (long) Hz * (long) i))); long hx, hy, hz; int u, v; byte color = 0; byte * mapping = texTures [texture] .PICTURE ; Then multiply the HX and Hy by 64 so that we do not need to calculate every pixel. We use long plastics instead of floating point numbers: hx = H.x * -64; hy = H.Y * 64; Hz = H.z; For each pixel, change the last parameter and replace the original parameter: if (c) {u = a / c; v = b / C; color = mapping [(V & 63) << 6) (U & 63)] ; If (color) {zBuffer [offset] = z; screenbuffler [offset] = LightTable [light] [color];}} a = hx; b = hy; C = Hz; now we get your texture map! Three-dimensional mild dark calculation method vector calculation fork multiplying light table Calculation Vector In the 3D mathematical tutorial we have discussed the vector and normal vector, here we give some implementation: float vec_dotproduct (_3d vector1, _3d vector2) {return (Vector1.x * vector2.x vector1.y * vector2 .y vector1.z * vector2.z); _3D vec_crossproduct (_3d vector1, _3d vector2) {return p3d (vector1.y * vector2.z-vector1.z * vector2.y, vector1.x * vector2.z, vector1.x * vector2 .y-vector1.y * vector2.x);} void vec_normalize (_3d * vector) {float m = sqrt (vector-> x * vector-> x vector-> y * vector-> y vector-> z * Vector-> z); Vector-> x / = m; vector-> y / = m; vector-> z / = m;} For 3D light and dark, you need to add: // Calculate the plane method to increase the plane. PLANENORMAL = VEC_CROSSPRODUCT (P3D (X2-X1, Y2-Y1, Z2-Z1), P3D (X3-X1, Y3-Y1, Z3-Z1)) VEC_NORMALIZE (& PLANENORMAL); Calculate the fork integration as in the mathematical part, the angle between the two vectors is equal to their points (after they are normalized). In order to discover the light of the plane, we simply add the largest light of the world coordinate system of the world coordinate system of the ambient light and the maximum light intensity. Below is the code: Global variable definition: Word Ambientlight = 20; #define maxlight 32static Vertex_tightsource; Word Light; In setPlane functions: // Calculation vector and source of intensity Light = Maxlight * VEC_DOTPRODUCT (PLANENORMAL, LIGHTSOURCE.WORLD) AMBIENTLIGHT; if (Light> Maxlight) Light = Maxlight; IF (light <1) light = 1; Obviously, we need to initialize the light source, just as the vertices of the calculation method. // Initialization Light source LightSource.local = P3D (0, 0); MAT_IDENTITY (Matrix); TR_TRIX, 10, 10, 10); Tr_ROTATE (Matrix, 0, 128-32, 128); VEC_MULTMAATRIX (& LightSource.local, Matrix, & Lightsource.world); VEC_NORMALIZE (& LightSource.World); use light table The light table is a method of using light intensity based on palette technology. The best color match can be found on each strength. Christopher Lampton designed a large number of light source table generators in his fantasy garden book. Unfortunately, he uses its own format, so we can choose your own or other people's light table. Once we already have a light table, once we have a western table, you can load it in the global array. Byte LightTable [Maxlight 1] [256]
