gdalgorithms-list

[Algorithms] LightMaps

[<SHA...@ao...>]

Hi,

I want to introduce static light maps, is there any utility out there which 
will precompute the lightmap textures out there if I give it a bunch of 
lights and triangles to play with?

Also, is it necessary for every tri to have it's own lightmap texture or is 
it better to just stick to a few basic lightmaps and put them all into one 
texture?

Regards,

John.

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

[Brian B. <BBa...@sc...>]

**********************
>>> al...@Ex... 08/16/00 01:20PM >>>
If MS doesn't patent everything it does it runs the risk of getting sued
for
using algorithms etc. which some guy may have invented earlier but never
published.

The problem is that there is no way to know if you are the 1st to invent
an algorithm, so if you come up with something that seems new you better
patent it or some other guy who discovered it 2 years ago, who sees that
MS is using this algorithm will apply for the patent it just to be able
to
sue MS for it.

**********************

This isn't quite true as I understand it.  Even if Microsoft patents an algorithm that someone invented earlier, that person can, if he has proof, still patent the algorithm.  He could then force Microsoft to either stop using the algorithm or pay royalties.

From what I understand, patents are just formal notices.  If there is documented prior art, then the patent is null and void.  So if Microsoft or anyone else patents an algorithm that was developed earlier by someone else, they are wasting money because the patent is bogus.

I may be completely off-base here, but as far as I know this is how patents work.

Brian Bartlow

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

[Alex P. <al...@Ex...>]

Thatcher,

I hate software patents as much as the next guy, I think they are a
totally obsolete
concept that was a bad idea 100 years ago and is a worse idea now.
Regarding this comment:

>Companies like IBM and Microsoft are filing
>software patents at a furious pace, carving up territory that was
pioneered
>by others.=20

Since I work here, although I am not a lawyer and my work has nothing to
do
with graphics.

This stupid software patenting has brought up a very dangerous situation
for
companies who have money, like IBM and MS.
If MS doesn't patent everything it does it runs the risk of getting sued
for
using algorithms etc. which some guy may have invented earlier but never
published.

The problem is that there is no way to know if you are the 1st to invent
an algorithm, so if you come up with something that seems new you better
patent it or some other guy who discovered it 2 years ago, who sees that
MS is using this algorithm will apply for the patent it just to be able
to
sue MS for it.
If you dont have money of course you wont be a target.  You wont believe
how many people make money by screwing around with the legal system like
that.

I think patents for software algorithms should be abolished as a whole,
then
we may stand a chance of clearing this up, but without that no one can
afford to take the 1st step, its like the arms race... we need a
Software Patent Abolishment Treaty (SPAT).

BTW.
If I come up with a faster route from my house to work by taking the
freeway,
can I patent it and force everyone else who uses the freeway to pay for
my patent?
I hope not.  But I am afraid that technically this is probably possible.

Alex

Dislaimer:
This message does not in anyway represent an official position of
Microsoft.
These are solely the author's personal opinions.

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

[Ben N. <be...@bl...>]

Sam McGrath <sa...@dn...> wrote:

> Not only that, but there's some other atari patents on there which
> I find pretty hard to believe.  Look at this one:
>
> http://patents.uspto.gov/cgi-bin/ifetch4?ENG+PATBIB-1976-2000+0+
> 972113+4+4+74061+OF+69+291+51+atari
>
> Any other examples of wacky patents??


Here's a pretty wacky one - there also seems to be a patent on
multiplayer (networked) games:

http://patents.uspto.gov/cgi-bin/ilink4?INDEX+0+4572509+F

And multiplayer matchmaking services:

http://patents.uspto.gov/cgi-bin/ifetch4?ENG+PATBIB-ALL+0+988969+0+8+16511+F
+3+78+1+REF%2f4572509

And also on game consoles:

http://patents.uspto.gov/cgi-bin/ilink4?INDEX+0+4126851+F
http://patents.uspto.gov/cgi-bin/ilink4?INDEX+0+4034990+F

There's lots more if you look around a bit.


-Ben

--
Benbuck Nason
 "I gotta make tracks and take back my words 'cause everyone knows
     I didn't mean 'em, I eat em."  - Del the Funky Homosapien

[Algorithms] Numerical methods

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

Cheers, I'll look into them when I get time :)

Jamie


"Graham S. Rhodes" wrote:

> Here are a few of the references that I use:
>
> "Computational Dynamics" by Ahmed Shabana is a decent book on, well,
> computational rigid-body dynamics with full discussion on many many joint
> constraints but not collision detection. It has a fair discussion of
> numerical methods, but it does not analyze the error terms sufficiently.
>
> "Computational Geometry: Algorithms and Applications" by M. de Berg et al.
> This book has some decent discussions on the development of robust geometric
> algorithms that handle degenerate cases well. Although I use the book as
> background, I haven't really tested their algorithms.
>
> One my favorite references on numerical methods is:
>
> "Computational Fluid Mechanics and Heat Transfer" by Tannehill, Anderson,
> and Pletcher. The order of the authors is random for each edition (there are
> two so far). This will be one of my references for the papers I'll be
> preparing.
>
> I know this sounds like a strange reference, but it has one of the best
> discussions I know of on the fundamental nature of numerical errors in
> discrete integration schemes for differential equations. Chapters 2 and 3
> are introductions to DE's (especially PDE's due to the nature of the
> material of the topic of the book), and have nothing really to do with
> fluids. Chapter 4 analyzes truncation error in a bit more detail, and
> studies the stability issues of a laundry list of equations, using a variety
> of different difference formulas.
>
> There is some discussion in the book about how to deal with discontinuities.
> In fluids, discontinuities are shock waves, contact surfaces (two regions of
> fluid that move at different velocities at a common boundary in an inviscid
> flow----such as the interface between water and air at the ocean). But some
> of the rules apply elsewhere, including when you have cracks in a rigid or
> nonrigid body, and when there are collisions in a dynamics problem. The
> trick is detecting the discontinuities in an automated and robust manner.
> Obviously, it is hard to detect collisions in a robust manner while keeping
> time steps large enough for games. (Well, even without dealing with time
> steps). In fluids, shock capture methods are pretty good at finding
> discontinuities, but as with using penalty methods in dynamics there tends
> to be a general mushiness/springiness with oscillations at the
> discontinuity---second order accurate methods are required to come close to
> tightly modeling the discontinuity. Shock fitting methods actually model the
> geometry of the shock explicitly, and this is similar to restarting the
> integration of a dynamics problem at the point of collision. Much nicer if
> you can do it fast enough, harder to code. And you still have the problem of
> intersecting the geometries. (In fluids, the geometry problem involves
> moving the shock geometry until the flow properties on both sides satisfy
> the "Rankine-Hugoniot" equations----required to satisfy the second law of
> thermodynamics for physically consistent shocks. Enough of this tangent!)
>
> Graham Rhodes
>
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...]On Behalf Of Jamie
> > Fowlston
> > Sent: Wednesday, August 16, 2000 4:55 AM
> > To: gda...@li...
> > Subject: Re: [Algorithms] XGDC conference
> >
> >
> > 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
> >
> >
> > _______________________________________________
> > 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]

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

IIRC, not the algorithm itself, only implementations of it. Which is what makes it
even more bizarre to my mind, since anyone can easily implement it....

Jamie


Kevin Lackey wrote:

> No the RSA algorithm was protected under the Beurea of Alcohol and
> FireArms as an export controlled item. It was basically deemed critical
> to national securtiy.
> Kevin
> On Wed, 16 Aug 2000, Matthew Davies wrote:
>
> > 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
> >
>
> --
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] XGDC conference

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

Here are a few of the references that I use:

"Computational Dynamics" by Ahmed Shabana is a decent book on, well,
computational rigid-body dynamics with full discussion on many many joint
constraints but not collision detection. It has a fair discussion of
numerical methods, but it does not analyze the error terms sufficiently.

"Computational Geometry: Algorithms and Applications" by M. de Berg et al.
This book has some decent discussions on the development of robust geometric
algorithms that handle degenerate cases well. Although I use the book as
background, I haven't really tested their algorithms.

One my favorite references on numerical methods is:

"Computational Fluid Mechanics and Heat Transfer" by Tannehill, Anderson,
and Pletcher. The order of the authors is random for each edition (there are
two so far). This will be one of my references for the papers I'll be
preparing.

I know this sounds like a strange reference, but it has one of the best
discussions I know of on the fundamental nature of numerical errors in
discrete integration schemes for differential equations. Chapters 2 and 3
are introductions to DE's (especially PDE's due to the nature of the
material of the topic of the book), and have nothing really to do with
fluids. Chapter 4 analyzes truncation error in a bit more detail, and
studies the stability issues of a laundry list of equations, using a variety
of different difference formulas.

There is some discussion in the book about how to deal with discontinuities.
In fluids, discontinuities are shock waves, contact surfaces (two regions of
fluid that move at different velocities at a common boundary in an inviscid
flow----such as the interface between water and air at the ocean). But some
of the rules apply elsewhere, including when you have cracks in a rigid or
nonrigid body, and when there are collisions in a dynamics problem. The
trick is detecting the discontinuities in an automated and robust manner.
Obviously, it is hard to detect collisions in a robust manner while keeping
time steps large enough for games. (Well, even without dealing with time
steps). In fluids, shock capture methods are pretty good at finding
discontinuities, but as with using penalty methods in dynamics there tends
to be a general mushiness/springiness with oscillations at the
discontinuity---second order accurate methods are required to come close to
tightly modeling the discontinuity. Shock fitting methods actually model the
geometry of the shock explicitly, and this is similar to restarting the
integration of a dynamics problem at the point of collision. Much nicer if
you can do it fast enough, harder to code. And you still have the problem of
intersecting the geometries. (In fluids, the geometry problem involves
moving the shock geometry until the flow properties on both sides satisfy
the "Rankine-Hugoniot" equations----required to satisfy the second law of
thermodynamics for physically consistent shocks. Enough of this tangent!)

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Jamie
> Fowlston
> Sent: Wednesday, August 16, 2000 4:55 AM
> To: gda...@li...
> Subject: Re: [Algorithms] XGDC conference
>
>
> 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
>
>
> _______________________________________________
> 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]

[Kevin L. <lac...@in...>]

No the RSA algorithm was protected under the Beurea of Alcohol and
FireArms as an export controlled item. It was basically deemed critical
to national securtiy.
Kevin
On Wed, 16 Aug 2000, Matthew Davies wrote:

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

-- 

[Algorithms] Bezier Triangle Rendering

[Dave S. <Dav...@sd...>]

I can compute points on a Bezier Triangle,
but I'm having a tough time coming up with
a good tessellator for it.  Are there any
references that has a demonstration of this?

I'm currently looking at fixed subdivision for 
the quadratic case, but because its not bi-quadratic 
in the square sense, like bezier patches, it's harder 
to come up with an easy algo for producing the parameter
space points.

Any ideas or pointers would be much appreciated,
Thanks,
-DaveS

ps.

Conor, that sure was a "wacky" patent. :-P

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

[Conor S. <cs...@tp...>]

 > Any other examples of wacky patents??

http://www.patents.ibm.com/cgi-bin/viewpat.cmd/US05501650__

Its the patent that can be used to get at all ego stroking anal patent
people.

Conor Stokes

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 pa tent]

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

On Wed, 16 Aug 2000, gl wrote:

> > 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?
 
There is a story from back when the 'PACman' lawsuits were being bounced around
and *everyone* with a pacman clone was being sued (rightfully in that case
I think).

Philips were one of the people being sued - and during the first meetings
on the subject, they dug out an old Magnavox patent that effectively covers
all synthetically generated video images used for the purposes of games playing.

The lawsuit was hastily dropped.

Evidently that's one patent that they never try to enforce - but it is evident
that they do employ it defensively.

  :-)

Be VERY afraid!

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] pissing in the well [was: Collision detection pa tent]

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

On Wed, 16 Aug 2000, Matthew Davies wrote:

> 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.
 
I'm guessing that a cryptography technology would be treated as needing
an export license - because (technically) it's a military weapon!

The US has some nasty laws about exporting strong cryptography algorithms.


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

[Jason B. <jba...@ig...>]

IMHO,
if a patent is contested and the originator loses, they should have to pay
all costs plus some large amount to the contestor.
That would encourage companies to only file patents for technology they are
confident of owning; i.e. it moves the onous of investigation (sp?) onto the
companies and builds in penalties for abuse.

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

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

From: "Sam McGrath" <sa...@dn...>
Subject: Re: [Algorithms] pissing in the well [was: Collision detection pa
tent]
>
> Any other examples of wacky patents??

Oh there are lots of foolish patents out there. But keep in
mind getting the patent is only the first, and easiest, step.
If you cannot get the courts to agree with you or cannot
even afford to defend you calim in court then your patent
is worthless.
--
Alan Hurshman

Senior Programmer/Analyst

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

[Sam K. <sa...@ip...>]

patents, pah!


-----Original Message-----
From: Matthew Davies <MD...@ac...>
To: 'gda...@li...'
<gda...@li...>
Date: 16 August 2000 9:46 AM
Subject: RE: [Algorithms] pissing in the well [was: Collision detection
patent]


>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] pissing in the well [was: Collision detection pa tent]

[Tom F. <to...@mu...>]

That second one is for Gauntlet of course. A great game, but patentable?
Then again, these are the people who patented the concept of a register that
scrolls the screen left by the value you write into it.

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

> -----Original Message-----
> From: Sam McGrath [mailto:sa...@dn...]
> Sent: 16 August 2000 11:49
> To: gda...@li...
> Subject: Re: [Algorithms] pissing in the well [was: Collision 
> detection
> pa tent]
> 
> 
> At 11:13 AM 8/16/2000 +0100, you wrote:
> >> 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?
> 
> I found this on the US Patent page:
> 
> http://patents.uspto.gov/cgi-bin/ifetch4?ENG+PATBIB-1976-2000+
0+972113+4+3+3
18762+OF+98+291+51+atari

Not only that, but there's some other atari patents on there which I find
pretty hard to believe.  Look at this one:

http://patents.uspto.gov/cgi-bin/ifetch4?ENG+PATBIB-1976-2000+0+972113+4+4+7
4061+OF+69+291+51+atari

Any other examples of wacky patents??

-Sam
______________________
Sam McGrath
sa...@dn...
http://www.dnai.com/~sammy
ICQ 5151160


_______________________________________________
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 B. <db...@bt...>]

> > Wasn't the reason why there were two version of PGP was because of
> software
> > ...
> > it worries me that my work here can be affected by a seemingly
incompetent
> > US Patents department.
>
> Worry no more... as we speak, our fine politician friends are talking
about
> allowing software (and technology) patents in the EU as well. So if all
goes
> wrong, we'll all be in the same boat in some years time :-(
>

If anybody doesnt know,there is a petition against EU software patents at:
http://petition.eurolinux.org/

David

http://www.dblack.btinternet.co.uk
ICQ #: 24402391
Mobile: (UK) 0778 7836188

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

[Sam M. <sa...@dn...>]

At 11:13 AM 8/16/2000 +0100, you wrote:
>> 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?

I found this on the US Patent page:

http://patents.uspto.gov/cgi-bin/ifetch4?ENG+PATBIB-1976-2000+0+972113+4+3+3
18762+OF+98+291+51+atari

Not only that, but there's some other atari patents on there which I find
pretty hard to believe.  Look at this one:

http://patents.uspto.gov/cgi-bin/ifetch4?ENG+PATBIB-1976-2000+0+972113+4+4+7
4061+OF+69+291+51+atari

Any other examples of wacky patents??

-Sam
______________________
Sam McGrath
sa...@dn...
http://www.dnai.com/~sammy
ICQ 5151160

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

[Eero P. <epa...@ko...>]

Matthew Davies wrote:
> 
> Hi,
> 
> Well I work and live in the UK.  How does this effect me?  Can U.S. patents
> effect my work?
> 

If your product will be sold/manifactured in USA, then it will...

		Eero

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

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

> Wasn't the reason why there were two version of PGP was because of
software
> ...
> it worries me that my work here can be affected by a seemingly incompetent
> US Patents department.

Worry no more... as we speak, our fine politician friends are talking about
allowing software (and technology) patents in the EU as well. So if all goes
wrong, we'll all be in the same boat in some years time :-(

Jim Offerman

Innovade
- designing the designer

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

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

I've just been pointed at this link from another games list;
http://www.patentcafe.com/patents_etc_cafe/pat_faqs3.html

> -----Original Message-----
> From: gl [mailto:gl...@nt...]
> Sent: Wednesday, August 16, 2000 11:14 AM
> To: gda...@li...
> Subject: Re: [Algorithms] pissing in the well [was: Collision 
> detection
> pa tent]
> 
> 
> > 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
> >
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>