18#ifdef MFEM_HAVE_GCC_PRAGMA_DIAGNOSTIC
19#pragma GCC diagnostic push
20#pragma GCC diagnostic ignored "-Wunused-function"
23#ifndef GSLIB_RELEASE_VERSION
24#define GSLIB_RELEASE_VERSION 10007
26#ifdef MFEM_HAVE_GCC_PRAGMA_DIAGNOSTIC
27#pragma GCC diagnostic pop
32#if GSLIB_RELEASE_VERSION >= 10009
33#define CODE_INTERNAL 0
35#define CODE_NOT_FOUND 2
40struct findptsElementPoint_t
42 double x[sDIM], r, oldr, dist2, dist2p, tr;
46struct findptsElementGEdge_t
51struct findptsElementGPT_t
53 double x[sDIM], jac[sDIM*rDIM], hes[sDIM*rDIM];
57using obbox_t = gslib::obbox_t<sDIM>;
72#define CONVERGED_FLAG (1u<<2)
73#define FLAG_MASK 0x07u
78static MFEM_HOST_DEVICE
inline int num_constrained(
const int flags)
80 return ((flags | flags>>1) & 1u);
84static MFEM_HOST_DEVICE
inline int point_index(
const int x)
94static MFEM_HOST_DEVICE
bool reject_prior_step_q(findptsElementPoint_t *out_pt,
95 const double resid[2],
96 const findptsElementPoint_t *
p,
99 const double dist2 = l2norm2<2>(resid);
100 const double decr =
p->dist2 - dist2;
101 const double pred =
p->dist2p;
102 out_pt->x[0] =
p->x[0];
103 out_pt->x[1] =
p->x[1];
105 out_pt->dist2 = dist2;
106 if (decr >= 0.01*pred)
108 if (decr >= 0.9*pred)
110 out_pt->tr =
p->tr*2;
124 double v0 = fabs(
p->r -
p->oldr);
126 out_pt->dist2 =
p->dist2;
128 out_pt->flags =
p->flags>>3;
129 out_pt->dist2p = -HUGE_VAL;
130 if (pred < dist2*tol)
132 out_pt->flags |= CONVERGED_FLAG;
138static MFEM_HOST_DEVICE
inline void newton_edge( findptsElementPoint_t *
const
142 const double resid[2],
144 const findptsElementPoint_t *
const p,
147 const double tr =
p->tr;
148 const double A = jac[0] * jac[0] + jac[1] * jac[1] -
150 const double y = jac[0]*resid[0] + jac[1]*resid[1];
152 const double oldr =
p->r;
153 double dr, newr, tdr, tnewr, v, tv;
154 int new_flags=0, tnew_flags=0;
156#define EVAL(dr) ( (dr*A - 2*y) * dr )
170 if (fabs(dr)<tr && fabs(newr)<1)
173 goto newton_edge_fin;
177 if ((newr=oldr-tr) > -1)
183 newr = -1, dr = -1-oldr, new_flags = flags|1u;
187 if ((tnewr=oldr+tr) < 1)
193 tnewr = 1, tdr = 1-oldr, tnew_flags = flags|2u;
199 newr = tnewr, dr = tdr, v = tv, new_flags = tnew_flags;
207 new_flags |= CONVERGED_FLAG;
211 out_pt->flags = flags | new_flags | ((
p->flags & FLAG_MASK)<<3);
214static MFEM_HOST_DEVICE
void seed_j(
const double *elx[sDIM],
215 const double x[sDIM],
223 for (
int d=0; d<sDIM; ++d)
225 dx[d] = x[d] - elx[d][ir];
227 dist2[ir] = HUGE_VAL;
228 const double dist2_rs = l2norm2(dx);
229 if (dist2[ir]>dist2_rs)
231 dist2[ir] = dist2_rs;
236template<
int T_D1D = 0>
237static void FindPointsEdgeLocal2DKernel(
const int npt,
239 const double dist2tol,
241 const int point_pos_ordering,
242 const double *xElemCoord,
245 const double *boxinfo,
246 const bool obb_check,
248 const double *hashMin,
249 const double *hashFac,
250 unsigned int *hashOffset,
251 unsigned int *
const code_base,
252 unsigned int *
const el_base,
253 double *
const r_base,
254 double *
const dist2_base,
256 const double *lagcoeff,
259 const int MD1 = T_D1D ? T_D1D : DofQuadLimits::MAX_D1D;
260 const int D1D = T_D1D ? T_D1D : pN;
261 const int p_NEL = nel*D1D;
262 MFEM_VERIFY(MD1<=DofQuadLimits::MAX_D1D,
263 "Increase Max allowable polynomial order.");
264 MFEM_VERIFY(pN<=DofQuadLimits::MAX_D1D,
265 "Increase Max allowable polynomial order.");
266 MFEM_VERIFY(D1D!=0,
"Polynomial order not specified.");
267 const int nThreads = D1D*sDIM;
272 constexpr int size1 = 3*MD1 + 7;
274 constexpr int size2 = 2*MD1;
276 constexpr int size3 = MD1*sDIM;
278 MFEM_SHARED findptsElementPoint_t el_pts[2];
279 MFEM_SHARED
double r_workspace[size1];
281 MFEM_SHARED
double constraint_workspace[size2];
283 MFEM_SHARED
double elem_coords[MD1 <= 6 ? size3 : 1];
285 double *r_workspace_ptr = r_workspace;
286 findptsElementPoint_t *fpt, *tmp;
291 int id_x = point_pos_ordering == 0 ? i : i*sDIM;
292 int id_y = point_pos_ordering == 0 ? i+npt : i*sDIM+1;
293 double x_i[2] = {x[id_x], x[id_y]};
295 unsigned int *code_i = code_base + i;
296 double *dist2_i = dist2_base + i;
300 for (
int d=0; d<sDIM; ++d)
302 hash.bnd[d].min = hashMin[d];
303 hash.fac[d] = hashFac[d];
305 hash.hash_n = hash_n;
306 hash.offset = hashOffset;
308 const int hi = hash_index(&hash, x_i);
309 const unsigned int *elp = hash.offset + hash.offset[hi];
310 const unsigned int *
const ele = hash.offset + hash.offset[hi+1];
311 *code_i = CODE_NOT_FOUND;
314 for (; elp!=ele; ++elp)
316 const unsigned int el = *elp;
318 const int n_box_ents = obb_check ? (3*sDIM + sDIM2) : (2*sDIM);
323 for (
int idx = 0; idx < sDIM; ++idx)
325 box.c0[idx] = boxinfo[n_box_ents*el + idx];
326 box.x[idx].min = boxinfo[n_box_ents*el + sDIM + idx];
327 box.x[idx].max = boxinfo[n_box_ents*el + 2*sDIM + idx];
329 for (
int idx = 0; idx < sDIM2; ++idx)
331 box.A[idx] = boxinfo[n_box_ents*el + 3*sDIM + idx];
333 pass_bb = (bbox_test(&box, x_i) >= 0);
337 for (
int d = 0; d < sDIM; ++d)
339 box.x[d].min = boxinfo[n_box_ents*el + d];
340 box.x[d].max = boxinfo[n_box_ents*el + sDIM + d];
342 pass_bb = (AABB_test(&box, x_i) >= 0);
351 MFEM_FOREACH_THREAD(j,x,D1D*sDIM)
353 const int qp = j % D1D;
354 const int d = j / D1D;
355 elem_coords[qp + d*D1D] =
356 xElemCoord[qp + el*D1D + d*p_NEL];
361 const double *elx[sDIM];
362 for (
int d=0; d<sDIM; d++)
364 elx[d] = MD1<= 6 ? &elem_coords[d*D1D] :
365 xElemCoord + d*p_NEL + el*D1D;
370 MFEM_FOREACH_THREAD(j,x,1)
372 fpt->dist2 = HUGE_VAL;
376 MFEM_FOREACH_THREAD(j,x,sDIM)
383 double *dist2_temp = r_workspace_ptr;
384 double *r_temp = dist2_temp + D1D;
385 MFEM_FOREACH_THREAD(j,x,D1D)
387 seed_j(elx, x_i, gll1D, dist2_temp, r_temp, j, D1D);
391 MFEM_FOREACH_THREAD(j,x,1)
393 for (
int ir=0; ir<D1D; ++ir)
395 if (dist2_temp[ir]<fpt->dist2)
397 fpt->dist2 = dist2_temp[ir];
406 MFEM_FOREACH_THREAD(j,x,1)
408 tmp->dist2 = HUGE_VAL;
414 MFEM_FOREACH_THREAD(j,x,sDIM)
416 tmp->x[j] = fpt->x[j];
421 for (
int step=0; step<50; step++)
423 int nc = num_constrained(tmp->flags & FLAG_MASK);
428 double *wt = r_workspace_ptr;
429 double *resid = wt + 3*D1D;
430 double *jac = resid + sDIM;
431 double *hess = jac + sDIM*rDIM;
433 findptsElementGEdge_t edge;
434 for (
int d=0; d<sDIM; ++d)
436 edge.x[d] = constraint_workspace + d*D1D;
438 MFEM_FOREACH_THREAD(j,x,D1D)
440 for (
int d=0; d<sDIM; ++d)
442 edge.x[d][j] = elx[d][j];
448 MFEM_FOREACH_THREAD(j,x,D1D)
450 lag_eval_second_der(wt, tmp->r, j, gll1D,
455 MFEM_FOREACH_THREAD(j,x,sDIM)
457 resid[j] = tmp->x[j];
460 for (
int k=0; k<D1D; ++k)
462 resid[j] -= wt[ k]*edge.x[j][k];
463 jac[j] += wt[D1D+k]*edge.x[j][k];
464 hess[j] += wt[2*D1D+k]*edge.x[j][k];
469 MFEM_FOREACH_THREAD(j,x,1)
471 hess[2] = resid[0]*hess[0] + resid[1]*hess[1];
475 MFEM_FOREACH_THREAD(j,x,1)
477 if (!reject_prior_step_q(fpt, resid, tmp, tol))
479 newton_edge(fpt, jac, hess[2], resid,
480 tmp->flags & FLAG_MASK, tmp, tol);
488 MFEM_FOREACH_THREAD(j,x,1)
490 const int pi = point_index(tmp->flags &
492 const double *wt = wtend + pi*3*D1D;
493 findptsElementGPT_t gpt;
494 for (
int d=0; d<sDIM; ++d)
496 gpt.x[d] = elx[d][pi*(D1D-1)];
499 for (
int k=0; k<D1D; ++k)
501 gpt.jac[d] += wt[D1D +k]*elx[d][k];
502 gpt.hes[d] += wt[2*D1D+k]*elx[d][k];
506 const double *
const pt_x = gpt.x;
507 const double *
const jac = gpt.jac;
508 const double *
const hes = gpt.hes;
509 double resid[sDIM], steep, sr;
510 resid[0] = fpt->x[0] - pt_x[0];
511 resid[1] = fpt->x[1] - pt_x[1];
512 steep = jac[0]*resid[0] + jac[1]*resid[1];
514 if ( !reject_prior_step_q(fpt, resid, tmp, tol) )
518 const double rhess = resid[0]*hes[0] +
520 newton_edge(fpt, jac, rhess,
527 fpt->flags = tmp->flags | CONVERGED_FLAG;
535 if (fpt->flags & CONVERGED_FLAG)
540 MFEM_FOREACH_THREAD(j,x,1)
548 bool converged_internal =
549 ((fpt->flags&FLAG_MASK) == CONVERGED_FLAG) &&
550 (fpt->dist2<dist2tol);
552 if (*code_i == CODE_NOT_FOUND || converged_internal ||
553 fpt->dist2 < *dist2_i)
555 MFEM_FOREACH_THREAD(j,x,1)
558 *code_i = converged_internal ? CODE_INTERNAL : CODE_BORDER;
559 *dist2_i = fpt->dist2;
560 *(r_base+i) = fpt->r;
563 if (converged_internal)
575 int point_pos_ordering,
586 MFEM_VERIFY(
dim==1 &&
spacedim==2,
"Function for 2D edges only");
588 auto pp = point_pos.
Read(use_dev);
595 auto pcode = code.
Write(use_dev);
596 auto pelem = elem.
Write(use_dev);
597 auto pref = ref.
Write(use_dev);
598 auto pdist = dist.
Write(use_dev);
606 FindPointsEdgeLocal2DKernel<2>(npt,
DEV.
newt_tol, dist2tol,
607 pp, point_pos_ordering, pgslm,
610 pcode, pelem, pref, pdist,
614 FindPointsEdgeLocal2DKernel<3>(npt,
DEV.
newt_tol, dist2tol,
615 pp, point_pos_ordering, pgslm,
618 pcode, pelem, pref, pdist,
622 FindPointsEdgeLocal2DKernel<4>(npt,
DEV.
newt_tol, dist2tol,
623 pp, point_pos_ordering, pgslm,
626 pcode, pelem, pref, pdist,
630 FindPointsEdgeLocal2DKernel(npt,
DEV.
newt_tol, dist2tol, pp,
631 point_pos_ordering, pgslm,
634 pcode, pelem, pref, pdist,
647 int point_pos_ordering,
T * ReadWrite(bool on_dev=true)
Shortcut for mfem::ReadWrite(a.GetMemory(), a.Size(), on_dev).
T * Write(bool on_dev=true)
Shortcut for mfem::Write(a.GetMemory(), a.Size(), on_dev).
void FindPointsEdgeLocal2(const Vector &point_pos, int point_pos_ordering, Array< unsigned int > &gsl_code_dev_l, Array< unsigned int > &gsl_elem_dev_l, Vector &gsl_ref_l, Vector &gsl_dist_l, int npt)
FindPoints locally on device for 2D edge elements.
struct mfem::FindPointsGSLIB::DevStruct DEV
virtual const real_t * Read(bool on_dev=true) const
Shortcut for mfem::Read(vec.GetMemory(), vec.Size(), on_dev).
virtual real_t * ReadWrite(bool on_dev=true)
Shortcut for mfem::ReadWrite(vec.GetMemory(), vec.Size(), on_dev).
virtual void UseDevice(bool use_dev) const
Enable execution of Vector operations using the mfem::Device.
virtual real_t * Write(bool on_dev=true)
Shortcut for mfem::Write(vec.GetMemory(), vec.Size(), on_dev).
MFEM_HOST_DEVICE T tr(const tensor< T, n, n > &A)
Returns the trace of a square matrix.
MFEM_HOST_DEVICE double bbox_test(const obbox_t< SDIM > *const b, const double(&x)[SDIM])
MFEM_HOST_DEVICE double l2norm2(const double(&x)[SDIM])
MFEM_HOST_DEVICE int hash_index(const findptsLocalHashData_t< SDIM > *const p, const double(&x)[SDIM])
MFEM_HOST_DEVICE void lag_eval_second_der(double *p0, double x, int i, const double *z, const double *lCoeff, int pN)
MFEM_HOST_DEVICE double AABB_test(const obbox_t< SDIM > *const b, const double(&x)[SDIM])
gslib::obbox_t< DIM > obbox_t
gslib::findptsLocalHashData_t< DIM > findptsLocalHashData_t
void forall_2D(int N, int X, int Y, lambda &&body)
gslib::dbl_range_t dbl_range_t
real_t p(const Vector &x, real_t t)
Array< unsigned int > lh_offset