Thread: Re: [Algorithms] N-body processing
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Adam M. <amo...@dp...> - 2000-08-18 15:12:44
|
Don't call it stupid, I do that! But of course I have at most tens of bodies, not hundreds. What you may want is a storage format for a sparse matrix. Sparse matrices are an important construct used a lot by sci computation people, so there is no need for you to invent anything new. -- --Adam Moravanszky http://www.n.ethz.ch/student/adammo >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: Matthew M. <ma...@me...> - 2000-08-18 17:03:35
|
Hey! Check out the swept sphere stuff at UNC! It's the newest thing I've seen in a while for fast proximities and N-Body sim. Even more interesting is what they're using it for -- it appears ideally suited to huge poly counts. I posted the link last week. > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...]On Behalf Of Adam > Moravanszky > Sent: Friday, August 18, 2000 4:00 AM > To: gda...@li... > Subject: Re: [Algorithms] N-body processing > > > Don't call it stupid, I do that! But of course I have at most tens of > bodies, not hundreds. What you may want is a storage format for a sparse > matrix. Sparse matrices are an important construct used a lot by sci > computation people, so there is no need for you to invent anything new. > > -- > --Adam Moravanszky > http://www.n.ethz.ch/student/adammo > > >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 > > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Dave E. <eb...@ma...> - 2000-08-18 17:57:25
|
From: "Matthew MacLaurin" <ma...@me...> To: <gda...@li...> Sent: Friday, August 18, 2000 1:02 PM Subject: RE: [Algorithms] N-body processing > Hey! Check out the swept sphere stuff at UNC! It's the newest thing I've > seen in a while for fast proximities and N-Body sim. Even more interesting > is what they're using it for -- it appears ideally suited to huge poly > counts. I posted the link last week. I put swept sphere stuff into NetImmerse when UNC was starting to look into the topic as an alternative to using OBBs in a tree. I had asked Stefan Gottschalk at his dissertation defense if he had considered such bounding volumes, but he indicated 'no'. They work out quite well because they rely on squared-distance calculations that turn out to be less expensive (on average) to calculate than the separating axes, especially so in situations of close proximity. Code for building trees of spheres (points a specified distance from a point), capsules (points a specified distance from a line segment), and lozenges (points a specified distance from a rectangle) is at my site, the MgcContainment.html page. I eventually plan on putting the code at my site for the collision detection, but it may take a couple of months. -- Dave Eberly eb...@ma... http://www.magic-software.com |
|
From: Pierre T. <p.t...@wa...> - 2000-08-18 20:23:46
|
Adam, I admit there's no point looking for other solutions in most cases :) But as a matter of facts, I'm not doing this for a particular commerial project, I have no milestone to face, so while I'm at it....... The sparse matrix may be worth looking at. I'll give it a try. Matthew, Err... I don't think swept volumes (as used in PQP) will help, except for 4D collision detection which is not what was worrying me :) But maybe I miss you point. Dave, Welcome. Stefan actually tried that approach, but later. Well, whatever. Could you explain what would be the benefit of lozenges ? Especially a lozenge-tree ?! /* Pierre Terdiman * Home: p.t...@wa... Software engineer * Zappy's Lair: www.codercorner.com */ ----- Original Message ----- From: Dave Eberly <eb...@ma...> To: <gda...@li...> Sent: Friday, August 18, 2000 7:56 PM Subject: Re: [Algorithms] N-body processing > From: "Matthew MacLaurin" <ma...@me...> > To: <gda...@li...> > Sent: Friday, August 18, 2000 1:02 PM > Subject: RE: [Algorithms] N-body processing > > > Hey! Check out the swept sphere stuff at UNC! It's the newest thing I've > > seen in a while for fast proximities and N-Body sim. Even more interesting > > is what they're using it for -- it appears ideally suited to huge poly > > counts. I posted the link last week. > > I put swept sphere stuff into NetImmerse when UNC was > starting to look into the topic as an alternative to using > OBBs in a tree. I had asked Stefan Gottschalk at his > dissertation defense if he had considered such bounding > volumes, but he indicated 'no'. They work out quite well > because they rely on squared-distance calculations that > turn out to be less expensive (on average) to calculate > than the separating axes, especially so in situations of > close proximity. > > Code for building trees of spheres (points a specified > distance from a point), capsules (points a specified > distance from a line segment), and lozenges (points a > specified distance from a rectangle) is at my site, the > MgcContainment.html page. I eventually plan on > putting the code at my site for the collision detection, > but it may take a couple of months. > > -- > Dave Eberly > eb...@ma... > http://www.magic-software.com > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Matthew M. <ma...@me...> - 2000-08-18 21:21:11
|
> Matthew, > Err... I don't think swept volumes (as used in PQP) will help, > except for 4D > collision detection which is not what was worrying me :) But maybe I miss > you point. > > Dave, > Welcome. Stefan actually tried that approach, but later. Well, whatever. > Could you explain what would be the benefit of lozenges ? Especially a > lozenge-tree ?! Dave and I are talking about the same thing here. Swept sphere volumes give you tighter fits, faster interference rejection, and MUCH faster proximity queries than OBBs. Particularly important if you're trying to stave off the poly^2 tests. I assumed from your topic you were talking about N-Body dynamic simulation, for which fast proximity queries will be extremely helpful. (re-)Read the paper "Fast Proximity Queries with Swept Sphere Volumes" at: You'll be glad you did, unless I'm missing your point. ;^) > > /* > Pierre Terdiman * Home: p.t...@wa... > Software engineer * Zappy's Lair: www.codercorner.com > */ > > ----- Original Message ----- > From: Dave Eberly <eb...@ma...> > To: <gda...@li...> > Sent: Friday, August 18, 2000 7:56 PM > Subject: Re: [Algorithms] N-body processing > > > > From: "Matthew MacLaurin" <ma...@me...> > > To: <gda...@li...> > > Sent: Friday, August 18, 2000 1:02 PM > > Subject: RE: [Algorithms] N-body processing > > > > > Hey! Check out the swept sphere stuff at UNC! It's the newest > thing I've > > > seen in a while for fast proximities and N-Body sim. Even more > interesting > > > is what they're using it for -- it appears ideally suited to huge poly > > > counts. I posted the link last week. > > > > I put swept sphere stuff into NetImmerse when UNC was > > starting to look into the topic as an alternative to using > > OBBs in a tree. I had asked Stefan Gottschalk at his > > dissertation defense if he had considered such bounding > > volumes, but he indicated 'no'. They work out quite well > > because they rely on squared-distance calculations that > > turn out to be less expensive (on average) to calculate > > than the separating axes, especially so in situations of > > close proximity. > > > > Code for building trees of spheres (points a specified > > distance from a point), capsules (points a specified > > distance from a line segment), and lozenges (points a > > specified distance from a rectangle) is at my site, the > > MgcContainment.html page. I eventually plan on > > putting the code at my site for the collision detection, > > but it may take a couple of months. > > > > -- > > Dave Eberly > > eb...@ma... > > http://www.magic-software.com > > > > > > > > _______________________________________________ > > 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: Matthew M. <ma...@me...> - 2000-08-18 21:31:40
|
Oops. The paper is at http://www.cs.unc.edu/~geom/SSV/ > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...]On Behalf Of > Matthew MacLaurin > Sent: Friday, August 18, 2000 2:20 PM > To: gda...@li... > Subject: RE: [Algorithms] N-body processing > > > > > > Matthew, > > Err... I don't think swept volumes (as used in PQP) will help, > > except for 4D > > collision detection which is not what was worrying me :) But > maybe I miss > > you point. > > > > Dave, > > Welcome. Stefan actually tried that approach, but later. Well, whatever. > > Could you explain what would be the benefit of lozenges ? Especially a > > lozenge-tree ?! > > Dave and I are talking about the same thing here. Swept sphere > volumes give > you tighter fits, faster interference rejection, and MUCH faster proximity > queries than OBBs. Particularly important if you're trying to > stave off the > poly^2 tests. I assumed from your topic you were talking about N-Body > dynamic simulation, for which fast proximity queries will be extremely > helpful. > > (re-)Read the paper "Fast Proximity Queries with Swept Sphere Volumes" at: > > You'll be glad you did, unless I'm missing your point. ;^) > > > > > > /* > > Pierre Terdiman * Home: p.t...@wa... > > Software engineer * Zappy's Lair: www.codercorner.com > > */ > > > > ----- Original Message ----- > > From: Dave Eberly <eb...@ma...> > > To: <gda...@li...> > > Sent: Friday, August 18, 2000 7:56 PM > > Subject: Re: [Algorithms] N-body processing > > > > > > > From: "Matthew MacLaurin" <ma...@me...> > > > To: <gda...@li...> > > > Sent: Friday, August 18, 2000 1:02 PM > > > Subject: RE: [Algorithms] N-body processing > > > > > > > Hey! Check out the swept sphere stuff at UNC! It's the newest > > thing I've > > > > seen in a while for fast proximities and N-Body sim. Even more > > interesting > > > > is what they're using it for -- it appears ideally suited > to huge poly > > > > counts. I posted the link last week. > > > > > > I put swept sphere stuff into NetImmerse when UNC was > > > starting to look into the topic as an alternative to using > > > OBBs in a tree. I had asked Stefan Gottschalk at his > > > dissertation defense if he had considered such bounding > > > volumes, but he indicated 'no'. They work out quite well > > > because they rely on squared-distance calculations that > > > turn out to be less expensive (on average) to calculate > > > than the separating axes, especially so in situations of > > > close proximity. > > > > > > Code for building trees of spheres (points a specified > > > distance from a point), capsules (points a specified > > > distance from a line segment), and lozenges (points a > > > specified distance from a rectangle) is at my site, the > > > MgcContainment.html page. I eventually plan on > > > putting the code at my site for the collision detection, > > > but it may take a couple of months. > > > > > > -- > > > Dave Eberly > > > eb...@ma... > > > http://www.magic-software.com > > > > > > > > > > > > _______________________________________________ > > > 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: Pierre T. <p.t...@wa...> - 2000-08-18 22:24:28
|
> Dave and I are talking about the same thing here. Swept sphere volumes give > you tighter fits, faster interference rejection, and MUCH faster proximity > queries than OBBs. Particularly important if you're trying to stave off the > poly^2 tests. I assumed from your topic you were talking about N-Body > dynamic simulation, for which fast proximity queries will be extremely > helpful. > > (re-)Read the paper "Fast Proximity Queries with Swept Sphere Volumes" at: > > You'll be glad you did, unless I'm missing your point. ;^) I'm talking about N-Body dynamic simulation, but I'm not concerned with reducing the poly^2 tests or even the BV^2 tests. Read the original post again: I already have this part. For example, if I send my list of 1024 bounding boxes to the system, I get the correct list of possibly colliding objects in output, and it already gets detected in a fraction of a frame. So far, so good. Now, my concern is this: how do I track the possible colliding pairs? How do I store them? How do I handle them? For the moment Adam seems to be the only one who actually understood the problem: that's why he introduced the sparse matrices. Let's have an example. Assume the system (it could be your SSV system, giving a fast answer to my proximity query) tells me pair (P,Q) is about to collide - that is, the bounding volumes collide. I need a way to: 1) know if they're overlapping for the first time (i.e. did they already overlap the frame before?) 2) retrieve some cached values for this pair (separating vectors, supporting vertices, contact features, whatever) Alternatively, I need to know pairs which do *not* collide anymore!...so that I can discard the previously cached values. What I have there looks more like a storage problem, a database problem, a design problem.... it's actually not really a CD-related problem. :) The possible solutions would be: 1) Allocate an array of N*N entries, each entry containing a pointer to a temporary cache, or null if the pair is not active. Very fast access, perfect. But for N=1024, forget it. 2) Put all those pointers in a linear list, using the minimal ram. P active pairs, P entries in a linear array, I like that. But access becomes the slow part. I can read the whole thing in search of the current pair, but it's obviously bad - the number of active pairs can get pretty high. I can use some better schemes: insertion sort, bisection, or even a hash-table to access the array. But all in all it looks painful, and I was curious about the existing standard ways to deal with it. ...now, the SSV article is very interesting nonetheless :) ... Pierre |
|
From: David B. <db...@bt...> - 2000-08-19 00:12:32
|
> Now, my concern is this: how do I track the possible colliding pairs? How do > I store them? How do I handle them? For the moment Adam seems to be the only > one who actually understood the problem: that's why he introduced the sparse > matrices. I just use a hash table, and a simple modulus hash key(with the polyhedra indexes), no performance problems with this and very easy to implement(especially when you use STL:-). Objects are stored in an unsorted linked list off each hash entry. I don't use the pair table for anything other than caching closest feature pairs to improve performance. When you actually detect that there has been a collision, i.e. the closest distance algo returns something smaller than your epsilon. You need to look at the features(verts, edges or faces) surrounding the closest points and determine if they are as close to each other as the closest points. This is determining the contact manifold, which can be two points, point and edge, edge and edge, point and face or face and face. The contact manifold is then used to determine the collision response. David http://www.dblack.btinternet.co.uk ICQ #: 24402391 Mobile: (UK) 0778 7836188 |
|
From: Pierre T. <p.t...@wa...> - 2000-08-19 14:29:44
|
> I just use a hash table, and a simple modulus hash key(with the polyhedra > indexes), no performance problems with this and very easy to > implement(especially when you use STL:-). Objects are stored in an unsorted > linked list off each hash entry. > I don't use the pair table for anything other than caching closest feature > pairs to improve performance. Thanks David - as always you provide useful answers. |
|
From: Pierre T. <p.t...@wa...> - 2000-08-19 15:07:03
|
> determining the contact manifold, which can be two points, point and edge, > edge and edge, point and face or face and face. The contact manifold is then > used to determine the collision response. I didn't notice it, but you mentioned the face/face contact manifold, which I do not detect. I only handle the four others, two of whom as degenerate cases. To make things clear I followed the Baraff's way, including how he deals with colliding & resting contacts. How do you detect the face/face case? It is useful? I guess it might be useful to handle the simple case of the cube falling vertically on the table... Pierre |
|
From: David B. <db...@bt...> - 2000-08-19 15:21:20
|
> I didn't notice it, but you mentioned the face/face contact manifold, which > I do not detect. I only handle the four others, two of whom as degenerate > cases. To make things clear I followed the Baraff's way, including how he > deals with colliding & resting contacts. > > How do you detect the face/face case? It is useful? I guess it might be > useful to handle the simple case of the cube falling vertically on the > table... Face/face contact detection isnt strictly necasery, things should work as long as you detect all the other types of contact. The reason I detect face/face contacts is that it can improve stability and provide more sensible contact normals. For example if you detect four point/point contacts for two cubes resting exactly on top of each other, typicaly you would pick the average vertex normals at the points(since a point/point contact is degenerate). A more sensible choice is the normal of the contact face(top or bottom face of cube). The algorithm which I use to detect contact regions is basically a modified polygon clipper which tracks features along the way... It outputs face/face contacts just as easily as the other types. David http://www.dblack.btinternet.co.uk ICQ #: 24402391 Mobile: (UK) 0778 7836188 |
|
From: Dave E. <eb...@ma...> - 2000-08-22 02:55:52
|
From: "Pierre Terdiman" <p.t...@wa...> > Dave, > Welcome. Stefan actually tried that approach, but later. Well, whatever. > Could you explain what would be the benefit of lozenges ? Especially a > lozenge-tree ?! A lozenge looks like an OBB that is 'rounded' at the edges and corners. You effectively have the same degrees of freedom to provide a good fit of an object by an OBB or lozenge. So now the problem is to decide whether an OBB-OBB or lozenge-lozenge test is cheaper. For static OBBs, you have up to 15 separating axes to test. You can compute an average time for the test based on empirical probabilities about which axes tend to yield the separation (for randomly generated OBBs, the face axes covered about 95% of the cases when boxes did not intersect). For static lozenges, you need to determine the time it takes to compute the distance between two rectangles in 3D. I believe this distance test wins. -- Dave Eberly eb...@ma... http://www.magic-software.com |
|
From: Pierre T. <p.t...@wa...> - 2000-08-22 14:32:30
|
> A lozenge looks like an OBB that is 'rounded' at the > edges and corners. You effectively have the same Wouldn't it be a Rectangle Swept Sphere, a.k.a. RSS ? A lozenge looks like a 2D thing to me (I mean, "un losange" in French couldn't possibly be a bounding volume. Hence my confusion.) But now I understand, since RSS are good candidates indeed. Pierre |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X