So hello and welcome to our computer graphics lecture.

So today we will learn about very basic computer graphic

algorithms.

We are right now in the section of rasterization.

So we already started with this last Thursday.

So the problem is quite simple.

Given a two dimensional polygon with n vertices,

so usually when we say polygon we mean triangle,

but it can be an arbitrary polygon.

And now we want to find out which pixels on a raster

display are covered by that triangle.

Yeah, so that's a very basic algorithm.

Imagine you have a scene consisting of something

like 10 million triangles.

All these triangles have been projected to the screen.

So you know the extent of that triangle on the screen,

and now you have to set all the pixels inside

to render that model.

So if you want to do that for 10 million triangles,

this algorithm runs 10 million times per frame.

And if you want to have 60 frames,

this algorithm runs 600 million times per second.

So it is very, very important that it's very fast.

And OK, for interactive graphics at least.

And yeah, the algorithms that we will learn here

are not the ones that are implemented on a GPU

or something.

Yeah, but they are the basis for it.

And of course, there are many little secrets

how these algorithms can be optimized and so on.

So we will learn about the very basic versions.

And there are many optimizations,

further optimizations possible.

OK, and the first one, yeah, it's

more a kind of introduction, because maybe that's

the first thing you would think about

if you hear about that problem, is

to use the so-called seed fill algorithm.

And the idea here is that we first

rasterize the boundary of the polygon.

We will see later on how this can be done very efficiently.

And then we do a flood fill from the center

or from a point inside the polygon.

And this flood fill can be implemented easily

using recursion.

Easily means, yeah, it's simple to implement.

So here you see the entire code for doing that flood fill.

And what it essentially does, it is always

called for a particular pixel.

And it just tests whether this pixel already has been set.