RE: [Algorithms] pissing in the well [was: Collision detection patent]

[Akbar A. <sye...@ea...>]

>A world where algorithm breakthroughs are routinely patented is a very
>scary world for me to contemplate.

hmm.
well we are _sort_ of lucky as graphics/3d programmers.
you should see the problems encryption/compression guys have to work with
:|
i just hope that cg doesn't become like that :|


>Before the release of gzip, I studied a lot of patents on data
>compression to make sure that my implementation avoided all of them.
>See section 8 of the comp.compression FAQ for a small subset (several
dozen) of all patents I've looked at.
http://gailly.net/index.html#patents
http://www.faqs.org/faqs/compression-faq/part1/section-7.html

it's sad that people have to _look_ at what has been "patented" to make sure
they aren't infringing.
greed is a very nasty thing :|


peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Thatcher Ulrich
Sent: Tuesday, August 15, 2000 10:29 PM
To: gda...@li...
Subject: [Algorithms] pissing in the well [was: Collision detection
patent]


Well, here it comes, my off-topic rant on software patents.  Delete now if
you don't want to hear it.

But first, by way of introduction and in the hopes of injecting a shred of
on-topicness, here's my analysis of this specific patent:

URL: http://www.patents.ibm.com/details?pn=US06067096__

Disclaimer: Dammit Jim, I'm a programmer not a lawyer, etc.

Contrary to the subject line, the patent doesn't cover collision detection,
but instead collision response.  It appears to me that the broadest claim of
the patent covers (to translate into graphics-programmer-speak) the
animation of collision response of articulated pseudo-rigid bodies using
penalty forces based on non-linear springs.  I say "pseudo" rigid bodies,
because penalty methods by their nature introduce some squishiness into
collision response.  There's also some language in there making it clear
they're talking about an iterated sampled system, which is pretty much the
case of most of what we talk about here w/r/t physics, although I'm pretty
sure it rules out impulses.

To me it seems like the non-linear springs part is the "novel and useful"
bit.  As Tom wrote:

From: Tom Forsyth <to...@mu...>
> Well, the only non-trivial bits I can see (having glanced through it
> briefly) are:
>
> (1) Pick the right non-linear function for impluse response.
>
> (2) Subdivide time when a collision happens to model it at a finer res.

So we read (1) the same way, but I don't see anything in claim 1 of the
patent which covers (2).  (2) shows up in later claims, but it always
depends on (1).  In other words, if you're doing (2) but not (1), you're not
infringing the patent.  However, digging up prior art on (2) might help
invalidate those later claims, if the first claim can't be invalidated on
its own.

It also seems odd to me that the first claim requires at least one of the
bodies to have at least one rotational joint, but that the first claim
doesn't say anything about penalty torques or anything else about that
joint.  There's probably a legal term for this... it's like a legal
kludge... mentioning a joint only makes the claim narrower, because it's
completely peripheral to the claim.  Perhaps it has something to do with
obviousness... like nonlinear springs are obvious in non-jointed collisions,
but not obvious in jointed collisions?  Gack.

Anyway, from the standpoint of invalidating the patent, I think Tom has it
right... non-linear springs aren't exactly rocket science and there should
be a ton of prior art (none of which Nagle bothered to dig up for his patent
application of course).  Vehicle suspension simulations would be a good
place to start.  It pretty much boils down to the same thing.  IMHO, IANAL
:)

>From the standpoint of avoiding infringing the patent, it seems like the
choices are:

* Don't use penalty methods

* Don't use nonlinear springs in your articulated body collision response

* Come up with a force computation that is not a function of penetration
distance.  Seems like kind of a wacky idea, but maybe base it on pentration
time or velocity.  Or better yet, volume overlap.  Volume is more physically
justifiable anyway.  Slower to calculate, unfortunately.

* Help invalidate the patent legally (e.g. help dig up prior art).

* Boycott Animats until Nagle stops trying to enforce the patent.  Or
otherwise convinve him that software patents are bad for the business of
software development.

OK, enough analysis.  ADVOCACY AND SOME PROFANITY FOLLOWS.  PARENTAL
DISCRETION ADVISED.
 .
.<scroll down>
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .
.
 .


This patent is a piece of shit.  As are many others like it.  It makes me
sick, and it should make you sick, if you enjoy programming and doing R&D
without the protection of an expensive team of lawyers.  Here's why:

Note that the patent claims depend on a method of collision detection.  The
background in the patent references some major collision-detection papers
such as I-Collide by Cohen, Lin et al '95; Lin/Canny '91; Enhancing GJK by
Cameron '97; V-Clip by Mirtich '97.  Imagine for a moment that UNC had
patented the I-Collide work, that van der Bergen et al had patented GJK,
that Mirtich had patented his work.

Would Nagle be using their work in Animats?  Would any of us have the option
of re-implementing these algorithms for our game projects, or would we be
stuck paying to license buggy I-Collide code?  Would any of the improvements
to I-Collide or GJK suggested by the community at large (such as Nagle's
suggestions) be publically available, or would they be buried in a
licensee-only message board somewhere, or would they not even have been
developed in the first place?  Would we have the option of rolling our own
physics for our game engines, or would we have to license Havok et al?
Would Havok et al even exist?

A world where algorithm breakthroughs are routinely patented is a very scary
world for me to contemplate.  It's a world where I would have had to patent
my work on quadtree LOD and loose octrees, either at the behest of an
employer or for my own protection as an individual programmer.  Almost
certainly for an employer, as it would be unlikely for an individual
researcher to be able to afford the necessary licenses on the supporting
algorithms to have even done the work in the first place.  It's a world
where people would be afraid to post substantive content to this mailing
list without running it past the legal department.  It's a world where only
large or well-capitalized companies would be able to afford to develop
cutting-edge games.  It would be a world with a hell of a lot less software
innovation.

Perhaps you think I'm being alarmist.  If you think so, I urge you to delve
into the world of software patents a little bit and see what's going on.
http://bustpatents.com is a good resource, as is http://www.patents.ibm.com
and http://www.uspto.gov  .  Companies like IBM and Microsoft are filing
software patents at a furious pace, carving up territory that was pioneered
by others.  Individuals like Nagle are calling down a heap of karmic abuse
on themselves by trying to profit from extensions to the work of those who
gave freely.  (Pissing in the well, as it were.  As I'm doing now by posting
this rant to a perfectly good mailing list.  That's what makes it so
ironic.)  And I understand why they're doing it... it's purely out of
self-interest, not malice.  Still, to me it seems like a particularly
unenlightened form of self interest which in the long run will only backfire
to the detriment of us all.

In my view it's the patent offices, particularly the USPTO, which are the
primary villains.  Not only are they incompetent, but they're extremely
misguided about software policy in general.  Software armageddon hasn't
happened yet, and maybe it won't, but personally I worry about it.

What can be done?

* Write your congressperson, MP, sultan, village chief, or whoever and
express your views as a programmer and citizen on software patents and how
the patent orifice is being run.

* Refuse to patent algorithms.  Your employer can't patent your invention
without your signature.  (Though it may get you fired, so I can understand
if you're reluctant.  Still, a good programmer can write his/her own ticket
these days; just get another job ;)

*  If you publish something, or even just invent something and use it and
keep a record (don't delete those old version-control-system repositories),
you're preventing someone else from getting a valid patent on your idea.

* Boycott those who patent algorithms.  It's pretty hard to do with the MS's
of the world, although they are sensitive to PR smudges, especially among
the technology-oriented.  Amazon and Animats for example are easy and
deserving boycott targets.

* Help destroy stupid patents by digging up prior art.  I've heard of a
number of plans to establish prior-art registries but I don't have any
concrete pointers yet.

* Peer pressure.

* Other ideas?

Sorry about the rant.  I think I'm done now.

--
Thatcher Ulrich
http://tulrich.com



_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list