gdalgorithms-list

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

[gl <gl...@nt...>]

> A practical example is Atari's patent on 'ghost cars' in racing games,
which is still actively enforced.

I never knew they patented that!  Amazing... and scary.  Does anyone have a
link to this one?

However, although I know very little about patents, whenever I do see them
listed they are usually listed for each country individually, suggesting
they need to be applied for separately for each country - can anyone confirm
whether a patent filed in the US can in any way affect other countries
unless specifically applied for there too?
--
gl

> US patents can definitely affect us here, there are various international
> agreements which effectively propagate patents and other intellectual
> property rights, though I'm not certain of the details.
>
> > -----Original Message-----
> > From: Matthew Davies [mailto:MD...@ac...]
> > Sent: Wednesday, August 16, 2000 9:50 AM
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] pissing in the well [was: Collision
> > detection
> > pa tent]
> >
> >
> > Hi,
> >
> > Well I work and live in the UK.  How does this effect me?
> > Can U.S. patents
> > effect my work?
> >
> > Best regards,
> > Matt.
> >
> > _______________________________________________
> > 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] pissing in the well [was: Collision detection pa tent]

[Peter W. <Pet...@vi...>]

Definitely drifting off-topic, but I understood the PGP issue was to do with
US export restrictions on strong cryptography, rather than intellectual
property rights.
I am _definitely_ not a lawyer, but my understanding is that having a US
patent at a minimum stops any other countries granting a patent for the same
thing to someone else, so that the original patent holder can apply for the
patent internationally.

> -----Original Message-----
> From: Matthew Davies [mailto:MD...@ac...]
> Sent: Wednesday, August 16, 2000 11:06 AM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] pissing in the well [was: Collision 
> detection
> pa tent]
> 
> 
> Wasn't the reason why there were two version of PGP was 
> because of software
> patents surrounding the RSA technology and that it only 
> affected the US
> version.  The international version was free of such 
> restrictions.  Or am I
> barking up the wrong tree?  Perhaps this is the wrong 
> discussion forum - but
> it worries me that my work here can be affected by a 
> seemingly incompetent
> US Patents department.
> 
> Regards,
> Matt.
> 
> 
> > -----Original Message-----
> > From: Peter Warden [mailto:Pet...@vi...]
> > Sent: Wednesday, August 16, 2000 10:47
> > To: gda...@li...
> > Subject: RE: [Algorithms] pissing in the well [was: Collision 
> > detection
> > pa tent]
> > 
> > 
> > US patents can definitely affect us here, there are various 
> > international
> > agreements which effectively propagate patents and other 
> intellectual
> > property rights, though I'm not certain of the details. A 
> > practical example
> > is Atari's patent on 'ghost cars' in racing games, which is 
> > still actively
> > enforced.
> > 
> > > -----Original Message-----
> > > From: Matthew Davies [mailto:MD...@ac...]
> > > Sent: Wednesday, August 16, 2000 9:50 AM
> > > To: 'gda...@li...'
> > > Subject: RE: [Algorithms] pissing in the well [was: Collision 
> > > detection
> > > pa tent]
> > > 
> > > 
> > > Hi,
> > > 
> > > Well I work and live in the UK.  How does this effect me?  
> > > Can U.S. patents
> > > effect my work?
> > > 
> > > Best regards,
> > > Matt.
> > > 
> > > _______________________________________________
> > > 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] pissing in the well [was: Collision detection pa tent]

[David C. <Dav...@vi...>]

Don't think so... The problem with PGP was down to the US encryption export
laws.  

Dave

-----Original Message-----
From: Matthew Davies [mailto:MD...@ac...]
Sent: 16 August 2000 11:06
To: 'gda...@li...'
Subject: RE: [Algorithms] pissing in the well [was: Collision detection
pa tent]


Wasn't the reason why there were two version of PGP was because of software
patents surrounding the RSA technology and that it only affected the US
version.  The international version was free of such restrictions.  Or am I
barking up the wrong tree?  Perhaps this is the wrong discussion forum - but
it worries me that my work here can be affected by a seemingly incompetent
US Patents department.

Regards,
Matt.


> -----Original Message-----
> From: Peter Warden [mailto:Pet...@vi...]
> Sent: Wednesday, August 16, 2000 10:47
> To: gda...@li...
> Subject: RE: [Algorithms] pissing in the well [was: Collision 
> detection
> pa tent]
> 
> 
> US patents can definitely affect us here, there are various 
> international
> agreements which effectively propagate patents and other intellectual
> property rights, though I'm not certain of the details. A 
> practical example
> is Atari's patent on 'ghost cars' in racing games, which is 
> still actively
> enforced.
> 
> > -----Original Message-----
> > From: Matthew Davies [mailto:MD...@ac...]
> > Sent: Wednesday, August 16, 2000 9:50 AM
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] pissing in the well [was: Collision 
> > detection
> > pa tent]
> > 
> > 
> > Hi,
> > 
> > Well I work and live in the UK.  How does this effect me?  
> > Can U.S. patents
> > effect my work?
> > 
> > Best regards,
> > Matt.
> > 
> > _______________________________________________
> > 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] pissing in the well [was: Collision detection pa tent]

[Matthew D. <MD...@ac...>]

Wasn't the reason why there were two version of PGP was because of software
patents surrounding the RSA technology and that it only affected the US
version.  The international version was free of such restrictions.  Or am I
barking up the wrong tree?  Perhaps this is the wrong discussion forum - but
it worries me that my work here can be affected by a seemingly incompetent
US Patents department.

Regards,
Matt.


> -----Original Message-----
> From: Peter Warden [mailto:Pet...@vi...]
> Sent: Wednesday, August 16, 2000 10:47
> To: gda...@li...
> Subject: RE: [Algorithms] pissing in the well [was: Collision 
> detection
> pa tent]
> 
> 
> US patents can definitely affect us here, there are various 
> international
> agreements which effectively propagate patents and other intellectual
> property rights, though I'm not certain of the details. A 
> practical example
> is Atari's patent on 'ghost cars' in racing games, which is 
> still actively
> enforced.
> 
> > -----Original Message-----
> > From: Matthew Davies [mailto:MD...@ac...]
> > Sent: Wednesday, August 16, 2000 9:50 AM
> > To: 'gda...@li...'
> > Subject: RE: [Algorithms] pissing in the well [was: Collision 
> > detection
> > pa tent]
> > 
> > 
> > Hi,
> > 
> > Well I work and live in the UK.  How does this effect me?  
> > Can U.S. patents
> > effect my work?
> > 
> > Best regards,
> > Matt.
> > 
> > _______________________________________________
> > 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] pissing in the well [was: Collision detection pa tent]

[Peter W. <Pet...@vi...>]

US patents can definitely affect us here, there are various international
agreements which effectively propagate patents and other intellectual
property rights, though I'm not certain of the details. A practical example
is Atari's patent on 'ghost cars' in racing games, which is still actively
enforced.

> -----Original Message-----
> From: Matthew Davies [mailto:MD...@ac...]
> Sent: Wednesday, August 16, 2000 9:50 AM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] pissing in the well [was: Collision 
> detection
> pa tent]
> 
> 
> Hi,
> 
> Well I work and live in the UK.  How does this effect me?  
> Can U.S. patents
> effect my work?
> 
> Best regards,
> Matt.
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] XGDC conference

[Jamie F. <j.f...@re...>]

Can you recommend any books on the topic? I avoided the numerical methods
lectures while at university, and so far it's been the most useful thing I could
have done there....

Jamie


"Graham S. Rhodes" wrote:

> Wow,
>
> Lots of attendees here! I appreciate the feedback folks. Starting to get
> excited. I'm planning to propose a talk on predicting and managing numerical
> error for stable physics simulation for games. The XGDC topic list on
> xgames3d.com has me listed with a title of "Advanced Physics Programming,"
> but really the idea is to introduce formal techniques for analyzing the
> errors introduced by numerical techniques, the way that the errors
> propogate(sometimes leading to instability and blow-ups), and how to control
> the errors by designing or selecting the right solution scheme. Sounds a bit
> boring, but just about everything I've seen related to game physics
> simulation has skipped over this, and it is essential to achieving the most
> robust physics simulations.
>
> I'm also going to submit at least one proposal to GDC on a related matter.
> By the time GDC rolls around hopefully I'll have some more interesting
> examples, such as tricky collision detection examples.
>
> Graham Rhodes
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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

[Matthew D. <MD...@ac...>]

Hi,

Well I work and live in the UK.  How does this effect me?  Can U.S. patents
effect my work?

Best regards,
Matt.

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] 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] Checking normals against an halfplane

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

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

[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] 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?

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] Understanding VIPM's

[Chris B. <Chr...@ma...>]

Tom, thankyou very, very much for the detialed response. The flanges idea is something I've never have considered, I guess I'm too used to conserving polygons.

The mail format problem is I suspect attributable to our corperate implementation as all my local client settings are set to plain text. In any case I won't post again to the list until they resolve the problem.



-----Original Message-----
From: Tom Forsyth [mailto:to...@mu...]
Sent: Tuesday, 15 August 2000 6:47 PM
To: gda...@li...
Subject: RE: [Algorithms] Understanding VIPM's


Hi Chris - plain text posting please. Ta.


Your first question seems to be a general VIPM question. Basically, you find
the error associated with collapsing all possible edges in your mesh, then
pick the one with the lower error, and collapse it. To collapse an edge, you
simply move one vertex on the edge to the other, and remove degenerate tris.
To expand, you do the opposite. Then recalculate all edge error values that
have changed (since the collapse will have changed some of them), and again
collapse the lowest-error edge. Repeat until there are no triangles left!
This is not locked to a regular grid, or indeed any particular topology -
except that most implementations don't deal with edges that have more than
two triangles using them (though they do handle fewer than two).



I assume you're talking about VIPM rendering of a terrain, rather than just
discrete objects. Be aware that things are not cut and dried for this
subject - as Charles says, there are a number of possible ways to VIPM
terrain.

Because VIPM is best when it takes a fixed "chunk" of something, then
processes it (which is what makes it idea for discrete objects), it needs a
certain adaptation to a continuous thing like a landscape.

The method I favour is to start with a regular heightfield grid. In fact,
any tesselation of your landscape data is just fine (including
non-heightfield data) - the concepts are the same, it's just simpler to talk
about the regular heightfield-type grid. Start with as high a resoloution as
you want (i.e. the maximum detail that anyone will see).

Then split this grid into chunks of a certain size (8x8 seems like a "good"
number, but it all depends on your app). Add "flanges" - small polygonal
edges that extend the chunk, sloping downwards underneath the neighbouring
chunk (and so not normally visible - they get Z-buffered away), and VIPM
each chunk.

The flanges make sure you can have adjacent chunks at different levels of
detail and still ensure there are no cracks between them. Remember - we're
talking about cracks of only a few pixels wide, if that, so it may be
kludgy, but the flange system will do just fine. And the really nice thing
about the flange system, as opposed to the other possibilites that Charles
mentions is that there is no need to communicate any information at all
between chunks at runtime, which reduces CPU time even further. The extra
overdraw you suffer is pretty minimal.


The variation of this scheme is to "mipmap" or "quadtree" your levels of
detail. If you have a view distance that is collossal, then whatever size
chunk you pick, it will always be wrong in some cases. Either the chunks are
too large (physically) and the VIPM is too coarse to reduce detail well at
different distances. Or they are too small physically, and when you draw to
the distance, you are collapsing them down to the maximum - two tris - but
then drawing tens of thousands of them.

The quadtree variation is similar to the quadtree texturing that some people
use, and indeed they do very similar things, and can easily be tied
together. You have fairly small chunks with flanges and you VIPM them as
above. Then you take groups of chunks (classically you take 4 chunks
together, but you could make it coarser and take 16 chunks together or
more), combine them into one mesh (bin the flanges between them, but still
have flanges at the new edges, and VIPM it as a single mesh.

Do this hierarchially, and according to distance, switch to whichever
quadtree level you want. There is also a good argument for controlling the
VIPM collapse order of each level so that the transition between drawing a
level, and drawing its four "child" levels is done when each uses the same
mesh, so that the transition is seamless.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day. 

-----Original Message-----
From: Chris Brodie [mailto:Chr...@ma...]
Sent: 15 August 2000 00:34
To: 'gda...@li...'
Subject: [Algorithms] Understanding VIPM's


I was going to send this e-mail directly to Mr Bloom for help but thought
that other lurkers here might be able to benefit from the answer I receive. 

I've been reading Charles Bloom's website documentation of VIPM's and am
starting to get a little more excited about them now that I realise how much
it can simplify the rendering pipeline amongst other things...

I have some question's though: 

-From what I've read I believe that the VIPM mesh would resemble something
along the lines of a Triangulated Irregular Network that is locked to a
grid. I don't however understand the edge collapsing and vertex insertion
routines. I understand the error array that would come with each
patch(chunk) but just not what to do with it.

-The other thing I don't understand is the edge matching for terrain chunks.
Under something like a triangle or quad ROAM implementation the edge mapping
is easy to visualise but I cant quite grasp how the edges get formed.  Does
the chunk start at minimum resolution, ie a square then get built up as the
error is implemented and the surface subdivided. If this is so at what point
is an edge broken. 

If anyone is interested in helping me understand this I'm happy to write up
a pretty graphical document that'll explain all this to other people new to
the technique (partly so you guys don't have to answer the question again,
partly so I know I understand the technique properly).
Many thanks 


Chris Brodie 

_______________________________________________
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] GJK - algorithm demonstration programs

[Will P. <wi...@cs...>]

>     A useful project would be to take Gino's code in SOLID,
> convert it to Java, and make up an applet that lets you watch
> the algorithm run.  This will make it much clearer how GJK
> converges on a result, and would be very helpful in diagnosing
> some of the problems that GJK implementations encounter.

I can't help but respond to somebody else's post on another forum. :)

This is actually a great idea.  I was thinking of working on some sort of
open source physics library, but I was worried about a variety of issues.  
But by writing it in java, and in such a form that it's less useful in a
commercial game and more useful as a public service, it's a much more
interesting project.  I know it would be useful for a variety of graphics
algorithms as well (i.e. bsp trees, subdivision schemes, and so on), and
I'm sure there are already several similar (thought not integrated)
programs out there.

Anyway, it's an idea.

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will

RE: [Algorithms] Collision detection patent

[Brock, K. <kb...@8c...>]

Howdy,

> 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__ 

	Can't wait for this guys to go after Bungie now they they are owned
by MS.  The fireworks should be very pretty.  =)

	Regards,

	KB

Re: [Algorithms] GJK

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

> Actually, I think your math is right (I had to write it in pencil :) ).
> The reason why it's not a big win is that with this formulation you
> require three multiplies for each term and then a dot product, as opposed
> to just one multiply per term with the dot product table lookups.  This is
> assuming, of course, that multiplies are the expensive operations.

Maybe you're right. As always, I think I'll test both ways and pick up the
fastest.

I asked some questions on comp.graphics.algorithm, where one can reach Van
Den Bergen (as well as John Nagle). I also searched my archives and found
some old messages by Nagle about GJK. Here's a big copy/paste of the whole
thing.....


Pierre

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

> Hi,
> I went through various papers in order to implement my own version of GJK,
> and there are some things I don't get:
>
> - in Johnson's distance subalgorithm, where does the Delta formula come
> from? I followed Gilbert's original paper and tried to re-derive it ny
> expressing the determinant of matrix As, but there's always something
wrong
> in the end. Is the demonstration available somewhere? I expect it can be
> found in Johnson's PhD thesis, but I can't find that one.
>
> - in Van Den Bergen's paper about GJK, page 5:
> "This subset X is the largest of all nonempty Z....". Largest ? I would
have
> said the smallest...? Typo ?
>

Not a typo. The smallest nonempty Z would be any singleton subset of  Y.
Take a pair of points Z = { x0, x1 }, then aff(Z) is a line. Let v = lambda0
x0 + lambda1 x1, lambda0 + lambda1 = 1, the point on aff(Z) closest to the
origin. Iff. the lambda0 and lambda1 are positive then |v(conv(Z))| < |x0|
and |v(conv(Z))| < |x1|, i.e. the line segment x0-x1 contains a point that
is closer to the origin than either x0 or x1. The fact than Z has to be a
minimal set is expressed in the fact that the lambdas have to be positive
(not equal to zero).


> - The delta formula is something like:
>
> Delta(j)(X+yj) = Sigma(i in IX) (Delta(i)(X) * (yi | yk - yi | yj))
>
> ...where | is a dot product.
>
> Why don't they rewrite it that way :
> Delta(j)(X+yj) = (yk - yj) | Sigma(i in IX) (Delta(i)(X) * yi)
>
> ...which saves a lot of dot products, and make all those caches useless ?
>

Hmmm, this looks OK. It has been a while, so I'll need some more thought on
this one. I have some worries regarding the numerics of this formulation. By
doing the subtraction first you might cancel out a lot of precision.

Gino

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

Gerhard wrote:
> I am working on a object-distance routine for collision detection. The
> GJK-algo was recommended to me. I read some very theoretical papers about
> it, and I think I understand how it basically works. I also understand the
> principle of the minkowski sum, which is used in the algorithm. But I
> wouldn't know how to compute it.
> So my question is, how can I compute the minkowski sum of two convex
> polyhedra?

    Try here for some links on GJK.  Check out Cameron's work,
and SOLID.

http://www.animats.com/topics/others.html

    Personally, I think that introducing the concept of the
Minkowsky sum into the design of GJK just complicates the
problem.  What GJK does can be envisioned in object space.

    What GJK is actually doing is trying to find the
closest-points figure, which can be a line, a triangle,
a nonplanar quadrelateral, or a tetrahedron.  These
represent the point vs. point case, the point vs. line
case, the line vs. line case, and the point vs. face case.

    GJK works by starting with a line between two more or less
arbitrary points on each object, and then adds a point to
"improve" the closest-points figure.  The new figure is
tested to determine whether a lower-order part of itself
is better than the whole figure, in which case a point is
thrown out of the closest-points figure.  This process
iterates until no improvement is observed.

    A useful project would be to take Gino's code in SOLID,
convert it to Java, and make up an applet that lets you watch
the algorithm run.  This will make it much clearer how GJK
converges on a result, and would be very helpful in diagnosing
some of the problems that GJK implementations encounter.

John Nagle
Animats
www.animats.com

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

ge...@gi... writes:
> Hello,
> Sorry for replying so late.
> I'd like to thank you for your help.
> You told me that computing the Minkowski sum is not necessary.

    My point was that the explaination of GJK that uses the
Minkowski sum is unnecessarily confusing.

    GJK does not, in fact, compute the Minkowski sum of the two
polyhedra.  That would be a huge data structure.

> I'm a
> bit confused about how GJK works in object space.
> I start with two vertices, one on each object. But now, which vectors do I
> use for the two support mappings?
>
> Here's a list of papers I have about GJK (doesn't mean that I understood
> them all completely, they're a bit complicated for a 17-year old
> student...):
>
> - "A Fast Procedure for Computing the Distance Between Complex Objects in
> Three-Dimensional Space"
> (Gilbert, Johnson and Keerthi)
> - "A Fast and Robust GJK Implementation for Collision Detection of Convex
> Objects"
> (Gino van den Bergen)
> - "Determining the Minimum Translational Distance between Two Convex
> Polyhedra"
> (Cameron)
> - "Enhancing GJK: Computing Minimum and Penetration Distances between
Convex
> Polyhedra"
> (Cameron)

    You have all the right papers.  Useful URLs are

     http://www.win.tue.nl/cs/tt/gino/solid/
     http://www.comlab.ox.ac.uk/oucl/people/stephen.cameron.html

> I have no problem understanding improvement details such as hill climbing,
> but the general algorithm in object space is not yet clear to me.

     It's not really clear to anybody.  Gilbert's original paper is
really hard to follow.  And none of the papers have enough pictures.
Early thinking on GJK applied it to point clouds rather than
convex polyhedra, and included extensions to N dimensions.  This
resulted in a very abstract view of the problem, which is confusing
when you try to follow what it's doing in 3D.

     The key to understanding GJK is understanding what the
"simplex" it uses is.  The simplex is a collection of from 1 to 4
pairs of points from the two polyhedra.  There will never be
more than three unique points from either polyhedron.  The
algorithm runs in two main steps:

1.  Find a "better" point to add to the simplex.
2.  Throw out one or more in the simplex that aren't
    helping.

This iterates until no improvement is possible.

     Step 1 works by using the previous closest-points vector
and examining each polyhedron, finding the point furthest in
the direction along the closest-points vector that heads towards
the other polyhedron.  This is simple.

    Step 2 is a table-driven case analysis that looks at
all the meaningful ways to build point vs. point, point vs.
face, edge vs. edge, etc. cases from the points in the
simplex and finds the current best.  It's hard to follow
what those tables are doing, but you could write an inefficient
exhaustive search that tried all possible combinations and it
would work.

     The original I-COLLIDE paper at

http://www.cs.unc.edu/~geom/I_COLLIDE.html

might be helpful.  This is the original Lin-Canny work.  It's
easier to understand the basic Lin-Canny algorithm than GJK,
but the code is huge.  Lin-Canny works by turning the problem
into a linear programming problem and using an existing linear
programming algorithm to solve it.  Not only does this take
a lot of code with many special cases, it's subject to
numerical precision problems.



John Nagle
Animats
www.animats.com

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

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

[Tom F. <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.


I'm sure loads of people have done (1) (especially with car suspension
systems and the like), and I personally coded (2) about five years ago, and
I'm sure many others have too. Date of filing is 1998, and I suspect there
will be plenty of prior art. My guess is there will be at least three
instances within five miles of where I sit (Guildford - incestuous coding
hothouse of the UK).

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Michael S. Harrison [mailto:mic...@ud...]
> Sent: 15 August 2000 19:46
> To: gda...@li...
> 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] 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] GJK

[Will P. <wi...@cs...>]

> > using your notation:
> >
> > Delta(j)(X + yj) = Sigma(i in IX) (Delta(i)(X) * ((yi | yk) - (yi | yj)))
> >
> > Delta(j)(X + yj) = Sigma(i in IX) (Delta(i)(X) * (yi | (yk - yj)))
> >
> > I don't think you can do that last step.
> 
> Ok, let's fix that, because it may be important. Either it works and nobody
> noticed it before (hence, I'm very happy), either it does not work and it
> probably means I'm not using the right delta formula, which would explain
> why I can't re-derive it (hence, I'm very happy as well because I found my
> bug :)
> 
> Let's get rid of the Sigma, painful to write in ASCII. Am I wrong, or do we
> have the following pattern :

All math is painful to write in ASCII.  I'd prefer latex, because I can
read and write it. :)

>     D(j) = d(0) * y0|(yk - yj)   +   d(1) * y1|(yk - yj)   +   d(2) *
> y2|(yk - yj)  + ......
> 
> with d(i) = scalar values, yi = vectors.
> 
> The dot-product is associative: (rX)|Y = r(X|Y)
> 
> Hence
>     D(j) = (d(0)*y0)|(yk - yj)   +   (d(1)*y1)|(yk - yj)   +
>   (d(2)*y2)|(yk - yj)  + ......
> 
> The dot-product is commutative: X|Y = Y|X
> 
> Hence
>     D(j) = (yk - yj)|(d(0)*y0)   +   (yk - yj)|(d(1)*y1)   +   (yk -
> yj)|(d(2)*y2)  + ......
> 
> The dot-product is distributive: X|(Y+Z) = X|Y + X|Z
> And since yk and yj are fixed (they don't depend on i in the Sigma
> expression):
> 
>     D(j) = (yk - yj)| [ (d(0)*y0)   +  (d(1)*y1)   +   (d(2)*y2)  + ...... ]
> 
> 
> Unless I'm blind and totally missing a key point somewhere, here it is. What
> do you think ?

Actually, I think your math is right (I had to write it in pencil :) ).  
The reason why it's not a big win is that with this formulation you
require three multiplies for each term and then a dot product, as opposed
to just one multiply per term with the dot product table lookups.  This is
assuming, of course, that multiplies are the expensive operations.

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will

Re: [Algorithms] Terrain Normals

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

Hi,

> How can your bilinear filtering method (as depicted below) be used with
the
> terrain layout (as depicted at bottom, the same as mine)?

A bit of flexible thinking I guess... Your (and my) terrain representation
is actually just an approximation of the 'actual' terrain (that is, there
are very few places to be found in the universe where a terrain is made up
of countless triangles in a regular grid). This 'flaw' can produce
unrealistic images (gray bands, for instance). By using a different method
to calculate the normals, I kinda masked the problem(*).

(*) I first used all eight surrounding triangles, but I found that using
only four gave nearly the same result, up to the point where it was no
longer visible.

Jim Offerman

Innovade
- designing the designer

RE: [Algorithms] XGDC conference

[Graham S. R. <gr...@se...>]

Wow,

Lots of attendees here! I appreciate the feedback folks. Starting to get
excited. I'm planning to propose a talk on predicting and managing numerical
error for stable physics simulation for games. The XGDC topic list on
xgames3d.com has me listed with a title of "Advanced Physics Programming,"
but really the idea is to introduce formal techniques for analyzing the
errors introduced by numerical techniques, the way that the errors
propogate(sometimes leading to instability and blow-ups), and how to control
the errors by designing or selecting the right solution scheme. Sounds a bit
boring, but just about everything I've seen related to game physics
simulation has skipped over this, and it is essential to achieving the most
robust physics simulations.

I'm also going to submit at least one proposal to GDC on a related matter.
By the time GDC rolls around hopefully I'll have some more interesting
examples, such as tricky collision detection examples.

Graham Rhodes