next up previous index
Next: Other optimisation tools Up: GEOM010 Tracking inside Previous: GEOM010 Tracking inside

Virtual divisions

Instead of a linear or binary search (time spent proportional or logarithmic with the number of volumes, respectively), a `direct access' technique has been developed to make the time basically independent from the number of volumes. Every volume containing other volumes is `virtually' divided in equal slices at initialization time via the call to GGCLOS (the best axis is computed automatically). For each slice, a data structure is filled with a list of the volumes identifiers intersecting such slice. Slices with identical lists are pointing to the same contents and are collected. At tracking time it is immediate to find in which slice the particle is and only its contents have to be checked. The same is true to find the next boundary to be crossed: only if the intersection point with a content lies outside the current collection of slices, the next one will be checked. The algorithm gives in average about a factor 2 in speed for the overall simulation in the large detectors. It also minimizes the dependency of the performance on the skill and experience of the programmer and allows a fast tracking even in geometrical structures received from CAD systems.


Janne Saarela
Mon Apr 3 12:46:29 METDST 1995