A bit of a sensational headline. According to Carmack himself, "the workaround added four lines of code and changed two." The validity of that or any software patent notwithstanding, he's not exactly rewriting the engine.
It's neither novel nor non-obvious. It's a minor variation on a well-known and oft-used algorithm. Carmack himself said as much when he started talking about the algorithm.
And that's where I have a problem with software patents in particular. I'm not in the camps that believe nothing should be patentable, or that some ideas should be patentable - but not software. I'm okay with software patents as a concept (for now). However, with software patents it seems there is a higher than average likelihood that an obvious and trivial patent will be granted. You'll have patents for things like: "a method to confirm a user action whereby a dialog window is presented to the user with several buttons including but not limited to Yes and No." This is just an example but I've seen similar patents granted.
There is also an non-insignificant number of patents that expressly cover an algorithm that would have been found in most computer science textbooks - verbatim - since the '70s. One notable example is the Quicksort algorithm (US 5,175,857). Another is arithmetic coding (known since at least 1976), which has been patented no less than 31 times.
If basic information theory can be patented, there's a problem.
Technically if he wants to do depth-pass instead of depth-fail, he has to change two or three lines of code. He probably added a workaround for the depth-pass near clipping plane errors.
Depth-fail is chosen due to working in the Camera-in-shadow-volume case, not the near clipping plane errors. This is the workaround he needs to solve for considering the Doom3 usage case.
People are talking here about the evil of patents - I remember the original deal causing similar controversy.
Some of Carmacks comments at the time seemed to say that Creative were using their patent to strong arm him into adding support for their hardware into Doom3.
There was also a lot of discussion about whether the patent was reasonable at the time, including, as stated on Slashdot, a claim that Sim Dietrich from Nvidia had demo'd the technique publicly, months before the patent was filed.
It's especially outrageous since Carmack came up with the technique independently of Creative. If it doesn't show that this is a fundamentally trivial patent that should be thrown out, when pretty much the second person to even look at using depth shadows in performance-critical code independently "invents" the technique, I don't know what it would take.
It really doesn't take John Carmack to figure how the patented shadowing algorithm works. It's a very trivial modification of an older shadowing volume algorithm where you slightly change depth test and stencil test settings to get more robust shadow volumes.
I used this algorithm just the other day in some exercise work for uni studies. We actually had this algorithm as an example on one of the basic 3d graphics courses.
When the d3 source is out, I might take the time to re-write the z-fail shadow volume code to doom3 and push it to a git server hosted in a country with sane patent laws. If I have very much time on my hands, I might try to do the shadow volume extrusion on the GPU with geometry shaders (a post-doom3 addition to GPU pipeline).
No, that doesn't demonstrate that the technique is "trivial", but it does make the requirement that the patent be "non-obvious" much harder to defend. As you note, if the first few people to look at the problem come up with the same solution independently, it is dubious that the solution is non-obvious.
Let's not forget that this is Carmack we're talking about. The fact that one of the best 3D graphics programmers in the industry has invented something independently does not tell us much. This thing happens in science all the time and not seldomly for things that are far from trivial.
Software patents are ridiculous, but not because (or only if) they're trivial.
Triviality is supposed to be a test case for the validity of a patent. I think you can make a reasonable argument that if the first few users of a technology all independently invent a technique, that technique should be considered trivial in the context of that technology.
I don't think it's necessary to deify Carmack, either. He is an extraordinary programmer, but he is not super-human.
I gotta say, you raise a good point, but I'm not sure using Carmack as an example here is going to work, because patents are supposed to be for things that an ordinary person in that field of work would not be able to come up with. Carmack is far from ordinary.
> There was also a lot of discussion about whether the patent was reasonable at the time, including, as stated on Slashdot, a claim that Sim Dietrich from Nvidia had demo'd the technique publicly, months before the patent was filed.
Until recently, the US was "first to invent", not first to file, and public disclosure didn't establish a bar date but rather started a count-down to a bar date. In other words, a public disclosure a few months before a filing can be irrelevant. Whether it actually is irrelevant depends on some other details.
Creative agreed to license the use of the "depth fail" technique to id, requiring in return that they implement support for Creative's EAX tech[1]. Perhaps Zenimax legal is not confident in that agreement extending to open source.
It should not be possible to patent an idea, since most great inventions throughout the history were discovered by two or more unconnected people in parallel. You probably know that yourself, you run to google to check if the domain for your next great thing is still free, only to find someone is already working on your idea.
in the hardware world, it's the opposite - you patent an implementation. I'd be able to patent a specific design of a mouse trap, but not the general idea of one
More specifically not the general idea of trapping mice, but the general idea of a hinge and a spring, or the use of cheese on a trigger, or whatever, as general as you can get it.
The point is you patent a specific method of trapping mice, that can be embodied in a device.
Your hypothetical patent would for example not cover a mousetrap that uses a box with the cheese at the bottom and a rod over it that the mouse will fall off if it goes out to try to stretch for the cheese, unless that is explicitly covered in separate claims. So it does not cover the general idea of a mousetrap but of the specific method of catching mice with a spring loaded trap.
(the method I described above works, very well, assuming the sides are slippery/smooth enough for the mouse to be unable to climb them) - my dad tried catching a mouse alive when I was a kid to show me; he tried 4-5 times, and it caught a mouse each time, but all of them were dead when we found them - we never figured out if it was from the very limited fall or from the shock or what it was).
Similar concept that I used with a SimonDelivers box to catch field mice: put bait in bottom of box. place stick against box so it forms a ramp for mouse to walk up.
Mouse walks up stick, sees/smells bait and jumps into box to eat it. Box is too high (about 14" tall) for mouse to jump back out. No, I did not patent this mousetrap!
I tossed the mice to my chickens. The ones that got away were lucky; the rest... well let's just say my chickens lay some mighty tasty eggs :-)
Every idea is math, even ideas for physical devices, as long as it is well-defined. If it's not well-defined, then it's ambiguous, and probably shouldn't be patented.
Physical devices can be modeled with math, they are not however mathematics itself.
"Programming languages" are in reality nothing more than fancy mathematical notations. Conversion to more traditional notations, such as lambda calculus, is so trivial that any computer science undergrad can do it.
To put it bluntly, algorithms are no less math than the Pythagorean Theorem.
I would suggest a clearer example to be long division or euclid's method. Or that software is like stating the Pythagorean theorem and then proving it constructively. This way the process of what goes on when writing code is better captured in how it relates to math.
I strongly disagree. Consider an event-driven presentation and interface layer over a database backend: a very common bit of software. You can't even explain that meaningfully in terms of math, let alone say it is math.
Some software has good math-based explanations, but lots of it doesn't. Saying software is math is rather like saying it's all ones and zeros. True in a weak sense, but it doesn't capture much that is meaningful. Often, a piece of software is better understood as a machine, which is a traditional domain of patents.
edit: I dislike software patents because they are often granted on stupid things in practice. This is probably due to abuse of the system by applicants, which is a response to the lack of expertise and bad previous judgement by the patent office, which seems to invite such abuse.
edit 2: the software patent situation is very hard to change now, since Big Software lobbies very hard to prevent that.
Whether you want it or not, software is math[0][1]. It has nothing to do with it being "ones and zeroes" and everything to do with the work of Turing.
> You can't even explain that meaningfully in terms of math
Oh yes you can. You just lack the tools and understanding for it, and it can get very complex, very quickly, but it can be done, as the Church-Turing thesis (recursion, lambda-calculus, and Turing machines are equivalent) is mathematically proven. And people do actually use that to formally prove correctness of software[2].
> > You can't even explain that meaningfully in terms of math
> Oh yes you can.
No, you can't. Proving the correctness of a word processor has almost nothing to do with the design of its functionality. What should a word processor do? The answer to that question is not math. Does this piece of code do what this written specification says it should do? The answer to that question can be produced by math. Software is at least both of these things. It certainly is not math alone.
> You just lack the tools and understanding for it, and it can get very complex, very quickly
That's an ad hominen in front of an irrelevant statement. The Church-Turing thesis is indeed proven. A simple statement of that thesis goes: "Everything algorithmically computable is computable by a Turing machine. Some things are not thus computable." This idea along its proof, is one of the finest human achievements of the twentieth century. But it sure doesn't tell you how to write a word processor. It tells you that the word processor you wrote could be run on any of a family of equivalent machines, and that it can't compute certain things. That's deep and lovely indeed. Since that proof was created, we knew that Visicalc, Word, TeX and Bit Torrent existed in the space of possible programs, and by implication we knew a lot about their properties. Somebody still had to design and write the fuckers, and they were not doing math when they did so. They were engineering software.
Another completely different angle: If you admit that "The Mythical Man Month" was any kind of contribution to software, can you explain its contribution to mathematics?
> You just lack the tools and understanding for it, and it can get very complex
Software is not math. Math and software are two different things.
It is true that most programs are a solution to a problem that can be formalized with math. However all math is not software and software deals with a lot of issues informally.
I'm with you. I'm a tenured CS professor. I didn't want to argue from authority with those above, but in case it makes you feel better, they're wrong. Software is not math. Let's all go learn more about both things.
Not clear what legal issues surround the release of patented (and licensed) source code. The whole idea behind a patent is to reveal the details of a technique to the public.
id wants to release the code as GPL. To be GPL there can be no legal obstacle to distributing and modifying the code. The patent is not held by id, and I doubt the patent holders have allowed anyone to copy & use this patent as much as they want, ergo you can't copy & use the code as much as you want. So you can't release it under the GPL.
The issue is that they will be releasing the source under the GPL, which requires that you give anyone who receives the code a patent license, but they probably can't give a patent license as they can't sublicense the patent from Creative.
The point of a patent is to prevent other people from making things that implement your idea. The patent was licensed to id, but maybe the license only covered one project.
Doesn't matter. There are no requirements to keep a patented implementation secret, unless for some reason they agreed to do so when they licensed the patent.
Under patent law any user would be violating the patent by playing the game (or possibly just having a copy on their computer), unless they bought a license from the patent holder or were covered by someone else's license.
Source: https://twitter.com/#!/ID_AA_Carmack/status/1371892125197926...