From: John Stone (
Date: Wed Nov 12 2003 - 10:27:19 CST

  Yeah, that's certainly one way to do it. One difficulty with directly using
voxel addresses in VMD is that people can and do load structures where atoms
overlap and violate physics now and then, so we do have to handle that case
since we don't prevent them from loading structures like that. We already use
a grid-based acceleration scheme for other things in VMD (bond search,
distance-based atom selections, the 'dynamic bonds' representation, etc...),
and I do grid-based ray tracing acceleration in Tachyon, so I'm quite familiar
with the technique in general. The main problem with doing it for VMD is
in regards to trajectory data, (both preexisting and real-time data coming
from IMD sims) where every frame needs its own grid since the atom positions
move. Even with the very efficient mapping you suggest below, there's
still O(N) work that must be done to create the grid for each timestep.

So, for VMD there's still the issue of when to create the acceleration
data structure, whether initially (most likely) or on-the-fly (not such
a good idea most likely). For IMD we'd have no choice but to create it

Anyway, the acceleration data structure is still only one issue, the other
is making a good GUI for the feature, deciding how the "highlighted" atoms
work, i.e. does the user have any control over HOW they are highlighted, etc.
The first implementation of this code was essentially hard-coded, and behaved
somewhat similarly to the way the sequence viewer extension works in VMD,
highlighting the nearby atoms in yellow, etc. If I recall correctly, there
was actually no GUI control, no way to turn it on or off at all.

Here's a fun little question for the VMD user community that relates
to this topic:
  Would you like to see a "palette" of atom selections in VMD?
  In a sense, if we had a central palette of atom selections in VMD,
  some could be manipulated in real-time by things like the sequence viewer,
  this 3-D nearest-atom tool thing we're discussing, and by any number of
  other Tcl/Python scripts, and of course the user could have his or her
  favorite atom selections for a given structure in the palette.
  If we had such a palette of atom selections, one might just choose one of
  the selections rather than typing them in anew each time in the graphical
  representations window. Does this sound advantageous? Do people make
  significant use of the same atom selections over and over, and would this
  make life easier? Or do you prefer to just type them in each time.
  (VMD already has atom selection macros that you can use to define things
   that you use really-long-term as a new atom selection word, but this isn't
   quite the same thing that I'm asking about above..)

Along with the palette of atom selections, what about associating atom
selections, and/or points in space with a textual annotation?
If you could associate textual annotations with atom selections or
spatial information, what would you want to do with them? Would you want
to color the structure by existence or density of annotation text? Would
you want to be able to click on the structure and see the annotation text
in a window somewhere? Would you want to import these text annotations from
other databases, information sources? I'm looking for ideas here as we may
do something like this in the not-too-distant future.


On Wed, Nov 12, 2003 at 11:22:51AM +0100, Eugen Leitl wrote:
> On Tue, Nov 11, 2003 at 05:40:47PM -0600, John Stone wrote:
> > One difficulty in doing a real-time highlight mode is making it
> > perform well with a large molecule. Doing picking in 3-D requires that
> > we compare the mouse or other pointer (wand, haptic, etc) position with
> > that of all "nearby" atoms. The naive implementation of picking just
> > loops over all atoms and finds the nearest one to the pointer position.
> > A more refined implementation does a spatial decomposition of the atoms
> > into a grid first, and then the mouse pointer is mapped to the nearest set
> > of grid cells, and only the atoms in the grid cells near the mouse pointer
> > are tested. That's way faster of course. The difficulty with doing this
> John: if you cut up the system box into voxels sufficiently small to hold
> individual hydrogens (voxel diagonal being the length of a H-H bond), you can
> simply scale x, y, z coordinates of each atom by a constant factor to obtain
> the coordinates of a 3d array. This would work for all physicaly realistic
> structures (no two atoms can occupy the same place). For hydrogen-less
> structures you could do with just C-C voxel diagonal, which will considerably
> reduce the memory footprint of the system.
> You could store a pointer to an atom there. Neighbors to that are just
> offsets x+1, y, z; x, y+1, z; etc.
> If if your array size is a power of two you can directly use x<<factor for
> scaling, and shift operators to directly construct the offset into the array.
> In fact, for sufficiently densely populated systems and on workstations with
> large amounts of memory (1 GByte desktops are cheap these days, cheap 64 bit
> machines (G5 and Opteron) with no 4 GByte limit are already available) you can store
> individual atoms directly in an array of structs. Notice that you can store
> coordinates relative to voxel edge, which allows you to use 8-bit integers
> for x, y, z offsets to within the cells for a compact representations,
> while retaining more than enough precision for accurate rendering.
> Such voxel-based representation is fundamentally extremely efficient for a
> number of graphics and MD related codes. The voxelbox is processed by
> linearly streaming through contiguous memory addresses (clever memory layout
> and prefetch allow a sliding neighbourhood window to stay ind 2nd level
> cache).
> The only tradeoff I see is for sparse systems, and machines which are tight
> on memory.
> > in real-time is that you have to update the spatial decomposition as
> > trajectory frames play back, etc. The most difficult case is for IMD,
> > where there's no possibility of doing lengthy pre-processing since the
> > data is coming in real-time. For IMD, this turned out to not matter as
> > much as one would expect because the structures typically consist of only
> > a few thousand atoms. As you can imagine, doing it for the general case
> > means that people might use it on structures with 500,000 to 2 million atoms,
> > so the "naive implementation" is out the window :-)
> >
> > I've been thinking about what we want to do to enable more
> > of this sort of real-time picking/highlighting in VMD and there are many
> > ways I could do it, its just a matter of having the time to attack the
> > problem. I do appreciate the suggestion, its a good one, and its just
> > a matter of having time to do it in the right way. If we can resurrect
> > that code, some may still be in the source tree and accessible by
> > undocumented commands!..., I'll let you know.
> >
> > John
> >
> > On Tue, Nov 11, 2003 at 11:09:17PM +0100, Marc Baaden wrote:
> > >
> > > Hi again,
> > >
> > > a current "difficulty" when working with tools in VMD (eg a
> > > phantom in tug mode) is to pick a specific atom. With stereo
> > > this is sort of feasible, but more often than not one gets the
> > > atom just next to the one you wanted.
> > >
> > > I wonder whether it would be possible to highlight the atom
> > > that *would* be selected (eg is nearest to the tool tip, I guess)
> > > at any given time.
> > >
> > > Something like a yellow sphere for instance ..
> > >
> > > This would certainly be even more helpful when working in mono
> > > mode.
> > >
> > > I guess that requires some hacking in the VMD source code, but if
> > > there was another possibility (tcl?) I'd give it a try ..
> > >
> > > Thanks,
> > > Marc
> > >
> > > --
> > > Dr. Marc Baaden - Institut de Biologie Physico-Chimique, Paris
> > > -
> > > FAX: +49 697912 39550 - Tel: +33 15841 5176 ou +33 609 843217
> > >
> >
> > --
> > 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: Phone: 217-244-3349
> > WWW: Fax: 217-244-6078
> -- Eugen* Leitl leitl
> ______________________________________________________________
> ICBM: 48.07078, 11.61144
> 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE

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:                 Phone: 217-244-3349              
  WWW:      Fax: 217-244-6078