Impasto discussion

[JL VT]

On Mon, Jul 19, 2010 at 7:06 PM, Matthew Woehlke
<mw_triad at users.sourceforge.net> wrote:
> JL VT wrote:
>> I'd like to perform thread necromancy now that I have a worthy update
>> to mention:
>>
>> http://pentalis.org/kritablog/?p=157
>>
>> I decided to follow the Phong Illumination Model to set the color of
>> the bumps, and for now I'm only using the pixels above and below, and
>> right and left of the reference pixel to calculate its normal vector
>> (and therefore, indirectly, "inclination/tilt").
>>
>> The main references being, as the blog post highlights:
>> http://www.mini.pw.edu.pl/~kotowski/Grafika/IlluminationModel/Index.html
>> http://www.gamedev.net/columns/hardcore/cgbumpmapping/
>>
>> The source of the program is:
>> http://pentalis.org/kritablog/wp-content/uploads/2010/07/bumpy_source.txt
>
>>         vector_x = [1, 0, height_array[x+1][y] - height_array[x-1][y]]
>>         vector_y = [0, 1, height_array[x][y+1] - height_array[x][y-1]]
>
> How do you handle edge pixels?
>
> At first that seemed like an over-simplification, so I decided to write
> my own version and work out the math.
>
> If we construct a four-quad mesh around the pixel being evaluated and
> calculate the normal of the center vertex, we can derive a very simple
> formula for interior pixels (which turns out to be equivalent to the
> above formula), as well as see how to calculate normals for edge pixels
> (simply omit the faces that don't exist). Like so:
>
> // Mesh looks like this:
> //
> // 1--2--3
> // |  |  |
> // 4--0--5
> // |  |  |
> // 6--7--8
> //
> // ha0 = ha[x,y]; - ha == height_array
> // had2 = ha[x,y-1] - ha0;
> // had4 = ha[x-1,y] - ha0;
> // had5 = ha[x+1,y] - ha0;
> // had7 = ha[x,y+1] - ha0;
> // cross: [y1*z2 - z1*y2, z1*x2 - x1*z2, x1*y2 - y1*x2]
> // n1 = (2 - 0) × (4 - 0) = [ 0, -1, had2] × [-1,  0, had4]
> // n3 = (5 - 0) × (2 - 0) = [ 1,  0, had5] × [ 0, -1, had2]
> // n6 = (7 - 0) × (5 - 0) = [ 0,  1, had7] × [ 1,  0, had5]
> // n8 = (4 - 0) × (7 - 0) = [-1,  0, had4] × [ 0,  1, had7]
> // n1 = [-had4, -had2, -1];
> // n3 = [ had5, -had2, -1];
> // n6 = [ had5,  had7, -1];
> // n8 = [-had4,  had7, -1];
> // n = n1 + n3 + n6 + n8;
> // n = [had5 - had4, had7 - had2, -2]; - can drop the constant scalar
> n = [ha[x+1,y] - ha[x-1,y], ha[x,y+1] - ha[x,y-1], -2];
> n = n / linalg.norm(n);
>
> I believe if you write out the cross product from your version, you'll
> see it works out the same (allowing for a constant scalar adjustment of
> the Z value).

Well, after giving your sample code a 10 minute look, it came to my
attention that the formula you derived with your own reasoning is in
fact the way to express the cross product of two perpendicular vectors
of differing z value, as illustrated by this link:
http://www.wolframalpha.com/input/?i=%281%2C+0%2C+z1%29+x+%280%2C+1%2C+z2%29

The scalar adjustment may be a bit contentious, I'd have to look into
it to be really sure that scalar adjustment should be there.

On the other hand, when I ported this Python script to Qt/C++, I found
Qt provided a very fast function that implements everything in a
single step, namely this:
http://doc.qt.nokia.com/4.6-snapshot/qvector3d.html#normal

It calculates the cross product of both vectors and then normalizes
them, in a single function. I believe the function is as optimized as
it can be so I decided to not venture finding alternative ways to work
out the normal at every pixel, because the most correct
(mathematically: elegant and minimal) way to do it is the cross
product vector of the plane described by vector_x and vector_y
(tangent to the height map pixel), and this function literally
calculates both and then normalizes the vector, which is required for
the other calculations to work quick and seamlessly.

Qt/C++ happened to perform 50+ times faster than the
PyGame/Numpy/Python implementation (I blame Numpy for that, most of
the overhead is in calculating the cross product, which maybe was what
triggered your concern), opening a .bmp, calculating a 198x198
bumpmap, and compressing it into a .png file and saving it, all after
mere 43 ms in my computer (which is pretty average). The cross product
calculation in its entirety took 13 ms (compared to 5.66 seconds in
Python/Numpy).

Certainly I haven't worked out the edge pixels, that's why the origin
file is of size <width, height> and the resulting image is of
dimensions <width-2, height-2>. I haven't thought of a solution for
the edge pixels yet, but I'm aware of the problem.

Funnily, the mesh you describe with all neighbouring pixels is very
similar to the idea I had in my head before I read the Cg tutorial.
The idea diverged after that point however. The idea was adding all
the heights surrounding the main pixel as if they were opposing
vectors, then take the resulting vector and rotate it 90° upwards and
away from the tip, effectively obtaining the normal of the pixel. But
when I thought of all the code I'd have to write to probably obtain a
slower function than what this elegant cross product solution offered,
so I just abandoned the idea. I like minimal code.

If I run into performance problems you can rest assured that I'll
attempt a solution along the lines of your proposal, trying to
directly express the resulting algebraic expression of the cross
product and then normalizing it, instead of asking Qt to calculate it.
But for now, I think the current algorithm works good enough (I did
some improvements upon that Python script, I removed unneeded steps
that involved saving and retrieving data from the arrays); soon an
unit test and the Qt/C++ algorithm should be available, when I solve
the problem with the border pixels.

Thank you for your insights  : )

> However you should be able to use the above to derive the
> simplified formulas for boundary pixels as well. (And I *would*
> recommend writing out the cross product result explicitly. It's only a
> few basic math operations saved, but even that over thousands or
> millions of pixels can be significant.)

Well, I can't be certain that I'm saving math operations. Or maybe I
am saving math operations but not processor operations and in the end
things may take longer. I don't know how optimized the Qt function is
but I bet it is very much so, because 13 ms for 40K normalized cross
products is certainly very little overhead; so for now I'll try to not
touch it unless it brings problems later.



~Pentalis.