The software rendering world

El otro día de vuelta del curro, me pare a comer en uno de los n-mil restaurantes asiáticos de la calle castro. En verdad este es de los pocos que es de comida japonesa, dado que la mayoría de los bares de la zona son indios, chinos o coreanos…

Mini-review:

• +1 chicas guapas atendiendo, nunca está de más ;)
• +2 comida excelente
• +1 tienen comida para llevar
• +1 precio: $16 (recordemos el restaurante aya de 36€ == $55)
• -1 el huevo duro con los palillos es un poco complicado

sitio: maru ichi en mountain view

fotos: winden en el maru ichi de mountain view

Update domingo 15:

• Ayer volví a cenar allí, y ahora si me explico pq en la entrada decía “espere aquí hasta que le den una mesa”… Sábado a las 6 y media y el restaurante estaba lleno hasta la bola! Fue curioso cenar de mientras en el tele tenían puesto un programa de la tele japonesa acerca del fútbol de japón…
• Corregido el nombre a Maru Ichi

So, having already been for 1 week at Silicon Valley… how is this place?

• weather: Nice, sunny, malaga-like “fresquito” but not “joder que frio copón!”
• food, part 1: enjoy the overwhelming amount of asian restaurants
• food, part 2: chinese restaurants have the infamous fortune cookies with random messages inside
• places, part 0: Typical highschool-teen-film-like neighbourhoods: wide streets, trees, houses with lawns and garages
• places, part 1: Enjoy the beer garden at zeitgeist on valencia street
• places, part 2: Marvel at the computer history museum, full of classic toys to marvel at!
• places, part 3: Free wifi while waiting for the bus shuttles at the Mountain View caltrain station
• people, part 1: Some random names encountered so far: Alicia, Vijay, Crystal, Fernando, Molly, Owen or Erika
• people, part 2: At some parts of the place, you are going to find a quite high density of not-so-random Dubliners
• people, part 3: Amongst the biggest differences to Europe, here you can and will find girls driving taxis
• drink, part 1: All bars will ask you for some age identification to check for 21+ age
• drink, part 2: there is no guiness here :( …
• drink, part 3: … but there are bars with sangria! :)

BTW, don’t forget take advantage of your +16 spanish ability:

• spanish tip 1: you can buy “picos” at the big supermarkets, just smile and ask any spanish-speaking 50s-looking mama
• spanish tip 2: many cooks here are from spanish-speaking families, take advantage and ask for treats

El Jet Lag es cuando vas de viaje muy lejos y estas con el horario tó cambiao. Entonces cuando es de dia tienes un sueño del copón, y luego a mitad de la noche te despiertas y no puedes dormir.

Hay formas de evitarlo, pero parecen mas una lección de masoquismo que otra cosa:

• Dormir bien antes de empezar su viaje: Vale, parece razonable excepto que siempre hay que arreglar la maleta a última hora.
• Evita las bebidas alcohólicas y la cafeína: Esta frase no me queda clara. No beber ni café ni cerveza… no lo entiendo.
• Beber mucho agua: La tónica lleva agua, no?
• Intentar dormir durante el viaje: El que hizo la lista se ve que no viaja en clase turista.
• Comer fruta y verduras frescas en vez de la comida del avión: Esta lista debe ser vieja, seguro que hoy día te meten el pakete por intentar traficar con fruta fresca.
• Llevar ropa cómoda: Hala, todos en shandal.
• Intentar pasear por el avión: Esto debe ir con lo de beber mucha agua, por aquello de ir a mear 15 veces durante el viaje.
• Usar gafas de sol: En Irlanda no hay de eso, tendría que hacer otro viaje antes para poder comprarlas!

Lo dicho, esta lista de trucos tiene menos usabilidad que el mando a distancia de un DVD.

Estoy seguro que entre los que leen esto hay más de uno que es un flipaillo de los juegos de plataformas… para ellos, http://www.fpi-productions.de/smw.htm es sin duda un buen sitio para re-engancharse al clasico Super Mario a la vez que tener nuevos mapas y situaciones :)

I had a revelation today. It may not work, or be totally irrelevant, but that’s not important for me at the moment. The idea itself is cool, and that is worth writing about.

When doing perspective correct mapping, you have to interpolate u/z and 1/z horizontally and perform (u/z)/(1/z) every so often. That division is usually done in a pipelined manner so that we continue performing mapping while it is calculated, so in effect it may be “free”.

But we can also “accumulate” all these divisions and perform them in one go, reusing the same technique we used on the first part to compute the 3d-to-2d projections for the three triangle vertices.

Let’s play an example in a scanline that has 4 control points:

• numerators: n0, n1, n2 ,n3
• denominators: d0, d1, d2, d3

We can calculate the values we need in the old way:

• u0 = n0 / d0
• u1 = n1 / d1
• u2 = n2 / d2
• u3 = n3 / d3

But we can also factor out the divisions like this:

• dddd = 1 / ( d0 * d1 * d2 * d3 )
• nddd = n0 * d1 * d2 * d3
• dndd = d0 * n1 * d2 * d3
• ddnd = d0 * d1 * n2 * d3
• dddn = d0 * d1 * d2 * n3
• u0 = nddd * dddd
• u1 = dndd * dddd
• u2 = ddnd * dddd
• u3 = dddn * dddd

The result, as usual, is trading divisions for many multiplies.

Now some parts of the audience will say “But I’m already pipelining my perspective divides with my texturing, what can I gain from this technique?”.

As I said at the start, you could gang all the usual divides you’d do in a scanline into just one, which would mean a lot of work into calculating all the different numerators. Other way would be to gang only 2 consecutive divides, which is easier on the code and be a very simple way to achieve 8 pixel steps instead of 16 pixel ones.

I feel there are a lot of things which can be improved by generalizing this technique.

So, we have figured out how to optimise a lot, but still are without any means to calculate texture deltas… lets try to do the calculations for linear texturing!

One of the basic formula for texture deltas is this one:

• num = ((v1 - v0) * (yy2 - yy0) - (v2 - v0) * (yy1 - yy0))
• den = ((xx1 - xx0) * (yy2 - yy0) - (xx2 - xx0) * (yy1 - yy0))
• dvdx = num / den

As you can see, the patterns area similar to the calculations for the area, and in fact the denominator is the are itself, so lets substitute:

• num = ((v1 - v0) * (yy2 - yy0) - (v2 - v0) * (yy1 - yy0))
• area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
• dvdx = num / area

We need to correlate v0, v1 and v2 to the zzz divider which is being used all over the place, so we define this:

• vzz = v0 * zzz
• zvz = v1 * zzz
• zzv = v2 * zzz

And we can substitute just like we did when calculating the area formula:

• num1 = (zvz/zzz - vzz/zzz) * (zzy/zzz - yzz/zzz)
• num2 = (zzv/zzz - vzz/zzz) * (zyz/zzz - yzz/zzz)
• num = num1 - num2
• area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
• dvdx = num / area

Push out the zzz divides:

• num1 = (zvz - vzz) * (zzy - yzz)
• num2 = (zzv - vzz) * (zyz - yzz)
• num = (num1 - num2) / (zzz*zzz)
• area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
• dvdx = num / area

And notice that both num and area are being divided by (zzz*zzz), so it can be eliminated:

• num = (zvz-vzz) * (zzy-yzz) - (zzv-vzz) * (zyz-yzz)
• area_non_www = (zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)
• dvdx = num / area_non_www

Extending this code to calculate perspective correct gradients is easy, by using these values for the starting points:

• uzz = u0 * z1 * z2 (becomes u0/z0 when divided by zzz)
• zuz = z0 * u1 * z2
• zzu = z0 * z1 * u2
• wzz = z1 * z2 (becomes 1/z0 when divided by zzz)
• zwz = z0 * z2
• zzw = z0 * z1

And these formula for the numerator on the deltas using the same principles as in other parts:

• u_num = (zuz-uzz) * (zzy-yzz) - (zzu-uzz) * (zyz-yzz)
• w_num = (zwz-wzz) * (zzy-yzz) - (zzw-wzz) * (zyz-yzz)

note: delta formulas taken from kalms/tbl page for texture gradients

So in previous parts we have calculated the 2d coords and whether the polygon is facing towards us. That’s good, but we can’t draw a polygon without knowing which pixels are inside and which are outside…

For that, the usual way was to get the staring and ending point of each edge, and calculate a ratio on their differences.

Let’s take for example the edge from vertex 0 to vertex 1.

First we have to get the difference along X and Y axis:

• dx01 = xx1 - xx0
• dy01 = yy1 - yy0

Then, we calculate the ratio of them:

• dxdy01 = dx01 / dy01

And then, we can do a loop to calculate all the X coords for each Y:

• x[y] = xx0 + (y - yy0) * dxdy01

Which can be calculated by starting with:

• ex = xx0
• ey = yy0

and using a loop like this:

• x[ey] = ex
• ex = ex + dxdy01
• ey = ey + 1

But we have a big problem: each triangle has 3 sides, and each of them needs a division… is there any way to reduce that?

Lets recap… we start with the original formula:

• dxdy01 = (xx1 - xx0) / (yy1 - yy0)

And go back to using the original 3d values:

• dxdy01 = (x1/z1 - x0/z0) / (y1/z1 - y0/z0)

Then, we substitute for the intermediate values used on previous parts:

• dxdy01 = (zxz*www - xzz*www) / (zyz*www - yzz*www)

And we can push out and eliminate www:

• dxdy01 = (www*(zxz - xzz)) / (www*(zyz - yzz))
• dxdy01 = (zxz - xzz) / (zyz - yzz)

All fine and dandy, we can use that last formula as a template for the other edges (nice patterns on the letters hehe):

• dxdy01 = (zxz - xzz) / (zyz - yzz)
• dxdy02 = (zzx - xzz) / (zzy - yzz)
• dxdy12 = (zzx - zxz) / (zzy - zyz)

We first define some short hand terms:

• xxz = zxz - xzz
• xzx = zzx - xzz
• zxx = zzx - zxz
• yyz = zyz - yzz
• yzy = zzy - yzz
• zyy = zzy - zyz

And substitute:

• dxdy01 = xxz / yyz
• dxdy02 = xzx / yzy
• dxdy12 = zxx / zyy

We are very near the end!

First expand across all values:

• dxdy01 = xxz * yzy * zyy / (yyz * yzy * zyy)
• dxdy02 = yyz * xzx * zyy / (yyz * yzy * zyy)
• dxdy12 = yyz * yzy * zxx / (yyz * yzy * zyy)

And then factor the common divisor:

• ddd = 1.0 / (yyz * yzy * zyy)
• dxdy01 = xxz * yzy * zyy * ddd
• dxdy02 = yyz * xzx * zyy * ddd
• dxdy12 = yyz * yzy * zxx * ddd

Wow, the letter patterns are starting to hurt my head but it sure has its payoff: we are down from 6 to 2 divides per triangle!!!

After calculating the 3d to 2d projections, there are two parts of a mapper that need some common values: back face culling and calculating texture deltas.

Back face culling works by measuring the screen space “signed area” of a polygon: the same absolute value can be positive for front facing polygons and negative for back facing polygons.

That way when we detect this value as negative, we can simply stop drawing the polygon.

The classic formula using 2d coordinates is something like this:

area = (xx1-xx0) * (yy2-yy0) - (xx2-xx0) * (yy1-yy0)

We can substitute for the original 3d coordinates:

area = (x1/z1-x0/z0) * (y2/z2-y0/z0) - (x2/z2-x0/z0) * (y1/z1-y0/z0)

And make all parts have the same denominator:

xzz = x0 * z1 * z2
yzz = y0 * z1 * z2
zxz = z0 * x1 * z2
zyz = z0 * y1 * z2
zzx = z0 * z1 * x2
zzy = z0 * z1 * y2
zzz = z0 * z1 * z2
area = (zxz/zzz-xzz/zzz) * (zzy/zzz-yzz/zzz) - (zzx/zzz-xzz/zzz) * (zyz/zzz-yzz/zzz)

And try to push out the denominator zzz:

area = ((zxz-xzz)/zzz) * ((zzy-yzz)/zzz) - ((zzx-xzz)/zzz) * ((zyz-yzz)/zzz)
area = ((zxz-xzz) * (zzy-yzz)/(zzz*zzz)) - ((zzx-xzz) * (zyz-yzz)/(zzz*zzz))
area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)

Notice that zzz is the same 1/z0*z1*z2 that we needed on the previous part, this means that we can calculate all the 3d-to-2d projections and screen area with just one divide… things are looking good! :)

It’s funny how it works… yesterday while watching the 4k compos from breakpoint 2008 y was talking with wisefox about trying to eliminate divisions from the polygon drawing setups…

To recap, let’s forget for a moment about texturing and just try to get which pixels are to be drawn and which are to be left untouched…

Input data is 3 vertexes in 3d:

• x0, y0, z0
• x1, y1, z1
• x2, y2, z2

Next we have to transform from 3d to 2d, which takes at 3 divs and 6 muls:

• w0 = 1.0 / z0
• w1 = 1.0 / z1
• w2 = 1.0 / z2
• xx0 = x0 * w0
• yy0 = y0 * w0
• xx1 = x1 * w1
• yy1 = y1 * w1
• xx2 = x2 * w2
• yy2 = y2 * w2

But we can be a bit sneaky about how we calculate the dividing:

• xzz = x0 * z1 * z2
• yzz = y0 * z1 * z2
• zxz = z0 * x1 * z2
• zyz = z0 * y1 * z2
• zzx = z0 * z1 * x2
• zzy = z0 * z1 * y2
• zzz = z0 * z1 * z2
• www = 1.0 / zzz
• xx0 = xzz * www
• yy0 = yzz * www
• xx1 = zxz * www
• yy1 = zyz * www
• xx2 = zzx * www
• yy2 = zzy * www

This form needs 1 divs and 20 muls… but there are a lot of common parts that can be factored, and end up with 1 divs and 13 muls.

So, if a div takes A cycles and a mul takes B cycles…

• normal: 3*A + 6*B
• new: A +  13 *B

We are carrying a lot of divs and muls so it is better to do all of this on the FPU to conserve some appearance of precision… on a 68060 a division takes 37 cycles and a multiplication 3 cycles, so lets count…

• normal: 3*A + 6*B = 3*37 + 6*3 = 111 + 18 = 129 cycles
• new: A + 13 * B = 37 + 39 = 76 cycles

The new method takes only 58% of the time of the original one!

Ok, so we have reduced the number of calculations for calculating the 2d projection… next time we can see how to reduce the time needed for the edge deltas!

note: edited 26-march-2008 for naming consistency with later parts