http://patft.uspto.gov/netacgi/nph-Parse…ac&RS=Rossignac
I found that link on gamedev.net
http://www.gamedev.net/community/forums/topic.asp?whichpage=1&pagesize=20&topic_id=181647
I thought some people here might find that interesting.
From the forum:
I think it is rediculous for people to patent algorithms like this
yer… how dare someone copyright intellectual property. damned inventors.
I was told, once, that a method of drawing a mouse cursor by XORing the cursor with the display was patented. By XORing the cursor sprite, you could delete it by XORing the sprite over the old position. Ingenious!
Other favourite patents include exercising a cat by shining a torch on the floor and moving the spotlight in patterns, and the copyright attached to the frowny : - ( ™
I don’t understand to get a patent you have to mantain “secrecy”, no?
There are 100’s of programs online that use the technique, not counting the fact that Carmack told it to alot of people.
Unless they did it in 1985 or so, they won’t get the patent or if they skipped the “precedent” research it won’t hold up in court. 
Charles
[This message has been edited by Pentagram (edited 09-22-2003).]
the idea of patents is that is not secret, so you can tell if someone is copying you. that’s why some people gamble on the difficulty of the thing they’ve invented (some kind of glue springs to mind; I saw it on a documentary, once) and NOT patent IP. that way no one will know how they did it and can’t duplicate what you’ve done. (Patents only last for so long and then it’s a freeforall).
Having said that, many people are of the opinion that the USA patent office doesn’t do as thorough background check as it could. If the people with this shadow patent can demonstrate that they invented the shadow algorithm before john carmack, then… well, a lot of people are going to have to fork out royalties. 
I taught you had to keep it secret untill you ask your patent. When you ask the patent you make it public so that when the x-years are over everyone can benifit from it, that’s the idea of a patent…
Charles
Originally posted by john:
If the people with this shadow patent can demonstrate that they invented the shadow algorithm before john carmack, then…
You are aware, of course, that Carmack did not invent “Carmacks reverse”. It’s quite probable that the people that put the patent on this technique are in fact the people who came up with the idea (or at least their version of it).
Apparently a guy (in Oz) applied for, and got, a patent for the wheel last year.
Know what? When i read of Carmack´s reverse, i thought: “Why is this genius? I would have done it the same way and a lot of other people certainly have done that before in their Hobby-projects, and now JC gets all the credit for such a simple idea.”
I mean, what is so special about that algorithm? Instead of having the problems at the near-plane, you have the problems at the far-plane, which makes it more suitable for indoor-games, or am i wrong here?
So, if one does real research, i am sure, that you will find some programmer or maths-professor, who already wrote about that algorithm (or implemented it) in the 80s.
In my oppinion “patents” and “software” are two things, which just don´t belong together. The problem is, that politicians, who decide what can be patented, just don´t know anything about software.
Tomorrow i will patent the concept of “walking forwards”, then all of you have to walk backwards, or sidewards, or whatever. Else you will have to pay for it.
Jan.
Patents, when done right, is a good thing. It protects investments and encourages innonvation. When it’s done the wrong way, like patenting overly simple ideas or things someone else actually invented or something that’s public, then it is counterproductive and creates artificial monopolies.
Carmack’s reversed is something I would file under the latter. An idea that’s not advanced enough to be called an invention, and which has also been public for quite some time.
Originally posted by Jan2000:
[b]I mean, what is so special about that algorithm? Instead of having the problems at the near-plane, you have the problems at the far-plane, which makes it more suitable for indoor-games, or am i wrong here?
So, if one does real research, i am sure, that you will find some programmer or maths-professor, who already wrote about that algorithm (or implemented it) in the 80s.[/b]
I don’t think so – stencil shadows were invented in 1991 
Also, just because the algorithm is simple doesn’t mean that it’s obvious. There really are no publications that describe the zfail approach prior to 1999, and if you read about some of the other attempted solutions (e.g. Paul Diefenbach’s image-space capping or Mark Kilgard’s “near plane ledge”) you’ll see that these previous attempts were pretty horrifying.
The main reason why the zfail algorithm is important is not because it moves the capping problem from the near plane to the far plane as you say, but because it paved the way for the first totally robust solution (infinite shadow volumes).
Oh, and Bilodeau filed for the patent in 1999 (it took two and a half years to get approved!?), whereas the mail in which Carmack describes the idea to Mark Kilgard is dated May 2000, so the patent is valid.
– Tom
I thought stencil shadows (the original) were invented back in 1977 or something by Crow.
There are so many patents out there that writing graphics software (and even trivial GUI software) is a potential minefield. Fortunately not everyone wields their patents in an attempt to extort unfair enrichment from the community in the same way that, for example, Unisys did over LZW compression in gif images, or suppress competition the way Adobe has attempted.
OK, Creative patented this, but nobody has pursued any claims over this, and highlighting it is exactly the kind of thing that might get some pointy haired type at whatever organization that has inherited this I.P thinking he’s earned a piece of your pie.
There are at least three parallel inventions of this idea on record now but claiming it is obvious might be a bit of a stretch considering the earlier efforts to solve the problem by other means.
Kudos to Michael Songy, and William Bilodeau, the inventors of reverse stencil testing who have been uncredited until now.
Apparently the poster SimmerD claims he publicly described, at a Creative developer conference, z-fail testing before the alleged patent was filed.
In my opinion, there is a problem with the advanced state of software research vs. the patent office. Ideas will often not be published, because they’re rejected as “trivial”. This means they’re not described in literature, and thus the patent office won’t find it when doing a search, and thus the patent will be issued because they couldn’t find prior art.
Crow didn’t render to a stencil buffer. I think he counted ray intersections with the extruded volume walls, but I haven’t read the paper. zpass stencil buffer shadows is approximately a parallel hardware implementation of that algorithm.
[This message has been edited by dorbie (edited 09-22-2003).]
Well I hope SimmerD kept his slides or that someone was taking notes. If they saw his presentation at the Creative dev conference and then patented the idea that would be pretty darned low. I’ve noticed some developers have very selective memories when it comes to invention.
there are lot of patents out there.
just take a look at this, and cry:
http://www.es.com/about_eands/patents/index.asp
http://patenting-art.com/database/cmpadobe.htm
http://ca.com/patents/
http://www.databank.oxydex.com/prospecting_for_knowledge/3-D_Graphics.html
[This message has been edited by AdrianD (edited 09-22-2003).]
Originally posted by Humus:
[b]Patents, when done right, is a good thing. It protects investments and encourages innonvation. When it’s done the wrong way, like patenting overly simple ideas or things someone else actually invented or something that’s public, then it is counterproductive and creates artificial monopolies.
B]
Patents, in general, when done right, can be a good thing.
Software patents, algorithms patents in my opinion are a bad thing. Most software patents are related to ideas and algorithms that any clever programmer or designer can reach if they work on the patented topic (without any known of the existence of the patent or any previous work).
And software patents are so diffuse that never can be done right so, using your argument, they are a bad thing.
There are many patents that can affect your code, not only stupid patents like Amazon’s one click: http://www.ross.net/compression/patents_by_coverage.html http://www.jmargolin.com/patents/5577913.htm
Or search at: http://www.uspto.gov/patft/index.html
for “video game” or other topics (companies like Atari, Pixar, …). For example: 4572509, 4126851, 4034990,
Probably you have read a couple of weeks ago about MS paying for infringing a patent of plugings embedded in web pages: http://www.infoworld.com/article/03/09/03/HNmicrosoftsloss_1.html
There are a lot of examples…
Now we have a problem, here at Europe, where companies like BSA (Microsoft, Adobe, Apple, Autodesk, …) and other corporations interested in, are trying to impose a similar system that has been demonstrated as wrong in the USA to control what is developed and ensuring that nobody is going to make a product that can compete with theirs.
You can read an open letter from Linus Torvalds sent to the European Parliament at: http://www.effi.org/patentit/patents_torvalds_cox.txt
You can read about the problem (and sign against them) here: http://www.ffii.org/index.en.html
"Patents only last for so long "
Sure, only 20 years, that’s not long, only about the same amount of time our industry has existed!
“Tomorrow i will patent the concept of “walking forwards”, then all of you have to walk backwards, or sidewards, or whatever. Else you will have to pay for it.”
Jan that is such a good example of a patents affect on an industry!
They are just wrong, they should have been abolished years ago, like slavery.
“Patents, when done right, is a good thing”
Maybe for a new toothpaste ingredient, or something REALLY original, but not code snippets or design, these things should go no further than copyrights… like drawings or other IP you cannot and should not be allowed to patent. For software, how can the following effect possibly be good?
“control what is developed and ensure that nobody is going to make a product that can compete”
What if say AOL patented the idea of accessing the internet, forcing us to use AOL?
This is an extreme example but I can just see something like that happening and totally screwing everyone…
“There really are no publications that describe the zfail approach prior to 1999”
There were no publications that told me how to build a DLL file with my particular compiler.
I should run out and get a patent for my original technique, so nobody can build their DLLs without paying me. That will help drive innovation in the industry alright.
There is no good reason why patents should exist. They are going to destroy this industry if we don’t do something to prevent that, and I’m not sure there is much we can do besides attempting to educate our politicians, who could give a damn about us… There should be a central site dedicated to educating programmers about these patents, so we don’t accidentally violate one. Kind of a “technique graveyard” if you will, that can also emphasize the dishonerability and detrimental effects of patents in the software industry.
following the above links, the guy from Autodesk(Mitch Kapor in 1994…)
summed it up nicely with this line.
“Let us stand on each others’ shoulders, rather than on each others’ toes”
There is so much opposition from so many companies, and programming is clearly similar to mathematics, why are patents still an issue? Is microsoft paying the gov or patent office a little extra to keep this up?? Is there anything we can do, or should we all move to europe where U.S. patents can’t affect us? I’m almost afraid to write code knowing all this is happening…
This is a link to a presentation given at GDC in March 1999 that describes zfail stencil tested shadow volumes:
http://developer.nvidia.com/attach/1807
In D3D STENCILZFAIL is a single token that refers to a stencil pass and depth buffer fail fragment path. When the stencil comparrison is ALWAYS then you have the stencil inverts (or increments and decrements) on all zfails. Both are described in the presentation.
It still mentions the need for near capping when it is far capping that is required by the algorithm, although it also mentions capping at the view frustum in what I think is a reference to far capping (based on context).
[This message has been edited by dorbie (edited 09-24-2003).]
This really isn’t a problem, as the patent is too specific. Check the description:
“A method for real-time shadow rendering in a 3-D graphics scene uses an inverted z-test to mark a shadow area in a stencil buffer. Front and back facing shadow volume polygons are rendered subsequent to rendering the scene and corresponding stencil buffer entries are incremented for pixels viewing the back facing polygon when the new z-test is passed and decremented for pixels viewing the front facing polygons when the new z-test is passed. The new z-test is passed for pixels having depth (z) values greater than the corresponding depth value stored z-buffer.”
So, instead of incrementing back-facing/decrementing front-facing, do the opposite (decrement back-facing/increment front-facing). It’s functionally identical since you’re eventually just testing for zero equality or non-equality, not greater or less than. Crisis averted.