Monthly Archives: June 2015

What is Pre-multiplied Alpha and Why Does it Matter?

The usual equation for blending two pixels with alpha is to use a source factor of “source alpha” and a destination factor of “one minus source alpha”.

That results in this equation:

\bf{Out.RGB} = In.RGB * In.A + Out.RGB * (1.0 - In.A)

In other words, it’s just a linear interpolation between In and Out, using the alpha of the pixel you are writing to determine the weighting for the lerp.

Just to be clear, Out is the pixel in your frame buffer (ie the final result that shows up on your monitor) and In is the new pixel you are trying to write or combine with the output image.

If you use pre-multiplied alpha, all that means is that In.RGB is already multipled by In.A which results in slightly less math:

\bf{Out.RGB} = In.RGB + Out.RGB * (1.0 - In.A)

Less math for the same results is always a good thing due to increased efficiency, but this also results in a higher quality results in the case of using mips. For more info on that check out this link: NVIDIA GameWorks – Alpha Blending: To Pre or Not To Pre

To achieve this in OpenGL or DirectX with pre-multiplied alpha textures, you just use a source factor of “one” and leave the destination factor at “one minus source alpha”.

If you are using alpha to write to a render target that also has an alpha channel, the math improvement is even better. Here is the equation with regular (post-multiplied) alpha in that scenario for combining the RGB portion of the pixels:

\bf{Out.RGB} = \frac{In.RGB * In.A + Out.RGB * Out.A * (1.0 - In.A)}{In.A + (1.0 - In.A) * Out.A}

When working with pre-multiplied alpha it just goes back to the lerp:

\bf{Out.RGB} = In.RGB + Out.RGB * (1.0 - In.A)

When blending to a target with alpha, the equation to combine alpha is the old familiar lerp:

\bf{Out.A} = In.A + Out.A * (1.0 - In.A)

That makes the lerp form of color combining even nicer since it means the same math for all color channels of the pixel:

\bf{Out} = In + Out * (1.0 - In.A)

Confused about why alpha combining using lerp makes sense? It makes most sense to me when thinking about it like this… if you had something that was half opaque(Out.A = 0.5), then you looked at that through something that was 3/4 opaque (In.A = 0.75), only 25% of the light would get past the top layer (0.25), to reach the bottom layer. Only 50% of the light that reached the bottom layer gets through, so we cut that 25% in half to get 12.5% (0.125). Since alpha really means “opaqueness” (1.0 means no transparency), that means that the combined alpha is 1 – 0.125, or 0.875.

If you plug the numbers into the above equation you get the same result:

\bf{Out.A} = 0.75 + (1.0 - 0.75) * 0.5
\bf{Out.A} = 0.75 + 0.25 * 0.5
\bf{Out.A} = 0.75 + 0.125
\bf{Out.A} = 0.875

This compute graphics stack exchange question has some more great info on what premultiplied alpha can give you. It’s much more than I wrote here:
Does premultiplied alpha give order independent transparency?

Here’s a fun question… does alpha represent transparency, or does it represent how much of a pixel is covered by an opaque object? To find out the answer give this a read!
Jounral of Computer Graphics Techniques: Interpreting Alpha

Adventures in Learning How to Publish a Research Paper Part 1

So I’m in the process of trying to get a research paper published and wanted to share what I’ve learned so far. I’ll continue to write more beyond this post as I continue the process. Yes, I know my writing is terrible (grammar etc), please don’t take this as a representation of the final product 😛

The world of published papers, journals and academia (not necessarily lumped into the same group) is a bit different than I expected. On the whole, I’ve found that it’s both more approachable than I expected, and less approachable than I expected, in different, unexpected ways.

Motivation

A handful of times in my life, I’ve come up with things, naiively thought that I had invented it, and then later found out that it already existed and was a known thing.

I’ve reached the point in my career and personal growth where I’m coming up with things that seem like finally, they may not actually yet be already known and exist.

A braver person may quit their job and start a software company and try to make it happen and then possibly fail 9 out of 10 attempts (hey look, im about to cite something that refutes that statement Washington Post: Do nine out of 10 new businesses fail, as Rand Paul claims?).

Maybe a more cunning, yet less adventurous person would try and patent their idea, then sell the patent, or wait for someone to intrude and then sue for damages. I don’t like the idea of patenting my ideas or techniques because honestly, I want other people to do things with them, I just want to be the first, and I want people to know I was the first (petty perhaps but at least I’m being honest haha).

I happen to be taking perhaps the least risky road, but seemingly most altruistic path (more info on that later), and am thinking about publishing my techniques in a research journal of an appropriate field. This way, everyone is free to use it, and I can see what other people do with it – if anything. I will be known as “the guy who came up with this”, but probably won’t ever actually get to use it in my actual job. Boo-hoo! (we’ll see I guess…)

You never know though… having published papers definitely ought to lead to better career advancement opportunities, and frankly, maybe some dream job will come along where I get to work on these topics I’m publishing about, and do some cutting edge research towards practical results, and push the envelope of what people think can be achieved with current technology. That would be pretty cool! If you are a game (or related) company that is heavy in research, and also practical results, working within the realm of real time raytracing, unorthodox graphics techniques, VR, and other cool tech, and interested in a dude such as myself, drop me a line. I’m happy where I am but never hurts to chat and network (;

Anyhow, with a 1 year old baby, a house payment, and the like, I need the stability. I can’t go starting a new company so a research paper it is!

A quick note to my son Loki, if he reads this in the future, a nice little time capsul for him 😛

Hello Loki! I love you very much and I hope you are doing well. Your initials are LZW which is a compression algorithm, and your namesake is the norse god of mischief. Your mom is a super smart psychologist, so I hope we’ve taught you well and that you are now a Robot Psychologist AI developer who somehow furthered the works of chaos theory for AI and data compression. Or… you can play guitar at starbucks. Whatever makes you happy (: Talk to you later – dad. PS bring me a beer pls!!

Misconceptions Untangled

Once the decision of publishing in a journal was made… it was time to figure out what the heck academia / research papers were all about. As a near high school drop out with no degree, all I really know is what my near PHd wife (educational psychology) and more educated friends and family have told me.

Here were some of my misconceptions when I started out:

  • Publishing a paper is not for the likes of a mere mortal like me
  • When a paper makes a statement backed by a reference to something else that says so, that is irrefutable evidence that it is fact.
  • Publishing papers is all about advancing science, and perhaps a bit about one’s ego, but not at all about money
  • When you publish something, it has to be new. In fact, it has to be so novel that it can’t be like anything else written EVER.
  • Google ought to be great at helping me find other related work that i can reference!

Let’s address these points.

Publishing a paper is not for the likes of a mere mortal like me

Yes it is. Flat out, it is for anyone who wants to participate.

YOU have something to contribute to the world, but even moreso, writing and publishing a paper isn’t as impressive as it may sound. That thought will be continued below.

When a paper makes a statement backed by a reference to something else that says so, that is irrefutable evidence that it is fact

Wrong! At best, all that means is that someone else said the same thing. At worst, it means that they misinterpreted the thing they cited.

In either case, it’s through “peer review” that we hope mistakes and fallacies are found and corrected before publication, but it’s all humans involved, and humans are imperfect machines.

This is likely basic info for anyone who went to college, but for the rest of us simple folk, this translates to: Check your sources, and make sure you have multiple sources that are in agreement. Also try to understand and address any source that disagrees.

Publishing papers is all about advancing science, and perhaps a bit about one’s ego, but not at all about money

Sure it is about advancing science, and perhaps a bit about one’s ego, but there is more to it.

Certain professions are bound as part of their employment contract to fulfill a quota of published papers. Kind of surprising isn’t it?

Also, it costs MONEY to submit papers to journals. Like 5 grand or more. Where does that money go? You’d hope it would go to fund other research, but I’m not really sure where it goes in general. It also varies from journal to journal.

Furthermore, it costs money to READ papers in journals. Yes, seriously. Someone did science for the benefit of the world, and wanted to put it out there for the world to see and make use of, and the journals charge quite a bit of money to anyone who wants to read these papers. In practice, only academic institutions likely have access to these papers.

Are you an independent researcher with something to share with the world? Too bad! Good luck even finding related work to cite or improve upon jerk! ha ha ha!

Basically, academic journals are there for academic folk to publish in, get well known in academic circles, get better academic jobs and kinda stay in that realm.

Similarly, those folks aren’t likely to show things at E3.

It’s just a different world with it’s own rules and people in that system have different goals than us folk developing video games or graphics applications.

When you publish something, it has to be new. In fact, it has to be so novel that it can’t be like anything else written EVER.

Funny enough, it turns out this doesn’t have to be true at all.

If you are patenting an idea, you need to look like it came from NO WHERE and that it’s the first of it’s kind and is super amazing and standalone.

If you are publishing a paper, it’s kinda the reverse that is true. To gain credibility you need to show how your work is based on work other folks have done, and how you’ve improved them.

Alternately, you could also just do a paper that is a survey of various techniques to show the pros and cons of each.

Lastly, you can even write about something someone else already wrote about, but just explain it better, or maybe explore some of the implications of their work that they didn’t.

Yeah. YOU right now, could write a research paper about something. I guarantee you could. It just will take some time and effort (and possibly money), which may or may not be worth it to you.

Google ought to be great at helping me find other related work that i can reference!

This is still a bit strange to me. Google has been NO help in finding work related to what I’ve been working on.

On one hand, I can see that being true due to research almost always being behind a pay wall that google can’t see behind, but on the other hand, there is a lot of research that isn’t. Also, the “Abstract” of papers (a ~4 sentence summary) is almost always able to be read for free. Why does google not have knowledge of those?

But yeah… google has found NOTHING. The references I have are things that I accidentally stumbled on, or that other people RANDOMLY happened to put something on twitter about, or talk about in graphics mailing lists.

I search for exact terms that should find things I now know exist, and it finds nothing.

WTF Google?!

Is it Worth it?

As a (professional?) (game?) programmer, is publishing a paper worth it? It depends.

Is this something you have a desire to do? I have always wanted to be a scientist and contribute to human progress, so that makes it worth while to me.

Also, it can’t hurt the resume, but it can be expensive.

If interested, make sure and find out what your employer’s policies are though, and also what your rights are which may be different than what your company would like you to do!

Then, in the end, do whatever you think is best (:

It’s also a good idea to read the guidelines for submission from the journal, read the notes that they give to reviewers to help review your paper, and also you should read papers that have been published in that journal to get an idea of what qualities an accepted paper has.

Some Resources

Here are some nice resources I’ve found so far.

First and foremost is the journal I’m going to be trying to publish my first paper with. They have some sort of partnership with SIGGRAPH which is awesome (because SIGGRAPH is amazing!!), and also, it’s FREE to submit papers to, and FREE for people to read. It’s also aimed towards professional game / graphics programmers and focuses more on practicality and results, and less on purely theoretical things, or typical academic practices that don’t really have a place in the non academic world (IMO). Go right now and go read some of their articles!

http://jcgt.org/ – the Journal ofComputer Graphics Techniquespeer-reviewed, open access, and free to all

Next, I encourage you to read the notes that jcgt gives to reviewers to help them review papers. This ought to show you the mindset of both the journal and the reviewers. They are literally there to try and help you succeed as much as possible.

JCGT – Review Form

I also want to share this presentation with you, which is from Microsoft Research, Cambridge.

How to write a great research paper

If you are someone like me who wishes for greatness, but feels like a “mere mortal”, I really recomend reading the book “Masters of Doom” to see how John Carmack and related folk made such a splash in the world as game developers. JC is someone I respect a lot, and a lot of things he does and has done in the past are things that are beyond my wildest dreams of success, but things I’d like to aspire to. The path is a lot more humble than you might expect, and even a little bit shady at times. Masters of Doom: How Two Guys Created an Empire and Transformed Pop Culture.

Lastly, as I write my paper, I hope that this is the time that I finally have invented something that doesn’t yet exist (please???!!!). I’ve spent several months on doing experiments, writing code, doing research to help explain my results, and finding ways to work around problems encountered. I’ve finally finished that phase and have started in on actually writing the paper (abstract v1 is finished, outline is work in progress).

RANDOMLY, last friday, someone posted a link to a paper in a graphics mailing list I’m on. That paper had a title so similar to what I’m writing that i nearly fell out of my chair and started crying LOL (ok maybe exaggerating but i was scared). I read it in a few passes, each time peeking out from between my fingers as i was covering my eyes, afraid of what I’d see, and after about 4 or 5 of those passes I gave a sigh of relief. There are similarities, but it is a world of different-ness, and it’s applications are way different than my paper.

PHEW. That close call actually gave me the strongest reference I have to cite and actually gave me some references to other papers which explain some of the strange results I was getting in a specific situation, so solved a mystery for me. Turned out to be a good thing, but man was I scared.

Believe it or not, the academia stack exchange site has been a great help too in finding answers to specific questions that you can’t just ask google about:
https://academia.stackexchange.com/

More coming in the future as I learn more, until then, ta ta!

A Fifth Way to Calculate Sine Without Trig

In a previous post, I showed Four Ways to Calculate Sine Without Trig. While reading up on rational bezier curves, I came across a 5th way!

A rational bezier curve post will be coming in the (hopefully near) future, so I won’t go into too many details of that, but the important thing to know is that with a rational 2d quadratic bezier curve, you can EXACTLY represent any conic section, including circle arcs. With a regular (integral) bezier curve, you can’t.

You can in fact see that in action in an interactive HTML5 demo i made here: Rational Quadratic Bezier Curve. Note that on my main page, i have links to other 1d/2d bezier/trig rational/integral interactive curve demos. go check them out if you are interested in seeing more: http://demofox.og.

After I made the 2d quadratic bezier demo I realized something… The x and y positions of that curve are calculated independently of each other, and if you wanted to draw a circle in a program, you’d calculate the x and y positions independently, using sine for the y axis value and cosine for the x axis value. That means that if rational curves can – as people say – perfectly represent conic sections, that the two 1d curves that control each axis of that circle arc curve must be exact representations of sine and cosine, at least for the 90 degrees of that arc.

It turns out that this is true enough. I am seeing some variation, but have an open question on math stack exchange to try to get to the bottom of that.

Let’s do some math to come up with our curve based sine equation!

Math Derivation – Skip If You Want To

A rational Bezier equation is defined like this, which is basically just one Bezier curve divided by another:

\bf{B}(t) = \frac{\sum\limits_{i=0}^n\binom {n} {i}(1-t)^{n-i}t^iW_iP_i}{\sum\limits_{i=0}^n\binom {n} {i}(1-t)^{n-i}t^iW_i}

So, here is the equation for a rational quadratic bezier curve (n = 2):

\bf{B}(t) = \frac{(A*W_1*(1-t)^2 + B*W_2*2t(1-t) + C*W_3*t^2)}{(W_1*(1-t)^2 + W_2*2t(1-t) + W_3*t^2)}

A,B,C are the control points and W_1,W_2,W_3 are the weightings associated with those control points.

For the first 90 degrees of sine, A=0, B=1, C = 1, W_1 = 1, W_2 = cos(arcAngle/2), W_3 = 1.

arcAngle is 90 degrees in our case, so W_2=cos(45) or W_2=1/sqrt(2) or W_2=0.70710678118.

If we plug those values in and simplify, and treat it as an explicit (1d) equation of y = f(x), instead of P=f(t), we come up with the equation in the next section.

Final Equation

y = \frac{(0.70710678118*2x(1-x) + x^2)}{((1-x)^2 + 0.70710678118*2x(1-x) + x^2)}

or, so you can copy paste it:
y=(0.70710678118*2x(1-x) + x^2) / ((1-x)^2 + 0.70710678118*2x(1-x) + x^2)

That gives us the first quadrant (first 90 degrees) of sine. To get the second quadrant, we just horizontally flip the first quadrant. To get the third quadrant, we vertically flip the first quadrant. To get the fourth quadrant, we vertically and horizontally flip the first quadrant.

Equation In Action

Here’s a screenshot from a shadertoy where I implemented this. red = true sine value, green = the value made with the curve, yellow = where they overlap and are equal. Any place you see red or green peaking out means they aren’t quite equal. I sort of expected it to be exactly dead on correct, but like I said, I have an open math stack exchange question to find out why it isn’t and will update this with my findings if they are relevant or interesting. It still is pretty darn good though.

Also, this formula may not be the most efficient way to calculate sine without trig that I’ve shown, but it is interesting, and that’s why I wanted to show it (:

You can see this in action at Shadertoy: Sin Without Trig IV