gdalgorithms-list

[Algorithms] Looking for a differential equation closed form

[Jon W. <jw...@gm...>]

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.

Re: [Algorithms] Looking for a differential equation closed form

[Jon V. <ju...@gm...>]

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&#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.
> 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
>

Re: [Algorithms] Looking for a differential equation closed form

[Raymond B. <ray...@gm...>]

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&#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.
> > 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&#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.
> 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

[Algorithms] Cache-coherent hashing for broad-phase collision detection

[Darren G. <dg...@ke...>]

Hi,

I am looking at ways of improving cache coherence for a typical 
broad-phase collision detection scenario (cpu).  The basic 
implementation utilizes these data structures:

	struct ObjectTracking {
		int ObjectIndex;
		int RefCount;
	};

	typedef set<ObjectTracking> Tile;

	struct TilingLevel {
		vector<Tile> Tiles;
		int Pitch;
		Tile& Map(int x, int y) { return Tiles[y*Pitch+x]; }
	};

	struct TilingHierarchy {
		vector<TilingLevel> TilingLevels;
		Tile& Map(int level, int x, int y)  { return TilingLevels[level].Map(x,y); }
	};


And the hot process involves frequent iteration of:

	for level from 0 to maxlevel
	for y from y0(level) to y1(level)
	for x from x0(level) to x1(level)
		tilingHierarchy.Map(level,x,y).InsertOrRemove();


Performance becomes an issue here when the std::set allocations get 
spread out across process memory.  I will therefore replace 
individual sets with a single shared map to explore implementations 
for coherence:

	(level,x,y,ObjectIndex)->(RefCount).


(level,x,y,ObjectIndex) has simple perfect hash functions since the 
boundary conditions are known at start.  Local memory access roughly 
favours tiling levels > tiling level > tile row > tile according to 
the given code, but I am wary of less obvious yet still important 
observations that may be missed.


Does this sound about right?  Are there any better options I have 
flown right past?

Thank you.



Cheers,
Darren Grant

Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Sebastian S. <seb...@gm...>]

On Mon, Mar 22, 2010 at 9:49 PM, Darren Grant <
dg...@ke...> wrote:

> Hi,
>
> I am looking at ways of improving cache coherence for a typical
> broad-phase collision detection scenario (cpu).  The basic
> implementation utilizes these data structures:
>
>        struct ObjectTracking {
>                int ObjectIndex;
>                int RefCount;
>        };
>
>        typedef set<ObjectTracking> Tile;
>
>        struct TilingLevel {
>                vector<Tile> Tiles;
>                int Pitch;
>                Tile& Map(int x, int y) { return Tiles[y*Pitch+x]; }
>        };
>
>        struct TilingHierarchy {
>                vector<TilingLevel> TilingLevels;
>                Tile& Map(int level, int x, int y)  { return
> TilingLevels[level].Map(x,y); }
>        };
>
>
> And the hot process involves frequent iteration of:
>
>        for level from 0 to maxlevel
>        for y from y0(level) to y1(level)
>        for x from x0(level) to x1(level)
>                tilingHierarchy.Map(level,x,y).InsertOrRemove();
>
>
> Performance becomes an issue here when the std::set allocations get
> spread out across process memory.  I will therefore replace
> individual sets with a single shared map to explore implementations
> for coherence:
>
>        (level,x,y,ObjectIndex)->(RefCount).
>
>
> (level,x,y,ObjectIndex) has simple perfect hash functions since the
> boundary conditions are known at start.  Local memory access roughly
> favours tiling levels > tiling level > tile row > tile according to
> the given code, but I am wary of less obvious yet still important
> observations that may be missed.
>
>
> Does this sound about right?  Are there any better options I have
> flown right past?
>
> Thank you.


Try a single hash table (multimap) mapping from the cell position to objects
in that cell position? You could try open adressing to get rid of pointers
altogether and have just a single flat array at the bottom of your data
structure, although that has limitations (difficulty deleting, less than
gracious performance degradation as the load factor grows).

-- 
Sebastian Sylvan

Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[John R. <jra...@gm...>]

You definitely do not want to ever be using a set or a map.  The only reason
to use a set or a map is if you absolutely need to constantly maintain
something in sorted order; which is rarely ever the case.  Most of the time
you just want to do a key/value lookup and for that a hash table is
extremely fast.  Using the STL in performance sensitive code is also
questionable as a whole lot of memory allocations and copy constructors get
executed both of which you want to avoid.

If you are going to use the STL, and then have a profile of many tiny
allocations, you should consider using a custom small memory allocator;
there are several implementations available.  If you are dealing in a
heavily multi-threaded environment you need to take that into consideration
as well.  Something like the Hoard memory allocator is not only designed to
handle many tiny allocations efficiently but also minimizes thread
contention.

John

On Mon, Mar 22, 2010 at 6:05 PM, Sebastian Sylvan <
seb...@gm...> wrote:

>
>
> On Mon, Mar 22, 2010 at 9:49 PM, Darren Grant <
> dg...@ke...> wrote:
>
>> Hi,
>>
>> I am looking at ways of improving cache coherence for a typical
>> broad-phase collision detection scenario (cpu).  The basic
>> implementation utilizes these data structures:
>>
>>        struct ObjectTracking {
>>                int ObjectIndex;
>>                int RefCount;
>>        };
>>
>>        typedef set<ObjectTracking> Tile;
>>
>>        struct TilingLevel {
>>                vector<Tile> Tiles;
>>                int Pitch;
>>                Tile& Map(int x, int y) { return Tiles[y*Pitch+x]; }
>>        };
>>
>>        struct TilingHierarchy {
>>                vector<TilingLevel> TilingLevels;
>>                Tile& Map(int level, int x, int y)  { return
>> TilingLevels[level].Map(x,y); }
>>        };
>>
>>
>> And the hot process involves frequent iteration of:
>>
>>        for level from 0 to maxlevel
>>        for y from y0(level) to y1(level)
>>        for x from x0(level) to x1(level)
>>                tilingHierarchy.Map(level,x,y).InsertOrRemove();
>>
>>
>> Performance becomes an issue here when the std::set allocations get
>> spread out across process memory.  I will therefore replace
>> individual sets with a single shared map to explore implementations
>> for coherence:
>>
>>        (level,x,y,ObjectIndex)->(RefCount).
>>
>>
>> (level,x,y,ObjectIndex) has simple perfect hash functions since the
>> boundary conditions are known at start.  Local memory access roughly
>> favours tiling levels > tiling level > tile row > tile according to
>> the given code, but I am wary of less obvious yet still important
>> observations that may be missed.
>>
>>
>> Does this sound about right?  Are there any better options I have
>> flown right past?
>>
>> Thank you.
>
>
> Try a single hash table (multimap) mapping from the cell position to
> objects in that cell position? You could try open adressing to get rid of
> pointers altogether and have just a single flat array at the bottom of your
> data structure, although that has limitations (difficulty deleting, less
> than gracious performance degradation as the load factor grows).
>
> --
> Sebastian Sylvan
>
>
> ------------------------------------------------------------------------------
> 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.
> 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
>

Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Jon W. <jw...@gm...>]

std::set<> is not the right solution. If there are only every a few elements
in each bucket, I suggest using a std::vector<> and just search it linearly.
Each element is 8 bytes, so 8 elements fit in a single cache line.
If you have buckets with zillions of items (a bad idea for other reasons)
and need to delete from the middle, try a std::list<> with a custom
allocator, or as others have said std::hash_map or similar.

STL containers sometimes help with caching, because they often use custom,
pool-based allocators. However, other times, they actually end up hurting,
either because the pools are too small (4 item buckets in std::deque<>,
say), or because of container implementation overhead (too many pointers
non-intrusive implementation, etc).

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.



On Mon, Mar 22, 2010 at 4:16 PM, John Ratcliff <jra...@gm...>wrote:

> You definitely do not want to ever be using a set or a map.  The only
> reason to use a set or a map is if you absolutely need to constantly
> maintain something in sorted order; which is rarely ever the case.  Most of
> the time you just want to do a key/value lookup and for that a hash table is
> extremely fast.  Using the STL in performance sensitive code is also
> questionable as a whole lot of memory allocations and copy constructors get
> executed both of which you want to avoid.
>
> If you are going to use the STL, and then have a profile of many tiny
> allocations, you should consider using a custom small memory allocator;
> there are several implementations available.  If you are dealing in a
> heavily multi-threaded environment you need to take that into consideration
> as well.  Something like the Hoard memory allocator is not only designed to
> handle many tiny allocations efficiently but also minimizes thread
> contention.
>
> John
>
> On Mon, Mar 22, 2010 at 6:05 PM, Sebastian Sylvan <
> seb...@gm...> wrote:
>
>>
>>
>> On Mon, Mar 22, 2010 at 9:49 PM, Darren Grant <
>> dg...@ke...> wrote:
>>
>>> Hi,
>>>
>>> I am looking at ways of improving cache coherence for a typical
>>> broad-phase collision detection scenario (cpu).  The basic
>>> implementation utilizes these data structures:
>>>
>>>        struct ObjectTracking {
>>>                int ObjectIndex;
>>>                int RefCount;
>>>        };
>>>
>>>        typedef set<ObjectTracking> Tile;
>>>
>>>        struct TilingLevel {
>>>                vector<Tile> Tiles;
>>>                int Pitch;
>>>                Tile& Map(int x, int y) { return Tiles[y*Pitch+x]; }
>>>        };
>>>
>>>        struct TilingHierarchy {
>>>                vector<TilingLevel> TilingLevels;
>>>                Tile& Map(int level, int x, int y)  { return
>>> TilingLevels[level].Map(x,y); }
>>>        };
>>>
>>>
>>> And the hot process involves frequent iteration of:
>>>
>>>        for level from 0 to maxlevel
>>>        for y from y0(level) to y1(level)
>>>        for x from x0(level) to x1(level)
>>>                tilingHierarchy.Map(level,x,y).InsertOrRemove();
>>>
>>>
>>> Performance becomes an issue here when the std::set allocations get
>>> spread out across process memory.  I will therefore replace
>>> individual sets with a single shared map to explore implementations
>>> for coherence:
>>>
>>>        (level,x,y,ObjectIndex)->(RefCount).
>>>
>>>
>>> (level,x,y,ObjectIndex) has simple perfect hash functions since the
>>> boundary conditions are known at start.  Local memory access roughly
>>> favours tiling levels > tiling level > tile row > tile according to
>>> the given code, but I am wary of less obvious yet still important
>>> observations that may be missed.
>>>
>>>
>>> Does this sound about right?  Are there any better options I have
>>> flown right past?
>>>
>>> Thank you.
>>
>>
>> Try a single hash table (multimap) mapping from the cell position to
>> objects in that cell position? You could try open adressing to get rid of
>> pointers altogether and have just a single flat array at the bottom of your
>> data structure, although that has limitations (difficulty deleting, less
>> than gracious performance degradation as the load factor grows).
>>
>> --
>> Sebastian Sylvan
>>
>>
>> ------------------------------------------------------------------------------
>> 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.
>> 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&#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.
> 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
>

Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Fabian G. <f.g...@49...>]

Jon Watte schrieb:
> std::set<> is not the right solution. If there are only every a few 
> elements in each bucket, I suggest using a std::vector<> and just search 
> it linearly. Each element is 8 bytes, so 8 elements fit in a single 
> cache line.
> If you have buckets with zillions of items (a bad idea for other 
> reasons) and need to delete from the middle, try a std::list<> with a 
> custom allocator, or as others have said std::hash_map or similar.

Linked lists enforce a particular order. Whenever you have something 
that is just a "bucket of things" with no particular ordering 
requirements, a good option is to just use a std::vector<> (or, more 
generally, any array - this is not STL specific). To insert, you always 
use push_back. To remove a given item "x", you do:

   std::swap(x, container.back());
   container.pop_back();

This doesn't preserve order, but it's simple, short and fast: insertion 
is amortized O(1) with std::vector semantics, and removal is guaranteed 
O(1). STL also offers this as an algorithm: there's std::remove and 
std::remove_if. Their usage is somewhat nonobvious: you do

   container.erase(std::remove(start, end), container.end());

to remove everything in [start,end) in a "non-order-preserving" way, and 
similar with remove_if which uses a predicate.

-Fabian

Re: [Algorithms] Looking for a differential equation closed form

[Stuart G. <gda...@gx...>]

<!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&amp;from=objects&amp;id=7023">http://planetmath.org/?op=getobj&amp;from=objects&amp;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&amp;#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>

Re: [Algorithms] Looking for a differential equation closed form

[Beau A. <alb...@cy...>]

Perhaps this might help?

http://www.scar.utoronto.ca/~pat/fun/NEWT3D/PDF/PRJCTILE.PDF

-Beau

On 3/10/10 10:49 AM, Jon Watte 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

Re: [Algorithms] Looking for a differential equation closed form

[Jon W. <jw...@gm...>]

That solution gets me halfway there. Pretty good! It doesn't do squared air
drag, doesn't do variable air drag over time, and needs to be
re-parameterized into vectors instead of separate scalars -- but the MAPLE
code at the end is probably the best part, because I could probably go from
there to my desired solution. Thanks!

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.



On Wed, Mar 10, 2010 at 5:47 PM, Beau Albiston <alb...@cy...> wrote:

> Perhaps this might help?
>
> http://www.scar.utoronto.ca/~pat/fun/NEWT3D/PDF/PRJCTILE.PDF
>
> -Beau
>
> On 3/10/10 10:49 AM, Jon Watte 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&#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.
> > 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&#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.
> 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
>

Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Gino v. d. B. <gin...@gm...>]

On 23-3-2010 10:34, Fabian Giesen wrote:
> Jon Watte schrieb:
>    
>> <snip>
>> If you have buckets with zillions of items (a bad idea for other
>> reasons) and need to delete from the middle, try a std::list<>  with a
>> custom allocator, or as others have said std::hash_map or similar.
>>      
> Linked lists enforce a particular order. Whenever you have something
> that is just a "bucket of things" with no particular ordering
> requirements, a good option is to just use a std::vector<>  (or, more
> generally, any array - this is not STL specific). To insert, you always
> use push_back. To remove a given item "x", you do:
>
>     std::swap(x, container.back());
>     container.pop_back();
>
> This doesn't preserve order, but it's simple, short and fast: insertion
> is amortized O(1) with std::vector semantics, and removal is guaranteed
> O(1).

I totally agree. Even with a custom allocator an std::list breaks cache 
coherence and simply has too much overhead. I would not use std::swap 
though, since x is a goner so no need to save it to back(). Instead do

std::vector<Entry>::iterator it;

...

Entry&  x = *it; //  it points to the item that needs to be destroyed, e.g.

                         // it = std::find(container.begin(), container.end(), victim);

x = container.back();

container.pop_back();


This saves you two writes since std::swap needs to create a temporary to 
hold one of the swapped values. The extra writes are better avoided if 
the size of Entry is huge or if it holds shared pointers.


>   STL also offers this as an algorithm: there's std::remove and
> std::remove_if. Their usage is somewhat nonobvious: you do
>
>     container.erase(std::remove(start, end), container.end());
>
> to remove everything in [start,end) in a "non-order-preserving" way, and
> similar with remove_if which uses a predicate.
>
> -Fabian
>
>
>    

I think you mean

container.erase(std::remove(start, end, value), container.end());


since the STL remove takes three parameters. Furthermore std::remove 
keeps the relative order intact. 
http://www.cplusplus.com/reference/algorithm/remove/
At least, that is what I see in Visual C++ 8.0 (Sometimes they do adhere 
to standards ;) Removing all values and leaving an unordered sequence 
can be done using

std::vector<Entry>::iterator it = container.begin(), last = container.end();

while (it != last)

{
     if (*it == value)

     {

         --last;
         *it = *last;
     }
     else
     {
         ++it;
     }
}

container.erase(last, container.end());


Gino

Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Darren G. <dg...@ke...>]

Thanks all for the info.

I have switched the set out with an unordered vector and will say how 
that affects things. There are at most only a handful of active 
objects per tile.

Cheers,
Darren Grant



At 05:07 AM 3/23/2010, you wrote:
>On 23-3-2010 10:34, Fabian Giesen wrote:
> > Jon Watte schrieb:
> >
> >> <snip>
> >> If you have buckets with zillions of items (a bad idea for other
> >> reasons) and need to delete from the middle, try a std::list<>  with a
> >> custom allocator, or as others have said std::hash_map or similar.
> >>
> > Linked lists enforce a particular order. Whenever you have something
> > that is just a "bucket of things" with no particular ordering
> > requirements, a good option is to just use a std::vector<>  (or, more
> > generally, any array - this is not STL specific). To insert, you always
> > use push_back. To remove a given item "x", you do:
> >
> >     std::swap(x, container.back());
> >     container.pop_back();
> >
> > This doesn't preserve order, but it's simple, short and fast: insertion
> > is amortized O(1) with std::vector semantics, and removal is guaranteed
> > O(1).
>
>I totally agree. Even with a custom allocator an std::list breaks cache
>coherence and simply has too much overhead. I would not use std::swap
>though, since x is a goner so no need to save it to back(). Instead do
>
>std::vector<Entry>::iterator it;
>
>...
>
>Entry&  x = *it; //  it points to the item that needs to be destroyed, e.g.
>
>                          // it = std::find(container.begin(), 
> container.end(), victim);
>
>x = container.back();
>
>container.pop_back();
>
>
>This saves you two writes since std::swap needs to create a temporary to
>hold one of the swapped values. The extra writes are better avoided if
>the size of Entry is huge or if it holds shared pointers.
>
>
> >   STL also offers this as an algorithm: there's std::remove and
> > std::remove_if. Their usage is somewhat nonobvious: you do
> >
> >     container.erase(std::remove(start, end), container.end());
> >
> > to remove everything in [start,end) in a "non-order-preserving" way, and
> > similar with remove_if which uses a predicate.
> >
> > -Fabian
> >
> >
> >
>
>I think you mean
>
>container.erase(std::remove(start, end, value), container.end());
>
>
>since the STL remove takes three parameters. Furthermore std::remove
>keeps the relative order intact.
>http://www.cplusplus.com/reference/algorithm/remove/
>At least, that is what I see in Visual C++ 8.0 (Sometimes they do adhere
>to standards ;) Removing all values and leaving an unordered sequence
>can be done using
>
>std::vector<Entry>::iterator it = container.begin(), last = container.end();
>
>while (it != last)
>
>{
>      if (*it == value)
>
>      {
>
>          --last;
>          *it = *last;
>      }
>      else
>      {
>          ++it;
>      }
>}
>
>container.erase(last, container.end());
>
>
>Gino
>
>
>
>
>
>
>
>
>------------------------------------------------------------------------------
>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.
>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

Darren Grant
Technical Director
http://www.kerberos-productions.com/