revise/expand/clarify comments about 3-phase algorithm for setting

up ghost-zone data


git-svn-id: http://svn.einsteintoolkit.org/cactus/EinsteinAnalysis/AHFinderDirect/trunk@84 f88db872-0e4f-0410-b76b-b9085cfa78c5

1 files changed, 108 insertions, 82 deletions

diff --git a/src/patch/patch.hh b/src/patch/patch.hh
index c41e95b..5b5256c 100644
--- a/src/patch/patch.hh
+++ b/src/patch/patch.hh
@@ -34,7 +34,11 @@
 //
 
 //
-// We use 5 interrelated types of objects to handle patch boundaries:
+// Basically, we handle patch boundaries using the usual "ghost zone"
+// technique, interpolating values from neighboring patches as necessary.
+//
+// In more detail, we use 5 interrelated types of objects to handle
+// patch boundaries:
 //
 // A  patch_edge  object represents the basic geometry of a min/max
 // rho/sigma side of a patch, i.e. it provides which-side-am-I predicates,
@@ -48,13 +52,13 @@
 // base class, from which we derive two classes:
 // * A  symmetry_ghost_zone  object describes an patch border which
 //   is a (discrete) symmetry of spacetime, either mirror-image or
-//   periodic.  Such an object knows how to fill in ghost-zone data
-//   from the "other side" of the symmetry.
+//   periodic.  Such an object knows how to fill in ghost-zone gridfn
+//   data from the "other side" of the symmetry.
 // * An  interpatch_ghost_zone  object describes a ghost zone which
 //   overlaps another patch.  Such an object knows how to get ghost
-//   zone data from the other patch.  More accurately, it gets the
-//   data from (the appropriate) one of the other patch's  patch_frontier
-//   objects.
+//   zone gridfn data from the other patch.  More accurately, it gets
+//   the data by asking (calling) the appropriate one of the other
+//   patch's  patch_frontier objects.
 // Every patch has (points to) 4  ghost_zone  objects, one for each of
 // the patch's sides.
 //
@@ -69,90 +73,112 @@
 //
 
 //
-// In order to make sure that ghost zone corners get set up properly,
-// we fill in gridfn data in ghost zones in 3 phases:
-// - symmetry-map all the non-corner points in all the symmetry borders
-//   of all patches
-// - interpatch-interpolate all the points in all the interpatch borders
-//   of all patches
-// - symmetry-map all the corner points in all the symmetry borders
-//   of all patches
+// There are some unobvious complications to how we set up ghost zone
+// gridfn data.  For example, notice that (for example) if we have octant
+// symmetry, then data near the +z axis with x and y both negative, comes
+// from the +z patch with *two* mirror-image symmetry reflections, i.e.
+// a single application of the mirror symmetry doesn't suffice.
 //
-
+// Because of this, and because we need data in the "corners" of the
+// ghost zones, we actually use a 3-phase algorithm to fill in data in
+// the ghost zones:
+// * We first fill in data at all the non-corner points in all the
+//   symmetry borders, by using the symmetries to get this data from
+//   patch nominal-grids.
+// * We then fill in data in all the interpatch borders in all the
+//   patches, by interpatch interpolating as described above.
+// * Finally, we fill in data at all the corner points in all the
+//   symmetry borders, by using the symmetries to get this data from
+//   patch nominal-grids or ghost zones.
 //
-// To illustrate these concepts, consider the following example, which
-// shows grid points in a single patch's coordinate system.  For purposes
+// For example, consider the +z patch in an octant patch system.
+// The following illustration is looking down the z axis; for purposes
 // of illuatration, we take the two patch coordinates to be (x,y).
 //
-//    <s+y>  <s+y>  <s+y>   s+y    s+y    s+y    s+y    s+y   <s+y>  <s+y>
-//    (0,9)  (1,9)  (2,9)  (3,9)  (4,9)  (5,9)  (6,9)  (7,9)  (8,9)  (9,9)
-//     s-x    s-x     #
-//                    #
-//    <s+y>  <s+y>  <s+y>   s+y    s+y    s+y    s+y    s+y   <s+y>  <s+y>
-//    (0,8)  (1,8)  (2,8)  (3,8)  (4,8)  (5,8)  (6,8)  (7,8)  (8,8)  (9,8)
-//     s-x    s-x     #
-//                    #
-//                    #
-//    (0,7)  (1,7)   2,7)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7)  (8,7)  (9,7)   
-//     s-x    s-x     #                                  |     i+x    i+x
-//                    #                                  |
-//                    #                                  |
-//    (0,6)  (1,6)  (2,6)  (3,6)  (4,6)  (5,6)  (6,6)  (7,6)  (8,6)  (9,6)
-//     s-x    s-x     #                                  |     i+x    i+x
-//                    #                                  |
-//                    #                                  |
-//    (0,5)  (1,5)  (2,5)  (3,5)  (4,5)  (5,5)  (6,5)  (7,5)  (8,5)  (9,5)
-//     s-x    s-x     #                                  |     i+x    i+x
-//                    #                                  |
-//                    #                                  |
-//    (0,4)  (1,4)  (2,4)  (3,4)  (4,4)  (5,4)  (6,4)  (7,4)  (8,4)  (9,4)
-//     s-x    s-x     #                                  |     i+x    i+x
-//                    #                                  |
-//                    #                                  |
-//    (0,3)  (1,3)  (2,3)  (3,3)  (4,3)  (5,3)  (6,3)  (7,3)  (8,3)  (9,3)
-//     s-x    s-x     #                                  |     i+x    i+x
-//                    #                                  |
-//                    #                                  |
-//    (0,2)##(1,2)##(2,2)##(3,2)##(4,2)##(5,2)##(6,2)##(7,2)##(8,2)##(9,2)
-//     s-x    s-x     #                                        i+x    i+x
-//                    #
-//    <s-y>  <s-y>   i-y    i-y    i-y    i-y    i-y    i-y    i-y
-//    (0,1)  (1,1)  (2,1)  (3,1)  (4,1)  (5,1)  (6,1)  (7,1)  (8,1)  (9,1)
-//    <s-x>  <s-x>   s-x    s-x    s-x    s-x    s-x    s-x    s-x    s-x
-//                    #
-//    <s-y>  <s-y>    #     i-y    i-y    i-y    i-y    i-y    i-y    i-y
-//    (0,0)  (1,0)  (2,0)  (3,0)  (4,0)  (5,0)  (6,0)  (7,0)  (8,0)  (9,0)
-//    <s-x>  <s-x>   s-x    s-x    s-x    s-x    s-x    s-x    s-x    s-x
+//                   #                                                   **
+//   <s-y>  <s-y>    #     i+y    i+y    i+y    i+y    i+y    i+y    i+y
+//  (-2,7) (-1,7)  (0,7)  (1,7)  (2,7)  (3,7)  (4,7)  (5,7)  (6,7)  (7,7)
+//    s-x    s-x     #                                              *i+x
+//                   #                                            **
+//   <s-y>  <s-y>    #     i+y    i+y    i+y    i+y    i+y    i+y
+//  (-2,6) (-1,6)  (0,6)  (1,6)  (2,6)  (3,6)  (4,6)  (5,6)  (6,6)  (7,6)
+//    s-x    s-x     #                                       *i+x    i+x
+//                   #                                     **
+//                   #                                   **
+//  (-2,5) (-1,5)   2,5)--(1,5)--(2,5)--(3,5)--(4,5)--(5,5)  (6,5)  (7,5)   
+//    s-x    s-x     #                                  |     i+x    i+x
+//                   #                                  |
+//                   #                                  |
+//  (-2,4) (-1,4)  (0,4)  (1,4)  (2,4)  (3,4)  (4,4)  (5,4)  (6,4)  (7,4)
+//    s-x    s-x     #                                  |     i+x    i+x
+//                   #                                  |
+//                   #                                  |
+//  (-2,3) (-1,3)  (0,3)  (1,3)  (2,3)  (3,3)  (4,3)  (5,3)  (6,3)  (7,3)
+//    s-x    s-x     #                                  |     i+x    i+x
+//                   #                                  |
+//                   #                                  |
+//  (-2,2) (-1,2)  (0,2)  (1,2)  (2,2)  (3,2)  (4,2)  (5,2)  (6,2)  (7,2)
+//    s-x    s-x     #                                  |     i+x    i+x
+//                   #                                  |
+//                   #                                  |
+//  (-2,1) (-1,1)  (0,1)  (1,1)  (2,1)  (3,1)  (4,1)  (5,1)  (6,1)  (7,1)
+//    s-x    s-x     #                                  |     i+x    i+x
+//                   #                                  |
+//                   #                                  |
+// #(-2,0)#(-1,0)##(0,0)##(1,0)##(2,0)##(3,0)##(4,0)##(5,0)##(6,0)##(7,0)##
+//    s-x    s-x     #                                        i+x    i+x
+//                   #
+//   <s-y>  <s-y>   s-y    s-y    s-y    s-y    s-y    s-y    s-y    s-y 
+//  (-2,-1)(-1,-1) (0,-1) (1,-1) (2,-1) (3,-1) (4,-1) (5,-1) (6,-1) (7,1)
+//   <s-x>  <s-x>   s-x    s-x    s-x    s-x    s-x    s-x    s-x    s-x
+//                   #
+//   <s-y>  <s-y>   s-y    s-y    s-y    s-y    s-y    s-y    s-y    s-y 
+//  (-2,-2)(-1,-2) (0,-2) (1,-2) (2,-2) (3,-2) (4,-2) (5,-2) (6,-2) (7,0)
+//   <s-x>  <s-x>   s-x    s-x    s-x    s-x    s-x    s-x    s-x    s-x
+//                   #
 //
 // For this example,
-// - The nominal patch is 3 <= x,y <= 7; its boundary lines are shown
-//   with single lines --- and | .
-// - The full grid patch is 1 <= x,y <= 9.
-// - There are mirror-symmetry boundaries at x=3 and y=3; these are
-//   shown with ### lines
-// - Points marked with an "s-x" below or an "m+y" above are computed
-//   via mirroring across the x=3 or y=3 symmetry boundaries respectively.
-// - The +x frontier is ([56],[3456789]), and the -y frontier is
-//   ([1234567],[45]).  Note that in both cases the frontier includes
-//   the points symmetry-imaged on the adjacent edges, since these will
-//   already have been done by the time interpatch interpolation uses
-//   data from the frontier (see the 3-pass algorithm below).  There
-//   are no -x or +y frontiers, since no interpolation is needed across
-//   those boundaries.
-// - The +x border is that set of points marked with an "i+x" below;
-//   the -y border is that set of points marked with an "i-y" above.
-// - Points marked with an "i+x" below or an "i-y" below are computed
-//   via interpatch interpolation from the appropriate other patch, as
-//   described by this patch's +x or -y  interpatch_patch_bndry  object
-//   respectively.
-// - The diagonal ** line shows the boundary between the -y and +x borders.
-// - Points marked with an "<m-x>" below or an "<m-y>" above are
-//   computed by mirroring across the x=3 or y=3 boundary respectively,
-//   but only *after* the previous mirror imaging and interpatch
-//   interpolation has been done.
+// * The xz plane and yz plane are marked with ### lines
+// * The nominal +z patch is ([0,5],[0,5]), i.e. 0 <= x,y <= 5; its
+//   boundary lines are shown with single lines --- and | .
+// * The +z patch's ghost zones are
+//	-x: ([-2,-1],[-2, 7])
+//	+x: ([ 6, 7],[-2, 7])
+//	-y: ([-2, 7],[-2,-1])
+//	+y: ([-2, 7],[ 6, 7])
+// * Points marked with an "s-x" below or an "s-y" above are computed via
+//   mirroring across the -x boundary (yz plane) or -y boundary (xz plane)
+//   respectively, as described by the +z patch's -x or -y symmetry_ghost_zone
+//   object respectively.  This is done in phase 1 of our 3-phase algorithm.
+// * The +z patch's frontiers are
+//	+x: ([ 3,4],[-2,7])
+//	+y: ([-2,7],[ 3,4])
+//   Note that in both cases the frontier includes the points computed
+//   by symmetry (in phase 1 of our 3-phase algorithm) on the adjacent
+//   edges! There are no -x or -y frontiers, since no interpolation is
+//   needed across those boundaries of this patch.
+// * Ghost-zone points marked with an "i+x" below or an "i+y" below are
+//   computed via interpatch interpolation from the appropriate other patch,
+//   as described by the +z patch's +x or +y  interpatch_ghost_zone  object
+//   respectively.  This is done in phase 2 of our 3-phase algorithm.
+// * The diagonal ** line shows the boundary between the +x and +y borders;
+//   points there may be interpolated via either of the two possible
+//    interpatch_ghost_zone  objects.
+//	[At present we require all points in a given ghost zone
+//	to be interpolated from the same neighboring patch and
+//	 patch_frontier  object, so must arbitrarily choose one
+//	of the two neighbors for the diagonal points.  In theory
+//	it would be better to take the average of the two neighbors,
+//	but in practice this doesn't matter for horizon finding.
+//	(For doing time evolution in my multipatch scheme it
+//	_does_ matter...)]
+// * Points marked with an "<s-x>" below or an "<s-y>" above are computed
+//   via mirroring across the -x boundary (yz plane) or -y boundary
+//   (xz plane) respectively, as described by the +z patch's -x or -y
+//    symmetry_ghost_zone  object respectively.  This is done in phase 3
+//   of our 3-phase algorithm.
 //
 
-
 //*****************************************************************************
 
 //