<!-- ******************************************************** -->
<!--                                                          -->
<!--  [History]                                               -->
<!--    Changed by: Gabriele Cosmo, 18-Apr-2005               -->
<!--    Converted to DocBook: Katsuya Amako, Aug-2006         -->
<!--                                                          -->
<!-- ******************************************************** -->


<!-- ******************* Section (Level#2) ****************** -->
<sect2 id="sect.Geom.Navig">
<title>
The Geometry Navigator
</title>

<para>
Navigation through the geometry at tracking time is implemented
by the class <literal>G4Navigator</literal>. The navigator is used to locate
points in the geometry and compute distances to geometry
boundaries. At tracking time, the navigator is intended to be the
only point of interaction with tracking.
</para>

<para>
Internally, the G4Navigator has several private helper/utility
classes:

<itemizedlist spacing="compact">
  <listitem><para>
    <emphasis role="bold">G4NavigationHistory</emphasis> - stores the compounded
    transformations, replication/parameterisation information, and
    volume pointers at each level of the hierarchy to the current
    location. The volume types at each level are also stored - whether
    normal (placement), replicated or parameterised.
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">G4NormalNavigation</emphasis> - provides location &amp; 
    distance computation functions for geometries containing 'placement'
    volumes, with no voxels.
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">G4VoxelNavigation</emphasis> - provides location and distance
    computation functions for geometries containing 'placement'
    physical volumes with voxels. Internally a stack of voxel
    information is maintained. Private functions allow for isotropic
    distance computation to voxel boundaries and for computation of the
    'next voxel' in a specified direction.
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">G4ParameterisedNavigation</emphasis> - provides location and
    distance computation functions for geometries containing
    parameterised volumes with voxels. Voxel information is maintained
    similarly to <literal>G4VoxelNavigation</literal>, but computation can also
    be simpler by adopting voxels to be one level deep only
    (<emphasis>unrefined</emphasis>, or 1D optimisation)
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">G4ReplicaNavigation</emphasis> - provides location and distance
    computation functions for replicated volumes.
  </para></listitem>
</itemizedlist>
</para>

<para>
In addition, the navigator maintains a set of flags for
exiting/entry optimisation. A navigator is not a singleton class;
this is mainly to allow a design extension in future (e.g
geometrical event biasing).
</para>


<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Navig.NavigTrack">
<title>
Navigation and Tracking
</title>

<para>
The main functions required for tracking in the geometry are
described below. Additional functions are provided to return the
net transformation of volumes and for the creation of touchables.
None of the functions implicitly requires that the geometry be
described hierarchically.

<itemizedlist spacing="compact">
  <listitem><para>
    <emphasis role="bold">SetWorldVolume()</emphasis>
    <para>
    Sets the first volume in the hierarchy. It must be unrotated and
    untranslated from the origin.
    </para>
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">LocateGlobalPointAndSetup()</emphasis>
    <para>
    Locates the volume containing the specified global point. This
    involves a traverse of the hierarchy, requiring the computation of
    compound transformations, testing replicated and parameterised
    volumes (etc). To improve efficiency this search may be performed
    relative to the last, and this is the recommended way of calling
    the function. A 'relative' search may be used for the first call of
    the function which will result in the search defaulting to a search
    from the root node of the hierarchy. Searches may also be performed
    using a <literal>G4TouchableHistory</literal>.
    </para>
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">LocateGlobalPointAndUpdateTouchableHandle()</emphasis>
    <para>
    First, search the geometrical hierarchy like the above method
    <literal>LocateGlobalPointAndSetup()</literal>. Then use the volume found and
    its navigation history to update the touchable.
    </para>
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">ComputeStep()</emphasis>
    <para>
    Computes the distance to the next boundary intersected along the
    specified unit direction from a specified point. The point must be
    have been located prior to calling <literal>ComputeStep()</literal>.
    </para>
    <para>
    When calling <literal>ComputeStep()</literal>, a proposed physics step is
    passed. If it can be determined that the first intersection lies at
    or beyond that distance then <literal>kInfinity</literal> is returned. In any
    case, if the returned step is greater than the physics step, the
    physics step must be taken.
    </para>
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">SetGeometricallyLimitedStep()</emphasis>
    <para>
    Informs the navigator that the last computed step was taken in its
    entirety. This enables entering/exiting optimisation, and should be
    called prior to calling <literal>LocateGlobalPointAndSetup()</literal>.
    </para>
  </para></listitem>
  <listitem><para>
    <emphasis role="bold">CreateTouchableHistory()</emphasis>
    <para>
    Creates a <literal>G4TouchableHistory</literal> object, for which the caller
    has deletion responsibility. The 'touchable' volume is the volume
    returned by the last Locate operation. The object includes a copy
    of the current NavigationHistory, enabling the efficient relocation
    of points in/close to the current volume in the hierarchy.
    </para>
  </para></listitem>
</itemizedlist>
</para>

<para>
As stated previously, the navigator makes use of utility classes to
perform location and step computation functions. The different
navigation utilities manipulate the <literal>G4NavigationHistory</literal>
object.
</para>

<para>
In <literal>LocateGlobalPointAndSetup()</literal> the process of locating a
point breaks down into three main stages - optimisation,
determination that the point is contained with a subtree (mother
and daughters), and determination of the actual containing
daughter. The latter two can be thought of as scanning first 'up'
the hierarchy until a volume that is guaranteed to contain the
point is found, and then scanning 'down' until the actual volume
that contains the point is found.
</para>

<para>
In <literal>ComputeStep()</literal> three types of computation are treated
depending on the current containing volume:

<itemizedlist spacing="compact">
  <listitem><para>
    The volume contains normal (placement) daughters (or none)
  </para></listitem>
  <listitem><para>
    The volume contains a single parameterised volume object,
    representing many volumes
  </para></listitem>
  <listitem><para>
    The volume is a replica and contains normal (placement) daughters
  </para></listitem>
</itemizedlist>
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Navig.LocPnt">
<title>
Using the navigator to locate points
</title>

<para>
More than one navigator objects can be created inside an application; these
navigators can act independently for different purposes. The main navigator
which is "<emphasis>activated</emphasis> automatically at the startup of a 
simulation program is the navigator used for the 
<emphasis>tracking</emphasis> and attached the world volume
of the main tracking (or <emphasis>mass</emphasis>) geometry.
</para>

<para>
The navigator for tracking can be retrieved at any state of the application
by messagging the <literal>G4TransportationManager</literal>:

<informalexample>
<programlisting>
  G4Navigator* tracking_navigator =
    G4TransportationManager::GetInstance()-&gt;GetNavigatorForTracking();
</programlisting>
</informalexample>

The navigator for tracking also retains all the information of the current
history of volumes transversed at a precise moment of the tracking during a
run. Therefore, if the navigator for tracking is used during tracking for
locating a generic point in the tree of volumes, the actual particle gets
also -relocated- in the specified position and tracking will be of course
affected !
</para>

<para>
In order to avoid the problem above and provide information about location
of a point without affecting the tracking, it is suggested to either use an
alternative <literal>G4Navigator</literal> object (which can then be assigned 
to the world-volume), or access the information through the step.
</para>

<!-- ******* Bridgehead ******* -->
<bridgehead renderas='sect4'>
Using the 'step' to retrieve geometrical information
</bridgehead>

<para>
During the tracking run, geometrical information can be retrieved through
the touchable handle associated to the current step. For example, to identify
the exact copy-number of a specific physical volume in the mass geometry,
one should do the following:

<informalexample>
<programlisting>
  // Given the pointer to the step object ...
  //
  G4Step* aStep = ..;

  // ... retrieve the 'pre-step' point
  //
  G4StepPoint* preStepPoint = aStep-&gt;GetPreStepPoint();

  // ... retrieve a touchable handle and access to the information
  //
  G4TouchableHandle theTouchable = preStepPoint-&gt;GetTouchableHandle();
  G4int copyNo = theTouchable-&gt;GetCopyNumber();
  G4int motherCopyNo = theTouchable-&gt;GetCopyNumber(1);
</programlisting>
</informalexample>
</para>

<para>
To determine the exact position in global coordinates in the mass geometry
and convert to local coordinates (local to the current volume):

<informalexample>
<programlisting>
  G4ThreeVector worldPosition = preStepPoint-&gt;GetPosition();
  G4ThreeVector localPosition = theTouchable-&gt;GetHistory()-&gt;
                GetTopTransform().TransformPoint(worldPosition);
</programlisting>
</informalexample>
</para>

<!-- ******* Bridgehead ******* -->
<bridgehead renderas='sect4'>
Using an alternative navigator to locate points
</bridgehead>

<para>
In order to know (when in the <literal>idle</literal> state of the 
application) in which physical volume a given point is located 
in the detector geometry, it is necessary to create an alternative 
navigator object first and assign it to the world volume:

<informalexample>
<programlisting>
  G4Navigator* aNavigator = new G4Navigator();
  aNavigator-&gt;SetWorldVolume(worldVolumePointer);
</programlisting>
</informalexample>
</para>

<para>
Then, locate the point <literal>myPoint</literal> (defined in global coordinates),
retrieve a <emphasis>touchable handle</emphasis> and do whatever you need with it:

<informalexample>
<programlisting>
  aNavigator-&gt;LocateGlobalPointAndSetup(myPoint);
  G4TouchableHistoryHandle aTouchable =
    aNavigator-&gt;CreateTouchableHistoryHandle();

  // Do whatever you need with it ...
  // ... convert point in local coordinates (local to the current volume)
  //
  G4ThreeVector localPosition = aTouchable-&gt;GetHistory()-&gt;
                GetTopTransform().TransformPoint(myPoint);

  // ... convert back to global coordinates system
  G4ThreeVector globalPosition = aTouchable-&gt;GetHistory()-&gt;
                GetTopTransform().Inverse().TransformPoint(localPosition);
</programlisting>
</informalexample>
</para>

<para>
If outside of the tracking run and given a generic local position (local to a
given volume in the geometry tree), it is -not- possible to determine a priori
its global position and convert it to the global coordinates system.
The reason for this is rather simple, nobody can guarantee that the given
(local) point is located in the right -copy- of the physical volume !
In order to retrieve this information, some extra knowledge related to the
absolute position of the physical volume is required first, i.e. one should
first determine a global point belonging to that volume, eventually making
a dedicated scan of the geometry tree through a dedicated 
<literal>G4Navigator</literal> object and then apply the method above after 
having created the touchable for it.
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Navig.ParaGeom">
<title>
Navigation in parallel geometries
</title>

<para>
Since release 8.2 of Geant4, it is possible to define geometry trees which
are <literal>parallel</literal> to the tracking geometry and having them 
assigned to navigator objects that transparently communicate in sync with 
the normal tracking geometry.
</para>

<para>
Parallel geometries can be defined for several uses (fast shower
parameterisation, geometrical biasing, particle scoring, readout
geometries, etc ...) and can <emphasis>overlap</emphasis> with the mass 
geometry defined for the tracking. The <literal>parallel</literal> 
transportation will be activated only after the registration of the 
parallel geometry in the detector description
setup; see Section <xref linkend="sect.ParaGeom" /> for how to define a parallel
geometry and register it to the run-manager.
</para>

<para>
The <literal>G4TransportationManager</literal> provides all the utilities to verify,
retrieve and activate the navigators associated to the various parallel
geometries defined.
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Navig.PhantomGeom">
<title>
Fast navigation in regular patterned geometries and phantoms
</title>

<para>
Since release 9.1 of Geant4, a specialised navigation algorithm has
been introduced to allow for optimal memory use and extremely efficient
navigation in geometries represented by a regular pattern of volumes
and particularly three-dimensional grids of boxes. A typical application
of this kind is the case of DICOM phantoms for medical physics studies.
</para>

<para>
The class <literal>G4RegularNavigation</literal> is used and automatically
activated when such geometries are defined. It is required to the user to
implement a parameterisation of the kind <literal>G4PhantomParameterisation</literal>
and place the parameterised volume containing it in a container volume, so that
all cells in the three-dimensional grid (<emphasis>voxels</emphasis>) completely
fill the container volume.
This way the location of a point inside a voxel can be done in a fast way,
transforming the position to the coordinate system of the container volume
and doing a simple calculation of the kind:

<informalexample>
<programlisting>
  copyNo_x = (localPoint.x()+fVoxelHalfX*fNoVoxelX)/(fVoxelHalfX*2.)
</programlisting>
</informalexample>

where <literal>fVoxelHalfX</literal> is the half dimension of the voxel along
<literal>X</literal> and <literal>fNoVoxelX</literal> is the number of voxels
in the <literal>X</literal> dimension.
Voxel <literal>0</literal> will be the one closest to the corner
<literal>(fVoxelHalfX*fNoVoxelX, fVoxelHalfY*fNoVoxelY, fVoxelHalfZ*fNoVoxelZ)</literal>.
</para>

<para>
Having the voxels filling completely the container volume allows to avoid
the lengthy computation of <literal>ComputeStep()</literal> and
<literal>ComputeSafety</literal> methods required in the traditional
navigation algorithm.
In this case, when a track is inside the parent volume, it has always to
be inside one of the voxels and it will be only necessary to calculate
the distance to the walls of the current voxel.
</para>

<!-- ******* Bridgehead ******* -->
<bridgehead renderas='sect4'>
Skipping borders of voxels with same material
</bridgehead>

<para>
Another speed optimisation can be provided by skipping the frontiers
of two voxels which the same material assigned, so that bigger steps
can be done. This optimisation may be not very useful when the number of
materials is very big (in which case the probability of having contiguous
voxels with same material is reduced), or when the physical step is small
compared to the voxel dimensions (very often the case of electrons).
The optimisation can be switched off in such cases, by invoking the
following method with argument <literal>skip = 0</literal>:

<informalexample>
<programlisting>
  G4RegularParameterisation::SetSkipEqualMaterials( G4bool skip );
</programlisting>
</informalexample>
</para>

<!-- ******* Bridgehead ******* -->
<bridgehead renderas='sect4'>
Example
</bridgehead>

<para>
To use the specialised navigation, it is required to first create an object
of type  <literal>G4PhantomParameterisation</literal>:

<informalexample>
<programlisting>
  G4PhantomParameterisation* param = new G4PhantomParameterisation();
</programlisting>
</informalexample>

Then, fill it with the all the necessary data:

<informalexample>
<programlisting>
  // Voxel dimensions in the three dimensions
  //
  G4double halfX = ...;
  G4double halfY = ...;
  G4double halfZ = ...;
  param-&gt;SetVoxelDimensions( halfX, halfY, halfZ );

  // Number of voxels in the three dimensions
  //
  G4int nVoxelX = ...;
  G4int nVoxelY = ...;
  G4int nVoxelZ = ...;
  param-&gt;SetNoVoxel( nVoxelX, nVoxelY, nVoxelZ );

  // Vector of materials of the voxels
  //
  std::vector &lt; G4Material* &gt; theMaterials;
  theMaterials.push_back( new G4Material( ...
  theMaterials.push_back( new G4Material( ...
  param-&gt;SetMaterials( theMaterials );

  // List of material indices
  // For each voxel it is a number that correspond to the index of its
  // material in the vector of materials defined above;
  //
  size_t* mateIDs = new size_t[nVoxelX*nVoxelY*nVoxelZ];
  mateIDs[0] = n0;
  mateIDs[1] = n1;
  ...
  param-&gt;SetMaterialIndices( mateIDs );
</programlisting>
</informalexample>

Then, define the volume that contains all the voxels:

<informalexample>
<programlisting>
  G4Box* cont_solid = new G4Box("PhantomContainer",nVoxelX*halfX.,nVoxelY*halfY.,nVoxelZ*halfZ);
  G4LogicalVolume* cont_logic = 
    new G4LogicalVolume( cont_solid, 
			 matePatient,        // material is not relevant here...
			 "PhantomContainer", 
			 0, 0, 0 );
  G4VPhysicalVolume * cont_phys = 
    new G4PVPlacement(rotm,                  // rotation
		      pos,                   // translation
		      cont_logic,            // logical volume
		      "PhantomContainer",    // name
		      world_logic,           // mother volume
		      false,                 // No op. bool.
		      1);                    // Copy number

</programlisting>
</informalexample>

The physical volume should be assigned as the container volume of the
parameterisation:

<informalexample>
<programlisting>
  param-&gt;BuildContainerSolid(cont_phys);

  // Assure that the voxels are completely filling the container volume
  //
  param-&gt;CheckVoxelsFillContainer( cont_solid-&gt;GetXHalfLength(), 
                                      cont_solid-&gt;GetyHalfLength(), 
                                      cont_solid-&gt;GetzHalfLength() );

  // The parameterised volume which uses this parameterisation is placed
  // in the container logical volume
  //
  G4PVParameterised * patient_phys =
    new G4PVParameterised("Patient",               // name
                          patient_logic,           // logical volume
                          cont_logic,              // mother volume
			  kXAxis,                  // optimisation hint
                          nVoxelX*nVoxelY*nVoxelZ, // number of voxels
                          param);                  // parameterisation

  // Indicate that this physical volume is having a regular structure
  //
  patient_phys-&gt;SetRegularStructureId(1);
</programlisting>
</informalexample>
</para>

An example showing the application of the optimised navigation algorithm
for phantoms geometries is available in
<literal>examples/extended/medical/DICOM</literal>. It implements a real
application for reading <literal>DICOM</literal> images and convert them to
Geant4 geometries with defined materials and densities, allowing for
different implementation solutions to be chosen (non optimised, classical
3D optimisation, nested parameterisations and use of
<literal>G4PhantomParameterisation</literal>).

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Navig.RunTime">
<title>
Run-time commands
</title>

<para>
When running in <emphasis>verbose</emphasis> mode (i.e. the default,
<literal>G4VERBOSE</literal> set while installing the Geant4 kernel
libraries), the navigator provides a few commands to control its
behavior. It is possible to select different verbosity levels (up
to 5), with the command:

<informalexample>
<programlisting>
  geometry/navigator/verbose [verbose_level]
</programlisting>
</informalexample>

or to force the navigator to run in <emphasis>check</emphasis> mode:

<informalexample>
<programlisting>
  geometry/navigator/check_mode [true/false]
</programlisting>
</informalexample>
</para>

<para>
The latter will force more strict and less tolerant checks in
step/safety computation to verify the correctness of the solids'
response in the geometry.
</para>

<para>
By combining <emphasis>check_mode</emphasis> with verbosity level-1, additional
verbosity checks on the response from the solids can be activated.
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Tolerance">
<title>
Setting Geometry Tolerance to be relative
</title>

<para>
The tolerance value defining the accuracy of tracking on the surfaces
is by default set to a reasonably small value of <emphasis>10E-9 mm</emphasis>.
Such accuracy may be however redundant for use on simulation of detectors
of big size or macroscopic dimensions. Since release 9.0, it is possible to
specify the surface tolerance to be relative to the extent of the world volume
defined for containing the geometry setup.
</para>

<para>
The class <literal>G4GeometryManager</literal> can be used to activate
the computation of the surface tolerance to be relative to the geometry
setup which has been defined. It can be done this way:

<informalexample>
<programlisting>
  G4GeometryManager::GetInstance()->SetWorldMaximumExtent(WorldExtent);
</programlisting>
</informalexample>

where, <literal>WorldExtent</literal> is the actual maximum extent of the
world volume used for placing the whole geometry setup.
</para>

<para>
Such call to <literal>G4GeometryManager</literal> must be done
<emphasis role="bold">before</emphasis> defining any geometrical component of
the setup (solid shape or volume), and can be done only
<emphasis role="bold">once</emphasis> !
</para>

<para>
The class <literal>G4GeometryTolerance</literal> is to be used for retrieving the
actual values defined for tolerances, surface (Cartesian), angular or radial
respectively:

<informalexample>
<programlisting>
  G4GeometryTolerance::GetInstance()->GetSurfaceTolerance();
  G4GeometryTolerance::GetInstance()->GetAngularTolerance();
  G4GeometryTolerance::GetInstance()->GetRadialTolerance();
</programlisting>
</informalexample>

</para>

</sect3>

</sect2>
