Saturday, July 28, 2012

More on Crunch vs. US Patent #20110115806

Doug has updated his blog -- he's now granting the open source community immunity from his patent (#20110115806, "High-Compression Texture Mapping"):

http://dougrogers.blogspot.com/2012/07/high-compression-rate-texture-mapping.html

Here's a screenshot of this URL in its current state (as of 7/28/12 2:46 PM PST):


There are several unresolved issues (for starters, how long will this immunity last once this patent is sold?), but this is a move in the right direction. 

Thursday, July 26, 2012

"Crunch" Open Source Texture Compression Library vs. US Patent #20110115806


I'm the author of crunch, a nifty open source DXTc compression library with two unique features: 
  • R/D optimized DXTc compressionDXTc is generally very lossy, but other DXTc compressors just optimize for maximum achievable quality. crunch allows the developer to purposely trade off quality for relatively large gains in the compressibility of the resulting DXTc data. This mode is cool because the client application doesn't need to be changed at all to benefit (as long as it losslessly compresses the DXTc bits somehow).
  • Transcodable file format: crunch can output mipmapped texture data to a custom format (with the .CRN extension) designed to be quickly transcodable directly to DXTc with no intermediate recompression step. The entire transcoder is contained in a single, large C++ header file. From a quality per bit perspective, .CRN performs more or less the same as R/D optimized DXTc followed by LZMA (sometimes a little better, sometimes worse). Speedwise, the transcode step is very fast (much faster than LZMA for example).

History of Crunch

I created this library in 2009, in my year off between working at the late Ensemble Studios and starting a full time position at Valve in August '09. I had a prototype version working good enough to compete against JPEG+real-time DXTc by mid 2009. I sent the crunch command line tool and library to several people and companies in the game industry (Matt Pritchard at Valve, John Brooks at Blue Shift Inc., and Colt McAnlis who was at Blizzard at the time). Matt Pritchard at Valve actually experimented with an early version of crunch on Half Life 2 texture assets around this time, which was a pretty cool validation that I had something interesting.

I made an attempt at exploring commercial licensing opportunities with Blue Shift acting as a distributor. They had some moderate success with technology licensing/distribution in the past (in the PS1/PS2/Xbox1 era), so it seemed like it was worth a try. But the reality is, commercialization of a library like this is a very, very hard thing to do. Honestly, neither Blue Shift or I really had the time, energy, or focus to devote to things like proper documentation, optimization, API design/simplification, and porting the library to enough platforms to actually make a compelling enough product. Game companies weren't interested in what we had to offer, so I basically put crunch on the back burner and moved to the Seattle area to start a new job at Valve in late '09.

After helping ship Portal 2 and DoTA 2, I took a few months off in late 2011 to decompress and finally push crunch out the door to Google Code. I spent a lot of time ruthlessly simplifying the API down to a few dead simple function calls. I probably went through 4-5 versions of the library, each version getting smaller, more focused, and easier to use. Colt McAnlis (now at Google) and I retested the whole thing on tens of thousands of game textures, photos, and sprites. I finally publicly released it with a ZLIB license on Dec. 27, 2011.

Crunch vs. US Patent #20110115806

Unfortunately, unbeknownst to me I was stepping into a virtual patent minefield by the act of releasing crunch to the world. Just as the library was starting to gain traction with game, WebGL, and open source developers, I received my first ever "Patent Violation Notice" by email from Doug Rogers on July 20th:


I immediately let Doug know that crunch is just an open source library, and that I've not made any money from crunch in any way (no donations, consulting, licensing, etc.) I've actually spent a large amount of my own time (and indirectly, money) developing this library. Since starting at Valve I've learned a ton of things about optimizing for value and focusing on customer's actual needs. I realized that there was much more value to be gained by releasing this code with a very permissive license (ZLIB), and then engaging and learning from the developer community to determine what they really wanted and thought was valuable. (And amusingly, what I thought the community wanted in a library for DXTc texture compression/transcoding, and what they told me they actually wanted, where two very different things.)

Anyway, I know of Doug from his excellent NVDXT texture compression tool he wrote while at NVidia. I used this library while creating the fully deferred renderer for the Xbox 1 launch title "Shrek". Doug's library and tool was basically the gold standard in DXTc compression for many years. I've spoken with Doug, and I don't think his intentions where bad or negative in any way. I'm not a big fan of software patents, but for better or worse they are the "coin of the realm" in the technology world. I'm no expert on patents, but I think Doug was trying to defend his patent from perceived infringement (a kind of "use it or loose it" situation) before releasing a product of his own.

At this point, I've discussed with Doug several possibilities. A few of them involve us jointly commercializing crunch and his code as a single product. However, I feel at this point that crunch is already open source, and I would be doing a disservice to the open source community by re-licensing the library with any sort of commercial terms or a different (less permissive) license. If anything, I'm going to change the license to be even more permissive, or maybe even slap the unlicense on it. I think my email to him earlier today describes the current situation pretty well:
Hi Doug, Thanks, but after considering all this stuff, I honestly think that it's best if I don't get involved in any commercialization activities. I was really interested in this before I started at Valve (and I attempted to use Blue Shift, Inc. as a distributor with console/PC devs in 2009 with little success). But I've now got a job that demands so much of my time and energy that it doesn't make much sense for me to put any more effort into this library. (And if you look closely at the dates, I've barely been able to release any updates to it since the initial release.) I would rather keep pushing the state of the art forward in my spare time, and I'm cool with just having my name associated with these efforts. Basically - I've already got a demanding day job, and I would rather not turn something that is a fun hobby (with possibly indirect career benefits) into another job.
I don't want to slow down you or others with attempting to commercialize this stuff, and I don't want companies or individuals to not be able to benefit from it. I think crunch has demonstrated what is possible, to enough of the right people, that there's a small but growing market out there for the right solutions. crunch's license is ZLIB, which is already very permissive, and I'm open to changing the license to something else (MIT/BSD, even unlicense.org) if that helps move things forward. I already have a bunch of my open source compression code (miniz, LZHAM, jpeg-compressor) used by several companies (like Epic Megagames, Valve, and Crytek), so this doesn't seem fundamentally any different to me. All that I ask is for some credits somewhere, but even that isn't required. If you go to Siggraph, I can explain how the library is put together, and most parts are pretty easy to modify.
On the technical side, I don't know a whole lot about your product, but it may be exactly what Google's WebGL team needs right now. Is your output data easy to transcode to DXTc, and further compressible with gzip? I ask because .CRN is not any of these things (the CRN transcoder is large and complex, so it's not the best fit for use in Javascript/WebGL applications). 
What the WebGL guys really need is:
  • A format that is quick and super easy to transcode to DXTc (in C or Javascript)
  • Total transcoder code size must be very small (because it needs to be transmitted with the webpage each time it's loaded)  
  • A format that is very compressible using specifically gzip (because gzip is supported by the browsers) 
  • Ideally, something that is roughly competitive against JPEG+real-time DXTc, or only 10-20% worse file size for the same PSNR. 
  • PVRTC support (DXTc+PVRTC will cover all the mobile platforms that matter)
.CRN isn't really the best fit (it was originally designed for PS3/X360 console games, not WebGL). There's a Google dev who has been trying to modify crnlib so it supports "raw" files, but I don't think he's made much progress. And crunch's RD optimized DXTc mode+gzip is ~30% larger than .CRN for the same PSNR, so it's not a compelling enough solution. (You really need LZMA or LZHAM for this option to be competitive, which isn't available in the browser, and cross compiling these libraries is not practical or compelling) If you want, I can introduce you by email or in person to the devs at Google who have been working on this stuff.
Last I heard, the SOE guys are using crunch's RD optimized DXTc mode for Planetside 2, because the ratio gain from .CRN doesn't justify the extra complexity (and potential patent risk) of transcoding. However, now that they are aware of what's actually possible, if there was a commercial solution available I would bet they would go for it. Let me know if you would like to talk to these guys.

Next Steps

At this point, I would really like to move forward with my life and put crunch (and S3TC/DXTc!) in the past. I strongly feel that video card vendors should get together and create a new set of GPU-friendly, open texture compression formats that are relatively easy to compress/decompress, very well defined, with easy to use open source libraries, and are also quickly and efficiently transcodable (in C, Python, Javascript, etc.). I don't think any of the existing texture compression formats (PVRTC, S3TC/DXTc, ETC, the new DX11 formats, etc.) are good solutions to the actual problems developers are facing today (more on this later).

Siggraph

It so happens that Brandon Jones, a WebGL and Javascript developer, is going to be demonstrating crunch (transcoding in Javascript of all things!) at the WebGL BoF (Birds of a Feather) event at Siggraph:

Brandon Jones: Crunch/DXT/Rage demo
http://www.khronos.org/news/events/siggraph-los-angeles-2012
Wednesday, August 8, 4:00 PM – 5:00 PM, JW Marriott Los Angeles at LA Live, Gold Ballroom Salon 3 

Also, I'll be at the later OpenGL BoF event at Siggraph to give a short presentation on Left 4 Dead 2 Linux:
Left 4 Dead 2 Linux: From 6 to 300 FPS in OpenGL– Rich Geldreich (Valve)
Wednesday, August 8, 6:00 PM – 7:00 PM, JW Marriott Los Angeles at LA Live, Gold Ballroom Salon 3