Cytosim PI Cytoskeleton Simulator

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- Class List
- Class Index
- Class Hierarchy
- Class Members

List of all members | Public Types | Public Member Functions
FiberGrid Class Reference

## Detailed Description

A divide-and-conquer algorithm is used to find all segments of fibers close to a given point:

1. It uses a grid 'mGrid' covering the space, initialized by setGrid(). After initialization, each cell of the grid has an empty SegmentList (a list of FiberLocus*).
2. clear() resets all lists on the grid
3. paintGrid() distributes the segments specified in the arguments to the cell-associated SegmentList. One of the argument specifies a maximum distance to be queried (max_range). After the distribution, tryToAttach() is able to find any segment located at a distance max_range or less from any given point, in linear time.
4. The function tryToAttach(X, ...) finds the cell on mGrid that contain X. The associated SegmentList will then contains all the segments located at distance max_range or less from X. tryToAttach() calls a function distanceSqr() sequentially for all the segments in this list, to calculate the exact Euclidian distance. Finally, using a random number it tests the probability of attachment for the Hand given as argument.

Todo:
  we could call paintGrid() only if the objects have moved by a certain threshold. This would work if we also extend the painted area around the rod, by the same threshold. we must also redo the paintGrid() when MT points are added or removed.

Such algortihm should lead to large CPU gain, if calling clear() or paintGrid() is limiting, which is the case in particular in 3D, because the number of grid-cells is large.

## Public Types
typedef Array< FiberLocus const * > | SegmentList
| type for a list of FiberLocus
typedef Grid< DIM, SegmentList, unsigned int > | grid_type

## Public Member Functions
| FiberGrid ()
| creator
virtual | ~FiberGrid ()
| destructor
int | setGrid (const Space *, const Modulo *, real max_step, unsigned long max_nb_cells)
| create a grid to cover the specified Space with cells of width max_step at most More...
bool | hasGrid () const
| true if the grid was initialized by calling setGrid()
void | clear ()
| clear the grid
void | paintGrid (const Fiber *first, const Fiber *last, real max_range)
| paint the Fibers, to be able to find up to a distance max_range More...
bool | tryToAttach (Vector const &, Hand &) const
| given a position, find nearby Fiber segments and test attachement of the provided Hand More...
SegmentList | nearbySegments (Vector const &P, real D, Fiber *exclude=0)
| return all fiber segments located at a distance D or less from P, except those belonging to exclude More...
FiberLocus | closestSegment (Vector const &)
| return the closest Segment to the given position, if it is closer than gridRange
void | testAttach (FILE *, Vector place, Fiber *start, HandProp const *)
| test the results of tryToAttach(), at a particular position More...

## Member Function Documentation

FiberGrid::SegmentList nearbySegments | ( | Vector const & | place,
|  | real | D,
|  | Fiber * | exclude = `0`
| ) |  |

This function is limited to the range given in paintGrid();

void paintGrid | ( | const Fiber * | first,
|  | const Fiber * | last,
|  | real | max_range
| ) |  |

paintGrid( first_fiber, last_fiber, max_range ) links all segments found in 'fiber' and its descendant, in the point-list GP that match distance(GP, segment) < H.

'H' is calculated such that tryToAttach() finds any segment closer than 'max_range':

To determine H, we start from a relation on the sides of a triangle: (A) distance( GP, segment ) < distance( GP, X ) + distance( X, segment ) where GP (grid-point) is the closest point on the grid to X.

Since GP in tryToAttach() is the closest point on mGrid to X, we have: (B) distance( GP, X ) < 0.5 * mGrid.diagonalLength()

Thus to find all rods for which: (B) distance( X, segment ) < max_range we simply use: H = max_range + 0.5 * mGrid.diagonalLength();

Note: H is calculated by paintGrid(), and the user only provides 'max_range'.

Linking all segments is done in an inverse way: for each segment, we cover all points of the grid inside a volume obtained by inflating the segment by the length H. We use for that the raterizer which calls the function paint() above.

int setGrid | ( | const Space * | space,
|  | const Modulo * | mod,
|  | real | max_step,
|  | unsigned long | max_nb_cells
| ) |  |

Creates a grid where the dimensions of the cells are max_step at most. If the numbers of cells that need to be created is greater than max_nb_cells, the function returns 1 without building the grid. The return value is zero in case of success.

The algorithm works with any value of max_step (the results are always correct), but max_steps affects the efficiency (speed) of the algorithm: -if max_step is too slow, paintGrid() will be slow, -if max_step is too large, tryToAttach() will be slow. A good compromise is to set max_step equivalent to the attachment distance, or at least to the size of the segments of the Fibers.

void testAttach | ( | FILE * | out,
|  | Vector | place,
|  | Fiber * | start,
|  | HandProp const * | hp
| ) |  |

Function testAttach() is given a position in space, it calls tryToAttach() from this position to check that:

- attachement has equal probability to all targets,
- no target is missed,
- attachment are not made to targets that are beyond binding_range_max

bool tryToAttach | ( | Vector const & | place,
|  | Hand & | ha
| ) |  | const

The range at which Hand will the the Fibers is limited to the range given in paintGrid()