in UVAtlas/geodesics/ExactOneToAll.cpp [784:1084]
void CExactOneToAll::IntersectWindow(EdgeWindow* pExistingWindow,
EdgeWindow* pNewWindow,
bool* pExistingWindowChanged,
bool* pNewWindowChanged,
bool* pExistingWindowNotAvailable,
bool* pNewWindowNotAvailable)
{
memset(&m_NewExistingWindow, 0, sizeof(EdgeWindow));
memset(&m_AnotherNewWindow, 0, sizeof(EdgeWindow));
if (pNewWindow->b1 <= pNewWindow->b0)
return;
// flags that both existing window and new window have not yet been changed
*pExistingWindowChanged = false;
*pNewWindowChanged = false;
*pExistingWindowNotAvailable = false;
*pNewWindowNotAvailable = false;
// although the existing window and the new window are on the same edge of the mesh,
// their b0 may count from different edge vertices (out from the two edge vertex)
// if this is the case, adjust so that both window's b0 count from the same edge vertex
// also, after this if statement, all the windows on this edge should be count from the same vertex of edge (because the new window will be adjusted correspond to all the existing one)
if (pExistingWindow->dwMarkFromEdgeVertexIdx != pNewWindow->dwMarkFromEdgeVertexIdx)
{
pNewWindow->dwMarkFromEdgeVertexIdx = pExistingWindow->dwMarkFromEdgeVertexIdx;
pNewWindow->pMarkFromEdgeVertex = pExistingWindow->pMarkFromEdgeVertex;
std::swap(pNewWindow->d0, pNewWindow->d1);
std::swap(pNewWindow->b0, pNewWindow->b1);
pNewWindow->b0 = std::max<double>(pNewWindow->pEdge->dEdgeLength - pNewWindow->b0, 0);
if (pNewWindow->b0 < double(FLT_EPSILON))
{
pNewWindow->b0 = 0;
}
pNewWindow->b1 = pNewWindow->pEdge->dEdgeLength - pNewWindow->b1;
pNewWindow->dv2Src.x = pNewWindow->pEdge->dEdgeLength - pNewWindow->dv2Src.x;
}
double a = std::min(std::min(std::min(pExistingWindow->b0, pExistingWindow->b1), pNewWindow->b0), pNewWindow->b1);
double b = std::max(std::max(std::max(pExistingWindow->b0, pExistingWindow->b1), pNewWindow->b0), pNewWindow->b1);
// compute the intersection length
double IntersectionLength =
(pExistingWindow->b1 - pExistingWindow->b0 + pNewWindow->b1 - pNewWindow->b0) -
(b - a);
// no intersection
if (IntersectionLength <= 0)
{
return;
}
// the "pseudo source pt" of the existing window and new window
DVector2 ExistingWindowSrc;
DVector2 NewWindowSrc;
ExistingWindowSrc = pExistingWindow->dv2Src;
NewWindowSrc = pNewWindow->dv2Src;
// the new window is almost the same as the existing one, simply drop the new window
if (SquredD2Dist(ExistingWindowSrc, NewWindowSrc) < double(FLT_EPSILON) &&
fabs(pExistingWindow->b0 - pNewWindow->b0) < double(FLT_EPSILON) &&
fabs(pExistingWindow->b1 - pNewWindow->b1) < double(FLT_EPSILON) &&
fabs(pExistingWindow->dPseuSrcToSrcDistance - pNewWindow->dPseuSrcToSrcDistance) < double(FLT_EPSILON))
{
*pNewWindowChanged = true;
*pNewWindowNotAvailable = true;
return;
}
const double dErrorOverlapLength = 0.00001;
// the new window is within the existing window
if (pNewWindow->b0 > pExistingWindow->b0&& pNewWindow->b1 < pExistingWindow->b1)
{
if (pNewWindow->b0 - pExistingWindow->b0 > dErrorOverlapLength)
{
m_NewExistingWindow.b0 = pExistingWindow->b0;
m_NewExistingWindow.b1 = pNewWindow->b0;
m_NewExistingWindow.dv2Src = pExistingWindow->dv2Src;
m_NewExistingWindow.d0 = pExistingWindow->d0;
m_NewExistingWindow.SetEdgeIdx(m_EdgeList, pExistingWindow->dwEdgeIdx);
m_NewExistingWindow.SetFaceIdxPropagatedFrom(m_FaceList, pExistingWindow->dwFaceIdxPropagatedFrom);
m_NewExistingWindow.SetMarkFromEdgeVertexIdx(m_VertexList, pExistingWindow->dwMarkFromEdgeVertexIdx);
m_NewExistingWindow.SetPseuSrcVertexIdx(m_VertexList, pExistingWindow->dwPseuSrcVertexIdx);
m_NewExistingWindow.d1 = sqrt(SquredD2Dist(DVector2(m_NewExistingWindow.b1, 0), m_NewExistingWindow.dv2Src));
m_NewExistingWindow.dPseuSrcToSrcDistance = pExistingWindow->dPseuSrcToSrcDistance;
m_NewExistingWindow.ksi = pExistingWindow->ksi;
m_NewExistingWindow.pEdgePropagatedFrom = pExistingWindow->pEdgePropagatedFrom;
pExistingWindow->b0 = pNewWindow->b0;
pExistingWindow->d0 = sqrt(SquredD2Dist(DVector2(pExistingWindow->b0, 0), ExistingWindowSrc));
*pExistingWindowChanged = true;
}
else
{
pExistingWindow->b0 = pNewWindow->b0;
pExistingWindow->d0 = sqrt(SquredD2Dist(DVector2(pExistingWindow->b0, 0), ExistingWindowSrc));
*pExistingWindowChanged = true;
}
}
// the existing window is within the new window
if (pExistingWindow->b0 > pNewWindow->b0&& pExistingWindow->b1 < pNewWindow->b1)
{
if (pExistingWindow->b0 - pNewWindow->b0 > dErrorOverlapLength)
{
m_AnotherNewWindow.b0 = pNewWindow->b0;
m_AnotherNewWindow.b1 = pExistingWindow->b0;
m_AnotherNewWindow.dv2Src = pNewWindow->dv2Src;
m_AnotherNewWindow.d0 = pNewWindow->d0;
m_AnotherNewWindow.SetEdgeIdx(m_EdgeList, pNewWindow->dwEdgeIdx);
m_AnotherNewWindow.SetFaceIdxPropagatedFrom(m_FaceList, pNewWindow->dwFaceIdxPropagatedFrom);
m_AnotherNewWindow.SetMarkFromEdgeVertexIdx(m_VertexList, pNewWindow->dwMarkFromEdgeVertexIdx);
m_AnotherNewWindow.SetPseuSrcVertexIdx(m_VertexList, pNewWindow->dwPseuSrcVertexIdx);
m_AnotherNewWindow.d1 = sqrt(SquredD2Dist(DVector2(m_AnotherNewWindow.b1, 0), m_AnotherNewWindow.dv2Src));
m_AnotherNewWindow.dPseuSrcToSrcDistance = pNewWindow->dPseuSrcToSrcDistance;
m_AnotherNewWindow.ksi = pNewWindow->ksi;
m_AnotherNewWindow.pEdgePropagatedFrom = pNewWindow->pEdgePropagatedFrom;
pNewWindow->b0 = pExistingWindow->b0;
pNewWindow->d0 = sqrt(SquredD2Dist(DVector2(pNewWindow->b0, 0), NewWindowSrc));
*pNewWindowChanged = true;
}
else
{
pNewWindow->b0 = pExistingWindow->b0;
pNewWindow->d0 = sqrt(SquredD2Dist(DVector2(pNewWindow->b0, 0), NewWindowSrc));
*pNewWindowChanged = true;
}
}
// the position of the intersection's start point
// there are two possibilities:
// the intersection starts from pExistingWindow->b0 or
// the intersection starts from pNewWindow->b0
double IntersectionStart;
bool bStartFromNewWindowB0 = false;
// intersection is from pNewWindow->b0 up to length IntersectionLength
if (pNewWindow->b0 > pExistingWindow->b0&& pNewWindow->b0 < pExistingWindow->b1)
{
IntersectionStart = pNewWindow->b0;
bStartFromNewWindowB0 = true;
}
// intersection is from pExistingWindow->b0 up to length IntersectionLength
else if (pExistingWindow->b0 > pNewWindow->b0&& pExistingWindow->b0 < pNewWindow->b1)
{
IntersectionStart = pExistingWindow->b0;
bStartFromNewWindowB0 = false;
}
else
// pNewWindow->b0 == pExistingWindow->b0
{
IntersectionStart = pNewWindow->b0;
bStartFromNewWindowB0 = true;
if (pNewWindow->b1 < pExistingWindow->b1)
{
IntersectionStart = pExistingWindow->b0;
bStartFromNewWindowB0 = false;
}
}
// we consider this to be an error overlap, if the overlap is too small
if (IntersectionLength > 0 && IntersectionLength <= dErrorOverlapLength/*0*/)
{
// we adjust the extent of the new window to eliminate the overlap
if (bStartFromNewWindowB0)
{
pNewWindow->b0 += IntersectionLength;
pNewWindow->d0 = sqrt(SquredD2Dist(DVector2(pNewWindow->b0, 0), NewWindowSrc));
if (pNewWindow->b0 >= pNewWindow->b1)
{
*pNewWindowNotAvailable = true;
}
*pNewWindowChanged = true;
return;
}
else
{
pNewWindow->b1 -= IntersectionLength;
pNewWindow->d1 = sqrt(SquredD2Dist(DVector2(pNewWindow->b1, 0), NewWindowSrc));
if (pNewWindow->b0 >= pNewWindow->b1)
{
*pNewWindowNotAvailable = true;
}
*pNewWindowChanged = true;
return;
}
}
bool bNoSolution = false;
bNoSolution = true; // force no solution, in reality, this produces very good results and also reduces process time
if (bNoSolution)
{
// whether the distance function of the new window is larger than that of the existing window everywhere in the intersection
if ((sqrt(SquredD2Dist(DVector2(IntersectionStart + IntersectionLength / 2, 0), NewWindowSrc)) + pNewWindow->dPseuSrcToSrcDistance) >
(sqrt(SquredD2Dist(DVector2(IntersectionStart + IntersectionLength / 2, 0), ExistingWindowSrc)) + pExistingWindow->dPseuSrcToSrcDistance))
{
if (pNewWindow->b0 == pExistingWindow->b0 && pNewWindow->b1 == pExistingWindow->b1)
{
*pNewWindowNotAvailable = true;
*pNewWindowChanged = true;
return;
}
if (!bStartFromNewWindowB0)
{
pNewWindow->b1 -= IntersectionLength;
if (pNewWindow->b1 <= pNewWindow->b0)
{
//assert(false) ;
*pNewWindowNotAvailable = true;
*pNewWindowChanged = true;
return;
}
else
{
pNewWindow->d1 = sqrt(SquredD2Dist(DVector2(pNewWindow->b1, 0), NewWindowSrc));
}
}
else
{
pNewWindow->b0 += IntersectionLength;
if (pNewWindow->b0 >= pNewWindow->b1)
{
//assert(false) ;
*pNewWindowNotAvailable = true;
*pNewWindowChanged = true;
return;
}
else
{
pNewWindow->d0 = sqrt(SquredD2Dist(DVector2(pNewWindow->b0, 0), NewWindowSrc));
}
}
*pNewWindowChanged = true;
}
else
// the distance function of the existing window is larger than that of the new window everywhere in the intersection
{
if (pNewWindow->b0 == pExistingWindow->b0 && pNewWindow->b1 == pExistingWindow->b1)
{
*pExistingWindowNotAvailable = true;
*pExistingWindowChanged = true;
return;
}
if (bStartFromNewWindowB0)
{
pExistingWindow->b1 -= IntersectionLength;
if (pExistingWindow->b1 <= pExistingWindow->b0)
{
//assert(false) ;
*pExistingWindowNotAvailable = true;
*pExistingWindowChanged = true;
}
else
{
pExistingWindow->d1 = sqrt(SquredD2Dist(DVector2(pExistingWindow->b1, 0), ExistingWindowSrc));
}
}
else
{
pExistingWindow->b0 += IntersectionLength;
if (pExistingWindow->b0 >= pExistingWindow->b1)
{
//assert(false) ;
*pExistingWindowNotAvailable = true;
*pExistingWindowChanged = true;
}
else
{
pExistingWindow->d0 = sqrt(SquredD2Dist(DVector2(pExistingWindow->b0, 0), ExistingWindowSrc));
}
}
*pExistingWindowChanged = true;
}
}
}