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


<!-- ******************* Section (Level#2) ****************** -->
<sect2 id="sect.Geom.Overlap">
<title>
Detecting Overlapping Volumes
</title>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Overlap.Prob">
<title>
The problem of overlapping volumes
</title>

<para>
Volumes are often positioned within other volumes with the
intent that one is fully contained within the other. If, however, a
volume extends beyond the boundaries of its mother volume, it is
defined as overlapping. It may also be intended that volumes are
positioned within the same mother volume such that they do not
intersect one another. When such volumes do intersect, they are
also defined as overlapping.
</para>

<para>
The problem of detecting overlaps between volumes is bounded by
the complexity of the solid model description. Hence it requires
the same mathematical sophistication which is needed to describe
the most complex solid topology, in general. However, a tunable
accuracy can be obtained by approximating the solids via first
and/or second order surfaces and checking their intersections.
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Overlap.BuiltIn">
<title>
Detecting overlaps: built-in kernel commands
</title>

<para>
In general, the most powerful clash detection algorithms are
provided by CAD systems, treating the intersection between the
solids in their topological form.
</para>

<para>
Geant4 provides some built-in run-time commands to activate
verification tests for the user-defined geometry:

<informalexample>
<programlisting>
     geometry/test/grid_test [recursion_flag]
     --&gt; to start verification of geometry for overlapping regions
         based on standard lines grid setup. If the "recursion_flag" is
         set to 'false' (the default), the check is limited to the first
         depth level of the geometry tree; otherwise it visits recursively
         the whole geometry tree. In the latter case, it may take a long
         time, depending on the complexity of the geometry.
     geometry/test/cylinder_test [recursion_flag]
     --&gt; shoots lines according to a cylindrical pattern. If the
         "recursion_flag" is set to 'false' (the default), the check is
         limited to the first depth level of the geometry tree; otherwise
         it visits recursively the whole geometry tree. In the latter case,
         it may take a long time, depending on the complexity of the geometry.
     geometry/test/line_test [recursion_flag]
     --&gt; shoots a line according to a specified direction and position
         defined by the user. If the "recursion_flag" is set to 'false'
         (the default), the check is limited to the first depth level of the
         geometry tree; otherwise it visits recursively the whole geometry 
         tree.
     geometry/test/position
     --&gt; to specify position for the line_test.
     geometry/test/direction
     --&gt; to specify direction for the line_test.
     geometry/test/grid_cells
     --&gt; to define the resolution of the lines in the grid test as number
         of cells, specifying them for each dimension, X, Y and Z.
         The new settings will be applied to the grid_test command.
     geometry/test/cylinder_geometry
     --&gt; to define the details of the cylinder geometry, by specifying:
             nPhi - number of lines per Phi
             nZ   - number of Z points
             nRho - number of Rho points
         The new settings will be applied to the cylinder_test command.
     geometry/test/cylinder_scaleZ
     --&gt; to define the resolution of the cylinder geometry, by specifying
         the fraction scale for points along Z.
         The new settings will be applied to the cylinder_test command.
     geometry/test/cylinder_scaleRho
     --&gt; to define the resolution of the cylinder geometry, by specifying
         the fraction scale for points along Rho.
         The new settings will be applied to the cylinder_test command.
     geometry/test/recursion_start
     --&gt; to set the initial level in the geometry tree for starting the
         recursion (default value being zero, i.e. the world volume).
         The new settings will then be applied to any recursive test.
     geometry/test/recursion_depth
     --&gt; to set the depth in the geometry tree for recursion, so that
         recursion will stop after having reached the specified depth (the
         default being the full depth of the geometry tree).
         The new settings will then be applied to any recursive test.
</programlisting>
</informalexample> 
</para>

<para>
To detect overlapping volumes, the built-in test uses the
intersection of solids with linear trajectories. For example,
consider <xref linkend="fig.Geom.Overlap_1" />:

<figure id="fig.Geom.Overlap_1">
<title>
  Different cases of placed volumes overlapping each other.
</title>
<mediaobject>
  <imageobject role="fo">
    <imagedata fileref="./AllResources/Detector/geometry.src/geomtest.jpg" 
               format="JPG" contentwidth="10.0cm" align="center" />
  </imageobject>
  <imageobject role="html">
    <imagedata fileref="./AllResources/Detector/geometry.src/geomtest.jpg" 
               format="JPG" align="center" />
  </imageobject>
</mediaobject>
</figure>
</para>

<para>
Here we have a line intersecting some physical volume (large,
black rectangle). Belonging to the volume are four daughters: A, B,
C, and D. Indicated by the dots are the intersections of the line
with the mother volume and the four daughters.
</para>

<para>
This example has two geometry errors. First, volume A sticks
outside its mother volume (this practice, sometimes used in
GEANT3.21, is not allowed in Geant4). This can be noticed because
the intersection point (leftmost magenta dot) lies outside the
mother volume, as defined by the space between the two black
dots.
</para>

<para>
The second error is that daughter volumes A and B overlap. This
is noticeable because one of the intersections with A (rightmost
magenta dot) is inside the volume B, as defined as the space
between the red dots. Alternatively, one of the intersections with
B (leftmost red dot) is inside the volume A, as defined as the
space between the magenta dots.
</para>

<para>
Each of these two types of errors is represented by a line
segment, which has a start point, an end point, and, a length.
Depending on the type of error, the points are most clearly
recognized in either the coordinate system of the volume, the
global coordinate system, or the coordinate system of the daughters
involved.
</para>

<para>
Also notice that certain errors will be missed unless a line is
supplied in precisely the correct path. Unfortunately, it is hard
to predict which lines are best at uncovering potential geometry
errors. Instead, the geometry testing code uses a grid of lines, in
the hope of at least uncovering gross geometry errors. More subtle
errors could easily be missed.
</para>

<para>
Another difficult issue is roundoff error. For example,
daughters C and D lie precisely next to each other. It is possible,
due to roundoff, that one of the intersections points will lie just
slightly inside the space of the other. In addition, a volume that
lies tightly up against the outside of its mother may have an
intersection point that just slightly lies outside the mother.
</para>

<para>
To avoid spurious errors caused by roundoff, a rather generous
tolerance of 0.1 micron is used by default. This tolerance can be
adjusted as needed by the application through the run-time
command:

<informalexample>
<programlisting>
   geometry/test/tolerance &lt;new-value&gt;
</programlisting>
</informalexample>
</para>

<para>
Finally, notice that no mention is made of the possible daughter
volumes of A, B, C, and D. To keep the code simple, only the
immediate daughters of a volume are checked at one pass. To test
these "granddaughter" volumes, the daughters A, B, C, and D each
have to be tested themselves in turn. To make this more automatic,
an optional recursive algorithm is included; it first tests a
target volume, then it loops over all daughter volumes and calls
itself.
</para>

<para>
Pay attention! For a complex geometry, checking the entire
volume hierarchy can be extremely time consuming.
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Overlap.AtConst">
<title>
Detecting overlaps at construction
</title>

<para>
Since release 8.0, the Geant4 geometry modeler provides the
ability to detect overlaps of placed volumes (normal placements or
parameterised) at the time of construction. This check is optional
and can be activated when instantiating a placement (see
<literal>G4PVPlacement</literal> constructor in 
<xref linkend="sect.Geom.PhysVol.PlaceSingle" />) or a parameterised
volume (see <literal>G4PVParameterised</literal> constructor in 
<xref linkend="sect.Geom.PhysVol.RepeatVol" />).
</para>

<para>
The positioning of that specific volume will be checked against all
volumes in the same hierarchy level and its mother volume.
Depending on the complexity of the geometry being checked, the
check may require considerable CPU time; it is therefore suggested
to use it only for debugging the geometry setup and to apply it
only to the part of the geometry setup which requires
debugging.
</para>

<para>
The classes <literal>G4PVPlacement</literal> and
<literal>G4PVParameterised</literal> also provide a method:

<informalexample>
<programlisting>
   G4bool CheckOverlaps(G4int res=1000, G4double tol=0., G4bool verbose=true)
</programlisting>
</informalexample>

which will force the check for the specified volume. The check
verifies if each placed or parameterised instance is overlapping
with other instances or with its mother volume. A default
resolution for the number of points to be generated and verified is
provided. The method returns <literal>true</literal> if an overlap
occurs. It is also possible to specify a "tolerance" by which overlaps
not exceeding such quantity will not be reported; by default, all
overlaps are reported.
</para>

<para>
<emphasis role="bold">Using the visualization driver: DAVID</emphasis>
</para>
<para>
The Geant4 visualization offers a powerful debugging tool for
detecting potential intersections of physical volumes. The Geant4
<ulink url="http://geant4.kek.jp/GEANT4/vis/DAWN/About_DAVID.html">
DAVID</ulink> visualization tool  can infact
automatically detect the overlaps between the volumes defined in
Geant4 and converted to a graphical representation for
visualization purposes. The accuracy of the graphical
representation can be tuned onto the exact geometrical description.
In the debugging, physical-volume surfaces are automatically
decomposed into 3D polygons, and intersections of the generated
polygons are investigated. If a polygon intersects with another
one, physical volumes which these polygons belong to are visualized
in color (red is the default). The <xref linkend="fig.Geom.Overlap_2" /> 
below is a sample visualization of a detector geometry with intersecting 
physical volumes highlighted:

<figure id="fig.Geom.Overlap_2">
<title>
  A geometry with overlapping volumes highlighted by DAVID.
</title>
<mediaobject>
  <imageobject role="fo">
    <imagedata fileref="./AllResources/Detector/geometry.src/DAVID_SAMPLE.jpg" 
               format="JPG" contentwidth="3.0cm" align="center" />
  </imageobject>
  <imageobject role="html">
    <imagedata fileref="./AllResources/Detector/geometry.src/DAVID_SAMPLE.jpg"
               format="JPG" align="center" />
  </imageobject>
</mediaobject>
</figure>
</para>

<para>
At present physical volumes made of the following solids are
able to be debugged: <literal>G4Box</literal>, <literal>G4Cons</literal>,
<literal>G4Para</literal>, <literal>G4Sphere</literal>, <literal>G4Trd</literal>,
<literal>G4Trap</literal>, <literal>G4Tubs</literal>. (Existence of other solids is
harmless.)
</para>

<para>
Visual debugging of physical-volume surfaces is performed with
the DAWNFILE driver defined in the visualization category and with
the two application packages, i.e. Fukui Renderer "DAWN" and a
visual intersection debugger "DAVID". 
<ulink url="http://geant4.kek.jp/GEANT4/vis/DAWN/About_DAWN.html">
DAWN</ulink> and 
<ulink url="http://geant4.kek.jp/GEANT4/vis/DAWN/About_DAVID.html">
DAVID</ulink> can be downloaded from the Web.
</para>

<para>
How to compile Geant4 with the DAWNFILE driver incorporated is
described in <xref linkend="sect.VisDrv" />.
</para>

<para>
If the DAWNFILE driver, DAWN and DAVID are all working well in
your host machine, the visual intersection debugging of
physical-volume surfaces can be performed as follows:
</para>

<para>
Run your Geant4 executable, invoke the DAWNFILE driver, and
execute visualization commands to visualize your detector
geometry:

<informalexample>
<programlisting>
     Idle&gt; /vis/open DAWNFILE
     .....(setting camera etc)...
     Idle&gt; /vis/drawVolume
     Idle&gt; /vis/viewer/update
</programlisting>
</informalexample>
</para>

<para>
Then a file "g4.prim", which describes the detector geometry, is
generated in the current directory and DAVID is invoked to read it.
(The description of the format of the file g4.prim can be found
from the 
<ulink url="http://geant4.kek.jp/GEANT4/vis/DAWN/G4PRIM_FORMAT_24/">
DAWN web site documentation</ulink>.)
</para>

<para>
If DAVID detects intersection of physical-volume surfaces, it
automatically invokes DAWN to visualize the detector geometry with
the intersected physical volumes highlighted (See the above sample
visualization).
</para>

<para>
If no intersection is detected, visualization is skipped and the
following message is displayed on the console:

<informalexample>
<programlisting>
     ------------------------------------------------------
     !!! Number of intersected volumes : 0 !!!
     !!! Congratulations ! \(^o^)/         !!!
     ------------------------------------------------------
</programlisting>
</informalexample>
</para>

<para>
If you always want to skip visualization, set an environmental
variable as follows beforehand:

<informalexample>
<programlisting>
     %  setenv DAVID_NO_VIEW  1
</programlisting>
</informalexample>
</para>

<para>
To control the precision associated to computation of
intersections (default precision is set to 9), it is possible to
use the environmental variable for the DAWNFILE graphics driver, as
follows:

<informalexample>
<programlisting>
     %  setenv G4DAWNFILE_PRECISION  10
</programlisting>
</informalexample>
</para>

<para>
If necessary, re-visualize the detector geometry with
intersected parts highlighted. The data are saved in a file
"g4david.prim" in the current directory. This file can be
re-visualized with DAWN as follows:

<informalexample>
<programlisting>
     % dawn g4david.prim
</programlisting>
</informalexample>
</para>

<para>
It is also helpful to convert the generated file g4david.prim
into a VRML-formatted file and perform interactive visualization of
it with your WWW browser. The file conversion tool
<literal>prim2wrml</literal> can be downloaded from the 
<ulink url="http://geant4.kek.jp/GEANT4/vis/DAWN/About_prim2vrml1.html">
DAWN web site download pages</ulink>.
</para>

<para>
For more details, see the 
<ulink url="http://geant4.kek.jp/GEANT4/vis/DAWN/About_DAVID.html">
document of DAVID</ulink> mentioned above.
</para>

</sect3>

<!-- ******************* Section (Level#3) ****************** -->
<sect3 id="sect.Geom.Overlap.OLAP">
<title>
Using the geometry debugging tool OLAP
</title>

<para>
<emphasis role="bold">OLAP</emphasis> is a tool developed in the CMS experiment 
at CERN to help in identifying ovelapping volumes in a detector geometry. It
is placed in the area for specific tools/examples, in
<literal>geant4/examples/extended/geometry</literal>. The technique consists
in shooting <literal>geantinos</literal> particles in one direction and the
opposite one, and verifying that the boundary crossings are the
same.
</para>

<para>
The tool can be used for any Geant4 geometry, provided that the
user geometry to be debugged is available as a subclass of
<literal>G4VUserDetectorConstruction</literal> and is used to construct the
<literal>OlapDetConstr</literal> class of the tool. A dummy class
<literal>RandomDetector</literal> is provided for this purpose in the tool
itself.
</para>

<para>
Run-time commands are provided by the tool to navigate in the
geometry tree. UNIX like navigation of the logical volume hierarchy
is provided by the <literal>/olap/cd</literal> command. The root of the
logical volume tree can be accessed by the character '/'. Any node
in the volume tree can be accessed by a '/' separated string of
regular expressions. If '/' is at the beginning of the string, the
tree hierarchy is transversed from the root, otherwise from the
currently chosen logical volume. Further the command <literal>/olap/goto
[regexp]</literal> can be used to jump to the first logical volume
matching the expression <literal>[regexp]</literal>. Every successful
navigation command (<literal>/olap/cd</literal>, <literal>olap/goto</literal>) results
in the construction of a <literal>NewWorld</literal>, the mother volume being
the argument of the command and the daughter volumes being the
direct daughters of the mother volume.
</para>

<para>
<literal>/olap/pwd</literal> always shows where in the full geometrical
hierarchy the current <literal>NewWorld</literal> and mother volume are
located.
</para>

<para>
For more detailed information, view the <literal>README</literal> file
provided with the tool.
</para>


</sect3>
</sect2>
