Previous | Next --- Slide 66 of 70
Back to Lecture Thumbnails
mchoquet

What are the benefits and drawbacks of this approach? Why might this have gone out of style, given recent trends in computing hardware?

BryceSummers

Can anybody discuss the notion of mathematical "linearity" and how it allows many algorithms such as the one discussed in this slide, polygonal area computations, rolling hash functions to be used efficiently with many successive computations?

dsaksena

Can someone please explain this method to me please? I believe I am missing how we go through the entire triangle here.

BryceSummers

The way in which we go through the triangle is not discussed on this slide, we go through the triangle via mathematics related to triangles.

What this slide does explain is that you can efficiently calculate the edge equations while doing such a traversal.

kmcrane

Bryce mentioned "linearity;" it's important to understand this concept clearly, because it shows up all over computer graphics (and life!).

In general, a function f is linear if

f(ax+by) = a f(x) + b f(y)

for all x, y, a, and b.

For this statement to make sense, you have to know how to add x to y, and you also have to know how to add f(x) to f(y). Moreover, you need to know how to multiply x, y, f(x), and f(y), by scalars a and b. In other words, both the domain of f and its codomain have to be vector spaces; very roughly speaking, collections of objects that can be added and scaled. If you took linear algebra, you should know about vector spaces!

It's very important not to confuse the notion of "line" and "linear function." For instance, consider the usual line equation

f(x) = mx + n.

Is this equation linear? Well, let's just plug in the definition above. We have

f(x+y) = m(x+y) + n = mx + my + n

and

f(x) + f(y) = mx+n + my+n = mx + my + 2n.

Since we get n in the first expression, and 2n in the latter expression, the function describing a line is not linear!. Welcome to the English language.

There is, however, another name for the kind of function describing a line: it is an affine function. Roughly speaking, an affine function is a linear function "plus a constant."

Geometrically, the important distinction between linear and affine sums is:

• linear functions preserve (weighted) sums;
• affine functions preserve (weighted) averages.

By "weighted" sum and "weighted" average, we just mean that each of the summands gets multiplied by a scalar factor, as in ax+by. A weighted average means that the scalars (in this case, a and b) add up to 1. For instance, take a look at what happens with our line function when a=b=1/2:

f(x/2+y/2) = m(x/2+y/2) + n = mx/2 + my/2 + n

f(x)/2 + f(y)/2 = (mx+n)/2 + (my+n)/2 = mx/2 + my/2 + n,

i.e., we get the same result.

pavelkang

In this particular case, it is easy to decide the "starting points" from where we go right and test each point. However, there are other triangles, for example (0, 0), (-1, 1), (0, 2) whose "left border" consists of two edges. Is there an algorithm to decide the set of "starting points"?

BryceSummers

You can decompose any of those degenerate triangles into 2 triangles that have only 1 edge.

In other words use the left edge for one of the triangles until y coordinate of the crossing location and then simply use the other edge from then on.

Symmetric logic applies for the right side.

So, just find the piecewise function for the left bounds and the piecewise equation for the right bounds.

You can easily determine which point is highest (A), lowest(C), and in the middle(B). Just use lines AC & AB above B.y and BC & AC for left / right bound points (may be flipped) points below B.y