Brunobkr/llama.cpp_AlgMor24_github

1import {epsilon, splitter, resulterrbound, estimate, vec, sum} from './util.js';2 3const ccwerrboundA = (3 + 16 * epsilon) * epsilon;4const ccwerrboundB = (2 + 12 * epsilon) * epsilon;5const ccwerrboundC = (9 + 64 * epsilon) * epsilon * epsilon;6 7const B = vec(4);8const C1 = vec(8);9const C2 = vec(12);10const D = vec(16);11const u = vec(4);12 13function orient2dadapt(ax, ay, bx, by, cx, cy, detsum) {14    let acxtail, acytail, bcxtail, bcytail;15    let bvirt, c, ahi, alo, bhi, blo, _i, _j, _0, s1, s0, t1, t0, u3;16 17    const acx = ax - cx;18    const bcx = bx - cx;19    const acy = ay - cy;20    const bcy = by - cy;21 22    s1 = acx * bcy;23    c = splitter * acx;24    ahi = c - (c - acx);25    alo = acx - ahi;26    c = splitter * bcy;27    bhi = c - (c - bcy);28    blo = bcy - bhi;29    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);30    t1 = acy * bcx;31    c = splitter * acy;32    ahi = c - (c - acy);33    alo = acy - ahi;34    c = splitter * bcx;35    bhi = c - (c - bcx);36    blo = bcx - bhi;37    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);38    _i = s0 - t0;39    bvirt = s0 - _i;40    B[0] = s0 - (_i + bvirt) + (bvirt - t0);41    _j = s1 + _i;42    bvirt = _j - s1;43    _0 = s1 - (_j - bvirt) + (_i - bvirt);44    _i = _0 - t1;45    bvirt = _0 - _i;46    B[1] = _0 - (_i + bvirt) + (bvirt - t1);47    u3 = _j + _i;48    bvirt = u3 - _j;49    B[2] = _j - (u3 - bvirt) + (_i - bvirt);50    B[3] = u3;51 52    let det = estimate(4, B);53    let errbound = ccwerrboundB * detsum;54    if (det >= errbound || -det >= errbound) {55        return det;56    }57 58    bvirt = ax - acx;59    acxtail = ax - (acx + bvirt) + (bvirt - cx);60    bvirt = bx - bcx;61    bcxtail = bx - (bcx + bvirt) + (bvirt - cx);62    bvirt = ay - acy;63    acytail = ay - (acy + bvirt) + (bvirt - cy);64    bvirt = by - bcy;65    bcytail = by - (bcy + bvirt) + (bvirt - cy);66 67    if (acxtail === 0 && acytail === 0 && bcxtail === 0 && bcytail === 0) {68        return det;69    }70 71    errbound = ccwerrboundC * detsum + resulterrbound * Math.abs(det);72    det += (acx * bcytail + bcy * acxtail) - (acy * bcxtail + bcx * acytail);73    if (det >= errbound || -det >= errbound) return det;74 75    s1 = acxtail * bcy;76    c = splitter * acxtail;77    ahi = c - (c - acxtail);78    alo = acxtail - ahi;79    c = splitter * bcy;80    bhi = c - (c - bcy);81    blo = bcy - bhi;82    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);83    t1 = acytail * bcx;84    c = splitter * acytail;85    ahi = c - (c - acytail);86    alo = acytail - ahi;87    c = splitter * bcx;88    bhi = c - (c - bcx);89    blo = bcx - bhi;90    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);91    _i = s0 - t0;92    bvirt = s0 - _i;93    u[0] = s0 - (_i + bvirt) + (bvirt - t0);94    _j = s1 + _i;95    bvirt = _j - s1;96    _0 = s1 - (_j - bvirt) + (_i - bvirt);97    _i = _0 - t1;98    bvirt = _0 - _i;99    u[1] = _0 - (_i + bvirt) + (bvirt - t1);100    u3 = _j + _i;101    bvirt = u3 - _j;102    u[2] = _j - (u3 - bvirt) + (_i - bvirt);103    u[3] = u3;104    const C1len = sum(4, B, 4, u, C1);105 106    s1 = acx * bcytail;107    c = splitter * acx;108    ahi = c - (c - acx);109    alo = acx - ahi;110    c = splitter * bcytail;111    bhi = c - (c - bcytail);112    blo = bcytail - bhi;113    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);114    t1 = acy * bcxtail;115    c = splitter * acy;116    ahi = c - (c - acy);117    alo = acy - ahi;118    c = splitter * bcxtail;119    bhi = c - (c - bcxtail);120    blo = bcxtail - bhi;121    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);122    _i = s0 - t0;123    bvirt = s0 - _i;124    u[0] = s0 - (_i + bvirt) + (bvirt - t0);125    _j = s1 + _i;126    bvirt = _j - s1;127    _0 = s1 - (_j - bvirt) + (_i - bvirt);128    _i = _0 - t1;129    bvirt = _0 - _i;130    u[1] = _0 - (_i + bvirt) + (bvirt - t1);131    u3 = _j + _i;132    bvirt = u3 - _j;133    u[2] = _j - (u3 - bvirt) + (_i - bvirt);134    u[3] = u3;135    const C2len = sum(C1len, C1, 4, u, C2);136 137    s1 = acxtail * bcytail;138    c = splitter * acxtail;139    ahi = c - (c - acxtail);140    alo = acxtail - ahi;141    c = splitter * bcytail;142    bhi = c - (c - bcytail);143    blo = bcytail - bhi;144    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);145    t1 = acytail * bcxtail;146    c = splitter * acytail;147    ahi = c - (c - acytail);148    alo = acytail - ahi;149    c = splitter * bcxtail;150    bhi = c - (c - bcxtail);151    blo = bcxtail - bhi;152    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);153    _i = s0 - t0;154    bvirt = s0 - _i;155    u[0] = s0 - (_i + bvirt) + (bvirt - t0);156    _j = s1 + _i;157    bvirt = _j - s1;158    _0 = s1 - (_j - bvirt) + (_i - bvirt);159    _i = _0 - t1;160    bvirt = _0 - _i;161    u[1] = _0 - (_i + bvirt) + (bvirt - t1);162    u3 = _j + _i;163    bvirt = u3 - _j;164    u[2] = _j - (u3 - bvirt) + (_i - bvirt);165    u[3] = u3;166    const Dlen = sum(C2len, C2, 4, u, D);167 168    return D[Dlen - 1];169}170 171export function orient2d(ax, ay, bx, by, cx, cy) {172    const detleft = (ay - cy) * (bx - cx);173    const detright = (ax - cx) * (by - cy);174    const det = detleft - detright;175 176    const detsum = Math.abs(detleft + detright);177    if (Math.abs(det) >= ccwerrboundA * detsum) return det;178 179    return -orient2dadapt(ax, ay, bx, by, cx, cy, detsum);180}181 182export function orient2dfast(ax, ay, bx, by, cx, cy) {183    return (ay - cy) * (bx - cx) - (ax - cx) * (by - cy);184}185