Lightmap optimizations for iOS

One of the main challenges of porting The Witness to iOS was reducing the app memory footprint. The lightmaps that we used in the PC version simply did not fit in the memory budget that we had for iOS.

As described in my previous article, on PC we compress our lightmaps using DXT5-RGBM. The DXT5 texture compression format is not available in iOS, so the first problem was to find a suitable alternative.

Continue reading →

Lightmap Compression in The Witness

In my initial implementation of our lightmapping technology I simply stored lightmap textures in RGBA16F format. This produced excellent results, but at a very high memory cost. I later switched to the R10G10B10A2 fixed point format to reduce the memory footprint of our lightmaps, but that introduced some quantization artifacts. At first glance it seemed that we would need more than 10 bits per component in order to have smooth gradients!

At the time the RGBM color transform seemed to be a popular way to encode lightmaps. I gave that a try and the results weren’t perfect, but it was a clear improvement and I could already think of several ways of improving the encoder. Over time I tested some of these ideas and managed to improve the quality significantly and also reduce the size of the lightmap data. In this post I’ll describe some of these ideas and support them with examples showing my results.

Continue reading →

D3DX UVAtlas released

I think it’s really awesome that Microsoft and Xin Huang released the source code of their D3DX mesh parameterization library. Chuck announced it on his blog.

There’s a lot of good stuff in there, more than in any of the previous D3DX source code releases. I was never too happy with the k-means style clustering that we use in The Witness, top-down spectral clustering seems a much better approach. Also their stretch-minimization parameterization is certainly better than our plain LSCM.

I wrote about our implementation in this article. A few people asked for our code and we released it here. However, today I’d recommend using Xin Huang’s as a better starting point.

First Backpacking Trip

IMG_20140901_091134I finally took Nachito on his first backpacking trip. We went to Desolation Wilderness, and following a friend suggestion we hiked the Pacific Crest Trail from from Echo Lake to Lake Aloha. There’s a boat taxy that takes you from one end of Echo Lakes to the other, and that shortens the hike quite a bit, allowing us to reach a fairly remote location with a real wilderness feel to it without having to walk all the distance.

Continue reading →

Irradiance Caching – Continued

Looks like I’m getting into the habit of starting article series and abandoning them after the first installment. Where’s part 2 of the irradiance caching article that I wrote several years ago? Before starting a new series, I think it’s about time to wrap that one up.

In the final part I wanted to write a bit about our record placement strategy. The main idea was to use the irradiance gradients to control the record density. That was nothing new, in Making Radiance and Irradiance Caching Practical Krivanek, et al also propose adjusting the record distribution based on the rate of change in the irradiance.

However, the interesting observation is that the scale of the gradient is not that relevant, what we care about are changes in the rate of change, that is, second order differences. If a sample has a small gradient and the one next to it has a large one, that’s an indication that the irradiance between the two changes abruptly and that additional samples may need to be taken in between them.

Continue reading →

Irradiance Caching – Part 1

I finally finished writing the next article about the lightmap rendering tech that I did for The Witness. This one is about irradiance caching, and in particular I describe how to estimate irradiance gradients when the irradiance is sampled using a hemicube distribution. I’m afraid the article is a bit too specialized and I suspect it will only be useful to those that are trying to solve this particular problem, but I think it’s good to have this documented anyway.

This time around we are trying something new and we are cross-posting it on #AltDevBlogADay. It seems to me that most of the subscribers to The Witness blog are non-programmers, so this way it may reach a wider audience. Hopefully this will also encourage me to post more regularly!

Software Patents are Programmer’s Responsibility

The other day I read this in Dark Shikari’s blog (one of the developers of x264):

Most importantly, stop harassing the guy whose name is on the patent (Lars): he’s just a programmer, not the management or lawyers responsible for filing the patent. This is stupid and unnecessary. I’ve removed the original post because of this; it can be found here for those who want to read it.

I don’t know much about this particular case, I don’t know whether Lars came up on his own with the algorithm that is being patented or not, and I’m not really qualified to discuss that.

But that’s not what I want to write about. What really struck me from this post is the idea that programmers are not to blame for filing software patents. I think that’s just wrong.

Lawyers alone cannot create patents, you also need inventors, and being just a programmer does not absolve you of your acts. Let me rephrase that: There would be no patents without inventors willing to file them.

Obviously, corporations provide incentives for employees to file patents, but in most cases it’s not the actual incentives what motivates people to patent their inventions. It’s the benefit of being a good corporate employee, not being considered a trouble maker, not loosing opportunities for promotion, not bringing negative attention to yourself, not going against the tide.

I firmly believe that patents discourage progress and impede the growth of public domain of knowledge. Today patents do not protect the inventor’s interests, but instead promote anti-competitive practices by corporations. Moreover, most software patents are vague, bogus, or trivial, they do not serve any social purpose other than expanding the patent portfolio of your corporate masters.

You may not agree with all that, but if you do, then don’t excuse yourself blaming the system.

During the 5 years that I worked at NVIDIA I constantly came up with algorithms and software ideas that could be patented. I implemented many of them, others I simply outlined.

So, I started a wiki page in which I documented these ideas. The goal was to prevent others from patenting them. I called them anti-patents. I usually came up with a new one every month, sometimes several.

This might seem exaggerated, but when you are designing new hardware features that no one has explored, it’s very easy to come up with new things to do with it that nobody has done before. I think this is true for almost any field when you are working on the bleeding edge.

Eventually I stopped maintaing the wiki, it was too much work to describe them in detail, and in many cases I considered them trivial. In spite of that I believe that most of them would have been pursued by NVIDIA if I had chosen to allow it.

Over time I ascended in the corporate hierarchy until I became part of a selected group in charge of the design of future GPUs.

I was working with people much more experienced and smarter than me. I didn’t want to get noticed for causing trouble, but for doing a good work. So, predictably my name ended up in several patent applications.

Today, I deeply regret that.

Matt’s Gregory ACC Tessellation Render

A while ago Matt Davidson contacted me to discuss a few issues with the Gregory ACC source code that we released. Turns out there were some issues in the code that determines whether two patches have the same neighbor configuration and therefore can share the stencils. The code that compares the configurations is not very robust and sometimes reports that two patches have the same configuration, while in practice they do not. In retrospect, it would have been a better idea to simply compute the stencils independently and merge them afterwards.

In any case, he managed to work around the problem and posted a video showing the results:

I’m glad that despite the bugs somebody is actually making use of that code and finding it useful! Cool work Matt!