gdalgorithms-list

Re: [Algorithms] Low pass filter on quaternions

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

There are open source Wiimote input libraries you could probably take a look
at. AFAICT, those generally use very simple, first-order filter type
approaches.

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 Sun, Mar 28, 2010 at 8:32 AM, John McCutchan <jo...@jo...>wrote:

> Hi,
>
> Each quaternion represents the orientation of an input device. I want
> to remove jitter that comes from holding it in a human hand.
>
> John
>
> On Sun, Mar 28, 2010 at 12:56 AM, Marc B. Reynolds
> <mar...@or...> wrote:
> > Also, what do they represent?
> >
> > -----Original Message-----
> > From: Robin Green [mailto:rob...@gm...]
> > Sent: Sunday, March 28, 2010 8:36 AM
> > To: Game Development Algorithms
> > Subject: Re: [Algorithms] Low pass filter on quaternions
> >
> >
> > Do you want to lowpass the signal, or do you want to fit a smooth
> > curve to the samples?
> > Are the samples regularly spaced?
> >
> > - Robin Green
> >
> >
> >
> > On Sat, Mar 27, 2010 at 7:14 PM, John McCutchan <jo...@jo...>
> > wrote:
> >> Hi,
> >>
> >> I have a sequence of quaternions and want to filter out any high
> >> frequency changes. I'm wondering if anyone has a paper or some code
> >> for performing a low pass filter on quaternions?
> >>
> >> Thanks,
> >> --
> >> John McCutchan <jo...@jo...>
> >>
> >>
> >
> ----------------------------------------------------------------------------
> > --
> >> 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
> >
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > 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
> >
>
>
>
> --
> John McCutchan <jo...@jo...>
>
>
> ------------------------------------------------------------------------------
> 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] Low pass filter on quaternions

[John M. <jo...@jo...>]

Hi,

Each quaternion represents the orientation of an input device. I want
to remove jitter that comes from holding it in a human hand.

John

On Sun, Mar 28, 2010 at 12:56 AM, Marc B. Reynolds
<mar...@or...> wrote:
> Also, what do they represent?
>
> -----Original Message-----
> From: Robin Green [mailto:rob...@gm...]
> Sent: Sunday, March 28, 2010 8:36 AM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Low pass filter on quaternions
>
>
> Do you want to lowpass the signal, or do you want to fit a smooth
> curve to the samples?
> Are the samples regularly spaced?
>
> - Robin Green
>
>
>
> On Sat, Mar 27, 2010 at 7:14 PM, John McCutchan <jo...@jo...>
> wrote:
>> Hi,
>>
>> I have a sequence of quaternions and want to filter out any high
>> frequency changes. I'm wondering if anyone has a paper or some code
>> for performing a low pass filter on quaternions?
>>
>> Thanks,
>> --
>> John McCutchan <jo...@jo...>
>>
>>
> ----------------------------------------------------------------------------
> --
>> 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
>
>
>
>
> ------------------------------------------------------------------------------
> 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
>



-- 
John McCutchan <jo...@jo...>

Re: [Algorithms] volumetric spotlight

[Bert P. <be...@bp...>]

Darren Grant schreef:

> The most complex approach is to write a ray-casting shader that 
> integrates over distance travelled by each eye ray through the umbra 
> volume. It is hard to get the results to overlap and intersect correctly 
> with the rest of the scene unless you have some sort of unified 
> rendering architecture built around ray-casting. Very pretty if you get 
> it working, but very difficult to deploy without limitations coming back 
> to get you later.

I'd give that a try too.  There's some good shadowmap based stuff in
ShaderX7 as well for easier integration with scene geometry (p. 331).


Also check out I3D10's update to Crytek's Light propagation volumes.


hth,
bert

Re: [Algorithms] Low pass filter on quaternions

[Marc B. R. <mar...@or...>]

Also, what do they represent?

-----Original Message-----
From: Robin Green [mailto:rob...@gm...] 
Sent: Sunday, March 28, 2010 8:36 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Low pass filter on quaternions


Do you want to lowpass the signal, or do you want to fit a smooth
curve to the samples?
Are the samples regularly spaced?

- Robin Green



On Sat, Mar 27, 2010 at 7:14 PM, John McCutchan <jo...@jo...>
wrote:
> Hi,
>
> I have a sequence of quaternions and want to filter out any high
> frequency changes. I'm wondering if anyone has a paper or some code
> for performing a low pass filter on quaternions?
>
> Thanks,
> --
> John McCutchan <jo...@jo...>
>
>
----------------------------------------------------------------------------
--
> 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] Low pass filter on quaternions

[Robin G. <rob...@gm...>]

Do you want to lowpass the signal, or do you want to fit a smooth
curve to the samples?
Are the samples regularly spaced?

- Robin Green



On Sat, Mar 27, 2010 at 7:14 PM, John McCutchan <jo...@jo...> wrote:
> Hi,
>
> I have a sequence of quaternions and want to filter out any high
> frequency changes. I'm wondering if anyone has a paper or some code
> for performing a low pass filter on quaternions?
>
> Thanks,
> --
> John McCutchan <jo...@jo...>
>
> ------------------------------------------------------------------------------
> 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
>

[Algorithms] Low pass filter on quaternions

[John M. <jo...@jo...>]

Hi,

I have a sequence of quaternions and want to filter out any high
frequency changes. I'm wondering if anyone has a paper or some code
for performing a low pass filter on quaternions?

Thanks,
-- 
John McCutchan <jo...@jo...>

Re: [Algorithms] volumetric spotlight

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

Try this one:
http://www.vis.uni-stuttgart.de/~dachsbcn/download/espmss10.pdf


On Wed, Mar 24, 2010 at 4:24 PM, Jeff Russell <je...@8m...>wrote:

> Hey, anybody have any cool reference for how to render a volumetric
> spotlight effect? I realize that full correct shadowing with volumetric
> lighting might be kind of heavy duty, so I'm willing to try something a
> little dirtier or with no shadows.
>
> Regards,
>
> Jeff
>
>
> --
> Jeff Russell
> Engineer, 8monkey Labs
> www.8monkeylabs.com
>
>
> ------------------------------------------------------------------------------
> 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
>



-- 
Sebastian Sylvan

Re: [Algorithms] volumetric spotlight

[Bob <ma...@di...>]

If you are using the texture-based method, an additive blend would be more effective than an alpha blend or mask.

--B
  From: Darren Grant 
  To: Game Development Algorithms ; Game Development Algorithms 
  Sent: Wednesday, March 24, 2010 2:19 PM
  Subject: Re: [Algorithms] volumetric spotlight


  I don't have references but here are a few techniques in increasing complexity:

  For viewers at a distance it is hard to beat the simplicity of billboard sprites. Just lock a billboard to the spotlight cone axis and use alpha blending to make the texture glow. Fade it out when the viewer gets close enough to make the effect cheesy.

  Create an umbra mesh, a skirt that resembles the spot cone and fix it to the spotlight in space. Simple vertex coloring to fade the skirt at the far end can be very effective. Again render using alpha blending. Some simple pixel shader work using normal averaging and dot product can help to hide the edges of the mesh. If you have access to the depth buffer values, you can also fade out pixels that approach the near plane so they don't clip noticeably as the viewer passes through the cone.

  The most complex approach is to write a ray-casting shader that integrates over distance travelled by each eye ray through the umbra volume. It is hard to get the results to overlap and intersect correctly with the rest of the scene unless you have some sort of unified rendering architecture built around ray-casting. Very pretty if you get it working, but very difficult to deploy without limitations coming back to get you later.


  Cheers,
  Darren




  At 09:24 AM 3/24/2010, Jeff Russell wrote:

    Hey, anybody have any cool reference for how to render a volumetric spotlight effect? I realize that full correct shadowing with volumetric lighting might be kind of heavy duty, so I'm willing to try something a little dirtier or with no shadows.

    Regards,

    Jeff


    -- 
    Jeff Russell
    Engineer, 8monkey Labs
    www.8monkeylabs.com
    ------------------------------------------------------------------------------
    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

Re: [Algorithms] volumetric spotlight

[David N. <da...@re...>]

Hi Jeff,

 

Just shooting off an idea that may be useful,

 

I'd imagine you could render the front facing polygons and then the back
facing polygons with depth testing on.  That difference in depth of the
two distance the light travels through the cone at that point. You could
then use that information to calculate how much light scattering has
occurred.

 

-= Dave

 

From: Jeff Russell [mailto:je...@8m...] 
Sent: Wednesday, March 24, 2010 12:53 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] volumetric spotlight

 

That third option is kind of what I'm leaning toward - ray tests vs a
cone are mathematically simple, so that combined with a screen depth
lookup (already available) I'm hoping to be able to swing something cool
today.

Jeff

On Wed, Mar 24, 2010 at 2:19 PM, Darren Grant
<dg...@ke...> wrote:

I don't have references but here are a few techniques in increasing
complexity:

For viewers at a distance it is hard to beat the simplicity of billboard
sprites. Just lock a billboard to the spotlight cone axis and use alpha
blending to make the texture glow. Fade it out when the viewer gets
close enough to make the effect cheesy.

Create an umbra mesh, a skirt that resembles the spot cone and fix it to
the spotlight in space. Simple vertex coloring to fade the skirt at the
far end can be very effective. Again render using alpha blending. Some
simple pixel shader work using normal averaging and dot product can help
to hide the edges of the mesh. If you have access to the depth buffer
values, you can also fade out pixels that approach the near plane so
they don't clip noticeably as the viewer passes through the cone.

The most complex approach is to write a ray-casting shader that
integrates over distance travelled by each eye ray through the umbra
volume. It is hard to get the results to overlap and intersect correctly
with the rest of the scene unless you have some sort of unified
rendering architecture built around ray-casting. Very pretty if you get
it working, but very difficult to deploy without limitations coming back
to get you later.


Cheers,
Darren






At 09:24 AM 3/24/2010, Jeff Russell wrote:

	Hey, anybody have any cool reference for how to render a
volumetric spotlight effect? I realize that full correct shadowing with
volumetric lighting might be kind of heavy duty, so I'm willing to try
something a little dirtier or with no shadows.
	
	Regards,
	
	Jeff
	
	
	-- 
	Jeff Russell
	Engineer, 8monkey Labs
	www.8monkeylabs.com

	
------------------------------------------------------------------------
------
	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-lis
t 


------------------------------------------------------------------------
------
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-lis
t




-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] volumetric spotlight

[Jeff R. <je...@8m...>]

That third option is kind of what I'm leaning toward - ray tests vs a cone
are mathematically simple, so that combined with a screen depth lookup
(already available) I'm hoping to be able to swing something cool today.

Jeff

On Wed, Mar 24, 2010 at 2:19 PM, Darren Grant <
dg...@ke...> wrote:

>  I don't have references but here are a few techniques in increasing
> complexity:
>
> For viewers at a distance it is hard to beat the simplicity of billboard
> sprites. Just lock a billboard to the spotlight cone axis and use alpha
> blending to make the texture glow. Fade it out when the viewer gets close
> enough to make the effect cheesy.
>
> Create an umbra mesh, a skirt that resembles the spot cone and fix it to
> the spotlight in space. Simple vertex coloring to fade the skirt at the far
> end can be very effective. Again render using alpha blending. Some simple
> pixel shader work using normal averaging and dot product can help to hide
> the edges of the mesh. If you have access to the depth buffer values, you
> can also fade out pixels that approach the near plane so they don't clip
> noticeably as the viewer passes through the cone.
>
> The most complex approach is to write a ray-casting shader that integrates
> over distance travelled by each eye ray through the umbra volume. It is hard
> to get the results to overlap and intersect correctly with the rest of the
> scene unless you have some sort of unified rendering architecture built
> around ray-casting. Very pretty if you get it working, but very difficult to
> deploy without limitations coming back to get you later.
>
>
> Cheers,
> Darren
>
>
>
>
>
> At 09:24 AM 3/24/2010, Jeff Russell wrote:
>
> Hey, anybody have any cool reference for how to render a volumetric
> spotlight effect? I realize that full correct shadowing with volumetric
> lighting might be kind of heavy duty, so I'm willing to try something a
> little dirtier or with no shadows.
>
> Regards,
>
> Jeff
>
>
> --
> Jeff Russell
> Engineer, 8monkey Labs
> www.8monkeylabs.com
>
> ------------------------------------------------------------------------------
> 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
>



-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] volumetric spotlight

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

I don't have references but here are a few techniques in increasing complexity:

For viewers at a distance it is hard to beat the simplicity of 
billboard sprites. Just lock a billboard to the spotlight cone axis 
and use alpha blending to make the texture glow. Fade it out when the 
viewer gets close enough to make the effect cheesy.

Create an umbra mesh, a skirt that resembles the spot cone and fix it 
to the spotlight in space. Simple vertex coloring to fade the skirt 
at the far end can be very effective. Again render using alpha 
blending. Some simple pixel shader work using normal averaging and 
dot product can help to hide the edges of the mesh. If you have 
access to the depth buffer values, you can also fade out pixels that 
approach the near plane so they don't clip noticeably as the viewer 
passes through the cone.

The most complex approach is to write a ray-casting shader that 
integrates over distance travelled by each eye ray through the umbra 
volume. It is hard to get the results to overlap and intersect 
correctly with the rest of the scene unless you have some sort of 
unified rendering architecture built around ray-casting. Very pretty 
if you get it working, but very difficult to deploy without 
limitations coming back to get you later.


Cheers,
Darren




At 09:24 AM 3/24/2010, Jeff Russell wrote:
>Hey, anybody have any cool reference for how to render a volumetric 
>spotlight effect? I realize that full correct shadowing with 
>volumetric lighting might be kind of heavy duty, so I'm willing to 
>try something a little dirtier or with no shadows.
>
>Regards,
>
>Jeff
>
>
>--
>Jeff Russell
>Engineer, 8monkey Labs
><http://www.8monkeylabs.com>www.8monkeylabs.com
>------------------------------------------------------------------------------
>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] Broadphase collision

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

Priyank,

Unless you want to write your own collision/physics engine yourself 'just
for fun' I strongly recommend you just use one of the many freely available
versions.  It's a large engineering project and almost for sure not worth
your time.

Check out; 'Bullet', 'OpCode', or 'PhysX' to name just a few.  All three of
these are free for commercial or non-commercial use and represent literally
man-years of engineering time invested.

Personally, I get no pleasure from re-writing code that is readily available
from other sources.  Unless you are writing it purely as a learning
exercise, I can't fathom a reason why you would do this.  Presumably you are
trying to create an actual game project, so wouldn't you prefer to be
working on your game instead of solving problems that have been solved many
times before by others and shared with the development community free of
charge?

John

On Wed, Mar 24, 2010 at 1:50 PM, Priyank Jain <fly...@gm...> wrote:

> Hi,
>
> I apologize in advance, but I'm not sure if my earlier message about
> broadphase collision got posted or not. Earlier when I posted it, it
> gave me a bounce-back error, saying that the message was too long, so am
> not sure if my question got posted.
>
> If none of you received it, please let me know.
>
> Thanks
> /Priyank
>
> On 3/24/2010 1:22 PM, Priyank Jain wrote:
> > Hi,
> > I am trying to implement broadphase collision for my game (3D FPS
> > genre). I have been reading about the commonly used techniques and I
> > have tailored the grid approach to my game. I want to know if this is
> > the right direction to go in or not.
> > The involved actors are :-
> > Players
> > Bullets(Fired)
> > Weapons (placed at points located throughout the level, which other
> > players can pick up, aka static objects)
> > World
> > As of now, I am just trying to get the Players and bullet collision
> > pairs.
> > Players: Players are represented by a bounding sphere, located at a
> > position and moving with a velocity. Each player would have
> > approximately the bounding sphere of same size.
> > Players - weapons
> > Players - World
> > Bullets: Bullets are represented by a segment with a start point and
> > an end point (using posn, posn + vel) (each frame). Bullet can hit :-
> > Fired Bullet     Player
> > (Other) Bullet
> > World
> >
> > Approach:
> > - As each player and bullet is created, associate a reference to each
> > entity within CollisionMgr as a list<Player*> and list<Bullet*>.
> > - On each update frame, do the following:
> > - For each player, find Cell(s); it is associated with :=> list< Cell*
> > > PlayerCells
> > - For each Bullet (segment), find Cell(s); it is associated with :=>
> > list< Cell* > BulletCells
> > - For each entity, the cell(s) can be found out based on the entity.
> > - Player: Bounding sphere :The grid size are uniformly sized cell
> > (size, M) such that the M = 2R (R = radius of the bounding sphere).
> > Thus, at any given time, at most the bounding sphere can be in contact
> > with 4 cells. To determine the cells associated, find the 8 points for
> > a given sphere (each at 45 degrees to the X,Y,Z axis along the 8
> > octants). (And then find out, in which grid cell does each of the
> > point lie. This could at max return 4 cells).
> > - Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel).
> > Thus, all the cells that the line passes through would yield the cells.
> > - Cell can be a structure like
> > Cell {
> > List < Player*>
> > List < Bullet* >
> > Value (x,y,z) => unique value based on these three coordinates
> > }
> > - As a cell is found by either of the entities, given its coordinates
> > and grid position, a cell can be put on the hash-map. As the players
> > and bullets yield cells, they can be referenced using this map and
> > in-turn populate the list of player and bullet residing within that
> > cell structure.
> > - After all the player and bullet –affected cells have been found, if
> > we iterate through the hash-map, then it would yield all the possible
> > pair of colliding players and bullets in a given cell. This can then
> > be further handled using narrow-phase collision.
> >
> > Does this sound feasible ? I'd really like to get some feedback on this.
> >
> > Thank you
> > /Priyank Jain
>
>
> ------------------------------------------------------------------------------
> 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] Broadphase collision

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

By way of anecdote, here is my experience: I am 
inserting bounding boxes into an implementation 
of the hierarchical hash table described in mirtich96a (2.4.2):

         <http://cg.cs.uni-bonn.de/docs/teaching/2004/SS/seminar_anim/documents/Mirtich96a.pdf>http://cg.cs.uni-bonn.de/docs/teaching/2004/SS/seminar_anim/documents/Mirtich96a.pdf 


This approach has proven effective for a 
relatively even distribution of many dynamic 
objects of reasonably varying size and velocity. 
The memory requirements can be quite large, which 
makes it more suitable for PC. I have thousands 
of objects running roughly 1-m to 1000-m in 
diameter and capped at 200-m/s, for instance, but 
very few are moving noticeably at any given time.

You may want to explore a hybrid partitioning 
approach to get the most out of your static world 
geometry. If you have a scenario with only a 
moderate number of small objects moving around 
there are better options. A tighter space 
partitioning and quad tree may be a better option.


Cheres,
Darren Grant.



At 10:22 AM 3/24/2010, Priyank Jain wrote:
>Hi,
>I am trying to implement broadphase collision for my game (3D FPS
>genre). I have been reading about the commonly used techniques and I
>have tailored the grid approach to my game. I want to know if this is
>the right direction to go in or not.
>The involved actors are :-
>Players
>Bullets(Fired)
>Weapons (placed at points located throughout the level, which other
>players can pick up, aka static objects)
>World
>As of now, I am just trying to get the Players and bullet collision pairs.
>Players: Players are represented by a bounding sphere, located at a
>position and moving with a velocity. Each player would have
>approximately the bounding sphere of same size.
>Players - weapons
>Players - World
>Bullets: Bullets are represented by a segment with a start point and an
>end point (using posn, posn + vel) (each frame). Bullet can hit :-
>Fired Bullet    Player
>(Other) Bullet
>World
>
>Approach:
>- As each player and bullet is created, associate a reference to each
>entity within CollisionMgr as a list<Player*> and list<Bullet*>.
>- On each update frame, do the following:
>- For each player, find Cell(s); it is associated with :=> list< Cell* >
>PlayerCells
>- For each Bullet (segment), find Cell(s); it is associated with :=>
>list< Cell* > BulletCells
>- For each entity, the cell(s) can be found out based on the entity.
>- Player: Bounding sphere :The grid size are uniformly sized cell (size,
>M) such that the M = 2R (R = radius of the bounding sphere). Thus, at
>any given time, at most the bounding sphere can be in contact with 4
>cells. To determine the cells associated, find the 8 points for a given
>sphere (each at 45 degrees to the X,Y,Z axis along the 8 octants). (And
>then find out, in which grid cell does each of the point lie. This could
>at max return 4 cells).
>- Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). Thus,
>all the cells that the line passes through would yield the cells.
>- Cell can be a structure like
>Cell {
>List < Player*>
>List < Bullet* >
>Value (x,y,z) => unique value based on these three coordinates
>}
>- As a cell is found by either of the entities, given its coordinates
>and grid position, a cell can be put on the hash-map. As the players and
>bullets yield cells, they can be referenced using this map and in-turn
>populate the list of player and bullet residing within that cell structure.
>- After all the player and bullet ­affected cells have been found, if we
>iterate through the hash-map, then it would yield all the possible pair
>of colliding players and bullets in a given cell. This can then be
>further handled using narrow-phase collision.
>
>Does this sound feasible ? I'd really like to get some feedback on this.
>
>Thank you
>/Priyank Jain
>
>------------------------------------------------------------------------------
>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] Broadphase collision

[Priyank J. <fly...@gm...>]

Hi,

I apologize in advance, but I'm not sure if my earlier message about 
broadphase collision got posted or not. Earlier when I posted it, it 
gave me a bounce-back error, saying that the message was too long, so am 
not sure if my question got posted.

If none of you received it, please let me know.

Thanks
/Priyank

On 3/24/2010 1:22 PM, Priyank Jain wrote:
> Hi,
> I am trying to implement broadphase collision for my game (3D FPS 
> genre). I have been reading about the commonly used techniques and I 
> have tailored the grid approach to my game. I want to know if this is 
> the right direction to go in or not.
> The involved actors are :-
> Players
> Bullets(Fired)
> Weapons (placed at points located throughout the level, which other 
> players can pick up, aka static objects)
> World
> As of now, I am just trying to get the Players and bullet collision 
> pairs.
> Players: Players are represented by a bounding sphere, located at a 
> position and moving with a velocity. Each player would have 
> approximately the bounding sphere of same size.
> Players - weapons
> Players - World
> Bullets: Bullets are represented by a segment with a start point and 
> an end point (using posn, posn + vel) (each frame). Bullet can hit :-
> Fired Bullet     Player
> (Other) Bullet
> World
>
> Approach:
> - As each player and bullet is created, associate a reference to each 
> entity within CollisionMgr as a list<Player*> and list<Bullet*>.
> - On each update frame, do the following:
> - For each player, find Cell(s); it is associated with :=> list< Cell* 
> > PlayerCells
> - For each Bullet (segment), find Cell(s); it is associated with :=> 
> list< Cell* > BulletCells
> - For each entity, the cell(s) can be found out based on the entity.
> - Player: Bounding sphere :The grid size are uniformly sized cell 
> (size, M) such that the M = 2R (R = radius of the bounding sphere). 
> Thus, at any given time, at most the bounding sphere can be in contact 
> with 4 cells. To determine the cells associated, find the 8 points for 
> a given sphere (each at 45 degrees to the X,Y,Z axis along the 8 
> octants). (And then find out, in which grid cell does each of the 
> point lie. This could at max return 4 cells).
> - Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). 
> Thus, all the cells that the line passes through would yield the cells.
> - Cell can be a structure like
> Cell {
> List < Player*>
> List < Bullet* >
> Value (x,y,z) => unique value based on these three coordinates
> }
> - As a cell is found by either of the entities, given its coordinates 
> and grid position, a cell can be put on the hash-map. As the players 
> and bullets yield cells, they can be referenced using this map and 
> in-turn populate the list of player and bullet residing within that 
> cell structure.
> - After all the player and bullet –affected cells have been found, if 
> we iterate through the hash-map, then it would yield all the possible 
> pair of colliding players and bullets in a given cell. This can then 
> be further handled using narrow-phase collision.
>
> Does this sound feasible ? I'd really like to get some feedback on this.
>
> Thank you
> /Priyank Jain

[Algorithms] Broadphase collision

[Priyank J. <fly...@gm...>]

Hi,
I am trying to implement broadphase collision for my game (3D FPS 
genre). I have been reading about the commonly used techniques and I 
have tailored the grid approach to my game. I want to know if this is 
the right direction to go in or not.
The involved actors are :-
Players
Bullets(Fired)
Weapons (placed at points located throughout the level, which other 
players can pick up, aka static objects)
World
As of now, I am just trying to get the Players and bullet collision pairs.
Players: Players are represented by a bounding sphere, located at a 
position and moving with a velocity. Each player would have 
approximately the bounding sphere of same size.
Players - weapons
Players - World
Bullets: Bullets are represented by a segment with a start point and an 
end point (using posn, posn + vel) (each frame). Bullet can hit :-
Fired Bullet 	Player
(Other) Bullet
World

Approach:
- As each player and bullet is created, associate a reference to each 
entity within CollisionMgr as a list<Player*> and list<Bullet*>.
- On each update frame, do the following:
- For each player, find Cell(s); it is associated with :=> list< Cell* > 
PlayerCells
- For each Bullet (segment), find Cell(s); it is associated with :=> 
list< Cell* > BulletCells
- For each entity, the cell(s) can be found out based on the entity.
- Player: Bounding sphere :The grid size are uniformly sized cell (size, 
M) such that the M = 2R (R = radius of the bounding sphere). Thus, at 
any given time, at most the bounding sphere can be in contact with 4 
cells. To determine the cells associated, find the 8 points for a given 
sphere (each at 45 degrees to the X,Y,Z axis along the 8 octants). (And 
then find out, in which grid cell does each of the point lie. This could 
at max return 4 cells).
- Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). Thus, 
all the cells that the line passes through would yield the cells.
- Cell can be a structure like
Cell {
List < Player*>
List < Bullet* >
Value (x,y,z) => unique value based on these three coordinates
}
- As a cell is found by either of the entities, given its coordinates 
and grid position, a cell can be put on the hash-map. As the players and 
bullets yield cells, they can be referenced using this map and in-turn 
populate the list of player and bullet residing within that cell structure.
- After all the player and bullet –affected cells have been found, if we 
iterate through the hash-map, then it would yield all the possible pair 
of colliding players and bullets in a given cell. This can then be 
further handled using narrow-phase collision.

Does this sound feasible ? I'd really like to get some feedback on this.

Thank you
/Priyank Jain

[Algorithms] volumetric spotlight

[Jeff R. <je...@8m...>]

Hey, anybody have any cool reference for how to render a volumetric
spotlight effect? I realize that full correct shadowing with volumetric
lighting might be kind of heavy duty, so I'm willing to try something a
little dirtier or with no shadows.

Regards,

Jeff


-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

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/

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

[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] 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

[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

[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

[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] 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] 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