Hierarchical Searching using the Interface

  Particle tracing methods which generate and visualize particle lines, stream surfaces ore moving clouds of particles are important tools for the examination of velocity fields. The efficiency of these methods depends senitively on searching algorithms. Let us suppose that h and are of the same size in the corresponding integration method. Fig 2 sketches a typical particle line on a 2D grid. The basic task is to locate points on the grid, which are computed by the corresponding ODE solver. For each new position we need the grid element and the corresponding local coordinates to evaluate the numerical velocity at that position. It is obvious, that a local algorithm should be used in this searching process. This local method can be provided with an inital guess, which typically is the result of the last timestep.

 
Figure 2: Typical particle line  

Figure 3 illustrates two alternative schemes. On the one hand, we can proceed recursively up and down. Thereby we first move from the guess positions fine grid element successively to coarser elements until the destination position is in the current element or we have reached the macro grid level. Then we zoom into finer grid level until the finest element which contains the destination position has been reached. On a other hand, we can start on the macro level, search for a coarse element containing the destination position and then perform the above zooming operation. Especially on hierarchical grids of a larger depth the first method is obviously the better choice. I. e. in average about four level changes (two up and two down respectively) are necessary for a 2D grid consisting of rectangles to locate the new point of the particle line under the above assumption on the step sizes.

 
Figure 3: Different searching strategies  

The kernel of the second algorithm could be implemented in the following way:

element = self->first_macro(hefAll);
element->descr->world_to_coord((ELEMENT*)element,point,local_coord);
while(element->descr->check_inside((ELEMENT*)element,local_coord)==false){
 element = self->next_macro(element,hefAll);
 }

while((help_element = element->first_child(element,hefAll))!=NULL){
 element = help_element;

 element->descr->world_to_coord((ELEMENT*)element,point,local_coord);
 while(element->descr->check_inside((ELEMENT*)element,point)==false){
   element = element->next_child(element,hefAll);
  }
 }

To improve efficiency the new interface routines

void coord_of_parent(HELEMENT3D *element, double *local_coord, 
        double *local_coord_of_parent);

and

HELEMENT3D *select_child(HELEMENT3D *element, double *local_coord,
        double *local_coord_of_child,HELEMENT3D_FLAGS hefall)

have been added. coord_of_parent() transforms the local coordinates of a point in an element to that one of the parent element. select_child() returns the child element containing a point already known to be inside the parent element and calculates its local coordinates corresponding to the child element. This allows very fast and direct access to elements of arbitrary nested hierarchical grids. With these functions at hand, the kernel for the first algorithm look as follows:

if(element != NULL){
 element->descr->world_to_coord((ELEMENT*)element,point,local_coord);
 while((-1 != element->desc->check_inside((ELEMENT3D *)element,local_coord)){
        &&(e[0]->parent!=NULL))
  help_element = element;
  ((HELEMENT3D_DESCRIPTION*)(element->descr))->coord_of_parent
	(element, local_coord,local_coord);
  element = element->parent;
  hmesh->free_element((ELEMENT3D*)help_element);
  }
 while((help_element = hmesh->select_child
	(element,local_coord,local_coord,hefAll))!=NULL)
  {element = help_element;}
 }

This algorithm is implemented in the method

HMESH3D *hmesh3d_search(VEC3 point, double *local_coord, HELEMENT3D **element)

which uses *element as the element of the intial guess, to locate a particle at position point on the grid hierarchy.