Thread: [Algorithms] Algorithm to return point to surface of concave volume
Brought to you by:
vexxed72
From: Andreas B. <and...@gm...> - 2010-02-03 10:54:53
|
Hi, I have a point inside a concave volume, does anyone know of an algorithm to find the shortest vector from the point to the surface of the volume? The volume in this case is defined as the union of a number of overlapping capsules (lines with radius). Thanks Andreas Brinck |
From: pontus b. <her...@ho...> - 2010-02-04 15:36:26
|
Andreas, Since the capsules are mathematically defined by a length and a radius there are no surfaces so I suggest using standard collision detection instead. There are standard intersection tests that return a collision normal along with a intersection distance. I'm guessing you can find it in most open source physics libraries or just google it. If you need increased performance you can always attempt to use proxy objects or perhaps switch primitive from capsule to something easier. Hope that helps, Pontus Date: Wed, 3 Feb 2010 11:54:45 +0100 From: and...@gm... To: gda...@li... Subject: [Algorithms] Algorithm to return point to surface of concave volume Hi, I have a point inside a concave volume, does anyone know of an algorithm to find the shortest vector from the point to the surface of the volume? The volume in this case is defined as the union of a number of overlapping capsules (lines with radius). Thanks Andreas Brinck _________________________________________________________________ Hitta kärleken! http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952 |
From: metanet s. <met...@ya...> - 2010-02-06 15:20:28
|
> Since the capsules are mathematically defined by a length > and a radius there are no surfaces so I suggest using > standard collision detection instead. There are standard > intersection tests that return a collision normal along with > a intersection distance. I'm guessing you can find it in > most open source physics libraries or just google it. This is tricky, because the actual collision surface (i.e the outer surface of the union of capsules) is implicit; you can't simply apply a capsule-based method and expect a correct result. For example: L1 S1 | | | | |_ac___S2 | *b |__|___L2 L1 and L2 are capsule linesegments; the capsule surfaces (S1,S2) intersect at c. If you query at the asterisk, you should get c as closest point on the surface. There's no way to arrive at this through simple point-vs-capsule queries -- point-vs-L1 will give you b, point-vs-L2 will give you a. You _can_ try to iteratively push the point out of each capsule and hope that it eventually reaches the surface; in the above case this would work, but in general it doesn't. AFAIK there is no correct way to take the many local solutions you would get from individual point-vs-capsule queries and "munge" them together to arrive at a correct global solution. If there *is* such a method, I'd love to know about it though since it would be extremely useful. Currently we just use "iteratively project out of local collisions, and pray" :) raigan --- On Thu, 2/4/10, pontus birgersson <her...@ho...> wrote: > From: pontus birgersson <her...@ho...> > Subject: Re: [Algorithms] Algorithm to return point to surface of concave volume > To: "GDAlgorithms" <gda...@li...> > Received: Thursday, February 4, 2010, 10:36 AM > > > > > > Andreas, > > Since the capsules are mathematically defined by a length > and a radius there are no surfaces so I suggest using > standard collision detection instead. There are standard > intersection tests that return a collision normal along with > a intersection distance. I'm guessing you can find it in > most open source physics libraries or just google it. > > If you need increased performance you can always attempt to > use proxy objects or perhaps switch primitive from capsule > to something easier. > > Hope that helps, > Pontus > > > Date: Wed, 3 Feb 2010 11:54:45 +0100 > From: and...@gm... > To: gda...@li... > Subject: [Algorithms] Algorithm to return point to surface > of concave volume > > Hi, > > I have a point inside a concave volume, does anyone know of > an algorithm to find the shortest vector from the point to > the surface of the volume? The volume in this case is > defined as the union of a number of overlapping capsules > (lines with radius). > > > Thanks > > Andreas Brinck > > Skaffa en Windows phone så kan du > chatta på Messenger var du än är! Skaffa en > Windows phone så kan du chatta på Messenger var du än > är! > > -----Inline Attachment Follows----- > > ------------------------------------------------------------------------------ > The Planet: dedicated and managed hosting, cloud storage, > colocation > Stay online with enterprise data centers and the best > network in the business > Choose flexible plans and management services without > long-term contracts > Personal 24x7 support from experience hosting pros just a > phone call away. > http://p.sf.net/sfu/theplanet-com > -----Inline Attachment Follows----- > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list __________________________________________________________________ Ask a question on any topic and get answers from real people. Go to Yahoo! Answers and share what you know at http://ca.answers.yahoo.com |
From: Nguyen B. <ng...@gm...> - 2010-02-06 15:34:41
|
> AFAIK there is no correct way to take the many local solutions you would get from individual point-vs-capsule queries and "munge" them together to arrive at a correct global solution. > > If there *is* such a method, I'd love to know about it though since it would be extremely useful. Currently we just use "iteratively project out of local collisions, and pray" :) > > raigan > Actually there is such method. Our method doesn't try to merge multiple local contacts into one contact but handle all of them directly. The price for it is you will end up with more contacts to handle. The intuitive is that instead of using collision detection to merge the set of local contacts, you can let the LCP solvers to do that instead. Advantage : the solution is more physically correct, disadvantage : bigger system to solve. -------------------------------------------------- Binh Nguyen Computer Science Department Rensselaer Polytechnic Institute Troy, NY, 12180 -------------------------------------------------- |
From: <chr...@pl...> - 2010-02-06 22:33:35
|
Nguyen Binh wrote: > Actually there is such method. Our method doesn't try to merge > multiple local contacts into one contact but handle all of them > directly. [...] If would probably be more helpful to the OP if you offered a solution beyond an academic nod to "our method". Andreas, if it helps, you can look at the problem in the following way. Given your query point P, the closest surface point Q will lie on the surface of one capsule, or on the intersection contour of two, three, four, ..., up to N capsules. You can find Q as the minimum solution over all these cases. Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica |
From: Nguyen B. <ng...@gm...> - 2010-02-06 23:06:13
|
>> Actually there is such method. Our method doesn't try to merge >> multiple local contacts into one contact but handle all of them >> directly. [...] > > If would probably be more helpful to the OP if you offered a > solution beyond an academic nod to "our method". > The idea is there : let LCP system decides which contact is actually active. I dont know how what to offer more. "Our method" was there in various publications and was implemented in dvc2D which you can get all information from here: Here is our website : http://twiki.cs.rpi.edu/twiki/bin/view/RoboticsWeb/WebHome |
From: Andreas B. <and...@gm...> - 2010-02-09 07:49:15
|
Thanks for all the feedback people, I was hoping that there would be some kind of simple iterative algorithm (something like GJK) but it seems like I'm out of luck. I knew that the problem could probably be formulated as a LCP but unfortunately I don't think this will be feasible given the number of queries each frame. Christer, I will look into the analytical solution but I think it will be hard and error prone to extract the intersection curves/points of the capsules. I'm also toying with the idea of using some kind of Monte Carlo method to find the minimum but perhaps it's faster to just solve the LCP. Thanks again Andreas Brinck |
From: David N. <da...@re...> - 2010-02-09 18:58:31
|
I've always been a big fan of representing surfaces as a distance field to the surface (e.g. a point cloud over a domain where every point is 1 scalar). Benefits, * Distance fields filter very well so you can have a smaller resolution and bilinear filter. For example, check out Valve's vector graphics paper for pictures to convince yourself if it doesn't make sense. * Compresses very well, you can look into wavelets for a compact representation. I've seen signals compress up to 98% of its data using wavelets. * Spatially hashed into for O(1) look-up on queries. * The normal is stored implicitly via calculating the gradient. Disadvantages, * It's a compression and you may not get exact surface representations and with bilinear filtering you will smooth out crevices. Then again triangle representation isn't an exact representation either. * It typically takes more memory then a triangle representation and much more than an analytical formulation. Though, if you code up a fast wavelet compression/decompression routine you can get huge memory savings over a triangle representation of a surface but not the analytical solution. * Generating the distance field is kind of a pain for arbitrary convex objects. The only other gotcha is integrating all your primitive types to collide against it. The basic idea is you take sample points on the surface of your object you are querying with and hash them against the distance field. It's a closet point problem for convex objects and for arbitrary concave objects you can generate sample points over the surface. Then you can take the minimum set of sample points that may collide (e.g. via some broad phase query) and hash them in. -= Dave From: Andreas Brinck [mailto:and...@gm...] Sent: Monday, February 08, 2010 11:49 PM To: Game Development Algorithms Subject: Re: [Algorithms] Algorithm to return point to surface of concavevolume Thanks for all the feedback people, I was hoping that there would be some kind of simple iterative algorithm (something like GJK) but it seems like I'm out of luck. I knew that the problem could probably be formulated as a LCP but unfortunately I don't think this will be feasible given the number of queries each frame. Christer, I will look into the analytical solution but I think it will be hard and error prone to extract the intersection curves/points of the capsules. I'm also toying with the idea of using some kind of Monte Carlo method to find the minimum but perhaps it's faster to just solve the LCP. Thanks again Andreas Brinck |
From: <chr...@pl...> - 2010-02-09 19:04:38
|
Andreas Brinck wrote: > Christer, I will look into the analytical solution but I think it > will be hard and error prone to extract the intersection curves/ > points of the capsules. You wouldn't actually extract them, but solve for a minimum point (distance to your original point) that simultaneously lies on the boundary of K capsules. Not easy or fast. If possible I would opt for an approximate solution of some kind. Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica |
From: Yaser Z. <y...@ya...> - 2010-02-06 16:14:02
Attachments:
signature.asc
|
On 2/3/2010 14:24, Andreas Brinck wrote: > Hi, > > I have a point inside a concave volume, does anyone know of an algorithm > to find the shortest vector from the point to the surface of the volume? > The volume in this case is defined as the union of a number of > overlapping capsules (lines with radius). > I'm not an expert here, but couldn't you just find the shortest distance to each of the capsules in isolation and then wouldn't your answer be the minimum of these distances? Also, I'm sure there are ways to speed this up if you have to repeat this query many times under changing circumstances (e.g. organizing the capsules as the leaves of a complete tree structure and letting the parent of each group of leaves contain the shortest distance of the children to the point. Also, nodes can have "dirty" flags which you set whenever the capsules below them in the tree change. This way, you can recompute the shortest distance in the dirty branches of the tree.) However, I'm sure there is a simpler and faster solution out there. -Yaser Zhian -- May the Source be with you. |
From: Nguyen B. <ng...@gm...> - 2010-02-06 20:59:07
|
> I'm not an expert here, but couldn't you just find the shortest distance > to each of the capsules in isolation and then wouldn't your answer be > the minimum of these distances? > That wont work if the point moving toward other capsule. The you may have penetration if you only consider one with shortest distance. Actually, the ultimate aim for collision detection is to minimize penetration. Finding shortest distance is only a (good) heuristic. -------------------------------------------------- Binh Nguyen Computer Science Department Rensselaer Polytechnic Institute Troy, NY, 12180 -------------------------------------------------- |