xref: /petsc/src/dm/impls/plex/plexgeometry.c (revision 28b400f66ebc7ae0049166a2294dfcd3df27e64b)

#include <petsc/private/dmpleximpl.h>   /*I      "petscdmplex.h"   I*/
#include <petsc/private/petscfeimpl.h>  /*I      "petscfe.h"       I*/
#include <petscblaslapack.h>
#include <petsctime.h>

/*@
  DMPlexFindVertices - Try to find DAG points based on their coordinates.

  Not Collective (provided DMGetCoordinatesLocalSetUp() has been called already)

  Input Parameters:
+ dm - The DMPlex object
. coordinates - The Vec of coordinates of the sought points
- eps - The tolerance or PETSC_DEFAULT

  Output Parameters:
. points - The IS of found DAG points or -1

  Level: intermediate

  Notes:
  The length of Vec coordinates must be npoints * dim where dim is the spatial dimension returned by DMGetCoordinateDim() and npoints is the number of sought points.

  The output IS is living on PETSC_COMM_SELF and its length is npoints.
  Each rank does the search independently.
  If this rank's local DMPlex portion contains the DAG point corresponding to the i-th tuple of coordinates, the i-th entry of the output IS is set to that DAG point, otherwise to -1.

  The output IS must be destroyed by user.

  The tolerance is interpreted as the maximum Euclidean (L2) distance of the sought point from the specified coordinates.

  Complexity of this function is currently O(mn) with m number of vertices to find and n number of vertices in the local mesh. This could probably be improved if needed.

.seealso: DMPlexCreate(), DMGetCoordinatesLocal()
@*/
PetscErrorCode DMPlexFindVertices(DM dm, Vec coordinates, PetscReal eps, IS *points)
{
  PetscInt          c, cdim, i, j, o, p, vStart, vEnd;
  PetscInt          npoints;
  const PetscScalar *coord;
  Vec               allCoordsVec;
  const PetscScalar *allCoords;
  PetscInt          *dagPoints;

  PetscFunctionBegin;
  if (eps < 0) eps = PETSC_SQRT_MACHINE_EPSILON;
  CHKERRQ(DMGetCoordinateDim(dm, &cdim));
  {
    PetscInt n;

    CHKERRQ(VecGetLocalSize(coordinates, &n));
    PetscCheckFalse(n % cdim,PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "Given coordinates Vec has local length %D not divisible by coordinate dimension %D of given DM", n, cdim);
    npoints = n / cdim;
  }
  CHKERRQ(DMGetCoordinatesLocal(dm, &allCoordsVec));
  CHKERRQ(VecGetArrayRead(allCoordsVec, &allCoords));
  CHKERRQ(VecGetArrayRead(coordinates, &coord));
  CHKERRQ(DMPlexGetDepthStratum(dm, 0, &vStart, &vEnd));
  if (PetscDefined(USE_DEBUG)) {
    /* check coordinate section is consistent with DM dimension */
    PetscSection      cs;
    PetscInt          ndof;

    CHKERRQ(DMGetCoordinateSection(dm, &cs));
    for (p = vStart; p < vEnd; p++) {
      CHKERRQ(PetscSectionGetDof(cs, p, &ndof));
      PetscCheckFalse(ndof != cdim,PETSC_COMM_SELF, PETSC_ERR_PLIB, "point %D: ndof = %D != %D = cdim", p, ndof, cdim);
    }
  }
  CHKERRQ(PetscMalloc1(npoints, &dagPoints));
  if (eps == 0.0) {
    for (i=0,j=0; i < npoints; i++,j+=cdim) {
      dagPoints[i] = -1;
      for (p = vStart,o=0; p < vEnd; p++,o+=cdim) {
        for (c = 0; c < cdim; c++) {
          if (coord[j+c] != allCoords[o+c]) break;
        }
        if (c == cdim) {
          dagPoints[i] = p;
          break;
        }
      }
    }
  } else {
    for (i=0,j=0; i < npoints; i++,j+=cdim) {
      PetscReal         norm;

      dagPoints[i] = -1;
      for (p = vStart,o=0; p < vEnd; p++,o+=cdim) {
        norm = 0.0;
        for (c = 0; c < cdim; c++) {
          norm += PetscRealPart(PetscSqr(coord[j+c] - allCoords[o+c]));
        }
        norm = PetscSqrtReal(norm);
        if (norm <= eps) {
          dagPoints[i] = p;
          break;
        }
      }
    }
  }
  CHKERRQ(VecRestoreArrayRead(allCoordsVec, &allCoords));
  CHKERRQ(VecRestoreArrayRead(coordinates, &coord));
  CHKERRQ(ISCreateGeneral(PETSC_COMM_SELF, npoints, dagPoints, PETSC_OWN_POINTER, points));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexGetLineIntersection_2D_Internal(const PetscReal segmentA[], const PetscReal segmentB[], PetscReal intersection[], PetscBool *hasIntersection)
{
  const PetscReal p0_x  = segmentA[0*2+0];
  const PetscReal p0_y  = segmentA[0*2+1];
  const PetscReal p1_x  = segmentA[1*2+0];
  const PetscReal p1_y  = segmentA[1*2+1];
  const PetscReal p2_x  = segmentB[0*2+0];
  const PetscReal p2_y  = segmentB[0*2+1];
  const PetscReal p3_x  = segmentB[1*2+0];
  const PetscReal p3_y  = segmentB[1*2+1];
  const PetscReal s1_x  = p1_x - p0_x;
  const PetscReal s1_y  = p1_y - p0_y;
  const PetscReal s2_x  = p3_x - p2_x;
  const PetscReal s2_y  = p3_y - p2_y;
  const PetscReal denom = (-s2_x * s1_y + s1_x * s2_y);

  PetscFunctionBegin;
  *hasIntersection = PETSC_FALSE;
  /* Non-parallel lines */
  if (denom != 0.0) {
    const PetscReal s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / denom;
    const PetscReal t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / denom;

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
      *hasIntersection = PETSC_TRUE;
      if (intersection) {
        intersection[0] = p0_x + (t * s1_x);
        intersection[1] = p0_y + (t * s1_y);
      }
    }
  }
  PetscFunctionReturn(0);
}

/* The plane is segmentB x segmentC: https://en.wikipedia.org/wiki/Line%E2%80%93plane_intersection */
static PetscErrorCode DMPlexGetLinePlaneIntersection_3D_Internal(const PetscReal segmentA[], const PetscReal segmentB[], const PetscReal segmentC[], PetscReal intersection[], PetscBool *hasIntersection)
{
  const PetscReal p0_x  = segmentA[0*3+0];
  const PetscReal p0_y  = segmentA[0*3+1];
  const PetscReal p0_z  = segmentA[0*3+2];
  const PetscReal p1_x  = segmentA[1*3+0];
  const PetscReal p1_y  = segmentA[1*3+1];
  const PetscReal p1_z  = segmentA[1*3+2];
  const PetscReal q0_x  = segmentB[0*3+0];
  const PetscReal q0_y  = segmentB[0*3+1];
  const PetscReal q0_z  = segmentB[0*3+2];
  const PetscReal q1_x  = segmentB[1*3+0];
  const PetscReal q1_y  = segmentB[1*3+1];
  const PetscReal q1_z  = segmentB[1*3+2];
  const PetscReal r0_x  = segmentC[0*3+0];
  const PetscReal r0_y  = segmentC[0*3+1];
  const PetscReal r0_z  = segmentC[0*3+2];
  const PetscReal r1_x  = segmentC[1*3+0];
  const PetscReal r1_y  = segmentC[1*3+1];
  const PetscReal r1_z  = segmentC[1*3+2];
  const PetscReal s0_x  = p1_x - p0_x;
  const PetscReal s0_y  = p1_y - p0_y;
  const PetscReal s0_z  = p1_z - p0_z;
  const PetscReal s1_x  = q1_x - q0_x;
  const PetscReal s1_y  = q1_y - q0_y;
  const PetscReal s1_z  = q1_z - q0_z;
  const PetscReal s2_x  = r1_x - r0_x;
  const PetscReal s2_y  = r1_y - r0_y;
  const PetscReal s2_z  = r1_z - r0_z;
  const PetscReal s3_x  = s1_y*s2_z - s1_z*s2_y; /* s1 x s2 */
  const PetscReal s3_y  = s1_z*s2_x - s1_x*s2_z;
  const PetscReal s3_z  = s1_x*s2_y - s1_y*s2_x;
  const PetscReal s4_x  = s0_y*s2_z - s0_z*s2_y; /* s0 x s2 */
  const PetscReal s4_y  = s0_z*s2_x - s0_x*s2_z;
  const PetscReal s4_z  = s0_x*s2_y - s0_y*s2_x;
  const PetscReal s5_x  = s1_y*s0_z - s1_z*s0_y; /* s1 x s0 */
  const PetscReal s5_y  = s1_z*s0_x - s1_x*s0_z;
  const PetscReal s5_z  = s1_x*s0_y - s1_y*s0_x;
  const PetscReal denom = -(s0_x*s3_x + s0_y*s3_y + s0_z*s3_z); /* -s0 . (s1 x s2) */

  PetscFunctionBegin;
  *hasIntersection = PETSC_FALSE;
  /* Line not parallel to plane */
  if (denom != 0.0) {
    const PetscReal t = (s3_x * (p0_x - q0_x) + s3_y * (p0_y - q0_y) + s3_z * (p0_z - q0_z)) / denom;
    const PetscReal u = (s4_x * (p0_x - q0_x) + s4_y * (p0_y - q0_y) + s4_z * (p0_z - q0_z)) / denom;
    const PetscReal v = (s5_x * (p0_x - q0_x) + s5_y * (p0_y - q0_y) + s5_z * (p0_z - q0_z)) / denom;

    if (t >= 0 && t <= 1 && u >= 0 && u <= 1 && v >= 0 && v <= 1) {
      *hasIntersection = PETSC_TRUE;
      if (intersection) {
        intersection[0] = p0_x + (t * s0_x);
        intersection[1] = p0_y + (t * s0_y);
        intersection[2] = p0_z + (t * s0_z);
      }
    }
  }
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexLocatePoint_Simplex_1D_Internal(DM dm, const PetscScalar point[], PetscInt c, PetscInt *cell)
{
  const PetscReal eps = PETSC_SQRT_MACHINE_EPSILON;
  const PetscReal x   = PetscRealPart(point[0]);
  PetscReal       v0, J, invJ, detJ;
  PetscReal       xi;

  PetscFunctionBegin;
  CHKERRQ(DMPlexComputeCellGeometryFEM(dm, c, NULL, &v0, &J, &invJ, &detJ));
  xi   = invJ*(x - v0);

  if ((xi >= -eps) && (xi <= 2.+eps)) *cell = c;
  else *cell = DMLOCATEPOINT_POINT_NOT_FOUND;
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexLocatePoint_Simplex_2D_Internal(DM dm, const PetscScalar point[], PetscInt c, PetscInt *cell)
{
  const PetscInt  embedDim = 2;
  const PetscReal eps      = PETSC_SQRT_MACHINE_EPSILON;
  PetscReal       x        = PetscRealPart(point[0]);
  PetscReal       y        = PetscRealPart(point[1]);
  PetscReal       v0[2], J[4], invJ[4], detJ;
  PetscReal       xi, eta;

  PetscFunctionBegin;
  CHKERRQ(DMPlexComputeCellGeometryFEM(dm, c, NULL, v0, J, invJ, &detJ));
  xi  = invJ[0*embedDim+0]*(x - v0[0]) + invJ[0*embedDim+1]*(y - v0[1]);
  eta = invJ[1*embedDim+0]*(x - v0[0]) + invJ[1*embedDim+1]*(y - v0[1]);

  if ((xi >= -eps) && (eta >= -eps) && (xi + eta <= 2.0+eps)) *cell = c;
  else *cell = DMLOCATEPOINT_POINT_NOT_FOUND;
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexClosestPoint_Simplex_2D_Internal(DM dm, const PetscScalar point[], PetscInt c, PetscReal cpoint[])
{
  const PetscInt  embedDim = 2;
  PetscReal       x        = PetscRealPart(point[0]);
  PetscReal       y        = PetscRealPart(point[1]);
  PetscReal       v0[2], J[4], invJ[4], detJ;
  PetscReal       xi, eta, r;

  PetscFunctionBegin;
  CHKERRQ(DMPlexComputeCellGeometryFEM(dm, c, NULL, v0, J, invJ, &detJ));
  xi  = invJ[0*embedDim+0]*(x - v0[0]) + invJ[0*embedDim+1]*(y - v0[1]);
  eta = invJ[1*embedDim+0]*(x - v0[0]) + invJ[1*embedDim+1]*(y - v0[1]);

  xi  = PetscMax(xi,  0.0);
  eta = PetscMax(eta, 0.0);
  if (xi + eta > 2.0) {
    r    = (xi + eta)/2.0;
    xi  /= r;
    eta /= r;
  }
  cpoint[0] = J[0*embedDim+0]*xi + J[0*embedDim+1]*eta + v0[0];
  cpoint[1] = J[1*embedDim+0]*xi + J[1*embedDim+1]*eta + v0[1];
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexLocatePoint_Quad_2D_Internal(DM dm, const PetscScalar point[], PetscInt c, PetscInt *cell)
{
  PetscSection       coordSection;
  Vec             coordsLocal;
  PetscScalar    *coords = NULL;
  const PetscInt  faces[8]  = {0, 1, 1, 2, 2, 3, 3, 0};
  PetscReal       x         = PetscRealPart(point[0]);
  PetscReal       y         = PetscRealPart(point[1]);
  PetscInt        crossings = 0, f;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordsLocal));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordsLocal, c, NULL, &coords));
  for (f = 0; f < 4; ++f) {
    PetscReal x_i   = PetscRealPart(coords[faces[2*f+0]*2+0]);
    PetscReal y_i   = PetscRealPart(coords[faces[2*f+0]*2+1]);
    PetscReal x_j   = PetscRealPart(coords[faces[2*f+1]*2+0]);
    PetscReal y_j   = PetscRealPart(coords[faces[2*f+1]*2+1]);
    PetscReal slope = (y_j - y_i) / (x_j - x_i);
    PetscBool cond1 = (x_i <= x) && (x < x_j) ? PETSC_TRUE : PETSC_FALSE;
    PetscBool cond2 = (x_j <= x) && (x < x_i) ? PETSC_TRUE : PETSC_FALSE;
    PetscBool above = (y < slope * (x - x_i) + y_i) ? PETSC_TRUE : PETSC_FALSE;
    if ((cond1 || cond2)  && above) ++crossings;
  }
  if (crossings % 2) *cell = c;
  else *cell = DMLOCATEPOINT_POINT_NOT_FOUND;
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordsLocal, c, NULL, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexLocatePoint_Simplex_3D_Internal(DM dm, const PetscScalar point[], PetscInt c, PetscInt *cell)
{
  const PetscInt  embedDim = 3;
  const PetscReal eps      = PETSC_SQRT_MACHINE_EPSILON;
  PetscReal       v0[3], J[9], invJ[9], detJ;
  PetscReal       x = PetscRealPart(point[0]);
  PetscReal       y = PetscRealPart(point[1]);
  PetscReal       z = PetscRealPart(point[2]);
  PetscReal       xi, eta, zeta;

  PetscFunctionBegin;
  CHKERRQ(DMPlexComputeCellGeometryFEM(dm, c, NULL, v0, J, invJ, &detJ));
  xi   = invJ[0*embedDim+0]*(x - v0[0]) + invJ[0*embedDim+1]*(y - v0[1]) + invJ[0*embedDim+2]*(z - v0[2]);
  eta  = invJ[1*embedDim+0]*(x - v0[0]) + invJ[1*embedDim+1]*(y - v0[1]) + invJ[1*embedDim+2]*(z - v0[2]);
  zeta = invJ[2*embedDim+0]*(x - v0[0]) + invJ[2*embedDim+1]*(y - v0[1]) + invJ[2*embedDim+2]*(z - v0[2]);

  if ((xi >= -eps) && (eta >= -eps) && (zeta >= -eps) && (xi + eta + zeta <= 2.0+eps)) *cell = c;
  else *cell = DMLOCATEPOINT_POINT_NOT_FOUND;
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexLocatePoint_General_3D_Internal(DM dm, const PetscScalar point[], PetscInt c, PetscInt *cell)
{
  PetscSection   coordSection;
  Vec            coordsLocal;
  PetscScalar   *coords = NULL;
  const PetscInt faces[24] = {0, 3, 2, 1,  5, 4, 7, 6,  3, 0, 4, 5,
                              1, 2, 6, 7,  3, 5, 6, 2,  0, 1, 7, 4};
  PetscBool      found = PETSC_TRUE;
  PetscInt       f;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordsLocal));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordsLocal, c, NULL, &coords));
  for (f = 0; f < 6; ++f) {
    /* Check the point is under plane */
    /*   Get face normal */
    PetscReal v_i[3];
    PetscReal v_j[3];
    PetscReal normal[3];
    PetscReal pp[3];
    PetscReal dot;

    v_i[0]    = PetscRealPart(coords[faces[f*4+3]*3+0]-coords[faces[f*4+0]*3+0]);
    v_i[1]    = PetscRealPart(coords[faces[f*4+3]*3+1]-coords[faces[f*4+0]*3+1]);
    v_i[2]    = PetscRealPart(coords[faces[f*4+3]*3+2]-coords[faces[f*4+0]*3+2]);
    v_j[0]    = PetscRealPart(coords[faces[f*4+1]*3+0]-coords[faces[f*4+0]*3+0]);
    v_j[1]    = PetscRealPart(coords[faces[f*4+1]*3+1]-coords[faces[f*4+0]*3+1]);
    v_j[2]    = PetscRealPart(coords[faces[f*4+1]*3+2]-coords[faces[f*4+0]*3+2]);
    normal[0] = v_i[1]*v_j[2] - v_i[2]*v_j[1];
    normal[1] = v_i[2]*v_j[0] - v_i[0]*v_j[2];
    normal[2] = v_i[0]*v_j[1] - v_i[1]*v_j[0];
    pp[0]     = PetscRealPart(coords[faces[f*4+0]*3+0] - point[0]);
    pp[1]     = PetscRealPart(coords[faces[f*4+0]*3+1] - point[1]);
    pp[2]     = PetscRealPart(coords[faces[f*4+0]*3+2] - point[2]);
    dot       = normal[0]*pp[0] + normal[1]*pp[1] + normal[2]*pp[2];

    /* Check that projected point is in face (2D location problem) */
    if (dot < 0.0) {
      found = PETSC_FALSE;
      break;
    }
  }
  if (found) *cell = c;
  else *cell = DMLOCATEPOINT_POINT_NOT_FOUND;
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordsLocal, c, NULL, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode PetscGridHashInitialize_Internal(PetscGridHash box, PetscInt dim, const PetscScalar point[])
{
  PetscInt d;

  PetscFunctionBegin;
  box->dim = dim;
  for (d = 0; d < dim; ++d) box->lower[d] = box->upper[d] = PetscRealPart(point[d]);
  PetscFunctionReturn(0);
}

PetscErrorCode PetscGridHashCreate(MPI_Comm comm, PetscInt dim, const PetscScalar point[], PetscGridHash *box)
{
  PetscFunctionBegin;
  CHKERRQ(PetscMalloc1(1, box));
  CHKERRQ(PetscGridHashInitialize_Internal(*box, dim, point));
  PetscFunctionReturn(0);
}

PetscErrorCode PetscGridHashEnlarge(PetscGridHash box, const PetscScalar point[])
{
  PetscInt d;

  PetscFunctionBegin;
  for (d = 0; d < box->dim; ++d) {
    box->lower[d] = PetscMin(box->lower[d], PetscRealPart(point[d]));
    box->upper[d] = PetscMax(box->upper[d], PetscRealPart(point[d]));
  }
  PetscFunctionReturn(0);
}

/*
  PetscGridHashSetGrid - Divide the grid into boxes

  Not collective

  Input Parameters:
+ box - The grid hash object
. n   - The number of boxes in each dimension, or PETSC_DETERMINE
- h   - The box size in each dimension, only used if n[d] == PETSC_DETERMINE

  Level: developer

.seealso: PetscGridHashCreate()
*/
PetscErrorCode PetscGridHashSetGrid(PetscGridHash box, const PetscInt n[], const PetscReal h[])
{
  PetscInt d;

  PetscFunctionBegin;
  for (d = 0; d < box->dim; ++d) {
    box->extent[d] = box->upper[d] - box->lower[d];
    if (n[d] == PETSC_DETERMINE) {
      box->h[d] = h[d];
      box->n[d] = PetscCeilReal(box->extent[d]/h[d]);
    } else {
      box->n[d] = n[d];
      box->h[d] = box->extent[d]/n[d];
    }
  }
  PetscFunctionReturn(0);
}

/*
  PetscGridHashGetEnclosingBox - Find the grid boxes containing each input point

  Not collective

  Input Parameters:
+ box       - The grid hash object
. numPoints - The number of input points
- points    - The input point coordinates

  Output Parameters:
+ dboxes    - An array of numPoints*dim integers expressing the enclosing box as (i_0, i_1, ..., i_dim)
- boxes     - An array of numPoints integers expressing the enclosing box as single number, or NULL

  Level: developer

.seealso: PetscGridHashCreate()
*/
PetscErrorCode PetscGridHashGetEnclosingBox(PetscGridHash box, PetscInt numPoints, const PetscScalar points[], PetscInt dboxes[], PetscInt boxes[])
{
  const PetscReal *lower = box->lower;
  const PetscReal *upper = box->upper;
  const PetscReal *h     = box->h;
  const PetscInt  *n     = box->n;
  const PetscInt   dim   = box->dim;
  PetscInt         d, p;

  PetscFunctionBegin;
  for (p = 0; p < numPoints; ++p) {
    for (d = 0; d < dim; ++d) {
      PetscInt dbox = PetscFloorReal((PetscRealPart(points[p*dim+d]) - lower[d])/h[d]);

      if (dbox == n[d] && PetscAbsReal(PetscRealPart(points[p*dim+d]) - upper[d]) < 1.0e-9) dbox = n[d]-1;
      if (dbox == -1   && PetscAbsReal(PetscRealPart(points[p*dim+d]) - lower[d]) < 1.0e-9) dbox = 0;
      PetscCheckFalse(dbox < 0 || dbox >= n[d],PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input point %d (%g, %g, %g) is outside of our bounding box",
                                             p, (double) PetscRealPart(points[p*dim+0]), dim > 1 ? (double) PetscRealPart(points[p*dim+1]) : 0.0, dim > 2 ? (double) PetscRealPart(points[p*dim+2]) : 0.0);
      dboxes[p*dim+d] = dbox;
    }
    if (boxes) for (d = dim-2, boxes[p] = dboxes[p*dim+dim-1]; d >= 0; --d) boxes[p] = boxes[p]*n[d] + dboxes[p*dim+d];
  }
  PetscFunctionReturn(0);
}

/*
 PetscGridHashGetEnclosingBoxQuery - Find the grid boxes containing each input point

 Not collective

  Input Parameters:
+ box       - The grid hash object
. numPoints - The number of input points
- points    - The input point coordinates

  Output Parameters:
+ dboxes    - An array of numPoints*dim integers expressing the enclosing box as (i_0, i_1, ..., i_dim)
. boxes     - An array of numPoints integers expressing the enclosing box as single number, or NULL
- found     - Flag indicating if point was located within a box

  Level: developer

.seealso: PetscGridHashGetEnclosingBox()
*/
PetscErrorCode PetscGridHashGetEnclosingBoxQuery(PetscGridHash box, PetscInt numPoints, const PetscScalar points[], PetscInt dboxes[], PetscInt boxes[],PetscBool *found)
{
  const PetscReal *lower = box->lower;
  const PetscReal *upper = box->upper;
  const PetscReal *h     = box->h;
  const PetscInt  *n     = box->n;
  const PetscInt   dim   = box->dim;
  PetscInt         d, p;

  PetscFunctionBegin;
  *found = PETSC_FALSE;
  for (p = 0; p < numPoints; ++p) {
    for (d = 0; d < dim; ++d) {
      PetscInt dbox = PetscFloorReal((PetscRealPart(points[p*dim+d]) - lower[d])/h[d]);

      if (dbox == n[d] && PetscAbsReal(PetscRealPart(points[p*dim+d]) - upper[d]) < 1.0e-9) dbox = n[d]-1;
      if (dbox < 0 || dbox >= n[d]) {
        PetscFunctionReturn(0);
      }
      dboxes[p*dim+d] = dbox;
    }
    if (boxes) for (d = dim-2, boxes[p] = dboxes[p*dim+dim-1]; d >= 0; --d) boxes[p] = boxes[p]*n[d] + dboxes[p*dim+d];
  }
  *found = PETSC_TRUE;
  PetscFunctionReturn(0);
}

PetscErrorCode PetscGridHashDestroy(PetscGridHash *box)
{
  PetscFunctionBegin;
  if (*box) {
    CHKERRQ(PetscSectionDestroy(&(*box)->cellSection));
    CHKERRQ(ISDestroy(&(*box)->cells));
    CHKERRQ(DMLabelDestroy(&(*box)->cellsSparse));
  }
  CHKERRQ(PetscFree(*box));
  PetscFunctionReturn(0);
}

PetscErrorCode DMPlexLocatePoint_Internal(DM dm, PetscInt dim, const PetscScalar point[], PetscInt cellStart, PetscInt *cell)
{
  DMPolytopeType ct;

  PetscFunctionBegin;
  CHKERRQ(DMPlexGetCellType(dm, cellStart, &ct));
  switch (ct) {
    case DM_POLYTOPE_SEGMENT:
    CHKERRQ(DMPlexLocatePoint_Simplex_1D_Internal(dm, point, cellStart, cell));break;
    case DM_POLYTOPE_TRIANGLE:
    CHKERRQ(DMPlexLocatePoint_Simplex_2D_Internal(dm, point, cellStart, cell));break;
    case DM_POLYTOPE_QUADRILATERAL:
    CHKERRQ(DMPlexLocatePoint_Quad_2D_Internal(dm, point, cellStart, cell));break;
    case DM_POLYTOPE_TETRAHEDRON:
    CHKERRQ(DMPlexLocatePoint_Simplex_3D_Internal(dm, point, cellStart, cell));break;
    case DM_POLYTOPE_HEXAHEDRON:
    CHKERRQ(DMPlexLocatePoint_General_3D_Internal(dm, point, cellStart, cell));break;
    default: SETERRQ(PetscObjectComm((PetscObject) dm), PETSC_ERR_ARG_OUTOFRANGE, "No point location for cell %D with type %s", cellStart, DMPolytopeTypes[ct]);
  }
  PetscFunctionReturn(0);
}

/*
  DMPlexClosestPoint_Internal - Returns the closest point in the cell to the given point
*/
PetscErrorCode DMPlexClosestPoint_Internal(DM dm, PetscInt dim, const PetscScalar point[], PetscInt cell, PetscReal cpoint[])
{
  DMPolytopeType ct;

  PetscFunctionBegin;
  CHKERRQ(DMPlexGetCellType(dm, cell, &ct));
  switch (ct) {
    case DM_POLYTOPE_TRIANGLE:
    CHKERRQ(DMPlexClosestPoint_Simplex_2D_Internal(dm, point, cell, cpoint));break;
#if 0
    case DM_POLYTOPE_QUADRILATERAL:
    CHKERRQ(DMPlexClosestPoint_General_2D_Internal(dm, point, cell, cpoint));break;
    case DM_POLYTOPE_TETRAHEDRON:
    CHKERRQ(DMPlexClosestPoint_Simplex_3D_Internal(dm, point, cell, cpoint));break;
    case DM_POLYTOPE_HEXAHEDRON:
    CHKERRQ(DMPlexClosestPoint_General_3D_Internal(dm, point, cell, cpoint));break;
#endif
    default: SETERRQ(PetscObjectComm((PetscObject) dm), PETSC_ERR_ARG_OUTOFRANGE, "No closest point location for cell %D with type %s", cell, DMPolytopeTypes[ct]);
  }
  PetscFunctionReturn(0);
}

/*
  DMPlexComputeGridHash_Internal - Create a grid hash structure covering the Plex

  Collective on dm

  Input Parameter:
. dm - The Plex

  Output Parameter:
. localBox - The grid hash object

  Level: developer

.seealso: PetscGridHashCreate(), PetscGridHashGetEnclosingBox()
*/
PetscErrorCode DMPlexComputeGridHash_Internal(DM dm, PetscGridHash *localBox)
{
  const PetscInt     debug = 0;
  MPI_Comm           comm;
  PetscGridHash      lbox;
  Vec                coordinates;
  PetscSection       coordSection;
  Vec                coordsLocal;
  const PetscScalar *coords;
  PetscScalar       *edgeCoords;
  PetscInt          *dboxes, *boxes;
  PetscInt           n[3] = {2, 2, 2};
  PetscInt           dim, N, maxConeSize, cStart, cEnd, c, eStart, eEnd, i;
  PetscBool          flg;

  PetscFunctionBegin;
  CHKERRQ(PetscObjectGetComm((PetscObject) dm, &comm));
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateDim(dm, &dim));
  CHKERRQ(DMPlexGetMaxSizes(dm, &maxConeSize, NULL));
  CHKERRQ(DMPlexGetSimplexOrBoxCells(dm, 0, &cStart, &cEnd));
  CHKERRQ(VecGetLocalSize(coordinates, &N));
  CHKERRQ(VecGetArrayRead(coordinates, &coords));
  CHKERRQ(PetscGridHashCreate(comm, dim, coords, &lbox));
  for (i = 0; i < N; i += dim) CHKERRQ(PetscGridHashEnlarge(lbox, &coords[i]));
  CHKERRQ(VecRestoreArrayRead(coordinates, &coords));
  c    = dim;
  CHKERRQ(PetscOptionsGetIntArray(NULL, ((PetscObject) dm)->prefix, "-dm_plex_hash_box_faces", n, &c, &flg));
  if (flg) {for (i = c; i < dim; ++i) n[i] = n[c-1];}
  else     {for (i = 0; i < dim; ++i) n[i] = PetscMax(2, PetscFloorReal(PetscPowReal((PetscReal) (cEnd - cStart), 1.0/dim) * 0.8));}
  CHKERRQ(PetscGridHashSetGrid(lbox, n, NULL));
#if 0
  /* Could define a custom reduction to merge these */
  CHKERRMPI(MPIU_Allreduce(lbox->lower, gbox->lower, 3, MPIU_REAL, MPI_MIN, comm));
  CHKERRMPI(MPIU_Allreduce(lbox->upper, gbox->upper, 3, MPIU_REAL, MPI_MAX, comm));
#endif
  /* Is there a reason to snap the local bounding box to a division of the global box? */
  /* Should we compute all overlaps of local boxes? We could do this with a rendevouz scheme partitioning the global box */
  /* Create label */
  CHKERRQ(DMPlexGetDepthStratum(dm, 1, &eStart, &eEnd));
  if (dim < 2) eStart = eEnd = -1;
  CHKERRQ(DMLabelCreate(PETSC_COMM_SELF, "cells", &lbox->cellsSparse));
  CHKERRQ(DMLabelCreateIndex(lbox->cellsSparse, cStart, cEnd));
  /* Compute boxes which overlap each cell: https://stackoverflow.com/questions/13790208/triangle-square-intersection-test-in-2d */
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordsLocal));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(PetscCalloc3(16 * dim, &dboxes, 16, &boxes, PetscPowInt(maxConeSize, dim) * dim, &edgeCoords));
  for (c = cStart; c < cEnd; ++c) {
    const PetscReal *h       = lbox->h;
    PetscScalar     *ccoords = NULL;
    PetscInt         csize   = 0;
    PetscInt        *closure = NULL;
    PetscInt         Ncl, cl, Ne = 0;
    PetscScalar      point[3];
    PetscInt         dlim[6], d, e, i, j, k;

    /* Get all edges in cell */
    CHKERRQ(DMPlexGetTransitiveClosure(dm, c, PETSC_TRUE, &Ncl, &closure));
    for (cl = 0; cl < Ncl*2; ++cl) {
      if ((closure[cl] >= eStart) && (closure[cl] < eEnd)) {
        PetscScalar *ecoords = &edgeCoords[Ne*dim*2];
        PetscInt     ecsize  = dim*2;

        CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordsLocal, closure[cl], &ecsize, &ecoords));
        PetscCheckFalse(ecsize != dim*2,PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "Got %D coords for edge, instead of %D", ecsize, dim*2);
        ++Ne;
      }
    }
    CHKERRQ(DMPlexRestoreTransitiveClosure(dm, c, PETSC_TRUE, &Ncl, &closure));
    /* Find boxes enclosing each vertex */
    CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordsLocal, c, &csize, &ccoords));
    CHKERRQ(PetscGridHashGetEnclosingBox(lbox, csize/dim, ccoords, dboxes, boxes));
    /* Mark cells containing the vertices */
    for (e = 0; e < csize/dim; ++e) {
      if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "Cell %D has vertex in box %D (%D, %D, %D)\n", c, boxes[e], dboxes[e*dim+0], dim > 1 ? dboxes[e*dim+1] : -1, dim > 2 ? dboxes[e*dim+2] : -1));
      CHKERRQ(DMLabelSetValue(lbox->cellsSparse, c, boxes[e]));
    }
    /* Get grid of boxes containing these */
    for (d = 0;   d < dim; ++d) {dlim[d*2+0] = dlim[d*2+1] = dboxes[d];}
    for (d = dim; d < 3;   ++d) {dlim[d*2+0] = dlim[d*2+1] = 0;}
    for (e = 1; e < dim+1; ++e) {
      for (d = 0; d < dim; ++d) {
        dlim[d*2+0] = PetscMin(dlim[d*2+0], dboxes[e*dim+d]);
        dlim[d*2+1] = PetscMax(dlim[d*2+1], dboxes[e*dim+d]);
      }
    }
    /* Check for intersection of box with cell */
    for (k = dlim[2*2+0], point[2] = lbox->lower[2] + k*h[2]; k <= dlim[2*2+1]; ++k, point[2] += h[2]) {
      for (j = dlim[1*2+0], point[1] = lbox->lower[1] + j*h[1]; j <= dlim[1*2+1]; ++j, point[1] += h[1]) {
        for (i = dlim[0*2+0], point[0] = lbox->lower[0] + i*h[0]; i <= dlim[0*2+1]; ++i, point[0] += h[0]) {
          const PetscInt box = (k*lbox->n[1] + j)*lbox->n[0] + i;
          PetscScalar    cpoint[3];
          PetscInt       cell, edge, ii, jj, kk;

          if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "Box %D: (%.2g, %.2g, %.2g) -- (%.2g, %.2g, %.2g)\n", box, point[0], point[1], point[2], point[0] + h[0], point[1] + h[1], point[2] + h[2]));
          /* Check whether cell contains any vertex of this subbox TODO vectorize this */
          for (kk = 0, cpoint[2] = point[2]; kk < (dim > 2 ? 2 : 1); ++kk, cpoint[2] += h[2]) {
            for (jj = 0, cpoint[1] = point[1]; jj < (dim > 1 ? 2 : 1); ++jj, cpoint[1] += h[1]) {
              for (ii = 0, cpoint[0] = point[0]; ii < 2; ++ii, cpoint[0] += h[0]) {

                CHKERRQ(DMPlexLocatePoint_Internal(dm, dim, cpoint, c, &cell));
                if (cell >= 0) {
                  if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "  Cell %D contains vertex (%.2g, %.2g, %.2g) of box %D\n", c, cpoint[0], cpoint[1], cpoint[2], box));
                  CHKERRQ(DMLabelSetValue(lbox->cellsSparse, c, box));
                  jj = kk = 2;
                  break;
                }
              }
            }
          }
          /* Check whether cell edge intersects any face of these subboxes TODO vectorize this */
          for (edge = 0; edge < Ne; ++edge) {
            PetscReal segA[6] = {0.,0.,0.,0.,0.,0.};
            PetscReal segB[6] = {0.,0.,0.,0.,0.,0.};
            PetscReal segC[6] = {0.,0.,0.,0.,0.,0.};

            PetscCheckFalse(dim > 3,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Unexpected dim %d > 3",dim);
            for (d = 0; d < dim*2; ++d) segA[d] = PetscRealPart(edgeCoords[edge*dim*2+d]);
            /* 1D: (x) -- (x+h)               0 -- 1
               2D: (x,   y)   -- (x,   y+h)   (0, 0) -- (0, 1)
                   (x+h, y)   -- (x+h, y+h)   (1, 0) -- (1, 1)
                   (x,   y)   -- (x+h, y)     (0, 0) -- (1, 0)
                   (x,   y+h) -- (x+h, y+h)   (0, 1) -- (1, 1)
               3D: (x,   y,   z)   -- (x,   y+h, z),   (x,   y,   z)   -- (x,   y,   z+h) (0, 0, 0) -- (0, 1, 0), (0, 0, 0) -- (0, 0, 1)
                   (x+h, y,   z)   -- (x+h, y+h, z),   (x+h, y,   z)   -- (x+h, y,   z+h) (1, 0, 0) -- (1, 1, 0), (1, 0, 0) -- (1, 0, 1)
                   (x,   y,   z)   -- (x+h, y,   z),   (x,   y,   z)   -- (x,   y,   z+h) (0, 0, 0) -- (1, 0, 0), (0, 0, 0) -- (0, 0, 1)
                   (x,   y+h, z)   -- (x+h, y+h, z),   (x,   y+h, z)   -- (x,   y+h, z+h) (0, 1, 0) -- (1, 1, 0), (0, 1, 0) -- (0, 1, 1)
                   (x,   y,   z)   -- (x+h, y,   z),   (x,   y,   z)   -- (x,   y+h, z)   (0, 0, 0) -- (1, 0, 0), (0, 0, 0) -- (0, 1, 0)
                   (x,   y,   z+h) -- (x+h, y,   z+h), (x,   y,   z+h) -- (x,   y+h, z+h) (0, 0, 1) -- (1, 0, 1), (0, 0, 1) -- (0, 1, 1)
             */
            /* Loop over faces with normal in direction d */
            for (d = 0; d < dim; ++d) {
              PetscBool intersects = PETSC_FALSE;
              PetscInt  e = (d+1)%dim;
              PetscInt  f = (d+2)%dim;

              /* There are two faces in each dimension */
              for (ii = 0; ii < 2; ++ii) {
                segB[d]     = PetscRealPart(point[d] + ii*h[d]);
                segB[dim+d] = PetscRealPart(point[d] + ii*h[d]);
                segC[d]     = PetscRealPart(point[d] + ii*h[d]);
                segC[dim+d] = PetscRealPart(point[d] + ii*h[d]);
                if (dim > 1) {
                  segB[e]     = PetscRealPart(point[e] + 0*h[e]);
                  segB[dim+e] = PetscRealPart(point[e] + 1*h[e]);
                  segC[e]     = PetscRealPart(point[e] + 0*h[e]);
                  segC[dim+e] = PetscRealPart(point[e] + 0*h[e]);
                }
                if (dim > 2) {
                  segB[f]     = PetscRealPart(point[f] + 0*h[f]);
                  segB[dim+f] = PetscRealPart(point[f] + 0*h[f]);
                  segC[f]     = PetscRealPart(point[f] + 0*h[f]);
                  segC[dim+f] = PetscRealPart(point[f] + 1*h[f]);
                }
                if (dim == 2) {
                  CHKERRQ(DMPlexGetLineIntersection_2D_Internal(segA, segB, NULL, &intersects));
                } else if (dim == 3) {
                  CHKERRQ(DMPlexGetLinePlaneIntersection_3D_Internal(segA, segB, segC, NULL, &intersects));
                }
                if (intersects) {
                  if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "  Cell %D edge %D (%.2g, %.2g, %.2g)--(%.2g, %.2g, %.2g) intersects box %D, face (%.2g, %.2g, %.2g)--(%.2g, %.2g, %.2g) (%.2g, %.2g, %.2g)--(%.2g, %.2g, %.2g)\n", c, edge, segA[0], segA[1], segA[2], segA[3], segA[4], segA[5], box, segB[0], segB[1], segB[2], segB[3], segB[4], segB[5], segC[0], segC[1], segC[2], segC[3], segC[4], segC[5]));
                  CHKERRQ(DMLabelSetValue(lbox->cellsSparse, c, box)); edge = Ne; break;
                }
              }
            }
          }
        }
      }
    }
    CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordsLocal, c, NULL, &ccoords));
  }
  CHKERRQ(PetscFree3(dboxes, boxes, edgeCoords));
  if (debug) CHKERRQ(DMLabelView(lbox->cellsSparse, PETSC_VIEWER_STDOUT_SELF));
  CHKERRQ(DMLabelConvertToSection(lbox->cellsSparse, &lbox->cellSection, &lbox->cells));
  CHKERRQ(DMLabelDestroy(&lbox->cellsSparse));
  *localBox = lbox;
  PetscFunctionReturn(0);
}

PetscErrorCode DMLocatePoints_Plex(DM dm, Vec v, DMPointLocationType ltype, PetscSF cellSF)
{
  const PetscInt  debug = 0;
  DM_Plex        *mesh = (DM_Plex *) dm->data;
  PetscBool       hash = mesh->useHashLocation, reuse = PETSC_FALSE;
  PetscInt        bs, numPoints, p, numFound, *found = NULL;
  PetscInt        dim, cStart, cEnd, numCells, c, d;
  const PetscInt *boxCells;
  PetscSFNode    *cells;
  PetscScalar    *a;
  PetscMPIInt     result;
  PetscLogDouble  t0,t1;
  PetscReal       gmin[3],gmax[3];
  PetscInt        terminating_query_type[] = { 0, 0, 0 };

  PetscFunctionBegin;
  CHKERRQ(PetscLogEventBegin(DMPLEX_LocatePoints,0,0,0,0));
  CHKERRQ(PetscTime(&t0));
  PetscCheckFalse(ltype == DM_POINTLOCATION_NEAREST && !hash,PetscObjectComm((PetscObject) dm), PETSC_ERR_SUP, "Nearest point location only supported with grid hashing. Use -dm_plex_hash_location to enable it.");
  CHKERRQ(DMGetCoordinateDim(dm, &dim));
  CHKERRQ(VecGetBlockSize(v, &bs));
  CHKERRMPI(MPI_Comm_compare(PetscObjectComm((PetscObject)cellSF),PETSC_COMM_SELF,&result));
  PetscCheckFalse(result != MPI_IDENT && result != MPI_CONGRUENT,PetscObjectComm((PetscObject)cellSF),PETSC_ERR_SUP, "Trying parallel point location: only local point location supported");
  PetscCheckFalse(bs != dim,PetscObjectComm((PetscObject)dm), PETSC_ERR_ARG_WRONG, "Block size for point vector %D must be the mesh coordinate dimension %D", bs, dim);
  CHKERRQ(DMPlexGetSimplexOrBoxCells(dm, 0, &cStart, &cEnd));
  CHKERRQ(VecGetLocalSize(v, &numPoints));
  CHKERRQ(VecGetArray(v, &a));
  numPoints /= bs;
  {
    const PetscSFNode *sf_cells;

    CHKERRQ(PetscSFGetGraph(cellSF,NULL,NULL,NULL,&sf_cells));
    if (sf_cells) {
      CHKERRQ(PetscInfo(dm,"[DMLocatePoints_Plex] Re-using existing StarForest node list\n"));
      cells = (PetscSFNode*)sf_cells;
      reuse = PETSC_TRUE;
    } else {
      CHKERRQ(PetscInfo(dm,"[DMLocatePoints_Plex] Creating and initializing new StarForest node list\n"));
      CHKERRQ(PetscMalloc1(numPoints, &cells));
      /* initialize cells if created */
      for (p=0; p<numPoints; p++) {
        cells[p].rank  = 0;
        cells[p].index = DMLOCATEPOINT_POINT_NOT_FOUND;
      }
    }
  }
  /* define domain bounding box */
  {
    Vec coorglobal;

    CHKERRQ(DMGetCoordinates(dm,&coorglobal));
    CHKERRQ(VecStrideMaxAll(coorglobal,NULL,gmax));
    CHKERRQ(VecStrideMinAll(coorglobal,NULL,gmin));
  }
  if (hash) {
    if (!mesh->lbox) {CHKERRQ(PetscInfo(dm, "Initializing grid hashing"));CHKERRQ(DMPlexComputeGridHash_Internal(dm, &mesh->lbox));}
    /* Designate the local box for each point */
    /* Send points to correct process */
    /* Search cells that lie in each subbox */
    /*   Should we bin points before doing search? */
    CHKERRQ(ISGetIndices(mesh->lbox->cells, &boxCells));
  }
  for (p = 0, numFound = 0; p < numPoints; ++p) {
    const PetscScalar *point = &a[p*bs];
    PetscInt           dbin[3] = {-1,-1,-1}, bin, cell = -1, cellOffset;
    PetscBool          point_outside_domain = PETSC_FALSE;

    /* check bounding box of domain */
    for (d=0; d<dim; d++) {
      if (PetscRealPart(point[d]) < gmin[d]) { point_outside_domain = PETSC_TRUE; break; }
      if (PetscRealPart(point[d]) > gmax[d]) { point_outside_domain = PETSC_TRUE; break; }
    }
    if (point_outside_domain) {
      cells[p].rank = 0;
      cells[p].index = DMLOCATEPOINT_POINT_NOT_FOUND;
      terminating_query_type[0]++;
      continue;
    }

    /* check initial values in cells[].index - abort early if found */
    if (cells[p].index != DMLOCATEPOINT_POINT_NOT_FOUND) {
      c = cells[p].index;
      cells[p].index = DMLOCATEPOINT_POINT_NOT_FOUND;
      CHKERRQ(DMPlexLocatePoint_Internal(dm, dim, point, c, &cell));
      if (cell >= 0) {
        cells[p].rank = 0;
        cells[p].index = cell;
        numFound++;
      }
    }
    if (cells[p].index != DMLOCATEPOINT_POINT_NOT_FOUND) {
      terminating_query_type[1]++;
      continue;
    }

    if (hash) {
      PetscBool found_box;

      if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "Checking point %D (%.2g, %.2g, %.2g)\n", p, point[0], point[1], point[2]));
      /* allow for case that point is outside box - abort early */
      CHKERRQ(PetscGridHashGetEnclosingBoxQuery(mesh->lbox, 1, point, dbin, &bin,&found_box));
      if (found_box) {
        if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "  Found point in box %D (%D, %D, %D)\n", bin, dbin[0], dbin[1], dbin[2]));
        /* TODO Lay an interface over this so we can switch between Section (dense) and Label (sparse) */
        CHKERRQ(PetscSectionGetDof(mesh->lbox->cellSection, bin, &numCells));
        CHKERRQ(PetscSectionGetOffset(mesh->lbox->cellSection, bin, &cellOffset));
        for (c = cellOffset; c < cellOffset + numCells; ++c) {
          if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "    Checking for point in cell %D\n", boxCells[c]));
          CHKERRQ(DMPlexLocatePoint_Internal(dm, dim, point, boxCells[c], &cell));
          if (cell >= 0) {
            if (debug) CHKERRQ(PetscPrintf(PETSC_COMM_SELF, "      FOUND in cell %D\n", cell));
            cells[p].rank = 0;
            cells[p].index = cell;
            numFound++;
            terminating_query_type[2]++;
            break;
          }
        }
      }
    } else {
      for (c = cStart; c < cEnd; ++c) {
        CHKERRQ(DMPlexLocatePoint_Internal(dm, dim, point, c, &cell));
        if (cell >= 0) {
          cells[p].rank = 0;
          cells[p].index = cell;
          numFound++;
          terminating_query_type[2]++;
          break;
        }
      }
    }
  }
  if (hash) CHKERRQ(ISRestoreIndices(mesh->lbox->cells, &boxCells));
  if (ltype == DM_POINTLOCATION_NEAREST && hash && numFound < numPoints) {
    for (p = 0; p < numPoints; p++) {
      const PetscScalar *point = &a[p*bs];
      PetscReal          cpoint[3], diff[3], best[3] = {PETSC_MAX_REAL, PETSC_MAX_REAL, PETSC_MAX_REAL}, dist, distMax = PETSC_MAX_REAL;
      PetscInt           dbin[3] = {-1,-1,-1}, bin, cellOffset, d, bestc = -1;

      if (cells[p].index < 0) {
        CHKERRQ(PetscGridHashGetEnclosingBox(mesh->lbox, 1, point, dbin, &bin));
        CHKERRQ(PetscSectionGetDof(mesh->lbox->cellSection, bin, &numCells));
        CHKERRQ(PetscSectionGetOffset(mesh->lbox->cellSection, bin, &cellOffset));
        for (c = cellOffset; c < cellOffset + numCells; ++c) {
          CHKERRQ(DMPlexClosestPoint_Internal(dm, dim, point, boxCells[c], cpoint));
          for (d = 0; d < dim; ++d) diff[d] = cpoint[d] - PetscRealPart(point[d]);
          dist = DMPlex_NormD_Internal(dim, diff);
          if (dist < distMax) {
            for (d = 0; d < dim; ++d) best[d] = cpoint[d];
            bestc = boxCells[c];
            distMax = dist;
          }
        }
        if (distMax < PETSC_MAX_REAL) {
          ++numFound;
          cells[p].rank  = 0;
          cells[p].index = bestc;
          for (d = 0; d < dim; ++d) a[p*bs+d] = best[d];
        }
      }
    }
  }
  /* This code is only be relevant when interfaced to parallel point location */
  /* Check for highest numbered proc that claims a point (do we care?) */
  if (ltype == DM_POINTLOCATION_REMOVE && numFound < numPoints) {
    CHKERRQ(PetscMalloc1(numFound,&found));
    for (p = 0, numFound = 0; p < numPoints; p++) {
      if (cells[p].rank >= 0 && cells[p].index >= 0) {
        if (numFound < p) {
          cells[numFound] = cells[p];
        }
        found[numFound++] = p;
      }
    }
  }
  CHKERRQ(VecRestoreArray(v, &a));
  if (!reuse) {
    CHKERRQ(PetscSFSetGraph(cellSF, cEnd - cStart, numFound, found, PETSC_OWN_POINTER, cells, PETSC_OWN_POINTER));
  }
  CHKERRQ(PetscTime(&t1));
  if (hash) {
    CHKERRQ(PetscInfo(dm,"[DMLocatePoints_Plex] terminating_query_type : %D [outside domain] : %D [inside initial cell] : %D [hash]\n",terminating_query_type[0],terminating_query_type[1],terminating_query_type[2]));
  } else {
    CHKERRQ(PetscInfo(dm,"[DMLocatePoints_Plex] terminating_query_type : %D [outside domain] : %D [inside initial cell] : %D [brute-force]\n",terminating_query_type[0],terminating_query_type[1],terminating_query_type[2]));
  }
  CHKERRQ(PetscInfo(dm,"[DMLocatePoints_Plex] npoints %D : time(rank0) %1.2e (sec): points/sec %1.4e\n",numPoints,t1-t0,(double)((double)numPoints/(t1-t0))));
  CHKERRQ(PetscLogEventEnd(DMPLEX_LocatePoints,0,0,0,0));
  PetscFunctionReturn(0);
}

/*@C
  DMPlexComputeProjection2Dto1D - Rewrite coordinates to be the 1D projection of the 2D coordinates

  Not collective

  Input/Output Parameter:
. coords - The coordinates of a segment, on output the new y-coordinate, and 0 for x

  Output Parameter:
. R - The rotation which accomplishes the projection

  Level: developer

.seealso: DMPlexComputeProjection3Dto1D(), DMPlexComputeProjection3Dto2D()
@*/
PetscErrorCode DMPlexComputeProjection2Dto1D(PetscScalar coords[], PetscReal R[])
{
  const PetscReal x = PetscRealPart(coords[2] - coords[0]);
  const PetscReal y = PetscRealPart(coords[3] - coords[1]);
  const PetscReal r = PetscSqrtReal(x*x + y*y), c = x/r, s = y/r;

  PetscFunctionBegin;
  R[0] = c; R[1] = -s;
  R[2] = s; R[3] =  c;
  coords[0] = 0.0;
  coords[1] = r;
  PetscFunctionReturn(0);
}

/*@C
  DMPlexComputeProjection3Dto1D - Rewrite coordinates to be the 1D projection of the 3D coordinates

  Not collective

  Input/Output Parameter:
. coords - The coordinates of a segment; on output, the new y-coordinate, and 0 for x and z

  Output Parameter:
. R - The rotation which accomplishes the projection

  Note: This uses the basis completion described by Frisvad in http://www.imm.dtu.dk/~jerf/papers/abstracts/onb.html, DOI:10.1080/2165347X.2012.689606

  Level: developer

.seealso: DMPlexComputeProjection2Dto1D(), DMPlexComputeProjection3Dto2D()
@*/
PetscErrorCode DMPlexComputeProjection3Dto1D(PetscScalar coords[], PetscReal R[])
{
  PetscReal      x    = PetscRealPart(coords[3] - coords[0]);
  PetscReal      y    = PetscRealPart(coords[4] - coords[1]);
  PetscReal      z    = PetscRealPart(coords[5] - coords[2]);
  PetscReal      r    = PetscSqrtReal(x*x + y*y + z*z);
  PetscReal      rinv = 1. / r;
  PetscFunctionBegin;

  x *= rinv; y *= rinv; z *= rinv;
  if (x > 0.) {
    PetscReal inv1pX   = 1./ (1. + x);

    R[0] = x; R[1] = -y;              R[2] = -z;
    R[3] = y; R[4] = 1. - y*y*inv1pX; R[5] =     -y*z*inv1pX;
    R[6] = z; R[7] =     -y*z*inv1pX; R[8] = 1. - z*z*inv1pX;
  }
  else {
    PetscReal inv1mX   = 1./ (1. - x);

    R[0] = x; R[1] = z;               R[2] = y;
    R[3] = y; R[4] =     -y*z*inv1mX; R[5] = 1. - y*y*inv1mX;
    R[6] = z; R[7] = 1. - z*z*inv1mX; R[8] =     -y*z*inv1mX;
  }
  coords[0] = 0.0;
  coords[1] = r;
  PetscFunctionReturn(0);
}

/*@
  DMPlexComputeProjection3Dto2D - Rewrite coordinates of 3 or more coplanar 3D points to a common 2D basis for the
    plane.  The normal is defined by positive orientation of the first 3 points.

  Not collective

  Input Parameter:
. coordSize - Length of coordinate array (3x number of points); must be at least 9 (3 points)

  Input/Output Parameter:
. coords - The interlaced coordinates of each coplanar 3D point; on output the first
           2*coordSize/3 entries contain interlaced 2D points, with the rest undefined

  Output Parameter:
. R - 3x3 row-major rotation matrix whose columns are the tangent basis [t1, t2, n].  Multiplying by R^T transforms from original frame to tangent frame.

  Level: developer

.seealso: DMPlexComputeProjection2Dto1D(), DMPlexComputeProjection3Dto1D()
@*/
PetscErrorCode DMPlexComputeProjection3Dto2D(PetscInt coordSize, PetscScalar coords[], PetscReal R[])
{
  PetscReal x1[3], x2[3], n[3], c[3], norm;
  const PetscInt dim = 3;
  PetscInt       d, p;

  PetscFunctionBegin;
  /* 0) Calculate normal vector */
  for (d = 0; d < dim; ++d) {
    x1[d] = PetscRealPart(coords[1*dim+d] - coords[0*dim+d]);
    x2[d] = PetscRealPart(coords[2*dim+d] - coords[0*dim+d]);
  }
  // n = x1 \otimes x2
  n[0] = x1[1]*x2[2] - x1[2]*x2[1];
  n[1] = x1[2]*x2[0] - x1[0]*x2[2];
  n[2] = x1[0]*x2[1] - x1[1]*x2[0];
  norm = PetscSqrtReal(n[0]*n[0] + n[1]*n[1] + n[2]*n[2]);
  for (d = 0; d < dim; d++) n[d] /= norm;
  norm = PetscSqrtReal(x1[0] * x1[0] + x1[1] * x1[1] + x1[2] * x1[2]);
  for (d = 0; d < dim; d++) x1[d] /= norm;
  // x2 = n \otimes x1
  x2[0] = n[1] * x1[2] - n[2] * x1[1];
  x2[1] = n[2] * x1[0] - n[0] * x1[2];
  x2[2] = n[0] * x1[1] - n[1] * x1[0];
  for (d=0; d<dim; d++) {
    R[d * dim + 0] = x1[d];
    R[d * dim + 1] = x2[d];
    R[d * dim + 2] = n[d];
    c[d] = PetscRealPart(coords[0*dim + d]);
  }
  for (p=0; p<coordSize/dim; p++) {
    PetscReal y[3];
    for (d=0; d<dim; d++) y[d] = PetscRealPart(coords[p*dim + d]) - c[d];
    for (d=0; d<2; d++) coords[p*2+d] = R[0*dim + d] * y[0] + R[1*dim + d] * y[1] + R[2*dim + d] * y[2];
  }
  PetscFunctionReturn(0);
}

PETSC_UNUSED
static inline void Volume_Triangle_Internal(PetscReal *vol, PetscReal coords[])
{
  /* Signed volume is 1/2 the determinant

   |  1  1  1 |
   | x0 x1 x2 |
   | y0 y1 y2 |

     but if x0,y0 is the origin, we have

   | x1 x2 |
   | y1 y2 |
  */
  const PetscReal x1 = coords[2] - coords[0], y1 = coords[3] - coords[1];
  const PetscReal x2 = coords[4] - coords[0], y2 = coords[5] - coords[1];
  PetscReal       M[4], detM;
  M[0] = x1; M[1] = x2;
  M[2] = y1; M[3] = y2;
  DMPlex_Det2D_Internal(&detM, M);
  *vol = 0.5*detM;
  (void)PetscLogFlops(5.0);
}

PETSC_UNUSED
static inline void Volume_Tetrahedron_Internal(PetscReal *vol, PetscReal coords[])
{
  /* Signed volume is 1/6th of the determinant

   |  1  1  1  1 |
   | x0 x1 x2 x3 |
   | y0 y1 y2 y3 |
   | z0 z1 z2 z3 |

     but if x0,y0,z0 is the origin, we have

   | x1 x2 x3 |
   | y1 y2 y3 |
   | z1 z2 z3 |
  */
  const PetscReal x1 = coords[3] - coords[0], y1 = coords[4]  - coords[1], z1 = coords[5]  - coords[2];
  const PetscReal x2 = coords[6] - coords[0], y2 = coords[7]  - coords[1], z2 = coords[8]  - coords[2];
  const PetscReal x3 = coords[9] - coords[0], y3 = coords[10] - coords[1], z3 = coords[11] - coords[2];
  const PetscReal onesixth = ((PetscReal)1./(PetscReal)6.);
  PetscReal       M[9], detM;
  M[0] = x1; M[1] = x2; M[2] = x3;
  M[3] = y1; M[4] = y2; M[5] = y3;
  M[6] = z1; M[7] = z2; M[8] = z3;
  DMPlex_Det3D_Internal(&detM, M);
  *vol = -onesixth*detM;
  (void)PetscLogFlops(10.0);
}

static inline void Volume_Tetrahedron_Origin_Internal(PetscReal *vol, PetscReal coords[])
{
  const PetscReal onesixth = ((PetscReal)1./(PetscReal)6.);
  DMPlex_Det3D_Internal(vol, coords);
  *vol *= -onesixth;
}

static PetscErrorCode DMPlexComputePointGeometry_Internal(DM dm, PetscInt e, PetscReal v0[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  const PetscScalar *coords;
  PetscInt       dim, d, off;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(PetscSectionGetDof(coordSection,e,&dim));
  if (!dim) PetscFunctionReturn(0);
  CHKERRQ(PetscSectionGetOffset(coordSection,e,&off));
  CHKERRQ(VecGetArrayRead(coordinates,&coords));
  if (v0) {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[off + d]);}
  CHKERRQ(VecRestoreArrayRead(coordinates,&coords));
  *detJ = 1.;
  if (J) {
    for (d = 0; d < dim * dim; d++) J[d] = 0.;
    for (d = 0; d < dim; d++) J[d * dim + d] = 1.;
    if (invJ) {
      for (d = 0; d < dim * dim; d++) invJ[d] = 0.;
      for (d = 0; d < dim; d++) invJ[d * dim + d] = 1.;
    }
  }
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeLineGeometry_Internal(DM dm, PetscInt e, PetscReal v0[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  PetscInt       numCoords, d, pStart, pEnd, numSelfCoords = 0;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(PetscSectionGetChart(coordSection,&pStart,&pEnd));
  if (e >= pStart && e < pEnd) CHKERRQ(PetscSectionGetDof(coordSection,e,&numSelfCoords));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, e, &numCoords, &coords));
  numCoords = numSelfCoords ? numSelfCoords : numCoords;
  PetscCheckFalse(invJ && !J,PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "In order to compute invJ, J must not be NULL");
  *detJ = 0.0;
  if (numCoords == 6) {
    const PetscInt dim = 3;
    PetscReal      R[9], J0;

    if (v0)   {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[d]);}
    CHKERRQ(DMPlexComputeProjection3Dto1D(coords, R));
    if (J)    {
      J0   = 0.5*PetscRealPart(coords[1]);
      J[0] = R[0]*J0; J[1] = R[1]; J[2] = R[2];
      J[3] = R[3]*J0; J[4] = R[4]; J[5] = R[5];
      J[6] = R[6]*J0; J[7] = R[7]; J[8] = R[8];
      DMPlex_Det3D_Internal(detJ, J);
      if (invJ) {DMPlex_Invert2D_Internal(invJ, J, *detJ);}
    }
  } else if (numCoords == 4) {
    const PetscInt dim = 2;
    PetscReal      R[4], J0;

    if (v0)   {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[d]);}
    CHKERRQ(DMPlexComputeProjection2Dto1D(coords, R));
    if (J)    {
      J0   = 0.5*PetscRealPart(coords[1]);
      J[0] = R[0]*J0; J[1] = R[1];
      J[2] = R[2]*J0; J[3] = R[3];
      DMPlex_Det2D_Internal(detJ, J);
      if (invJ) {DMPlex_Invert2D_Internal(invJ, J, *detJ);}
    }
  } else if (numCoords == 2) {
    const PetscInt dim = 1;

    if (v0)   {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[d]);}
    if (J)    {
      J[0]  = 0.5*(PetscRealPart(coords[1]) - PetscRealPart(coords[0]));
      *detJ = J[0];
      CHKERRQ(PetscLogFlops(2.0));
      if (invJ) {invJ[0] = 1.0/J[0]; CHKERRQ(PetscLogFlops(1.0));}
    }
  } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "The number of coordinates for this segment is %D != 2", numCoords);
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, e, &numCoords, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeTriangleGeometry_Internal(DM dm, PetscInt e, PetscReal v0[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  PetscInt       numCoords, numSelfCoords = 0, d, f, g, pStart, pEnd;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(PetscSectionGetChart(coordSection,&pStart,&pEnd));
  if (e >= pStart && e < pEnd) CHKERRQ(PetscSectionGetDof(coordSection,e,&numSelfCoords));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, e, &numCoords, &coords));
  numCoords = numSelfCoords ? numSelfCoords : numCoords;
  *detJ = 0.0;
  if (numCoords == 9) {
    const PetscInt dim = 3;
    PetscReal      R[9], J0[9] = {1.0,0.0,0.0,0.0,1.0,0.0,0.0,0.0,1.0};

    if (v0)   {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[d]);}
    CHKERRQ(DMPlexComputeProjection3Dto2D(numCoords, coords, R));
    if (J)    {
      const PetscInt pdim = 2;

      for (d = 0; d < pdim; d++) {
        for (f = 0; f < pdim; f++) {
          J0[d*dim+f] = 0.5*(PetscRealPart(coords[(f+1)*pdim+d]) - PetscRealPart(coords[0*pdim+d]));
        }
      }
      CHKERRQ(PetscLogFlops(8.0));
      DMPlex_Det3D_Internal(detJ, J0);
      for (d = 0; d < dim; d++) {
        for (f = 0; f < dim; f++) {
          J[d*dim+f] = 0.0;
          for (g = 0; g < dim; g++) {
            J[d*dim+f] += R[d*dim+g]*J0[g*dim+f];
          }
        }
      }
      CHKERRQ(PetscLogFlops(18.0));
    }
    if (invJ) {DMPlex_Invert3D_Internal(invJ, J, *detJ);}
  } else if (numCoords == 6) {
    const PetscInt dim = 2;

    if (v0)   {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[d]);}
    if (J)    {
      for (d = 0; d < dim; d++) {
        for (f = 0; f < dim; f++) {
          J[d*dim+f] = 0.5*(PetscRealPart(coords[(f+1)*dim+d]) - PetscRealPart(coords[0*dim+d]));
        }
      }
      CHKERRQ(PetscLogFlops(8.0));
      DMPlex_Det2D_Internal(detJ, J);
    }
    if (invJ) {DMPlex_Invert2D_Internal(invJ, J, *detJ);}
  } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "The number of coordinates for this triangle is %D != 6 or 9", numCoords);
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, e, &numCoords, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeRectangleGeometry_Internal(DM dm, PetscInt e, PetscBool isTensor, PetscInt Nq, const PetscReal points[], PetscReal v[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  PetscInt       numCoords, numSelfCoords = 0, d, f, g, pStart, pEnd;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(PetscSectionGetChart(coordSection,&pStart,&pEnd));
  if (e >= pStart && e < pEnd) CHKERRQ(PetscSectionGetDof(coordSection,e,&numSelfCoords));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, e, &numCoords, &coords));
  numCoords = numSelfCoords ? numSelfCoords : numCoords;
  if (!Nq) {
    PetscInt vorder[4] = {0, 1, 2, 3};

    if (isTensor) {vorder[2] = 3; vorder[3] = 2;}
    *detJ = 0.0;
    if (numCoords == 12) {
      const PetscInt dim = 3;
      PetscReal      R[9], J0[9] = {1.0,0.0,0.0,0.0,1.0,0.0,0.0,0.0,1.0};

      if (v)   {for (d = 0; d < dim; d++) v[d] = PetscRealPart(coords[d]);}
      CHKERRQ(DMPlexComputeProjection3Dto2D(numCoords, coords, R));
      if (J)    {
        const PetscInt pdim = 2;

        for (d = 0; d < pdim; d++) {
          J0[d*dim+0] = 0.5*(PetscRealPart(coords[vorder[1]*pdim+d]) - PetscRealPart(coords[vorder[0]*pdim+d]));
          J0[d*dim+1] = 0.5*(PetscRealPart(coords[vorder[2]*pdim+d]) - PetscRealPart(coords[vorder[1]*pdim+d]));
        }
        CHKERRQ(PetscLogFlops(8.0));
        DMPlex_Det3D_Internal(detJ, J0);
        for (d = 0; d < dim; d++) {
          for (f = 0; f < dim; f++) {
            J[d*dim+f] = 0.0;
            for (g = 0; g < dim; g++) {
              J[d*dim+f] += R[d*dim+g]*J0[g*dim+f];
            }
          }
        }
        CHKERRQ(PetscLogFlops(18.0));
      }
      if (invJ) {DMPlex_Invert3D_Internal(invJ, J, *detJ);}
    } else if (numCoords == 8) {
      const PetscInt dim = 2;

      if (v)   {for (d = 0; d < dim; d++) v[d] = PetscRealPart(coords[d]);}
      if (J)    {
        for (d = 0; d < dim; d++) {
          J[d*dim+0] = 0.5*(PetscRealPart(coords[vorder[1]*dim+d]) - PetscRealPart(coords[vorder[0]*dim+d]));
          J[d*dim+1] = 0.5*(PetscRealPart(coords[vorder[3]*dim+d]) - PetscRealPart(coords[vorder[0]*dim+d]));
        }
        CHKERRQ(PetscLogFlops(8.0));
        DMPlex_Det2D_Internal(detJ, J);
      }
      if (invJ) {DMPlex_Invert2D_Internal(invJ, J, *detJ);}
    } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "The number of coordinates for this quadrilateral is %D != 8 or 12", numCoords);
  } else {
    const PetscInt Nv = 4;
    const PetscInt dimR = 2;
    PetscInt  zToPlex[4] = {0, 1, 3, 2};
    PetscReal zOrder[12];
    PetscReal zCoeff[12];
    PetscInt  i, j, k, l, dim;

    if (isTensor) {zToPlex[2] = 2; zToPlex[3] = 3;}
    if (numCoords == 12) {
      dim = 3;
    } else if (numCoords == 8) {
      dim = 2;
    } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "The number of coordinates for this quadrilateral is %D != 8 or 12", numCoords);
    for (i = 0; i < Nv; i++) {
      PetscInt zi = zToPlex[i];

      for (j = 0; j < dim; j++) {
        zOrder[dim * i + j] = PetscRealPart(coords[dim * zi + j]);
      }
    }
    for (j = 0; j < dim; j++) {
      /* Nodal basis for evaluation at the vertices: (1 \mp xi) (1 \mp eta):
           \phi^0 = (1 - xi - eta + xi eta) --> 1      = 1/4 ( \phi^0 + \phi^1 + \phi^2 + \phi^3)
           \phi^1 = (1 + xi - eta - xi eta) --> xi     = 1/4 (-\phi^0 + \phi^1 - \phi^2 + \phi^3)
           \phi^2 = (1 - xi + eta - xi eta) --> eta    = 1/4 (-\phi^0 - \phi^1 + \phi^2 + \phi^3)
           \phi^3 = (1 + xi + eta + xi eta) --> xi eta = 1/4 ( \phi^0 - \phi^1 - \phi^2 + \phi^3)
      */
      zCoeff[dim * 0 + j] = 0.25 * (  zOrder[dim * 0 + j] + zOrder[dim * 1 + j] + zOrder[dim * 2 + j] + zOrder[dim * 3 + j]);
      zCoeff[dim * 1 + j] = 0.25 * (- zOrder[dim * 0 + j] + zOrder[dim * 1 + j] - zOrder[dim * 2 + j] + zOrder[dim * 3 + j]);
      zCoeff[dim * 2 + j] = 0.25 * (- zOrder[dim * 0 + j] - zOrder[dim * 1 + j] + zOrder[dim * 2 + j] + zOrder[dim * 3 + j]);
      zCoeff[dim * 3 + j] = 0.25 * (  zOrder[dim * 0 + j] - zOrder[dim * 1 + j] - zOrder[dim * 2 + j] + zOrder[dim * 3 + j]);
    }
    for (i = 0; i < Nq; i++) {
      PetscReal xi = points[dimR * i], eta = points[dimR * i + 1];

      if (v) {
        PetscReal extPoint[4];

        extPoint[0] = 1.;
        extPoint[1] = xi;
        extPoint[2] = eta;
        extPoint[3] = xi * eta;
        for (j = 0; j < dim; j++) {
          PetscReal val = 0.;

          for (k = 0; k < Nv; k++) {
            val += extPoint[k] * zCoeff[dim * k + j];
          }
          v[i * dim + j] = val;
        }
      }
      if (J) {
        PetscReal extJ[8];

        extJ[0] = 0.;
        extJ[1] = 0.;
        extJ[2] = 1.;
        extJ[3] = 0.;
        extJ[4] = 0.;
        extJ[5] = 1.;
        extJ[6] = eta;
        extJ[7] = xi;
        for (j = 0; j < dim; j++) {
          for (k = 0; k < dimR; k++) {
            PetscReal val = 0.;

            for (l = 0; l < Nv; l++) {
              val += zCoeff[dim * l + j] * extJ[dimR * l + k];
            }
            J[i * dim * dim + dim * j + k] = val;
          }
        }
        if (dim == 3) { /* put the cross product in the third component of the Jacobian */
          PetscReal x, y, z;
          PetscReal *iJ = &J[i * dim * dim];
          PetscReal norm;

          x = iJ[1 * dim + 0] * iJ[2 * dim + 1] - iJ[1 * dim + 1] * iJ[2 * dim + 0];
          y = iJ[0 * dim + 1] * iJ[2 * dim + 0] - iJ[0 * dim + 0] * iJ[2 * dim + 1];
          z = iJ[0 * dim + 0] * iJ[1 * dim + 1] - iJ[0 * dim + 1] * iJ[1 * dim + 0];
          norm = PetscSqrtReal(x * x + y * y + z * z);
          iJ[2] = x / norm;
          iJ[5] = y / norm;
          iJ[8] = z / norm;
          DMPlex_Det3D_Internal(&detJ[i], &J[i * dim * dim]);
          if (invJ) {DMPlex_Invert3D_Internal(&invJ[i * dim * dim], &J[i * dim * dim], detJ[i]);}
        } else {
          DMPlex_Det2D_Internal(&detJ[i], &J[i * dim * dim]);
          if (invJ) {DMPlex_Invert2D_Internal(&invJ[i * dim * dim], &J[i * dim * dim], detJ[i]);}
        }
      }
    }
  }
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, e, &numCoords, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeTetrahedronGeometry_Internal(DM dm, PetscInt e, PetscReal v0[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  const PetscInt dim = 3;
  PetscInt       d;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, e, NULL, &coords));
  *detJ = 0.0;
  if (v0)   {for (d = 0; d < dim; d++) v0[d] = PetscRealPart(coords[d]);}
  if (J)    {
    for (d = 0; d < dim; d++) {
      /* I orient with outward face normals */
      J[d*dim+0] = 0.5*(PetscRealPart(coords[2*dim+d]) - PetscRealPart(coords[0*dim+d]));
      J[d*dim+1] = 0.5*(PetscRealPart(coords[1*dim+d]) - PetscRealPart(coords[0*dim+d]));
      J[d*dim+2] = 0.5*(PetscRealPart(coords[3*dim+d]) - PetscRealPart(coords[0*dim+d]));
    }
    CHKERRQ(PetscLogFlops(18.0));
    DMPlex_Det3D_Internal(detJ, J);
  }
  if (invJ) {DMPlex_Invert3D_Internal(invJ, J, *detJ);}
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, e, NULL, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeHexahedronGeometry_Internal(DM dm, PetscInt e, PetscInt Nq, const PetscReal points[], PetscReal v[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  const PetscInt dim = 3;
  PetscInt       d;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, e, NULL, &coords));
  if (!Nq) {
    *detJ = 0.0;
    if (v)   {for (d = 0; d < dim; d++) v[d] = PetscRealPart(coords[d]);}
    if (J)    {
      for (d = 0; d < dim; d++) {
        J[d*dim+0] = 0.5*(PetscRealPart(coords[3*dim+d]) - PetscRealPart(coords[0*dim+d]));
        J[d*dim+1] = 0.5*(PetscRealPart(coords[1*dim+d]) - PetscRealPart(coords[0*dim+d]));
        J[d*dim+2] = 0.5*(PetscRealPart(coords[4*dim+d]) - PetscRealPart(coords[0*dim+d]));
      }
      CHKERRQ(PetscLogFlops(18.0));
      DMPlex_Det3D_Internal(detJ, J);
    }
    if (invJ) {DMPlex_Invert3D_Internal(invJ, J, *detJ);}
  } else {
    const PetscInt Nv = 8;
    const PetscInt zToPlex[8] = {0, 3, 1, 2, 4, 5, 7, 6};
    const PetscInt dim = 3;
    const PetscInt dimR = 3;
    PetscReal zOrder[24];
    PetscReal zCoeff[24];
    PetscInt  i, j, k, l;

    for (i = 0; i < Nv; i++) {
      PetscInt zi = zToPlex[i];

      for (j = 0; j < dim; j++) {
        zOrder[dim * i + j] = PetscRealPart(coords[dim * zi + j]);
      }
    }
    for (j = 0; j < dim; j++) {
      zCoeff[dim * 0 + j] = 0.125 * (  zOrder[dim * 0 + j] + zOrder[dim * 1 + j] + zOrder[dim * 2 + j] + zOrder[dim * 3 + j] + zOrder[dim * 4 + j] + zOrder[dim * 5 + j] + zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 1 + j] = 0.125 * (- zOrder[dim * 0 + j] + zOrder[dim * 1 + j] - zOrder[dim * 2 + j] + zOrder[dim * 3 + j] - zOrder[dim * 4 + j] + zOrder[dim * 5 + j] - zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 2 + j] = 0.125 * (- zOrder[dim * 0 + j] - zOrder[dim * 1 + j] + zOrder[dim * 2 + j] + zOrder[dim * 3 + j] - zOrder[dim * 4 + j] - zOrder[dim * 5 + j] + zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 3 + j] = 0.125 * (  zOrder[dim * 0 + j] - zOrder[dim * 1 + j] - zOrder[dim * 2 + j] + zOrder[dim * 3 + j] + zOrder[dim * 4 + j] - zOrder[dim * 5 + j] - zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 4 + j] = 0.125 * (- zOrder[dim * 0 + j] - zOrder[dim * 1 + j] - zOrder[dim * 2 + j] - zOrder[dim * 3 + j] + zOrder[dim * 4 + j] + zOrder[dim * 5 + j] + zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 5 + j] = 0.125 * (+ zOrder[dim * 0 + j] - zOrder[dim * 1 + j] + zOrder[dim * 2 + j] - zOrder[dim * 3 + j] - zOrder[dim * 4 + j] + zOrder[dim * 5 + j] - zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 6 + j] = 0.125 * (+ zOrder[dim * 0 + j] + zOrder[dim * 1 + j] - zOrder[dim * 2 + j] - zOrder[dim * 3 + j] - zOrder[dim * 4 + j] - zOrder[dim * 5 + j] + zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
      zCoeff[dim * 7 + j] = 0.125 * (- zOrder[dim * 0 + j] + zOrder[dim * 1 + j] + zOrder[dim * 2 + j] - zOrder[dim * 3 + j] + zOrder[dim * 4 + j] - zOrder[dim * 5 + j] - zOrder[dim * 6 + j] + zOrder[dim * 7 + j]);
    }
    for (i = 0; i < Nq; i++) {
      PetscReal xi = points[dimR * i], eta = points[dimR * i + 1], theta = points[dimR * i + 2];

      if (v) {
        PetscReal extPoint[8];

        extPoint[0] = 1.;
        extPoint[1] = xi;
        extPoint[2] = eta;
        extPoint[3] = xi * eta;
        extPoint[4] = theta;
        extPoint[5] = theta * xi;
        extPoint[6] = theta * eta;
        extPoint[7] = theta * eta * xi;
        for (j = 0; j < dim; j++) {
          PetscReal val = 0.;

          for (k = 0; k < Nv; k++) {
            val += extPoint[k] * zCoeff[dim * k + j];
          }
          v[i * dim + j] = val;
        }
      }
      if (J) {
        PetscReal extJ[24];

        extJ[0]  = 0.         ; extJ[1]  = 0.        ; extJ[2]  = 0.      ;
        extJ[3]  = 1.         ; extJ[4]  = 0.        ; extJ[5]  = 0.      ;
        extJ[6]  = 0.         ; extJ[7]  = 1.        ; extJ[8]  = 0.      ;
        extJ[9]  = eta        ; extJ[10] = xi        ; extJ[11] = 0.      ;
        extJ[12] = 0.         ; extJ[13] = 0.        ; extJ[14] = 1.      ;
        extJ[15] = theta      ; extJ[16] = 0.        ; extJ[17] = xi      ;
        extJ[18] = 0.         ; extJ[19] = theta     ; extJ[20] = eta     ;
        extJ[21] = theta * eta; extJ[22] = theta * xi; extJ[23] = eta * xi;

        for (j = 0; j < dim; j++) {
          for (k = 0; k < dimR; k++) {
            PetscReal val = 0.;

            for (l = 0; l < Nv; l++) {
              val += zCoeff[dim * l + j] * extJ[dimR * l + k];
            }
            J[i * dim * dim + dim * j + k] = val;
          }
        }
        DMPlex_Det3D_Internal(&detJ[i], &J[i * dim * dim]);
        if (invJ) {DMPlex_Invert3D_Internal(&invJ[i * dim * dim], &J[i * dim * dim], detJ[i]);}
      }
    }
  }
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, e, NULL, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeTriangularPrismGeometry_Internal(DM dm, PetscInt e, PetscInt Nq, const PetscReal points[], PetscReal v[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  const PetscInt dim = 3;
  PetscInt       d;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, e, NULL, &coords));
  if (!Nq) {
    /* Assume that the map to the reference is affine */
    *detJ = 0.0;
    if (v)   {for (d = 0; d < dim; d++) v[d] = PetscRealPart(coords[d]);}
    if (J)    {
      for (d = 0; d < dim; d++) {
        J[d*dim+0] = 0.5*(PetscRealPart(coords[2*dim+d]) - PetscRealPart(coords[0*dim+d]));
        J[d*dim+1] = 0.5*(PetscRealPart(coords[1*dim+d]) - PetscRealPart(coords[0*dim+d]));
        J[d*dim+2] = 0.5*(PetscRealPart(coords[4*dim+d]) - PetscRealPart(coords[0*dim+d]));
      }
      CHKERRQ(PetscLogFlops(18.0));
      DMPlex_Det3D_Internal(detJ, J);
    }
    if (invJ) {DMPlex_Invert3D_Internal(invJ, J, *detJ);}
  } else {
    const PetscInt dim  = 3;
    const PetscInt dimR = 3;
    const PetscInt Nv   = 6;
    PetscReal verts[18];
    PetscReal coeff[18];
    PetscInt  i, j, k, l;

    for (i = 0; i < Nv; ++i) for (j = 0; j < dim; ++j) verts[dim * i + j] = PetscRealPart(coords[dim * i + j]);
    for (j = 0; j < dim; ++j) {
      /* Check for triangle,
           phi^0 = -1/2 (xi + eta)  chi^0 = delta(-1, -1)   x(xi) = \sum_k x_k phi^k(xi) = \sum_k chi^k(x) phi^k(xi)
           phi^1 =  1/2 (1 + xi)    chi^1 = delta( 1, -1)   y(xi) = \sum_k y_k phi^k(xi) = \sum_k chi^k(y) phi^k(xi)
           phi^2 =  1/2 (1 + eta)   chi^2 = delta(-1,  1)

           phi^0 + phi^1 + phi^2 = 1    coef_1   = 1/2 (         chi^1 + chi^2)
          -phi^0 + phi^1 - phi^2 = xi   coef_xi  = 1/2 (-chi^0 + chi^1)
          -phi^0 - phi^1 + phi^2 = eta  coef_eta = 1/2 (-chi^0         + chi^2)

          < chi_0 chi_1 chi_2> A /  1  1  1 \ / phi_0 \   <chi> I <phi>^T  so we need the inverse transpose
                                 | -1  1 -1 | | phi_1 | =
                                 \ -1 -1  1 / \ phi_2 /

          Check phi^0: 1/2 (phi^0 chi^1 + phi^0 chi^2 + phi^0 chi^0 - phi^0 chi^1 + phi^0 chi^0 - phi^0 chi^2) = phi^0 chi^0
      */
      /* Nodal basis for evaluation at the vertices: {-xi - eta, 1 + xi, 1 + eta} (1 \mp zeta):
           \phi^0 = 1/4 (   -xi - eta        + xi zeta + eta zeta) --> /  1  1  1  1  1  1 \ 1
           \phi^1 = 1/4 (1      + eta - zeta           - eta zeta) --> | -1  1 -1 -1 -1  1 | eta
           \phi^2 = 1/4 (1 + xi       - zeta - xi zeta)            --> | -1 -1  1 -1  1 -1 | xi
           \phi^3 = 1/4 (   -xi - eta        - xi zeta - eta zeta) --> | -1 -1 -1  1  1  1 | zeta
           \phi^4 = 1/4 (1 + xi       + zeta + xi zeta)            --> |  1  1 -1 -1  1 -1 | xi zeta
           \phi^5 = 1/4 (1      + eta + zeta           + eta zeta) --> \  1 -1  1 -1 -1  1 / eta zeta
           1/4 /  0  1  1  0  1  1 \
               | -1  1  0 -1  0  1 |
               | -1  0  1 -1  1  0 |
               |  0 -1 -1  0  1  1 |
               |  1  0 -1 -1  1  0 |
               \  1 -1  0 -1  0  1 /
      */
      coeff[dim * 0 + j] = (1./4.) * (                      verts[dim * 1 + j] + verts[dim * 2 + j]                      + verts[dim * 4 + j] + verts[dim * 5 + j]);
      coeff[dim * 1 + j] = (1./4.) * (-verts[dim * 0 + j] + verts[dim * 1 + j]                      - verts[dim * 3 + j]                      + verts[dim * 5 + j]);
      coeff[dim * 2 + j] = (1./4.) * (-verts[dim * 0 + j]                      + verts[dim * 2 + j] - verts[dim * 3 + j] + verts[dim * 4 + j]);
      coeff[dim * 3 + j] = (1./4.) * (                    - verts[dim * 1 + j] - verts[dim * 2 + j]                      + verts[dim * 4 + j] + verts[dim * 5 + j]);
      coeff[dim * 4 + j] = (1./4.) * ( verts[dim * 0 + j]                      - verts[dim * 2 + j] - verts[dim * 3 + j] + verts[dim * 4 + j]);
      coeff[dim * 5 + j] = (1./4.) * ( verts[dim * 0 + j] - verts[dim * 1 + j]                      - verts[dim * 3 + j]                      + verts[dim * 5 + j]);
      /* For reference prism:
      {0, 0, 0}
      {0, 1, 0}
      {1, 0, 0}
      {0, 0, 1}
      {0, 0, 0}
      {0, 0, 0}
      */
    }
    for (i = 0; i < Nq; ++i) {
      const PetscReal xi = points[dimR * i], eta = points[dimR * i + 1], zeta = points[dimR * i + 2];

      if (v) {
        PetscReal extPoint[6];
        PetscInt  c;

        extPoint[0] = 1.;
        extPoint[1] = eta;
        extPoint[2] = xi;
        extPoint[3] = zeta;
        extPoint[4] = xi * zeta;
        extPoint[5] = eta * zeta;
        for (c = 0; c < dim; ++c) {
          PetscReal val = 0.;

          for (k = 0; k < Nv; ++k) {
            val += extPoint[k] * coeff[k*dim + c];
          }
          v[i*dim + c] = val;
        }
      }
      if (J) {
        PetscReal extJ[18];

        extJ[0]  = 0.  ; extJ[1]  = 0.  ; extJ[2]  = 0. ;
        extJ[3]  = 0.  ; extJ[4]  = 1.  ; extJ[5]  = 0. ;
        extJ[6]  = 1.  ; extJ[7]  = 0.  ; extJ[8]  = 0. ;
        extJ[9]  = 0.  ; extJ[10] = 0.  ; extJ[11] = 1. ;
        extJ[12] = zeta; extJ[13] = 0.  ; extJ[14] = xi ;
        extJ[15] = 0.  ; extJ[16] = zeta; extJ[17] = eta;

        for (j = 0; j < dim; j++) {
          for (k = 0; k < dimR; k++) {
            PetscReal val = 0.;

            for (l = 0; l < Nv; l++) {
              val += coeff[dim * l + j] * extJ[dimR * l + k];
            }
            J[i * dim * dim + dim * j + k] = val;
          }
        }
        DMPlex_Det3D_Internal(&detJ[i], &J[i * dim * dim]);
        if (invJ) {DMPlex_Invert3D_Internal(&invJ[i * dim * dim], &J[i * dim * dim], detJ[i]);}
      }
    }
  }
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, e, NULL, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeCellGeometryFEM_Implicit(DM dm, PetscInt cell, PetscQuadrature quad, PetscReal *v, PetscReal *J, PetscReal *invJ, PetscReal *detJ)
{
  DMPolytopeType  ct;
  PetscInt        depth, dim, coordDim, coneSize, i;
  PetscInt        Nq = 0;
  const PetscReal *points = NULL;
  DMLabel         depthLabel;
  PetscReal       xi0[3] = {-1.,-1.,-1.}, v0[3], J0[9], detJ0;
  PetscBool       isAffine = PETSC_TRUE;

  PetscFunctionBegin;
  CHKERRQ(DMPlexGetDepth(dm, &depth));
  CHKERRQ(DMPlexGetConeSize(dm, cell, &coneSize));
  CHKERRQ(DMPlexGetDepthLabel(dm, &depthLabel));
  CHKERRQ(DMLabelGetValue(depthLabel, cell, &dim));
  if (depth == 1 && dim == 1) {
    CHKERRQ(DMGetDimension(dm, &dim));
  }
  CHKERRQ(DMGetCoordinateDim(dm, &coordDim));
  PetscCheckFalse(coordDim > 3,PetscObjectComm((PetscObject)dm), PETSC_ERR_SUP, "Unsupported coordinate dimension %D > 3", coordDim);
  if (quad) CHKERRQ(PetscQuadratureGetData(quad, NULL, NULL, &Nq, &points, NULL));
  CHKERRQ(DMPlexGetCellType(dm, cell, &ct));
  switch (ct) {
    case DM_POLYTOPE_POINT:
    CHKERRQ(DMPlexComputePointGeometry_Internal(dm, cell, v, J, invJ, detJ));
    isAffine = PETSC_FALSE;
    break;
    case DM_POLYTOPE_SEGMENT:
    case DM_POLYTOPE_POINT_PRISM_TENSOR:
    if (Nq) CHKERRQ(DMPlexComputeLineGeometry_Internal(dm, cell, v0, J0, NULL, &detJ0));
    else    CHKERRQ(DMPlexComputeLineGeometry_Internal(dm, cell, v,  J,  invJ,  detJ));
    break;
    case DM_POLYTOPE_TRIANGLE:
    if (Nq) CHKERRQ(DMPlexComputeTriangleGeometry_Internal(dm, cell, v0, J0, NULL, &detJ0));
    else    CHKERRQ(DMPlexComputeTriangleGeometry_Internal(dm, cell, v,  J,  invJ,  detJ));
    break;
    case DM_POLYTOPE_QUADRILATERAL:
    CHKERRQ(DMPlexComputeRectangleGeometry_Internal(dm, cell, PETSC_FALSE, Nq, points, v, J, invJ, detJ));
    isAffine = PETSC_FALSE;
    break;
    case DM_POLYTOPE_SEG_PRISM_TENSOR:
    CHKERRQ(DMPlexComputeRectangleGeometry_Internal(dm, cell, PETSC_TRUE, Nq, points, v, J, invJ, detJ));
    isAffine = PETSC_FALSE;
    break;
    case DM_POLYTOPE_TETRAHEDRON:
    if (Nq) CHKERRQ(DMPlexComputeTetrahedronGeometry_Internal(dm, cell, v0, J0, NULL, &detJ0));
    else    CHKERRQ(DMPlexComputeTetrahedronGeometry_Internal(dm, cell, v,  J,  invJ,  detJ));
    break;
    case DM_POLYTOPE_HEXAHEDRON:
    CHKERRQ(DMPlexComputeHexahedronGeometry_Internal(dm, cell, Nq, points, v, J, invJ, detJ));
    isAffine = PETSC_FALSE;
    break;
    case DM_POLYTOPE_TRI_PRISM:
    CHKERRQ(DMPlexComputeTriangularPrismGeometry_Internal(dm, cell, Nq, points, v, J, invJ, detJ));
    isAffine = PETSC_FALSE;
    break;
    default: SETERRQ(PetscObjectComm((PetscObject) dm), PETSC_ERR_ARG_OUTOFRANGE, "No element geometry for cell %" PetscInt_FMT " with type %s", cell, DMPolytopeTypes[PetscMax(0, PetscMin(ct, DM_NUM_POLYTOPES))]);
  }
  if (isAffine && Nq) {
    if (v) {
      for (i = 0; i < Nq; i++) {
        CoordinatesRefToReal(coordDim, dim, xi0, v0, J0, &points[dim * i], &v[coordDim * i]);
      }
    }
    if (detJ) {
      for (i = 0; i < Nq; i++) {
        detJ[i] = detJ0;
      }
    }
    if (J) {
      PetscInt k;

      for (i = 0, k = 0; i < Nq; i++) {
        PetscInt j;

        for (j = 0; j < coordDim * coordDim; j++, k++) {
          J[k] = J0[j];
        }
      }
    }
    if (invJ) {
      PetscInt k;
      switch (coordDim) {
      case 0:
        break;
      case 1:
        invJ[0] = 1./J0[0];
        break;
      case 2:
        DMPlex_Invert2D_Internal(invJ, J0, detJ0);
        break;
      case 3:
        DMPlex_Invert3D_Internal(invJ, J0, detJ0);
        break;
      }
      for (i = 1, k = coordDim * coordDim; i < Nq; i++) {
        PetscInt j;

        for (j = 0; j < coordDim * coordDim; j++, k++) {
          invJ[k] = invJ[j];
        }
      }
    }
  }
  PetscFunctionReturn(0);
}

/*@C
  DMPlexComputeCellGeometryAffineFEM - Assuming an affine map, compute the Jacobian, inverse Jacobian, and Jacobian determinant for a given cell

  Collective on dm

  Input Parameters:
+ dm   - the DM
- cell - the cell

  Output Parameters:
+ v0   - the translation part of this affine transform
. J    - the Jacobian of the transform from the reference element
. invJ - the inverse of the Jacobian
- detJ - the Jacobian determinant

  Level: advanced

  Fortran Notes:
  Since it returns arrays, this routine is only available in Fortran 90, and you must
  include petsc.h90 in your code.

.seealso: DMPlexComputeCellGeometryFEM(), DMGetCoordinateSection(), DMGetCoordinates()
@*/
PetscErrorCode DMPlexComputeCellGeometryAffineFEM(DM dm, PetscInt cell, PetscReal *v0, PetscReal *J, PetscReal *invJ, PetscReal *detJ)
{
  PetscFunctionBegin;
  CHKERRQ(DMPlexComputeCellGeometryFEM_Implicit(dm,cell,NULL,v0,J,invJ,detJ));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeCellGeometryFEM_FE(DM dm, PetscFE fe, PetscInt point, PetscQuadrature quad, PetscReal v[], PetscReal J[], PetscReal invJ[], PetscReal *detJ)
{
  PetscQuadrature   feQuad;
  PetscSection      coordSection;
  Vec               coordinates;
  PetscScalar      *coords = NULL;
  const PetscReal  *quadPoints;
  PetscTabulation T;
  PetscInt          dim, cdim, pdim, qdim, Nq, numCoords, q;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, point, &numCoords, &coords));
  CHKERRQ(DMGetDimension(dm, &dim));
  CHKERRQ(DMGetCoordinateDim(dm, &cdim));
  if (!quad) { /* use the first point of the first functional of the dual space */
    PetscDualSpace dsp;

    CHKERRQ(PetscFEGetDualSpace(fe, &dsp));
    CHKERRQ(PetscDualSpaceGetFunctional(dsp, 0, &quad));
    CHKERRQ(PetscQuadratureGetData(quad, &qdim, NULL, &Nq, &quadPoints, NULL));
    Nq = 1;
  } else {
    CHKERRQ(PetscQuadratureGetData(quad, &qdim, NULL, &Nq, &quadPoints, NULL));
  }
  CHKERRQ(PetscFEGetDimension(fe, &pdim));
  CHKERRQ(PetscFEGetQuadrature(fe, &feQuad));
  if (feQuad == quad) {
    CHKERRQ(PetscFEGetCellTabulation(fe, J ? 1 : 0, &T));
    PetscCheckFalse(numCoords != pdim*cdim,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "There are %d coordinates for point %d != %d*%d", numCoords, point, pdim, cdim);
  } else {
    CHKERRQ(PetscFECreateTabulation(fe, 1, Nq, quadPoints, J ? 1 : 0, &T));
  }
  PetscCheckFalse(qdim != dim,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Point dimension %d != quadrature dimension %d", dim, qdim);
  {
    const PetscReal *basis    = T->T[0];
    const PetscReal *basisDer = T->T[1];
    PetscReal        detJt;

#if defined(PETSC_USE_DEBUG)
    PetscCheckFalse(Nq != T->Np,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Np %D != %D", Nq, T->Np);
    PetscCheckFalse(pdim != T->Nb,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Nb %D != %D", pdim, T->Nb);
    PetscCheckFalse(dim != T->Nc,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Nc %D != %D", dim, T->Nc);
    PetscCheckFalse(cdim != T->cdim,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "cdim %D != %D", cdim, T->cdim);
#endif
    if (v) {
      CHKERRQ(PetscArrayzero(v, Nq*cdim));
      for (q = 0; q < Nq; ++q) {
        PetscInt i, k;

        for (k = 0; k < pdim; ++k) {
          const PetscInt vertex = k/cdim;
          for (i = 0; i < cdim; ++i) {
            v[q*cdim + i] += basis[(q*pdim + k)*cdim + i] * PetscRealPart(coords[vertex*cdim + i]);
          }
        }
        CHKERRQ(PetscLogFlops(2.0*pdim*cdim));
      }
    }
    if (J) {
      CHKERRQ(PetscArrayzero(J, Nq*cdim*cdim));
      for (q = 0; q < Nq; ++q) {
        PetscInt i, j, k, c, r;

        /* J = dx_i/d\xi_j = sum[k=0,n-1] dN_k/d\xi_j * x_i(k) */
        for (k = 0; k < pdim; ++k) {
          const PetscInt vertex = k/cdim;
          for (j = 0; j < dim; ++j) {
            for (i = 0; i < cdim; ++i) {
              J[(q*cdim + i)*cdim + j] += basisDer[((q*pdim + k)*cdim + i)*dim + j] * PetscRealPart(coords[vertex*cdim + i]);
            }
          }
        }
        CHKERRQ(PetscLogFlops(2.0*pdim*dim*cdim));
        if (cdim > dim) {
          for (c = dim; c < cdim; ++c)
            for (r = 0; r < cdim; ++r)
              J[r*cdim+c] = r == c ? 1.0 : 0.0;
        }
        if (!detJ && !invJ) continue;
        detJt = 0.;
        switch (cdim) {
        case 3:
          DMPlex_Det3D_Internal(&detJt, &J[q*cdim*dim]);
          if (invJ) {DMPlex_Invert3D_Internal(&invJ[q*cdim*dim], &J[q*cdim*dim], detJt);}
          break;
        case 2:
          DMPlex_Det2D_Internal(&detJt, &J[q*cdim*dim]);
          if (invJ) {DMPlex_Invert2D_Internal(&invJ[q*cdim*dim], &J[q*cdim*dim], detJt);}
          break;
        case 1:
          detJt = J[q*cdim*dim];
          if (invJ) invJ[q*cdim*dim] = 1.0/detJt;
        }
        if (detJ) detJ[q] = detJt;
      }
    } else PetscCheckFalse(detJ || invJ,PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Need J to compute invJ or detJ");
  }
  if (feQuad != quad) CHKERRQ(PetscTabulationDestroy(&T));
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, point, &numCoords, &coords));
  PetscFunctionReturn(0);
}

/*@C
  DMPlexComputeCellGeometryFEM - Compute the Jacobian, inverse Jacobian, and Jacobian determinant at each quadrature point in the given cell

  Collective on dm

  Input Parameters:
+ dm   - the DM
. cell - the cell
- quad - the quadrature containing the points in the reference element where the geometry will be evaluated.  If quad == NULL, geometry will be
         evaluated at the first vertex of the reference element

  Output Parameters:
+ v    - the image of the transformed quadrature points, otherwise the image of the first vertex in the closure of the reference element
. J    - the Jacobian of the transform from the reference element at each quadrature point
. invJ - the inverse of the Jacobian at each quadrature point
- detJ - the Jacobian determinant at each quadrature point

  Level: advanced

  Fortran Notes:
  Since it returns arrays, this routine is only available in Fortran 90, and you must
  include petsc.h90 in your code.

.seealso: DMGetCoordinateSection(), DMGetCoordinates()
@*/
PetscErrorCode DMPlexComputeCellGeometryFEM(DM dm, PetscInt cell, PetscQuadrature quad, PetscReal *v, PetscReal *J, PetscReal *invJ, PetscReal *detJ)
{
  DM             cdm;
  PetscFE        fe = NULL;

  PetscFunctionBegin;
  PetscValidPointer(detJ, 7);
  CHKERRQ(DMGetCoordinateDM(dm, &cdm));
  if (cdm) {
    PetscClassId id;
    PetscInt     numFields;
    PetscDS      prob;
    PetscObject  disc;

    CHKERRQ(DMGetNumFields(cdm, &numFields));
    if (numFields) {
      CHKERRQ(DMGetDS(cdm, &prob));
      CHKERRQ(PetscDSGetDiscretization(prob,0,&disc));
      CHKERRQ(PetscObjectGetClassId(disc,&id));
      if (id == PETSCFE_CLASSID) {
        fe = (PetscFE) disc;
      }
    }
  }
  if (!fe) CHKERRQ(DMPlexComputeCellGeometryFEM_Implicit(dm, cell, quad, v, J, invJ, detJ));
  else     CHKERRQ(DMPlexComputeCellGeometryFEM_FE(dm, fe, cell, quad, v, J, invJ, detJ));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeGeometryFVM_0D_Internal(DM dm, PetscInt dim, PetscInt cell, PetscReal *vol, PetscReal centroid[], PetscReal normal[])
{
  PetscSection        coordSection;
  Vec                 coordinates;
  const PetscScalar  *coords = NULL;
  PetscInt            d, dof, off;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(VecGetArrayRead(coordinates, &coords));

  /* for a point the centroid is just the coord */
  if (centroid) {
    CHKERRQ(PetscSectionGetDof(coordSection, cell, &dof));
    CHKERRQ(PetscSectionGetOffset(coordSection, cell, &off));
    for (d = 0; d < dof; d++){
      centroid[d] = PetscRealPart(coords[off + d]);
    }
  }
  if (normal) {
    const PetscInt *support, *cones;
    PetscInt        supportSize;
    PetscReal       norm, sign;

    /* compute the norm based upon the support centroids */
    CHKERRQ(DMPlexGetSupportSize(dm, cell, &supportSize));
    CHKERRQ(DMPlexGetSupport(dm, cell, &support));
    CHKERRQ(DMPlexComputeCellGeometryFVM(dm, support[0], NULL, normal, NULL));

    /* Take the normal from the centroid of the support to the vertex*/
    CHKERRQ(PetscSectionGetDof(coordSection, cell, &dof));
    CHKERRQ(PetscSectionGetOffset(coordSection, cell, &off));
    for (d = 0; d < dof; d++){
      normal[d] -= PetscRealPart(coords[off + d]);
    }

    /* Determine the sign of the normal based upon its location in the support */
    CHKERRQ(DMPlexGetCone(dm, support[0], &cones));
    sign = cones[0] == cell ? 1.0 : -1.0;

    norm = DMPlex_NormD_Internal(dim, normal);
    for (d = 0; d < dim; ++d) normal[d] /= (norm*sign);
  }
  if (vol) {
    *vol = 1.0;
  }
  CHKERRQ(VecRestoreArrayRead(coordinates, &coords));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexComputeGeometryFVM_1D_Internal(DM dm, PetscInt dim, PetscInt cell, PetscReal *vol, PetscReal centroid[], PetscReal normal[])
{
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  PetscScalar    tmp[2];
  PetscInt       coordSize, d;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, cell, &coordSize, &coords));
  CHKERRQ(DMLocalizeCoordinate_Internal(dm, dim, coords, &coords[dim], tmp));
  if (centroid) {
    for (d = 0; d < dim; ++d) centroid[d] = 0.5*PetscRealPart(coords[d] + tmp[d]);
  }
  if (normal) {
    PetscReal norm;

    PetscCheckFalse(dim != 2,PETSC_COMM_SELF, PETSC_ERR_SUP, "We only support 2D edges right now");
    normal[0]  = -PetscRealPart(coords[1] - tmp[1]);
    normal[1]  =  PetscRealPart(coords[0] - tmp[0]);
    norm       = DMPlex_NormD_Internal(dim, normal);
    for (d = 0; d < dim; ++d) normal[d] /= norm;
  }
  if (vol) {
    *vol = 0.0;
    for (d = 0; d < dim; ++d) *vol += PetscSqr(PetscRealPart(coords[d] - tmp[d]));
    *vol = PetscSqrtReal(*vol);
  }
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, cell, &coordSize, &coords));
  PetscFunctionReturn(0);
}

/* Centroid_i = (\sum_n A_n Cn_i) / A */
static PetscErrorCode DMPlexComputeGeometryFVM_2D_Internal(DM dm, PetscInt dim, PetscInt cell, PetscReal *vol, PetscReal centroid[], PetscReal normal[])
{
  DMPolytopeType ct;
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *coords = NULL;
  PetscInt       fv[4] = {0, 1, 2, 3};
  PetscInt       cdim, coordSize, numCorners, p, d;

  PetscFunctionBegin;
  /* Must check for hybrid cells because prisms have a different orientation scheme */
  CHKERRQ(DMPlexGetCellType(dm, cell, &ct));
  switch (ct) {
    case DM_POLYTOPE_SEG_PRISM_TENSOR: fv[2] = 3; fv[3] = 2;break;
    default: break;
  }
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMPlexGetConeSize(dm, cell, &numCorners));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, cell, &coordSize, &coords));
  CHKERRQ(DMGetCoordinateDim(dm, &cdim));
  {
    PetscReal c[3] = {0., 0., 0.}, n[3] = {0., 0., 0.}, origin[3] = {0., 0., 0.}, norm;

    for (d = 0; d < cdim; d++) origin[d] = PetscRealPart(coords[d]);
    for (p = 0; p < numCorners-2; ++p) {
      PetscReal e0[3] = {0., 0., 0.}, e1[3] = {0., 0., 0.};
      for (d = 0; d < cdim; d++) {
        e0[d] = PetscRealPart(coords[cdim*fv[p+1]+d]) - origin[d];
        e1[d] = PetscRealPart(coords[cdim*fv[p+2]+d]) - origin[d];
      }
      const PetscReal dx = e0[1] * e1[2] - e0[2] * e1[1];
      const PetscReal dy = e0[2] * e1[0] - e0[0] * e1[2];
      const PetscReal dz = e0[0] * e1[1] - e0[1] * e1[0];
      const PetscReal a  = PetscSqrtReal(dx*dx + dy*dy + dz*dz);

      n[0] += dx;
      n[1] += dy;
      n[2] += dz;
      for (d = 0; d < cdim; d++) {
        c[d] += a * PetscRealPart(origin[d] + coords[cdim*fv[p+1]+d] + coords[cdim*fv[p+2]+d]) / 3.;
      }
    }
    norm = PetscSqrtReal(n[0]*n[0] + n[1]*n[1] + n[2]*n[2]);
    n[0] /= norm;
    n[1] /= norm;
    n[2] /= norm;
    c[0] /= norm;
    c[1] /= norm;
    c[2] /= norm;
    if (vol) *vol = 0.5*norm;
    if (centroid) for (d = 0; d < cdim; ++d) centroid[d] = c[d];
    if (normal) for (d = 0; d < cdim; ++d) normal[d] = n[d];
  }
  CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, cell, &coordSize, &coords));
  PetscFunctionReturn(0);
}

/* Centroid_i = (\sum_n V_n Cn_i) / V */
static PetscErrorCode DMPlexComputeGeometryFVM_3D_Internal(DM dm, PetscInt dim, PetscInt cell, PetscReal *vol, PetscReal centroid[], PetscReal normal[])
{
  DMPolytopeType  ct;
  PetscSection    coordSection;
  Vec             coordinates;
  PetscScalar    *coords = NULL;
  PetscReal       vsum = 0.0, vtmp, coordsTmp[3*3], origin[3];
  const PetscInt *faces, *facesO;
  PetscBool       isHybrid = PETSC_FALSE;
  PetscInt        numFaces, f, coordSize, p, d;

  PetscFunctionBegin;
  PetscCheckFalse(dim > 3,PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"No support for dim %D > 3",dim);
  /* Must check for hybrid cells because prisms have a different orientation scheme */
  CHKERRQ(DMPlexGetCellType(dm, cell, &ct));
  switch (ct) {
    case DM_POLYTOPE_POINT_PRISM_TENSOR:
    case DM_POLYTOPE_SEG_PRISM_TENSOR:
    case DM_POLYTOPE_TRI_PRISM_TENSOR:
    case DM_POLYTOPE_QUAD_PRISM_TENSOR:
      isHybrid = PETSC_TRUE;
    default: break;
  }

  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));

  if (centroid) for (d = 0; d < dim; ++d) centroid[d] = 0.0;
  CHKERRQ(DMPlexGetConeSize(dm, cell, &numFaces));
  CHKERRQ(DMPlexGetCone(dm, cell, &faces));
  CHKERRQ(DMPlexGetConeOrientation(dm, cell, &facesO));
  for (f = 0; f < numFaces; ++f) {
    PetscBool      flip = isHybrid && f == 0 ? PETSC_TRUE : PETSC_FALSE; /* The first hybrid face is reversed */
    DMPolytopeType ct;

    CHKERRQ(DMPlexVecGetClosure(dm, coordSection, coordinates, faces[f], &coordSize, &coords));
    // If using zero as the origin vertex for each tetrahedron, an element far from the origin will have positive and
    // negative volumes that nearly cancel, thus incurring rounding error. Here we define origin[] as the first vertex
    // so that all tetrahedra have positive volume.
    if (f == 0) for (d = 0; d < dim; d++) origin[d] = PetscRealPart(coords[d]);
    CHKERRQ(DMPlexGetCellType(dm, faces[f], &ct));
    switch (ct) {
    case DM_POLYTOPE_TRIANGLE:
      for (d = 0; d < dim; ++d) {
        coordsTmp[0*dim+d] = PetscRealPart(coords[0*dim+d]) - origin[d];
        coordsTmp[1*dim+d] = PetscRealPart(coords[1*dim+d]) - origin[d];
        coordsTmp[2*dim+d] = PetscRealPart(coords[2*dim+d]) - origin[d];
      }
      Volume_Tetrahedron_Origin_Internal(&vtmp, coordsTmp);
      if (facesO[f] < 0 || flip) vtmp = -vtmp;
      vsum += vtmp;
      if (centroid) {           /* Centroid of OABC = (a+b+c)/4 */
        for (d = 0; d < dim; ++d) {
          for (p = 0; p < 3; ++p) centroid[d] += coordsTmp[p*dim+d]*vtmp;
        }
      }
      break;
    case DM_POLYTOPE_QUADRILATERAL:
    case DM_POLYTOPE_SEG_PRISM_TENSOR:
    {
      PetscInt fv[4] = {0, 1, 2, 3};

      /* Side faces for hybrid cells are are stored as tensor products */
      if (isHybrid && f > 1) {fv[2] = 3; fv[3] = 2;}
      /* DO FOR PYRAMID */
      /* First tet */
      for (d = 0; d < dim; ++d) {
        coordsTmp[0*dim+d] = PetscRealPart(coords[fv[0]*dim+d]) - origin[d];
        coordsTmp[1*dim+d] = PetscRealPart(coords[fv[1]*dim+d]) - origin[d];
        coordsTmp[2*dim+d] = PetscRealPart(coords[fv[3]*dim+d]) - origin[d];
      }
      Volume_Tetrahedron_Origin_Internal(&vtmp, coordsTmp);
      if (facesO[f] < 0 || flip) vtmp = -vtmp;
      vsum += vtmp;
      if (centroid) {
        for (d = 0; d < dim; ++d) {
          for (p = 0; p < 3; ++p) centroid[d] += coordsTmp[p*dim+d]*vtmp;
        }
      }
      /* Second tet */
      for (d = 0; d < dim; ++d) {
        coordsTmp[0*dim+d] = PetscRealPart(coords[fv[1]*dim+d]) - origin[d];
        coordsTmp[1*dim+d] = PetscRealPart(coords[fv[2]*dim+d]) - origin[d];
        coordsTmp[2*dim+d] = PetscRealPart(coords[fv[3]*dim+d]) - origin[d];
      }
      Volume_Tetrahedron_Origin_Internal(&vtmp, coordsTmp);
      if (facesO[f] < 0 || flip) vtmp = -vtmp;
      vsum += vtmp;
      if (centroid) {
        for (d = 0; d < dim; ++d) {
          for (p = 0; p < 3; ++p) centroid[d] += coordsTmp[p*dim+d]*vtmp;
        }
      }
      break;
    }
    default:
      SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Cannot handle face %D of type %s", faces[f], DMPolytopeTypes[ct]);
    }
    CHKERRQ(DMPlexVecRestoreClosure(dm, coordSection, coordinates, faces[f], &coordSize, &coords));
  }
  if (vol)     *vol = PetscAbsReal(vsum);
  if (normal)   for (d = 0; d < dim; ++d) normal[d]    = 0.0;
  if (centroid) for (d = 0; d < dim; ++d) centroid[d] = centroid[d] / (vsum*4) + origin[d];
;
  PetscFunctionReturn(0);
}

/*@C
  DMPlexComputeCellGeometryFVM - Compute the volume for a given cell

  Collective on dm

  Input Parameters:
+ dm   - the DM
- cell - the cell

  Output Parameters:
+ volume   - the cell volume
. centroid - the cell centroid
- normal - the cell normal, if appropriate

  Level: advanced

  Fortran Notes:
  Since it returns arrays, this routine is only available in Fortran 90, and you must
  include petsc.h90 in your code.

.seealso: DMGetCoordinateSection(), DMGetCoordinates()
@*/
PetscErrorCode DMPlexComputeCellGeometryFVM(DM dm, PetscInt cell, PetscReal *vol, PetscReal centroid[], PetscReal normal[])
{
  PetscInt       depth, dim;

  PetscFunctionBegin;
  CHKERRQ(DMPlexGetDepth(dm, &depth));
  CHKERRQ(DMGetDimension(dm, &dim));
  PetscCheckFalse(depth != dim,PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Mesh must be interpolated");
  CHKERRQ(DMPlexGetPointDepth(dm, cell, &depth));
  switch (depth) {
  case 0:
    CHKERRQ(DMPlexComputeGeometryFVM_0D_Internal(dm, dim, cell, vol, centroid, normal));
    break;
  case 1:
    CHKERRQ(DMPlexComputeGeometryFVM_1D_Internal(dm, dim, cell, vol, centroid, normal));
    break;
  case 2:
    CHKERRQ(DMPlexComputeGeometryFVM_2D_Internal(dm, dim, cell, vol, centroid, normal));
    break;
  case 3:
    CHKERRQ(DMPlexComputeGeometryFVM_3D_Internal(dm, dim, cell, vol, centroid, normal));
    break;
  default:
    SETERRQ(PetscObjectComm((PetscObject)dm), PETSC_ERR_SUP, "Unsupported dimension %D (depth %D) for element geometry computation", dim, depth);
  }
  PetscFunctionReturn(0);
}

/*@
  DMPlexComputeGeometryFEM - Precompute cell geometry for the entire mesh

  Collective on dm

  Input Parameter:
. dm - The DMPlex

  Output Parameter:
. cellgeom - A vector with the cell geometry data for each cell

  Level: beginner

@*/
PetscErrorCode DMPlexComputeGeometryFEM(DM dm, Vec *cellgeom)
{
  DM             dmCell;
  Vec            coordinates;
  PetscSection   coordSection, sectionCell;
  PetscScalar   *cgeom;
  PetscInt       cStart, cEnd, c;

  PetscFunctionBegin;
  CHKERRQ(DMClone(dm, &dmCell));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  CHKERRQ(DMSetCoordinateSection(dmCell, PETSC_DETERMINE, coordSection));
  CHKERRQ(DMSetCoordinatesLocal(dmCell, coordinates));
  CHKERRQ(PetscSectionCreate(PetscObjectComm((PetscObject) dm), &sectionCell));
  CHKERRQ(DMPlexGetSimplexOrBoxCells(dm, 0, &cStart, &cEnd));
  CHKERRQ(PetscSectionSetChart(sectionCell, cStart, cEnd));
  /* TODO This needs to be multiplied by Nq for non-affine */
  for (c = cStart; c < cEnd; ++c) CHKERRQ(PetscSectionSetDof(sectionCell, c, (PetscInt) PetscCeilReal(((PetscReal) sizeof(PetscFEGeom))/sizeof(PetscScalar))));
  CHKERRQ(PetscSectionSetUp(sectionCell));
  CHKERRQ(DMSetLocalSection(dmCell, sectionCell));
  CHKERRQ(PetscSectionDestroy(&sectionCell));
  CHKERRQ(DMCreateLocalVector(dmCell, cellgeom));
  CHKERRQ(VecGetArray(*cellgeom, &cgeom));
  for (c = cStart; c < cEnd; ++c) {
    PetscFEGeom *cg;

    CHKERRQ(DMPlexPointLocalRef(dmCell, c, cgeom, &cg));
    CHKERRQ(PetscArrayzero(cg, 1));
    CHKERRQ(DMPlexComputeCellGeometryFEM(dmCell, c, NULL, cg->v, cg->J, cg->invJ, cg->detJ));
    PetscCheckFalse(*cg->detJ <= 0.0,PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Invalid determinant %g for element %D", (double) *cg->detJ, c);
  }
  PetscFunctionReturn(0);
}

/*@
  DMPlexComputeGeometryFVM - Computes the cell and face geometry for a finite volume method

  Input Parameter:
. dm - The DM

  Output Parameters:
+ cellgeom - A Vec of PetscFVCellGeom data
- facegeom - A Vec of PetscFVFaceGeom data

  Level: developer

.seealso: PetscFVFaceGeom, PetscFVCellGeom, DMPlexComputeGeometryFEM()
@*/
PetscErrorCode DMPlexComputeGeometryFVM(DM dm, Vec *cellgeom, Vec *facegeom)
{
  DM             dmFace, dmCell;
  DMLabel        ghostLabel;
  PetscSection   sectionFace, sectionCell;
  PetscSection   coordSection;
  Vec            coordinates;
  PetscScalar   *fgeom, *cgeom;
  PetscReal      minradius, gminradius;
  PetscInt       dim, cStart, cEnd, cEndInterior, c, fStart, fEnd, f;

  PetscFunctionBegin;
  CHKERRQ(DMGetDimension(dm, &dim));
  CHKERRQ(DMGetCoordinateSection(dm, &coordSection));
  CHKERRQ(DMGetCoordinatesLocal(dm, &coordinates));
  /* Make cell centroids and volumes */
  CHKERRQ(DMClone(dm, &dmCell));
  CHKERRQ(DMSetCoordinateSection(dmCell, PETSC_DETERMINE, coordSection));
  CHKERRQ(DMSetCoordinatesLocal(dmCell, coordinates));
  CHKERRQ(PetscSectionCreate(PetscObjectComm((PetscObject) dm), &sectionCell));
  CHKERRQ(DMPlexGetHeightStratum(dm, 0, &cStart, &cEnd));
  CHKERRQ(DMPlexGetGhostCellStratum(dm, &cEndInterior, NULL));
  CHKERRQ(PetscSectionSetChart(sectionCell, cStart, cEnd));
  for (c = cStart; c < cEnd; ++c) CHKERRQ(PetscSectionSetDof(sectionCell, c, (PetscInt) PetscCeilReal(((PetscReal) sizeof(PetscFVCellGeom))/sizeof(PetscScalar))));
  CHKERRQ(PetscSectionSetUp(sectionCell));
  CHKERRQ(DMSetLocalSection(dmCell, sectionCell));
  CHKERRQ(PetscSectionDestroy(&sectionCell));
  CHKERRQ(DMCreateLocalVector(dmCell, cellgeom));
  if (cEndInterior < 0) cEndInterior = cEnd;
  CHKERRQ(VecGetArray(*cellgeom, &cgeom));
  for (c = cStart; c < cEndInterior; ++c) {
    PetscFVCellGeom *cg;

    CHKERRQ(DMPlexPointLocalRef(dmCell, c, cgeom, &cg));
    CHKERRQ(PetscArrayzero(cg, 1));
    CHKERRQ(DMPlexComputeCellGeometryFVM(dmCell, c, &cg->volume, cg->centroid, NULL));
  }
  /* Compute face normals and minimum cell radius */
  CHKERRQ(DMClone(dm, &dmFace));
  CHKERRQ(PetscSectionCreate(PetscObjectComm((PetscObject) dm), &sectionFace));
  CHKERRQ(DMPlexGetHeightStratum(dm, 1, &fStart, &fEnd));
  CHKERRQ(PetscSectionSetChart(sectionFace, fStart, fEnd));
  for (f = fStart; f < fEnd; ++f) CHKERRQ(PetscSectionSetDof(sectionFace, f, (PetscInt) PetscCeilReal(((PetscReal) sizeof(PetscFVFaceGeom))/sizeof(PetscScalar))));
  CHKERRQ(PetscSectionSetUp(sectionFace));
  CHKERRQ(DMSetLocalSection(dmFace, sectionFace));
  CHKERRQ(PetscSectionDestroy(&sectionFace));
  CHKERRQ(DMCreateLocalVector(dmFace, facegeom));
  CHKERRQ(VecGetArray(*facegeom, &fgeom));
  CHKERRQ(DMGetLabel(dm, "ghost", &ghostLabel));
  minradius = PETSC_MAX_REAL;
  for (f = fStart; f < fEnd; ++f) {
    PetscFVFaceGeom *fg;
    PetscReal        area;
    const PetscInt  *cells;
    PetscInt         ncells, ghost = -1, d, numChildren;

    if (ghostLabel) CHKERRQ(DMLabelGetValue(ghostLabel, f, &ghost));
    CHKERRQ(DMPlexGetTreeChildren(dm,f,&numChildren,NULL));
    CHKERRQ(DMPlexGetSupport(dm, f, &cells));
    CHKERRQ(DMPlexGetSupportSize(dm, f, &ncells));
    /* It is possible to get a face with no support when using partition overlap */
    if (!ncells || ghost >= 0 || numChildren) continue;
    CHKERRQ(DMPlexPointLocalRef(dmFace, f, fgeom, &fg));
    CHKERRQ(DMPlexComputeCellGeometryFVM(dm, f, &area, fg->centroid, fg->normal));
    for (d = 0; d < dim; ++d) fg->normal[d] *= area;
    /* Flip face orientation if necessary to match ordering in support, and Update minimum radius */
    {
      PetscFVCellGeom *cL, *cR;
      PetscReal       *lcentroid, *rcentroid;
      PetscReal        l[3], r[3], v[3];

      CHKERRQ(DMPlexPointLocalRead(dmCell, cells[0], cgeom, &cL));
      lcentroid = cells[0] >= cEndInterior ? fg->centroid : cL->centroid;
      if (ncells > 1) {
        CHKERRQ(DMPlexPointLocalRead(dmCell, cells[1], cgeom, &cR));
        rcentroid = cells[1] >= cEndInterior ? fg->centroid : cR->centroid;
      }
      else {
        rcentroid = fg->centroid;
      }
      CHKERRQ(DMLocalizeCoordinateReal_Internal(dm, dim, fg->centroid, lcentroid, l));
      CHKERRQ(DMLocalizeCoordinateReal_Internal(dm, dim, fg->centroid, rcentroid, r));
      DMPlex_WaxpyD_Internal(dim, -1, l, r, v);
      if (DMPlex_DotRealD_Internal(dim, fg->normal, v) < 0) {
        for (d = 0; d < dim; ++d) fg->normal[d] = -fg->normal[d];
      }
      if (DMPlex_DotRealD_Internal(dim, fg->normal, v) <= 0) {
        PetscCheckFalse(dim == 2,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Direction for face %d could not be fixed, normal (%g,%g) v (%g,%g)", f, (double) fg->normal[0], (double) fg->normal[1], (double) v[0], (double) v[1]);
        PetscCheckFalse(dim == 3,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Direction for face %d could not be fixed, normal (%g,%g,%g) v (%g,%g,%g)", f, (double) fg->normal[0], (double) fg->normal[1], (double) fg->normal[2], (double) v[0], (double) v[1], (double) v[2]);
        SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Direction for face %d could not be fixed", f);
      }
      if (cells[0] < cEndInterior) {
        DMPlex_WaxpyD_Internal(dim, -1, fg->centroid, cL->centroid, v);
        minradius = PetscMin(minradius, DMPlex_NormD_Internal(dim, v));
      }
      if (ncells > 1 && cells[1] < cEndInterior) {
        DMPlex_WaxpyD_Internal(dim, -1, fg->centroid, cR->centroid, v);
        minradius = PetscMin(minradius, DMPlex_NormD_Internal(dim, v));
      }
    }
  }
  CHKERRMPI(MPIU_Allreduce(&minradius, &gminradius, 1, MPIU_REAL, MPIU_MIN, PetscObjectComm((PetscObject)dm)));
  CHKERRQ(DMPlexSetMinRadius(dm, gminradius));
  /* Compute centroids of ghost cells */
  for (c = cEndInterior; c < cEnd; ++c) {
    PetscFVFaceGeom *fg;
    const PetscInt  *cone,    *support;
    PetscInt         coneSize, supportSize, s;

    CHKERRQ(DMPlexGetConeSize(dmCell, c, &coneSize));
    PetscCheckFalse(coneSize != 1,PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Ghost cell %d has cone size %d != 1", c, coneSize);
    CHKERRQ(DMPlexGetCone(dmCell, c, &cone));
    CHKERRQ(DMPlexGetSupportSize(dmCell, cone[0], &supportSize));
    PetscCheckFalse(supportSize != 2,PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %d has support size %d != 2", cone[0], supportSize);
    CHKERRQ(DMPlexGetSupport(dmCell, cone[0], &support));
    CHKERRQ(DMPlexPointLocalRef(dmFace, cone[0], fgeom, &fg));
    for (s = 0; s < 2; ++s) {
      /* Reflect ghost centroid across plane of face */
      if (support[s] == c) {
        PetscFVCellGeom       *ci;
        PetscFVCellGeom       *cg;
        PetscReal              c2f[3], a;

        CHKERRQ(DMPlexPointLocalRead(dmCell, support[(s+1)%2], cgeom, &ci));
        DMPlex_WaxpyD_Internal(dim, -1, ci->centroid, fg->centroid, c2f); /* cell to face centroid */
        a    = DMPlex_DotRealD_Internal(dim, c2f, fg->normal)/DMPlex_DotRealD_Internal(dim, fg->normal, fg->normal);
        CHKERRQ(DMPlexPointLocalRef(dmCell, support[s], cgeom, &cg));
        DMPlex_WaxpyD_Internal(dim, 2*a, fg->normal, ci->centroid, cg->centroid);
        cg->volume = ci->volume;
      }
    }
  }
  CHKERRQ(VecRestoreArray(*facegeom, &fgeom));
  CHKERRQ(VecRestoreArray(*cellgeom, &cgeom));
  CHKERRQ(DMDestroy(&dmCell));
  CHKERRQ(DMDestroy(&dmFace));
  PetscFunctionReturn(0);
}

/*@C
  DMPlexGetMinRadius - Returns the minimum distance from any cell centroid to a face

  Not collective

  Input Parameter:
. dm - the DM

  Output Parameter:
. minradius - the minimum cell radius

  Level: developer

.seealso: DMGetCoordinates()
@*/
PetscErrorCode DMPlexGetMinRadius(DM dm, PetscReal *minradius)
{
  PetscFunctionBegin;
  PetscValidHeaderSpecific(dm,DM_CLASSID,1);
  PetscValidPointer(minradius,2);
  *minradius = ((DM_Plex*) dm->data)->minradius;
  PetscFunctionReturn(0);
}

/*@C
  DMPlexSetMinRadius - Sets the minimum distance from the cell centroid to a face

  Logically collective

  Input Parameters:
+ dm - the DM
- minradius - the minimum cell radius

  Level: developer

.seealso: DMSetCoordinates()
@*/
PetscErrorCode DMPlexSetMinRadius(DM dm, PetscReal minradius)
{
  PetscFunctionBegin;
  PetscValidHeaderSpecific(dm,DM_CLASSID,1);
  ((DM_Plex*) dm->data)->minradius = minradius;
  PetscFunctionReturn(0);
}

static PetscErrorCode BuildGradientReconstruction_Internal(DM dm, PetscFV fvm, DM dmFace, PetscScalar *fgeom, DM dmCell, PetscScalar *cgeom)
{
  DMLabel        ghostLabel;
  PetscScalar   *dx, *grad, **gref;
  PetscInt       dim, cStart, cEnd, c, cEndInterior, maxNumFaces;

  PetscFunctionBegin;
  CHKERRQ(DMGetDimension(dm, &dim));
  CHKERRQ(DMPlexGetHeightStratum(dm, 0, &cStart, &cEnd));
  CHKERRQ(DMPlexGetGhostCellStratum(dm, &cEndInterior, NULL));
  cEndInterior = cEndInterior < 0 ? cEnd : cEndInterior;
  CHKERRQ(DMPlexGetMaxSizes(dm, &maxNumFaces, NULL));
  CHKERRQ(PetscFVLeastSquaresSetMaxFaces(fvm, maxNumFaces));
  CHKERRQ(DMGetLabel(dm, "ghost", &ghostLabel));
  CHKERRQ(PetscMalloc3(maxNumFaces*dim, &dx, maxNumFaces*dim, &grad, maxNumFaces, &gref));
  for (c = cStart; c < cEndInterior; c++) {
    const PetscInt        *faces;
    PetscInt               numFaces, usedFaces, f, d;
    PetscFVCellGeom        *cg;
    PetscBool              boundary;
    PetscInt               ghost;

    CHKERRQ(DMPlexPointLocalRead(dmCell, c, cgeom, &cg));
    CHKERRQ(DMPlexGetConeSize(dm, c, &numFaces));
    CHKERRQ(DMPlexGetCone(dm, c, &faces));
    PetscCheckFalse(numFaces < dim,PETSC_COMM_SELF,PETSC_ERR_ARG_INCOMP,"Cell %D has only %D faces, not enough for gradient reconstruction", c, numFaces);
    for (f = 0, usedFaces = 0; f < numFaces; ++f) {
      PetscFVCellGeom       *cg1;
      PetscFVFaceGeom       *fg;
      const PetscInt        *fcells;
      PetscInt               ncell, side;

      CHKERRQ(DMLabelGetValue(ghostLabel, faces[f], &ghost));
      CHKERRQ(DMIsBoundaryPoint(dm, faces[f], &boundary));
      if ((ghost >= 0) || boundary) continue;
      CHKERRQ(DMPlexGetSupport(dm, faces[f], &fcells));
      side  = (c != fcells[0]); /* c is on left=0 or right=1 of face */
      ncell = fcells[!side];    /* the neighbor */
      CHKERRQ(DMPlexPointLocalRef(dmFace, faces[f], fgeom, &fg));
      CHKERRQ(DMPlexPointLocalRead(dmCell, ncell, cgeom, &cg1));
      for (d = 0; d < dim; ++d) dx[usedFaces*dim+d] = cg1->centroid[d] - cg->centroid[d];
      gref[usedFaces++] = fg->grad[side];  /* Gradient reconstruction term will go here */
    }
    PetscCheck(usedFaces,PETSC_COMM_SELF, PETSC_ERR_USER, "Mesh contains isolated cell (no neighbors). Is it intentional?");
    CHKERRQ(PetscFVComputeGradient(fvm, usedFaces, dx, grad));
    for (f = 0, usedFaces = 0; f < numFaces; ++f) {
      CHKERRQ(DMLabelGetValue(ghostLabel, faces[f], &ghost));
      CHKERRQ(DMIsBoundaryPoint(dm, faces[f], &boundary));
      if ((ghost >= 0) || boundary) continue;
      for (d = 0; d < dim; ++d) gref[usedFaces][d] = grad[usedFaces*dim+d];
      ++usedFaces;
    }
  }
  CHKERRQ(PetscFree3(dx, grad, gref));
  PetscFunctionReturn(0);
}

static PetscErrorCode BuildGradientReconstruction_Internal_Tree(DM dm, PetscFV fvm, DM dmFace, PetscScalar *fgeom, DM dmCell, PetscScalar *cgeom)
{
  DMLabel        ghostLabel;
  PetscScalar   *dx, *grad, **gref;
  PetscInt       dim, cStart, cEnd, c, cEndInterior, fStart, fEnd, f, nStart, nEnd, maxNumFaces = 0;
  PetscSection   neighSec;
  PetscInt     (*neighbors)[2];
  PetscInt      *counter;

  PetscFunctionBegin;
  CHKERRQ(DMGetDimension(dm, &dim));
  CHKERRQ(DMPlexGetHeightStratum(dm, 0, &cStart, &cEnd));
  CHKERRQ(DMPlexGetGhostCellStratum(dm, &cEndInterior, NULL));
  if (cEndInterior < 0) cEndInterior = cEnd;
  CHKERRQ(PetscSectionCreate(PetscObjectComm((PetscObject)dm),&neighSec));
  CHKERRQ(PetscSectionSetChart(neighSec,cStart,cEndInterior));
  CHKERRQ(DMPlexGetHeightStratum(dm, 1, &fStart, &fEnd));
  CHKERRQ(DMGetLabel(dm, "ghost", &ghostLabel));
  for (f = fStart; f < fEnd; f++) {
    const PetscInt        *fcells;
    PetscBool              boundary;
    PetscInt               ghost = -1;
    PetscInt               numChildren, numCells, c;

    if (ghostLabel) CHKERRQ(DMLabelGetValue(ghostLabel, f, &ghost));
    CHKERRQ(DMIsBoundaryPoint(dm, f, &boundary));
    CHKERRQ(DMPlexGetTreeChildren(dm, f, &numChildren, NULL));
    if ((ghost >= 0) || boundary || numChildren) continue;
    CHKERRQ(DMPlexGetSupportSize(dm, f, &numCells));
    if (numCells == 2) {
      CHKERRQ(DMPlexGetSupport(dm, f, &fcells));
      for (c = 0; c < 2; c++) {
        PetscInt cell = fcells[c];

        if (cell >= cStart && cell < cEndInterior) {
          CHKERRQ(PetscSectionAddDof(neighSec,cell,1));
        }
      }
    }
  }
  CHKERRQ(PetscSectionSetUp(neighSec));
  CHKERRQ(PetscSectionGetMaxDof(neighSec,&maxNumFaces));
  CHKERRQ(PetscFVLeastSquaresSetMaxFaces(fvm, maxNumFaces));
  nStart = 0;
  CHKERRQ(PetscSectionGetStorageSize(neighSec,&nEnd));
  CHKERRQ(PetscMalloc1((nEnd-nStart),&neighbors));
  CHKERRQ(PetscCalloc1((cEndInterior-cStart),&counter));
  for (f = fStart; f < fEnd; f++) {
    const PetscInt        *fcells;
    PetscBool              boundary;
    PetscInt               ghost = -1;
    PetscInt               numChildren, numCells, c;

    if (ghostLabel) CHKERRQ(DMLabelGetValue(ghostLabel, f, &ghost));
    CHKERRQ(DMIsBoundaryPoint(dm, f, &boundary));
    CHKERRQ(DMPlexGetTreeChildren(dm, f, &numChildren, NULL));
    if ((ghost >= 0) || boundary || numChildren) continue;
    CHKERRQ(DMPlexGetSupportSize(dm, f, &numCells));
    if (numCells == 2) {
      CHKERRQ(DMPlexGetSupport(dm, f, &fcells));
      for (c = 0; c < 2; c++) {
        PetscInt cell = fcells[c], off;

        if (cell >= cStart && cell < cEndInterior) {
          CHKERRQ(PetscSectionGetOffset(neighSec,cell,&off));
          off += counter[cell - cStart]++;
          neighbors[off][0] = f;
          neighbors[off][1] = fcells[1 - c];
        }
      }
    }
  }
  CHKERRQ(PetscFree(counter));
  CHKERRQ(PetscMalloc3(maxNumFaces*dim, &dx, maxNumFaces*dim, &grad, maxNumFaces, &gref));
  for (c = cStart; c < cEndInterior; c++) {
    PetscInt               numFaces, f, d, off, ghost = -1;
    PetscFVCellGeom        *cg;

    CHKERRQ(DMPlexPointLocalRead(dmCell, c, cgeom, &cg));
    CHKERRQ(PetscSectionGetDof(neighSec, c, &numFaces));
    CHKERRQ(PetscSectionGetOffset(neighSec, c, &off));
    if (ghostLabel) CHKERRQ(DMLabelGetValue(ghostLabel, c, &ghost));
    PetscCheckFalse(ghost < 0 && numFaces < dim,PETSC_COMM_SELF,PETSC_ERR_ARG_INCOMP,"Cell %D has only %D faces, not enough for gradient reconstruction", c, numFaces);
    for (f = 0; f < numFaces; ++f) {
      PetscFVCellGeom       *cg1;
      PetscFVFaceGeom       *fg;
      const PetscInt        *fcells;
      PetscInt               ncell, side, nface;

      nface = neighbors[off + f][0];
      ncell = neighbors[off + f][1];
      CHKERRQ(DMPlexGetSupport(dm,nface,&fcells));
      side  = (c != fcells[0]);
      CHKERRQ(DMPlexPointLocalRef(dmFace, nface, fgeom, &fg));
      CHKERRQ(DMPlexPointLocalRead(dmCell, ncell, cgeom, &cg1));
      for (d = 0; d < dim; ++d) dx[f*dim+d] = cg1->centroid[d] - cg->centroid[d];
      gref[f] = fg->grad[side];  /* Gradient reconstruction term will go here */
    }
    CHKERRQ(PetscFVComputeGradient(fvm, numFaces, dx, grad));
    for (f = 0; f < numFaces; ++f) {
      for (d = 0; d < dim; ++d) gref[f][d] = grad[f*dim+d];
    }
  }
  CHKERRQ(PetscFree3(dx, grad, gref));
  CHKERRQ(PetscSectionDestroy(&neighSec));
  CHKERRQ(PetscFree(neighbors));
  PetscFunctionReturn(0);
}

/*@
  DMPlexComputeGradientFVM - Compute geometric factors for gradient reconstruction, which are stored in the geometry data, and compute layout for gradient data

  Collective on dm

  Input Parameters:
+ dm  - The DM
. fvm - The PetscFV
- cellGeometry - The face geometry from DMPlexComputeCellGeometryFVM()

  Input/Output Parameter:
. faceGeometry - The face geometry from DMPlexComputeFaceGeometryFVM(); on output
                 the geometric factors for gradient calculation are inserted

  Output Parameter:
. dmGrad - The DM describing the layout of gradient data

  Level: developer

.seealso: DMPlexGetFaceGeometryFVM(), DMPlexGetCellGeometryFVM()
@*/
PetscErrorCode DMPlexComputeGradientFVM(DM dm, PetscFV fvm, Vec faceGeometry, Vec cellGeometry, DM *dmGrad)
{
  DM             dmFace, dmCell;
  PetscScalar   *fgeom, *cgeom;
  PetscSection   sectionGrad, parentSection;
  PetscInt       dim, pdim, cStart, cEnd, cEndInterior, c;

  PetscFunctionBegin;
  CHKERRQ(DMGetDimension(dm, &dim));
  CHKERRQ(PetscFVGetNumComponents(fvm, &pdim));
  CHKERRQ(DMPlexGetHeightStratum(dm, 0, &cStart, &cEnd));
  CHKERRQ(DMPlexGetGhostCellStratum(dm, &cEndInterior, NULL));
  /* Construct the interpolant corresponding to each face from the least-square solution over the cell neighborhood */
  CHKERRQ(VecGetDM(faceGeometry, &dmFace));
  CHKERRQ(VecGetDM(cellGeometry, &dmCell));
  CHKERRQ(VecGetArray(faceGeometry, &fgeom));
  CHKERRQ(VecGetArray(cellGeometry, &cgeom));
  CHKERRQ(DMPlexGetTree(dm,&parentSection,NULL,NULL,NULL,NULL));
  if (!parentSection) {
    CHKERRQ(BuildGradientReconstruction_Internal(dm, fvm, dmFace, fgeom, dmCell, cgeom));
  } else {
    CHKERRQ(BuildGradientReconstruction_Internal_Tree(dm, fvm, dmFace, fgeom, dmCell, cgeom));
  }
  CHKERRQ(VecRestoreArray(faceGeometry, &fgeom));
  CHKERRQ(VecRestoreArray(cellGeometry, &cgeom));
  /* Create storage for gradients */
  CHKERRQ(DMClone(dm, dmGrad));
  CHKERRQ(PetscSectionCreate(PetscObjectComm((PetscObject) dm), &sectionGrad));
  CHKERRQ(PetscSectionSetChart(sectionGrad, cStart, cEnd));
  for (c = cStart; c < cEnd; ++c) CHKERRQ(PetscSectionSetDof(sectionGrad, c, pdim*dim));
  CHKERRQ(PetscSectionSetUp(sectionGrad));
  CHKERRQ(DMSetLocalSection(*dmGrad, sectionGrad));
  CHKERRQ(PetscSectionDestroy(&sectionGrad));
  PetscFunctionReturn(0);
}

/*@
  DMPlexGetDataFVM - Retrieve precomputed cell geometry

  Collective on dm

  Input Parameters:
+ dm  - The DM
- fv  - The PetscFV

  Output Parameters:
+ cellGeometry - The cell geometry
. faceGeometry - The face geometry
- gradDM       - The gradient matrices

  Level: developer

.seealso: DMPlexComputeGeometryFVM()
@*/
PetscErrorCode DMPlexGetDataFVM(DM dm, PetscFV fv, Vec *cellgeom, Vec *facegeom, DM *gradDM)
{
  PetscObject    cellgeomobj, facegeomobj;

  PetscFunctionBegin;
  CHKERRQ(PetscObjectQuery((PetscObject) dm, "DMPlex_cellgeom_fvm", &cellgeomobj));
  if (!cellgeomobj) {
    Vec cellgeomInt, facegeomInt;

    CHKERRQ(DMPlexComputeGeometryFVM(dm, &cellgeomInt, &facegeomInt));
    CHKERRQ(PetscObjectCompose((PetscObject) dm, "DMPlex_cellgeom_fvm",(PetscObject)cellgeomInt));
    CHKERRQ(PetscObjectCompose((PetscObject) dm, "DMPlex_facegeom_fvm",(PetscObject)facegeomInt));
    CHKERRQ(VecDestroy(&cellgeomInt));
    CHKERRQ(VecDestroy(&facegeomInt));
    CHKERRQ(PetscObjectQuery((PetscObject) dm, "DMPlex_cellgeom_fvm", &cellgeomobj));
  }
  CHKERRQ(PetscObjectQuery((PetscObject) dm, "DMPlex_facegeom_fvm", &facegeomobj));
  if (cellgeom) *cellgeom = (Vec) cellgeomobj;
  if (facegeom) *facegeom = (Vec) facegeomobj;
  if (gradDM) {
    PetscObject gradobj;
    PetscBool   computeGradients;

    CHKERRQ(PetscFVGetComputeGradients(fv,&computeGradients));
    if (!computeGradients) {
      *gradDM = NULL;
      PetscFunctionReturn(0);
    }
    CHKERRQ(PetscObjectQuery((PetscObject) dm, "DMPlex_dmgrad_fvm", &gradobj));
    if (!gradobj) {
      DM dmGradInt;

      CHKERRQ(DMPlexComputeGradientFVM(dm,fv,(Vec) facegeomobj,(Vec) cellgeomobj,&dmGradInt));
      CHKERRQ(PetscObjectCompose((PetscObject) dm, "DMPlex_dmgrad_fvm", (PetscObject)dmGradInt));
      CHKERRQ(DMDestroy(&dmGradInt));
      CHKERRQ(PetscObjectQuery((PetscObject) dm, "DMPlex_dmgrad_fvm", &gradobj));
    }
    *gradDM = (DM) gradobj;
  }
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexCoordinatesToReference_NewtonUpdate(PetscInt dimC, PetscInt dimR, PetscScalar *J, PetscScalar *invJ, PetscScalar *work,  PetscReal *resNeg, PetscReal *guess)
{
  PetscInt l, m;

  PetscFunctionBeginHot;
  if (dimC == dimR && dimR <= 3) {
    /* invert Jacobian, multiply */
    PetscScalar det, idet;

    switch (dimR) {
    case 1:
      invJ[0] = 1./ J[0];
      break;
    case 2:
      det = J[0] * J[3] - J[1] * J[2];
      idet = 1./det;
      invJ[0] =  J[3] * idet;
      invJ[1] = -J[1] * idet;
      invJ[2] = -J[2] * idet;
      invJ[3] =  J[0] * idet;
      break;
    case 3:
      {
        invJ[0] = J[4] * J[8] - J[5] * J[7];
        invJ[1] = J[2] * J[7] - J[1] * J[8];
        invJ[2] = J[1] * J[5] - J[2] * J[4];
        det = invJ[0] * J[0] + invJ[1] * J[3] + invJ[2] * J[6];
        idet = 1./det;
        invJ[0] *= idet;
        invJ[1] *= idet;
        invJ[2] *= idet;
        invJ[3]  = idet * (J[5] * J[6] - J[3] * J[8]);
        invJ[4]  = idet * (J[0] * J[8] - J[2] * J[6]);
        invJ[5]  = idet * (J[2] * J[3] - J[0] * J[5]);
        invJ[6]  = idet * (J[3] * J[7] - J[4] * J[6]);
        invJ[7]  = idet * (J[1] * J[6] - J[0] * J[7]);
        invJ[8]  = idet * (J[0] * J[4] - J[1] * J[3]);
      }
      break;
    }
    for (l = 0; l < dimR; l++) {
      for (m = 0; m < dimC; m++) {
        guess[l] += PetscRealPart(invJ[l * dimC + m]) * resNeg[m];
      }
    }
  } else {
#if defined(PETSC_USE_COMPLEX)
    char transpose = 'C';
#else
    char transpose = 'T';
#endif
    PetscBLASInt m = dimR;
    PetscBLASInt n = dimC;
    PetscBLASInt one = 1;
    PetscBLASInt worksize = dimR * dimC, info;

    for (l = 0; l < dimC; l++) {invJ[l] = resNeg[l];}

    PetscStackCallBLAS("LAPACKgels",LAPACKgels_(&transpose,&m,&n,&one,J,&m,invJ,&n,work,&worksize, &info));
    PetscCheckFalse(info != 0,PETSC_COMM_SELF,PETSC_ERR_LIB,"Bad argument to GELS");

    for (l = 0; l < dimR; l++) {guess[l] += PetscRealPart(invJ[l]);}
  }
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexCoordinatesToReference_Tensor(DM dm, PetscInt cell, PetscInt numPoints, const PetscReal realCoords[], PetscReal refCoords[], Vec coords, PetscInt dimC, PetscInt dimR)
{
  PetscInt       coordSize, i, j, k, l, m, maxIts = 7, numV = (1 << dimR);
  PetscScalar    *coordsScalar = NULL;
  PetscReal      *cellData, *cellCoords, *cellCoeffs, *extJ, *resNeg;
  PetscScalar    *J, *invJ, *work;

  PetscFunctionBegin;
  PetscValidHeaderSpecific(dm,DM_CLASSID,1);
  CHKERRQ(DMPlexVecGetClosure(dm, NULL, coords, cell, &coordSize, &coordsScalar));
  PetscCheckFalse(coordSize < dimC * numV,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Expecting at least %D coordinates, got %D",dimC * (1 << dimR), coordSize);
  CHKERRQ(DMGetWorkArray(dm, 2 * coordSize + dimR + dimC, MPIU_REAL, &cellData));
  CHKERRQ(DMGetWorkArray(dm, 3 * dimR * dimC, MPIU_SCALAR, &J));
  cellCoords = &cellData[0];
  cellCoeffs = &cellData[coordSize];
  extJ       = &cellData[2 * coordSize];
  resNeg     = &cellData[2 * coordSize + dimR];
  invJ       = &J[dimR * dimC];
  work       = &J[2 * dimR * dimC];
  if (dimR == 2) {
    const PetscInt zToPlex[4] = {0, 1, 3, 2};

    for (i = 0; i < 4; i++) {
      PetscInt plexI = zToPlex[i];

      for (j = 0; j < dimC; j++) {
        cellCoords[dimC * i + j] = PetscRealPart(coordsScalar[dimC * plexI + j]);
      }
    }
  } else if (dimR == 3) {
    const PetscInt zToPlex[8] = {0, 3, 1, 2, 4, 5, 7, 6};

    for (i = 0; i < 8; i++) {
      PetscInt plexI = zToPlex[i];

      for (j = 0; j < dimC; j++) {
        cellCoords[dimC * i + j] = PetscRealPart(coordsScalar[dimC * plexI + j]);
      }
    }
  } else {
    for (i = 0; i < coordSize; i++) {cellCoords[i] = PetscRealPart(coordsScalar[i]);}
  }
  /* Perform the shuffling transform that converts values at the corners of [-1,1]^d to coefficients */
  for (i = 0; i < dimR; i++) {
    PetscReal *swap;

    for (j = 0; j < (numV / 2); j++) {
      for (k = 0; k < dimC; k++) {
        cellCoeffs[dimC * j + k]                = 0.5 * (cellCoords[dimC * (2 * j + 1) + k] + cellCoords[dimC * 2 * j + k]);
        cellCoeffs[dimC * (j + (numV / 2)) + k] = 0.5 * (cellCoords[dimC * (2 * j + 1) + k] - cellCoords[dimC * 2 * j + k]);
      }
    }

    if (i < dimR - 1) {
      swap = cellCoeffs;
      cellCoeffs = cellCoords;
      cellCoords = swap;
    }
  }
  CHKERRQ(PetscArrayzero(refCoords,numPoints * dimR));
  for (j = 0; j < numPoints; j++) {
    for (i = 0; i < maxIts; i++) {
      PetscReal *guess = &refCoords[dimR * j];

      /* compute -residual and Jacobian */
      for (k = 0; k < dimC; k++) {resNeg[k] = realCoords[dimC * j + k];}
      for (k = 0; k < dimC * dimR; k++) {J[k] = 0.;}
      for (k = 0; k < numV; k++) {
        PetscReal extCoord = 1.;
        for (l = 0; l < dimR; l++) {
          PetscReal coord = guess[l];
          PetscInt  dep   = (k & (1 << l)) >> l;

          extCoord *= dep * coord + !dep;
          extJ[l] = dep;

          for (m = 0; m < dimR; m++) {
            PetscReal coord = guess[m];
            PetscInt  dep   = ((k & (1 << m)) >> m) && (m != l);
            PetscReal mult  = dep * coord + !dep;

            extJ[l] *= mult;
          }
        }
        for (l = 0; l < dimC; l++) {
          PetscReal coeff = cellCoeffs[dimC * k + l];

          resNeg[l] -= coeff * extCoord;
          for (m = 0; m < dimR; m++) {
            J[dimR * l + m] += coeff * extJ[m];
          }
        }
      }
      if (0 && PetscDefined(USE_DEBUG)) {
        PetscReal maxAbs = 0.;

        for (l = 0; l < dimC; l++) {
          maxAbs = PetscMax(maxAbs,PetscAbsReal(resNeg[l]));
        }
        CHKERRQ(PetscInfo(dm,"cell %D, point %D, iter %D: res %g\n",cell,j,i,(double) maxAbs));
      }

      CHKERRQ(DMPlexCoordinatesToReference_NewtonUpdate(dimC,dimR,J,invJ,work,resNeg,guess));
    }
  }
  CHKERRQ(DMRestoreWorkArray(dm, 3 * dimR * dimC, MPIU_SCALAR, &J));
  CHKERRQ(DMRestoreWorkArray(dm, 2 * coordSize + dimR + dimC, MPIU_REAL, &cellData));
  CHKERRQ(DMPlexVecRestoreClosure(dm, NULL, coords, cell, &coordSize, &coordsScalar));
  PetscFunctionReturn(0);
}

static PetscErrorCode DMPlexReferenceToCoordinates_Tensor(DM dm, PetscInt cell, PetscInt numPoints, const PetscReal refCoords[], PetscReal realCoords[], Vec coords, PetscInt dimC, PetscInt dimR)
{
  PetscInt       coordSize, i, j, k, l, numV = (1 << dimR);
  PetscScalar    *coordsScalar = NULL;
  PetscReal      *cellData, *cellCoords, *cellCoeffs;

  PetscFunctionBegin;
  PetscValidHeaderSpecific(dm,DM_CLASSID,1);
  CHKERRQ(DMPlexVecGetClosure(dm, NULL, coords, cell, &coordSize, &coordsScalar));
  PetscCheckFalse(coordSize < dimC * numV,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Expecting at least %D coordinates, got %D",dimC * (1 << dimR), coordSize);
  CHKERRQ(DMGetWorkArray(dm, 2 * coordSize, MPIU_REAL, &cellData));
  cellCoords = &cellData[0];
  cellCoeffs = &cellData[coordSize];
  if (dimR == 2) {
    const PetscInt zToPlex[4] = {0, 1, 3, 2};

    for (i = 0; i < 4; i++) {
      PetscInt plexI = zToPlex[i];

      for (j = 0; j < dimC; j++) {
        cellCoords[dimC * i + j] = PetscRealPart(coordsScalar[dimC * plexI + j]);
      }
    }
  } else if (dimR == 3) {
    const PetscInt zToPlex[8] = {0, 3, 1, 2, 4, 5, 7, 6};

    for (i = 0; i < 8; i++) {
      PetscInt plexI = zToPlex[i];

      for (j = 0; j < dimC; j++) {
        cellCoords[dimC * i + j] = PetscRealPart(coordsScalar[dimC * plexI + j]);
      }
    }
  } else {
    for (i = 0; i < coordSize; i++) {cellCoords[i] = PetscRealPart(coordsScalar[i]);}
  }
  /* Perform the shuffling transform that converts values at the corners of [-1,1]^d to coefficients */
  for (i = 0; i < dimR; i++) {
    PetscReal *swap;

    for (j = 0; j < (numV / 2); j++) {
      for (k = 0; k < dimC; k++) {
        cellCoeffs[dimC * j + k]                = 0.5 * (cellCoords[dimC * (2 * j + 1) + k] + cellCoords[dimC * 2 * j + k]);
        cellCoeffs[dimC * (j + (numV / 2)) + k] = 0.5 * (cellCoords[dimC * (2 * j + 1) + k] - cellCoords[dimC * 2 * j + k]);
      }
    }

    if (i < dimR - 1) {
      swap = cellCoeffs;
      cellCoeffs = cellCoords;
      cellCoords = swap;
    }
  }
  CHKERRQ(PetscArrayzero(realCoords,numPoints * dimC));
  for (j = 0; j < numPoints; j++) {
    const PetscReal *guess  = &refCoords[dimR * j];
    PetscReal       *mapped = &realCoords[dimC * j];

    for (k = 0; k < numV; k++) {
      PetscReal extCoord = 1.;
      for (l = 0; l < dimR; l++) {
        PetscReal coord = guess[l];
        PetscInt  dep   = (k & (1 << l)) >> l;

        extCoord *= dep * coord + !dep;
      }
      for (l = 0; l < dimC; l++) {
        PetscReal coeff = cellCoeffs[dimC * k + l];

        mapped[l] += coeff * extCoord;
      }
    }
  }
  CHKERRQ(DMRestoreWorkArray(dm, 2 * coordSize, MPIU_REAL, &cellData));
  CHKERRQ(DMPlexVecRestoreClosure(dm, NULL, coords, cell, &coordSize, &coordsScalar));
  PetscFunctionReturn(0);
}

/* TODO: TOBY please fix this for Nc > 1 */
static PetscErrorCode DMPlexCoordinatesToReference_FE(DM dm, PetscFE fe, PetscInt cell, PetscInt numPoints, const PetscReal realCoords[], PetscReal refCoords[], Vec coords, PetscInt Nc, PetscInt dimR)
{
  PetscInt       numComp, pdim, i, j, k, l, m, maxIter = 7, coordSize;
  PetscScalar    *nodes = NULL;
  PetscReal      *invV, *modes;
  PetscReal      *B, *D, *resNeg;
  PetscScalar    *J, *invJ, *work;

  PetscFunctionBegin;
  CHKERRQ(PetscFEGetDimension(fe, &pdim));
  CHKERRQ(PetscFEGetNumComponents(fe, &numComp));
  PetscCheckFalse(numComp != Nc,PetscObjectComm((PetscObject)dm),PETSC_ERR_SUP,"coordinate discretization must have as many components (%D) as embedding dimension (!= %D)",numComp,Nc);
  CHKERRQ(DMPlexVecGetClosure(dm, NULL, coords, cell, &coordSize, &nodes));
  /* convert nodes to values in the stable evaluation basis */
  CHKERRQ(DMGetWorkArray(dm,pdim,MPIU_REAL,&modes));
  invV = fe->invV;
  for (i = 0; i < pdim; ++i) {
    modes[i] = 0.;
    for (j = 0; j < pdim; ++j) {
      modes[i] += invV[i * pdim + j] * PetscRealPart(nodes[j]);
    }
  }
  CHKERRQ(DMGetWorkArray(dm,pdim * Nc + pdim * Nc * dimR + Nc,MPIU_REAL,&B));
  D      = &B[pdim*Nc];
  resNeg = &D[pdim*Nc * dimR];
  CHKERRQ(DMGetWorkArray(dm,3 * Nc * dimR,MPIU_SCALAR,&J));
  invJ = &J[Nc * dimR];
  work = &invJ[Nc * dimR];
  for (i = 0; i < numPoints * dimR; i++) {refCoords[i] = 0.;}
  for (j = 0; j < numPoints; j++) {
      for (i = 0; i < maxIter; i++) { /* we could batch this so that we're not making big B and D arrays all the time */
      PetscReal *guess = &refCoords[j * dimR];
      CHKERRQ(PetscSpaceEvaluate(fe->basisSpace, 1, guess, B, D, NULL));
      for (k = 0; k < Nc; k++) {resNeg[k] = realCoords[j * Nc + k];}
      for (k = 0; k < Nc * dimR; k++) {J[k] = 0.;}
      for (k = 0; k < pdim; k++) {
        for (l = 0; l < Nc; l++) {
          resNeg[l] -= modes[k] * B[k * Nc + l];
          for (m = 0; m < dimR; m++) {
            J[l * dimR + m] += modes[k] * D[(k * Nc + l) * dimR + m];
          }
        }
      }
      if (0 && PetscDefined(USE_DEBUG)) {
        PetscReal maxAbs = 0.;

        for (l = 0; l < Nc; l++) {
          maxAbs = PetscMax(maxAbs,PetscAbsReal(resNeg[l]));
        }
        CHKERRQ(PetscInfo(dm,"cell %D, point %D, iter %D: res %g\n",cell,j,i,(double) maxAbs));
      }
      CHKERRQ(DMPlexCoordinatesToReference_NewtonUpdate(Nc,dimR,J,invJ,work,resNeg,guess));
    }
  }
  CHKERRQ(DMRestoreWorkArray(dm,3 * Nc * dimR,MPIU_SCALAR,&J));
  CHKERRQ(DMRestoreWorkArray(dm,pdim * Nc + pdim * Nc * dimR + Nc,MPIU_REAL,&B));
  CHKERRQ(DMRestoreWorkArray(dm,pdim,MPIU_REAL,&modes));
  CHKERRQ(DMPlexVecRestoreClosure(dm, NULL, coords, cell, &coordSize, &nodes));
  PetscFunctionReturn(0);
}

/* TODO: TOBY please fix this for Nc > 1 */
static PetscErrorCode DMPlexReferenceToCoordinates_FE(DM dm, PetscFE fe, PetscInt cell, PetscInt numPoints, const PetscReal refCoords[], PetscReal realCoords[], Vec coords, PetscInt Nc, PetscInt dimR)
{
  PetscInt       numComp, pdim, i, j, k, l, coordSize;
  PetscScalar    *nodes = NULL;
  PetscReal      *invV, *modes;
  PetscReal      *B;

  PetscFunctionBegin;
  CHKERRQ(PetscFEGetDimension(fe, &pdim));
  CHKERRQ(PetscFEGetNumComponents(fe, &numComp));
  PetscCheckFalse(numComp != Nc,PetscObjectComm((PetscObject)dm),PETSC_ERR_SUP,"coordinate discretization must have as many components (%D) as embedding dimension (!= %D)",numComp,Nc);
  CHKERRQ(DMPlexVecGetClosure(dm, NULL, coords, cell, &coordSize, &nodes));
  /* convert nodes to values in the stable evaluation basis */
  CHKERRQ(DMGetWorkArray(dm,pdim,MPIU_REAL,&modes));
  invV = fe->invV;
  for (i = 0; i < pdim; ++i) {
    modes[i] = 0.;
    for (j = 0; j < pdim; ++j) {
      modes[i] += invV[i * pdim + j] * PetscRealPart(nodes[j]);
    }
  }
  CHKERRQ(DMGetWorkArray(dm,numPoints * pdim * Nc,MPIU_REAL,&B));
  CHKERRQ(PetscSpaceEvaluate(fe->basisSpace, numPoints, refCoords, B, NULL, NULL));
  for (i = 0; i < numPoints * Nc; i++) {realCoords[i] = 0.;}
  for (j = 0; j < numPoints; j++) {
    PetscReal *mapped = &realCoords[j * Nc];

    for (k = 0; k < pdim; k++) {
      for (l = 0; l < Nc; l++) {
        mapped[l] += modes[k] * B[(j * pdim + k) * Nc + l];
      }
    }
  }
  CHKERRQ(DMRestoreWorkArray(dm,numPoints * pdim * Nc,MPIU_REAL,&B));
  CHKERRQ(DMRestoreWorkArray(dm,pdim,MPIU_REAL,&modes));
  CHKERRQ(DMPlexVecRestoreClosure(dm, NULL, coords, cell, &coordSize, &nodes));
  PetscFunctionReturn(0);
}

/*@
  DMPlexCoordinatesToReference - Pull coordinates back from the mesh to the reference element using a single element
  map.  This inversion will be accurate inside the reference element, but may be inaccurate for mappings that do not
  extend uniquely outside the reference cell (e.g, most non-affine maps)

  Not collective

  Input Parameters:
+ dm         - The mesh, with coordinate maps defined either by a PetscDS for the coordinate DM (see DMGetCoordinateDM()) or
               implicitly by the coordinates of the corner vertices of the cell: as an affine map for simplicial elements, or
               as a multilinear map for tensor-product elements
. cell       - the cell whose map is used.
. numPoints  - the number of points to locate
- realCoords - (numPoints x coordinate dimension) array of coordinates (see DMGetCoordinateDim())

  Output Parameters:
. refCoords  - (numPoints x dimension) array of reference coordinates (see DMGetDimension())

  Level: intermediate

.seealso: DMPlexReferenceToCoordinates()
@*/
PetscErrorCode DMPlexCoordinatesToReference(DM dm, PetscInt cell, PetscInt numPoints, const PetscReal realCoords[], PetscReal refCoords[])
{
  PetscInt       dimC, dimR, depth, cStart, cEnd, i;
  DM             coordDM = NULL;
  Vec            coords;
  PetscFE        fe = NULL;

  PetscFunctionBegin;
  PetscValidHeaderSpecific(dm,DM_CLASSID,1);
  CHKERRQ(DMGetDimension(dm,&dimR));
  CHKERRQ(DMGetCoordinateDim(dm,&dimC));
  if (dimR <= 0 || dimC <= 0 || numPoints <= 0) PetscFunctionReturn(0);
  CHKERRQ(DMPlexGetDepth(dm,&depth));
  CHKERRQ(DMGetCoordinatesLocal(dm,&coords));
  CHKERRQ(DMGetCoordinateDM(dm,&coordDM));
  if (coordDM) {
    PetscInt coordFields;

    CHKERRQ(DMGetNumFields(coordDM,&coordFields));
    if (coordFields) {
      PetscClassId id;
      PetscObject  disc;

      CHKERRQ(DMGetField(coordDM,0,NULL,&disc));
      CHKERRQ(PetscObjectGetClassId(disc,&id));
      if (id == PETSCFE_CLASSID) {
        fe = (PetscFE) disc;
      }
    }
  }
  CHKERRQ(DMPlexGetSimplexOrBoxCells(dm, 0, &cStart, &cEnd));
  PetscCheckFalse(cell < cStart || cell >= cEnd,PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"point %D not in cell range [%D,%D)",cell,cStart,cEnd);
  if (!fe) { /* implicit discretization: affine or multilinear */
    PetscInt  coneSize;
    PetscBool isSimplex, isTensor;

    CHKERRQ(DMPlexGetConeSize(dm,cell,&coneSize));
    isSimplex = (coneSize == (dimR + 1)) ? PETSC_TRUE : PETSC_FALSE;
    isTensor  = (coneSize == ((depth == 1) ? (1 << dimR) : (2 * dimR))) ? PETSC_TRUE : PETSC_FALSE;
    if (isSimplex) {
      PetscReal detJ, *v0, *J, *invJ;

      CHKERRQ(DMGetWorkArray(dm,dimC + 2 * dimC * dimC, MPIU_REAL, &v0));
      J    = &v0[dimC];
      invJ = &J[dimC * dimC];
      CHKERRQ(DMPlexComputeCellGeometryAffineFEM(dm, cell, v0, J, invJ, &detJ));
      for (i = 0; i < numPoints; i++) { /* Apply the inverse affine transformation for each point */
        const PetscReal x0[3] = {-1.,-1.,-1.};

        CoordinatesRealToRef(dimC, dimR, x0, v0, invJ, &realCoords[dimC * i], &refCoords[dimR * i]);
      }
      CHKERRQ(DMRestoreWorkArray(dm,dimC + 2 * dimC * dimC, MPIU_REAL, &v0));
    } else if (isTensor) {
      CHKERRQ(DMPlexCoordinatesToReference_Tensor(coordDM, cell, numPoints, realCoords, refCoords, coords, dimC, dimR));
    } else SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Unrecognized cone size %D",coneSize);
  } else {
    CHKERRQ(DMPlexCoordinatesToReference_FE(coordDM, fe, cell, numPoints, realCoords, refCoords, coords, dimC, dimR));
  }
  PetscFunctionReturn(0);
}

/*@
  DMPlexReferenceToCoordinates - Map references coordinates to coordinates in the the mesh for a single element map.

  Not collective

  Input Parameters:
+ dm         - The mesh, with coordinate maps defined either by a PetscDS for the coordinate DM (see DMGetCoordinateDM()) or
               implicitly by the coordinates of the corner vertices of the cell: as an affine map for simplicial elements, or
               as a multilinear map for tensor-product elements
. cell       - the cell whose map is used.
. numPoints  - the number of points to locate
- refCoords  - (numPoints x dimension) array of reference coordinates (see DMGetDimension())

  Output Parameters:
. realCoords - (numPoints x coordinate dimension) array of coordinates (see DMGetCoordinateDim())

   Level: intermediate

.seealso: DMPlexCoordinatesToReference()
@*/
PetscErrorCode DMPlexReferenceToCoordinates(DM dm, PetscInt cell, PetscInt numPoints, const PetscReal refCoords[], PetscReal realCoords[])
{
  PetscInt       dimC, dimR, depth, cStart, cEnd, i;
  DM             coordDM = NULL;
  Vec            coords;
  PetscFE        fe = NULL;

  PetscFunctionBegin;
  PetscValidHeaderSpecific(dm,DM_CLASSID,1);
  CHKERRQ(DMGetDimension(dm,&dimR));
  CHKERRQ(DMGetCoordinateDim(dm,&dimC));
  if (dimR <= 0 || dimC <= 0 || numPoints <= 0) PetscFunctionReturn(0);
  CHKERRQ(DMPlexGetDepth(dm,&depth));
  CHKERRQ(DMGetCoordinatesLocal(dm,&coords));
  CHKERRQ(DMGetCoordinateDM(dm,&coordDM));
  if (coordDM) {
    PetscInt coordFields;

    CHKERRQ(DMGetNumFields(coordDM,&coordFields));
    if (coordFields) {
      PetscClassId id;
      PetscObject  disc;

      CHKERRQ(DMGetField(coordDM,0,NULL,&disc));
      CHKERRQ(PetscObjectGetClassId(disc,&id));
      if (id == PETSCFE_CLASSID) {
        fe = (PetscFE) disc;
      }
    }
  }
  CHKERRQ(DMPlexGetSimplexOrBoxCells(dm, 0, &cStart, &cEnd));
  PetscCheckFalse(cell < cStart || cell >= cEnd,PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"point %D not in cell range [%D,%D)",cell,cStart,cEnd);
  if (!fe) { /* implicit discretization: affine or multilinear */
    PetscInt  coneSize;
    PetscBool isSimplex, isTensor;

    CHKERRQ(DMPlexGetConeSize(dm,cell,&coneSize));
    isSimplex = (coneSize == (dimR + 1)) ? PETSC_TRUE : PETSC_FALSE;
    isTensor  = (coneSize == ((depth == 1) ? (1 << dimR) : (2 * dimR))) ? PETSC_TRUE : PETSC_FALSE;
    if (isSimplex) {
      PetscReal detJ, *v0, *J;

      CHKERRQ(DMGetWorkArray(dm,dimC + 2 * dimC * dimC, MPIU_REAL, &v0));
      J    = &v0[dimC];
      CHKERRQ(DMPlexComputeCellGeometryAffineFEM(dm, cell, v0, J, NULL, &detJ));
      for (i = 0; i < numPoints; i++) { /* Apply the affine transformation for each point */
        const PetscReal xi0[3] = {-1.,-1.,-1.};

        CoordinatesRefToReal(dimC, dimR, xi0, v0, J, &refCoords[dimR * i], &realCoords[dimC * i]);
      }
      CHKERRQ(DMRestoreWorkArray(dm,dimC + 2 * dimC * dimC, MPIU_REAL, &v0));
    } else if (isTensor) {
      CHKERRQ(DMPlexReferenceToCoordinates_Tensor(coordDM, cell, numPoints, refCoords, realCoords, coords, dimC, dimR));
    } else SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Unrecognized cone size %D",coneSize);
  } else {
    CHKERRQ(DMPlexReferenceToCoordinates_FE(coordDM, fe, cell, numPoints, refCoords, realCoords, coords, dimC, dimR));
  }
  PetscFunctionReturn(0);
}

/*@C
  DMPlexRemapGeometry - This function maps the original DM coordinates to new coordinates.

  Not collective

  Input Parameters:
+ dm      - The DM
. time    - The time
- func    - The function transforming current coordinates to new coordaintes

   Calling sequence of func:
$    func(PetscInt dim, PetscInt Nf, PetscInt NfAux,
$         const PetscInt uOff[], const PetscInt uOff_x[], const PetscScalar u[], const PetscScalar u_t[], const PetscScalar u_x[],
$         const PetscInt aOff[], const PetscInt aOff_x[], const PetscScalar a[], const PetscScalar a_t[], const PetscScalar a_x[],
$         PetscReal t, const PetscReal x[], PetscInt numConstants, const PetscScalar constants[], PetscScalar f[]);

+  dim          - The spatial dimension
.  Nf           - The number of input fields (here 1)
.  NfAux        - The number of input auxiliary fields
.  uOff         - The offset of the coordinates in u[] (here 0)
.  uOff_x       - The offset of the coordinates in u_x[] (here 0)
.  u            - The coordinate values at this point in space
.  u_t          - The coordinate time derivative at this point in space (here NULL)
.  u_x          - The coordinate derivatives at this point in space
.  aOff         - The offset of each auxiliary field in u[]
.  aOff_x       - The offset of each auxiliary field in u_x[]
.  a            - The auxiliary field values at this point in space
.  a_t          - The auxiliary field time derivative at this point in space (or NULL)
.  a_x          - The auxiliary field derivatives at this point in space
.  t            - The current time
.  x            - The coordinates of this point (here not used)
.  numConstants - The number of constants
.  constants    - The value of each constant
-  f            - The new coordinates at this point in space

  Level: intermediate

.seealso: DMGetCoordinates(), DMGetCoordinatesLocal(), DMGetCoordinateDM(), DMProjectFieldLocal(), DMProjectFieldLabelLocal()
@*/
PetscErrorCode DMPlexRemapGeometry(DM dm, PetscReal time,
                                   void (*func)(PetscInt, PetscInt, PetscInt,
                                                const PetscInt[], const PetscInt[], const PetscScalar[], const PetscScalar[], const PetscScalar[],
                                                const PetscInt[], const PetscInt[], const PetscScalar[], const PetscScalar[], const PetscScalar[],
                                                PetscReal, const PetscReal[], PetscInt, const PetscScalar[], PetscScalar[]))
{
  DM             cdm;
  DMField        cf;
  Vec            lCoords, tmpCoords;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinateDM(dm, &cdm));
  CHKERRQ(DMGetCoordinatesLocal(dm, &lCoords));
  CHKERRQ(DMGetLocalVector(cdm, &tmpCoords));
  CHKERRQ(VecCopy(lCoords, tmpCoords));
  /* We have to do the coordinate field manually right now since the coordinate DM will not have its own */
  CHKERRQ(DMGetCoordinateField(dm, &cf));
  cdm->coordinateField = cf;
  CHKERRQ(DMProjectFieldLocal(cdm, time, tmpCoords, &func, INSERT_VALUES, lCoords));
  cdm->coordinateField = NULL;
  CHKERRQ(DMRestoreLocalVector(cdm, &tmpCoords));
  CHKERRQ(DMSetCoordinatesLocal(dm, lCoords));
  PetscFunctionReturn(0);
}

/* Shear applies the transformation, assuming we fix z,
  / 1  0  m_0 \
  | 0  1  m_1 |
  \ 0  0   1  /
*/
static void f0_shear(PetscInt dim, PetscInt Nf, PetscInt NfAux,
                     const PetscInt uOff[], const PetscInt uOff_x[], const PetscScalar u[], const PetscScalar u_t[], const PetscScalar u_x[],
                     const PetscInt aOff[], const PetscInt aOff_x[], const PetscScalar a[], const PetscScalar a_t[], const PetscScalar a_x[],
                     PetscReal t, const PetscReal x[], PetscInt numConstants, const PetscScalar constants[], PetscScalar coords[])
{
  const PetscInt Nc = uOff[1]-uOff[0];
  const PetscInt ax = (PetscInt) PetscRealPart(constants[0]);
  PetscInt       c;

  for (c = 0; c < Nc; ++c) {
    coords[c] = u[c] + constants[c+1]*u[ax];
  }
}

/*@C
  DMPlexShearGeometry - This shears the domain, meaning adds a multiple of the shear coordinate to all other coordinates.

  Not collective

  Input Parameters:
+ dm          - The DM
. direction   - The shear coordinate direction, e.g. 0 is the x-axis
- multipliers - The multiplier m for each direction which is not the shear direction

  Level: intermediate

.seealso: DMPlexRemapGeometry()
@*/
PetscErrorCode DMPlexShearGeometry(DM dm, DMDirection direction, PetscReal multipliers[])
{
  DM             cdm;
  PetscDS        cds;
  PetscObject    obj;
  PetscClassId   id;
  PetscScalar   *moduli;
  const PetscInt dir = (PetscInt) direction;
  PetscInt       dE, d, e;

  PetscFunctionBegin;
  CHKERRQ(DMGetCoordinateDM(dm, &cdm));
  CHKERRQ(DMGetCoordinateDim(dm, &dE));
  CHKERRQ(PetscMalloc1(dE+1, &moduli));
  moduli[0] = dir;
  for (d = 0, e = 0; d < dE; ++d) moduli[d+1] = d == dir ? 0.0 : (multipliers ? multipliers[e++] : 1.0);
  CHKERRQ(DMGetDS(cdm, &cds));
  CHKERRQ(PetscDSGetDiscretization(cds, 0, &obj));
  CHKERRQ(PetscObjectGetClassId(obj, &id));
  if (id != PETSCFE_CLASSID) {
    Vec           lCoords;
    PetscSection  cSection;
    PetscScalar  *coords;
    PetscInt      vStart, vEnd, v;

    CHKERRQ(DMPlexGetDepthStratum(dm, 0, &vStart, &vEnd));
    CHKERRQ(DMGetCoordinateSection(dm, &cSection));
    CHKERRQ(DMGetCoordinatesLocal(dm, &lCoords));
    CHKERRQ(VecGetArray(lCoords, &coords));
    for (v = vStart; v < vEnd; ++v) {
      PetscReal ds;
      PetscInt  off, c;

      CHKERRQ(PetscSectionGetOffset(cSection, v, &off));
      ds   = PetscRealPart(coords[off+dir]);
      for (c = 0; c < dE; ++c) coords[off+c] += moduli[c]*ds;
    }
    CHKERRQ(VecRestoreArray(lCoords, &coords));
  } else {
    CHKERRQ(PetscDSSetConstants(cds, dE+1, moduli));
    CHKERRQ(DMPlexRemapGeometry(dm, 0.0, f0_shear));
  }
  CHKERRQ(PetscFree(moduli));
  PetscFunctionReturn(0);
}