Summary of the GAMES101 Series (5) - How Geometry is Expressed in Graphics

上一篇关于如何使用贴图的博客中我们讲了如何从贴图中提取我们想要的数据。

In this blog, we will briefly talk about the application of maps, and then transition from displacement maps to the expression of aggregates.

Application of Geometry

In GPU programming, the map is equal to the memory + range query in our CPU programming. We can use ByteGraph to paste the data we need in the calculation process and perform range queries on the data.

Therefore, the texture can not only be used to store the color information of the point on the object itself, but also can store information such as environment information, normal information, displacement information, etc.

Environmental map

As shown in the figure below, the reflection of the environment on this teapot needs to be calculated in real time, but the environment is infinity, so the relative position of the teapot to the environment remains unchanged, and the reflection result is also unchanged, so we can calculate it in advance. Then save it in the map. When rendering, just mix the color map of the teapot itself and the sampling result of the environment map.

Bump map (normal map)

If our geometry itself is relatively smooth, we want to create a sense of unevenness on a smooth surface, such as creating a sense of asphalt road on a plane, we can use the way of bump mapping, because the so-called bump feeling we see is also caused by the different angles of light reflection. We can directly intervene through bump mapping when calculating the reflection angle.

Displacement mapping

Just now we said that we can change the reflection angle of each point on the smooth surface by means of bump mapping to create a bump feeling. Then we can actually change the position of the point directly through displacement mapping when rendering. Rendering effect.

The difference between this method and bump mapping is that bump mapping does not change the position of the point, but only changes the direction of the normal, while the only mapping is to directly change the position of the point, which stores the position of the corresponding point based on the original position.

So here is a question involved, I changed the position, how to calculate the new normal?

The displacement map here is actually a representation of geometry, an explicit representation

Representation of geometry

There are many different ways of representing geometry, but there are mainly two, one is explicit and the other is implicit.

Implicit representation

The so-called implicit way, which represents the relationship satisfied by the points on the set, theoretically we can get this geometry by finding all the points that satisfy the relationship.

Common implicit representations are:

• algebraic surface
• level sets
• distance functions

algebraic

For the implicit representation, it represents the relationship satisfied by the points on the set, so it can be very simple to determine whether a point is on the surface of the geometry, and its disadvantage is that it is difficult for you to see what it represents, as shown below

** Here we may have a question, that is, can this way of doing things only represent relatively simple and regular graphics? **

In fact, implicit way can represent very complex graphics, here to provide two ideas:

The first idea is that if we have studied advanced mathematics, any function can be Fourier expanded in the way that multiple functions are added together. Similarly, we can add enough functions to fit any function, as long as you have this knowledge reserve and willing to spend time.

The second idea is more like the idea we have when we make charts, using multiple simple graph splicing or elimination methods (that is, Boolean operations) to do it, as shown in the following figure:

distance

As shown in the figure, this method is a variant of the boolean operation of the second idea we just mentioned

Signed Distance Function (SDF) is a mathematical representation commonly used in Computer Graphics and geometric processing. It is used to describe the shortest distance from a point to the surface of a shape, and also contains the position information of the point relative to the surface of the shape. The value of SDF can be positive, negative or zero:

1. When the point is located on the surface of the shape, the value of SDF is zero.
2. When the point is located inside the shape, the value of SDF is negative, indicating the shortest distance from the point to the surface of the shape.
3. When the point is located outside the shape, the value of SDF is positive, indicating the shortest distance from the point to the surface of the shape.

SDF is widely used in many applications, such as ray tracing, collision detection, fluid simulation, etc. Its advantage is that it can efficiently calculate the distance between points and shapes, while retaining the position information of points relative to shapes.

In the above figure, in the process of merging two balls, we first calculate the distance function of any point in space relative to the surfaces of the two spheres, and then weigh it, leaving the point with 0 as the result

If the three-dimensional one is more difficult to understand, we can use a two-dimensional diagram to see:

level

This method is also a variant. For the case where we cannot write an SDF, but can only write a rough table map, how do we get the result after fusion? Take a line as an example:

Explicit representation

The explicit representation is to directly give information to the out-point surface, or through parameter mapping, such as our very common Mesh. The displacement map we just mentioned is actually a mapping method, so we just said it is an explicit geometry representation.

Common explicit representations are:

• point cloud: point cloud
• polygon mesh: we common mesh
• Subdivision, simplification, regularization: subdivision, simplification, regularization

The disadvantage of explicit representation is that it is more difficult to determine whether a point is on the surface of the geometry. As shown in the figure below:

Point cloud

This is easier to understand, is a large number of points, these points do not need to connect, as long as enough, you can not see the gap.

Because it is a series of points, it is good to store it in an array, but the amount of data is very large

Polygon mesh

Specific usage scenarios

Bezier curve

A Bezier curve is a method of determining a curve from several points. It has very common applications. For example, if we use xmind, when we establish a connection between different labels, it will give us four points, of which two The fixed point is the position of the two labels that need to be connected, and the other two points are given to us to drag, and after dragging, we can change the shape of the curve. This curve is a cubic Bezier curve.

Bézier curve can have n times (n is greater than or equal to 2), we take quadratic Bézier curve as an example to explain, and so on

As shown in the figure, suppose we have three points. Our three points determine that our curve starts at $b_0 $and ends at $b_1 $. The tangent direction of the starting point needs to be $\ vec {b_0b_1} $, and the tangent direction of the end point needs to be $\ vec {b_1b_2} $

Suppose we have a point that moves from $b_0 $to $b_1 $in time, then at any point t, its position should be:

The ratio of $b_0b_0 ^ 1 $to $b_0 ^ 1b_1 $, the ratio of $b_1b_1 ^ 1 $to $b_1 ^ 1b_2 $, the ratio of $b_0 ^ 1b_0 ^ 2 $to $b_0 ^ 2b_1 ^ 1 $are all t/(1-t)

Quadratic Bézier curve is actually to use three points to get two new points proportionally, and then to get a point proportionally on the connection of the new two points

The cubic Bézier curve is actually four points that determine the curve, and the way it connects gradually becomes one point from four points

The higher Bezier curve is actually the recursion of the above process:

We just talked about how the Bézier curve is obtained, so how to express this process in a formula? The following is the result of the quadratic Bézier curve

The result is that we actually take the coefficients on the right side of the equation and it’s the expansion of $ (1 - t + t) ^ 2 $

For a higher-order Bézier curve, the formula is as follows, where B represents the expansion of the binomial distribution, that is, the probability of getting a result each time is t, then the probability of j results in n independent replicates:

Joining of Bézier curves

When our curve is a very high-order Bézier curve, it is actually difficult to control, as shown in the figure below:

So we can take the method of splicing multiple low-order Bézier curves:

Bessel surface

A Bézier surface is a surface controlled by 4 * 4 = 16 points:

As shown in the figure below, first of all, we can get a Bézier curve from the four points of each line horizontally. At this time, we get four Bézier curves, and then we imagine that there is a plane cut vertically, and four Bézier curves get four points, these four points can then determine a Bézier curve, and we can get a Bézier surface in the process of moving this numerical surface:

This process is actually a recursion process.

Mesh

The so-called mesh subdivision refers to splitting the polygons in the mesh to obtain a smoother effect

From the definition, we can see that this mesh subdivision actually has two things to do. The first thing is to split the polygon, and the second part is to adjust the split polygon, otherwise the simple split will not be The smoother effect will be obtained, for example, we connect the midpoints of the three sides of a triangle to obtain four triangles, but these four triangles are still on one surface, and there will be no smoother effect

Loop

It’s called Loop only because the person who invented the algorithm is called Loop.

The first step of the algorithm is to connect the vertices of the three sides of the triangle, and we have four triangles.

Next we need to update the position of the dots to make the split face smoother:

For the three new points, we update the coordinates in the following way

For the original three points, we update as follows:

Catmull-Clark

The limitation of Loop subdivision is obvious, it can only split triangles, so how do we split polygons?

It can be seen that only the first split will increase the number of singularities, that is, only the first time the triangle is split into three quadrilaterals, how to split the quadrilateral is a quadrilateral.

So how do we use the updated position of the new quadrilateral?

Mesh

Edge collapse

In fact, one edge is deleted, or the two vertices of the edge are merged into one.

、

This scheme sounds simple, but there are two problems, which side to remove, and where the position of the merged point can introduce the smallest error.

Note that in graphics, many of the so-called most only mean acceptable effects

Here we introduce a new concept called quadratic metric error, that is, the distance from the plane L2 where the distance is deleted and the minimum L2 distance

We only need to calculate the quadratic measurement error of all faces, and then select the smallest deletion in turn.

There is actually a problem here, that is, after each deletion, it will affect the position of some points, thus affecting their secondary measurement error. We need to recalculate and reorder to get the smallest one for deletion. Here we need to use the priority queue data structure, get the team head for deletion every time, then update the affected secondary measurement error, and then get it from the team head.