gdalgorithms-list

[Algorithms] Collision detection patent

[Michael S. H. <mic...@ud...>]

I have no idea if this is going to start an off-topic patent war, but I'm interested in the reaction here on the following patent.  http://www.patents.ibm.com/details?pn=US06067096__ 

I read about it in the latest Game Developer and did a bit of reading through the patent claims since it appears that Mr. Nagle is attempting to patent methods which have not only been written about prior to his application (March, '98) but actually implemented in our, and other people's engines, prior to '98.

According to GDMag, he actually intends to go after game companies which infringe his patent.

Thoughts?


- Michael Harrison
  High Plains Coder, 
  United Developers / Inertia, LLC
  Work log @ http://lynx.inertiagames.com

Re: [Algorithms] Collision detection patent

[Jeff L. <je...@di...>]

This is my (and my company's) opinion only though I believe that the editorial staff of Game Developer shares my views.

I know John and was quite disappointed with his decision to go this route.  I tried to urge him to compete in the commercial arena.  If he really has some unique ideas that make penalty method simulations so much more stable, he should come up with a licensable system that could compete with MathEngine and Havok or just sell his idea to them.  I have seen his Falling Bodies and as a non-realtime simulator for animation work it seems to work as advertised but that package at least in not ready to compete with the physics engines out there.

His take on his patent is "It's quite broad; it covers most spring/damper ("penalty method") simulations that handle collisions and joints" and he will be watching upcoming games for infringement.  Going after game companies directly is just foolish and biting the hand that he hopes would feed him.  I don't really know how serious he is about this but it sounds like he may be.  Then again it could be just trying to build up IP for VC money or ...?  Game developers that have developed their own physics systems are obviously no happy about this attitude either.

If anyone here either gets a notice from John saying their engine is in violation or is worried about it.  Contact me, I will assist in documenting prior art and providing other contacts for more info.  I disagree with John and believe that plenty of well documented prior art exists.

Also I would currently urge everyone to avoid buying John's Falling Bodies or licensing any technology from him unless he declares a non-aggressive patent policy.  I feel the same way about all such patents and if anyone knows of any other aggressive software enforcements, please let me know.

-Jeff

At 01:46 PM 8/15/2000 -0500, you wrote:
>I have no idea if this is going to start an off-topic patent war, but I'm interested in the reaction here on the following patent.  http://www.patents.ibm.com/details?pn=US06067096__ 
>
>I read about it in the latest Game Developer and did a bit of reading through the patent claims since it appears that Mr. Nagle is attempting to patent methods which have not only been written about prior to his application (March, '98) but actually implemented in our, and other people's engines, prior to '98.
>
>According to GDMag, he actually intends to go after game companies which infringe his patent.
>
>Thoughts?
>
>
>- Michael Harrison
>   High Plains Coder, 
>   United Developers / Inertia, LLC
>   Work log @ http://lynx.inertiagames.com
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Collision detection patent

[Pierre T. <p.t...@wa...>]

John Nagle works for Animats, and more information can probably be found
there:
http://www.animats.com/topics/patents.html

He's also the one responsible for one of the most recent improvements of the
SOLID 2.0 collision detection library (that is, he hinted Gino Van Den
Bergen with a way to handle pathological cases for which the original GJK
method failed).

Now, the above patent covers Animat's last version of "Falling Bodies", a
Softimage plug-in. I don't know more about it, but I hope it only covers
their "slip control" method, and what they *really* invented - or more
precisely, I think they managed to make an old method work, which had
previously been left dead in the dust.

The patent you point out seems a lot more shameful, but so does the famous
Pixar patent about that utterly obvious way of subdividing vertex parameters
in subdivision surfaces. And I don't tell you about the myriad of wacky
patents you can find in data compression. (I think you get dozens of them
even for RLE)

I think (I hope) this won't change anything for game developers.

----- Original Message -----
From: Michael S. Harrison <mic...@ud...>
To: <gda...@li...>
Sent: Tuesday, August 15, 2000 8:46 PM
Subject: [Algorithms] Collision detection patent


> I have no idea if this is going to start an off-topic patent war, but I'm
interested in the reaction here on the following patent.
http://www.patents.ibm.com/details?pn=US06067096__
>
> I read about it in the latest Game Developer and did a bit of reading
through the patent claims since it appears that Mr. Nagle is attempting to
patent methods which have not only been written about prior to his
application (March, '98) but actually implemented in our, and other people's
engines, prior to '98.
>
> According to GDMag, he actually intends to go after game companies which
infringe his patent.
>
> Thoughts?
>
>
> - Michael Harrison
>   High Plains Coder,
>   United Developers / Inertia, LLC
>   Work log @ http://lynx.inertiagames.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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

[Thatcher U. <tu...@tu...>]

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

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

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

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

what about non-profit software or "free" software?
can the company's that hold patents effect us as well?
for ex.
if i release a chunk of software that uses a "patented" routine.
could that company in theory target _ME_ in court?
how does patent infringement court cases even work in the software field.
Big Corporate Company versus small independent developer?
are these even heard of?
what about countersealing by saying that the patent is "logical" or was
going to come anyways?

suppose i _DO_ release that software with the patented routines, could they
sue me?

i have heard some people getting worried about company's taking there homes,
cars, etc..
is this _really_ possible ?

thanks,
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.

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

[Jim O. <j.o...@in...>]

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

Eh? Same here ;-).

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

It is always better to express your frustration, instead of building it all
up inside ;-).

I consider it a sign of weakness if people require patents and lawyers just
to keep up with competitors, in a field where so many people share knowledge
and technology freely, like we do here every day. The paradox being that
patents tend to stall the very process of innovation they were supposed to
protect.

Jim Offerman

Innovade
- designing the designer

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

[Alan H. <ala...@hf...>]

From: "Thatcher Ulrich" <tu...@tu...>
>
> * Refuse to patent algorithms.

Another option if you have real control - patent the algorithm
if you think it valid then license it freely to those who do the same.
Do not license it to companies who try to use software patents
to restrict the creativity of others.


> * Boycott those who patent algorithms.  It's pretty hard to do with the
MS's
> of the world,

Actually MS is a rather late entry in the algorithm patent game.

--
Alan Hurshman

Senior Programmer/Analyst

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

[Thatcher U. <tu...@tu...>]

From: Alan Hurshman <ala...@hf...>


> From: "Thatcher Ulrich" <tu...@tu...>
> >
> > * Refuse to patent algorithms.
>
> Another option if you have real control - patent the algorithm
> if you think it valid then license it freely to those who do the same.
> Do not license it to companies who try to use software patents
> to restrict the creativity of others.

Sort of a "copyleft" for patents... someone on a slashdot forum brought up
this idea, taken a little further:  establish a patent pool which would
grant free licenses to any organization which lacked software patents or
donated all their software patents to the pool... no licenses at any cost
for anybody else.  If the pool contained enough decent patents, it could
conceivably pull the teeth of software patent enforcement in general.

The major obstacle is money.  Unlike copyrights, patents are not cheap to
obtain & maintain.  If the pool didn't collect license fees, the funding
would have to come from somewhere else.  This is also the problem with doing
it as an individual; the expense of obtaining patents makes it costly to
pursue this strategy on principle.

But it's an interesting idea.  Maybe it could work.

--
Thatcher Ulrich
http://tulrich.com

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

[Jeff L. <je...@di...>]

My manditory response rant as a researcher and independent developer.  Please ignore if you do not care.

I obviously agree with Thatcher's sentiment (personally going back to the whole Compton's multimedia debacle anyone else get a legal letter on that one?)  but I feel I need to point out a couple of things.

There are different levels of patents and we have to acknowledge that they are realities in today's business world.  However, we as consumers need to do as you suggest and through our dollars (and business dealings) try and effect change.  

One example is that you mention V-clip.  Well it is actually patented.  It doesn't say anywhere in the code or on Brian's website that this is the case.  However, Merl, who Brian works for routinely patents new technology (some companies pay people extra for this) and Brian doesn't see a problem with it (He even has one with Jessica Hogins who I like as well).  Now MERL is not a bad guy in this.  They encourage Brian to continue to publish his work.  They (at least for now and with regard to software) are non-aggressive about their patents and seem to largely use them for protection.  When I found this out though, I urged Brian to make note of this in his code, publications, and website because I feel potential users must know when things they are looking at are patented for their own protection.  Hopefully Merl will do this.

There are lots of them that are silly.  Just look at SGI's patents. SGI has a completely broad patent on IK.  However, they haven't gone after competition in the animation program market (that I know of).  They also have things like using particles to render hair (probably took a hour hour to come up with this "improvement" on Reeve's particle system).

I used to get mad at all of them.  But have since given up that as impractical.  You could never get anything done and would just worry and not research.  The realities of modern research mean that people sometimes need to build up IP to get money and that can mean building your patent portfolio.  

I agree with Thatcher's list but would add my own spin.

1. Document your personal research well for self protection.  Have a list of every article you looked at so you are armed if someone claims you ripped them off.  This will not totally protect you as independent discovery is not an excuse.  But a well written lawyer letter explaining that your sources are well documented and all from prior art will scare off most.

2. If you work on projects for clients, these days most will ask for you to assist them in filing for patents on your work.  Insist and have put in your contracts that you fully support and will help with copyright protection.  But insist on leaving out any patent language.  We have been doing this for years and it has only been an issue once.  Those people we wanting to be DOT-COM sellouts who thought that a quick patent was the road to riches.  We told them to take a hike.

3. Refuse to buy any product or service from a company that "aggressively enforces and abuse software patents".  I personally disagree with but understand defensive patents but once you use it as a tool to stifle competition, you are off my list.

4. Publish your work so others can use it as prior art.  Some businesses claim that this will lose you customers.  I can prove that it gets you them.

5. Agree totally on the write your congressperson about funding the USPTO so they can afford to get a clue or enact legislation that gives them better guidelines.

At 11:28 PM 8/15/2000 -0400, you wrote:
>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?

[Algorithms] Checking normals against an halfplane

[Pierre T. <p.t...@wa...>]

Ok, another little algorithm I'm fighting with.

Say I have a set of N normals, centered at the origin, in random directions.
The goal is to:
1) check all of them lie on the same side of a plane passing through the
origin
2) find such a plane

That plane is unknown when the routine is called. I must determine whether
such a plane can exist (this is not always the case). Needless to say, it
must be done in a quick way.


I don't expect a light-speed algorithm to exist, but I know you people
sometimes come up with amazing solutions. Hence, worth trying.

Pierre

Re: [Algorithms] Checking normals against an halfplane

[Pierre T. <p.t...@wa...>]

...typo in the title... : "against an halfspace" actually.
...oh, well...

Re: [Algorithms] Checking normals against an halfplane

[Andreas <and...@st...>]

I haven't encountered that problem earlier, so I don't know if
the following (high-level) algorithm is the fastest (or even
correct). But consider doing something like:

1. Find the convex hull of all normals (considered as points).
2. Check if the origin is within this convex hull. If so, there
is no such plane.
3. Compute the normal of the plane as the vector from the origin
to the average point of all points at the edge of the convex
hull. If the special case that the average point is zero, just
compute the cross product of two normals at the convex hull
edge.

--Andreas

Pierre Terdiman wrote:
> 
> Ok, another little algorithm I'm fighting with.
> 
> Say I have a set of N normals, centered at the origin, in random directions.
> The goal is to:
> 1) check all of them lie on the same side of a plane passing through the
> origin
> 2) find such a plane
> 
> That plane is unknown when the routine is called. I must determine whether
> such a plane can exist (this is not always the case). Needless to say, it
> must be done in a quick way.
> 
> I don't expect a light-speed algorithm to exist, but I know you people
> sometimes come up with amazing solutions. Hence, worth trying.
> 
> Pierre
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Checking normals against an halfplane

[Pierre T. <p.t...@wa...>]

Your name reminds me of something.... you wrote a thesis about ROAM, don't
you ? :)

This method seems to work. Unfortunately I don't feel like computing the
convex hull of the vertex cloud before starting the real work. BTW what is
the fastest known algorithm to compute a convex hull? Should be quickhull I
think, but I don't remember, is it O(n*lg n) ?

Point 2) looks slow as well. Is there any fast method to check a vertex is
inside a convex polytope? I can see how to do that in O(n) time, nothing
really better.

Pierre

----- Original Message -----
From: Andreas Ögren <and...@st...>
To: <gda...@li...>
Sent: Wednesday, August 16, 2000 9:35 AM
Subject: Re: [Algorithms] Checking normals against an halfplane


> I haven't encountered that problem earlier, so I don't know if
> the following (high-level) algorithm is the fastest (or even
> correct). But consider doing something like:
>
> 1. Find the convex hull of all normals (considered as points).
> 2. Check if the origin is within this convex hull. If so, there
> is no such plane.
> 3. Compute the normal of the plane as the vector from the origin
> to the average point of all points at the edge of the convex
> hull. If the special case that the average point is zero, just
> compute the cross product of two normals at the convex hull
> edge.
>
> --Andreas
>
> Pierre Terdiman wrote:
> >
> > Ok, another little algorithm I'm fighting with.
> >
> > Say I have a set of N normals, centered at the origin, in random
directions.
> > The goal is to:
> > 1) check all of them lie on the same side of a plane passing through the
> > origin
> > 2) find such a plane
> >
> > That plane is unknown when the routine is called. I must determine
whether
> > such a plane can exist (this is not always the case). Needless to say,
it
> > must be done in a quick way.
> >
> > I don't expect a light-speed algorithm to exist, but I know you people
> > sometimes come up with amazing solutions. Hence, worth trying.
> >
> > Pierre
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Checking normals against an halfplane

[Andreas <and...@st...>]

Pierre Terdiman wrote:
> 
> Your name reminds me of something.... you wrote a thesis about ROAM, don't
> you ? :)

That's me...

> This method seems to work. Unfortunately I don't feel like computing the
> convex hull of the vertex cloud before starting the real work. BTW what is
> the fastest known algorithm to compute a convex hull? Should be quickhull I
> think, but I don't remember, is it O(n*lg n) ?

I have heard that quickhull is the fastest, and that its average
time complexity is O(n*lg n), but O(n^2) in worst case.

> Point 2) looks slow as well. Is there any fast method to check a vertex is
> inside a convex polytope? I can see how to do that in O(n) time, nothing
> really better.

I don't think we can do any better than linear time either, but
that's quite ok considering the problem.

Step 3 computed the normal of the plane, given that such a plane
exist. I realized that it can do wrong sometimes. I tried to
find the central point as fast as possible, but it fails
sometimes. You need to find a better algorithm for this.

--Andreas

> 
> Pierre
> 
> ----- Original Message -----
> From: Andreas Ögren <and...@st...>
> To: <gda...@li...>
> Sent: Wednesday, August 16, 2000 9:35 AM
> Subject: Re: [Algorithms] Checking normals against an halfplane
> 
> > I haven't encountered that problem earlier, so I don't know if
> > the following (high-level) algorithm is the fastest (or even
> > correct). But consider doing something like:
> >
> > 1. Find the convex hull of all normals (considered as points).
> > 2. Check if the origin is within this convex hull. If so, there
> > is no such plane.
> > 3. Compute the normal of the plane as the vector from the origin
> > to the average point of all points at the edge of the convex
> > hull. If the special case that the average point is zero, just
> > compute the cross product of two normals at the convex hull
> > edge.
> >
> > --Andreas
> >
> > Pierre Terdiman wrote:
> > >
> > > Ok, another little algorithm I'm fighting with.
> > >
> > > Say I have a set of N normals, centered at the origin, in random
> directions.
> > > The goal is to:
> > > 1) check all of them lie on the same side of a plane passing through the
> > > origin
> > > 2) find such a plane
> > >
> > > That plane is unknown when the routine is called. I must determine
> whether
> > > such a plane can exist (this is not always the case). Needless to say,
> it
> > > must be done in a quick way.
> > >
> > > I don't expect a light-speed algorithm to exist, but I know you people
> > > sometimes come up with amazing solutions. Hence, worth trying.
> > >
> > > Pierre
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Collision detection patent

[Stephen J B. <sj...@li...>]

On Tue, 15 Aug 2000, Michael S. Harrison wrote:

> I have no idea if this is going to start an off-topic patent war, but I'm interested in the reaction here on the following patent.  http://www.patents.ibm.com/details?pn=US06067096__ 
> 
> I read about it in the latest Game Developer and did a bit of reading through the patent claims since it appears that Mr. Nagle is attempting to patent methods which have not only been written about prior to his application (March, '98) but actually imp
lemented in our, and other people's engines, prior to '98.
> 
> According to GDMag, he actually intends to go after game companies which infringe his patent.
> 
> Thoughts?
 
If you can prove that you had a product out there that used this technology before
the patent was filed - then the patent is invalid because there is "Prior Art".

However, you may have to go to court to prove that - which might be more
costly than settling out of court.

This is of course incredibly stupid - but that's life.  The US patent office
spends on average less than 4 man-hours per patent to research it's validity.
Given that it probably takes a couple of those hours just to read the damned
thing - you may guess how much useful checking they actually do on each one.

You should (of course) write to Mr Nagle pointing out that you think his
patent is invalid.

The one time I was in this situation, I wrote to the patent holder telling
him that I had discovered clear proof of prior art - and that I would therefore
be using this technology irrespective of the patent that he'd filed.  I didn't
hear any more about it.

On one occasion, I filed a patent and by the time the lawyers had
finished writing it, I thought they'd sent me back the wrong patent.
On another occasion, they appended the diagrams from one patent to
the words of another - and NOBODY noticed until after the patent was
granted world-wide.

The whole process is broken.

Another problem with patents is also that they are not written in
plain English - so it's hard to understand exactly *what* they claim.

FWIW though this is only IMHO and IANAL so YMMV.   :-)

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] Collision detection patent

[Tom H. <to...@3d...>]

At 12:25 PM 8/15/2000, you wrote:
>This is my (and my company's) opinion only though I believe that the 
>editorial staff of Game Developer shares my views.
>
>I know John and was quite disappointed with his decision to go this 
>route.  I tried to urge him to compete in the commercial arena.  If he 
>really has some unique ideas that make penalty method simulations so much 
>more stable, he should come up with a licensable system that could compete 
>with MathEngine and Havok or just sell his idea to them.  I have seen his 
>Falling Bodies and as a non-realtime simulator for animation work it seems 
>to work as advertised but that package at least in not ready to compete 
>with the physics engines out there.
>
>His take on his patent is "It's quite broad; it covers most spring/damper 
>("penalty method") simulations that handle collisions and joints" and he 
>will be watching upcoming games for infringement.  Going after game 
>companies directly is just foolish and biting the hand that he hopes would 
>feed him.  I don't really know how serious he is about this but it sounds 
>like he may be.  Then again it could be just trying to build up IP for VC 
>money or ...?  Game developers that have developed their own physics 
>systems are obviously no happy about this attitude either.
>
>If anyone here either gets a notice from John saying their engine is in 
>violation or is worried about it.  Contact me, I will assist in 
>documenting prior art and providing other contacts for more info.  I 
>disagree with John and believe that plenty of well documented prior art exists.
>
>Also I would currently urge everyone to avoid buying John's Falling Bodies 
>or licensing any technology from him unless he declares a non-aggressive 
>patent policy.  I feel the same way about all such patents and if anyone 
>knows of any other aggressive software enforcements, please let me know.

I don't mind patents so much, I mean there has to be some way to protect 
genuine intellectual property. What I hate are bogus patents that are a 
nuisance to the community and stifle development of small developers. 
Threats of the nature this John Nagle make the problems even worse. What 
really inflames me is that even though the patent is obviously bogus to 
those "in the know", the fact remains that the patent exists and if the 
company that owns the patent has money and feels like getting in the news 
they can push it in court with minimal energy. The little guy won't have 
the funds to defend themselves so they're just screwed.

Now, tonight I had a thought that might be quite useful. It seems to me 
that if a non-profit organization was formed with funding from game 
companies that went out and proactively challenged these kinds of patents. 
It would also have a public web page that listed the status of the many 
different patents relevant to the game industry. Patents for which a 
non-aggressive stance had been taken by the owner would be listed, as well 
as ones which were currently in litigation, those that had been deemed 
"bogus" by experts but not by the courts, and those that are in fact valid 
and for which the company is pursuing those who violate their IP. This is 
all rather off the cuff so I don't really even know the feasibility of such 
a thing, but if it is indeed feasible, I can definitely see many game 
development houses being interested in contributing. I'm just a small fry, 
but I know I'd give money, especially if it could some how be considered a 
charitable donation for tax purposes. The way I see it, my taxes paid to 
the US government aren't giving me adequate service in this area, so in 
effect I'd be taking money away from them and giving it to someone else to 
fix their mistakes :)

Also, I don't know if its the same guy or not, but the scenes are almost 
identical so I'm assuming it is. I talked to someone who was working on 
this stuff back around 1995. At that time he was still wrapping up the 
demos and had MPEGs that look to be using the exact same models (untextured 
at the time) as the ones shown on the web page. He was working on making it 
into a plug-in for Softimage, which I'm assuming became Falling Bodies. I 
don't really understand the intricacies of what he's done, or what he's 
patented (I loathe reading patents ... especially after seeing how lawyers 
have taken things I've written and turned into patent submissions that even 
I had trouble following ... don't worry .. they weren't game related), but 
it remains to be seen if what he has is just a good implementation of 
existing methods, or if it is in fact a new twist on old tech that 
constitutes a new invention. I mean, if he's trying to patent collision 
detection and physically based simulation in general then he's cracked 
(unfortunately, patents must be made very general, otherwise they won't be 
approved .. its a very weird process). If he's trying to patent some key 
processes that make the act of physically based simulation better, or at 
least different, than what has been done before, and if he's the first to 
invent those specific processes then I think he has a valid claim and 
something worth protecting. I'll even go out on a limb and say that if the 
scope of his legal actions are limited to other peoples implementations 
that implement the exact same processes that he describes, then I think 
he's within his rights to do so. However, I don't see how it is 
realistically possible to be so selective ... I mean, the only thing you 
can really do is say, "Oh wow .. their stuff looks good, they must be using 
our methods .. better sue them and find out for sure". Its an ugly ugly 
mess that really needs a much better solution than patents.

Tom

Re: [Algorithms] Collision detection patent

[Pierre T. <p.t...@wa...>]

Let me copy here a recent post to comp.graphics.algorithms from Hong Lip
Lim. Worth reading.

===========================================

Re: Siggraph'2000 authors take my research result as their own (long)

In an earlier posting, Mr. Jones mentioned that  it was common
to have "parallel discovery" by independent teams.  I am afraid
Mr. Jones has missed the point.  I never question whether the
authors have discovered the technique on their own, although it
is strange that my technique can be reinvented after so many
years and published in a high caliber conference.  Whether
there is a parallel  discovery is a non-issue here.  The issues
have always been, and remain to be: (1) improper citing of
an earlier reference that covers many basic aspects of their work.
(2) the lack of mentioning of certain attributes of my earlier
approach which, in my opinion, are important to the next levels
of occlusion culling.

I have already talked about both issues in detail in my earlier
postings.  I do not want to delve into further technical details about
the second issue here.  Concerning the first issue: in the old days,
a paper accepted in a conference or journal would be read by very
few people (mostly the reviewers) before it was formally published
during the conference.  However, today the papers are posted
everywhere on the Internet.  The authors can bask in the glory by
promulgating their achievements early and widely.  However, they do
run the small risk of being detected by the irate author of a certain
early and forgotten paper who finds that his work has been copied.
The latter does not have any other option than to protest to the
former if he/she is worth the salt of a researcher.   After the authors
of the later paper have been informed of the earlier work before
the conference, they can no more hide under the excuse of
independent/parallel discovery.  Since they have chosen to publich
their paper prematurely and have benefited from such an action, it is
only fair that they have to either change the paper substantially,
or to withdraw it before the conference when its duplicity has
been pointed out.  This is exactly what the authors of the Siggraph
paper should do.  I have listed in detail in my earlier postings what I felt
the authors of the Siggraph paper have not done or have not done
enough in rectifying the deficiencies of their paper.

Mr. Jones' has quoted the case involving Leibnitz and Newton.
The severity between the two cases are very different as Newton was
totally unaware of Leibnitz work when he published his work.  Even
though it has never been doubted that Newton has independently
discovered his theory, Mr. Jones must be aware that the favoritism
towards Newton is often seen as one of the greatest injustice in the
history of scientific research.   Newton is undoubtedly one of the most
prominent figures in Science. It is also true that even now Calculus
have still been commonly and incorrectly regarded as being invented by
Newton.  However, what has been done by a prominent person and taken
as truth by many people does not necessarily imply that it must be
correct.  Surely Mr. Jone's heart belongs to Liebnitz and not Newton?

Still on the topic of parallel discovery, I have full proof to show that I
had independently discovered occlusion culling and developed my
full technique before the publication of Prof. Teller's first occlusion
culling technique in Siggraph'91.   Prof. Teller's technique at that
time was limited to isothetic surfaces.  On the other hand a technique
similar to mine just appeared in Siggraph'2000.  I should say that there
is at least some difference in maturity of technology between the two.
Should I went on to publish my paper without a single mention of
Prof. Teller's work?  When I prepared my paper in late 1991 I did
considered this possibility.  However, since Prof. Teller's paper had
already been published and I had read it before I submitted my paper,
I decided that I had to follow the standard rules of research and therefore
I went on to cite his work in my paper.  By doing so my original
discovery looked like also-runs to all readers who didn't know the
inside story, which might have contributed to the cold-shoulder I received
for my paper.  While the authors of other conferences have to honestly
abide by and endure the strict rules of academic publication, why should
some authors of a particular conference be exempted from the regulations?
Why should they be even allowed to use parallel discovery as an excuse
when this is not the case?

Mr. Jones mentioned that the authors of the Siggraph paper would
likely to work even more closely with me to address the situation
if they were not so preoccupied defending their reputations from
my accusations.   The unfolding of events was totally different from
what Mr. Jones has speculated.    What really happened
was that after the discovery of that the to-be published Siggraph
paper was very similar to my earlier paper, I had emailed to these
authors and the Siggraph paper committee.  However, the response
from Siggraph and the authors has turned from initially positive to one
that was very strange.   It appeared as if the people involved have
all at once toed the party line and united in ignoring my request. It was
only after the authors and Siggraph had totally ignored my repeated
pleas to find a solution and proceeded to publish their paper totally
unchanged that I had to air the grievance.  Therefore, saying that
the authors ignore me because I have attack them is putting the
cart before the horse.

Mr. Jones feels that the word plagiarism is overly strong.  As a
technical person myself, I have done detail analysis on this matter
and some research on plagiarism.  I knew that the use of the word
would ruffle many feathers and I myself never take pleasure in
using it.  Unfortunately, all the evidence and the definition of the word
just point to the current case as plagiarism.   If Mr. Jones disapproves
of my charge, he should provide counter-evidence and alternative
definition of plagiarism to show that it is invalid.  However, Mr. Jones
most likely can't even quote Siggraph's own official regulations to
support that.  As far as I know, the "not published previously in
SIGGRAPH" policy has never been publicly admitted by Siggraph.

Mr. Jones mentioned that the authors of the Siggraph paper
have themselves entered into the victim list of Siggraph.  This
sounds as if there have been a witch hunt and some holding
of kangaroo court.  If Mr. Jones feels that these authors are
innocent, he should provide more detail about what has
happened and why and how the authors have been victimized.

Thanks to Mr. Jones for telling publicly what has already been
an open secret, that the effective acceptance rule in Siggraph is
"not published previously in SIGGRAPH."   Unfortunately,
Siggraph always states in its call-for-paper that one condition for
its acceptance of papers is totally new and unpublished material.
As Mr. Jones has correctly noted, most people believe that Siggraph
papers are the final words in computer graphics.  If Siggraph can
officially and publicly admit that their effective aceptance rule, then
everybody would know that Siggraph proceedings could not be
treated as ordinary academic references.  The alternative would
be for Siggraph to eschew its secret rules and to adhere to the
universally accepted publication standard.  Needless to say,
the latter is a healthier policy.

Mr. Jones proposed that I should write directly to Siggraph and ACM.
From my dealing with Siggraph, I am very doubtful how much can I
achieve from my letter.  I am probably at the top of Siggraph's shoot-
at-sight list.  Nevertheless I am willing to give it a try.  Mr. Jones and
everyone who has an interest in this matter can also email to me
(hon...@ya...) their views towards Siggraph's publication
policy. I will include their opinions and send them to Siggraph and
ACM.  Please also state if you want your identity be kept confidential.