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}

S  M  T  W  T  F  S 







1
(12) 
2
(5) 
3
(30) 
4
(13) 
5
(26) 
6
(37) 
7
(26) 
8
(24) 
9
(9) 
10
(34) 
11
(39) 
12
(16) 
13
(21) 
14
(27) 
15
(11) 
16
(2) 
17
(7) 
18
(6) 
19
(3) 
20
(15) 
21
(4) 
22

23

24
(6) 
25
(20) 
26
(32) 
27
(35) 
28
(28) 

From: Mark Wayland <Mwayland@to...>  20030206 23:52:33

Chris, I wrote a memory manager about 3 weeks ago. The manager is based on a set of fixed sized buckets for small allocations and a singly linked = list for large ones. Here's some tips for pretty good performance: * If your pool allocations are in fixed sized increments, say 8 bytes, = then you can quickly and easily find which pool an allocation should come from: nPoolIndex =3D nAllocSize >> 3; if (nPoolIndex > MAX_POOL_INDEX) AllocFromList(...) * When a pool is empty there are many heuristics you can use to fill it. = A couple I've used are: * Simply filling from the list with a fixed number of allocs. So you = simply alloc n * nAllocSize from the large list. * Take items from pools whose size is a multiple of the requested size. = A simple example is filling the 8byte pool with a 16byte pool alloc split into 2 8byte allocs. There are lots of things you could do here. I would suggest adding a = hint mechanism whereby the app can prealloc a set number of pool items. * The large list is stored as a basic structure like struct ListNode { ListNode* pNextNode; unsigned int nNodeSize; }; Obviously, pNextNode is used in implementing the linked list. The fun = bit comes into play when allocating... when you find a node containing = enough memory to allocate from, instead of splitting it into multiple nodes = and relinking the list, simply decrement the size by the allocated amount = and return a pointer to pListNode + nNodeSize  nAllocSize, effectively allocating from the end of the block. * In memory allocations, I store a pointer to the heap object that the = allocation came from and the size of the allocation. This lets us use multiple = heaps safely and the pointer to the heap effectively acts as the magic number = ensuring allocs came from the same heap that they're being freed from. I'm no expert on memory management or anything like that, but I've used = the above techniques to implement a working memory manager that is at least 10 = times faster than what we had (in most cases faster than 10x), took 3 hours to write, = 8 hours to debug a failure after more than 100000 allocations, supports multiple = heaps, and is conceptually very simple in operation. It is also trivial to get = allocation statistics from it... Let me know if you want more info, Cheers, Mark > Original Message > From: Chris Brodie [mailto:Chris.Brodie@...] > Sent: Wednesday, 5 February 2003 4:58 PM > To: 'gdalgorithmslist@...' > Subject: [Algorithms] Memory Allocators >=20 >=20 > Can anyone here recommend a small easy to understand memory=20 > manager. I'm stuck writing a utility to allocate AGP ram and=20 > would like a reference.=20 >=20 > How I'm doing(or am trying to) it is I allocate a block of=20 > memory to the manager. The manager then is asked for memory.=20 > It subdivides it's pool in POW2 increments until it's found=20 > the smallest division thats larger than the requested size.=20 > Marks the allocation as used and returns the pointer. The=20 > pointer is stored as an ID ready for the=20 > 'deallocation'(unmarking). I'm considering things like=20 > keeping lists of the unused fragments in an ordered vector=20 > for easier searching as well. >=20 > Does anyone have any information on a implementation on how I=20 > can get away with doing this? >=20 > Many thanks, >=20 > Chris >=20 >=20 > NOTICE > This email and any attachments are confidential and may=20 > contain copyright material of Macquarie Bank or third=20 > parties. If you are not the intended recipient of this email=20 > you should not read, print, retransmit, store or act in=20 > reliance on this email or any attachments, and should=20 > destroy all copies of them. Macquarie Bank does not guarantee=20 > the integrity of any emails or any attached files. The views=20 > or opinions expressed are the author's own and may not=20 > reflect the views or opinions of Macquarie Bank.=20 >=20 >=20 >=20 >  > This SF.NET email is sponsored by: > SourceForge Enterprise Edition + IBM + LinuxWorld =3D Something 2 See! > http://www.vasoftware.com > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 
From: Jaba Adams <Jaba@ps...>  20030206 22:23:00

>... >to say in my previous message. Considering in a very short >period of time that force are constant >is not really annoying. Sorry, but this is simply wrong. The fundamental problem is assuming that a continuously variable force (or acceleration) can be approximated _sufficiently closely_ by a piecewiselinear force, to ensure stable simulation. Euler's method is an analytical solution. It is only exact if the acceleration is perfectly constant over the time period in question. The moment you start talking about "approximately constant" forces, decreasing time steps, etc, you're doing numerical (imprecise) integration, anyway. You will have to address the same problems that other schemes do, and that Euler integration doesn't handle. Example: Consider a 1kg mass particle, constrained to move along one axis (say x). You've set up a repulsion force field at 0; it will apply a force to the particle, pointing away from the origin. Let's say the force is 1 / x Newtons, where x is the particle's position. Okay, now suppose that the particle is at x = 1, traveling with v = 10 m/s. Let's use Euler's method: x1 = x0 + v0 * t + 0.5 * a * t^2 x1 = 1  10 * t + 0.5 * (1 / 1) * t^2 x1 = 1  10 * t + 0.5 * t^2 Question: can the particle ever overshoot the origin, and have a negative x position? If we continuously update a, based on x, the answer should be "No!" For arbitrarily small x, the repulsion gets arbitrarily large. The particle should never hit (or cross) 0. Now, let's look at the formula. Are there values of t for which x1 < 0 ? Yup. For t > than about 0.101 s, the particle will overshoot. What happens then? Well, x is now slightly negative, so the particle receives a large force towards ve x; it accelerates off towards ve infinity. This kind of situation happens all the time. This is exactly the problem that the numeric integration methods address. In the case of a spring, you'd see energy slowly seeping into the system, because the spring never actually hits its rest length. Eventually, it goes BOOM!  Jaba 
From: Dean Ashton <dean.ashton@ju...>  20030206 22:16:36

Hi, > Does anybody know how efficient (in terms of both performance and > fragmentation) > is the default PS2 memory manager. I've heard that it is far=20 > better than PS1 but I wasn't given any detail. The default PS2 memory manager is based on Doug Lea's malloc = implementation (http://gee.cs.oswego.edu/dl/). When I last looked at the PS2 = implementation (back when I was at SCEE Cambridge) it appeared to be a pretty old = version they based it on though. Unfortunately I don't have any performance = figures, but at the time we didn't hesitate in replacing it given Sony's complete failure to fix the PS1 memory allocation system (even though they had at least 5 attempts at rewriting it). Anyway, check out the current version of the source on the link above. = Might be useful. Cheers, Dean  Dean Ashton, Senior Programmer Just Add Monsters Ltd, Cambridge =20 
From: Jeff Lander <jeffl@da...>  20030206 21:52:26

>Considering in a very short period of time that force are constant is = not really annoying. That is the point, the short period of time is really a problem. = Neither the formula you stated or Euler's are terribly stable = integration schemes. You could add some extra calculations to make it = slightly better or worse than Euler's. But, if your system is in any = ways stiff, and your integrator isn't very good, the system will not = converge to the solution if the timestep is at all very large. In fact = they will diverge. Don't take my word for it. Try it. =20 Use my sample problem: F =3D Kd V (a simple drag force) Set up an initial velocity and try some fairly large K (say 2 to 3) and = then integrate it for given stepsizes. You will see the point where = your integration will diverge rather than converge. Even if you set the = Kd to something pretty normal like 0.5, if the stepsize is large, it = will not work. You should be able to see that for a complex problem = like a mass pulled on by many springs, this is a real issue. A more robust integration system that more closely approximates the = nonlinear function will converge. 
From: Michael Pohoreski <MPohoreski@cy...>  20030206 21:49:08

You'll get far faster performance, and less overhead if you use fixedsize memory pools. Why are you using a generic allocator anyways on consoles?! Original Message From: Yordan Gyurchev [mailto:yordan@...]=20 Sent: Thursday, February 06, 2003 4:25 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Memory Allocators Does anybody know how efficient (in terms of both performance and fragmentation) is the default PS2 memory manager. I've heard that it is far better than PS1 but I wasn't given any detail. Thanks, Yordan 
From: Yordan Gyurchev <yordan@gy...>  20030206 21:24:03

Someone mentioned this technique few weeks ago (on another forum) but had failed to give a reference. (thanks for the link by the way) He (the guy I spoke to) called it "BSP segmentation" though or may be I'm confusing techniques here... At that time I tried to experiment with treebased memory management but (due to my inexperience) I didn't quite like the result. So I went on and experimented with another approach which is my current preferred method... I will try to explain it here (without doubt it has already been implemented). What I didn't like about the tree based approach is the considerable amount of memory lost for bookkeeping. In the case of the article it is 28 bytes per tree node. So what I did is to move to the usual opponent of trees  hash tables. Hashed by size (for best fit searches) with a minimal bookkeeping header which looks like that: struct MemChunkStruct { struct MemChunkStruct* m_pNeighbourPrev; struct MemChunkStruct* m_pNeighbourNext; unsigned int m_Size; /* highest bit 1 means > allocated }; The neighbor pointers are used for merging (coalescing) free nodes quickly. When not allocated the structure is "expanded" with two pointers for "hash table bin" double linked list support. (the two pointers are effectively in the "free" memory area so they don't take additional space. struct MemChunkExStruct { MemChunk m_Head; struct MemChunkExStruct* m_pNext; struct MemChunkExStruct* m_pPrev; }; This structure is used only when the chunk is free. When allocated the chunk does not present in the "hash table". Bin sorting: Each hash table bin is sorted in ascending size order to maximize best fit searches. First fit is best fit. Hash function: Due to the nature of memory blocks a nice function can be chosen that concentrates more bins in the small sizes and disperses bins in larger sizes. I use: f(x) = (Table size)(2x  x^2) where x is 1/(max size). Everything above max size is put in the last bin. Worst cases and inefficiencies:  when the allocate request hits an empty bin it proceeds to the next (larger size) bin. In the case of many empty bins this results in a linear search. To resolve that an additional array of (table size) integers can be present which indicates for each empty bin which is the next larger nonempty bin. The update of the last is minimal and will speed the search of nonempty bin to O(1)  the usual drawback that follows all hash tables  worst case results in a linked list The size lost to book keeping is 12 bytes per memory allocation plus the memory for the bins (and if implemented  first non empty bin array). In debug the structure can be 16 bytes adding some safety information for debugging. Source code: You can find my experimental source code at: http://www.gyurchev.com/files/memoryman_hash.txt Let me know what you guys think. Is this useful? Does anybody know how efficient (in terms of both performance and fragmentation) is the default PS2 memory manager. I've heard that it is far better than PS1 but I wasn't given any detail. Thanks, Yordan  Original Message  From: "Martin Gladnishki" <bzb@...> To: <gdalgorithmslist@...> Sent: Thursday, February 06, 2003 10:36 AM Subject: Re: [Algorithms] Memory Allocators > Folks, > > I ran a search for the paper Willem mentioned and found this little gem: > "Segregated Binary Trees: AddressOrdered Binary Trees Revisited" > by Krishna Kavi > http://citeseer.nj.nec.com/532444.html > > >From what I read there, this is the best memory management data structure > I've seen so far. The author uses a sizerangelist of startaddressordered > binary trees, each containing freed blocks of sizes within the corresponding > sizerange. The trees are ordered by block start address to enable free > block merging where possible and each treenode maintains the size of the > largest blocks in its left & right subtrees in order to boost freeblock > searching performance. At the end, Krishna Kavi also proposes the old trick > of using a list of recently freed blocks to boost cache utilization. He > warns that this LIST may kill the performance benefits of the main structure > if made too big and deals with the problem by limiting the list size and > moving the half of its contents in the main list of trees whenever this > recentlist gets full. And last but not least  this structire keeps page > swaps down to a reasonable minimum, compared to other algorithms. > > And yet Krishna Kavi fails to realize that this structure of recently freed > blocks (here come my two dimes :) can be implemented just as efficiently as > the main structure of freed blocks  with the same kind of addressordered > tree featuring the same limitation  fixed number of nodes, and cutting by > half when exhausted. > > What do you think? > > Cheers, > Martin > >  Original Message  > From: "Willem H. de Boer" <Willem@...> > To: <gdalgorithmslist@...> > Sent: Wednesday, February 05, 2003 11:32 AM > Subject: RE: [Algorithms] Memory Allocators > > > > Alternatively, have a look at the paper "The Memory > > Fragmentation Problem: Solved?", by Mark S. Johnstone > > and Paul R. Wilson. > > > > It's got some good explanations of memory allocation > > schemes, and the pow2 stuff you describe sounds remarkably > > similar to a socalled "buddy system". > > > > Cheers, > > > >  > > Willem H. de Boer http://www.whdeboer.com > > mail AT whdeboer DOT com > > > > >Original Message > > >From: Gareth White [mailto:gwhite@...] > > >Sent: 05 February 2003 06:24 > > >To: gdalgorithmslist@... > > >Subject: Re: [Algorithms] Memory Allocators > > > > > > > > >This went round the lists last week and sounds like it could > > >be what you're > > >after. > > > > > > > > >Gareth White  Engine Programmer  Ratbag Pty Ltd > > >Level 8, 63 Pirie Street, Adelaide, SA, Australia, 5000 > > >Ph: +61 8 8223 5830, Fax: +61 8 8223 5746, Mob: 0403 942668 > > >http://www.ratbaggames.com/ > > > > > > > > > Original Message  > > >From: "Johnson, James" <James.Johnson@...> > > >To: <gdalgorithmslist@...> > > >Sent: Wednesday, January 29, 2003 1:03 PM > > >Subject: RE: [Algorithms] Game Entities  avoiding inheritance > > >/ fixed pool > > >allocation > > > > > >Check out boost.org, specifically their memory pool implementation > > >http://www.boost.org/libs/pool/doc/index.html. It has a > > >options for ordered > > >free's limiting fragmentation and fast frees. It's implemented via C++ > > >templates, is easy to use, free to use (no GPL or LGPL), well > > >documented, > > >and much faster than standard new/delete/malloc/free. Even if > > >you don't use > > >it, its a fantastic reference. Did I mention it's cross > > >platform? It is. > > > > > > Original Message  > > >From: "Chris Brodie" <Chris.Brodie@...> > > >To: <gdalgorithmslist@...> > > >Sent: Wednesday, February 05, 2003 4:27 PM > > >Subject: [Algorithms] Memory Allocators > > > > > > > > >Can anyone here recommend a small easy to understand memory > > >manager. I'm stuck > > >writing a utility to allocate AGP ram and would like a reference. > > > > > > > > > > > > > > >This SF.NET email is sponsored by: > > >SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! > > >http://www.vasoftware.com > > >_______________________________________________ > > >GDAlgorithmslist mailing list > > >GDAlgorithmslist@... > > >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > >Archives: > > >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > >  > > This SF.NET email is sponsored by: > > SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! > > http://www.vasoftware.com > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > >  > This SF.NET email is sponsored by: > SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! > http://www.vasoftware.com > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Igor Kravtchenko <igor@ob...>  20030206 21:17:12

> The force from the spring changes with the position. That force = changes constantly. Btw. You talk about spring changes, but you could also mention any kind = of particle systems where a set of gravitational's point apply forces (attractive or = repulsive) to a body. But the fact the forces changes constantly should not avoid to still use = Newton's formula as I tried to say in my previous message. Considering in a very short period of = time that force are constant is not really annoying. Igor. 
From: Chris Hecker <checker@d6...>  20030206 20:53:23

> > 2. How to efficiently compute the linear solution to the closest point on > > a simplex. >a.k.a. Johnson's distance algorithm, or the "J" from "GJK". It's also just Cramer's Rule for solving linear systems, incrementally computed. Chris 
From: Igor Kravtchenko <igor@ob...>  20030206 20:23:33

Jeff, > If the acceleration is constant over the life of the object, you can = obtain the position directly without integration. Well, maybe it's just language barrier but even if the acceleration is = constant, you still have to integrate. The Newton's formula is precisely deducted by starting from a constant = value, integrating once to obtain the velocity over the time, and integrating once again to obtain position over time. = If the acceleration is not constant but evolves in a linear fashion you have to integrate for the third time (that would = start to be a little complex). The fact you know the formula in "advance" in your code doesn't remove the fact it becomes = from a serie of integration thought on paper. > The force from the spring changes with the position. That force = changes constantly. Okey so it's when the acceleration changes. However we could still use Newton's law and add: acc +=3D accChange * dt; it would become an approximation but still more precis than "pure" = Euler. Here I agree that would start another topic. > The point of numerical integration is to approximate the solution to = this continuous function at fixed timesteps. > For those problems, different integrators work differently. Read my = articles from game developer March and > April 1999, http://www.darwin3d.com/gdm1999.htm#gdm0399 and it will be = more clear. I guess I already knew your articles. The issue is not that I don't know/understand the involved = mathematicals. That's not the problem. I just wonder why Newton's basis are not more directly used. All rises from them. = Approximative integration should be used only when the integration formula becomes too complex/costly to be computed = in a real time application. That's all. But well, I will have to satisfy of that for the moment. "It's in the order of things" Jem'Hadar :) Igor. 
From: Pierre Terdiman <p.terdiman@wa...>  20030206 19:03:18

> Think of skeletal animation. When my keyframe data is composed out of a > quaternion defining the orientation and a vector defining the position. a.k.a. a "PR" structure, named after 3DS MAX's "PRS" when you drop the "S" :) > After the interpolations I transform the data into a matrix and then > multiply each of these matrices with its parent matrix. Would it be cheaper > to transform the quaternions and vectors into the global coordinatesystem > and then create the matrices? Yes, mainly because there are less cache misses. Search the archives for a frebruary 2001 thread named "Matrix vs. Quaternion Hierarchy walk". It's also faster for most hierarchy walks, say in OBB trees, etc  Pierre http://www.codercorner.com 
From: Pierre Terdiman <p.terdiman@wa...>  20030206 18:59:46

> 2. How to efficiently compute the linear solution to the closest point on > a simplex. a.k.a. Johnson's distance algorithm, or the "J" from "GJK". I'd say the easiest introduction to GJK is in the old Kelvin Chung's thesis (the guy from QCollide). It draws a clear distinction between the various parts IMHO. (search the archives for more GJK fun)  Pierre http://www.codercorner.com 
From: Paul Firth <pfirth@at...>  20030206 18:53:34

Jay Stelly wrote: > > but use a > > > polygon instead of a circle and it's a finite, converging, > > exact search > > > (ignoring floating point issues). > > > > Right, so if I use a polygon instead of a circle does GJK simply > > become a walking on the surface of the Minkowski sum search for the > > minimum distance to the origin? > > Sort of. "walking on the surface" is not really an accurate description. > It's more like a binary search  it will go through the middle of the sum, > not just around the surface. I'm not sure if that's what you mean, but if > so: > > In my circle/point example  if you find that the current triangle you have > does not contain the point you know whether the point is to the left or to > the right, so the next triangle you build will be in that direction. That's > a really rough description of what's going on, but GJK is definitely NOT > traversing connected features on the surface of the sum. You MAY traverse > connected features on the objects in order to accelerate the support map > computations, but from an algorithmic point of view it's a divide and > conquer kind of search to see if the point intersects the sum. With each > query you essentially cut off another piece of the sum that can't contain > the point. Ah right, I get it  so you cut the sum in half with a point which you generate using support mappings? Cheers, Paul. 
From: Dirk Gregorius <dirk@di...>  20030206 18:48:18

Hi, let's say I have two matrices M1 and M2. Both define a coordinatesystem. M1 is defined relative to our global coordinatesystem and M2 is defined relative to M1. Now I extract the rotation out of these matrices into two quaternions Q1 and Q2 and the translation data into two vectors T1 and T2. After that I have a quaternion Q2 which is IMO defined relative to Q1. Can I transform Q2 into the global coordinatesytem by some kind of quaternion composition? Think of skeletal animation. When my keyframe data is composed out of a quaternion defining the orientation and a vector defining the position. After the interpolations I transform the data into a matrix and then multiply each of these matrices with its parent matrix. Would it be cheaper to transform the quaternions and vectors into the global coordinatesystem and then create the matrices? The reason for my question is that if I would use this way I would be able to load more "bones" into a vertex shader? Kind regards Dirk 
From: Chris Hecker <checker@d6...>  20030206 18:39:22

>Right, so if I use a polygon instead of a circle does GJK simply >become a walking on the surface of the Minkowski sum search for the >minimum distance to the origin? GJK goes through the center of the object, which is part of the reason it's cool. As others have said, there are really two things glommed together in the GJK papers: 1. How to use the implicit sum (avoid forming the explicit sum) using the support mapping to find a vertex on the sum in a given direction. 2. How to efficiently compute the linear solution to the closest point on a simplex. Chris 
From: Jeff Lander <jeffl@da...>  20030206 18:37:57

Igor, If the acceleration is constant over the life of the object, you can = obtain the position directly without integration. People use this for = simulating things like cannon shots and particle systems (that you can = run now on the GPU). For any time, t: pos =3D initial_pos + initial_velocity * t + 0.5 * acc * t * t; When we simulate these types of integrations, we have to assume that = acceleration is constant through the timestep. But in most interesting = problems it really isn't. The simple case is the mass connected to a = spring and a fixed point. The force from the spring changes with the = position. That force changes constantly. The point of numerical integration is to approximate the solution to = this continuous function at fixed timesteps. For those problems, = different integrators work differently. Read my articles from game = developer March and April 1999, = http://www.darwin3d.com/gdm1999.htm#gdm0399 and it will be more clear.  Original Message =20 From: Igor Kravtchenko=20 To: gdalgorithmslist@...=20 Sent: Thursday, February 06, 2003 10:01 AM Subject: Re: [Algorithms] Euler's integration > If the acceleration is constant, there is no need to perform time = stepping. For what ? You deduct new position/rotation magically ? Igor. 
From: Jamie Fowlston <jamief@qu...>  20030206 18:23:52

analytic integration. if a is the acceleration (and is constant), and t is time starting from 0, then: v(t) = v0 + at x(t) = x0 + v0 * t + 0.5 * a * t * t jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Igor Kravtchenko Sent: 06 February 2003 18:02 To: gdalgorithmslist@... Subject: Re: [Algorithms] Euler's integration > If the acceleration is constant, there is no need to perform time stepping. For what ? You deduct new position/rotation magically ? Igor. 
From: Nick Waanders <nwaanders@re...>  20030206 18:21:54

Hi Igor,=20 When you are using springs, dampers and stuff like that, the = acceleration changes all the time.. This can make the Euler integrator = instable (depending on your timestep and magnitude of forces, etc). Maybe you've read it, but this paper describes really well what the = possible problems are with Euler and other methods: http://www2.cs.cmu.edu/~baraff/sigcourse/notesb.pdf Hope it helps! Cheers, Nick Waanders=20 Original Message From: Igor Kravtchenko [mailto:igor@...] Sent: Wednesday, February 05, 2003 7:03 PM To: gdalgorithmslist@... Subject: [Algorithms] Euler's integration Well maybe, there is something absolutely fundamental I've missed, but I = don't understand this passion for the Euler's integration. By supposing at a given time's interval, the forces acting on a body are = constant and the mass of this body stays unchanged, then the acceleration of the body is also = constant. However, we see without any concern such code : velocity +=3D acc * dt; pos +=3D velocity * dt; Here I just wonder what's this madness. Integrating with constant acceleration is trivial with Newton's formula: pos +=3D velocity * dt + 0.5 * acc * dt * dt; velocity +=3D acc * dt; and is 100% accurate with a constant acceleration. I also doubt it worth = to gain some cycles by using the Euler's integration. I try to understand what I've missed but just don't see. Igor. 
From: Jay Stelly <Jay@va...>  20030206 18:20:43

> but use a > > polygon instead of a circle and it's a finite, converging, > exact search > > (ignoring floating point issues). > > Right, so if I use a polygon instead of a circle does GJK simply > become a walking on the surface of the Minkowski sum search for the > minimum distance to the origin? Sort of. "walking on the surface" is not really an accurate description. It's more like a binary search  it will go through the middle of the sum, not just around the surface. I'm not sure if that's what you mean, but if so: In my circle/point example  if you find that the current triangle you have does not contain the point you know whether the point is to the left or to the right, so the next triangle you build will be in that direction. That's a really rough description of what's going on, but GJK is definitely NOT traversing connected features on the surface of the sum. You MAY traverse connected features on the objects in order to accelerate the support map computations, but from an algorithmic point of view it's a divide and conquer kind of search to see if the point intersects the sum. With each query you essentially cut off another piece of the sum that can't contain the point. Jay 
From: Igor Kravtchenko <igor@ob...>  20030206 18:02:29

> If the acceleration is constant, there is no need to perform time = stepping. For what ? You deduct new position/rotation magically ? Igor. 
From: Igor Kravtchenko <igor@ob...>  20030206 18:02:28

Tom, I don't get the point and what you meant by telling Euler's integration = gives more responsive position change. If you retake the context which is to have a set of forces applied to a = body in a time's interval, the kinetic of this body is just perfectly defined by the Newtow's laws. That's just = the correct math. No problem where it's used, it's just ... clean ! Igor.  Original Message =20 From: Tom Lowe=20 To: gdalgorithmslist@...=20 Sent: Thursday, February 06, 2003 5:20 AM Subject: Re: [Algorithms] Euler's integration The integration method you suggest works well for a projectile under = gravity for instance, but I've found it not as useful when using spring = models or for collisions using forces. This is because when you have a = sudden change in force (or acceleration) such as when you hit an object, = Euler's integration gives a more responsive position change. But yes, for constant acceleration, Newton's formula is perfectly = correct and also doesn't give differing results with a different dt.  Original Message =20 From: Igor Kravtchenko=20 To: gdalgorithmslist@...=20 Sent: Thursday, February 06, 2003 1:02 PM Subject: [Algorithms] Euler's integration Well maybe, there is something absolutely fundamental I've missed, = but I don't understand this passion for the Euler's integration. By supposing at a given time's interval, the forces acting on a body = are constant and the mass of this body stays unchanged, then the acceleration of the body is also = constant. However, we see without any concern such code : velocity +=3D acc * dt; pos +=3D velocity * dt; Here I just wonder what's this madness. Integrating with constant acceleration is trivial with Newton's = formula: pos +=3D velocity * dt + 0.5 * acc * dt * dt; velocity +=3D acc * dt; and is 100% accurate with a constant acceleration. I also doubt it = worth to gain some cycles by using the Euler's integration. I try to understand what I've missed but just don't see. Igor. 
From: Paul Firth <pfirth@at...>  20030206 17:59:52

Jay Stelly wrote: > In reality for a circle there are an infinite number of triangles to form, > so GJK will need an epsilon/tolernace to handle some cases, but use a > polygon instead of a circle and it's a finite, converging, exact search > (ignoring floating point issues). Right, so if I use a polygon instead of a circle does GJK simply become a walking on the surface of the Minkowski sum search for the minimum distance to the origin? Cheers, Paul. 
From: Jay Stelly <Jay@va...>  20030206 17:16:48

> Maybe I have. I've never been able to really grasp what GJK is going > even after reading numorus papers and even looking through > implementations > of it. > > Its a shame there isn't something thats written for games > programmers not > mathematicians which explains it all. The GJK algorithm is surprisingly simple once you get a few things figured out. The most difficult part conceptually is getting an intuition for the minkowski sum (some papers refer to this as the configuration space obstacle) and how that relates to the two objects. It sounds like you already have that part. So the thing that's tripping you up is most likely how the search works. I thought about writing the paper you want (GJK for game devs) after I understood GJK, but since I don't have time to do anything other than work on my game that isn't likely to happen any time soon. But here's a highlevel hint that may or may not help depending on how you're stuck (in 2d, but the logic works fine in 3d): You're trying to figure out if a point (the origin) is inside a convex polygon (minkowski sum). But you don't know the data for the polygon. You do have a way to compute verts on the polygon (this is what support maps do). The fundamental principles GJK uses are: a) any three verts of a convex polygon form a triangle that is within that polygon. b) If a point is within a triangle that is within a polygon, then the point is within the polygon. More intuitively: You have a point and a circle. You can make a triangle out of any 3 verts on the surface of a circle right? You could then test to see if the point was inside that triangle. If the point is inside that triangle, you know it's inside the circle, right?. GJK is an algorithm for picking those points on the circle to make triangles in such a way that you know when it's ok to stop (i.e. no intersections so far means the point isn't in there). In reality for a circle there are an infinite number of triangles to form, so GJK will need an epsilon/tolernace to handle some cases, but use a polygon instead of a circle and it's a finite, converging, exact search (ignoring floating point issues). Jay 
From: Paul Firth <pfirth@at...>  20030206 14:19:52

Richard Fabian wrote: > Hah! yes, of course! damn that I didn't think of it first... > > btw you can make this "nicer" by keeping the vert IDs of the joined > verts in the minkowski verts.... erm... e.g. for every vert in your > minkowski sum mesh, you will have the ID of each vert that made > that vert. > > if you check the two verts that end the edge that you collided with, > then you will find that one side of the creator vert pair (oject a > side, or object b side, will be the same on both ends of the edge.) > > e.g. you have two triangles interpenetrating, and you find that the > closest point is on edge n of your minkowski sum, you then see that > edge n has the two ending vert IDs of {2,3} and {2,1} from this you > can tell that point 2 on object 1 hit edge 31 on object 2. Ah yes, that works a treat! Much nicer than that awful search. > can't believe I didn't think of this before.... Two brains and all that... Cheers, Paul. 
From: Jamie Fowlston <jamief@qu...>  20030206 14:08:38

i'd have to read a paper again to be sure i was right, and i'm afraid i don't have time for that now. iirc, the basic idea is that you crawl along the meshes to find the points closest to each other (relying on convexity for the process to work). it's really not very complicated :) the support functions are largely about giving you a sane way to crawl across meshes, or to work the answer out analytically if you're using primitives (e.g. sphere, whatever), and to deal with rotations and so on (which can all be worked into the support functions). then, of course, you cache your closest calculated points as they're likely to be a good guess for the next time you check. jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Paul Firth Sent: 06 February 2003 13:41 To: gdalgorithmslist@... Subject: Re: [Algorithms] minkowski sum Jamie Fowlston wrote: > sounds like you're moving to the GJK style of doing things. > > keeping information linking the sum to the originals is similar to using an > implicit sum. searching through the points efficiently is likely to lead you > in the direction of support functions, i think. Maybe I have. I've never been able to really grasp what GJK is going even after reading numorus papers and even looking through implementations of it. Its a shame there isn't something thats written for games programmers not mathematicians which explains it all. Cheers, Paul.  This SF.NET email is sponsored by: SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! http://www.vasoftware.com _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Gareth Lewin <GLewin@cl...>  20030206 14:06:18

To be fair to hotmail, they give an extremely good service, much better than a lot of things I pay for. > The free, [expensive from MS means ordinary  what does free > mean] or as has > been pointed out, digest mode. Just not sure that Hotmail + a list as active as gdalgo = really workable. 