gdalgorithms-list Mailing List for Game Dev Algorithms (Page 16)
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
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: Stuart G. <gda...@gx...> - 2010-03-10 20:08:00
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <meta content="text/html; charset=UTF-8" http-equiv="Content-Type"> </head> <body bgcolor="#ffffff" text="#000000"> Rather rusty too (7 years ago now :)) and a computer scientist rather than a mathematician these days, but I think what you're saying is that you want to solve an equation which looks like this:<br> <br> dv/dt = W/m + ((a+bt)/m).v + ((c+dt)/m).v^2<br> <br> In that, W is the weight force, v is the velocity of the object, m is its mass, t is time, and a through d are arbitrary constants. (The equation originally comes from writing m[dv/dt] = W + (a + bt)v + (c + dt)v^2.)<br> <br> In that case (and bearing in mind that I only did up to further maths at A-level, so take this with a pinch of salt), it appears to be what is called a Riccati equation:<br> <br> <a class="moz-txt-link-freetext" href="http://planetmath.org/encyclopedia/RiccatiDifferentialEquation.html">http://planetmath.org/encyclopedia/RiccatiDifferentialEquation.html</a><br> <br> Not sure if that helps for Google purposes? There's a bit on Wikipedia as well, for what it's worth. PlanetMath itself has an index of differential equations, which can be found here:<br> <br> <a class="moz-txt-link-freetext" href="http://planetmath.org/?op=getobj&from=objects&id=7023">http://planetmath.org/?op=getobj&from=objects&id=7023</a><br> <br> Hope that helps a little - wish I could be of more use!<br> <br> Stu<br> <br> On 10/03/2010 16:49, Jon Watte wrote: <blockquote cite="mid:c7b...@ma..." type="cite">I'm looking for a closed form solution for a differential equation. I did pass this stuff 20 years ago, but was more interested in graph theory, discrete math and DSP, so it's all vanished from my brain :-) <div><br> </div> <div>The equation is given a point mass that leaves a start position with a start velocity. On this point mass is acting a fixed gravitational force (in a fixed direction), as well as a linear and quadratic motion-opposed force (air drag) based on a linear and quadratic coefficient of air drag. So far, it's pretty much your standard "cannonball" equation (although I'd really appreciate a convenient reference for this solution, too). However, in this case, I also want to make the drag coefficients a linear function of time -- drag(linear, quadratic) = const(linear, quadratic) + factor(linear, quadratic) * time.</div> <div><br> </div> <div>If someone could plug this into Mathematica (or look it up in a handy formula reference), I'd really appreciate it. If someone could take the time to point at the proper online reference, that'd be wonderful, too!</div> <div><br> </div> <div>Sincerely,</div> <div><br> </div> <div>jw</div> <div><br clear="all"> <br> --<br> Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. <br> <br> </div> <pre wrap=""> <fieldset class="mimeAttachmentHeader"></fieldset> ------------------------------------------------------------------------------ Download Intel&#174; Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. <a class="moz-txt-link-freetext" href="http://p.sf.net/sfu/intel-sw-dev">http://p.sf.net/sfu/intel-sw-dev</a></pre> <pre wrap=""> <fieldset class="mimeAttachmentHeader"></fieldset> _______________________________________________ GDAlgorithms-list mailing list <a class="moz-txt-link-abbreviated" href="mailto:GDA...@li...">GDA...@li...</a> <a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a> Archives: <a class="moz-txt-link-freetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a></pre> </blockquote> </body> </html> |
|
From: Raymond B. <ray...@gm...> - 2010-03-10 18:51:44
|
These links might be helpful... http://math.fullerton.edu/mathews/n2003/ProjectileMotionMod.html http://www.grc.nasa.gov/WWW/K-12/airplane/flteqs.html On Wed, Mar 10, 2010 at 1:05 PM, Jon Valdés <ju...@gm...> wrote: > My math is just as rusty as yours, so I can't help much here, but > maybe this can help you find your solution: > http://www.wolframalpha.com/examples/Integrals.html > > Good luck ;-) > > On Wed, Mar 10, 2010 at 5:49 PM, Jon Watte <jw...@gm...> wrote: > > I'm looking for a closed form solution for a differential equation. I did > > pass this stuff 20 years ago, but was more interested in graph theory, > > discrete math and DSP, so it's all vanished from my brain :-) > > The equation is given a point mass that leaves a start position with a > start > > velocity. On this point mass is acting a fixed gravitational force (in a > > fixed direction), as well as a linear and quadratic motion-opposed force > > (air drag) based on a linear and quadratic coefficient of air drag. So > far, > > it's pretty much your standard "cannonball" equation (although I'd really > > appreciate a convenient reference for this solution, too). However, in > this > > case, I also want to make the drag coefficients a linear function of time > -- > > drag(linear, quadratic) = const(linear, quadratic) + factor(linear, > > quadratic) * time. > > If someone could plug this into Mathematica (or look it up in a handy > > formula reference), I'd really appreciate it. If someone could take the > time > > to point at the proper online reference, that'd be wonderful, too! > > Sincerely, > > jw > > > > -- > > Americans might object: there is no way we would sacrifice our living > > standards for the benefit of people in the rest of the world. > Nevertheless, > > whether we get there willingly or not, we shall soon have lower > consumption > > rates, because our present rates are unsustainable. > > > > > > > ------------------------------------------------------------------------------ > > Download Intel® Parallel Studio Eval > > Try the new software tools for yourself. Speed compiling, find bugs > > proactively, and fine-tune applications for parallel performance. > > See why Intel Parallel Studio got high marks during beta. > > http://p.sf.net/sfu/intel-sw-dev > > _______________________________________________ > > 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 > > > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > 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 > -- Raymond "VisualPhoenix" Barbiero Programmer EA Montreal |
|
From: Jon V. <ju...@gm...> - 2010-03-10 18:05:45
|
My math is just as rusty as yours, so I can't help much here, but maybe this can help you find your solution: http://www.wolframalpha.com/examples/Integrals.html Good luck ;-) On Wed, Mar 10, 2010 at 5:49 PM, Jon Watte <jw...@gm...> wrote: > I'm looking for a closed form solution for a differential equation. I did > pass this stuff 20 years ago, but was more interested in graph theory, > discrete math and DSP, so it's all vanished from my brain :-) > The equation is given a point mass that leaves a start position with a start > velocity. On this point mass is acting a fixed gravitational force (in a > fixed direction), as well as a linear and quadratic motion-opposed force > (air drag) based on a linear and quadratic coefficient of air drag. So far, > it's pretty much your standard "cannonball" equation (although I'd really > appreciate a convenient reference for this solution, too). However, in this > case, I also want to make the drag coefficients a linear function of time -- > drag(linear, quadratic) = const(linear, quadratic) + factor(linear, > quadratic) * time. > If someone could plug this into Mathematica (or look it up in a handy > formula reference), I'd really appreciate it. If someone could take the time > to point at the proper online reference, that'd be wonderful, too! > Sincerely, > jw > > -- > Americans might object: there is no way we would sacrifice our living > standards for the benefit of people in the rest of the world. Nevertheless, > whether we get there willingly or not, we shall soon have lower consumption > rates, because our present rates are unsustainable. > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > 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 > |
|
From: Jon W. <jw...@gm...> - 2010-03-10 16:50:23
|
I'm looking for a closed form solution for a differential equation. I did pass this stuff 20 years ago, but was more interested in graph theory, discrete math and DSP, so it's all vanished from my brain :-) The equation is given a point mass that leaves a start position with a start velocity. On this point mass is acting a fixed gravitational force (in a fixed direction), as well as a linear and quadratic motion-opposed force (air drag) based on a linear and quadratic coefficient of air drag. So far, it's pretty much your standard "cannonball" equation (although I'd really appreciate a convenient reference for this solution, too). However, in this case, I also want to make the drag coefficients a linear function of time -- drag(linear, quadratic) = const(linear, quadratic) + factor(linear, quadratic) * time. If someone could plug this into Mathematica (or look it up in a handy formula reference), I'd really appreciate it. If someone could take the time to point at the proper online reference, that'd be wonderful, too! Sincerely, jw -- Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. |
|
From: <Pau...@sc...> - 2010-02-11 14:46:40
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > Hi! I was wondering if there is a better way for finding the contact > points in 2D when using SAT. Here's what i currently use: > > Find the two objects positions pos1New and pos2New that represent > the positions when the two objects are just touching and are about > to collide if moved further. Find the minimum translation vector, > let it be vectMTD. > > Take polygon1 in position pos1New and find the minimum of projecting > it's vertices onto vectMTD. Also store the points that cause this > minimum projection measure int list L1. > Build a separating plane using vectMTD and one of these points > detected. Now build a second list(L2) of points that lie on this > plane but correspond to polygon2 in position pos2New. > > If one of the lists has 1 point an the other two then we have > vertex-edge case, if both have one point then we have vertex-vertex case. > If both lists have two points than we have edge-edge case. We > calculate a new plane along the edge of the polygons using a normal > perpendicular to vectMTD and located in the origin. Next the for > points are sorted based on their distance to the plane. The second > and third point define the line of collision. Hi Adrian, In 2d there is only edge/vertex and vertex/edge cases. Once you have determined which case you have, you take the edge from one object and then build another edge from the vertex of the other using some metric to choose the other vertex (like vertex which produces most edge overlap, for example) and then simply project the vertices of one edge onto the other edge (clamping to edge extents) and visa versa, giving you two contact points for each object, penetration distances and a single normal (the normal from MTD). Thats what we did anyway :) Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBS3QSBHajGqjtoMHxAQgK/AgAjF9cOwqaP93BadjnQDfsyj2K/7Z4XjQ/ w96MEdcMopygc1mouIAUcDUsoTvhLABXBysQFLE7aNyoUEM1yFip9LS1oetqrB6q ATjfdUFz6OpuX1+qhWYqV2SiTu6GcX1akO1svQXuKxHKklZhaA1zHn0We0L0rQ8e DhIRMnaOFDpa0uxO9p3Zge67HKUINwqxEG6LbixjummZn6Qm5/7yx5QNpnKAlE90 fegXEBqLKAonEcmiDYvSWbIQHIfiZNnACqv++eSFRg1yzxMw9W6+MoWxk5ImPkPe /E2sK0JMPhVQmJQSYVJ+6QrM1mzCSH4lRldtv5tVud3RctaU6RTzeQ== =UVEJ -----END PGP SIGNATURE----- |
|
From: Manolache A. <pro...@ya...> - 2010-02-11 14:07:56
|
Hi! I was wondering if there is a better way for finding the contact points in 2D when using SAT. Here's what i currently use:
Find the two objects positions pos1New and pos2New that represent the positions when the two objects are just touching and are about to collide if moved further. Find the minimum translation vector, let it be vectMTD.
Take polygon1 in position pos1New and find the minimum of projecting it's vertices onto vectMTD. Also store the points that cause this minimum projection measure int list L1.
Build a separating plane using vectMTD and one of these points detected. Now build a second list(L2) of points that lie on this plane but correspond to polygon2 in position pos2New.
If one of the lists has 1 point an the other two then we have vertex-edge case, if both have one point then we have vertex-vertex case.
If both lists have two points than we have edge-edge case. We calculate a new plane along the edge of the polygons using a normal perpendicular to vectMTD and located in the origin. Next the for points are sorted based on their distance to the plane. The second and third point define the line of collision.
Are there any flaws with this approach?
|
|
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: 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: Sebastian S. <seb...@gm...> - 2010-02-09 18:37:46
|
On Tue, Feb 9, 2010 at 9:35 AM, <Pau...@sc...> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA256 > > > I should have mentioned that I'm writing a 2D space shooter, so all > > the objects are moving all the time. And I'll have like 200 objects or > > so. > > Ahhh, ok - are you on a platform with reasonably quick memory (good caches > etc)? Have you tried just gridding up your world (screen?) using a quite > large cell size and do a simple bounding volume check in each cell > location? > Or even use a fairly small cell size (the size of the largest objects), and store cells with objects in them in a hashmap from the cell coordinate to a list of objects. That way you can have an infinite grid and you only need storage proportional to the number of non-empty cells for the grid itself. Of course a simple BV hierarchy (e.g. AABB-tree, BIH, etc.) works too, since you can usually adjust it to remain valid without doing a full re-insert each frame. I suspect that a simple SaP will outdo all of these though. It's just that much simpler. -- Sebastian Sylvan |
|
From: <Pau...@sc...> - 2010-02-09 09:34:58
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > I should have mentioned that I'm writing a 2D space shooter, so all > the objects are moving all the time. And I'll have like 200 objects or > so. Ahhh, ok - are you on a platform with reasonably quick memory (good caches etc)? Have you tried just gridding up your world (screen?) using a quite large cell size and do a simple bounding volume check in each cell location? The advantage of the grid is that you don't need to do any work until objects move from one cell into another. Of course if your objects are all wildly different sizes this can get tricky - there are hierarchical grid methods to cope with this but they have their own limitations... Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBS3EsOXajGqjtoMHxAQg4Fwf/RaCRsxE3qeBXKLjeVULeDqeVF0nQTZlB ZHeSkQvQ+OLgjdJpVyZsCvCAnrU7zOBS+Zu+6MzDUSi1yRZMver7Nhzfz17d7fLk tI6QLDkKzntTIMVhXjpMfxWqkLuHYElYfYzPbUQDSkLk1nhfg64alPQeFVse2huq lPUwrdbL7VMNGXIcMlGScXK8xcVu1MADhZVg+2gfMUOxZrx4gv/F6qIaVVaXF3gE dcGiSuccFinF1pq5GT5ax3/aoK3i3AREkaz6ktXjTI4AvC/1iCBF5WzPqAwUpQUo 5gOTOw3IijTM31cqU1nx3fa9h79rPx91KVnd7DjJAL3G6lneZ+jEtg== =tWrz -----END PGP SIGNATURE----- |
|
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: Samuel M. <sam...@go...> - 2010-02-08 17:03:33
|
> I thought triangulation was a O(n^2) problem at least? (looks it up on > wikipedia) ahh, i see there is talk of triangulating a simple polygon in > O(n), but i'm not sure a connected graph of all objects constitutes a > simple polygon? You can do Delaunay-Triangulation in O(n*logn), but the point is that I need to maintain a triangulation of moving points -- that's entirely different from constructing one from scratch. > The most important thing to keep in mind is that a good broad-phase > algorithm should do zero work when nothing moves in the world. > Are all your objects always moving in your world? How many objects are you > talking about? I should have mentioned that I'm writing a 2D space shooter, so all the objects are moving all the time. And I'll have like 200 objects or so. Samuel |
|
From: Simon F. <sim...@po...> - 2010-02-08 11:00:12
|
Pau...@sc... wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA256 > >> The triangulation is maintained incrementally -- normally it doesn't >> change, so it only needs to be checked if it is still valid every >> frame. If it changes, it only needs to be recalculated partially. >> This is an O(n+something for the changed part) operation. > > I thought triangulation was a O(n^2) problem at least? (looks it up on > wikipedia) ahh, i see there is talk of triangulating a simple polygon > in O(n), but i'm not sure a connected graph of all objects > constitutes a simple polygon? Drifting a bit OT, but from what I've read, the O(n) triangulation algorithm of simple polygons is said to be very complicated. Although wikipedia does have a link to a claimed simple, linear time, triangulation algorithm, until I someone posts a copy of the paper that is in English, I'll take it with a grain of salt. :) FWIW, there are O(n log* n) algorithms (the star is important) which are fairly simple to implement and are pretty much indistinguishable from O(n). Again, apologies for going a little OT. Simon |
|
From: <Pau...@sc...> - 2010-02-08 09:48:57
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > The triangulation is maintained incrementally -- normally it doesn't > change, so it only needs to be checked if it is still valid every > frame. If it changes, it only needs to be recalculated partially. This > is an O(n+something for the changed part) operation. I thought triangulation was a O(n^2) problem at least? (looks it up on wikipedia) ahh, i see there is talk of triangulating a simple polygon in O(n), but i'm not sure a connected graph of all objects constitutes a simple polygon? > Using circles makes it a bit cheaper (that's one of the reasons why I > want to use circles as bounding volumes), it's something like 6 The trouble with circles is that they don't fit the kind of triangles that a convex decomposition algorithm spits out very well, since they can be long and thin. We used AABBs in the end. > I guess by multi-sweep you mean doing the sweeping on more than one > axis? How do you combine the results of the sweeps, for example for > 100x100 objects arranged in a grid? Multi-sweep is where you divide your (huge) world up into a small number of chunks (rectangles in 2d) and then do regular sweep and prune in each chunk. This gets around the clustering problem where far away objects can cause a lot of clustered entries on one axis. We just used regular SAP for the record :) > My motivation for trying this is that all broad phase algorithms I > know of are far away from a O(n) running time and have other The most important thing to keep in mind is that a good broad-phase algorithm should do zero work when nothing moves in the world. > Maybe the cost per object is too high to be competitive with other > methods like SnP. But for a very high number of objects it will > definitely be better. In any case it is worth trying out... Are all your objects always moving in your world? How many objects are you talking about? Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBS2/eAHajGqjtoMHxAQjybQf/UrQsqYNvEQN82/slrWd8LwdOQchc2X4v GlwZ8lfHhMH7JB0uFnRPmgyd/pvIlj/q8JFi0SL+m0wrQNemw9Y0DvVhj3FNyk6M ezSqU5MvjVc6H6+Bp3ZGXDOWyCpgYW5FBENI8OKHkirv2YgC3Lk4iYAxIx/HPQPo 6zIbXpL1eBIM53BrcYR1WHHU57NwqHxHOZjjM6KYIt+M/vzX/fi0UFiKN4lhFkNf fOKhgdWgUsmCIFDUV/j3z+CnsCMfFSqgevSd2sDy78O5dx7rZrs+nBaSvsN31+AN IoyQVqD/RAdoXGNfGR1GxQcoGIDOU92fjijoBYOGgA/DQUzkC4lomw== =pibX -----END PGP SIGNATURE----- |
|
From: Nathaniel H. <na...@io...> - 2010-02-08 06:21:53
|
SIGGRAPH Talks are due on February 18, less than two weeks away. Submitting a talk proposal is actually quite easy. More details in a recent post on the Real-Time Rendering blog: http://www.realtimerendering.com/blog/game-developers-submit-a-siggraph-talk-before-february-18/ Thanks, Naty Hoffman |
|
From: Samuel M. <sam...@go...> - 2010-02-08 04:47:57
|
> At first glance this approach seems pretty complex and expensive for a > broad phase? I can't see how you can do this without triangulation and > thats not a cheap operation. The triangulation is maintained incrementally -- normally it doesn't change, so it only needs to be checked if it is still valid every frame. If it changes, it only needs to be recalculated partially. This is an O(n+something for the changed part) operation. > Even then, you have to intersect polygons > against AABBs which is actually quite a costly operation - not that far > away from a full narrow phase. Using circles makes it a bit cheaper (that's one of the reasons why I want to use circles as bounding volumes), it's something like 6 line-circle intersection tests per object on average. But yes, the cost per object is quite high compared to other methods. > I would recommend sweep and prune, or multi-sweep and prune if your worlds > are huge. We used sweep and prune in little big planet psp and it worked > quite well. I guess by multi-sweep you mean doing the sweeping on more than one axis? How do you combine the results of the sweeps, for example for 100x100 objects arranged in a grid? My motivation for trying this is that all broad phase algorithms I know of are far away from a O(n) running time and have other limitations. The triangulation method doesn't have any limitations on object sizes or distribution and should have an expected O(n) running time (and memory requirement) if neighborhood relations between objects don't change too much in one frame. Maybe the cost per object is too high to be competitive with other methods like SnP. But for a very high number of objects it will definitely be better. In any case it is worth trying out... Greets, Samuel |
|
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: <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 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 -------------------------------------------------- |
|
From: Peter-Pike S. <pet...@ho...> - 2010-02-06 16:25:04
|
I don't believe they do - the "5*3" numbers from the talk are (DC + linear + optimal_linear intensity) * 3 = (1 + 3 + 1)*3 I hope that makes sense... Peter-Pike Date: Fri, 5 Feb 2010 16:03:56 +0000 From: sam...@ge... To: gda...@li... Subject: Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3" Hi Peter, Do you have a link to a paper/slides explaining why they store an “optimal linear” direction separately? I’m not sure why you wouldn’t want to just use the L1 coeffs as a vector? I couldn’t find an explanation in the links below. Thanks, Sam From: Peter-Pike Sloan [mailto:pet...@ho...] Sent: 01 February 2010 21:45 To: gda...@li... Subject: Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3" Hi, I believe the source of confusion is that in this equation (5) things are expressed in the local coordinate frame, the fact that they show 3 coefficients implies they are using quadratic SH (so when rotated into the local frame and integrated against a clamped cosine function you only need the 3 ZH coefficients.) The general case (where you don't know the coordinate frame, or you want to evaluate for any normal) requires all 9 coefficients. I think the "5*3" comes from the compression mentioned in Hao's slides (linear SH + RGB for directional light in "optimal linear" direction. Which is 5*3 scalars.) The compression work is Wang et al, I think Yaohua's slides are more indicative of what was actually used... Peter-Pike Sloan Date: Fri, 29 Jan 2010 16:28:57 +0100 From: seb...@do... To: gda...@li... Subject: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3" Hello all, I tried to contact the author of this two (now old) paper, without success,: "Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf) and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf) so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :) 1. "Lighting and Material of Halo 3" About equation (5) the diffuse reflectance using SH basis the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i A_i is the projection of the cosine lobe in SH, and as it is radially symetric. all coefficient with m != 0 are 0. After that the author give the first three term of A_i. I wondering how many band are use for this calculation ? (order 3, 4 or more ?) I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf) that order 3 SH is sufficient for approximate light source but for HDR light sources he recommand order 5. As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i) This mean 4 coefficient to store by color channel. As I am pretty sure the author store HDR data, can someone lighten me ? 2. About texture storage (which are deduced from above statement) I try to figure out how are encoded the incident radiance in their SHLightmap. From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to store for each texel a vector of 5 * 3 float values. I don't figure what are the values exactly. My assumption is that "3" is for each channel color RGB, But I can't figure what's the 5 is ? Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case) or maybe order 6 ? In this same paper later I found: A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative) And B. Each band of the SH coefficients (RGB) are converted to Luvw space I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf) What I don't understand is that A and B seem different. I can't understand what is store. Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order or do they store store 5 SH coefficient for channel color R in two DXT5 ? So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ? Cause It looks like to be pretty big. Thanks for anyone interested by this post Best regards Lagarde Sébastien |
|
From: Yaser Z. <y...@ya...> - 2010-02-06 16:14:02
|
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 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: 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: Sébastien L. <seb...@do...> - 2010-02-05 17:23:01
|
I think halo wanted to store direct + indirect lighting in their SH lightmap, so they require L2 coeff , (if only indirect lighting was store L1 coeff will be sufficient) As RGB * 9 coeff = 27 float represent too much data to store in texture, they compress by converting the L2 coeff by L1 coeff + a directional light RGB You can find a similar conversion in "Stupid spherical harmonics tricks" section "Extracting Conventional Lights from SH" where an ambient light + directional light is extracted from SH coefficient. The difference here is that instead of using a conventional ambient light, the ambient light is the remaining L1 SH coefficient after removing the contribution of the directional light in the optimal linear direction (at least, I suppose they do that). You can find explanation and code of this in this paper: http://ati.amd.com/developer/SIGGRAPH08/Chapter03-SBOT-March_of_The_Froblins.pdf So to sum up, they get their L2 coeff, they calc the dominant light intensity RGB from them, they extract this dominant light intensity RGB from L2 coeff and discard quadratic coefficient to only conserve L1 coeff. So you get remaining L1 coeff RGB = 12 float and HDR dominant RGB = 3 float, this result in 15 float instead of the 27 initially which they claim of similar quality. At runtime, mesh are lighted by a RGB directional light as usual, and the L1 contribution is added to the diffuse part of the lighting. If you not compress, you light your mesh with L2 coeff directly (for the diffuse part). The point here is that they store the intensity RGB, they don't need to store "optimal linear" direction as it can be retrieve from L1 SH coeff. (at least, this is my question, if L1 coeff are remaining SH light, we won't get the same "optimal linear" direction, so I suppose they store the L1 SH light, and remove dominant RGB contribution in the shader, any though about this ?) Of course, all this is just guess. Peter ? Lagarde Sébastien De : Sam Martin [mailto:sam...@ge...] Envoyé : vendredi 5 février 2010 17:46 À : Game Development Algorithms Objet : Re: [Algorithms] Some question about "Lighting and Material ofHalo3" and "Lightmap compression in Halo 3" Hi Peter, Do you have a link to a paper/slides explaining why they store an "optimal linear" direction separately? I'm not sure why you wouldn't want to just use the L1 coeffs as a vector? I couldn't find an explanation in the links below. Thanks, Sam From: Peter-Pike Sloan [mailto:pet...@ho...] Sent: 01 February 2010 21:45 To: gda...@li... Subject: Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3" Hi, I believe the source of confusion is that in this equation (5) things are expressed in the local coordinate frame, the fact that they show 3 coefficients implies they are using quadratic SH (so when rotated into the local frame and integrated against a clamped cosine function you only need the 3 ZH coefficients.) The general case (where you don't know the coordinate frame, or you want to evaluate for any normal) requires all 9 coefficients. I think the "5*3" comes from the compression mentioned in Hao's slides (linear SH + RGB for directional light in "optimal linear" direction. Which is 5*3 scalars.) The compression work is Wang et al, I think Yaohua's slides are more indicative of what was actually used... Peter-Pike Sloan ________________________________ Date: Fri, 29 Jan 2010 16:28:57 +0100 From: seb...@do... To: gda...@li... Subject: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3" Hello all, I tried to contact the author of this two (now old) paper, without success,: "Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf) and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf) so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :) 1. "Lighting and Material of Halo 3" About equation (5) the diffuse reflectance using SH basis the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i A_i is the projection of the cosine lobe in SH, and as it is radially symetric. all coefficient with m != 0 are 0. After that the author give the first three term of A_i. I wondering how many band are use for this calculation ? (order 3, 4 or more ?) I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf) that order 3 SH is sufficient for approximate light source but for HDR light sources he recommand order 5. As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i) This mean 4 coefficient to store by color channel. As I am pretty sure the author store HDR data, can someone lighten me ? 2. About texture storage (which are deduced from above statement) I try to figure out how are encoded the incident radiance in their SHLightmap. >From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to store for each texel a vector of 5 * 3 float values. I don't figure what are the values exactly. My assumption is that "3" is for each channel color RGB, But I can't figure what's the 5 is ? Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case) or maybe order 6 ? In this same paper later I found: A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative) And B. Each band of the SH coefficients (RGB) are converted to Luvw space I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf) What I don't understand is that A and B seem different. I can't understand what is store. Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order or do they store store 5 SH coefficient for channel color R in two DXT5 ? So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ? Cause It looks like to be pretty big. Thanks for anyone interested by this post Best regards Lagarde Sébastien |
|
From: <Pau...@sc...> - 2010-02-05 16:42:14
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hi Samuel, At first glance this approach seems pretty complex and expensive for a broad phase? I can't see how you can do this without triangulation and thats not a cheap operation. Even then, you have to intersect polygons against AABBs which is actually quite a costly operation - not that far away from a full narrow phase. I would recommend sweep and prune, or multi-sweep and prune if your worlds are huge. We used sweep and prune in little big planet psp and it worked quite well. Just my 2p :) Cheers, Paul. Samuel Moll <sam...@go...> wrote on 03/02/2010 14:38:46: > @Ben: Thanks for the link, but I wanted to avoid doing full Delauney > triangulation since everything remotely Delauney-like suffices for > me... but I can probably use some of the methods in this paper. > @ Erwin: Thought I read somewhere that Box2D uses a hash... but the > source code looks alot like a AABB tree ;) > > > But I think I found something better, because I realized that I don't > really need a triangulation, only some partition for example using > polygons... > > Okay, here's the outline to my approach: > Every objects center is a "node", around the node is this objects > bounding volume (I think I'll use circles). > Then you build a graph that partitions the plane into (convex and > concave) polygons (You could make the graph so that only triangles are > used). On every corner of a polygon is an object, no object is on the > inside of a polygon. > > Now you test for every object which polygon its bounding volume > intersects. Obviously it intersects at least all polygons adjacent to > its node; if the bounding volumes are relatively tight, it should not > intersect more than these. > I think the average number of bounding volume tests for each object > should be around 6. > > Now all nodes move, and if the graph changes its topology, it needs to > be repaired. This is the part where I have no concrete algorithm > yet... but I guess I'll find one. I'm relatively sure that this step > should be fast ;) > > Then the graph is optimized: a few edges are swapped, inserted etc. to > avoid slivers and such. This should be easy. > > Greets, > Samuel > > > > On Wed, Feb 3, 2010 at 6:39 AM, Erwin Coumans <erw...@gm...> wrote: > > > > Hi Samuel, > > > > Box2d uses a dynamic AABB tree for the broadphase, based on the original > > implementation from our Bullet library in 3d. > > > > This tree is incrementally updated, faster than sweep and prune. > > > > No spatial hash. > > > > I'm interested in your approach. How do you 'triangulate' the centers, and > > compute connectivity? > > > > Thanks, > > Erwin > > > > Feel free to forward this to the list, I cannot mail to the list because of > > mail server issues. > > > > Sent from my iPhone > > > > On Feb 2, 2010, at 16:54, Samuel Moll <sam...@go...> wrote: > > > >> Hello all, > >> > >> I need a broadphase collision detection algorithm for 2D rigid body > >> physics (continuous collision detection, but that shouldn't matter for > >> the broadphase...). > >> > >> I have objects of wildly varying sizes, lots of free space and > >> possibly lots of clustering or even a single object very far away from > >> all the others, so a Quadtree (without some strange modifications, > >> wrapping the world came to mind) is not the best option. > >> > >> What I came up with is to take all the objects positions and > >> triangulate this point set. Then for each triangle I determine which > >> objects it overlaps and test all these objects for collision. > >> > >> This has a number of advantages, and I believe it could be competitive > >> to sweep and prune or Quadtrees (at least in 2D, in 3D its probably > >> not cool, but who knows?). I couldn't find anything about this method, > >> but if somebody already invented it I'd appreciate some pointers. > >> > >> What I need now is an (efficient :D) algorithm for updating the > >> triangulation when the points move. i.e. given a valid triangulation > >> (no triangles overlap, triangulates the convex hull of all points) and > >> movement vectors for all points, how can I "repair" the old > >> triangulation? > >> > >> The first part of the problem is how to maintain fat triangles > >> (slivers lead to poor collision rejection). I'm sure there are already > >> good algorithms to incrementally maintain a good triangulation, but I > >> couldn't find them. Also, the union of all triangles must stay convex. > >> > >> The second problem is how to detect and remove triangle overlaps that > >> arise due to fast-moving objects. I have no idea how to do this > >> robustly (theoretically, the points could teleport arbitrarily) > >> > >> I guess somebody already has solved this problem, but I could find no > >> relevant paper... > >> > >> Of course I'll release the finished implementation as open source, or > >> try to incorporate it into Box2D if they want it and if it proves > >> faster than their existing spatial hashing ;) > >> > >> > >> Sincerely, > >> Samuel Moll > >> > >> > >> > - ------------------------------------------------------------------------------ > >> 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 > >> _______________________________________________ > >> 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 > > > > - ------------------------------------------------------------------------------ > 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 > _______________________________________________ > 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 ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBS2xEHXajGqjtoMHxAQi/iQf+LA826T+HJfDyYpXe89DM3tx1H9bBBbME ND94GJj6Gbd93YNNgfXfYQV1kkyKKE+jyRG0IrQmrd3UaKIb2176hHkRfeDtmuJQ LH9W45L9ePp9kLYqadveQv0CKME8Vy9Bg9MlmTtDYp56eLUa7A0uUHVFmRaJmExK AgmZLio9fiuR14bUqHXXik50Wk7kwXcOt0sWQqSO0HPmXyLFGgCRiNF1TSzxjPZA hK7dbKzoS772s6UyT6QHqeD3B5XE6J4cJCY0utNNxMeNCcVUaP0CcS+5//IlfGZn ZcFZOvLJGoY2Mt9h1JDFWY3blmWLla+7mrGWWAag7aqCdtg2U02pYQ== =pGyB -----END PGP SIGNATURE----- |
279 messages has been excluded from this view by a project administrator.
