WEBVTT

1
00:00:05.686 --> 00:00:09.854
Basics of Games
Production Mechanism of Game Contents 3 (Straight Line)

2
00:00:09.854 --> 00:00:12.111
GCC Academy

3
00:00:27.535 --> 00:00:29.035
Hello, everyone

4
00:00:29.035 --> 00:00:30.821
This is Lee Deukwoo of Game Math

5
00:00:30.821 --> 00:00:34.599
During this time, we're going to talk about lines

6
00:00:34.599 --> 00:00:37.249
Last time, we defined a point

7
00:00:37.249 --> 00:00:39.560
of affine space

8
00:00:39.560 --> 00:00:42.599
We'll learn about how to draw a line using these points

9
00:00:42.599 --> 00:00:45.959
We'll learn about the mathematical foundation for that

10
00:00:45.959 --> 00:00:48.639
And in order to express the actual line

11
00:00:48.639 --> 00:00:52.480
we'll learn about the application process of plotting the point

12
00:00:52.480 --> 00:00:54.840
and drawing the line on the screen

13
00:00:55.333 --> 00:00:58.996
Combination of Points in Affine Space

14
00:00:59.436 --> 00:01:01.794
Last time, we defined a point

15
00:01:01.794 --> 00:01:03.545
in affine space

16
00:01:03.545 --> 00:01:06.359
We'll learn about how to draw a line using these points

17
00:01:07.000 --> 00:01:10.250
And for that, we'll learn about the mathematical foundation

18
00:01:10.250 --> 00:01:14.100
and in order to express the actual line

19
00:01:14.100 --> 00:01:17.700
we'll learn about the application methods of how to plot points

20
00:01:17.700 --> 00:01:21.440
and draw lines on the screen

21
00:01:21.440 --> 00:01:25.440
First, I'll explain about the mathematical background

22
00:01:25.440 --> 00:01:28.840
that composes the mathematical line

23
00:01:28.840 --> 00:01:32.390
Last time, I've said that the operation between points

24
00:01:32.390 --> 00:01:34.160
is impossible

25
00:01:34.160 --> 00:01:37.460
That's because although we can add two points

26
00:01:37.460 --> 00:01:41.660
the final coordinate of the resulting point

27
00:01:41.660 --> 00:01:44.360
has a value of 2 for the last dimension

28
00:01:44.360 --> 00:01:47.960
Therefore, we cannot set and move

29
00:01:47.960 --> 00:01:52.919
in a transformation that we want

30
00:01:52.919 --> 00:01:55.919
But when we combine two points

31
00:01:55.919 --> 00:01:59.919
if we use a scalar value as an assistant and multiply it

32
00:01:59.919 --> 00:02:02.880
then we can combine two points

33
00:02:02.880 --> 00:02:05.480
It goes as the following

34
00:02:05.480 --> 00:02:07.480
Let's try combining

35
00:02:07.480 --> 00:02:10.180
two points in a two-dimensional space

36
00:02:10.180 --> 00:02:16.130
Then we'll name arbitrary values x1, y1, x2, and y2

37
00:02:16.130 --> 00:02:18.630
Since it's a point, the last dimension would be 1

38
00:02:18.630 --> 00:02:22.028
Then the following coordinate would be made

39
00:02:22.028 --> 00:02:24.628
When we multiply a and b here, the expression

40
00:02:24.628 --> 00:02:26.578
would go as follows

41
00:02:26.578 --> 00:02:31.928
But here, the value of the last dimension must be 1

42
00:02:31.928 --> 00:02:36.199
in order for us to move by the amount we want

43
00:02:36.199 --> 00:02:39.649
We would be able to move by the set scale

44
00:02:39.649 --> 00:02:43.549
Therefore, we get the expression that

45
00:02:43.549 --> 00:02:45.199
a+b must be equal to 1

46
00:02:45.199 --> 00:02:49.499
Then b is ultimately 1-a

47
00:02:49.499 --> 00:02:54.519
So it develops into an expression like this

48
00:02:54.519 --> 00:02:58.219
This expression, when combined, ultimately

49
00:02:58.219 --> 00:03:01.969
becomes a point, no matter what

50
00:03:01.969 --> 00:03:05.419
With that, the operation between points is impossible

51
00:03:05.419 --> 00:03:09.730
but using a scalar to operate two points

52
00:03:09.730 --> 00:03:12.680
to form a new point

53
00:03:12.680 --> 00:03:16.320
is called an affine combination

54
00:03:16.320 --> 00:03:19.555
For affine combinations, as you can see here

55
00:03:19.555 --> 00:03:21.805
you don't necessarily need to use two

56
00:03:21.805 --> 00:03:24.555
Even with 3, 4, or 5

57
00:03:24.555 --> 00:03:29.039
even with more numbers, as long as the coefficients add up to 1

58
00:03:29.039 --> 00:03:31.639
it will eventually guarantee a point

59
00:03:31.639 --> 00:03:34.539
Therefore, we can actually combine n number of points

60
00:03:34.539 --> 00:03:36.839
infinitely, and form a point

61
00:03:36.839 --> 00:03:40.039
However, there's one condition

62
00:03:40.039 --> 00:03:43.789
that the sum of all the coefficients has to be 1

63
00:03:43.789 --> 00:03:46.759
This must always stand true

64
00:03:46.759 --> 00:03:48.991
Let's take a look at the results

65
00:03:48.991 --> 00:03:51.741
of creating a point this way

66
00:03:51.741 --> 00:03:56.600
If the value of a is 0

67
00:03:56.600 --> 00:04:01.350
the value of P1 will disappear, and we'll only be left with P2

68
00:04:01.350 --> 00:04:06.039
Therefore, when a=0, P2 is created

69
00:04:06.039 --> 00:04:12.880
When a=1, only P1 would be left, and P2 would disappear

70
00:04:12.880 --> 00:04:17.880
And if a=0.5, a midpoint would be created

71
00:04:17.880 --> 00:04:22.679
with half and half of P1 and P2 mixed together

72
00:04:22.679 --> 00:04:24.729
As you can see in the picture

73
00:04:24.729 --> 00:04:28.979
the points created when a=0, 1, and 0.5

74
00:04:28.979 --> 00:04:31.800
have been lined up here

75
00:04:31.800 --> 00:04:36.292
And if a is set to other numbers, such as less than 0

76
00:04:36.292 --> 00:04:39.000
or greater than 1

77
00:04:39.000 --> 00:04:41.359
we can see that they form on the outside

78
00:04:41.359 --> 00:04:44.119
of these two points

79
00:04:44.119 --> 00:04:46.269
If you look here

80
00:04:46.269 --> 00:04:50.638
it can create the shape of a line

81
00:04:50.638 --> 00:04:55.360
and expand upon the line like this

82
00:04:55.360 --> 00:04:58.410
But we wouldn't be able to plot an infinite number of points

83
00:04:58.410 --> 00:05:01.710
to prove that they're all on the same line

84
00:05:01.710 --> 00:05:05.360
Let's take a look at how we can prove it

85
00:05:05.360 --> 00:05:08.313
Here

86
00:05:08.320 --> 00:05:09.637
On this expression

87
00:05:15.600 --> 00:05:16.750
On this expression

88
00:05:16.750 --> 00:05:19.500
If we say that the created point is P'

89
00:05:19.500 --> 00:05:26.839
then we can make it as aP1+(1-a)P2

90
00:05:26.839 --> 00:05:31.731
Here, we'll try moving the point

91
00:05:31.731 --> 00:05:38.162
We'll move it to P2, then it will be aP1-aP2

92
00:05:38.162 --> 00:05:41.512
That's how the expression would turn out

93
00:05:41.512 --> 00:05:46.000
Here, if we put the a outside of the parenthesis

94
00:05:46.000 --> 00:05:49.100
We can put it outside the parenthesis

95
00:05:49.100 --> 00:05:51.550
What did we say that point-point was?

96
00:05:51.550 --> 00:05:54.160
Point-point=vector

97
00:05:54.160 --> 00:05:57.010
P'-P2 means

98
00:05:57.010 --> 00:05:59.880
a vector going from P2 to P'

99
00:05:59.880 --> 00:06:02.930
If I say that this is v

100
00:06:02.930 --> 00:06:05.600
on top of "a", we got point minus point again

101
00:06:05.600 --> 00:06:08.920
We'll put u here and call this v

102
00:06:08.920 --> 00:06:14.044
This would be u, and this would be v, and I'll express it as a vector

103
00:06:16.795 --> 00:06:20.395
We can express it with this kind of expression

104
00:06:20.395 --> 00:06:22.079
Now, what does this mean?

105
00:06:22.079 --> 00:06:26.829
Multiplying this vector by scalar is vector u

106
00:06:26.829 --> 00:06:28.229
That means

107
00:06:28.229 --> 00:06:32.839
How is the product of vector and scalar made?

108
00:06:32.839 --> 00:06:37.389
It gets made along the same slope

109
00:06:37.389 --> 00:06:40.489
Then the starting point is currently P2

110
00:06:40.489 --> 00:06:42.600
and it's the same for both

111
00:06:42.600 --> 00:06:47.000
Then this vector u that starts from P2 and goes to P'

112
00:06:47.000 --> 00:06:49.100
and vector v that starts from P2 and goes to P1

113
00:06:49.100 --> 00:06:51.679
have the same slope

114
00:06:51.679 --> 00:06:56.379
That means, the points formed here

115
00:06:56.379 --> 00:06:58.879
are ultimately along the same line

116
00:06:58.879 --> 00:07:03.029
They will be made on a straight line

117
00:07:03.029 --> 00:07:05.119
with the same slope as the line going from P2 to P1

118
00:07:05.119 --> 00:07:09.519
We can prove this with numerical expressions

119
00:07:09.519 --> 00:07:14.769
Therefore, the combination of these points

120
00:07:14.769 --> 00:07:19.040
create points that are included on the line

121
00:07:19.040 --> 00:07:23.140
If we increase the value of "a" infinitely

122
00:07:23.140 --> 00:07:28.279
in the positive and negative direction, then an infinite line forms

123
00:07:28.279 --> 00:07:30.979
These are the normal results

124
00:07:30.979 --> 00:07:32.679
made from doing that

125
00:07:32.679 --> 00:07:40.559
These can be divided based on the utilization methods

126
00:07:40.559 --> 00:07:43.909
When we use a line

127
00:07:43.909 --> 00:07:47.640
we use it in three types

128
00:07:47.640 --> 00:07:51.790
Conceptually, going from infinity to infinity

129
00:07:51.790 --> 00:07:55.540
with a single slope

130
00:07:55.540 --> 00:07:56.679
is called a line

131
00:07:56.679 --> 00:08:01.600
The definition of a line is, a line with the concept of infinity

132
00:08:01.600 --> 00:08:03.521
Actually, when this goes to infinity

133
00:08:03.521 --> 00:08:05.279
we wouldn't be able to actually draw it

134
00:08:05.279 --> 00:08:09.519
Since we have to draw it infinitely, we wouldn't finish drawing it

135
00:08:09.519 --> 00:08:12.169
There's another type

136
00:08:12.169 --> 00:08:13.819
There's ray

137
00:08:13.819 --> 00:08:15.881
It's called ray in English

138
00:08:15.881 --> 00:08:17.640
You probably have heard of it a lot

139
00:08:17.640 --> 00:08:21.012
With one point fixed

140
00:08:21.012 --> 00:08:24.440
only one side increases infinitely

141
00:08:24.440 --> 00:08:28.090
It's usually used when something is launched

142
00:08:28.090 --> 00:08:30.279
or detected

143
00:08:30.279 --> 00:08:34.679
It's a function that's used a lot during game production, ray casting

144
00:08:34.679 --> 00:08:37.979
And there's a function that's mentioned a lot in graphics

145
00:08:37.979 --> 00:08:39.029
called ray tracing

146
00:08:39.029 --> 00:08:40.799
Ray casting is where

147
00:08:40.799 --> 00:08:43.051
I can launch a line infinitely

148
00:08:43.051 --> 00:08:47.799
from a set point

149
00:08:47.799 --> 00:08:51.261
It's used in the concept of detecting something

150
00:08:51.261 --> 00:08:53.399
and that's why they use the word ray

151
00:08:53.399 --> 00:08:55.899
It holds the meaning of half-line

152
00:08:55.899 --> 00:08:58.078
Same thing with ray tracing

153
00:08:58.078 --> 00:09:01.160
We go backwards from the target screen

154
00:09:01.160 --> 00:09:04.110
and track how the ray proceeds

155
00:09:04.110 --> 00:09:07.660
to draw the picture, and because of that mechanism

156
00:09:07.660 --> 00:09:10.799
it's called a ray tracing

157
00:09:10.799 --> 00:09:14.799
Ray has the purpose of detecting something

158
00:09:14.799 --> 00:09:17.326
and it also has the concept of infinity

159
00:09:17.326 --> 00:09:21.320
so it's difficult in actually drawing the line as well

160
00:09:21.320 --> 00:09:24.520
It's for calculation, so in the perspective of drawing something

161
00:09:24.520 --> 00:09:26.420
it has the concept of infinity

162
00:09:26.420 --> 00:09:28.279
so it's not fit for drawing

163
00:09:28.279 --> 00:09:30.529
The end is uncertain

164
00:09:30.529 --> 00:09:36.198
If the start point and the end point is certain

165
00:09:36.198 --> 00:09:38.079
then we can draw the line

166
00:09:38.079 --> 00:09:40.679
Rather than calling this a line

167
00:09:40.679 --> 00:09:45.280
we call it a line segment, to be exact

168
00:09:45.280 --> 00:09:48.030
The starting point and the ending point is clear

169
00:09:48.030 --> 00:09:51.630
so we can draw the line, and that's the concept of

170
00:09:51.630 --> 00:09:53.719
a segment

171
00:09:53.719 --> 00:09:56.021
In order to form this

172
00:09:56.021 --> 00:09:59.071
the coefficient "a" has to be greater than or equal to 0

173
00:09:59.071 --> 00:10:03.155
and less than or equal to 1

174
00:10:03.936 --> 00:10:07.599
Algorithm of Drawing a Line

175
00:10:08.139 --> 00:10:12.189
Then in order to make a line like this

176
00:10:12.189 --> 00:10:14.520
let's first learn about

177
00:10:14.520 --> 00:10:16.560
how to express a point

178
00:10:16.560 --> 00:10:21.710
In order to express an actual point on the screen

179
00:10:21.710 --> 00:10:24.660
then rather than using the concept of point

180
00:10:24.660 --> 00:10:26.559
directly from math

181
00:10:26.559 --> 00:10:30.759
we would have to convert it based on the hardware of the screen

182
00:10:30.759 --> 00:10:33.879
and then plot the point

183
00:10:33.879 --> 00:10:36.329
The concept of a point in math

184
00:10:36.329 --> 00:10:39.719
doesn't really have the rectangular shape

185
00:10:39.719 --> 00:10:41.569
It's no more than setting the location

186
00:10:41.569 --> 00:10:44.599
A location with no form

187
00:10:44.599 --> 00:10:47.299
In order to put that on the screen

188
00:10:47.299 --> 00:10:50.680
we have to understand the characteristic of a screen

189
00:10:50.680 --> 00:10:54.230
First, for the characteristic of a screen, as you can see here

190
00:10:54.230 --> 00:10:57.080
unlike the Cartesian coordinate system

191
00:10:57.080 --> 00:10:59.000
that we normally see in math

192
00:10:59.000 --> 00:11:01.521
it continues from the upper left hand corner

193
00:11:01.521 --> 00:11:05.160
all the way to the lower right hand corner

194
00:11:05.160 --> 00:11:09.328
And based on the size of resolution

195
00:11:09.328 --> 00:11:12.028
it increases one by one from (0, 0)

196
00:11:12.028 --> 00:11:15.400
as whole numbers

197
00:11:15.400 --> 00:11:20.302
And in the screen, it's not an infinite number of points

198
00:11:20.302 --> 00:11:23.400
being closely linked together

199
00:11:23.400 --> 00:11:27.800
It's in the unit of whole numbers

200
00:11:27.800 --> 00:11:30.120
It is distinctly composed

201
00:11:30.120 --> 00:11:32.341
These are called pixels

202
00:11:32.341 --> 00:11:35.040
This square is called a pixel

203
00:11:35.040 --> 00:11:40.080
Ultimately, the collection of real numbers of the Cartesian coordinate system

204
00:11:40.080 --> 00:11:44.208
are converted into real numbers on the screen coordinate system

205
00:11:44.208 --> 00:11:47.561
We have to think of this way

206
00:11:47.561 --> 00:11:49.919
of expressing

207
00:11:49.919 --> 00:11:54.919
At the step of implementation, plotting a value of a vector

208
00:11:54.919 --> 00:11:59.269
on the screen by converting it into a pixel

209
00:11:59.269 --> 00:12:02.959
is called rasterization

210
00:12:02.959 --> 00:12:06.459
Once we set the form of an object mathematically

211
00:12:06.459 --> 00:12:10.259
the actual plotting process

212
00:12:10.259 --> 00:12:14.480
involves actual the number of pixels

213
00:12:14.480 --> 00:12:17.880
and the colors of the pixels

214
00:12:17.880 --> 00:12:23.747
So even the number and color has to be set in this process

215
00:12:23.747 --> 00:12:26.697
One of the things we need to implement here is

216
00:12:26.697 --> 00:12:30.347
If the screen resolution is an odd number

217
00:12:30.347 --> 00:12:35.801
(0, 0) would simply be the pixel in the center, of course

218
00:12:35.801 --> 00:12:39.201
We just need to plot the pixel in the middle of the resolution

219
00:12:39.201 --> 00:12:43.600
But if the resolution of the screen is an even number

220
00:12:43.600 --> 00:12:47.000
we need to choose one

221
00:12:47.000 --> 00:12:49.639
out of these four

222
00:12:49.639 --> 00:12:53.039
For this case, based on the set rule

223
00:12:53.039 --> 00:12:56.651
we set one of the four

224
00:12:56.651 --> 00:12:59.423
so that one of the four would be chosen mathematically

225
00:12:59.423 --> 00:13:02.069
We have to make an expression so that

226
00:13:02.069 --> 00:13:03.600
the pixel would be chosen

227
00:13:03.600 --> 00:13:06.100
In this picture, it's the bottom right one

228
00:13:06.100 --> 00:13:10.624
The program we saw during the lectures

229
00:13:10.624 --> 00:13:13.039
implemented the rasterization itself

230
00:13:13.039 --> 00:13:17.239
and that program chose the bottom right pixel

231
00:13:17.239 --> 00:13:18.800
to be used

232
00:13:18.800 --> 00:13:22.200
On the other hand, graphic libraries like DirectX

233
00:13:22.200 --> 00:13:26.080
have the rule of plotting the upper left one

234
00:13:26.080 --> 00:13:28.280
That's called

235
00:13:28.280 --> 00:13:31.399
the rasterization rule

236
00:13:31.399 --> 00:13:33.761
One more thing

237
00:13:33.761 --> 00:13:38.461
When we convert back from pixel

238
00:13:38.461 --> 00:13:42.080
to the Cartesian coordinate system

239
00:13:42.080 --> 00:13:44.030
the whole number here

240
00:13:44.030 --> 00:13:46.230
has to be expressed as a real number again

241
00:13:46.230 --> 00:13:48.380
A pixel is ultimately a square

242
00:13:48.380 --> 00:13:50.240
Therefore, it has an area

243
00:13:50.240 --> 00:13:54.590
When we convert this into a single value

244
00:13:54.590 --> 00:13:57.540
it has to eventually be changed into

245
00:13:57.540 --> 00:13:59.119
a representative value

246
00:13:59.119 --> 00:14:04.520
Same thing for this, we have to set a rule

247
00:14:04.520 --> 00:14:07.770
The program that we'll often use

248
00:14:07.770 --> 00:14:11.479
uses the 0.5 and 0.5 in the middle

249
00:14:11.479 --> 00:14:15.129
It uses the middle value

250
00:14:15.129 --> 00:14:19.919
to extract the representative vector value

251
00:14:19.919 --> 00:14:22.269
We need these rules

252
00:14:22.269 --> 00:14:24.419
in order proceed with rasterization

253
00:14:24.419 --> 00:14:26.839
as what you should know

254
00:14:26.839 --> 00:14:32.920
With that, we learned about rasterization

255
00:14:32.920 --> 00:14:37.470
From the mathematical concept of infinity

256
00:14:37.470 --> 00:14:41.000
from the elemental concept of an infinite collection

257
00:14:41.000 --> 00:14:43.950
in order to transport it into the screen

258
00:14:43.950 --> 00:14:47.399
with a finite form of pixels

259
00:14:47.399 --> 00:14:53.559
a few, actual optimistic methods need to be considered

260
00:14:53.559 --> 00:14:56.909
Those various methods need to be used

261
00:14:56.909 --> 00:14:58.760
to implement them

262
00:14:58.760 --> 00:15:02.720
For example, when we draw a line that we mentioned earlier

263
00:15:02.720 --> 00:15:07.120
we said that we can make a line when we increase

264
00:15:07.120 --> 00:15:09.119
the value of "a" from 0 to 2

265
00:15:09.119 --> 00:15:11.719
Then we can increase the value of "a"

266
00:15:11.719 --> 00:15:13.799
all the way from 0 to 2, make a point

267
00:15:13.799 --> 00:15:17.559
and we can also draw it by correlating each to a pixel

268
00:15:17.559 --> 00:15:20.872
But how much do we need to increase it by?

269
00:15:20.872 --> 00:15:23.279
Whether we need to increase it by 0.01

270
00:15:23.279 --> 00:15:25.379
or by 1

271
00:15:25.379 --> 00:15:28.839
will depend on the slope of the line

272
00:15:28.839 --> 00:15:33.470
Therefore, just because we want to draw it in detail

273
00:15:33.470 --> 00:15:37.519
and increase by 0.001

274
00:15:37.519 --> 00:15:39.669
then the computer would be overloaded

275
00:15:39.669 --> 00:15:42.079
even for drawing a simple line

276
00:15:42.079 --> 00:15:47.040
So there's an effective way of drawing this

277
00:15:47.040 --> 00:15:50.266
This is the Bresenham's line algorithm

278
00:15:50.266 --> 00:15:52.799
or the line-drawing algorithm

279
00:15:52.799 --> 00:15:56.519
To simply explain about this algorithm

280
00:15:56.519 --> 00:15:59.869
the coordinates of the pixels on the screen coordinate system

281
00:15:59.869 --> 00:16:01.880
are in whole numbers anyways

282
00:16:01.880 --> 00:16:05.439
Therefore, when drawing a line, rather than using real numbers

283
00:16:05.440 --> 00:16:07.990
if we only use whole numbers to draw

284
00:16:07.990 --> 00:16:12.359
we can implement this very quickly

285
00:16:12.359 --> 00:16:18.320
Here, we can see that it's composed of integers

286
00:16:18.320 --> 00:16:21.000
This algorithm has been developed a long time ago

287
00:16:21.000 --> 00:16:25.692
It was invented back when decimal calculation was very difficult

288
00:16:25.692 --> 00:16:29.679
Back in 1962

289
00:16:29.679 --> 00:16:32.229
Therefore, they came up with a way to draw a line

290
00:16:32.229 --> 00:16:35.000
with minimum amount of load on the computer

291
00:16:35.000 --> 00:16:38.650
Because of the principal of this algorithm

292
00:16:38.650 --> 00:16:41.359
this is also called a midpoint algorithm

293
00:16:41.359 --> 00:16:44.059
Then I'll explain about the implementation method

294
00:16:44.059 --> 00:16:46.160
of this Bresenham's line algorithm

295
00:16:46.160 --> 00:16:49.360
We'll divide the space of the screen

296
00:16:49.360 --> 00:16:52.600
We'll divide the screen coordinate system into 8 parts

297
00:16:52.600 --> 00:16:55.559
And we'll divide it into octants

298
00:16:55.559 --> 00:16:59.600
Then 8 sides would be formed

299
00:16:59.600 --> 00:17:02.600
We'll try expressing the lines used here

300
00:17:02.600 --> 00:17:07.760
in the form of y=ax+b

301
00:17:07.760 --> 00:17:10.721
Then in the screen coordinate system

302
00:17:10.721 --> 00:17:12.971
when we're given the start point and the end point

303
00:17:12.971 --> 00:17:15.600
we can solve for various things

304
00:17:15.600 --> 00:17:17.559
First, we would be able to solve for the width

305
00:17:17.559 --> 00:17:20.867
When we subtract the start from the end, we would get the width

306
00:17:20.867 --> 00:17:22.839
and we would get the height

307
00:17:22.839 --> 00:17:25.939
And the coordinates of the start point and the end point

308
00:17:25.939 --> 00:17:28.760
would each be inputted

309
00:17:28.760 --> 00:17:30.760
With these information

310
00:17:30.760 --> 00:17:32.831
we'll learn about how we can draw

311
00:17:32.831 --> 00:17:35.160
by only using integers

312
00:17:35.160 --> 00:17:38.441
First, we'll proceed with drawing

313
00:17:38.441 --> 00:17:40.399
the first octant

314
00:17:40.399 --> 00:17:43.949
Here, in this area

315
00:17:43.949 --> 00:17:47.000
it's less than 45 degrees

316
00:17:47.000 --> 00:17:49.050
Drawing a line here means

317
00:17:49.050 --> 00:17:52.550
that we're drawing a line between

318
00:17:52.550 --> 00:17:54.320
0 degrees and 45 degrees

319
00:17:54.320 --> 00:17:59.640
That means there's no steep slope

320
00:17:59.640 --> 00:18:02.940
In other words, it goes as parallel as it can

321
00:18:02.940 --> 00:18:05.920
or goes down just one unit

322
00:18:05.920 --> 00:18:07.770
We cannot go

323
00:18:07.770 --> 00:18:12.079
more than two units down

324
00:18:12.079 --> 00:18:14.379
With that basic situation

325
00:18:14.379 --> 00:18:18.200
let's transform the linear equation

326
00:18:18.200 --> 00:18:22.640
First, substitute x0 and y0

327
00:18:22.640 --> 00:18:29.139
And since the value of slope, a, is height/width

328
00:18:29.139 --> 00:18:31.239
we can make this expression

329
00:18:31.239 --> 00:18:34.892
Ultimately we can use the given values

330
00:18:34.892 --> 00:18:38.884
to obtain the value of b

331
00:18:38.884 --> 00:18:42.640
With this situation, I've explained about the first octant earlier

332
00:18:42.640 --> 00:18:45.940
This can't pass the slope of 1

333
00:18:45.940 --> 00:18:48.520
Therefore, it can only go parallel or one unit down

334
00:18:48.520 --> 00:18:51.080
Therefore, we first plot the start point

335
00:18:51.080 --> 00:18:52.760
Plot the first point

336
00:18:52.760 --> 00:18:56.110
The next point can either go parallel

337
00:18:56.110 --> 00:18:58.599
or go on unit down

338
00:18:58.599 --> 00:19:02.520
Those two are the only possible results

339
00:19:02.520 --> 00:19:05.880
Then how can we decide this?

340
00:19:05.880 --> 00:19:09.119
That is the Midpoint Algorithm

341
00:19:09.119 --> 00:19:12.119
We look at the midpoint and decide

342
00:19:12.119 --> 00:19:14.929
if we're going to go as-is or go one step down

343
00:19:14.929 --> 00:19:17.972
If we use the linear equation from earlier

344
00:19:17.972 --> 00:19:21.559
to obtain the value of x0+1

345
00:19:21.559 --> 00:19:27.609
when that value is less than y0+0.5

346
00:19:27.609 --> 00:19:30.200
then the line goes this way

347
00:19:30.200 --> 00:19:32.550
That means this needs to go parallel

348
00:19:32.550 --> 00:19:35.119
and we need to plot the point here

349
00:19:35.119 --> 00:19:37.771
If the actual linear value

350
00:19:37.771 --> 00:19:40.000
is lower than this value

351
00:19:40.000 --> 00:19:44.119
then that means this has to go one unit down

352
00:19:44.119 --> 00:19:46.269
Then we need to learn the mathematical formula

353
00:19:46.269 --> 00:19:49.440
to distinguish this

354
00:19:49.440 --> 00:19:53.490
On this linear equation from earlier

355
00:19:53.490 --> 00:19:57.080
we'll substitute x0+1 in place of x

356
00:19:57.080 --> 00:19:58.400
x0+1

357
00:19:58.400 --> 00:20:00.915
When we substitute x0+1

358
00:20:00.915 --> 00:20:05.546
we get this expression, and it simplifies to this

359
00:20:05.546 --> 00:20:07.746
Then this is the linear equation

360
00:20:07.746 --> 00:20:10.896
It will be the actual value of the line we will draw

361
00:20:10.896 --> 00:20:15.640
We're now going to compare this with y0+0.5

362
00:20:15.640 --> 00:20:19.440
If that value is less than y0+0.5

363
00:20:19.440 --> 00:20:22.140
then we're just going to draw parallel

364
00:20:22.140 --> 00:20:25.800
The point will just be plotted to the side

365
00:20:25.800 --> 00:20:29.862
So we'll make a comparative inequality

366
00:20:29.862 --> 00:20:32.476
Here, we'll multiply w on each side

367
00:20:32.476 --> 00:20:36.800
Since 0.5 is 1/2, we'll multiply 2, so multiply 2w

368
00:20:36.800 --> 00:20:40.500
Ultimately, we'll check if 2h-w

369
00:20:40.500 --> 00:20:43.900
is less than 0

370
00:20:43.900 --> 00:20:48.400
If it's less than 0, we'll go one unit sideways

371
00:20:48.400 --> 00:20:50.818
If it's greater than or equal to 0

372
00:20:50.818 --> 00:20:56.268
we would plot the point one unit downwards

373
00:20:56.268 --> 00:20:58.768
We can draw the next point

374
00:20:58.768 --> 00:21:02.319
by choosing from either one

375
00:21:02.319 --> 00:21:05.419
From here, let's say that we go on unit further

376
00:21:05.419 --> 00:21:09.719
Then here, there are two possible cases

377
00:21:09.719 --> 00:21:11.319
Actually, there are two midpoints

378
00:21:11.319 --> 00:21:13.800
and three possible cases

379
00:21:13.800 --> 00:21:16.300
If I go sideways

380
00:21:16.300 --> 00:21:20.450
then this would also look at this midpoint

381
00:21:20.450 --> 00:21:22.750
and decide whether it would go this way

382
00:21:22.750 --> 00:21:24.640
or this way

383
00:21:24.640 --> 00:21:28.888
But if I plotted the point on the bottom

384
00:21:28.888 --> 00:21:31.888
then it would look at this midpoint and decide

385
00:21:31.888 --> 00:21:34.079
whether it would go sideways or down

386
00:21:34.079 --> 00:21:38.129
Anyways, it has to look at this situation and this situation

387
00:21:38.129 --> 00:21:41.129
It has to look at the two midpoints

388
00:21:41.129 --> 00:21:44.239
to decide whether it will go as-is or go down

389
00:21:44.239 --> 00:21:49.189
This time, when we try calculating for these two midpoints

390
00:21:49.189 --> 00:21:52.539
this one gets 4h-w

391
00:21:52.539 --> 00:21:57.199
and the bottom point gets 4h-3w

392
00:21:57.199 --> 00:21:58.499
Let's proceed once more

393
00:21:58.499 --> 00:22:00.399
This one would have three midpoints

394
00:22:00.399 --> 00:22:05.649
When we calculate the resulting value of these midpoints

395
00:22:05.649 --> 00:22:10.810
this gives us 6h-w, 6h-3w, 6h-5w

396
00:22:10.810 --> 00:22:16.810
It increases like this, and if you look at these discriminants

397
00:22:16.810 --> 00:22:19.880
it first started with 2h-w

398
00:22:19.880 --> 00:22:27.682
but it proceeds to 4h-w, 4h-3w, 6h-w, 6h-3w, 6h-5w

399
00:22:27.682 --> 00:22:31.432
Just like that, they change with

400
00:22:31.432 --> 00:22:33.560
a certain pattern

401
00:22:33.560 --> 00:22:37.110
But when I move parallel

402
00:22:37.110 --> 00:22:40.810
When I move parallel, I actually just need to think about

403
00:22:40.810 --> 00:22:42.260
this one

404
00:22:42.260 --> 00:22:46.465
And this one was 4h-w

405
00:22:46.465 --> 00:22:48.515
If I go one unit down

406
00:22:48.515 --> 00:22:51.228
it becomes 4h-3w

407
00:22:51.228 --> 00:22:52.528
Same thing here

408
00:22:52.528 --> 00:22:54.228
If I moved parallel

409
00:22:54.228 --> 00:22:56.878
I just need to think about this one

410
00:22:56.878 --> 00:22:58.488
And the discriminant for this is

411
00:22:58.488 --> 00:23:04.011
6h-w, 6h-3w, 6h-5w

412
00:23:04.011 --> 00:23:07.711
In other words, when we think of the normal pattern

413
00:23:07.711 --> 00:23:09.661
as x increases

414
00:23:09.661 --> 00:23:13.160
it's based on the plotted result as we increase one unit

415
00:23:13.160 --> 00:23:16.260
If we just move parallel, sideways

416
00:23:16.260 --> 00:23:20.810
then the discriminant simply needs to increase by 2h

417
00:23:20.810 --> 00:23:22.660
If we go downwards, then

418
00:23:22.660 --> 00:23:27.379
the discriminant increases by 2h-2w

419
00:23:27.379 --> 00:23:32.129
That way, we can continuously obtain the values

420
00:23:32.129 --> 00:23:35.239
with a consistent algorithm

421
00:23:35.239 --> 00:23:37.439
Putting this in order, it's as follows

422
00:23:37.439 --> 00:23:39.039
We first plot the point

423
00:23:39.039 --> 00:23:41.439
Then, we see if it arrived to the end point

424
00:23:41.439 --> 00:23:45.393
If it arrived at the end point, we would just end the line drawing

425
00:23:45.393 --> 00:23:48.693
If not, we would first obtain the discriminant

426
00:23:48.693 --> 00:23:50.760
That would be 2h-w

427
00:23:50.760 --> 00:23:56.953
If 2h-w is less than 0

428
00:23:56.953 --> 00:24:00.095
only the x value would be increased

429
00:24:00.095 --> 00:24:04.568
and we would plot a point on the pixel on the right

430
00:24:04.568 --> 00:24:07.518
And we would only add 2h to the discriminant

431
00:24:07.518 --> 00:24:10.560
If it's not less than 0

432
00:24:10.560 --> 00:24:12.610
then we increase x and y by one unit

433
00:24:12.610 --> 00:24:14.410
We would plot the point underneath

434
00:24:14.410 --> 00:24:17.610
On the discriminant, add 2h-2w

435
00:24:17.610 --> 00:24:19.640
and change the discriminant value

436
00:24:19.640 --> 00:24:23.990
On the increased value, plot the point

437
00:24:23.990 --> 00:24:26.440
Since the discriminant has been changed

438
00:24:26.440 --> 00:24:30.400
we use the new discriminant to decide

439
00:24:30.400 --> 00:24:33.300
We repeat this logic until we reach the end point

440
00:24:33.300 --> 00:24:38.680
and as a result, we'll form a line

441
00:24:38.680 --> 00:24:41.130
I'll explain about how we'll proceed

442
00:24:41.130 --> 00:24:43.330
with the rest of the octants

443
00:24:43.330 --> 00:24:45.880
With that, we learned about drawing a line

444
00:24:45.880 --> 00:24:49.877
in the first octant, the area less than

445
00:24:49.877 --> 00:24:52.177
45 degrees

446
00:24:52.177 --> 00:24:54.577
How do we plot points in the second octant?

447
00:24:54.577 --> 00:24:56.920
This one has a deep slope

448
00:24:56.920 --> 00:25:00.970
But if you change your thoughts a little

449
00:25:00.970 --> 00:25:04.320
instead of increasing the x here

450
00:25:04.320 --> 00:25:07.687
we increase the y, then it's technically

451
00:25:07.687 --> 00:25:09.787
the same as the first octant

452
00:25:09.787 --> 00:25:11.387
Here, we increased the x

453
00:25:11.387 --> 00:25:12.937
but here, we're increasing the y

454
00:25:12.937 --> 00:25:15.537
Then in the perspective of y

455
00:25:15.537 --> 00:25:18.959
this has a slope of less than 1

456
00:25:18.959 --> 00:25:24.047
then x won't increase

457
00:25:24.047 --> 00:25:26.040
for more than a unit

458
00:25:26.040 --> 00:25:28.642
Here, y didn't increase for more than a unit

459
00:25:28.642 --> 00:25:33.839
But here, the x doesn't increase for more than a unit

460
00:25:33.839 --> 00:25:37.389
Therefore, with the x switched to y

461
00:25:37.389 --> 00:25:39.631
when we conduct the same algorithm

462
00:25:39.631 --> 00:25:42.531
then we can calculate for second octant the same way

463
00:25:42.531 --> 00:25:46.476
For the discriminant, h and w will be switched as well

464
00:25:46.476 --> 00:25:51.826
We would start from 2w-h, and if it increases parallel to y

465
00:25:51.826 --> 00:25:53.826
if it increases perpendicularly

466
00:25:53.826 --> 00:25:56.913
downwards, then we add 2w

467
00:25:56.913 --> 00:25:59.413
If it increased one unit toward the x axis

468
00:25:59.413 --> 00:26:05.959
then we add 2w-2h and continuously change the discriminant

469
00:26:05.959 --> 00:26:09.159
Here, for the third, fourth, fifth

470
00:26:09.159 --> 00:26:12.559
sixth, seventh, and eighth octant

471
00:26:12.559 --> 00:26:15.709
the proceeding direction

472
00:26:15.709 --> 00:26:17.908
of x and y ultimately

473
00:26:17.908 --> 00:26:22.608
only has the difference of positive or negative direction

474
00:26:22.608 --> 00:26:24.958
Technically, it only divides into two types

475
00:26:24.958 --> 00:26:26.751
Whether you're going to be based on x

476
00:26:26.751 --> 00:26:29.680
or based on y

477
00:26:29.680 --> 00:26:33.180
So from the previous algorithm

478
00:26:33.180 --> 00:26:35.580
as long as we supplement the following elements

479
00:26:35.580 --> 00:26:37.430
we can create lines

480
00:26:37.430 --> 00:26:39.480
for all eight octants

481
00:26:39.480 --> 00:26:41.560
in a very stable way

482
00:26:41.560 --> 00:26:44.110
Whether the slope is low or steep

483
00:26:44.110 --> 00:26:46.210
And whether the direction of x and y

484
00:26:46.210 --> 00:26:49.540
is positive or negative

485
00:26:49.540 --> 00:26:55.590
We just need to understand these two elements

486
00:26:55.590 --> 00:26:57.800
and we can proceed with the generalized algorithm

487
00:26:57.800 --> 00:27:02.500
With that, we learned about the basic, theoretical system

488
00:27:02.500 --> 00:27:07.160
of creating a line mathematically

489
00:27:07.160 --> 00:27:11.296
In order to change this into a line on the screen

490
00:27:11.296 --> 00:27:13.565
we also learned about

491
00:27:13.565 --> 00:27:16.333
how engineers applied this

492
00:27:16.333 --> 00:27:18.768
in order to develop the line drawing algorithm

493
00:27:18.768 --> 00:27:20.868
We need to know both the theory

494
00:27:20.868 --> 00:27:22.868
and the actual application

495
00:27:22.868 --> 00:27:26.418
in order to implement an efficient computer graphic

496
00:27:26.418 --> 00:27:29.448
That way, we will be able to reach 60 frames that's needed on the game

497
00:27:29.448 --> 00:27:34.439
through this effective implementation

498
00:27:34.439 --> 00:27:36.189
That's all for this lecture

499
00:27:36.189 --> 00:27:39.093
Great job for listening to this lesson, thank you

500
00:27:39.471 --> 00:27:40.671
Combination of points in affine space
Expression of affine combination
Can add points by multiplying scalar in affine space

501
00:27:40.671 --> 00:27:41.821
Affine combination: using scalar to add two points and create a new point

502
00:27:41.821 --> 00:27:42.921
Expression of affine combination Σ (i = 0 to n) [c_i * P_i]
s.t. Σ (i = 0 to n) [c_i] = 1

503
00:27:42.921 --> 00:27:43.921
Points from affine combination forms on the same slope
Types of lines

504
00:27:43.921 --> 00:27:45.171
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<∞)

505
00:27:45.171 --> 00:27:46.411
Segment: Drawable line with a clear start point and end point (0≤a≤1)

506
00:27:46.414 --> 00:27:47.914
Line drawing algorithm
Expression of points
Points on the screen can be expressed after converting to match the hardware

507
00:27:47.914 --> 00:27:49.364
Real numbers of the Cartesian coordinate system are converted into whole numbers on the screen coordinate system
Screen coordinate system: Increase...

508
00:27:49.364 --> 00:27:50.864
Rasterization
Pixel: Smallest unit forming up the image on the screen, element of integers

509
00:27:50.864 --> 00:27:52.334
Rasterization: Process of converting the vector value of an object into pixels
Need a rule for setting the representative value when converting...

510
00:27:52.341 --> 00:27:53.641
Bresenham's line algorithm
Only using integers to quickly draw a line and minimize computer overload

511
00:27:53.641 --> 00:27:54.941
Drawing a line in first octant
Can only go parallel or one unit down
Discriminant 2h-w

512
00:27:54.941 --> 00:27:56.341
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

513
00:27:56.341 --> 00:27:57.841
Processing the other octants
Based on the direction of x and y, supplement the first octant algorithm

514
00:27:57.841 --> 00:27:59.380
Elements to supplement
Is the slope low or steep?
Is the direction of x and y positive or negative?