in UVAtlas/geodesics/ApproximateOneToAll.cpp [17:373]
void CApproximateOneToAll::CutHeapTopData(EdgeWindow& EdgeWindowOut)
{
for (;;)
{
TypeEdgeWindowsHeap::item_type* pItem = m_EdgeWindowsHeap.cutTop();
uint32_t dwIdxSelf = FLAG_INVALIDDWORD;
for (uint32_t i = 0; i < pItem->m_data.pEdge->WindowsList.size(); ++i)
{
if (!pItem->m_data.pEdge->WindowsList[i].pHeapItem)
{
continue;
}
if (pItem->m_data.pEdge->WindowsList[i].pHeapItem == pItem)
{
// here we get a byproduct, because we actually need the idx of the popped off window itself
dwIdxSelf = i;
// when searching for a window adjacent to the popped off (from the heap) window, skip the window itself on the edge
continue;
}
// in pWindowLeft and pWindowRight, one is the the popped off window itself, the other one is the possible found adjacent window
EdgeWindow* pWindowLeft = &(pItem->m_data);
EdgeWindow* pWindowRight = &(pItem->m_data.pEdge->WindowsList[i].theWindow);
if ((pWindowLeft->b0 == pWindowRight->b1 || pWindowLeft->b1 == pWindowRight->b0) /*&&
(pWindowLeft->dwFaceIdxPropagatedFrom == pWindowRight->dwFaceIdxPropagatedFrom)*/)
{
// found an adjacent window
if (pWindowLeft->b0 == pWindowRight->b1)
{
std::swap(pWindowLeft, pWindowRight);
}
double b1pie = pWindowRight->b1;
double b0pie = pWindowLeft->b0;
double D1 = pWindowRight->dPseuSrcToSrcDistance + SqrtMin0(SquredD2Dist(DVector2(b1pie, 0), pWindowRight->dv2Src));
double D0 = pWindowLeft->dPseuSrcToSrcDistance + SqrtMin0(SquredD2Dist(DVector2(b0pie, 0), pWindowLeft->dv2Src));
if (fabs(D1 - D0) < DBL_EPSILON)
{
continue; // prevent divide-by-zero on very narrow windows
}
double alpha = (b1pie - b0pie) / (D1 - D0);
double beta = (SQR(b0pie) - SQR(b1pie) - SQR(D0) + SQR(D1)) / (2 * (D1 - D0));
double A = SQR(alpha) - 1;
double B = 2 * alpha * (beta - D0) + 2 * b0pie;
double C = SQR(D0 - beta) - SQR(b0pie);
DVector2 ptRes;
bool bTmp;
GetCommonPointOf2Lines(pWindowLeft->dv2Src, DVector2(pWindowLeft->b0, 0),
pWindowRight->dv2Src, DVector2(pWindowRight->b1, 0), ptRes, bTmp);
double sigma = DBL_MAX;
DVector2 spie;
double x1, x2, x3;
x1 = -beta / alpha;
x2 = (D0 - beta) / alpha;
x3 = (D1 - beta) / alpha;
if (alpha < 0)
{
if (x3 > x2)
x2 = x3;
if (x2 > x1)
continue;
}
else
{
if (x3 < x2)
x2 = x3;
if (x1 > x2)
continue;
}
DVector2 spietmp;
spietmp.x = (x1 + x2) * 0.5;
spietmp.y = A * SQR(spietmp.x) + B * spietmp.x + C;
if (spietmp.y < 0)
{
continue;
}
spietmp.y = sqrt(spietmp.y);
DVector2 P0, Q0, P1, Q1;
DVector2Minus(pWindowLeft->dv2Src, DVector2(pWindowLeft->b0, 0), P0);
DVector2Minus(spietmp, DVector2(pWindowLeft->b0, 0), Q0);
DVector2Minus(pWindowRight->dv2Src, DVector2(pWindowRight->b1, 0), P1);
DVector2Minus(spietmp, DVector2(pWindowRight->b1, 0), Q1);
DVector3 tmpv0, tmpv1;
DVector3Cross(DVector3(Q0), DVector3(P0), tmpv0);
DVector3Cross(DVector3(Q1), DVector3(P1), tmpv1);
// spietmp.y must < ptRes.y (if ptRes exists, which means two line segments passed into the following GetCommonPointOf2Lines are not parallel, and ptRes.y is positive)
bTmp = true;
if ((ptRes.x < DBL_MAX) && (ptRes.y > 0))
{
if (spietmp.y > ptRes.y)
bTmp = false;
}
// the new computed pseudosource is within the yellow region
if (((SQN(tmpv0.z) != SQN(tmpv1.z)) || (tmpv0.z == 0) || (tmpv1.z == 0)) && bTmp)
{
sigma = alpha * spietmp.x + beta;
spie = spietmp;
}
if (sigma == DBL_MAX)
{
// this adjacent window cannot fulfill all the criteria listed in the paper, continue to try the next window on edge
continue;
}
double diflargest = 0;
double Dp = DBL_MAX;
for (size_t ca = 0; ca < 6; ++ca)
{
DVector2 tmpp;
tmpp.y = 0;
double tmpdif = 0;
double tmpDp = 0;
switch (ca)
{
case 0:
tmpp.x = pWindowLeft->b0;
tmpDp = pWindowLeft->dPseuSrcToSrcDistance + pWindowLeft->d0;
tmpdif = fabs(sigma + SqrtMin0(SquredD2Dist(spie, tmpp)) - tmpDp);
break;
case 1:
tmpp.x = pWindowLeft->b1;
tmpDp = pWindowLeft->dPseuSrcToSrcDistance + pWindowLeft->d1;
tmpdif = fabs(sigma + SqrtMin0(SquredD2Dist(spie, tmpp)) - tmpDp);
break;
case 2:
tmpp.x = pWindowRight->b0;
tmpDp = pWindowRight->dPseuSrcToSrcDistance + pWindowRight->d0;
tmpdif = fabs(sigma + SqrtMin0(SquredD2Dist(spie, tmpp)) - tmpDp);
break;
case 3:
tmpp.x = pWindowRight->b1;
tmpDp = pWindowRight->dPseuSrcToSrcDistance + pWindowRight->d1;
tmpdif = fabs(sigma + SqrtMin0(SquredD2Dist(spie, tmpp)) - tmpDp);
break;
case 4:
{
double A0 = SQR(spie.y) - SQR(pWindowLeft->dv2Src.y);
double B0 = 2 * (spie.x * SQR(pWindowLeft->dv2Src.y) - pWindowLeft->dv2Src.x * SQR(spie.y));
double C0 = SQR(pWindowLeft->dv2Src.x) * SQR(spie.y) - SQR(spie.x) * SQR(pWindowLeft->dv2Src.y);
if (A0 > double(FLT_EPSILON) || A0 < double(-FLT_EPSILON))
{
double discriminant = SQR(B0) - 4 * A0 * C0;
if (discriminant > 0)
{
tmpp.x = (-B0 + SqrtMin0(discriminant)) / (2 * A0);
if (tmpp.x < pWindowLeft->b0 || tmpp.x > pWindowLeft->b1)
{
tmpp.x = (-B0 - SqrtMin0(discriminant)) / (2 * A0);
if (tmpp.x < pWindowLeft->b0 || tmpp.x > pWindowLeft->b1)
{
continue;
}
}
}
else
{
continue;
}
}
else
{
if (B0 != 0)
{
tmpp.x = -C0 / B0;
if (tmpp.x < pWindowLeft->b0 || tmpp.x > pWindowLeft->b1)
{
continue;
}
}
else
{
continue;
}
}
tmpDp = pWindowLeft->dPseuSrcToSrcDistance + SqrtMin0(SquredD2Dist(pWindowLeft->dv2Src, tmpp));
tmpdif = fabs(sigma + SqrtMin0(SquredD2Dist(spie, tmpp)) - tmpDp);
}
break;
case 5:
{
double A0 = SQR(spie.y) - SQR(pWindowRight->dv2Src.y);
double B0 = 2 * (spie.x * SQR(pWindowRight->dv2Src.y) - pWindowRight->dv2Src.x * SQR(spie.y));
double C0 = SQR(pWindowRight->dv2Src.x) * SQR(spie.y) - SQR(spie.x) * SQR(pWindowRight->dv2Src.y);
if (A0 > double(FLT_EPSILON) || A0 < double(-FLT_EPSILON))
{
double discriminant = SQR(B0) - 4 * A0 * C0;
if (discriminant > 0)
{
tmpp.x = (-B0 + SqrtMin0(discriminant)) / (2 * A0);
if (tmpp.x < pWindowRight->b0 || tmpp.x > pWindowRight->b1)
{
tmpp.x = (-B0 - SqrtMin0(discriminant)) / (2 * A0);
if (tmpp.x < pWindowRight->b0 || tmpp.x > pWindowRight->b1)
{
continue;
}
}
}
else
{
continue;
}
}
else
{
if (B0 != 0)
{
tmpp.x = -C0 / B0;
if (tmpp.x < pWindowRight->b0 || tmpp.x > pWindowRight->b1)
{
continue;
}
}
else
{
continue;
}
}
tmpDp = pWindowRight->dPseuSrcToSrcDistance + SqrtMin0(SquredD2Dist(pWindowRight->dv2Src, tmpp));
tmpdif = fabs(sigma + SqrtMin0(SquredD2Dist(spie, tmpp)) - tmpDp);
}
break;
}
if (tmpdif > diflargest)
{
diflargest = tmpdif;
Dp = tmpDp;
}
}
double ksi;
ksi = std::max(pWindowRight->ksi, pWindowLeft->ksi) + diflargest;
//double ksi = 0.0;
if (ksi / Dp < 0.01 && diflargest / Dp < 0.01 * 0.1)
{
// allow the merge
if (dwIdxSelf == FLAG_INVALIDDWORD)
{
// the idx of the popped off window is not yet set, so search for it here
// we only need to search from i + 1 (rather than from 0), because the previous ones have already been searched
for (uint32_t t = i + 1; t < pItem->m_data.pEdge->WindowsList.size(); ++t)
if (pItem->m_data.pEdge->WindowsList[t].pHeapItem == pItem)
{
dwIdxSelf = t;
break;
}
}
// remove the found adjacent window from the heap and from the edge it is on
m_EdgeWindowsHeap.remove(pItem->m_data.pEdge->WindowsList[i].pHeapItem);
delete pItem->m_data.pEdge->WindowsList[i].pHeapItem;
pItem->m_data.pEdge->WindowsList.erase(pItem->m_data.pEdge->WindowsList.begin() + ptrdiff_t(i));
if (dwIdxSelf > i)
{
--dwIdxSelf;
}
EdgeWindow* pTheWindow = &(pItem->m_data.pEdge->WindowsList[dwIdxSelf].theWindow);
pTheWindow->b0 = b0pie;
pTheWindow->b1 = b1pie;
pTheWindow->dPseuSrcToSrcDistance = sigma;
pTheWindow->dv2Src = spie;
pTheWindow->d0 = SqrtMin0(SquredD2Dist(DVector2(b0pie, 0), spie));
pTheWindow->d1 = SqrtMin0(SquredD2Dist(DVector2(b1pie, 0), spie));
pTheWindow->ksi = ksi;
pTheWindow->dwPseuSrcVertexIdx = FLAG_INVALIDDWORD;
pTheWindow->pPseuSrcVertex = nullptr;
/*pTheWindow->pHeapItem = nullptr ;
EdgeWindowOut = *pTheWindow ;
delete pItem ;
return ;*/
pItem->m_data.pEdge->WindowsList[dwIdxSelf].pHeapItem =
new TypeEdgeWindowsHeap::item_type(std::min(pTheWindow->d0, pTheWindow->d1) + pTheWindow->dPseuSrcToSrcDistance, *pTheWindow);
m_EdgeWindowsHeap.insert(pItem->m_data.pEdge->WindowsList[dwIdxSelf].pHeapItem);
delete pItem;
// continue to pop the next window in heap and test whether any merge is possible
goto l_outter_while_again;
}
}
}
if (dwIdxSelf == FLAG_INVALIDDWORD)
{
for (size_t i = 0; i < pItem->m_data.pEdge->WindowsList.size(); ++i)
{
if (pItem->m_data.pEdge->WindowsList[i].pHeapItem == pItem)
{
pItem->m_data.pEdge->WindowsList[i].pHeapItem = nullptr;
break;
}
}
EdgeWindowOut = pItem->m_data;
delete pItem;
return;
}
pItem->m_data.pEdge->WindowsList[dwIdxSelf].pHeapItem = nullptr;
EdgeWindowOut = pItem->m_data;
delete pItem;
return;
l_outter_while_again:
;
}
}