in SpatialUnderstanding/Src/PlaySpace/PlaySpace_ScanMesh_W.cpp [78:459]
Bool BlindDetector::ComputeBlindZone(QuadTree_ScanMesh *_pMapDatas, Vec3i &_StartPos)
{
FIFO_Z<PlaySpace_Vec3i, 4096, FALSE> FIFOCell;
static S32 TabDelta[] = { 1, 0, 0,
-1, 0, 0,
0, 1, 0,
0, -1, 0,
0, 0, 1,
0, 0, -1
};
// Fill with MaxDist + 1
S32 FillDist = BLINDDETECT_UPPERDIST;
FillDist += (FillDist << 8);
FillDist += (FillDist << 16);
memset(TabBlindZone.GetArrayPtr(), FillDist, TabBlindZone.GetSize());
// Set Border to 1.
U8 *pStartCell = TabBlindZone.GetArrayPtr();
S32 ModuloZ = m_SizeY*m_SizeX;
for (S32 z = 0; z<m_SizeZ; z++)
{
U8 *pCurCell = pStartCell;
for (S32 y = 0; y < m_SizeY; y++)
*pCurCell++ = 1;
pCurCell = pStartCell + (m_SizeX - 1) * m_SizeY;
for (S32 y = 0; y < m_SizeY; y++)
*pCurCell++ = 1;
pStartCell += ModuloZ;
}
pStartCell = TabBlindZone.GetArrayPtr() + m_SizeY;
for (S32 x = 2; x<m_SizeX; x++)
{
U8 *pCurCell = pStartCell;
for (S32 y = 0; y < m_SizeY; y++)
*pCurCell++ = 1;
pCurCell = pStartCell + (m_SizeZ - 1) * ModuloZ;
for (S32 y = 0; y < m_SizeY; y++)
*pCurCell++ = 1;
pStartCell += m_SizeY;
}
// First Add Bloc.
for (S32 x = 0; x<m_SizeX; x++)
for (S32 z = 0; z<m_SizeZ; z++)
{
S32 Delta = ((z * m_SizeX + x) * m_SizeY);
QuadTree_ScanMesh::Cell *pCell = _pMapDatas->GetCell(x, z);
QuadTree_ScanMesh::ObjectChain *pZone = pCell->pFirst;
while (pZone)
{
if (pZone->pFirstRefFace)
{
// Add a bloc on BlindZone.
PlaySpace_Vec3i *pos = FIFOCell.Push();
pos->x = x;
pos->y = pZone->hMin;
pos->z = z;
TabBlindZone[Delta + pZone->hMin] = 0;
}
pZone = pZone->pNext;
}
}
// Pre Filter CanGo => suppress Empty Zone from Ground to Ceiling.
pStartCell = TabBlindZone.GetArrayPtr();
for (S32 z = 0; z<m_SizeZ; z++)
{
for (S32 x = 0; x<m_SizeX; x++)
{
Bool TotalEmpty = TRUE;
U8 *pCurCell = pStartCell;
for (S32 y = 0; y < m_SizeY; y++)
{
if (!*pCurCell)
{
TotalEmpty = FALSE;
break;
}
pCurCell++;
}
if (TotalEmpty)
{
pCurCell = pStartCell;
for (S32 y = 0; y < m_SizeY; y++)
{
*pCurCell++ = 1;
}
}
// Next !
pStartCell += m_SizeY;
}
}
// Now Do the Dist Compute
// => Largeur d'abord !!! (Important, permet de garantir que la distance est bonne !)
// => Use diagonal !!!
for (;;)
{
// Pop.
PlaySpace_Vec3i CurPos;
if (!FIFOCell.Pop(CurPos))
break; // Nothng to do.
// Manage it.
S32 x = CurPos.x;
S32 y = CurPos.y;
S32 z = CurPos.z;
U8 *pMyCell = GetCell(x, y, z);
S32 NextVal = *pMyCell + 1;
for (S32 dz = -1; dz <= 1; dz++)
{
S32 cz = z + dz;
if ((cz < 0) || (cz >= m_SizeZ))
continue;
for (S32 dx = -1; dx <= 1; dx++)
{
S32 cx = x + dx;
if ((cx < 0) || (cx >= m_SizeX))
continue;
for (S32 dy = -1; dy <= 1; dy++)
{
S32 cy = y + dy;
if ((cy < 0) || (cy >= m_SizeY))
continue;
U8 *pOtherCell = GetCell(cx, cy, cz);
if (*pOtherCell == BLINDDETECT_UPPERDIST)
{
if (NextVal < BLINDDETECT_MAXDIST)
{
PlaySpace_Vec3i *pos = FIFOCell.Push();
pos->x = cx;
pos->y = cy;
pos->z = cz;
}
*pOtherCell = NextVal;
}
}
}
}
}
// Modify StartPos.
Vec3i GoodStartPos = _StartPos;
S32 GCurVal = *GetCell(GoodStartPos.x, GoodStartPos.y, GoodStartPos.z);
while (GCurVal != BLINDDETECT_UPPERDIST)
{
if (GoodStartPos.x > 0)
{
S32 OtherVal = *GetCell(GoodStartPos.x - 1, GoodStartPos.y, GoodStartPos.z);
if (OtherVal > GCurVal)
{
GoodStartPos.x--;
GCurVal = OtherVal;
continue;
}
}
if (GoodStartPos.x < (m_SizeX - 1))
{
S32 OtherVal = *GetCell(GoodStartPos.x + 1, GoodStartPos.y, GoodStartPos.z);
if (OtherVal > GCurVal)
{
GoodStartPos.x++;
GCurVal = OtherVal;
continue;
}
}
if (GoodStartPos.y > 0)
{
S32 OtherVal = *GetCell(GoodStartPos.x, GoodStartPos.y - 1, GoodStartPos.z);
if (OtherVal > GCurVal)
{
GoodStartPos.y--;
GCurVal = OtherVal;
continue;
}
}
if (GoodStartPos.y < (m_SizeY - 1))
{
S32 OtherVal = *GetCell(GoodStartPos.x, GoodStartPos.y + 1, GoodStartPos.z);
if (OtherVal > GCurVal)
{
GoodStartPos.y++;
GCurVal = OtherVal;
continue;
}
}
if (GoodStartPos.z > 0)
{
S32 OtherVal = *GetCell(GoodStartPos.x, GoodStartPos.y, GoodStartPos.z - 1);
if (OtherVal > GCurVal)
{
GoodStartPos.z--;
GCurVal = OtherVal;
continue;
}
}
if (GoodStartPos.z < (m_SizeZ - 1))
{
S32 OtherVal = *GetCell(GoodStartPos.x, GoodStartPos.y, GoodStartPos.z + 1);
if (OtherVal > GCurVal)
{
GoodStartPos.z++;
GCurVal = OtherVal;
continue;
}
}
// Lock ! :(
return FALSE;
}
// Fill The _CanGoArea (can't go into little hole).
// => Largeur d'abord !!! Important.
// => Use diagonal !!! => Important to stop
PlaySpace_Vec3i *pos = FIFOCell.Push();
pos->x = GoodStartPos.x;
pos->y = GoodStartPos.y;
pos->z = GoodStartPos.z;
*GetCell(GoodStartPos.x, GoodStartPos.y, GoodStartPos.z) |= BLINDDETECT_CANGO;
S32 StopYGround = _pMapDatas->m_hGround;
S32 StopYCeiling = _pMapDatas->m_hCeiling;
for (;;)
{
// Pop.
PlaySpace_Vec3i CurPos;
if (!FIFOCell.Pop(CurPos))
break; // Nothng to do.
// Manage it.
S32 x = CurPos.x;
S32 y = CurPos.y;
S32 z = CurPos.z;
U8 *pMyCell = GetCell(x, y, z);
S32 CurPrevVal = (*pMyCell & BLINDDETECT_MSK_DIST) - 1;
for (S32 dz = -1; dz <= 1; dz++)
{
S32 cz = z + dz;
if ((cz < 0) || (cz >= m_SizeZ))
continue;
for (S32 dx = -1; dx <= 1; dx++)
{
S32 cx = x + dx;
if ((cx < 0) || (cx >= m_SizeX))
continue;
for (S32 dy = -1; dy <= 1; dy++)
{
S32 cy = y + dy;
if ((cy < 0) || (cy >= m_SizeY))
continue;
if ((cy < StopYGround) || (cy > StopYCeiling))
continue;
U8 *pOtherCell = GetCell(cx, cy, cz);
S32 OtherVal = *pOtherCell;
if ((OtherVal == BLINDDETECT_UPPERDIST) || (OtherVal == CurPrevVal))
{
if (OtherVal > 1) // Important because of diagonale.
{
PlaySpace_Vec3i *lpos = FIFOCell.Push();
lpos->x = cx;
lpos->y = cy;
lpos->z = cz;
}
*pOtherCell = OtherVal | BLINDDETECT_CANGO;
}
}
}
}
}
// Finally : Fill the Visible Area
const S32 FlagEmpty = 0x01;
const S32 FlagPX = 0x02;
const S32 FlagNX = 0x04;
const S32 FlagPY = 0x08;
const S32 FlagNY = 0x10;
const S32 FlagPZ = 0x20;
const S32 FlagNZ = 0x40;
const S32 FlagTotal = FlagPX + FlagPY + FlagPZ + FlagNX + FlagNY + FlagNZ + FlagEmpty;
S32 Size = TabBlindZone.GetSize();
U8 *pCurCell = TabBlindZone.GetArrayPtr();
for (S32 t = 0; t<Size; t++)
{
if (*pCurCell)
{
*pCurCell = (*pCurCell & BLINDDETECT_CANGO) ? FlagTotal : FlagEmpty;
}
pCurCell++;
}
EXCEPTIONC_Z(pCurCell <= (TabBlindZone.GetArrayPtr() + Size), "ComputeBlindZone : Out of buffer");
Bool SomethingToDo = TRUE;
while (SomethingToDo)
{
SomethingToDo = FALSE;
S32 SizeBase = m_SizeX * m_SizeY;
U8 *pCurCellP = TabBlindZone.GetArrayPtr();
U8 *pCurCellN = TabBlindZone.GetArrayPtr() + Size;
for (S32 z = 0; z<m_SizeZ; z++)
{
for (S32 x = 0; x<m_SizeX; x++)
{
for (S32 y = 0; y<m_SizeY; y++)
{
// Positive propagation.
S32 CurVal = *pCurCellP;
if (CurVal)
{
if (y && (pCurCellP[-1] & FlagPY))
CurVal |= FlagPY;
if (x && (pCurCellP[-m_SizeY] & FlagPX))
CurVal |= FlagPX;
if (z && (pCurCellP[-SizeBase] & FlagPZ))
CurVal |= FlagPZ;
*pCurCellP = CurVal;
}
pCurCellP++;
// Negative propagation
pCurCellN--;
CurVal = *pCurCellN;
if (CurVal)
{
if (y && (pCurCellN[1] & FlagNY))
CurVal |= FlagNY;
if (x && (pCurCellN[m_SizeY] & FlagNX))
CurVal |= FlagNX;
if (z && (pCurCellN[SizeBase] & FlagNZ))
CurVal |= FlagNZ;
*pCurCellN = CurVal;
}
}
}
}
EXCEPTIONC_Z(pCurCellP == (TabBlindZone.GetArrayPtr() + Size), "ComputeBlindZone : Out of buffer");
EXCEPTIONC_Z(pCurCellN == (TabBlindZone.GetArrayPtr()), "ComputeBlindZone : Out of buffer");
// Transform specific value into CANGO.
pCurCell = TabBlindZone.GetArrayPtr();
for (S32 t = 0; t<Size; t++)
{
S32 CurVal = *pCurCell;
if ((CurVal > 1) && (CurVal != FlagTotal))
{
S32 NbBits = 0;
if (CurVal & FlagNX)
NbBits++;
if (CurVal & FlagPX)
NbBits++;
if (CurVal & FlagNY)
NbBits++;
if (CurVal & FlagPY)
NbBits++;
if (CurVal & FlagNZ)
NbBits++;
if (CurVal & FlagPZ)
NbBits++;
if (NbBits > 1)
{
SomethingToDo = TRUE;
*pCurCell = FlagTotal;
}
}
pCurCell++;
}
}
return TRUE;
}