Basics of Games Production Mechanism of Game Contents 4 (Triangle, Texture Mapping)
GCC Academy
Hello, everyone
This is Lee Deukwoo of Game Math
During this time, we're going to talk about the topic of
triangle and texture mapping
The talk on triangles
is composed of three parts
Last time, we talked about the affine combination of two points
This time, we're going to talk about
the affine combination of three points
Next, we'll explain about the mesh structure that applies
the triangle made with the affine combination of three points
Then we'll learn about
the barycentric coordinate that we can utilize in triangles
The final is about texture mapping
We're going to learn about how to
apply images on the surface of a triangle
Triangle
First, I'm going to explain about the affine combination of three points
As you can see in the expression
for the affine combination of three points
each of the coefficients of the three points
can be used and combined
The sum of these three coefficients must be 1
Therefore, the last coefficient
must be equal to 1 minus the first and second coefficient
in order for us to form a point
With the affine combination expression that we made
If we pass P3 over and then proceed
P'-P3, then s outside the parenthesis of P1-P3
and t outside the parenthesis of P2-P3
Point minus point
Thus, it can be expressed with three vectors that start at P3
I expressed each as w, u, and v
Here, s and t is multiplied to each
The affine combination expression can be converted
into a vector expression like this
We learned earlier that
if vector u and v are two-dimensional vectors
and if they are linearly independent
the result of multiplying scalar values
in the sense of dimension
when we learned linear independency earlier
we've said that they create a flat surface
When we combine two linearly independent vectors
then we make a flat surface
Therefore, the combination of three points
can ultimately create all the points
belonging to the same surface
For this combination
each coefficient, which are s, t, and 1-s-t
For these three coefficients
if we decrease the range to greater than or equal to 0
and less than or equal to 1
let's take a look at each
When s=1, t=0
and 1-s-t is also 0, so it becomes the point P1
When t=1, P2
When s=0 and t is also 0
it becomes point P3 no matter what
Next, when we fix one value
and adjust the two values
the lines corresponding to that value
can be made
When we adjust all the values
the triangle area is made
Last time, when we combined two points
we've said that if "a" value goes from positive to negative infinity
then this means an abstract line
that extends out infinitely
However, when the coefficient is greater than or equal to 0
and less than 1
then we get a segment that we can express
with a clear start point and end point
Same thing goes for combining three points
If the range of each coefficient
is between 0 and 1
it forms an object
that we can actually configure
Therefore, this condition
where all the coefficients in an affine combination
are greater than 0 and less than 1
creates the range of the object
that we can visualize
And this is called a convex combination
As you can see here, up to here
was the condition we had in the original affine combination
The red one on the right
is the strengthened condition from the affine combination
and this represents the convex combination
So when it's not the convex combination
it creates an infinite line
or points belonging to a surface
But convex combination creates a visualized shape
A shape with a clear start
and an end
Then what does this convex mean?
It might be an unfamiliar word
In Korean, it means convex
You probably all know what convex is
The opposite of convex is concave
In English, it's convex
and concave
In daily life, convex and concave means
this, and going in like this
That's what how we use them in everyday life
In math, they wouldn't define it in vague forms like this
In math, how is convex determined?
This is how convex is determined
When there's an area
we select two arbitrary points in that area
When a line is drawn to connect the two points
and if the line always stays inside that area
then that area is called convex
On the other hand, for concave
when you select two points and draw a line
and if it goes outside of that area
we call it concave
To see it in pictures
this is a convex area
and this can be defined as
a concave area
Therefore, convexity
is ultimately in this form
Triangles, that we're going to talk about today
are one of the representative convex shapes
The properties of convex
are useful in graphics as well
but it's actually very useful in physics engine
When you use things like mesh collider
you have probably heard about convex a lot
That's the convex I just talked about
These convexing areas
become the foundation of mechanisms
that can calculate collisions
in a much more simple, easy way
Therefore, physics engine greatly prefers the convex
However, since we're using graphics
we'll just keep in mind that those are the properties
Then now, I'll explain about how convex
can actually be used in graphics
Before that, what would happen if we combine four points?
When we combine four points, it's the same for this
Among the four coefficients, the last coefficient
would be equal to 1 minus the three coefficients
When expressed in a vector expression, like the following
the coefficients of three vectors would be added
to be linearly combined
When all these vectors are linearly independent
this shape
will be able to infinitely make points
belonging to this three-dimensional space
through this combined expression
But if we limit the range of each coefficient
to greater than or equal to 0 and less than or equal to 1
then this would create a convex area
A three-dimensional space
made with this convex combination
looks like a tetrahedron
We usually call it a triangular pyramid
It becomes an area of tetrahedron
Within this area, no matter which two points are chosen
to draw a straight line
it cannot escape this tetrahedron
That was an explanation about convex
There are various convexes like these
We created a segment using two points
and that's also a convex
We combined three points to form a triangle
And we combined four points to form a tetrahedron
All these were convex areas
Using these convex shapes
we need to express objects in the three-dimensional space
that are similar to reality
The main reference structure we use here
is a reference called mesh
About this mesh structure
here, I organized the mesh structures
that are normally used
First of all
among the segment, triangle, and tetrahedron that we mentioned earlier
the most useful convex area
is actually the triangle
You might have guessed, but it's the triangle
That's because if we use triangles
we can express two-dimension very effectively
Not all graphics use
three-dimension
so we use two-dimensions as well
In the case of three-dimensions
we express the stereoscopy of three-dimension
but we don't show the insides
Especially for games
there's no reason to show the insides in detail
because we need to show them quickly
We don't think about the contents inside
We just use light and reflection
to quickly express the outer surface
For the back side as well, we think of the drawing
when we deal with the surface
It's because speed is important
So for 3D objects as well
when we use triangles
to put together the surfaces
we can express various forms of 3D
And that's why we prefer triangles
We can combine many triangles
to create complex objects like this
Then these complex objects
are ultimately a collection of triangles
The data that organized and saved those things
is called a mesh
There are various types of mesh structures
Right now, a majority of them
manage the vertex information and the triangle information separately
and this is called the Triangle List
Most of them use this method
To briefly explain about this triangle list
that's often used in mesh structures
Let's say that we're expressing a square like this
This square is composed of two triangles
Then this triangle
must include three points
in order for us to form a triangle
Since this square is composed of 2 triangles
if we have a maximum of 6 points
then we can express a square
If these triangles are connected
the second point and the 0th point
The very first 0th point and the second point
can be shared, actually
Then we can
use the data more efficiently
in cases when they're connected like this
So we'll just gather up the points
A total of four points has been used
We would gather up only the points in order
And we would use this order information
and utilize the information about this shared point as much as we can
to compose the list of triangles
That's what an index buffer is
We gather up the points, make the vertex buffer, and
then create the index buffer
about the triangle
So this index buffer
always includes information about the points composing the triangle
We don't write the coordinates of these points here
It's in the form of pointing to the index order
used in the vertex buffer
In the index buffer, there's always three times
the number of triangles
If you see here, the index buffer is
composed of two triangles, and therefore
3x2, so it would be composed of 6 elements
It's composed of 6 elements and
going in order, the 0th
the first point of the first triangle is number 0
Second point is 1, and third point is 2
That's how the first triangle is set up
For the second triangle, number 0, 2, and 3
That's how the second triangle is set
For information like the location
we record it in the vertex buffer, in detail
That's because there could be overlaps
In order to avoid overlapping where there's a lot of data
they're taken care of in the vertex buffer
And that's the composition
If we connect the points for each triangle and draw the lines
we can embody a mesh like this
Expressing a mesh like this
is usually called wireframe
For this wireframe
when drawing the line
Bresenham's line algorithm, that we talked about earlier, was used
When we handle mesh, one of the important concepts
that we need to know is barycentric coordinate
Since we're going to use triangles
the affine combinations and convex combinations
that we'll use from now on
will be a combination of three points
This coefficient that we use in the combination of three points
s, t, 1-s-t, these three coefficients
are scalar, right?
So we will combine scalars
and be able to make vectors
Just like that, the coordinate that made the 3D vector
is widely called
the barycentric coordinate
This is how we calculate the barycentric coordinate
Just like before, we proceed by converting points
into vectors
In this location where there's three points
let's say that there's an imaginary surface
Then for an arbitrary point on the surface
we can create these 3 vectors
We did this earlier
Then for this arbitrary point
we need to get the barycentric coordinate, s, t, 1-s-t
If each of the three coefficients
don't lie between 0 and 1
then that means it went outside of this triangle area
If at least one of them is not between 0 and 1
then no matter where we are at
it can be mathematically recognized
that it went outside the triangle no matter what
Then when we color the triangle
during the rasterization process, we would obtain
the barycentric coordinates of the pixels we would color
And as long as we prove that all the values
of the barycentric coordinate are between 0 and 1
then we can determine
that the pixel is inside the triangle
If we color just those pixels
then we would be able to color inside the triangle
Then we'll use an expression
to see how we obtain that barycentric coordinate
With these linear combination of vectors from the earlier expression
we can obtain the vector of the arbitrary point
On this arbitrary point, we'll do ·u, a dot product
Since the distributive property stands for dot products
we can put a dot product for each
through the distributive property
Additionally, we'll multiply u·u
Actually, this gets us a scalar value
and this is also a scalar, so when we multiply scalars
the distributive property of real numbers becomes valid
Therefore, you can just think of it as multiplying numbers
So when we multiply this to both sides, it will take this form
This form
If you look at the "s" side here
There's u·u, u·v and u·v, u·u
so you can see that they're the same
If you eliminate these
s would be eliminated, and you would be left with t
You would be left with t and
If you take "t" out and then divide the result
we can obtain this value of t
Using the same method, we'll
use u·v and v·v on both sides, and eliminate t
Then we get this value for s
Through these expressions, we can obtain s and t
and we can also obtain 1-s-t
Using those 3 coefficients
if all those values are greater than or equal to 0
and less than or equal to 1
then we can color the corresponding pixel
If we have a triangle, we can
obtain the pixels of the rectangle surrounding this triangle
Then all the pixels inside this rectangular area
would be candidates
Then we would go through each pixel
and decide whether to color it
or not
That decision
would be made by the barycentric coordinate
If we just draw the pixels that satisfy the convex condition
this is the actual implemented result
For the triangle
Or, two triangles are formed
We get a resulting screen of drawing two triangles
That's how we can put it
Texture mapping
I'll first talk about how to utilize
the barycentric coordinate that we mentioned last time
Using this barycentric coordinate, we can
determine whether it's inside the triangle
or outside the triangle
Barycentric coordinate is used to determine
simply whether it's inside or outside the triangle, but
it also checks how much influence that pixel inside the triangle
is receiving from each of the three points
So barycentric coordinate is very useful
for expressing the amount of influence
For example, if we have these 3 coefficients
if the first coefficient is 1
the rest of the coefficients would be 0
Then this is solely
influenced by P1
If these values have 1/3 each
If they have the value of 0.3333
then we can say that P1, P2, and P3 have uniform influence
That's why we call it the barycentric coordinate
Using this property of barycentric coordinate
when we color the inside of the triangle
we don't simply color them with a single color
We receive influence from each point
and have a linear effect
That's the foundation we get
As we explained about vertex array earlier
In the vertex array, we
only recorded the location of points
but here, on top of the location information
we give additional data
We give additional data and
do linear interpolation on the data
and decorate the inside of the triangle in various ways
Therefore, vertex
goes beyond the concept of point in affine space
It's a concept of point that
manages the additional properties as well
It's not an ordinary point
If we're drawing a triangle
let's say that we're setting the vertex coordinate and the color
Then this point would have a location coordinate
When we set a color coordinate for each point, like this
let's color this form of triangle by
doing linear interpolation on the inside
Then when we do linear interpolation on the
color of the vertex based on the barycentric coordinate
then we can create this pattern
where there's a rainbow gradation
If we use these characteristics
we can use it in a variety of effects
One of the main ones is
the topic of this lecture, texture mapping
Texture mapping is
bringing in an image and
using that image to fill in the triangle
It's a technique of using the color information of the image
and applying it on the surface of the triangle
When the images that we normally use
get taken into game production
it gets internally transformed into the form that can be used
That transformed data is called texture
For the triangle
before rasterization takes place, it's simply
a logical area formed of three vectors
or three points
Then it would be an area of image corresponding
to this logical area
But in order to utilize the images the same way
this vector system has to be used the same way
in the Cartesian coordinate system used by the triangle
When we normally open images in Photoshop or other programs
it's calculated as a pixel coordinate system that
increases from (0, 0) to the bottom right hand corner
Therefore, rather than using that coordinate
we need to use the flat coordinate system that's based on real numbers
Instead of the coordinate systems used in image programs
the mathematical coordinate system
or the Cartesian system, has to be used when expressing the image
When we express it that way
the horizontal and vertical range
has to be limited to [0, 1] no matter what the resolution is
when expressing the 2D coordinate
And this is called a UV coordinate
U refers to the horizontal
and V refers to the vertical
Using this UV coordinate
In the process of expressing triangle on the screen
the triangle will also go through rasterization in that step
And then texture
The texture, composed of UV coordinate, will also
have to obtain the color
from the texture corresponding to
the rasterization of triangle
In this perspective
then how are we going to get that color?
The original of the texture
is axtually a collection of pixels composed of integers
What we're expressing on the screen is pixel
and the data of the original image
composing the texture is also pixel
Calling both of them pixel would be confusing
So during the rendering process, these two
are distinguished in separate terms
The units forming up the texture image
is called a texel
And the final unit that shows on the monitor, or
the screen coordinate system, is called a pixel
Therefore, in order to choose the pixel, we
bring in the data of texel
and it's finally utilized to choose the pixel
The pixel area to be drawn on the triangle
and the texel area of the texture
have different sizes
Therefore, there are a few things to keep in mind
while delivering the texel information to pixel
We'll talk about those things now
When the two are completely the same, then
we just substitute the texel information into the pixel
This is usually not the case
First, if the texel is bigger than the pixel
Let me explain what this is
Let's say that we're drawing a very big triangle
But the actual image
is very small like this
Then what should we do?
In order to make this small image fill up the entire triangle
we would have to expand the image
This is when we're expanding it
When expanding, these two methods are usually used
When expanded, the UV coordinate
Inside the expanded triangle, there are
lots of pixels inside
For the barycentric coordinate corresponding to the pixel
the UV coordinate corresponding to that will be linearly calculated
and be made
There are lots of UV coordinates
but the ones corresponding to this
There actually aren't many texels in the original image
So we're very short on numbers, then what should we do?
Many pixels
would be colored by a single texel
Which texel does it take? The closest texel
It brings in the image of the texel as-is
From the final UV coordinate
we bring in the color information of the nearest texel
And this is called Nearest-neighbor interpolation
It's simply a technique of finding the nearest pixel
and bringing in the color
Second, if we proceed like this
the distribution of the color
is distinct, it's either this color or that color
Then we end up with a feel of chopped up pixel art
But in the perspective of 3D, rather than
expressing it as a pixel art
making it become blurry when you approach closer
would seem more realistic
So rather than having discontinued colors
it uses the UV coordinate of the calculated pixel as the standard
and determine the 4 related texels
It determines the color values of the texels
By interpolating the four colors
the final color is decided
Then in texel, there were only two kinds of information but
in the actual corresponding coordinate, the two will be interpolated
to form a new color
And that's called Bilinear-interpolation
Bilinear-interpolation and Nearest-neighbor interpolation
are the two commonly used methods
When setting up the texel in game engine
we usually go to Filter Mode in settings
Filter Mode is where we can select it
This is the screen of Unity Engine
Right now, Trilinear method is chosen
I'll explain about this method later
If you use Unity or Unreal
go to texture settings
and check the option of Filter Mode
After applying the Filter Mode
we've now chosen the method to apply texel on the pixel
Then there's a method of implementing this
For implementation
there's this entire image to be used in texture mapping
We may use the entire image or
we can also choose the UV coordinate of
a certain area, and then bring it in
For this example image
we put the basic (0, 0) coordinate of UV on the lower left side
And we set it so that it would increase to the right and upwards
But let's say that I only want to bring in the face
and do mapping on the triangle
But on the area of the triangle
when I map out the rectangular face on the triangle
the UV coordinate of each vertex
would just need to be matched as-is
Then for this triangle
there's a set vertex for each
And with the locations, we write down the
UV coordinates, with the values as-is
We write it on the vertex buffer
Then when we rasterize this, when we
start the rendering
as we draw each pixel
the UV coordinate of the corresponding pixel
can be calculated through interpolation
Then we just need to bring in the pixel information
corresponding to the texel
When you use the Nearest-neighbor interpolation method
as I've explained earlier
these small images
would just be expanded like pixel art
There's no blurry interpolation in-between
It just uses the nearest color as-is
Therefore, it creates an enlargened result
of the small image
So usually when dot games are
used in Unity, Unity doesn't call this Filter Mode
as Nearest-neighbor
It calls it "point"
The Filter Mode called point
is usually used when making 2D games
The resulting screen from implementing that
turns out like this
The original image used here is very small
The entire image is 64x64
It's a very small image, and the face is even smaller
It's a very small pixel, barely about 10 pixels
But in a big face like this
it went in almost uniformly
With that, we learned about
Nearest-neighbor interpolation among texture mapping
This time, the case when the texel is smaller than the pixel
In other words, we have a very big image
We have an image with high resolution
but the actual triangle that we'll draw is very small
This is a method to process this
in an efficient way
It's the other way around
If we choose a single pixel
out of many pixels that we can choose from
this can cause a smear effect
or an aliasing effect
And we would have a lot to calculate
In this case, the shrunk image
The shrunk image with good quality
is made in multiple beforehand
And as we go further, the shrunk image
is used instead of the original image
This method is used a lot in game implementation
In order to use it like this
we need to link the shrunk image and the original image
and create a new image
This is called Mipmap
Mipmap can be set in the texture option
We can decide whether to use the mipmap or not
I can't see it in this option
Oh, there are settings related to mipmap
Generate Mip Maps
So if I turn on this option, we are telling it to change
the image I brought, by setting the mipmap
The original image is a single image of a satellite
When it gets changed into texture after being imported into game engine
if we import it after checking off that option
the game engine makes these images automatically
Then the capacity of the image would increase
It increases about 1/3 greater
But when drawing an object that's far away
we can draw it effectively, so even though the capacity increases
the graphic processing becomes faster
So when this object
goes away from the camera by the set distance
then among the texture created with mipmap
we would use this
And when it gets even further, we would use this
In a way, mipmap is
texture that goes further away
based on the 3D distance
Therefore, we can call it three-dimensional
Based on the distance
Based on the area of the object
we select either Bilinear interpolation
or Nearest-neighbor interpolation
After that, there's one more thing that
we can consider, based on the distance
Area is important too, but if the distance is in the middle
If it's in the middle of the distance used by this mipmap
and the distance used by this mapmap
then the these two mipmaps
can interpolate the depth value for the selected location
So interpolating this in 3D
in a more complex interpolation
is called a Trilinear interpolation
Up until now, we
only mentioned the objects that show
their front view on the screen
In a way, for texture mapping
the technique is not the most important
It's important that we express an object realistically
with the textures
So there are different interpolation methods based on the area
but there are a few exceptions to these methods
One of the main ones is when the camera is here
and the object is placed in a slanted way
For those cases, even the trilinear methods
make it look blurry
In order to solve this problem
there's a technique that creates
and provides a separate image
that's optimized for the slanted angle
This is called
Anisotropic filtering
Let's call it anisotropic
It's called an anisotropic filtering
These example images for every angle
are prepared beforehand
and it switches between these
based on the angle
As explained earlier, in the case of Trilinear
these slanted areas
look blurry like this
But in the case of anisotropic filtering
it created good image sources after considering this
Therefore, when it's expressed with these images, it gets expressed
in a clean way
With that, we learned about the mechanism of texture mapping
and various parts to consider
when proceeding with texture mapping
With that, we have formed the foundation
for creating a realistic game
using basic texture mapping
That's all for today's lecture
Great job for listening to the lesson
Thank you
Triangle Affine combination of three sides P'=s·P1+t·P2+(1-s-t)·P3 Combination of 3 points can create all the points on the same plane
Convex combination: When all the coefficients of affine combination is between 0 and 1 0≤c_i≤1 Convex: When the line drawn between two points is...
Concave: When the line drawn between two points goes outside the area Tetrahedron formed with convex combination of four points
Mesh structure Mesh structure: Data containing vertex information and triangle information
Triangle List method is usually used, where vertex and triangle information are separately placed Wire frame: screen that expresses mesh by drawing...
Barycentric coordinate Coefficient used in combination of 3 points s, t, (1-s-t) Calculation expression of barycentric coordinate
t=[(w·u)(u·v)-(w·v)(u·u)] / [(u·v)^2-(v·v)(u·u)] s=[(w·v)(u·v)-(w·u)(v·v)] / [(u·v)^2-(v·v)(u·u)]
Barycentric coordinate value decides the pixel coloring
Texture mapping Utilizing barycentric coordinate Linear interpolation of vertex color based on the barycentric coordinate can decorate the triangle
Texture mapping Texture: image data converted into the form needed in game production Texture mapping: technique used to fill up triangle with image
Things to consider when delivering texel information to pixel When texel and pixel is uniform, substitute as-is
When texel is bigger than pixel Image expansion Nearest-neighbor interpolation: using the color information of the closest texel on the UV coordinate
Bilinear-interpolation: determining 4 related texels on the UV coordinate and deciding the final color through interpolation
When texel is bigger than pixel Image shrinkage Mipmap can be used to process the graphics of far-away objects quickly
Trilinear interpolation: calculating through 3D interpolation based on the area and distance
When triangle is placed slanted on the camera Anisotropic filtering: create and provide separate images that are optimized for the slanted angle