gdalgorithms-list Mailing List for Game Dev Algorithms (Page 1408)
Brought to you by:
vexxed72
You can subscribe to this list here.
2000 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(390) |
Aug
(767) |
Sep
(940) |
Oct
(964) |
Nov
(819) |
Dec
(762) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2001 |
Jan
(680) |
Feb
(1075) |
Mar
(954) |
Apr
(595) |
May
(725) |
Jun
(868) |
Jul
(678) |
Aug
(785) |
Sep
(410) |
Oct
(395) |
Nov
(374) |
Dec
(419) |
2002 |
Jan
(699) |
Feb
(501) |
Mar
(311) |
Apr
(334) |
May
(501) |
Jun
(507) |
Jul
(441) |
Aug
(395) |
Sep
(540) |
Oct
(416) |
Nov
(369) |
Dec
(373) |
2003 |
Jan
(514) |
Feb
(488) |
Mar
(396) |
Apr
(624) |
May
(590) |
Jun
(562) |
Jul
(546) |
Aug
(463) |
Sep
(389) |
Oct
(399) |
Nov
(333) |
Dec
(449) |
2004 |
Jan
(317) |
Feb
(395) |
Mar
(136) |
Apr
(338) |
May
(488) |
Jun
(306) |
Jul
(266) |
Aug
(424) |
Sep
(502) |
Oct
(170) |
Nov
(170) |
Dec
(134) |
2005 |
Jan
(249) |
Feb
(109) |
Mar
(119) |
Apr
(282) |
May
(82) |
Jun
(113) |
Jul
(56) |
Aug
(160) |
Sep
(89) |
Oct
(98) |
Nov
(237) |
Dec
(297) |
2006 |
Jan
(151) |
Feb
(250) |
Mar
(222) |
Apr
(147) |
May
(266) |
Jun
(313) |
Jul
(367) |
Aug
(135) |
Sep
(108) |
Oct
(110) |
Nov
(220) |
Dec
(47) |
2007 |
Jan
(133) |
Feb
(144) |
Mar
(247) |
Apr
(191) |
May
(191) |
Jun
(171) |
Jul
(160) |
Aug
(51) |
Sep
(125) |
Oct
(115) |
Nov
(78) |
Dec
(67) |
2008 |
Jan
(165) |
Feb
(37) |
Mar
(130) |
Apr
(111) |
May
(91) |
Jun
(142) |
Jul
(54) |
Aug
(104) |
Sep
(89) |
Oct
(87) |
Nov
(44) |
Dec
(54) |
2009 |
Jan
(283) |
Feb
(113) |
Mar
(154) |
Apr
(395) |
May
(62) |
Jun
(48) |
Jul
(52) |
Aug
(54) |
Sep
(131) |
Oct
(29) |
Nov
(32) |
Dec
(37) |
2010 |
Jan
(34) |
Feb
(36) |
Mar
(40) |
Apr
(23) |
May
(38) |
Jun
(34) |
Jul
(36) |
Aug
(27) |
Sep
(9) |
Oct
(18) |
Nov
(25) |
Dec
|
2011 |
Jan
(1) |
Feb
(14) |
Mar
(1) |
Apr
(5) |
May
(1) |
Jun
|
Jul
|
Aug
(37) |
Sep
(6) |
Oct
(2) |
Nov
|
Dec
|
2012 |
Jan
|
Feb
(7) |
Mar
|
Apr
(4) |
May
|
Jun
(3) |
Jul
|
Aug
|
Sep
(1) |
Oct
|
Nov
|
Dec
(10) |
2013 |
Jan
|
Feb
(1) |
Mar
(7) |
Apr
(2) |
May
|
Jun
|
Jul
(9) |
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2014 |
Jan
(14) |
Feb
|
Mar
(2) |
Apr
|
May
(10) |
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
(3) |
Dec
|
2015 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
(12) |
Nov
|
Dec
(1) |
2016 |
Jan
|
Feb
(1) |
Mar
(1) |
Apr
(1) |
May
|
Jun
(1) |
Jul
|
Aug
(1) |
Sep
|
Oct
|
Nov
|
Dec
|
2017 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(1) |
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2022 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
(2) |
Dec
|
From: Tom F. <to...@mu...> - 2000-08-18 00:00:57
|
I've been thinking about this a bit. And probably for exactly the same hypothetical equipment you're thinking of. It's certainly a real pain having to feed your T&L through push-mode streaming DMA, rather than a demand-loaded vertex cache. My current thoughts are to (offline) take the fully-expanded stream of indices (whether list or strip, doesn't realyl matter). Then simulate a vertex cache of around the size that will fit - you mention 100 verts, which is hooooj by vertex cache standards. Anyway, you will of course get very few cache misses, but you will get a few. While doing this, write out a "command buffer" sort of thing that contains indices, vertex data when the cache misses (replicated for each miss) along with the position in the cache that this will go to. And the indices are these cache positions (so in this case, you can shrink them to bytes, not words, which is a bonus), not their original values. So you are basically implementing a vertex cache, but where the behaviour of the cache is calculated beforehand, offline, so that you can use push-model. Now, to use VIPM, you do standard VIPM on this modified command buffer with the CPU (the vertex data in the command stream is ignored), and then throw the buffer at the T&L unit, up to the last triangle you want to draw. And of course you have precompiled versions for different powers of two of vertices, which will bin stuff earlier as well. To be clear, I'm talking about the old-style VIPM, where indices are stored in reverse collapse order, not the stuff Charles was talking about very recently. This is just a rough thought-sketch, but it's essentially the same as normal VIPM, but with push-mode instead. It is slightly less efficient, since if there is a triangle that references vertex 3, and then that vertex gets binned through an edge collapse, but the triangle is still drawn (because it now uses the other vertex on that edge), then the data for vertex 3 will still be in the "cache", and will still use DMA space. But as soon as all tris that, at full, rez, use this vertex, that vertex will also be binned, so vertices do eventually vanish from the DMA stream, just not as soon as with the demand-loaded case. I'm sure someone will point out the flaws in this - I haven't really worked it through properly yet. Note that although the collapse-order indexed list method is now officially Old And Slow (and without a line of code being written :-), that is because of poor vertex cache performance. But in this case, we have a hooooooooj cache, so that really shouldn't matter. And the powers-of-two versions will help a lot - they need to, as the cache use isn't dynamic, so as you do more collapses, you effectively have a smaller cache (since entries are taken up by vertices that are no longer referenced). Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > -----Original Message----- > From: Nicolas Serres [mailto:nic...@ch...] > Sent: 18 August 2000 00:23 > To: gda...@li... > Subject: [Algorithms] VIPM console implementations > > > I'm rather curious about VIPM; I don't use this technique > right now, and I'd > like to know if some of you already implemented it in an > efficient way as > microcode for a next-gen console having a DMA? I don't think > indexed stuff > is very efficient in that case, but I might be wrong.. I'd > like to hear from > your implementation issues > > You tend to have many many vertices, that can be efficiently > int-quantized > and depacked after the dma transfer so you save lots of > bandwidth, but you > still have to store the depacked stuff in the small "tl-like" > unit memory. > To be efficient you also have to double buffer this memory. > This leads to a > model splited in realtively small chunks. > > Let's say my "hypothetical" console lets me have 8 k in a > half-buffer, a > typical simple depacked vertex (with normal, mapping, and > rgb) is about 64 > bytes in temporary local memory.. This leads to about 100 > vertices and index > data. This is relatively small. Of course I can't have an index that > references something outside of the current chunk.. I think > it is a very > strong limitation for VIPM. > > Is VIPM still efficient done that way, with such small chunks > ? Did I miss > something ? > > > Nicolas > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
From: Nicolas S. <nic...@ch...> - 2000-08-17 23:26:30
|
I'm rather curious about VIPM; I don't use this technique right now, and I'd like to know if some of you already implemented it in an efficient way as microcode for a next-gen console having a DMA? I don't think indexed stuff is very efficient in that case, but I might be wrong.. I'd like to hear from your implementation issues You tend to have many many vertices, that can be efficiently int-quantized and depacked after the dma transfer so you save lots of bandwidth, but you still have to store the depacked stuff in the small "tl-like" unit memory. To be efficient you also have to double buffer this memory. This leads to a model splited in realtively small chunks. Let's say my "hypothetical" console lets me have 8 k in a half-buffer, a typical simple depacked vertex (with normal, mapping, and rgb) is about 64 bytes in temporary local memory.. This leads to about 100 vertices and index data. This is relatively small. Of course I can't have an index that references something outside of the current chunk.. I think it is a very strong limitation for VIPM. Is VIPM still efficient done that way, with such small chunks ? Did I miss something ? Nicolas |
From: Akbar A. <sye...@ea...> - 2000-08-17 23:17:52
|
just couldn't- we write software. patents effect us. we also write algoritms. algoritms are getting patented. we can be effected. we make a living of writing software. it's better to be "prepared"; then to ship your game/application, only 3 weeks later to hear a certain lawywer/company barking up your ass. and court fees cost "money". going to court is not _FUN_ and "giving" away money in court costs is not something most people enjoy. some of the gcc developers have been to court on there software. see the gcc archives, there was a thread on patents, going to court and being prepared; which lasted for a few months. LOTS of "IMPORTANT" people (including linus as well) had something to say on this. i don't know about you, but this thread has helped me a lot on what "TO AVOID". a perfect exaple was the one where the guy got in trouble with a midway cause they included a ghost option. do you think they would have included this in the game if he had heard about the patent? akbar A. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Matthew MacLaurin Sent: Thursday, August 17, 2000 2:40 PM To: gda...@li... Subject: [Algorithms] ENOUGH ABOUT THE PATENTS, PLEASE Hey folks; Can we stop talking about ghost cars, centrifugal *ahem* devices, and whatnot? We've got a bad noise problem here. This is not a political forum. And please do NOT "list any current patents on 3d character animation that they know about." COME ON! It's an *extremely* worthwhile topic, but it's not an algorithm. -- Matt _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
From: Akbar A. <sye...@ea...> - 2000-08-17 23:09:52
|
i see, apparently big companies have more power than i thought they have. oh well. somebody mentioned that companies like ms and ibm are patenting a lot of algo's. i understand that these companies must protect there assets by taking these extreme action, but; a patent doesn't effect us if the owner doesn't take action? couldn't ms or ibm sign official treaties with developers saying that they will not sue developers who use these algorithms. by doing this, they are still protecting there assets from greedy people looking for money and, us as developers can work of there algorithms by not having the fear of getting sued? i thought of this last night when i was sleeping, i hope this makes sense :-) peace. akbar A. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Kent Quirk Sent: Thursday, August 17, 2000 7:37 AM To: gda...@li... Subject: Re: [Algorithms] pissing in the well [was: Collision detection patent] IANAL, but as I recall, the phrase is "obvious to a skilled practioner". It seems clear that the USPTO strategy in recent years has been to ignore that phrase and let the courts sort it out later. Understand, however, that most of these cases never reach court. What tends to happen is this: * GreatSatan Corp. goes to the USPTO and gets a patent on the bubble sort. * They include it in the list of several thousand patents they hold, and sign a cross-licensing agreement with IBM, Microsoft, and several other large companies. * They find several small companies with less money than brains and notify them they're infringing on the patent, but that they'll license them the right to continue to use the technology for a smallish fee (a couple of thousand dollars). Realizing that it will cost them that much for the first phone call with a decent patent attorney, they sign the license. * They find a couple of medium-sized companies and extort them for large license fees. They point out that all sorts of companies both big and small have licensed this patent rather than fight it. If anyone puts up a fight and starts talking about going to court with "prior art" or "obvious" claims, they drop the fees and give away the license. Played properly by a big company with idle attorneys, even the most obvious patent never goes to court, unless they have the bad luck to find someone who is both principled and rich (rare in itself), and who also cares enough to fight to the bitter end. What does this mean to the free software developer? If someone thinks the patent is being infringed, and that your work is impacting their patent rights (if you give it away how can they sell it?), they can get an injunction to keep you from distributing the work, and they can sue you for damages. On the other hand, if the patented technology is only a small portion of what you're doing, and you're really doing it for free, you might find some patent holders would be willing to license it for free or very cheap. Kent Jani Peltonen wrote: > > As far as I remember, one of the requirements for a new patent is that the > patented idea be non-obvious. Lot of the software patents I have seen are > clearly obvious to someone who works in the field but how would you prove > that in a court. > > > ---------- > > From: Akbar A.[SMTP:sye...@ea...] > > Reply To: gda...@li... > > Sent: Thursday, August 17, 2000 2:28 AM > > To: gda...@li... > > Subject: RE: [Algorithms] pissing in the well [was: Collision > > detection patent] > > > > what about non-profit software or "free" software? > > can the company's that hold patents effect us as well? > > for ex. > > if i release a chunk of software that uses a "patented" routine. > > could that company in theory target _ME_ in court? > > how does patent infringement court cases even work in the software field. > > Big Corporate Company versus small independent developer? > > are these even heard of? > > what about countersealing by saying that the patent is "logical" or was > > going to come anyways? > > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list -- ----------------------------------------------------------------------- Kent Quirk | CogniToy: Intelligent toys... Game Architect | for intelligent minds. ken...@co... | http://www.cognitoy.com/ _____________________________|_________________________________________ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
From: Patrick E. H. <hu...@tr...> - 2000-08-17 22:06:33
|
>is there any way to implement this without recursion? >any opinions on using recursion for anything? So what's wrong with recursion? Directory trees are a natural for this.. You could always build a local stack of directories in your current level, then keep looping through that stack building further stacks, etc.. Basically recreating what a recursion would do anyways. <question> Where in heck did recursion get such a bad rap? </question> |
From: J M. <jmo...@bi...> - 2000-08-17 21:51:17
|
First, an introduction. Name is Jesse M Moore, and programming (as a hobby) since Turbo Pascal 1.0. now the question: Writing a program that searches for a file on disk. I need search to sub folders. Typically the algorithm is like this: (in pseudo-pascal code) procedure Search procedure nextdir; begin FindFirst; repeat if (searchrec yields a subdirectory) then NextDir; until FindNext=0; FindClose; end; .. is there any way to implement this without recursion? any opinions on using recursion for anything? thanks (and trying not to be a lurker) |
From: Nicolas S. <nic...@ch...> - 2000-08-17 21:45:05
|
I played Sega Rally 2 a lot last summer, when we (some coders) decided to sacrifice hour holidays not to be late for the dreamcast version of our game, and our wonderful paranoid management left on vacation to some sunny place without giving us the keys of where the devkits were stored... Hmmm I'm glad we all left this company.. At least this improved my sega rally 2 skills and I can tell you that in my japanese version, there were definitely ghost cars (althought they were opaque). Did it stay in us/european versions? I don't know what attitude got hasbro with sega, as it is a very different company because they are also the ones you require approval from them, and major buisness partners.. Did they ever sue nintendo, sega or sony, who obviously did infringe some of their "claimed" patents ??? I'm curious if they also sue those major console companies for their first-party titles. IIRC, sgi has many patents on character animation (and probably lots of other 3d stuff too)..What's their attitude towards game developers? Nicolas ----- Original Message ----- From: "Tom Forsyth" <to...@mu...> To: <gda...@li...> Sent: Thursday, August 17, 2000 11:06 PM Subject: RE: [Algorithms] pissing in the well [was: Collision detection pa tent] > I seem to remember TOCA had a ghost-car mode in it. Did they license it, or > just put their foot down and say "go on - sue us then". > > Tom Forsyth - Muckyfoot bloke. > Whizzing and pasting and pooting through the day. |
From: Jeff L. <je...@di...> - 2000-08-17 21:44:40
|
There are hundreds. Go to the IBM patent server and type in animation. It is a huge list covering tons of different areas. A list of game related ones is a good idea but should be done off maillist since it would be large. I will compile the ones I have noted and post them on my website or to interested people. -Jeff At 11:30 AM 8/17/2000 -1000, you wrote: >Can people please list any current patents on 3d character animation that they know about. For both creation, and display of character animation. > >thanks >dave |
From: Matthew M. <ma...@me...> - 2000-08-17 21:41:44
|
Hey folks; Can we stop talking about ghost cars, centrifugal *ahem* devices, and whatnot? We've got a bad noise problem here. This is not a political forum. And please do NOT "list any current patents on 3d character animation that they know about." COME ON! It's an *extremely* worthwhile topic, but it's not an algorithm. -- Matt |
From: Dave S. <Dav...@sd...> - 2000-08-17 21:38:34
|
sorry |
From: David P. <eti...@ho...> - 2000-08-17 21:30:31
|
Can people please list any current patents on 3d character animation that they know about. For both creation, and display of character animation. thanks dave ________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com |
From: Akbar A. <sye...@ea...> - 2000-08-17 21:24:12
|
what about companies like nintendo? in mario kart 64 and a few others there is a "ghost" mode. peace, akbar A. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Dean Calver Sent: Thursday, August 17, 2000 1:00 PM To: gda...@li... Subject: Re: [Algorithms] pissing in the well [was: Collision detection pa tent] The most annoying thing about the Atari 'ghost car' patent, is that Midway (who now own it) ACTIVELY enforce it, I know because 2 years the game we had just released (Powerboat Racing) was hit with it, we had a mode with a recorded ghost boat to race again. Midway told us we had infringed there patent and could they have some money, I never found our if we paid or if our publisher (Interplay) fought them. So now we never include ghost anything in any our race games. The actual defination involves transparency (ghost like look), so if you do include pre-recorded cars to race again the visual image is very important. An lawyer thought that if we had made the 'ghost' solid it wouldn't have affected us, but we were released by this time. Usual stuff, that I'm not a lawyer and my memory be going so name of companies may be wrong etc (I pretty sure Midway brought Atari though) Be afraid, be very afraid Deano Dean Calver, Senior Games Programmer, Promethean Designs Ltd. ----- Original Message ----- From: "gl" <gl...@nt...> To: <gda...@li...> Sent: Wednesday, August 16, 2000 11:13 AM 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 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
From: Adam M. <amo...@dp...> - 2000-08-17 21:16:02
|
>and simpler distance computations can be used. Would you mind sharing some >details there? (..oh... wouldn't this code be included in Source Commander >? - I think that was the name of the project IIRC. I'll check that.) Sun, not Source! But yes, the source code is all on my site, as part of SC. It is all in this function, in the file CollBody.cpp: void CollBody::GetCollisionReport(Mat33 &q1, Mat33 &q2, Vec3 &pos1, Vec3 &pos2, clCollisionReport & cr); It is rather long, so I won't paste it all in here. It doesn't use anything complicated like Johnson's whatever, only some heuristics. It is also used in the bouncy rigid body demo on the site, there you can see (I think the faces and edges which are used are marked in red) that it is quite robust. I'd like to point out that I am no longer using this code with my current resting contact project. I am currently using custom algorithmic collision detection for simple cases as seen in the MathEngine demos, and am working on implementing an OBB and space partition tree based approach I made up myself. This will not descend to the level of triangles! Aside from the obvious speed benefit, I believe getting perfect edge/vertex/face pairs for resting contact is far more important than for colliding-only contact, and I don't think I can guarantee this when I use arbitrary geometry and a simple heuristics based scheme. Also, as I have mentioned earlyer, I don't think we will be able to/want to use display geometry to do physics on anyway, with the rise of HW T&L in grx boards, and the associated explosion of polygon counts, as well as the introduction of progressive meshes and subdivision surfaces which keep the display geometry in constant flux anyway. I think bounding volumes can provide enough information about the shape of an object to create very realistic looking physically based animation. -- --Adam Moravanszky http://www.n.ethz.ch/student/adammo > > >> The rigid body simulation itself typically doesn't need to track closest >> points, unless they are really close, as above. Permanent closest point >> tracking between objects is usually used to speed up the collision >detector >> (temporal coherence). > >I don't follow you there. To me, permanent closest point tracking (as used >in I-Collide for example) is only used to waste CPU time :) Because most of >the time you just don't need them: you just need them when there's a >collision. Makes sense ? > >Pierre > > > > >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
From: Tom F. <to...@mu...> - 2000-08-17 21:06:29
|
I seem to remember TOCA had a ghost-car mode in it. Did they license it, or just put their foot down and say "go on - sue us then". Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > From: Dean Calver [mailto:de...@ra...] > > The most annoying thing about the Atari 'ghost car' patent, > is that Midway > (who now own it) ACTIVELY enforce it, > I know because 2 years the game we had just released > (Powerboat Racing) was > hit with it, we had a mode with > a recorded ghost boat to race again. Midway told us we had > infringed there > patent and could they have some > money, I never found our if we paid or if our publisher > (Interplay) fought > them. > > So now we never include ghost anything in any our race games. > > The actual defination involves transparency (ghost like > look), so if you do > include pre-recorded cars to race again > the visual image is very important. An lawyer thought that if > we had made > the 'ghost' solid it wouldn't have affected > us, but we were released by this time. > > Usual stuff, that I'm not a lawyer and my memory be going so name of > companies may be wrong etc > (I pretty sure Midway brought Atari though) > > Be afraid, be very afraid > Deano > > Dean Calver, > Senior Games Programmer, > Promethean Designs Ltd. |
From: Pierre T. <p.t...@wa...> - 2000-08-17 20:02:18
|
I dropped a on-purpose inquisitive and naive mail on comp.games.development.programming.algorithms where John Nagle can be reached. Here is his answer, for what it's worth. Pierre ============================================================ Hi there, I recently heard rumors about a new patent regarding collision detection/collision response. As far as I know, this is a patent from John Nagle, related to Animats's Softimage plug-in called "Falling Bodies". I'd really like to have more information about that one. You know how rumors can be. Crazy things are said. For example one reported it was covering most collision detection methods, which have been used in games for years. Which is, let me find the appropriate word.... oh yeah: grotesque. And shameful as well. I think I'm wrong in the way I understood that patent, am I not? I'd love to hear what's the exact issue here, what it is supposed to change for game developers, and so on. Regards, ============================================================ Sure. See http://www.animats.com/topics/patents.html Read claim 1 of the second patent listed for what's covered. The general idea is that older "penalty method" systems break down on the hard cases, but this one doesn't. Most other demos of physically-based animation have simple blocks or balls banging around. Even then, they usually don't get motion that makes things look like they have weight, one of the hardest things to do in animation. We have human figures falling downstairs, and they looks right. And it's not vaporware; we have demos, downloads, videos, and a shrink-wrapped product, and we've had them for years. We took a technology that sucked and made it work. That's a patentable improvement. I'd be glad to discuss this with industry people who have a problem with this. I'm also willing to consider licensing games or academic work that are 100% open source and covered under the GPL at no charge. John Nagle Animats www.animats.com Menlo Park, CA |
From: Dean C. <de...@ra...> - 2000-08-17 19:59:22
|
The most annoying thing about the Atari 'ghost car' patent, is that Midway (who now own it) ACTIVELY enforce it, I know because 2 years the game we had just released (Powerboat Racing) was hit with it, we had a mode with a recorded ghost boat to race again. Midway told us we had infringed there patent and could they have some money, I never found our if we paid or if our publisher (Interplay) fought them. So now we never include ghost anything in any our race games. The actual defination involves transparency (ghost like look), so if you do include pre-recorded cars to race again the visual image is very important. An lawyer thought that if we had made the 'ghost' solid it wouldn't have affected us, but we were released by this time. Usual stuff, that I'm not a lawyer and my memory be going so name of companies may be wrong etc (I pretty sure Midway brought Atari though) Be afraid, be very afraid Deano Dean Calver, Senior Games Programmer, Promethean Designs Ltd. ----- Original Message ----- From: "gl" <gl...@nt...> To: <gda...@li...> Sent: Wednesday, August 16, 2000 11:13 AM 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 |
From: Will P. <wi...@cs...> - 2000-08-17 19:53:51
|
> Hill-climbing is a dramatic optimization provided the number of > vertices gets "reasonable". Now, it's up to you :) I agree totally (i.e. O(1) is better than O(n)). There are just other things that are slower and worth speeding up at this time and making it O(1) (however easy it might be) will complicate the code. For example, I'm going to integrate my rigid bodies into a bsp-tree based world and I'll need to do full collision detection there. I expect those algorithms will be costly. > > Talking about cycling, it reminds me of something I forgot to mention > so far. What termination condition do you use? I'm using Gino's termination condition (the one that monotonically increases to a tighter lower bound). > Basically, you just need to keep recording the pair of vertices > encountered, and you just stop the algorithm the day you find a > reoccurrence. This is a lot more robust than everything else of > course, since it doesn't imply numerical accuracy anymore. But would > it be what you mean by "cycling" ? This is what I was thinking that I might have to add in case the simplex went through the same series of sets of points repeatedly. But I haven't seen it yet. > Any thoughts regarding that particular, delicate point? I think it's > important to improve GJK's robustness, I don't feel like playing with > epsilons for ages, as Gino did. I thought Gino's solution was to look for cycling? That doesn't seem too hard. > There is also the implementation issue behind that : you must record > pair of vertices. If P has p vertices and Q has q, then you basically > can have to face pq different pairs. Recording them is easy. But you > also must be able to tell whether a new pair has already been recorded > or not - and of course in a very quick way. This is not a very big > problem, but choices have to be made there. For the moment, and in the > sake of laziness, I just scan the array of recorded pairs in search of > current one, in a very stupid linear way. It could be improved using > some dichotomy methods, but I didn't do it. I also could use a stupid > array of pq bits, but it really would waste some ram for nothing. > Comments welcome here as well. Well, you could just remember which points are removed from the simplex in that time step.... that shouldn't be too hard, and is constant time. > What do you mean by "full contact manifold" ? Like if two cubes are on top of each other. The full contact manifold (or roughly parts that touch) wouldn't just be one closest point as returned by gjk, but a face or some other combination of features. For my purposes, it might not be worth calculating. > It actually made me think to a new question! When the algorithm stops, > it returns a pair of closest points expressed as : Cp = l0*P0 + l1*P1 > + ... Cq = l0*Q0 + l1*Q1 + ... > > (assuming li are Lambda(i), Cp belongs to P, Cq belongs to Q) Now, I > didn't notice it before, but Lamdbas are the same for Cp and Cq !? > Isn't it a strong limitation regarding the actual positions of Cp and > Cq on the convex hulls of P and Q ? I mean, when you start looking for > two arbitrary points on P and Q, you're supposed to be able to express > them with arbitrary Lambda values. There's a little something here I > don't get. Weird. Do you find it shocking or normal ?...maybe there's > an obvious reason I don't see. And maybe that's what you mean when you > say it doesn't find a "full contact manifold" ? It's weird, yes, but not that weird considering that the whole algorithm works on the two polyhedra A and B at the same time to find the point in A - B closest to the origin. > Pheew, when you think it's finished, well, it's not :) It never is. The harder part is coming up with good collision response/contact forces, and god forbid if I decide to go with nonlinear springs for fear of patent violations. :) Will ---- Will Portnoy http://www.cs.washington.edu/homes/will |
From: Pierre T. <p.t...@wa...> - 2000-08-17 19:51:47
|
Ok, while we are deeply in touch with the subject (GJK, RAPID, Q-COLLIDE, wacky patents...) let me introduce my new brain-blaster for the week-end: N-body processing. Some CD libraries such as RAPID only deal with two bodies. On top of that, you need some more code to handle collision between multiple pairs, something known as N-body processing. For example V-Collide is just made of some N-body code built on top of RAPID. I know the usual ways to deal with it: cut your world into sectors, use spatial partitionning techniques, octrees, quadtrees, whatever, and use some sweep&prune approach as a final death-blow. In other words, assume I know which pairs are possibly colliding. My concern is about the way I can manage (not detect) all of them. For example, for each pair I could have to do some processing the first time the pair gets active, and some processing when it stops colliding. For example in GJK it would involve computing the initial supporting vertices in an efficient way. Then, for each possible pair I may need some data structure to store some values. I then need a way to: - allocate and de-allocate ram for active pairs - track active pairs - access any possible pair in an efficient way The most obvious and stupid solution would be something like an array of N*N structures, with N = the number of objects in the simulation. Of course, this is absolutely out of question. My standard test sets N = 1024, to give you some ideas. I'm curious about the solutions you people could imagine. Something with an hash-table maybe, but then what would be a good hash-key? This also can be seen as the reference/owner problem one can have with shared materials/textures/etc, since an (owner, ref) couple is nothing more than a pair of colliding/touching/linked/related entities. I don't think I have any brilliant ideas for the moment, but I'm curious about yours.... Cheers, Pierre |
From: Pierre T. <p.t...@wa...> - 2000-08-17 19:28:22
|
> A potential problem with RAPID is that it works from a 'polygon soup', and > as such has no concept of solidity to distinguish between insideness and > outsideness. Sure, but the concept does not exist in RAPID for a good reason : it does not exist at all for polygon soups. It remains the only library so far to deal with such cases. Tell me if I'm wrong, but say I want to simulate 256 stupid teapots, what choices do I have ? > So, depending on how small or fast your objects are, RAPID might not be > able to detect all your collisions (i.e. object A fully inside object B) That's what swept volumes are for, I guess. Painful problem indeed. > unless it's enhanced to do so. I guess this is probably not a problem > in general, as you're probably running your physical simulation at a fairly > high frame rate, but it could be an issue in some cases. Of course, the > triangle-triangle test could of course be extended to handle velocity, > which would fix this problem. Yes, this is the big issue: 4D collision detection. A real PITA: - difficult to implement and visualize - difficult to design since it suddenly links a perfectly static stand-alone collision detection library to the heart of your dynamic simulation. Perfectly painful. > Also, I'm no expert on physical simulation, but one important aspect is > computing the contact manifold (the set of points of contact) and again > this is something RAPID would have to be enhanced with, to be able to > provide. Actually that's what we were discussing, I think. (...err I hope... because that was my question at first !) The way I see it, the closest pair of points becomes the points of contacts, as soon as the distance between the two bodies is less than your favorite threshold. All that junk starts to be very clear IMHO. The only nasty remaining part will probably be the linear programming one for resting contacts, but I'm really not in a hurry for that one. ...hmm and there are also those KDS thingies I still must read about... oh, well. Pierre |
From: Pierre T. <p.t...@wa...> - 2000-08-17 19:08:43
|
Yeah, here we go again ! > I have one working as well, but I'm not taking hill-climbing into account > (I could add it, but for simple shapes like cubes I wouldn't be surprised > if it were more expensive to generate the adjacencies and load-time and > check them in the support point computation routine). I haven't > encountered cycling yet, though it's easy enough to detect that issue. Hill-climbing is a dramatic optimization provided the number of vertices gets "reasonable". Now, it's up to you :) Talking about cycling, it reminds me of something I forgot to mention so far. What termination condition do you use? Gino's one is the same as Gilbert's one, and you can read in his paper how much pain he had to make it more robust. That's why I discarded it and I used an "improved" termination condition presented in the Q-COLLIDE thesis. Basically, you just need to keep recording the pair of vertices encountered, and you just stop the algorithm the day you find a reoccurrence. This is a lot more robust than everything else of course, since it doesn't imply numerical accuracy anymore. But would it be what you mean by "cycling" ? I don't know where this improved termination condition comes from, I trusted Kelvin Chung on that point - regarding the rest of the thesis I think I can. Best proof of that is just that it works indeed, and very well. Now, I'm a little upset about one of the last paragraphs in Cameron's papers about his enhanced GJK. I must read it again, but I think he claims this new termination condition doesn't handle all possible cases. Any thoughts regarding that particular, delicate point? I think it's important to improve GJK's robustness, I don't feel like playing with epsilons for ages, as Gino did. There is also the implementation issue behind that : you must record pair of vertices. If P has p vertices and Q has q, then you basically can have to face pq different pairs. Recording them is easy. But you also must be able to tell whether a new pair has already been recorded or not - and of course in a very quick way. This is not a very big problem, but choices have to be made there. For the moment, and in the sake of laziness, I just scan the array of recorded pairs in search of current one, in a very stupid linear way. It could be improved using some dichotomy methods, but I didn't do it. I also could use a stupid array of pq bits, but it really would waste some ram for nothing. Comments welcome here as well. > I substituted this GJK implementation in the place of the separating plane > stuff I had beforehand, and although it doesn't find a full contact > manifold, it looks pretty decent in the context of a rigid body > simulation. Looks like we're all doing the same. I already had the separating vector from Q-COLLIDE, and I actually started GJK to implement the "combined algorithm" presented in the end. What do you mean by "full contact manifold" ? It actually made me think to a new question! When the algorithm stops, it returns a pair of closest points expressed as : Cp = l0*P0 + l1*P1 + ... Cq = l0*Q0 + l1*Q1 + ... (assuming li are Lambda(i), Cp belongs to P, Cq belongs to Q) Now, I didn't notice it before, but Lamdbas are the same for Cp and Cq !? Isn't it a strong limitation regarding the actual positions of Cp and Cq on the convex hulls of P and Q ? I mean, when you start looking for two arbitrary points on P and Q, you're supposed to be able to express them with arbitrary Lambda values. There's a little something here I don't get. Weird. Do you find it shocking or normal ?...maybe there's an obvious reason I don't see. And maybe that's what you mean when you say it doesn't find a "full contact manifold" ? Pheew, when you think it's finished, well, it's not :) Pierre |
From: Tom F. <to...@mu...> - 2000-08-17 18:14:12
|
Yes, you can always strip any list. What I mean is that the sort of highly twisted traversal path (with frequent little side-branches) that is optimal across a wide range of vertex cache sizes and behaviours usually has a larger index size (because of the large number of degenerate tris needed to turn corners and start elsewhere and so on) when stripped than when just using a standard list. You can get lower bandwidth with strips if the strips are long and straight, but in that case you are tuning for a specific cache size and replacement type, which you usually don't know. However, since the size difference is not something big like a factor of two either way, there is probably very little difference in the overall bandwidth, since the vertex data is the no.1 biggest chunk of data, so it's probably all down to personal preference. Tom Forsyth - Muckyfoot bloke. Whizzing and pasting and pooting through the day. > -----Original Message----- > From: Charles Bloom [mailto:cb...@cb...] > Sent: 17 August 2000 18:24 > To: gda...@li... > Cc: cb...@su... > Subject: RE: [Algorithms] Strips > > > > At 10:36 AM 8/17/2000 +0100, you wrote: > >I have a bit of a knee-jerk response to strips, because of their > >worse-than-list vertex caching (up to twice as bad). > However, since normal > >VIPM pretty much destroys the vertex cache anyway, this > argument doesn't > >hold much water! > > I don't understand why you say strips have a worse cache > behaviour than > lists. At the very worst, I can always make a strip which is > identical to > a given list. > > The list (abc)(def)... > is the strip (abccddef...) > > Which has identical vertex cache behaviour. Given, that's > not such a hot > thing to do, but when you optimize for vertex cache, you will > in general > be generating lots of rectangular grids of triangles in your > triangle list, > and those can be stripped neatly. > > Hence, I can write a new stripper which simply optimizes the > tri-list for > vertex cache and then tries to strip the resulting triangle > list by building > the "brute force" strip I describe above, but collapse the uneccessary > duplicated vertex indices when possible. I conjecture that on typical > meshes, you'd end up with a (maybe small) saving in the > number of indices > by using strips, and get (nearly) identical vertex cache behaviour. > > -------------------------------------- > Charles Bloom www.cbloom.com |
From: Discoe, B. <ben...@in...> - 2000-08-17 18:06:06
|
The data is definitely a simple heightmap. What are you trying to do with it? The geographic extents are provided (optionally in UTM) so that you can match it to other geospatial data you have. If you just want to draw the data by itself, you can ignore the extents. -Ben http://vterrain.org/ > -----Original Message----- > From: Wayne Coles [mailto:W....@re...] > > Does anyone know where I can get some information on reading Universal > Transverse Mercator (UTM) data for 3D/2D display. I'm > starting off with the Binary Terrain (BT) format that I picked up > from www.vterrain.org. Unfortunately I can't find any info on what > the data actually is (it doesn't appear to be a simple heightmap). > Any info would be appreciated :) > > Wayney |
From: Will P. <wi...@cs...> - 2000-08-17 17:55:00
|
I have one working as well, but I'm not taking hill-climbing into account (I could add it, but for simple shapes like cubes I wouldn't be surprised if it were more expensive to generate the adjacencies and load-time and check them in the support point computation routine). I haven't encountered cycling yet, though it's easy enough to detect that issue. I substituted this GJK implementation in the place of the separating plane stuff I had beforehand, and although it doesn't find a full contact manifold, it looks pretty decent in the context of a rigid body simulation. Will ---- Will Portnoy http://www.cs.washington.edu/homes/will On Thu, 17 Aug 2000, Pierre Terdiman wrote: > Ok, I have my very first version running - and my head hurts. > > Pretty basic for the moment, but it seems to work. The computed distance > does not look very accurate nonetheless. For example I saw it reported as > 0.000261 altough the two objects obviously collided. Duno if it's normal. I > skipped the backup procedure (I actually *forgot* about it) but my basic > tests worked anyway. I think Gino was right when he discarded it. Running > time is correct, provided you use hill-climbing. If you don't.... *grin*, if > you don't, just forget it. (ok, unless your meshes have few triangles). I > used Rabbitz' subroutine for Johnson's algorithm, so that I could build the > Gilbert part on a working basis. Now I'm going to recode that one my way. > > I think some day I'll also pack all my notes in a ppt file for interested > people. > > Pierre > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
From: <Chr...@Pl...> - 2000-08-17 17:35:09
|
Pierre Terdiman wrote: >In rigid body simulations, one needs a correct estimation of the distance >and contact points between two bodies, in order to: >- backup the simulator in search of the exact collision time >- compute an accurate collision response > >If you followed the recent GJK thread, you know this algorithm works well >for such tasks. But what about other collision detection methods? For >example, say I'm just using OBBs, as with RAPID. RAPID will detect >collisions, but won't give me a distance or a pair of closest points. Does >it mean it can't be used efficiently within a rigid body simulator ? A potential problem with RAPID is that it works from a 'polygon soup', and as such has no concept of solidity to distinguish between insideness and outsideness. So, depending on how small or fast your objects are, RAPID might not be able to detect all your collisions (i.e. object A fully inside object B) unless it's enhanced to do so. I guess this is probably not a problem in general, as you're probably running your physical simulation at a fairly high frame rate, but it could be an issue in some cases. Of course, the triangle-triangle test could of course be extended to handle velocity, which would fix this problem. Also, I'm no expert on physical simulation, but one important aspect is computing the contact manifold (the set of points of contact) and again this is something RAPID would have to be enhanced with, to be able to provide. Christer Ericson SCEA, Santa Monica |
From: Charles B. <cb...@cb...> - 2000-08-17 17:24:06
|
At 10:36 AM 8/17/2000 +0100, you wrote: >I have a bit of a knee-jerk response to strips, because of their >worse-than-list vertex caching (up to twice as bad). However, since normal >VIPM pretty much destroys the vertex cache anyway, this argument doesn't >hold much water! I don't understand why you say strips have a worse cache behaviour than lists. At the very worst, I can always make a strip which is identical to a given list. The list (abc)(def)... is the strip (abccddef...) Which has identical vertex cache behaviour. Given, that's not such a hot thing to do, but when you optimize for vertex cache, you will in general be generating lots of rectangular grids of triangles in your triangle list, and those can be stripped neatly. Hence, I can write a new stripper which simply optimizes the tri-list for vertex cache and then tries to strip the resulting triangle list by building the "brute force" strip I describe above, but collapse the uneccessary duplicated vertex indices when possible. I conjecture that on typical meshes, you'd end up with a (maybe small) saving in the number of indices by using strips, and get (nearly) identical vertex cache behaviour. -------------------------------------- Charles Bloom www.cbloom.com |