gradients

The gradient of a scalar field is a vector associated with each scalar so that the vector points in direction of the greatest slope of the surrounding scalar values. Its vector length furthur points out how heavy the change is. Assume for example a height field (i.e. the scalars denote heights), then the gradient points in direction of the steepest slope. A sphere deposited at a location will start moving exactly against the direction of the gradient ("against" since the gravity "points down"), but still on the surface, of course. On a (infinite) plane the gradient is everywhere 0, since there is no change in the scalars.

can you explain how this would work when rasterizing a triangle?, I normally just interpolated the values down the left and right sides of the triangle and then interpolated the interpolated values across the scanline.

[Edited by - staticVoid2 on March 9, 2008 1:10:49 PM]

Quote:

On a (infinite) plane the gradient is everywhere 0, since there is no change in the scalars.

so, are the vertices of the (finite)plane the scalar values? or do the scalar values represent each individual point in the plane?

Meanwhile I've thrown a look into the cited paper. That has durated a while, sorry. Hopefully I'm right with my following interpretation...

Quote:

Original post by staticVoid2 I think what he means is for each edge of the polygon/triangle the interpolants are constant, so you can assign values to the two endpoints of each edge of the trinagle and interpolate between them

Well, as far as I understood the article, he means more than that. He means that the interpolants are not only constant along the edge but along any arbitrary line in the plane in which the triangle lies in. This obviously includes the lines resulting from backward projecting the scan lines.

The interpolation is well done pixel-wise, i.e. on the screen. (Wolberg, the book cited by the article, shows why that backward mapping is senseful.) In detail this means that interpolation stepping is done line-wise (i.e. inc-/decrementing y') in an outer loop and pixel-wise (i.e. inc-/decrementing x') in an inner loop (or vice-versa). For each of these steps on the screen a analogous step on the triangle's plane exists, named dy and dx, resp.

Now, any value one wants to interpolate, e.g, the u co-ordinate of the texture, the v co-ordinate, or whatever, is given as a scalar field, i.e. the values are given at (discrete) vertex positions only. Let's name that value c. As written above, the interpolation stepping yields in offsets (dx,dy) in the triangle's plane. What we want to know is how much does c change for a single dx step, and how much does c change for a single dy step. If we know this, then we can compute the belonging difference c' in screen space for each line/pixel step, if needed. Mathematically it is written as dc/dx and dc/dy for 2 dimensions (this is mathematically not 100% correct, but good enough here), or in vectorial form dc/dv.

One of the two definitions of the gradient is
dc/dv = v . grad c
where the dot means the dot operator and grad c the gradient vector of the scalar field c. This formula means that for a given vector v, the value looking for is the projected length of the said vector onto the gradient vector. However, this explains the use of "gradient" but is not needed to be known especially for using dc/dv for interpolation.

All this leads to the "new texture mapping algorithm" as is mentioned on page 20 of the article.

Quote:

Original post by staticVoid2 so, are the vertices of the (finite)plane the scalar values? or do the scalar values represent each individual point in the plane?

Neither - nor, see above. What I meant was that on a planar height field all heights (i.e. the scalars) are equal and hence the gradient everywhere 0. In the given case, the vertices are just the support points at which the scalars are given.

I understand now, but in the article, in figure 3 why does he create two new points to find the gradient? could you not just sample any part of the triangle to find the gradients, eg. (P1.c - P0.c)/(P1.x - P0.x).

In figure 3, the new triangle has some special properties w.r.t. P0, namely that P4 has the same y' co-ordinate as P0, and P3 has the same x' co-ordinate as P0. Using P0 and P4 to compute a gradient has the advantage that it only depends on dy' but not on dx'. Similarly, using P0 and P3 depends only on dx but not dy, i.e. it is just in scanline direction. Using P2 and P0 would compute a gradient that depends on a direction somewhat across dx' and dy'.

thanx. Im sure I understand now, you're basically taking the difference of any two points of the triangles edges that are parallel with the x axis, finding the appropriate value of c for these two points of course, and dividing dc/dx. and the same for the y axis.

[Edited by - staticVoid2 on March 10, 2008 8:35:45 AM]

theres only one thing im not sure about. how does the cross product of the the two triangle sides result in the width and height values?

Quote:

Original post by staticVoid2 you're basically taking the difference of any two points of the triangles edges that are parallel with the x axis, finding the appropriate value of c for these two points of course, and dividing dc/dx. and the same for the y axis.

I'm not quite sure about the detail correctness of your analysis. They are correct so far but only due to special circumstances given by this use case. So I give some more detailed explanation here:

Mathematically the expression df/dx denotes the rate at which the value of f changes in direction of x for any given x. This is called the (partial) derivation of f w.r.t. x if f is a continous function of x, and dx denotes an infinitesimal small offset in direction of x. In our case here, we have extended offsets of 1 pixel or 1 line on the screen. This is no problem, since dc/dx and dc/dy are constant in our special case.

The extended offsets are named dx' and dy' by the paper. The equivalents on the triangle's plane are named dx and dy, resp. Hence they don't span from one edge to another or the like; instead, they span the "unprojected" (i.e. backward projected) distance of 1 pixel or 1 line, resp, on the triangle's plane. Furthurmore, in the given special case, dc/dx (or dc/dy) is constant for any x (or y). This allows to use any multiples of dx (or dy) to compute dc/dx (or dc/dy). Hence the paper suggests to extend the one edge of the triangle, and to construct new points on the extended edge where, emanating from P0, the multiples of {dx,0] (or {0,dy}) hit. So in fact, the point P4 is given as
x4 := x0 + k*dx, y4 = y0 + k*0
where k denotes said extension factor. Now, due to constant dc/dx, also
c4 := c0 + k*dc
must hold. In other words,
(c4 - c0) / (x4 - x0) = (c0 + k*dc - c0) / (x0 + k*dx - x0) = (k*dc) / (k*dx) = dc/dx
what is like formula 6 of the paper (but in world space instead of screen space). Formula 7 can be derived similarly.

Quote:

Original post by staticVoid2 how does the cross product of the the two triangle sides result in the width and height values?

AFAIK not at all. The cross product can be used to compute the area of the triangle. E.g. is e₁₂ and e₁₃ are the both edges as vectors, then
| e₁₂ x e₁₃ | / 2
denotes the area. I haven't found where a cross product is used the way you've mentioned. Please hint me to that place for furthur investigation...

Quote:

Please hint me to that place for furthur investigation...

on figure 5(referred to on page 20) he gives the two equations.
like you said he mentions you have to extend the edge of the triangle until y' and x' of that edge are equal to p0.x and p0.y respectfully and then dx = (x' - p0.x) and dy = (y' - p0.y) but he does this a different way in his equations in figure 5. he multiplies the width of one edge by the height of the other and vice versa then subtracts these values to get dx and dy.

[Edited by - staticVoid2 on March 10, 2008 6:30:50 PM]

Quote:

Original post by staticVoid2 on figure 5(referred to on page 20) he gives the two equations. like you said he mentions you have to extend the edge of the triangle until y' and x' of that edge are equal to p0.x and p0.y respectfully and then dx = (x' - p0.x) and dy = (y' - p0.y) but he does this a different way in his equations in figure 5. he multiplies the width of one edge by the height of the other and vice versa then subtracts these values to get dx and dy.

This kind of math is not the cross product. On page 20, central column, the 1st formula

x1' - x2'    x4' - x2'--------- == ---------y1' - y2'    y4' - y2'

is a formulation of the "intercept theorem" a.k.a. "theorem on intersecting lines", expressing a geometrical length relation when intersecting with parallel lines (which are not explicitely shown in figure 3 in the paper). Also on page 20, central column, the 2nd formula

c1' - c2'    c4' - c2'--------- == ---------y1' - y2'    y4' - y2'

is a formulation of the "rule of proportion" a.k.a. "rule of three". Both formulations are very similar, where the former one is more of a pure geometrical interpretation, while the latter one relates any 2 proportional values.

What follows are a couple of substitutions to remove all "unknowns", and a bit of re-arrangement to yield in dc'/dx' and dc'/dy', resp.

Its finally clicked:

y4 = y0
x4 = (x1 - x2/y1 - y2) * y0 - y2 + x2

x3 = x0
y3 = (y1 - y2/x1 - x2) * x0 - x2 + y2

mx : my = dx : dy

(I'm not sure if thats the correct mathematical term)

mx = gradient w.r.t x
my = gradient w.r.t y

so there's no need in calculating the gradient when you are only finding the difference.