FastLSM soft body physics (source code available)

Issues with the forum and all license/patent related discussion
Post Reply
dog
Posts: 44
Joined: Fri Jul 22, 2005 8:00 pm
Location: Santa Monica

Re: FastLSM soft body physics (source code available)

Post by dog » Wed Sep 26, 2007 12:50 am

Thank you for posting a link to your work. It is a great pity that you went the route of encumbering it with patents (some of which strike me as having dubious defensibility). Based on past experience this will probably stop your technique being used by anyone. Oh well.

Alec
Posts: 12
Joined: Tue Sep 25, 2007 4:30 am

Re: FastLSM soft body physics (source code available)

Post by Alec » Wed Sep 26, 2007 4:20 am

I read the discussion of patents on another thread with interest. I think it's true what people say, that patents are annoying once the paper is published, but I believe most people (certainly including researchers working for companies, such as Dr. Mueller) would not publish the paper in the first place if patents were not available to secure their idea. In that case, they would simply keep their developments secret, and try to sell the secret. The purpose of patents is to let people publish without losing anything, so that the scientific community can see it and keep building on it. A patent does not stop people from understanding the idea and pursuing research based on it. As to whether it will stop actual developers using this method, well, we'll see. In this particular case, the FastLSM algorithm uses shape matching techniques from Mueller's Meshless Deformations paper which were separately patented by AGEIA, so any company wanting to use FastLSM would have to get at least one license anyway, so I don't think my patent has greatly changed the playing field. At any rate, I don't want to hijack my own thread into a discussion of patents -- I'd be happier to discuss the details of the method or answer any questions anyone might have. Hope you guys like the system. Best,

Alec

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: FastLSM soft body physics (source code available)

Post by Dirk Gregorius » Wed Sep 26, 2007 8:51 am

I'd be happier to discuss the details of the method or answer any questions anyone might have. Hope you guys like the system.
With all respect for your work I doubt anybody will discuss your method here or anywhere else because of the patent most people simply can't do this since we all run into the possibily to be sued by you if we use a soft-body solver in a game. The recommended behavior with papers like yours is not to read them, because of the legal issues. I think you read this in the other threads. It is a pitty since your system sounds interesting from what I have read in the post above.

If you want an open discussion about your method you should consider publishing it under a liberal license. The experience shows that people do contribute back and also give you the deserved credits. Look at Bullet or the ODE. I think one of the main reasons for their success is their liberal license.

Note that this is not meant as an offensive post.


Cheers,
-Dirk

Alec
Posts: 12
Joined: Tue Sep 25, 2007 4:30 am

Re: FastLSM soft body physics (source code available)

Post by Alec » Wed Sep 26, 2007 10:19 am

No offense taken. However, I think that the situation may be being cast in an inaccurate light. First of all, I believe that the comparison between ODE / Bullet and FastLSM is not a completely direct one (though it may still be a useful one), because the first two are software libraries, whereas FastLSM is an algorithm. I would not dream of patenting or copyrighting some piece of open-source software I wanted people to use -- instead I would release it under a liberal license, as you suggest. However, an algorithm is a different story: it's an idea, not a product, and the only way to make any compensation from it is to have a patent.

Secondly, and more importantly, I believe that the discussion of patents as they relate to academic research is perhaps misdirected. It is my understanding (and, while I don't have the experience to know this myself, the professor I worked with, who does have vast amounts of experience in academic graphics research, gave me this understanding) that most computer research papers published in leading journals do have associated patents filed. For example, to refer again to Dr. Mueller, I believe every paper he publishes has a corresponding patent filed by AGEIA. The point being that this does not stop people from reading and discussing and implementing all these new methods -- Dr. Mueller's methods are very widely talked about and implemented, including in this forum.

How exactly the patents are enforced is totally out of my knowledge -- I would imagine that large companies with AAA products acquire the relevant patents as they are developing their engines. Also, as a side note, I do know for a fact that it generally takes several years for any graphics-related patent to be approved or denied. The patent I saw discussed on this forum, relating to the Position Based Dynamics paper, must be a patent application rather than a granted patent (as is mine). It may be that both my and Dr. Mueller's patents will be thrown out. (By the way, I noticed people voicing surprise at the broadness of the patent claims -- this is standard. A patent seeker will list the broadest claims he or she can possibly imagine, and wait until the review period to see which claims are accepted and which rejected, narrowing the claims as necessary.)

If my mentioning a patent related to this algorithm scares people off, that's a pity. I don't think it has been the case for many other papers read and discussed here which were quite likely patented in some form.

Eternl Knight
Posts: 58
Joined: Sun Jan 22, 2006 4:31 am

Re: FastLSM soft body physics (source code available)

Post by Eternl Knight » Wed Sep 26, 2007 11:15 am

There is a big difference to discussing papers and algorithms that "may" be patented to those that are clarified as explicitly being patented. And that is what will prevent anyone here being able to discuss your paper/algorithm with you.

You mention that not only have you covered your algorithm with a patent application, but that you have worded the claims as broadly as possible. Given the patent claims I've seen make it through the patent office, this means it is quite likely that even the broadest of your claims could be approved. That would mean anyone implementing soft-bodies in their engine that have also read your paper would be liable for triple damages should they be sued for infringement.

And all this without going into the moral implications of software patents and/or using the "everyone else does it" for trying to pass off broader claims in the patent than the actual innovation your paper brings to the practice. Note, I am not commenting on these two things, only that they may be another consideration completely outside the "commercial risk" associated with knowing you have patented your innovations.

I would be very surprised if you will find anyone on these boards willing to risk triple damages to discuss your paper let alone risk looking at the code. Sorry *shrug*

--EK

Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: FastLSM soft body physics (source code available)

Post by Erin Catto » Wed Sep 26, 2007 5:37 pm

I've never heard of a game studio licensing a patent except under duress. By patenting your algorithm, you've guaranteed that far fewer people will embrace it.

Was this research privately funded? I'd hate to think that tax payer money would go to funding such activities.

pinballwizard
Posts: 15
Joined: Tue Jun 19, 2007 5:52 am

Re: FastLSM soft body physics (source code available)

Post by pinballwizard » Thu Sep 27, 2007 2:54 am

Unfortunately most institutional research these days seems to be going the patent route, as in some cases the metric "number of patents awarded" is used as a measure of employee performance, with minimum yearly patent quotas being imposed on individual researchers and corresponding punitive measures if such quotas are not met. The new research model seems to be not just "publish or persish", but rather "publish and patent, or perish".

To an individual researcher (like the OP) working within an institution, the patent-policy mandates are likely coming from the highest levels of the institution itself, making it difficult for the individual researcher to avoid this policy. The individual researcher must then either choose to accept and embrace the patent system, or leave the research institution or research field entirely. Clearly, the first path is of less resistance, and has no immediately-noticeable direct impact on the individual researcher.

I'm reminded of the economic principle of the "tragedy of the commons": in the beginning nobody has any patents, and no power over any other player. Then if one person starts to claim patents, he has an economic advantage over others; other persons who have no patents feel the need to claim patents, too, to become competitive. In the end, everyone claims patents. Unfortunately this situation leads to destruction of the common good of freely shared knowledge that benefits everyone; now, all knowledge and ideas are locked up behind patents. Indeed, a classic case of "tragedy of the commons".

Is there a solution to the tragedy of the commons?

Eternl Knight
Posts: 58
Joined: Sun Jan 22, 2006 4:31 am

Re: FastLSM soft body physics (source code available)

Post by Eternl Knight » Thu Sep 27, 2007 4:16 am

I don;t know if this is required by Erwin or Alec, but I think we should keep the topic about either the paper/algorithm/code or why we cannot look at the paper/algorithm/code. While I would love to discuss the merits of software patents on primarily mathematical conveniences (or merit lack thereof) - I think that would permanently derail the topic of this particular thread. If Alec so wishes, I'll be the first to jump in, but if there is someone who wishes to discuss his paper &/or his code - I think it would be nice to simply let them do it in the thread without the added patent debate.

Which is why my initial post was lean on what I personally thought and heavier on explaining to Alec why many would not want to risk exposure to the paper due to the high commercial risk associated with broadly defined software patents. By sticking to the purely commercial considerations, I was (& am) hoping to keep this thread clean of the political/religious argument patenting "mathematical software" tends to bring up.

--EK

pinballwizard
Posts: 15
Joined: Tue Jun 19, 2007 5:52 am

Re: FastLSM soft body physics (source code available)

Post by pinballwizard » Thu Sep 27, 2007 4:56 am

Eternl Knight wrote:I think we should keep the topic about either the paper/algorithm/code or why we cannot look at the paper/algorithm/code.
You're right. Sorry for derailing this particular thread. I'll bow out of this discussion for now, for the reasons of commercial/legal-risk already mentioned.

To the OP: Good luck with your research and/or commercialization. I would guess that the likely market for such patented ideas is either the academic research community or big companies, not the open-source community or small indie developers.

Alec
Posts: 12
Joined: Tue Sep 25, 2007 4:30 am

Re: FastLSM soft body physics (source code available)

Post by Alec » Thu Sep 27, 2007 5:57 am

Wow, I really was out of my depth here. Thanks so much for all the info you guys are providing -- I really didn't have much of an understanding of any of this (that is, the realities of patents). It seems I really blundered by mentioning patents at all. I've taken the step of removing the mention of patents from the project page.

To answer the question, this research was privately funded. I did all my research for the project in my spare time over several years, while I was an undergraduate and then for half a year after I graduated. (I collaborated with Professor James in the later stages of the research, but none of his work was related to patented ideas.) The fact that I wasn't paid for any of it is the reason I wanted to pursue commercializing it / getting some form of concrete intellectual property. Maybe getting a patent was a terrible way of doing that -- I really don't know. Actually, I've been pretty much going blind on all this, which is why I really appreciate hearing from people with experience of these things. So even if it's been mostly bad news so far, I really appreciate this feedback!

So, a couple of things: the discussion of patents is a very interesting one, even beyond how it applies to my work, and I don't want to stop it. However, could we possibly discuss it on the thread "Position Based Dynamics: Patent", where there's already a bunch of comments about patents? I've made a new posting there with what I was thinking about in response to these and other comments. Secondly, is there any possibility of getting this work discussed? I still would love input / feedback... I don't suppose there's any method like, starting a new thread and deleting the references on the project page, so that a newcomer could avoid any reference to patents? The distinction between things that *are* patented and those that *may be* patented was one I hadn't appreciated before, and I'm trying to backtrack, but it may be too late...

Thanks again.

Alec

Eternl Knight
Posts: 58
Joined: Sun Jan 22, 2006 4:31 am

Re: FastLSM soft body physics (source code available)

Post by Eternl Knight » Thu Sep 27, 2007 6:25 am

Unfortunately Alec, once out of the bag - I think it quite problematic to get the proverbial cat it back in there. If Erwin were to remove the thread, it could be construed as "hiding evidence" that people knew about said patent. Given that some of the more knowledgeable contributors to these forums & Bullet have already read the thread (and hence know of the patent), the risk would be unacceptably high (at least as far as my experience is concerned).

On the other hand, "hiding" the fact that you have a patent on the subject matter IS a problem. A quick google on "submarine patents" and "patent trolls" will inform you as to why. We have to remember that you may not be the sole owner of the patent throughout it's lifetime (and this is generally how commercialization of patent IP has worked out where I have been involved). As such, the fact that YOU may not sue us is no guarantee that the eventual owner of said IP will not.

I wish I could help, as while I am not heavily into soft-body dynamics (well, not into it much at all really), I am involved in efficient runtime deformation using geometry embedded in lattices (which I assume from your blurb is something you speed up somehow). Given that I AM developing code stuff in this area commercially for my employer - I cannot take the risk of being "tainted" with information in your paper (innovative or not). Even checking the patent itself to see if it covers what I am doing would make me liable (should it cover something I am already doing in my code).

--EK

mewert
Posts: 57
Joined: Sat Oct 08, 2005 1:16 am
Location: Itinerant

Re: FastLSM soft body physics (source code available)

Post by mewert » Sat Sep 29, 2007 12:50 am

I tried out the demo, and the videos look pretty nice. I didn't read your paper, on advice of the others here. But there are existing ways to do soft-bodies at real-time rates; complete with tearing, that are unencumbered by patents. At least I think they are unpatented... Maybe I should patent the way I do it before somebody else does :) ( even though I think my technique is obvious ).

When I tried to ramp up the stiffness ( w ) things got very slow, unstable and the "facture" ( tearing ) looked worse, or failed to fracture at all. Actually I don't really know what 'w' is because I've been advised not to read your paper or the source code. But it seemed to make things "stiffer", or at least not deform locally. Which was another artifact: I saw lots of penetration of the object into the walls when it was stiffer. If the slowness is attributed to the O( w^3 ) solver. You should really implement the O( w ) thing at least. Even considering it was O( w^3 ) , it was too slow for the small amount of simulated material. If you want to sell this, you need to make it clearly better than anything else on the market, which it appears to be far from the case.

Alec
Posts: 12
Joined: Tue Sep 25, 2007 4:30 am

Re: FastLSM soft body physics (source code available)

Post by Alec » Tue Oct 02, 2007 6:55 am

mewert wrote:But there are existing ways to do soft-bodies at real-time rates; complete with tearing, that are unencumbered by patents.
This method is significantly faster.
mewert wrote: You should really implement the O( w ) thing at least. If you want to sell this, you need to make it clearly better than anything else on the market, which it appears to be far from the case.
I'd appreciate it if you read the Readme.txt before coming to this conclusion. As I state there, the 2D demo does not implement the O(1) solver, which is the crux of the paper (better even than O(w) -- it's O(1) per smoothing region), because the 2D demo is meant to have clean, readable code illustrating the basic lattice shape matching approach, and the optimization obfuscates that. As for the other artifacts mentioned, poor fracturing at high w is a known issue (which I believe could be fixed easily, but which I have not spent any time on, as fracturing was not a major feature for the paper), and wall penetration is an implementation-dependent issue and is not a result of the FastLSM algorithm.

FastLSM can handle 20,000 particles, enough for hundreds of soft bodies, deforming in real time. This, to the best of my knowledge, is significantly more than previous methods. This is illustrated in the video, and I think it is sufficient to demonstrate the method's contribution.

mewert
Posts: 57
Joined: Sat Oct 08, 2005 1:16 am
Location: Itinerant

Re: FastLSM soft body physics (source code available)

Post by mewert » Tue Oct 02, 2007 6:41 pm

I'd appreciate it if you read the Readme.txt before coming to this conclusion.
I did read it. My point was that, if you want to sell this, you should show your best stuff in the interactive demo. Videos aren't super impressive. Since a claim of "real-time" can be anywhere from 3fps to 60fps. You should fix the soft walls too. You've got to get your hands dirty and code a bit.

20,000 particles in real-time is not _that_ impressive. For real-time cloth, I've have seen simulators that will do that. I know volume preservation is a bit tricky, but the simulator is not the limiting factor in a soft-body simulation. For an in-game situation, collision detection is typically more expensive.

Alec
Posts: 12
Joined: Tue Sep 25, 2007 4:30 am

Re: FastLSM soft body physics (source code available)

Post by Alec » Wed Oct 03, 2007 4:06 am

My misunderstanding -- sorry! At any rate, the 2D demo is not the one that is intended to impress people; the 3D demo is a bit better (it has the O(1) implemented), but I still haven't put a ton of time into it (it's not widely tested and all you can do is spawn objects). As for the claim of real-time, the FPS timings are given in the paper (about 24 FPS at worst, on a 3.4 ghz machine).

As for whether 20,000 particles is a lot, the thing is that this is not a cloth simulator; it simulates 3D objects. That really changes the playing field as it's very expensive to get stiff 3D objects. There are a lot of tricks you can do with cloth that don't apply to arbitrary 3D lattices. So, I would argue that 20,000 particles is pretty good. Compare it, e.g., to Mueller's Interactive Virtual Materials demo, or the DefColStudio demo. As far as I know, it's several times more than what was possible before. Also, this is all on the CPU, not GPU (I know some cloth stuff is done on the GPU now).

As for collision detection, I don't know a ton about that, but in my demo the rudimentary collision detection I do (which is far from perfect, I know, but which is also very basic) takes about 30% of CPU time. I think CD costs will decrease relative to total cost if you start having very complex (many particle) non-self-colliding objects, as you might want e.g. for a highly detailed destructible vehicle mesh. Also, I think the main use of FastLSM for games would be for destructible near-rigid objects. In that case, I think you could have the particles deforming slightly, but just draw and do collision detection with the rigid mesh. I've done some thinking about that before now and I think it would work fine. Imagine, for example, a model of a wooden chair -- it's actually a soft body, because it flexes and bends in response to forces, which allows it to fracture properly (at the stress points), but it's so near to rigid that you could render it as the undeformed mesh and also do CD with that, applying the contact forces to the underlying particles. Then when it breaks you'd split the mesh and have two rigid-looking bodies interacting.

I agree that I've got to code more. I'm not great at graphics programming, so I've been trying to find a skilled programmer to collaborate with on a good demo, but I haven't found one yet, so when I have some free time I'll probably try my hand at it myself.

Post Reply