in SpatialUnderstanding/Src/PlaySpace/PlaySpace_ScanMesh_W.cpp [2014:2581]
Bool HMapMeshInfos3D::ProcessBubbleAlgorithm(Segment_Z &_ViewSeg, Playspace_SR_W *_pPlayspaceSR, Bool onlySeen /*= TRUE*/)
{
if ((m_NbCellX <= 0) || (m_NbCellY <= 0) || (m_NbCellZ <= 0))
return FALSE;
// Init Blind Map.
m_BlindDetector.Init(m_NbCellX, m_NbCellY, m_NbCellZ);
U8 *pBlind = m_BlindDetector.TabBlindZone.GetArrayPtr();
memset(pBlind, 0x7F, m_BlindDetector.TabBlindZone.GetSize());
Float InvSizeCell = 1.f / m_SizeCell;
HU16DA flags2D;
ProcessConcaveHull2D(m_infos2D, flags2D, onlySeen);
S32 xMin = 1000, xMax = -1, zMin = 1000, zMax = -1;
// Add Seen Face Blocs.
for (S32 x = 0; x < m_NbCellX; x++)
{
for (S32 z = 0; z < m_NbCellZ; z++)
{
S32 Delta = ((z * m_NbCellX + x) * m_NbCellY);
QuadTree_ScanMesh::Cell *pCell = m_pMapMeshDatas->GetCell(x, z);
QuadTree_ScanMesh::ObjectChain *pZone = pCell->pFirst;
while (pZone)
{
if ((pZone->hMin >= m_pMapMeshDatas->m_hGround)
&& (pZone->hMin <= m_pMapMeshDatas->m_hCeiling)
)
{
// Only if upper Ground
Bool IsSeen = !onlySeen; // FALSE;
if (onlySeen)
{
PlaySpace_ScanMeshRefFace *pRefFace = pZone->pFirstRefFace;
while (pRefFace)
{
if (pRefFace->pFace->IsSeenQuality > 0) // Seen or paint.
{
IsSeen = TRUE;
break;
}
pRefFace = pRefFace->pNext;
}
}
if (IsSeen && (m_infos2D[(z * m_NbCellX) + x] != 1))
{
// Add a bloc on BlindZone.
pBlind[Delta + pZone->hMin] = 0;
xMin = Min<S32>(xMin, x);
xMax = Max<S32>(xMax, x);
zMin = Min<S32>(zMin, z);
zMax = Max<S32>(zMax, z);
}
}
pZone = pZone->pNext;
}
}
}
//////////////////////////////////////////////////////////
S32 zIncr = m_NbCellX * m_NbCellY;
S32 d2Y = m_NbCellY + m_NbCellY;
S32 d2Z = zIncr + zIncr;
S32 sizeTotal = zIncr * m_NbCellZ;
S32 dir[6] = { m_NbCellY , -m_NbCellY, zIncr , -zIncr , 1 , -1 };
S32 concIdx[13] = { 1 , m_NbCellY , zIncr , 1 + m_NbCellY , 1 - m_NbCellY , 1 + zIncr , 1 - zIncr , zIncr + m_NbCellY , zIncr - m_NbCellY , 1 + m_NbCellY + zIncr , 1 + m_NbCellY - zIncr , 1 - m_NbCellY + zIncr , 1 - m_NbCellY - zIncr };
U8 border;
static U8 concTst[13] = { BUBBLE_Y , BUBBLE_X , BUBBLE_Z , BUBBLE_XY , BUBBLE_XY , BUBBLE_YZ , BUBBLE_YZ , BUBBLE_XZ , BUBBLE_XZ , BUBBLE_ALL , BUBBLE_ALL , BUBBLE_ALL , BUBBLE_ALL };
static U8 tst[27] = { BUBBLE_YN_XN_ZN , BUBBLE_XN_ZN , BUBBLE_YP_XN_ZN , BUBBLE_YN_ZN , BUBBLE_ZN , BUBBLE_YP_ZN , BUBBLE_YN_XP_ZN , BUBBLE_XP_ZN , BUBBLE_YP_XP_ZN ,
BUBBLE_YN_XN , BUBBLE_XN , BUBBLE_YP_XN , BUBBLE_YN , 0 , BUBBLE_YP , BUBBLE_YN_XP , BUBBLE_XP , BUBBLE_YP_XP ,
BUBBLE_YN_XN_ZP , BUBBLE_XN_ZP , BUBBLE_YP_XN_ZP , BUBBLE_YN_ZP , BUBBLE_ZP , BUBBLE_YP_ZP , BUBBLE_YN_XP_ZP , BUBBLE_XP_ZP , BUBBLE_YP_XP_ZP };
static U8 planeYTst[8] = { BUBBLE_XN_ZN, BUBBLE_XN, BUBBLE_XN_ZP, BUBBLE_ZN, BUBBLE_ZP, BUBBLE_XP_ZN, BUBBLE_XP, BUBBLE_XP_ZP };
static U8 planeXTst[8] = { BUBBLE_YN_ZN, BUBBLE_YN, BUBBLE_YN_ZP, BUBBLE_ZN, BUBBLE_ZP, BUBBLE_YP_ZN, BUBBLE_YP, BUBBLE_YP_ZP };
static U8 planeZTst[8] = { BUBBLE_YN_XN, BUBBLE_XN, BUBBLE_YP_XN, BUBBLE_YN, BUBBLE_YP, BUBBLE_YN_XP, BUBBLE_XP, BUBBLE_YP_XP };
S32 planeYIdx[8] = { -m_NbCellY - zIncr, -m_NbCellY, -m_NbCellY + zIncr, -zIncr, zIncr, m_NbCellY - zIncr, m_NbCellY, m_NbCellY + zIncr };
S32 planeXIdx[8] = { -1 - zIncr, -1, -1 + zIncr, -zIncr, zIncr, 1 - zIncr, 1, 1 + zIncr };
S32 planeZIdx[8] = { -1 - m_NbCellY, -m_NbCellY, 1 - m_NbCellY, -1, 1, -1 + m_NbCellY, m_NbCellY, 1 + m_NbCellY };
S32 ty = m_NbCellY - 1;
S32 tx = m_NbCellX - 1;
S32 tz = m_NbCellZ - 1;
Float maxCosErr = Cos(DegToRad(20.0f));
// First step
for (S32 x = 0; x < m_NbCellX; x++)
{
for (S32 z = 0; z < m_NbCellZ; z++)
{
S32 Delta = (z * m_NbCellX + x) * m_NbCellY;
QuadTree_ScanMesh::Cell *pCell = m_pMapMeshDatas->GetCell(x, z);
QuadTree_ScanMesh::ObjectChain *pZone = pCell->pFirst;
Bool haveGround = FALSE;
Bool haveCeil = FALSE;
Bool haveCeilUp = FALSE;
Bool haveCeilUpUp = FALSE;
Bool haveMin = FALSE;
while (pZone)
{
if (pZone->pFirstRefFace)
{
PlaySpace_ScanMeshRefFace *pRefFace = pZone->pFirstRefFace;
Bool isSeen = FALSE;
while (pRefFace)
{
PlaySpace_ScanMeshFace *pFace = pRefFace->pFace;
if (!onlySeen || (pFace->IsSeenQuality > 0)) // Seen or paint.
{
isSeen = TRUE;
if (pFace->Normal.y > maxCosErr)
haveMin = TRUE;
}
pRefFace = pRefFace->pNext;
}
if (isSeen)
{
if (pZone->hMin == m_pMapMeshDatas->m_hGround)
haveGround = TRUE;
if (pZone->hMin == m_pMapMeshDatas->m_hCeiling)
haveCeil = TRUE;
if (pZone->hMin == (m_pMapMeshDatas->m_hCeiling + 1))
haveCeilUp = TRUE;
if (pZone->hMin == (m_pMapMeshDatas->m_hCeiling + 2))
haveCeilUpUp = TRUE;
}
}
pZone = pZone->pNext;
}
if ((haveGround || haveMin) && (m_infos2D[(z * m_NbCellX) + x] != 1))
{
xMin = Min<S32>(xMin, x);
xMax = Max<S32>(xMax, x);
zMin = Min<S32>(zMin, z);
zMax = Max<S32>(zMax, z);
S32 ceiling = m_pMapMeshDatas->m_hCeiling;
if (haveCeil)
ceiling = m_pMapMeshDatas->m_hCeiling;
else if (haveCeilUp)
ceiling = m_pMapMeshDatas->m_hCeiling + 1;
else if (haveCeilUpUp)
ceiling = m_pMapMeshDatas->m_hCeiling + 2;
for (S32 i = ceiling; i < m_NbCellY; i++)
pBlind[Delta + i] = 0;
}
}
}
HU8DA flagBuffer;
flagBuffer.SetSize(sizeTotal);
U8* pFlagBuffer = flagBuffer.GetArrayPtr();
memset(pFlagBuffer, 0, flagBuffer.GetSize());
Vec3iDA ringBuf;
ringBuf.SetSize(6 * ((m_NbCellX * m_NbCellY) + (m_NbCellY * m_NbCellZ) + (m_NbCellX * m_NbCellZ))); // majorant grossier mais s�r
S32 rbHead = 0;
S32 rbTail = 0;
Vec3i *pRingBuf = ringBuf.GetArrayPtr();
// Fill the ring buffer
///////////////////////////////////
U8* pCell = pBlind;
U8* pFlagBuf = pFlagBuffer;
for (S32 z = 0; z < m_NbCellZ; z++)
{
U8 zmask = (z > 0 ? 0 : BUBBLE_ZN) | (z < tz ? 0 : BUBBLE_ZP);
for (S32 x = 0; x < m_NbCellX; x++)
{
U8 mask = zmask | (x > 0 ? 0 : BUBBLE_XN) | (x < tx ? 0 : BUBBLE_XP);
if (mask)
{
for (S32 y = 1; y < ty; y++)
{
pFlagBuf[y] |= mask;
if (pCell[y] == 0x7F)
{
pRingBuf[rbHead++] = Vec3i(x, y, z);
pFlagBuf[y] |= BUBBLE_IN;
}
}
}
if (pCell[0] == 0x7F)
{
pRingBuf[rbHead++] = Vec3i(x, 0, z);
pFlagBuf[0] |= BUBBLE_IN;
}
if (pCell[ty] == 0x7F)
{
pRingBuf[rbHead++] = Vec3i(x, ty, z);
pFlagBuf[ty] |= BUBBLE_IN;
}
pFlagBuf[0] |= mask | BUBBLE_YN;
pFlagBuf[ty] |= mask | BUBBLE_YP;
pCell += m_NbCellY;
pFlagBuf += m_NbCellY;
}
}
///////////////////////////////////
HU32DA wallFlags;
ComputeWallInfos(wallFlags);
U32* pWallInfos = wallFlags.GetArrayPtr();
U32* pWall = pWallInfos;
///////////////////////////////////
S32 nbElem = rbHead;
S32 nbIter = 0;
while (nbElem)
{
nbIter++;
Vec3i pos = ringBuf[rbTail];
S32 idx = (zIncr * pos.z) + (m_NbCellY * pos.x) + pos.y;
pCell = pBlind + idx;
pFlagBuf = pFlagBuffer + idx;
U8 flag = (*pFlagBuf &= BUBBLE_MASK);
rbTail++;
if (rbTail == ringBuf.GetSize())
rbTail = 0;
nbElem--;
border = flag;
U8 test = BUBBLE_IN;
for (S32 i = 0; i < 6; i++)
{
test <<= 1;
if (((border & test) == 0) && (pCell[dir[i]] == 1))
border |= test;
}
if (border)
{
U32 wall = pWallInfos[idx];
Bool eat = FALSE;
if (!(wall & WALL_IN_FRONT_ALL_BUT_CEIL))
{
if ((border & BUBBLE_YP) && (wall & WALL_BEHIND_YN))
{
if (flag & BUBBLE_YP)
eat = TRUE;
else
{
S32 nbEat = 0;
for (S32 i = 0; i < 8; i++)
{
if (((flag & planeYTst[i]) == 0) && (pCell[1 + planeYIdx[i]] == 1))
nbEat++;
}
eat = (nbEat > 3);
}
}
if (!eat && (border & BUBBLE_YN) && (wall & WALL_BEHIND_YP))
{
if (flag & BUBBLE_YN)
eat = TRUE;
else
{
S32 nbEat = 0;
for (S32 i = 0; i < 8; i++)
{
if (((flag & planeYTst[i]) == 0) && (pCell[-1 + planeYIdx[i]] == 1))
nbEat++;
}
eat = (nbEat > 3);
}
}
if (!eat && (border & BUBBLE_XP) && (wall & WALL_BEHIND_XN))
{
if (flag & BUBBLE_XP)
eat = TRUE;
else
{
S32 nbEat = 0;
for (S32 i = 0; i < 8; i++)
{
if (((flag & planeXTst[i]) == 0) && (pCell[m_NbCellY + planeXIdx[i]] == 1))
nbEat++;
}
eat = (nbEat > 3);
}
}
if (!eat && (border & BUBBLE_XN) && (wall & WALL_BEHIND_XP))
{
if (flag & BUBBLE_XN)
eat = TRUE;
else
{
S32 nbEat = 0;
for (S32 i = 0; i < 8; i++)
{
if (((flag & planeXTst[i]) == 0) && (pCell[-m_NbCellY + planeXIdx[i]] == 1))
nbEat++;
}
eat = (nbEat > 3);
}
}
if (!eat && (border & BUBBLE_ZP) && (wall & WALL_BEHIND_ZN))
{
if (flag & BUBBLE_ZP)
eat = TRUE;
else
{
S32 nbEat = 0;
for (S32 i = 0; i < 8; i++)
{
if (((flag & planeZTst[i]) == 0) && (pCell[zIncr + planeZIdx[i]] == 1))
nbEat++;
}
eat = (nbEat > 3);
}
}
if (!eat && (border & BUBBLE_ZN) && (wall & WALL_BEHIND_ZP))
{
if (flag & BUBBLE_ZN)
eat = TRUE;
else
{
S32 nbEat = 0;
for (S32 i = 0; i < 8; i++)
{
if (((flag & planeZTst[i]) == 0) && (pCell[-zIncr + planeZIdx[i]] == 1))
nbEat++;
}
eat = (nbEat > 3);
}
}
}
if (!eat)
{
if ((border & BUBBLE_YN) && (wall & WALL_BEHIND_YP) && (wall & (WALL_BEHIND_XP | WALL_BEHIND_XN | WALL_BEHIND_ZP | WALL_BEHIND_ZN)))
eat = TRUE;
}
if (!eat)
{
Bool concave = FALSE;
for (S32 i = 0; i < 13; i++)
{
S32 d = concIdx[i];
if (((flag & concTst[i]) == 0) && ((pCell[d] != 1) && (pCell[-d] != 1)))
{
concave = TRUE;
break;
}
}
eat = !concave;
}
if (!eat)
{
eat = ((border & BUBBLE_YP) && ((flag & BUBBLE_YN) == 0) && (pCell[-1] == 0)) ||
((border & BUBBLE_YN) && ((flag & BUBBLE_YP) == 0) && (pCell[1] == 0)) ||
((border & BUBBLE_XP) && ((flag & BUBBLE_XN) == 0) && (pCell[-m_NbCellY] == 0)) ||
((border & BUBBLE_XN) && ((flag & BUBBLE_XP) == 0) && (pCell[m_NbCellY] == 0)) ||
((border & BUBBLE_ZP) && ((flag & BUBBLE_ZN) == 0) && (pCell[-zIncr] == 0)) ||
((border & BUBBLE_ZN) && ((flag & BUBBLE_ZP) == 0) && (pCell[zIncr] == 0));
}
if (eat)
{
*pCell = 1;
S32 dIdx0 = -1 - m_NbCellY - zIncr;
U8* pTst = tst;
for (S32 dz = -1; dz < 2; dz++)
{
S32 dIdx1 = dIdx0;
for (S32 dx = -1; dx < 2; dx++)
{
S32 dIdx2 = dIdx1;
for (S32 dy = -1; dy < 2; dy++)
{
if ((dIdx2 != 0) && ((flag & *pTst) == 0) && ((pFlagBuf[dIdx2] & BUBBLE_IN) == 0) && (pCell[dIdx2] == 0x7F))
{
nbElem++;
pFlagBuf[dIdx2] |= BUBBLE_IN;
pRingBuf[rbHead++] = pos + Vec3i(dx, dy, dz);
if (rbHead == ringBuf.GetSize())
rbHead = 0;
}
dIdx2++;
pTst++;
}
dIdx1 += m_NbCellY;
}
dIdx0 += zIncr;
}
EXCEPTIONC_Z((nbElem < ringBuf.GetSize()), "Apprends � majorer !!!");
}
}
}
///////////////////////////////////////// Post process : fix mushrooms ///////////////////////////////////////////
// Add Upper Ceiling and Under Ground.
for (S32 x = 0; x < m_NbCellX; x++)
{
for (S32 z = 0; z < m_NbCellZ; z++)
{
S32 Delta = ((z * m_NbCellX + x) * m_NbCellY);
QuadTree_ScanMesh::Cell *pCell = m_pMapMeshDatas->GetCell(x, z);
QuadTree_ScanMesh::ObjectChain *pZone = pCell->pFirst;
while (pZone)
{
if ((pZone->hMin < m_pMapMeshDatas->m_hGround) || (pZone->hMin > m_pMapMeshDatas->m_hCeiling))
pBlind[Delta + pZone->hMin] = 0;
pZone = pZone->pNext;
}
}
}
pCell = pBlind;
pFlagBuf = pFlagBuffer;
for (S32 z = 0; z < m_NbCellZ; z++)
{
for (S32 x = 0; x < m_NbCellX; x++)
{
for (S32 y = 0; y < m_NbCellY; y++)
{
if (*pCell == 0x7F)
{
U8 flag = (*pFlagBuf &= BUBBLE_MASK);
border = flag;
U8 test = BUBBLE_IN;
for (S32 i = 0; i < 6; i++)
{
test <<= 1;
if (((border & test) == 0) && (pCell[dir[i]] == 1))
border |= test;
}
if (border)
{
Bool eat = FALSE;
if ((border & BUBBLE_XP) || (border & BUBBLE_XN))
{
S32 nbN = 0;
if (((flag & BUBBLE_YP) == 0) && (pCell[1] == 0))
nbN++;
if (((flag & BUBBLE_YN) == 0) && (pCell[-1] == 0))
nbN++;
if (((flag & BUBBLE_ZP) == 0) && (pCell[zIncr] == 0))
nbN++;
if (((flag & BUBBLE_ZN) == 0) && (pCell[-zIncr] == 0))
nbN++;
eat = (nbN > 1);
}
if (!eat && ((border & BUBBLE_YP) || (border & BUBBLE_YN)))
{
S32 nbN = 0;
if (((flag & BUBBLE_XP) == 0) && (pCell[m_NbCellY] == 0))
nbN++;
if (((flag & BUBBLE_XN) == 0) && (pCell[-m_NbCellY] == 0))
nbN++;
if (((flag & BUBBLE_ZP) == 0) && (pCell[zIncr] == 0))
nbN++;
if (((flag & BUBBLE_ZN) == 0) && (pCell[-zIncr] == 0))
nbN++;
eat = (nbN > 0);
}
if (!eat && ((border & BUBBLE_ZP) || (border & BUBBLE_ZN)))
{
S32 nbN = 0;
if (((flag & BUBBLE_XP) == 0) && (pCell[m_NbCellY] == 0))
nbN++;
if (((flag & BUBBLE_XN) == 0) && (pCell[-m_NbCellY] == 0))
nbN++;
if (((flag & BUBBLE_YP) == 0) && (pCell[1] == 0))
nbN++;
if (((flag & BUBBLE_YN) == 0) && (pCell[-1] == 0))
nbN++;
eat = (nbN > 1);
}
if (eat)
{
*pCell = 0x80;
}
}
}
pCell++;
pFlagBuf++;
}
}
}
pCell = pBlind;
for (S32 z = 0; z < m_NbCellZ; z++)
{
for (S32 x = 0; x < m_NbCellX; x++)
{
for (S32 y = 0; y < m_NbCellY; y++)
{
if (*pCell == 0x80)
*pCell = 1;
pCell++;
}
}
}
///////////////////////////////////////// end of mushrooms Post process ///////////////////////////////////////////
// Re-Add ALL Face Blocs.
for (S32 x = 0; x < m_NbCellX; x++)
{
for (S32 z = 0; z < m_NbCellZ; z++)
{
S32 Delta = ((z * m_NbCellX + x) * m_NbCellY);
QuadTree_ScanMesh::Cell *pCell = m_pMapMeshDatas->GetCell(x, z);
QuadTree_ScanMesh::ObjectChain *pZone = pCell->pFirst;
while (pZone)
{
Bool IsSeen = FALSE;
PlaySpace_ScanMeshRefFace *pRefFace = pZone->pFirstRefFace;
if (pRefFace)
{
// Add a bloc on BlindZone.
pBlind[Delta + pZone->hMin] = 0;
}
pZone = pZone->pNext;
}
}
}
// First Get The StartPoint.
Vec3f Start = _ViewSeg.Org;
Vec3f Delta = _ViewSeg.Dir * m_SizeCell;
S32 NbPass = 10.f * InvSizeCell;
Vec3i StartPos;
Bool HaveFoundSomething = FALSE;
for (S32 i = 0; i<NbPass; i++, Start += Delta)
{
StartPos.x = (S32)((Start.x - m_PosMin.x) * InvSizeCell);
StartPos.y = (S32)((Start.y - m_PosMin.y) * InvSizeCell);
StartPos.z = (S32)((Start.z - m_PosMin.z) * InvSizeCell);
if ((StartPos.x < 0) || (StartPos.x >= m_NbCellX))
continue;
if ((StartPos.y < 0) || (StartPos.y >= m_pMapMeshDatas->m_hMax))
continue;
if ((StartPos.z < 0) || (StartPos.z >= m_NbCellZ))
continue;
U8 *pVoxel = m_BlindDetector.GetCell(StartPos.x, StartPos.y, StartPos.z);
if (*pVoxel <= 1)
continue;
HaveFoundSomething = TRUE;
break;
}
if (!HaveFoundSomething)
return FALSE;
ProcessFlood(StartPos);
// Free BlidDetector...
m_BlindDetector.Flush();
return TRUE;
}