in UVAtlas/geodesics/ExactOneToAll.cpp [601:781]
void CExactOneToAll::ProcessNewWindow(EdgeWindow* pNewEdgeWindow)
{
std::vector<EdgeWindow> NewWindowsList;
NewWindowsList.push_back(*pNewEdgeWindow);
size_t j = 0;
while (j < NewWindowsList.size())
{
pNewEdgeWindow = &NewWindowsList[j];
size_t i;
bool bExistingWindowChanged, bNewWindowChanged, bExistingWindowNotAvailable, bNewWindowNotAvailable;
EdgeWindow WindowToBeInserted;
bNewWindowNotAvailable = false;
for (i = 0; i < pNewEdgeWindow->pEdge->WindowsList.size(); ++i)
{
TypeEdgeWindowsHeap::item_type* pExistingWindowItem;
bExistingWindowChanged = false;
bNewWindowChanged = false;
bExistingWindowNotAvailable = false;
// get a copy of current window on edge
pExistingWindowItem =
new TypeEdgeWindowsHeap::item_type(
std::min(pNewEdgeWindow->pEdge->WindowsList[i].theWindow.d0, pNewEdgeWindow->pEdge->WindowsList[i].theWindow.d1) + pNewEdgeWindow->pEdge->WindowsList[i].theWindow.dPseuSrcToSrcDistance,
pNewEdgeWindow->pEdge->WindowsList[i].theWindow
);
// the copy of current window on edge is then tested with the new window for intersection
// after this test, the copy is possibly changed
IntersectWindow(&pExistingWindowItem->m_data,
pNewEdgeWindow, &bExistingWindowChanged, &bNewWindowChanged, &bExistingWindowNotAvailable, &bNewWindowNotAvailable);
if (m_NewExistingWindow.b1 - m_NewExistingWindow.b0 > 0) // m_NewExistingWindow is modified in IntersectWindow
WindowToBeInserted = m_NewExistingWindow;
if (m_AnotherNewWindow.b1 - m_AnotherNewWindow.b0 > 0) // m_AnotherNewWindow is modified in IntersectWindow
{
NewWindowsList.push_back(m_AnotherNewWindow);
// new allocations may occur in the above add operation, so pNewEdgeWindow must be reset here
pNewEdgeWindow = &NewWindowsList[j];
}
bool bDontDelete;
bDontDelete = false;
// after the intersection operation, if the existing window has been changed,
// remove the old one from the heap (if it is in heap) and update the one on edge
if (bExistingWindowChanged)
{
// whether the window is in heap
if (pNewEdgeWindow->pEdge->WindowsList[i].pHeapItem)
{
// get the item in heap and remove it from the heap
TypeEdgeWindowsHeap::item_type* pHeapItem = pNewEdgeWindow->pEdge->WindowsList[i].pHeapItem;
m_EdgeWindowsHeap.remove(pHeapItem);
delete pHeapItem;
// if the existing window still available (b0<b1), we insert the updated one into heap again
// and update the one on edge correspondingly
if (!bExistingWindowNotAvailable)
{
pNewEdgeWindow->pEdge->WindowsList[i].theWindow = pExistingWindowItem->m_data;
pExistingWindowItem->m_weight = std::min(pExistingWindowItem->m_data.d0, pExistingWindowItem->m_data.d1) + pExistingWindowItem->m_data.dPseuSrcToSrcDistance;
m_EdgeWindowsHeap.insert(pExistingWindowItem);
pNewEdgeWindow->pEdge->WindowsList[i].pHeapItem = pExistingWindowItem;
bDontDelete = true;
}
else
{
// we set a flag here, that this window on edge is to be removed
pNewEdgeWindow->pEdge->WindowsList[i].pHeapItem = reinterpret_cast<TypeEdgeWindowsHeap::item_type*>(FLAG_INVALID_SIZE_T);
}
}
else
{
// the window is not in heap, so we just update the one on edge
if (!bExistingWindowNotAvailable)
{
pNewEdgeWindow->pEdge->WindowsList[i].theWindow = pExistingWindowItem->m_data;
}
else
pNewEdgeWindow->pEdge->WindowsList[i].pHeapItem = reinterpret_cast<TypeEdgeWindowsHeap::item_type*>(FLAG_INVALID_SIZE_T);
}
}
if (!bDontDelete)
delete pExistingWindowItem;
// if the new window is already unavailable during this iteration, we break ;
if (bNewWindowNotAvailable)
break;
}
i = 0;
while (i < pNewEdgeWindow->pEdge->WindowsList.size())
{
// test the remove flag set above, and erase the invalidated window from this edge
if (reinterpret_cast<size_t>(pNewEdgeWindow->pEdge->WindowsList[i].pHeapItem) == FLAG_INVALID_SIZE_T)
{
pNewEdgeWindow->pEdge->WindowsList.erase(pNewEdgeWindow->pEdge->WindowsList.begin() + ptrdiff_t(i));
}
else
{
++i;
}
}
if (WindowToBeInserted.b1 - WindowToBeInserted.b0 > 0)
{
TypeEdgeWindowsHeap::item_type* pNewWindowItem =
new TypeEdgeWindowsHeap::item_type(std::min(WindowToBeInserted.d0, WindowToBeInserted.d1) + WindowToBeInserted.dPseuSrcToSrcDistance, WindowToBeInserted);
m_EdgeWindowsHeap.insert(pNewWindowItem);
WindowToBeInserted.pEdge->WindowsList.push_back(Edge::WindowListElement(pNewWindowItem, pNewWindowItem->m_data));
// update the geodesic distance on vertices affected by this new window
if (WindowToBeInserted.b0 < 0.01)
{
if ((WindowToBeInserted.d0 + WindowToBeInserted.dPseuSrcToSrcDistance) < WindowToBeInserted.pMarkFromEdgeVertex->dGeoDistanceToSrc)
{
WindowToBeInserted.pMarkFromEdgeVertex->dGeoDistanceToSrc = WindowToBeInserted.d0 + WindowToBeInserted.dPseuSrcToSrcDistance;
WindowToBeInserted.pMarkFromEdgeVertex->dLengthOfWindowEdgeToThisVertex = WindowToBeInserted.b0;
WindowToBeInserted.pMarkFromEdgeVertex->pEdgeReportedGeoDist = WindowToBeInserted.pEdge;
}
}
Vertex* pAnotherPt = WindowToBeInserted.pEdge->GetAnotherVertex(WindowToBeInserted.dwMarkFromEdgeVertexIdx);
if (WindowToBeInserted.b1 > (WindowToBeInserted.pEdge->dEdgeLength - 0.01))
{
if ((WindowToBeInserted.d1 + WindowToBeInserted.dPseuSrcToSrcDistance) < pAnotherPt->dGeoDistanceToSrc)
{
pAnotherPt->dGeoDistanceToSrc = WindowToBeInserted.d1 + WindowToBeInserted.dPseuSrcToSrcDistance;
pAnotherPt->dLengthOfWindowEdgeToThisVertex = WindowToBeInserted.pEdge->dEdgeLength - WindowToBeInserted.b1;
pAnotherPt->pEdgeReportedGeoDist = WindowToBeInserted.pEdge;
}
}
}
// after intersect the new window with all the existing windows on edge, if the new window is still available
// add it to the edge and heap
if (!bNewWindowNotAvailable/*pNewEdgeWindow->b0 < pNewEdgeWindow->b1*/)
{
TypeEdgeWindowsHeap::item_type* pNewWindowItem =
new TypeEdgeWindowsHeap::item_type(std::min(pNewEdgeWindow->d0, pNewEdgeWindow->d1) + pNewEdgeWindow->dPseuSrcToSrcDistance, *pNewEdgeWindow);
m_EdgeWindowsHeap.insert(pNewWindowItem);
pNewEdgeWindow->pEdge->WindowsList.push_back(Edge::WindowListElement(pNewWindowItem, pNewWindowItem->m_data));
// update the geodesic distance on vertices affected by this new window
if (pNewEdgeWindow->b0 < 0.01)
{
if ((pNewEdgeWindow->d0 + pNewEdgeWindow->dPseuSrcToSrcDistance) < pNewEdgeWindow->pMarkFromEdgeVertex->dGeoDistanceToSrc)
{
pNewEdgeWindow->pMarkFromEdgeVertex->dGeoDistanceToSrc = pNewEdgeWindow->d0 + pNewEdgeWindow->dPseuSrcToSrcDistance;
pNewEdgeWindow->pMarkFromEdgeVertex->dLengthOfWindowEdgeToThisVertex = pNewEdgeWindow->b0;
pNewEdgeWindow->pMarkFromEdgeVertex->pEdgeReportedGeoDist = pNewEdgeWindow->pEdge;
}
}
Vertex* pAnotherPt = pNewEdgeWindow->pEdge->GetAnotherVertex(pNewEdgeWindow->dwMarkFromEdgeVertexIdx);
if (pNewEdgeWindow->b1 > (pNewEdgeWindow->pEdge->dEdgeLength - 0.01))
{
if ((pNewEdgeWindow->d1 + pNewEdgeWindow->dPseuSrcToSrcDistance) < pAnotherPt->dGeoDistanceToSrc)
{
pAnotherPt->dGeoDistanceToSrc = pNewEdgeWindow->d1 + pNewEdgeWindow->dPseuSrcToSrcDistance;
pAnotherPt->dLengthOfWindowEdgeToThisVertex = pNewEdgeWindow->pEdge->dEdgeLength - pNewEdgeWindow->b1;
pAnotherPt->pEdgeReportedGeoDist = pNewEdgeWindow->pEdge;
}
}
}
++j;
}
}