From: Eugen Leitl (eugen_at_leitl.org)
Date: Wed Nov 12 2003 - 04:51:06 CST

Haven't seen it come over, so I'm resending it minus the MIME signature.

----- Forwarded message from Eugen Leitl <eugen_at_leitl.org> -----

From: Eugen Leitl <eugen_at_leitl.org>
Date: Wed, 12 Nov 2003 11:22:51 +0100
To: John Stone <johns_at_ks.uiuc.edu>, vmd-l_at_ks.uiuc.edu
Subject: Re: vmd-l: Highlighting nearest atom ? (wrt to a tool)
User-Agent: Mutt/1.4i

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
> > mailto:baaden_at_smplinux.de - http://www.marc-baaden.de
> > 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: johns_at_ks.uiuc.edu Phone: 217-244-3349
> WWW: http://www.ks.uiuc.edu/~johns/ Fax: 217-244-6078
-- Eugen* Leitl leitl
______________________________________________________________
ICBM: 48.07078, 11.61144 http://www.leitl.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE

----- End forwarded message -----
-- Eugen* Leitl leitl
______________________________________________________________
ICBM: 48.07078, 11.61144 http://www.leitl.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE