in SpatialUnderstanding/Src/PlaySpace/PlaySpace_Mesh_W.cpp [2359:2942]
void Playspace_Mesh::SimplifyTri2(Float cosMaxErr, Bool _ignoreVirtual /*= TRUE*/, Bool _ignoreExternal /*= TRUE*/)
{
if (IsEmpty())
return;
ComputePointsLinks();
InvalidateFaceToolNormal();
InvalidatePointsToolNormal();
HS8DA ptsTab;
HS8DA faces;
HugeDynArray_Z<Vec3f, 4096, FALSE, FALSE> faceNormals;
S32 nbPass = 1; // JY: peut-etre les passer en params ?
S32 maxNeighbours = 8; //
S32 triangles[96];
S32 nbTri0, nbTri1, nbTriTotal;
vItem list[32]; // la taille doit IMPERATIVEMENT etre sup�rieure � (maxNeighbours + 2)
vItem *lstPtr, *lstNxt, *lstPrv, *head[2], *tail[2];
S32 nb[2], currPoint, lastPoint, currState, currFace;
Bool virt[2], ext[2]; // are the clusters virtual or external ?
Bool toggled = FALSE, normOk[2];
Vec3f center, v1, v2, normal[2];
S32* ptr, *ptr2;
S32 nbFaces = m_TabQuad.GetSize();
Playspace_Mesh::Face* pFaceIdx = m_TabQuad.GetArrayPtr();
S32 nbPoints = m_TabPoints.GetSize();
Vec3f* TabPoints = m_TabPoints.GetArrayPtr();
ptsTab.SetSize(nbPoints, TRUE);
S8* pPtsTab = ptsTab.GetArrayPtr();
memset(pPtsTab, 0, nbPoints * sizeof(S8));
faces.SetSize(nbFaces, TRUE);
S8* pFaces = faces.GetArrayPtr();
memset(pFaces, 0, nbFaces * sizeof(S8));
faceNormals.SetSize(nbFaces, TRUE);
Vec3f* pFaceNormals = faceNormals.GetArrayPtr();
for (S32 i = 0; i < nbFaces; i++)
{
ptr = pFaceIdx[i].TabPoints;
v1 = (TabPoints[ptr[1]] - TabPoints[ptr[0]]) ^ (TabPoints[ptr[2]] - TabPoints[ptr[0]]);
Float len2 = v1.GetNorm2();
if (len2 < (1.0e-6f * 1.0e-6f))
pFaces[i] = 126;
else
pFaceNormals[i] = v1 * InvSqrt(1.0f, len2); // INVSQRT
}
for (S32 pass = 0; pass < nbPass; pass++)
{
for (S32 pt = 0; pt < nbPoints; pt++)
{
if (pPtsTab[pt])
goto Next_point_label; // point already removed
center = TabPoints[pt];
PointsLinks& ptLinks = m_TabPointsLinks[pt];
S32 nbNeighbours = ptLinks.GetNbFaces();
if ((nbNeighbours > 2) && (nbNeighbours <= maxNeighbours))
{
S32 numFace = ptLinks.GetFace(0);
ptr = pFaceIdx[numFace].TabPoints;
head[0] = list;
tail[0] = list + 1;
if (pt == ptr[0])
{
list->point = ptr[1];
tail[0]->point = ptr[2];
}
else if (pt == ptr[1])
{
list->point = ptr[2];
tail[0]->point = ptr[0];
}
else
{
list->point = ptr[0];
tail[0]->point = ptr[1];
}
list->next = tail[0];
tail[0]->prev = list;
list->radius = TabPoints[list->point] - center;
tail[0]->radius = TabPoints[tail[0]->point] - center;
nb[0] = 2;
nb[1] = 0;
lastPoint = tail[0]->point;
lstNxt = tail[0] + 1;
ext[0] = pFaceIdx[numFace].IsExternal;
virt[0] = pFaceIdx[numFace].IsVirtual;
toggled = FALSE;
if (pFaces[numFace] != 126)
{
normal[0] = pFaceNormals[numFace];
normOk[0] = TRUE;
}
else
normOk[0] = FALSE;
normOk[1] = FALSE;
currState = 0;
for (S32 i = 1; i < nbNeighbours; i++)
{
currPoint = -1;
for (S32 j = 0; j < nbNeighbours; j++)
{
currFace = ptLinks.GetFace(j);
ptr = pFaceIdx[currFace].TabPoints;
if ((ptr[0] == pt) && (ptr[1] == lastPoint))
{
currPoint = ptr[2];
break;
}
else if ((ptr[1] == pt) && (ptr[2] == lastPoint))
{
currPoint = ptr[0];
break;
}
else if ((ptr[2] == pt) && (ptr[0] == lastPoint))
{
currPoint = ptr[1];
break;
}
}
//if (pFaces[currFace] == 126)
// goto Next_point_label;
if (currPoint == -1)
goto Next_point_label; // Rejection => point on border
if (((pFaces[currFace] != 126) && normOk[currState] && ((normal[currState] * pFaceNormals[currFace]) < cosMaxErr)) || (!_ignoreVirtual && (virt[currState] != pFaceIdx[currFace].IsVirtual)) || (!_ignoreExternal && (ext[currState] != pFaceIdx[currFace].IsExternal)))
{
if (toggled)
goto Next_point_label; // Rejection => more than two clusters
if (currState == 0)
{
currState++;
lstNxt->point = lastPoint;
lstNxt->radius = TabPoints[lastPoint] - center;
head[1] = tail[1] = lstNxt++;
nb[1]++;
virt[1] = pFaceIdx[currFace].IsVirtual;
ext[1] = pFaceIdx[currFace].IsExternal;
}
else
{
if (((pFaces[currFace] != 126) && normOk[0] && ((normal[0] * pFaceNormals[currFace]) < cosMaxErr)) || (!_ignoreVirtual && (virt[0] != pFaceIdx[currFace].IsVirtual)) || (!_ignoreExternal && (ext[0] != pFaceIdx[currFace].IsExternal)))
goto Next_point_label; // Rejection => more than two clusters
else
{
currState--;
lstNxt->point = lastPoint;
lstNxt->radius = TabPoints[lastPoint] - center;
tail[0]->next = lstNxt;
lstNxt->prev = tail[0];
tail[0] = lstNxt++;
nb[0]++;
toggled = TRUE;
}
}
}
if ((pFaces[currFace] != 126) && !normOk[currState])
{
normal[currState] = pFaceNormals[currFace];
normOk[currState] = TRUE;
}
lstNxt->point = lastPoint = currPoint;
lstNxt->radius = TabPoints[lastPoint] - center;
tail[currState]->next = lstNxt;
lstNxt->prev = tail[currState];
tail[currState] = lstNxt++;
nb[currState]++;
}
if (currState == 0)
{
tail[0] = tail[0]->prev; // because we have already put the first point
nb[0]--;
}
tail[0]->next = list;
list->prev = tail[0];
if (nb[1])
{
tail[1]->next = head[1];
head[1]->prev = tail[1];
}
if ((currPoint != list->point) || !normOk[0] || ((nb[1] != 0) && !normOk[1])) // Rejection => pathological cases (not 2-manifold or only degenerate triangles)
goto Next_point_label;
if ((nb[0] == 2) && (nb[1] == nbNeighbours))
{
head[0] = head[1];
nb[0] = nb[1];
nb[1] = 0;
normal[0] = normal[1];
ext[0] = ext[1];
virt[0] = virt[1];
}
if ((nb[1] == 2) && (nb[0] == nbNeighbours))
nb[1] = 0;
if ((nb[0] == 2) || (nb[1] == 2)) // Rejection => pathological cases (like branching point on Riemann surface)
goto Next_point_label;
lstPtr = head[0];
lstNxt = NULL;
while (lstNxt != head[0])
{
lstNxt = lstPtr->next;
lstPtr->edge = lstNxt->radius - lstPtr->radius;
lstPtr = lstNxt;
}
lstPtr = head[0];
lstNxt = NULL;
while (lstNxt != head[0])
{
lstPrv = lstPtr->prev;
lstNxt = lstPtr->next;
Vec3f v1 = (lstPrv->edge ^ lstPtr->edge);
v1.ANormalize();
lstPtr->crossEdge = v1 * normal[0];
lstPtr->dot = lstPrv->edge * lstPtr->edge;
v1 = (lstPrv->radius ^ lstNxt->radius);
v1.ANormalize();
lstPtr->crossCenter = v1 * normal[0];
lstPtr = lstNxt;
}
nbTri1 = 0;
if (DecomposePolyedra(head[0], nb[0], normal[0], triangles, nbTri0))
{
if (nb[1])
{
lstPtr = head[1];
lstNxt = NULL;
while (lstNxt != head[1])
{
lstNxt = lstPtr->next;
lstPtr->edge = lstNxt->radius - lstPtr->radius;
lstPtr = lstNxt;
}
lstPtr = head[1];
lstNxt = NULL;
while (lstNxt != head[1])
{
lstPrv = lstPtr->prev;
lstNxt = lstPtr->next;
Vec3f v2 = (lstPrv->edge ^ lstPtr->edge);
v2.ANormalize();
lstPtr->crossEdge = v2 * normal[1];
lstPtr->dot = lstPrv->edge * lstPtr->edge;
v2 = (lstPrv->radius ^ lstNxt->radius);
v2.ANormalize();
lstPtr->crossCenter = v2 * normal[1];
lstPtr = lstNxt;
}
if (!DecomposePolyedra(head[1], nb[1], normal[1], triangles + (3 * nbTri0), nbTri1)) // Rejection => decompose polyedra returned FALSE
goto Next_point_label;
}
nbTriTotal = nbTri0 + nbTri1;
EXCEPTIONC_Z((nbTriTotal == (nbNeighbours - 2)), "Le mesh est dans un espace non euclidien ou bien il y a un gros bug dans DecomposePolyedra...");
if (nbTriTotal != (nbNeighbours - 2)) // on est dans la 4e dimension...
goto Next_point_label;
ptr2 = triangles;
for (S32 j = 0; j < nbTriTotal; j++)
{
S32 numFace = ptLinks.GetFace(j);
ptr = pFaceIdx[numFace].TabPoints;
if (pt != ptr[0])
m_TabPointsLinks[ptr[0]].RemoveFace(numFace);
if (pt != ptr[1])
m_TabPointsLinks[ptr[1]].RemoveFace(numFace);
if (pt != ptr[2])
m_TabPointsLinks[ptr[2]].RemoveFace(numFace);
ptr[0] = ptr2[0];
ptr[1] = ptr2[1];
ptr[2] = ptr2[2];
ptr[3] = ptr2[2];
m_TabPointsLinks[ptr2[0]].AddFace(numFace);
m_TabPointsLinks[ptr2[1]].AddFace(numFace);
m_TabPointsLinks[ptr2[2]].AddFace(numFace);
if (_ignoreVirtual)
pFaceIdx[numFace].IsVirtual = FALSE;
else
pFaceIdx[numFace].IsVirtual = (j < nbTri0 ? virt[0] : virt[1]);
if (_ignoreExternal)
pFaceIdx[numFace].IsExternal = FALSE;
else
pFaceIdx[numFace].IsExternal = (j < nbTri0 ? ext[0] : ext[1]);
v1 = (TabPoints[ptr[1]] - TabPoints[ptr[0]]) ^ (TabPoints[ptr[2]] - TabPoints[ptr[0]]);
Float len2 = v1.GetNorm2();
if (len2 < (1.0e-6f * 1.0e-6f))
pFaces[numFace] = 126;
else
pFaceNormals[numFace] = v1 * InvSqrt(1.0f, len2); // INVSQRT
ptr2 += 3;
}
numFace = ptLinks.GetFace(nbTriTotal);
ptr = pFaceIdx[numFace].TabPoints;
if (pt != ptr[0])
m_TabPointsLinks[ptr[0]].RemoveFace(numFace);
if (pt != ptr[1])
m_TabPointsLinks[ptr[1]].RemoveFace(numFace);
if (pt != ptr[2])
m_TabPointsLinks[ptr[2]].RemoveFace(numFace);
pFaces[numFace] = 127;
numFace = ptLinks.GetFace(nbTriTotal + 1);
ptr = pFaceIdx[numFace].TabPoints;
if (pt != ptr[0])
m_TabPointsLinks[ptr[0]].RemoveFace(numFace);
if (pt != ptr[1])
m_TabPointsLinks[ptr[1]].RemoveFace(numFace);
if (pt != ptr[2])
m_TabPointsLinks[ptr[2]].RemoveFace(numFace);
pFaces[numFace] = 127;
pPtsTab[pt] = 1;
}
}
else
{
if (nbNeighbours == 2)
{
S32 p0, p1, p2, p3, p4;
S32 numFace0 = ptLinks.GetFace(0);
S32 numFace1 = ptLinks.GetFace(1);
if (!_ignoreVirtual && (pFaceIdx[numFace0].IsVirtual != pFaceIdx[numFace1].IsVirtual))
goto Next_point_label;
if (!_ignoreExternal && (pFaceIdx[numFace0].IsExternal != pFaceIdx[numFace1].IsExternal))
goto Next_point_label;
ptr = pFaceIdx[numFace0].TabPoints;
if (pt == ptr[0])
{
p0 = ptr[1];
p1 = ptr[2];
}
else if (pt == ptr[1])
{
p0 = ptr[2];
p1 = ptr[0];
}
else
{
p0 = ptr[0];
p1 = ptr[1];
}
ptr2 = pFaceIdx[numFace1].TabPoints;
if (pt == ptr2[0])
{
p2 = ptr2[1];
p3 = ptr2[2];
}
else if (pt == ptr2[1])
{
p2 = ptr2[2];
p3 = ptr2[0];
}
else
{
p2 = ptr2[0];
p3 = ptr2[1];
}
if (p1 == p2)
{
p2 = p3;
}
else if (p0 == p3)
{
p4 = p1;
p1 = p0;
p0 = p2;
p2 = p4;
}
else
goto Next_point_label;
if ((p0 == p1) || (p0 == p2) || (p1 == p2))
goto Next_point_label;
v1 = TabPoints[p0] - center;
v1.Normalize();
v2 = TabPoints[p2] - center;
Vec3f delta = v2 - v1 * (v1 * v2);
if (delta.GetNorm2() < (2.0e-2f * 2.0e-2f))
{
if (pt != ptr[0])
m_TabPointsLinks[ptr[0]].RemoveFace(numFace0);
if (pt != ptr[1])
m_TabPointsLinks[ptr[1]].RemoveFace(numFace0);
if (pt != ptr[2])
m_TabPointsLinks[ptr[2]].RemoveFace(numFace0);
ptr[0] = p0;
ptr[1] = p1;
ptr[2] = p2;
ptr[3] = p2;
m_TabPointsLinks[p0].AddFace(numFace0);
m_TabPointsLinks[p1].AddFace(numFace0);
m_TabPointsLinks[p2].AddFace(numFace0);
if (_ignoreVirtual)
pFaceIdx[numFace0].IsVirtual = FALSE;
if (_ignoreExternal)
pFaceIdx[numFace0].IsExternal = FALSE;
v1 = (TabPoints[p1] - TabPoints[p0]) ^ (TabPoints[p2] - TabPoints[p0]);
Float len2 = v1.GetNorm2();
if (len2 < (1.0e-6f * 1.0e-6f))
pFaces[numFace0] = 126;
else
pFaceNormals[numFace0] = v1 * InvSqrt(1.0f, len2); // INVSQRT
if (pt != ptr2[0])
m_TabPointsLinks[ptr2[0]].RemoveFace(numFace1);
if (pt != ptr2[1])
m_TabPointsLinks[ptr2[1]].RemoveFace(numFace1);
if (pt != ptr2[2])
m_TabPointsLinks[ptr2[2]].RemoveFace(numFace1);
pFaces[numFace1] = 127;
pPtsTab[pt] = 1;
}
}
}
Next_point_label:
;
}
}
HS32DA redir;
redir.SetSize(nbPoints, TRUE);
S32* pRedir = redir.GetArrayPtr();
S32 idx1 = 0;
S32 idx2 = nbPoints - 1;
while (idx1 < idx2)
{
if (pPtsTab[idx1]) // if point 'idx1' is removed
{
while ((idx1 < idx2) && pPtsTab[idx2]) // get the last non removed point
idx2--;
if (idx1 == idx2)
break;
TabPoints[idx1] = TabPoints[idx2]; // and fills the hole
pRedir[idx2] = idx1;
idx2--;
}
else
pRedir[idx1] = idx1;
idx1++;
}
if (!pPtsTab[idx1])
{
pRedir[idx1] = idx1;
idx1++;
}
S32 nbPoints2 = idx1;
idx1 = 0;
idx2 = nbFaces - 1;
while (idx1 < idx2)
{
ptr = pFaceIdx[idx1].TabPoints;
EXCEPTIONC_Z((ptr[0] < nbPoints) && (ptr[1] < nbPoints) && (ptr[2] < nbPoints), "BIM !!!!!");
if (pFaces[idx1] == 127) // if face 'idx1' is removed
{
while ((idx1 < idx2) && (pFaces[idx2] == 127)) // get the last non removed face
idx2--;
if (idx1 == idx2)
break;
ptr2 = pFaceIdx[idx2].TabPoints;
EXCEPTIONC_Z((ptr2[0] < nbPoints) && (ptr2[1] < nbPoints) && (ptr2[2] < nbPoints), "BIM !!!!!");
EXCEPTIONC_Z((pRedir[ptr2[0]] >= 0) && (pRedir[ptr2[0]] < nbPoints2) && (pRedir[ptr2[1]] >= 0) && (pRedir[ptr2[1]] < nbPoints2) && (pRedir[ptr2[2]] >= 0) && (pRedir[ptr2[2]] < nbPoints2), "BIM dans les points !!!!");
ptr[0] = pRedir[ptr2[0]];
ptr[1] = pRedir[ptr2[1]];
ptr[2] = pRedir[ptr2[2]];
ptr[3] = ptr[2];
pFaceIdx[idx1].IsVirtual = pFaceIdx[idx2].IsVirtual;
pFaceIdx[idx1].IsExternal = pFaceIdx[idx2].IsExternal;
idx2--;
}
else
{
EXCEPTIONC_Z((pRedir[ptr[0]] >= 0) && (pRedir[ptr[0]] < nbPoints2) && (pRedir[ptr[1]] >= 0) && (pRedir[ptr[1]] < nbPoints2) && (pRedir[ptr[2]] >= 0) && (pRedir[ptr[2]] < nbPoints2), "BIM dans les points !!!!");
ptr[0] = pRedir[ptr[0]];
ptr[1] = pRedir[ptr[1]];
ptr[2] = pRedir[ptr[2]];
ptr[3] = ptr[2];
}
idx1++;
}
if (pFaces[idx1] != 127)
{
ptr = pFaceIdx[idx1].TabPoints;
EXCEPTIONC_Z((ptr[0] < nbPoints) && (ptr[1] < nbPoints) && (ptr[2] < nbPoints), "BIM !!!!!");
EXCEPTIONC_Z((pRedir[ptr[0]] >= 0) && (pRedir[ptr[0]] < nbPoints2) && (pRedir[ptr[1]] >= 0) && (pRedir[ptr[1]] < nbPoints2) && (pRedir[ptr[2]] >= 0) && (pRedir[ptr[2]] < nbPoints2), "BIM dans les points !!!!");
ptr[0] = pRedir[ptr[0]];
ptr[1] = pRedir[ptr[1]];
ptr[2] = pRedir[ptr[2]];
ptr[3] = ptr[2];
idx1++;
}
nbFaces = idx1;
m_TabPoints.SetSize(nbPoints2);
m_TabQuad.SetSize(nbFaces);
m_QuadTreePt.SetSize(MESH_QUADTREE_TOTAL_SIZE);
memset(m_QuadTreePt.GetArrayPtr(), 0, MESH_QUADTREE_TOTAL_SIZE*sizeof(Playspace_Mesh::RefPoint*));
for (S32 i = 0; i<m_TabPoints.GetSize(); i++)
InsertQuadTreePoint(i, m_TabPoints[i]);
InvalidatePointsLinks();
return;
}