Basics of Games Production Mechanism of Game Contents 3 (Straight Line)
GCC Academy
Hello, everyone
This is Lee Deukwoo of Game Math
During this time, we're going to talk about lines
Last time, we defined a point
of affine space
We'll learn about how to draw a line using these points
We'll learn about the mathematical foundation for that
And in order to express the actual line
we'll learn about the application process of plotting the point
and drawing the line on the screen
Combination of Points in Affine Space
Last time, we defined a point
in affine space
We'll learn about how to draw a line using these points
And for that, we'll learn about the mathematical foundation
and in order to express the actual line
we'll learn about the application methods of how to plot points
and draw lines on the screen
First, I'll explain about the mathematical background
that composes the mathematical line
Last time, I've said that the operation between points
is impossible
That's because although we can add two points
the final coordinate of the resulting point
has a value of 2 for the last dimension
Therefore, we cannot set and move
in a transformation that we want
But when we combine two points
if we use a scalar value as an assistant and multiply it
then we can combine two points
It goes as the following
Let's try combining
two points in a two-dimensional space
Then we'll name arbitrary values x1, y1, x2, and y2
Since it's a point, the last dimension would be 1
Then the following coordinate would be made
When we multiply a and b here, the expression
would go as follows
But here, the value of the last dimension must be 1
in order for us to move by the amount we want
We would be able to move by the set scale
Therefore, we get the expression that
a+b must be equal to 1
Then b is ultimately 1-a
So it develops into an expression like this
This expression, when combined, ultimately
becomes a point, no matter what
With that, the operation between points is impossible
but using a scalar to operate two points
to form a new point
is called an affine combination
For affine combinations, as you can see here
you don't necessarily need to use two
Even with 3, 4, or 5
even with more numbers, as long as the coefficients add up to 1
it will eventually guarantee a point
Therefore, we can actually combine n number of points
infinitely, and form a point
However, there's one condition
that the sum of all the coefficients has to be 1
This must always stand true
Let's take a look at the results
of creating a point this way
If the value of a is 0
the value of P1 will disappear, and we'll only be left with P2
Therefore, when a=0, P2 is created
When a=1, only P1 would be left, and P2 would disappear
And if a=0.5, a midpoint would be created
with half and half of P1 and P2 mixed together
As you can see in the picture
the points created when a=0, 1, and 0.5
have been lined up here
And if a is set to other numbers, such as less than 0
or greater than 1
we can see that they form on the outside
of these two points
If you look here
it can create the shape of a line
and expand upon the line like this
But we wouldn't be able to plot an infinite number of points
to prove that they're all on the same line
Let's take a look at how we can prove it
Here
On this expression
If we say that the created point is P'
then we can make it as aP1+(1-a)P2
Here, we'll try moving the point
We'll move it to P2, then it will be aP1-aP2
That's how the expression would turn out
Here, if we put the a outside of the parenthesis
We can put it outside the parenthesis
What did we say that point-point was?
Point-point=vector
P'-P2 means
a vector going from P2 to P'
If I say that this is v
on top of "a", we got point minus point again
We'll put u here and call this v
This would be u, and this would be v, and I'll express it as a vector
We can express it with this kind of expression
Now, what does this mean?
Multiplying this vector by scalar is vector u
That means
How is the product of vector and scalar made?
It gets made along the same slope
Then the starting point is currently P2
and it's the same for both
Then this vector u that starts from P2 and goes to P'
and vector v that starts from P2 and goes to P1
have the same slope
That means, the points formed here
are ultimately along the same line
They will be made on a straight line
with the same slope as the line going from P2 to P1
We can prove this with numerical expressions
Therefore, the combination of these points
create points that are included on the line
If we increase the value of "a" infinitely
in the positive and negative direction, then an infinite line forms
These are the normal results
made from doing that
These can be divided based on the utilization methods
When we use a line
we use it in three types
Conceptually, going from infinity to infinity
with a single slope
is called a line
The definition of a line is, a line with the concept of infinity
Actually, when this goes to infinity
we wouldn't be able to actually draw it
Since we have to draw it infinitely, we wouldn't finish drawing it
There's another type
There's ray
It's called ray in English
You probably have heard of it a lot
With one point fixed
only one side increases infinitely
It's usually used when something is launched
or detected
It's a function that's used a lot during game production, ray casting
And there's a function that's mentioned a lot in graphics
called ray tracing
Ray casting is where
I can launch a line infinitely
from a set point
It's used in the concept of detecting something
and that's why they use the word ray
It holds the meaning of half-line
Same thing with ray tracing
We go backwards from the target screen
and track how the ray proceeds
to draw the picture, and because of that mechanism
it's called a ray tracing
Ray has the purpose of detecting something
and it also has the concept of infinity
so it's difficult in actually drawing the line as well
It's for calculation, so in the perspective of drawing something
it has the concept of infinity
so it's not fit for drawing
The end is uncertain
If the start point and the end point is certain
then we can draw the line
Rather than calling this a line
we call it a line segment, to be exact
The starting point and the ending point is clear
so we can draw the line, and that's the concept of
a segment
In order to form this
the coefficient "a" has to be greater than or equal to 0
and less than or equal to 1
Algorithm of Drawing a Line
Then in order to make a line like this
let's first learn about
how to express a point
In order to express an actual point on the screen
then rather than using the concept of point
directly from math
we would have to convert it based on the hardware of the screen
and then plot the point
The concept of a point in math
doesn't really have the rectangular shape
It's no more than setting the location
A location with no form
In order to put that on the screen
we have to understand the characteristic of a screen
First, for the characteristic of a screen, as you can see here
unlike the Cartesian coordinate system
that we normally see in math
it continues from the upper left hand corner
all the way to the lower right hand corner
And based on the size of resolution
it increases one by one from (0, 0)
as whole numbers
And in the screen, it's not an infinite number of points
being closely linked together
It's in the unit of whole numbers
It is distinctly composed
These are called pixels
This square is called a pixel
Ultimately, the collection of real numbers of the Cartesian coordinate system
are converted into real numbers on the screen coordinate system
We have to think of this way
of expressing
At the step of implementation, plotting a value of a vector
on the screen by converting it into a pixel
is called rasterization
Once we set the form of an object mathematically
the actual plotting process
involves actual the number of pixels
and the colors of the pixels
So even the number and color has to be set in this process
One of the things we need to implement here is
If the screen resolution is an odd number
(0, 0) would simply be the pixel in the center, of course
We just need to plot the pixel in the middle of the resolution
But if the resolution of the screen is an even number
we need to choose one
out of these four
For this case, based on the set rule
we set one of the four
so that one of the four would be chosen mathematically
We have to make an expression so that
the pixel would be chosen
In this picture, it's the bottom right one
The program we saw during the lectures
implemented the rasterization itself
and that program chose the bottom right pixel
to be used
On the other hand, graphic libraries like DirectX
have the rule of plotting the upper left one
That's called
the rasterization rule
One more thing
When we convert back from pixel
to the Cartesian coordinate system
the whole number here
has to be expressed as a real number again
A pixel is ultimately a square
Therefore, it has an area
When we convert this into a single value
it has to eventually be changed into
a representative value
Same thing for this, we have to set a rule
The program that we'll often use
uses the 0.5 and 0.5 in the middle
It uses the middle value
to extract the representative vector value
We need these rules
in order proceed with rasterization
as what you should know
With that, we learned about rasterization
From the mathematical concept of infinity
from the elemental concept of an infinite collection
in order to transport it into the screen
with a finite form of pixels
a few, actual optimistic methods need to be considered
Those various methods need to be used
to implement them
For example, when we draw a line that we mentioned earlier
we said that we can make a line when we increase
the value of "a" from 0 to 2
Then we can increase the value of "a"
all the way from 0 to 2, make a point
and we can also draw it by correlating each to a pixel
But how much do we need to increase it by?
Whether we need to increase it by 0.01
or by 1
will depend on the slope of the line
Therefore, just because we want to draw it in detail
and increase by 0.001
then the computer would be overloaded
even for drawing a simple line
So there's an effective way of drawing this
This is the Bresenham's line algorithm
or the line-drawing algorithm
To simply explain about this algorithm
the coordinates of the pixels on the screen coordinate system
are in whole numbers anyways
Therefore, when drawing a line, rather than using real numbers
if we only use whole numbers to draw
we can implement this very quickly
Here, we can see that it's composed of integers
This algorithm has been developed a long time ago
It was invented back when decimal calculation was very difficult
Back in 1962
Therefore, they came up with a way to draw a line
with minimum amount of load on the computer
Because of the principal of this algorithm
this is also called a midpoint algorithm
Then I'll explain about the implementation method
of this Bresenham's line algorithm
We'll divide the space of the screen
We'll divide the screen coordinate system into 8 parts
And we'll divide it into octants
Then 8 sides would be formed
We'll try expressing the lines used here
in the form of y=ax+b
Then in the screen coordinate system
when we're given the start point and the end point
we can solve for various things
First, we would be able to solve for the width
When we subtract the start from the end, we would get the width
and we would get the height
And the coordinates of the start point and the end point
would each be inputted
With these information
we'll learn about how we can draw
by only using integers
First, we'll proceed with drawing
the first octant
Here, in this area
it's less than 45 degrees
Drawing a line here means
that we're drawing a line between
0 degrees and 45 degrees
That means there's no steep slope
In other words, it goes as parallel as it can
or goes down just one unit
We cannot go
more than two units down
With that basic situation
let's transform the linear equation
First, substitute x0 and y0
And since the value of slope, a, is height/width
we can make this expression
Ultimately we can use the given values
to obtain the value of b
With this situation, I've explained about the first octant earlier
This can't pass the slope of 1
Therefore, it can only go parallel or one unit down
Therefore, we first plot the start point
Plot the first point
The next point can either go parallel
or go on unit down
Those two are the only possible results
Then how can we decide this?
That is the Midpoint Algorithm
We look at the midpoint and decide
if we're going to go as-is or go one step down
If we use the linear equation from earlier
to obtain the value of x0+1
when that value is less than y0+0.5
then the line goes this way
That means this needs to go parallel
and we need to plot the point here
If the actual linear value
is lower than this value
then that means this has to go one unit down
Then we need to learn the mathematical formula
to distinguish this
On this linear equation from earlier
we'll substitute x0+1 in place of x
x0+1
When we substitute x0+1
we get this expression, and it simplifies to this
Then this is the linear equation
It will be the actual value of the line we will draw
We're now going to compare this with y0+0.5
If that value is less than y0+0.5
then we're just going to draw parallel
The point will just be plotted to the side
So we'll make a comparative inequality
Here, we'll multiply w on each side
Since 0.5 is 1/2, we'll multiply 2, so multiply 2w
Ultimately, we'll check if 2h-w
is less than 0
If it's less than 0, we'll go one unit sideways
If it's greater than or equal to 0
we would plot the point one unit downwards
We can draw the next point
by choosing from either one
From here, let's say that we go on unit further
Then here, there are two possible cases
Actually, there are two midpoints
and three possible cases
If I go sideways
then this would also look at this midpoint
and decide whether it would go this way
or this way
But if I plotted the point on the bottom
then it would look at this midpoint and decide
whether it would go sideways or down
Anyways, it has to look at this situation and this situation
It has to look at the two midpoints
to decide whether it will go as-is or go down
This time, when we try calculating for these two midpoints
this one gets 4h-w
and the bottom point gets 4h-3w
Let's proceed once more
This one would have three midpoints
When we calculate the resulting value of these midpoints
this gives us 6h-w, 6h-3w, 6h-5w
It increases like this, and if you look at these discriminants
it first started with 2h-w
but it proceeds to 4h-w, 4h-3w, 6h-w, 6h-3w, 6h-5w
Just like that, they change with
a certain pattern
But when I move parallel
When I move parallel, I actually just need to think about
this one
And this one was 4h-w
If I go one unit down
it becomes 4h-3w
Same thing here
If I moved parallel
I just need to think about this one
And the discriminant for this is
6h-w, 6h-3w, 6h-5w
In other words, when we think of the normal pattern
as x increases
it's based on the plotted result as we increase one unit
If we just move parallel, sideways
then the discriminant simply needs to increase by 2h
If we go downwards, then
the discriminant increases by 2h-2w
That way, we can continuously obtain the values
with a consistent algorithm
Putting this in order, it's as follows
We first plot the point
Then, we see if it arrived to the end point
If it arrived at the end point, we would just end the line drawing
If not, we would first obtain the discriminant
That would be 2h-w
If 2h-w is less than 0
only the x value would be increased
and we would plot a point on the pixel on the right
And we would only add 2h to the discriminant
If it's not less than 0
then we increase x and y by one unit
We would plot the point underneath
On the discriminant, add 2h-2w
and change the discriminant value
On the increased value, plot the point
Since the discriminant has been changed
we use the new discriminant to decide
We repeat this logic until we reach the end point
and as a result, we'll form a line
I'll explain about how we'll proceed
with the rest of the octants
With that, we learned about drawing a line
in the first octant, the area less than
45 degrees
How do we plot points in the second octant?
This one has a deep slope
But if you change your thoughts a little
instead of increasing the x here
we increase the y, then it's technically
the same as the first octant
Here, we increased the x
but here, we're increasing the y
Then in the perspective of y
this has a slope of less than 1
then x won't increase
for more than a unit
Here, y didn't increase for more than a unit
But here, the x doesn't increase for more than a unit
Therefore, with the x switched to y
when we conduct the same algorithm
then we can calculate for second octant the same way
For the discriminant, h and w will be switched as well
We would start from 2w-h, and if it increases parallel to y
if it increases perpendicularly
downwards, then we add 2w
If it increased one unit toward the x axis
then we add 2w-2h and continuously change the discriminant
Here, for the third, fourth, fifth
sixth, seventh, and eighth octant
the proceeding direction
of x and y ultimately
only has the difference of positive or negative direction
Technically, it only divides into two types
Whether you're going to be based on x
or based on y
So from the previous algorithm
as long as we supplement the following elements
we can create lines
for all eight octants
in a very stable way
Whether the slope is low or steep
And whether the direction of x and y
is positive or negative
We just need to understand these two elements
and we can proceed with the generalized algorithm
With that, we learned about the basic, theoretical system
of creating a line mathematically
In order to change this into a line on the screen
we also learned about
how engineers applied this
in order to develop the line drawing algorithm
We need to know both the theory
and the actual application
in order to implement an efficient computer graphic
That way, we will be able to reach 60 frames that's needed on the game
through this effective implementation
That's all for this lecture
Great job for listening to this lesson, thank you
Combination of points in affine space Expression of affine combination Can add points by multiplying scalar in affine space
Affine combination: using scalar to add two points and create a new point
Expression of affine combination Σ (i = 0 to n) [c_i * P_i] s.t. Σ (i = 0 to n) [c_i] = 1
Points from affine combination forms on the same slope Types of lines
Line: Line going to infinity with a single slope (-∞<a<∞) Ray: Line with only one side going to infinity, with one point fixed (0≤a<∞)
Segment: Drawable line with a clear start point and end point (0≤a≤1)
Line drawing algorithm Expression of points Points on the screen can be expressed after converting to match the hardware
Real numbers of the Cartesian coordinate system are converted into whole numbers on the screen coordinate system Screen coordinate system: Increase...
Rasterization Pixel: Smallest unit forming up the image on the screen, element of integers
Rasterization: Process of converting the vector value of an object into pixels Need a rule for setting the representative value when converting...
Bresenham's line algorithm Only using integers to quickly draw a line and minimize computer overload
Drawing a line in first octant Can only go parallel or one unit down Discriminant 2h-w
When 2h-w<0 → parallel move, when 2h-w≥0 → one unit down x increases → parallel → add 2h x increases → one unit down → add 2h-2w
Processing the other octants Based on the direction of x and y, supplement the first octant algorithm
Elements to supplement Is the slope low or steep? Is the direction of x and y positive or negative?