Facet experience -- the development side of dragon game client

Due to the rendering part of my resume, the interview questions are a little biased towards the rendering direction , For reference only .
1、 How to find the of any vector in a two-dimensional plane x Axis and y Vector in the axial direction
2、 How to judge whether a vertex is inside or outside a triangle .（ More than one way ）

• Internal angle sum method ： Connection point P And the three vertices of the triangle to get three line segments PA,PB and PC, Find the included angle between these three line segments and each side of the triangle （ Use point multiplication to find the angle ）, If the sum of all the angles is 180 degree , So a little P In a triangle , Otherwise, it's not in .
• In the same direction ： Will point P Connect with a corner , Find the cross product of the vector and the vector formed by the connection of the two corners to get the vector , Calculate the three corners in turn , And follow the same method , Finally, we get three vectors , If the directions of the three vectors are the same, it means that the point P Inside the triangle , On the contrary, as long as the direction of one vector is different from the rest, it is not inside the triangle .
• Barycenter method ： We can take an angle of a triangle as the standard , Then the other two corners can be expressed as the angle moves in a certain direction to get . And any point inside the triangle can also be expressed as the movement of the standard point in a certain direction , This direction can be expressed by two triangular sides . So if you click P It can be expressed by this formula P = A + u * (C – A) + v * (B - A) , also u>=0,v>=0,（u+v）<=1, The point of P Inside the triangle , If the condition is not satisfied, it is not inside the triangle .
  If u=0,v=0 be P=A;
  If u=0,v=1 be P=B;
  If u=1,v=0 be P=C;
  When u+v=1 when , Express P The point is BC On the edge , So if P The point inside the triangle should u+v<=1

3、 Render pipeline
Three stages ： Application stage 、 Geometric stage 、 Grating stage
Application stage ：

• Prepare the scene data , Do coarse-grained removal
• Set the state of rendering
• call drawcall

Geometric stage ：

• Vertex shader ： Process input vertex information , Transform to crop space
• Surface subdivision shaders ： Subdivide elements
• Geometry shaders ： Generate more elements
• tailoring ： If it is in the field of view of the camera, it is directly discarded , If there are parts inside and outside the field of vision, you need to cut them to leave visible parts
• Screen mapping ： Convert crop space to screen space , The clipping space is [-1,1] In the area , The switch to 2 Dimension screen space .

Grating stage ：

• Triangle settings ： According to the previous vertex , Calculate the boundary of the triangle
• Triangle traversal ： Traverse entities , Calculate which elements are inside the triangle .
• Chip shader ： Shading the elements to be rendered
• Slice by slice operation ： Change the color 、 Deep buffer 、 Mix and so on .

4、 There are several transformations from model space to clipping space
Model space - World space - Perspective space - Cutting space
5、 If you transform a point from model space to world space
The point in world coordinates is the offset from the origin , We can get the transformation matrix that transforms the origin of world coordinates into the origin of model space in model space , The inverse transformation matrix of this transformation matrix can represent the world space , The origin of model space is obtained by transforming from the origin of world coordinates .
6、 How do shadows work
（1） Put the camera on the light source and rasterize it to get a texture map storing depth information
（2） Rasterize from the position of the real camera , If it is greater than the depth of the texture map at this point , It means that it is in shadow
7、 How to judge whether a linked list has rings
（1） Exhausting ： Traversing the linked list , Record the data that is traversed , If there is a repetition, there is a ring
（2） Use a hash table to store ： If the traversed data has been stored, there is a ring
（3） Speed pointer ： Two pointers point to the header node , A pointer traverses one by one , One pointer traverses two by two , If the value pointed to by the pointer has the same time , Description ring , Otherwise there is no ring .
8、 The geometric meaning of dot multiplication
Get the projection of one vector on another vector , Indicates the closeness of two vectors , The larger the value, the closer it is , The smaller the value, the less similar