VMD-L Mailing List

From: John Stone (johns_at_ks.uiuc.edu)
Date: Fri May 11 2007 - 13:46:39 CDT

HI,
  The specifics will depend greatly on the actual calculations you
plan to do. If you use the grid as an acceleration
structure to search for atoms that meet a certain spatial locality
criteria, then what you typically do is build a uniform grid within
the unit cell. In order to search for atoms within distance X of
a point in space, you loop over grid cells which fall at least
partially within the distance sphere. Atoms contained in grid cells
that fall entirely within the sphere can simply be added to the results
list with no further testing. Atoms contained in grid cells that are
entirely outside of the sphere aren't considered at all. The only tests
that need to be performed are for atoms contained in grid cells that are
partially in and partially out of the distance sphere you care about.

By selecting the grid resolution so each cell contains tens or hundreds of
atoms, you can save a tremendous amount of memory references
and arithmetic in doing distance based searches of this type.
This is just one example of how you can use a grid-based spatial
acceleration data structure to speed up queries. Kd trees and other
data structures can do even better than uniform grids for various
types of queries, but can be far more complex to implement effectively.
A grid based method is easy to adapt for periodicity simply by using
modular arithmetic when testing individual grid cells within the
radius of interest. There are likely ways to do the same for Kd trees
but they are undoubtably much more involved.
Hope that helps.

Cheers,
  John Stone
  vmd_at_ks.uiuc.edu

On Fri, May 11, 2007 at 06:35:38PM +0000, Arturas Ziemys wrote:
>
> Thanks for prompts answer!
> Do yo know some reference about that uniform grid or what kind of topic is related to that I could search more info? Because, I have no idea what is like - just some sense.
>
> Is that (uniform grid) precise treatment of distances, or have some tolerance?
>
> Best
> Arturas
>
> >-----Original Message-----
> >From: John Stone [mailto:johns_at_ks.uiuc.edu]
> >Sent: Friday, May 11, 2007 06:15 PM
> >To: 'Arturas Ziemys'
> >Cc: 'vmd-l', namd-l_at_ks.uiuc.edu
> >Subject: Re: vmd-l: Fast routines for distance evaluations using PBC.
> >
> >
> >A uniform grid should to work fine even for PBC, though the algorithm
> >for PBC requires doing wraparound on the grid cells. This is the strategy
> >I plan to implement for adding PBC handling in some of the internal VMD
> >routines for things like the "within" selection and so on.
> >Let me know if you need help with this.
> >
> >Cheers,
> > John Stone
> > vmd_at_ks.uiuc.edu
> >
> >On Fri, May 11, 2007 at 04:52:49PM +0000, Arturas Ziemys wrote:
> >> Hi,
> >>
> >> Does anybody know some routines/algorithms to make particle distance evaluation and/or selection faster than "brute-force" way recalculating those distances directly (using PBC)? One could use some things like KDTrees, but it is useless with PBC.
> >>
> >> Any clues would be welcome :) !
> >>
> >> Best
> >> Arturas Z.
> >>
> >
> >--
> >NIH Resource for Macromolecular Modeling and Bioinformatics
> >Beckman Institute for Advanced Science and Technology
> >University of Illinois, 405 N. Mathews Ave, Urbana, IL 61801
> >Email: johns_at_ks.uiuc.edu Phone: 217-244-3349
> > WWW: http://www.ks.uiuc.edu/~johns/ Fax: 217-244-6078
> >
>
> 

-- 
NIH Resource for Macromolecular Modeling and Bioinformatics
Beckman Institute for Advanced Science and Technology
University of Illinois, 405 N. Mathews Ave, Urbana, IL 61801
Email: johns_at_ks.uiuc.edu                 Phone: 217-244-3349
  WWW: http://www.ks.uiuc.edu/~johns/      Fax: 217-244-6078