wmlconvexpolyhedron3.cpp

3D Game Engine Design Source Code非常棒

{
    ConvexClipper<Real> kClipper(*this);

    const PArray& rakPlane = rkPoly.GetPlanes();
    for (int i = 0; i < (int)rakPlane.size(); i++)
    {
        if ( kClipper.Clip(rakPlane[i]) == Plane3<Real>::NEGATIVE_SIDE )
            return false;
    }

    kClipper.Convert(rkIntr);
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::FindAllIntersections (int iQuantity,
    ConvexPolyhedron3* akPoly, int& riCombos, ConvexPolyhedron3**& rapkIntr)
{
    // Only 2^16 possible combinations for intersections are currently
    // supported.  If you need more, then GetHighBit(int) must be modified
    // to handle more than 16-bit inputs.
    if ( iQuantity <= 0 || iQuantity > 16 )
    {
        riCombos = 0;
        rapkIntr = NULL;
        return;
    }

    riCombos = (1 << iQuantity);
    bool* abNeedsTesting = new bool[riCombos];
    rapkIntr = new ConvexPolyhedron3*[riCombos];
    int i;
    for (i = 0; i < riCombos; i++)
    {
        abNeedsTesting[i] = true;
        rapkIntr[i] = NULL;
    }

    // trivial cases, zero or one polyhedron--already the intersection
    abNeedsTesting[0] = false;
    for (i = 0; i < iQuantity; i++)
    {
        int j = (1 << i);
        abNeedsTesting[j] = false;
        rapkIntr[j] = new ConvexPolyhedron3(akPoly[i]);
    }
    
    for (i = 3; i < riCombos; i++)
    {
        if ( abNeedsTesting[i] )
        {
            // In binary, i = b[m]...b[0] where b[m] is not zero (the
            // high-order bit.  Also, i1 = b[m-1]...b[0] is not zero
            // since, if it were, we would have ruled out the combination
            // by the j-loop below.  Therefore, i0 = b[m]0...0 and
            // i1 correspond to already existing polyhedra.  The
            // intersection finding just needs to look at the intersection
            // of the two polyhedra.
            int i0 = GetHighBit(i);
            int i1 = i & ~i0;
            rapkIntr[i] = FindSolidIntersection(*rapkIntr[i0],
                *rapkIntr[i1]);
            if ( !rapkIntr[i] )
            {
                // No intersection for this combination.  No need to test
                // other combinations that include this one.
                for (int j = 0; j < riCombos; j++)
                {
                    if ( (i & j) == i )
                        abNeedsTesting[j] = false;
                }
            }
#ifdef _DEBUG
            else  // test if well-formed convex polyhedron
            {
                Vector3<Real> kCentroid = rapkIntr[i]->GetCentroid();
                bool bContains = rapkIntr[i]->ContainsPoint(kCentroid);
                assert( bContains );
            }
#endif
        }
    }

    delete[] abNeedsTesting;
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolyhedron3<Real>* ConvexPolyhedron3<Real>::FindSolidIntersection (
    const ConvexPolyhedron3& rkPoly0, const ConvexPolyhedron3& rkPoly1)
{
    ConvexPolyhedron3* pkIntr = new ConvexPolyhedron3;
    if ( rkPoly0.FindIntersection(rkPoly1,*pkIntr) )
        return pkIntr;
    
    // As surfaces, the polyhedra do not intersect.  However, as solids,
    // one polyhedron might be fully contained in the other.
    if ( rkPoly0.ContainsPoint(rkPoly1.GetCentroid()) )
    {
        *pkIntr = rkPoly1;
        return pkIntr;
    }
        
    if ( rkPoly1.ContainsPoint(rkPoly0.GetCentroid()) )
    {
        *pkIntr = rkPoly0;
        return pkIntr;
    }

    delete pkIntr;
    return NULL;
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexPolyhedron3<Real>::GetHighBit (int i)
{
    // assert: i in [1,2^16].  That is, (i>0) && (0xFFFF0000&i)==0.
    // This is a binary search for the high-order bit of i.
    if ( (i & 0xFF00) != 0 )
    {
        if ( (i & 0xF000) != 0 )
        {
            if ( (i & 0xC000) != 0 )
            {
                if ( (i & 0x8000) != 0 )
                    return 0x8000;
                else // (i & 0x4000) != 0
                    return 0x4000;
            }
            else  // (i & 0x3000) != 0
            {
                if ( (i & 0x2000) != 0 )
                    return 0x2000;
                else  // (i & 0x1000) != 0
                    return 0x1000;
            }
        }
        else  // (i & 0x0F00) != 0
        {
            if ( (i & 0x0C00) != 0 )
            {
                if ( (i & 0x0800) != 0 )
                    return 0x0800;
                else  // (i & 0x0400) != 0
                    return 0x0400;
            }
            else  // (i & 0x0300) != 0
            {
                if ( (i & 0x0200) != 0 )
                    return 0x0200;
                else  // (i & 0x0100) != 0
                    return 0x0100;
            }
        }
    }
    else  // (i & 0x00FF)
    {
        if ( (i & 0x00F0) != 0 )
        {
            if ( (i & 0x00C0) != 0 )
            {
                if ( (i & 0x0080) != 0 )
                    return 0x0080;
                else  // (i & 0x0040) != 0
                    return 0x0040;
            }
            else  // (i & 0x0030) != 0
            {
                if ( (i & 0x0020) != 0 )
                    return 0x0020;
                else  // (i & 0x0010) != 0
                    return 0x0010;
            }
        }
        else  // (i & 0x000F) != 0
        {
            if ( (i & 0x000C) != 0 )
            {
                if ( (i & 0x0008) != 0 )
                    return 0x0008;
                else  // (i & 0x0004) != 0
                    return 0x0004;
            }
            else  // (i & 0x0003) != 0
            {
                if ( (i & 0x0002) != 0 )
                    return 0x0002;
                else  // (i & 0x0001) != 0
                    return 0x0001;
            }
        }
    }
}
//----------------------------------------------------------------------------
template <class Real>
Real ConvexPolyhedron3<Real>::GetTriangleArea (const Vector3<Real>& rkN,
    const Vector3<Real>& rkV0, const Vector3<Real>& rkV1,
    const Vector3<Real>& rkV2) const
{
    // compute maximum absolute component of normal vector
    int iMax = 0;
    Real fMax = Math<Real>::FAbs(rkN.X());

    Real fAbs = Math<Real>::FAbs(rkN.Y());
    if ( fAbs > fMax )
    {
        iMax = 1;
        fMax = fAbs;
    }

    fAbs = Math<Real>::FAbs(rkN.Z());
    if ( fAbs > fMax )
    {
        iMax = 2;
        fMax = fAbs;
    }

    // catch degenerate triangles
    if ( fMax == (Real)0.0 )
        return (Real)0.0;

    // compute area of projected triangle
    Real fD0, fD1, fD2, fArea;
    if ( iMax == 0 )
    {
        fD0 = rkV1.Z() - rkV2.Z();
        fD1 = rkV2.Z() - rkV0.Z();
        fD2 = rkV0.Z() - rkV1.Z();
        fArea = Math<Real>::FAbs(rkV0.Y()*fD0 + rkV1.Y()*fD1 + rkV2.Y()*fD2);
    }
    else if ( iMax == 1 )
    {
        fD0 = rkV1.X() - rkV2.X();
        fD1 = rkV2.X() - rkV0.X();
        fD2 = rkV0.X() - rkV1.X();
        fArea = Math<Real>::FAbs(rkV0.Z()*fD0 + rkV1.Z()*fD1 + rkV2.Z()*fD2);
    }
    else
    {
        fD0 = rkV1.Y() - rkV2.Y();
        fD1 = rkV2.Y() - rkV0.Y();
        fD2 = rkV0.Y() - rkV1.Y();
        fArea = Math<Real>::FAbs(rkV0.X()*fD0 + rkV1.X()*fD1 + rkV2.X()*fD2);
    }

    fArea *= ((Real)0.5)/fMax;
    return fArea;
}
//----------------------------------------------------------------------------
template <class Real>
Real ConvexPolyhedron3<Real>::GetSurfaceArea () const
{
    Real fSurfaceArea = (Real)0.0;

    for (int iT = 0; iT < m_akTriangle.GetQuantity(); iT++)
    {
        const MTTriangle& rkT = m_akTriangle.Get(iT);
        int iV0 = GetVLabel(rkT.GetVertex(0));
        int iV1 = GetVLabel(rkT.GetVertex(1));
        int iV2 = GetVLabel(rkT.GetVertex(2));
        const Vector3<Real>& rkV0 = m_akPoint[iV0];
        const Vector3<Real>& rkV1 = m_akPoint[iV1];
        const Vector3<Real>& rkV2 = m_akPoint[iV2];
        const Vector3<Real>& rkN = m_akPlane[iT].GetNormal();

        fSurfaceArea += GetTriangleArea(rkN,rkV0,rkV1,rkV2);
    }

    return fSurfaceArea;
}
//----------------------------------------------------------------------------
template <class Real>
Real ConvexPolyhedron3<Real>::GetVolume () const
{
    Real fVolume = (Real)0.0;

    for (int iT = 0; iT < m_akTriangle.GetQuantity(); iT++)
    {
        const MTTriangle& rkT = m_akTriangle.Get(iT);
        int iV0 = GetVLabel(rkT.GetVertex(0));
        int iV1 = GetVLabel(rkT.GetVertex(1));
        int iV2 = GetVLabel(rkT.GetVertex(2));
        const Vector3<Real>& rkV0 = m_akPoint[iV0];
        const Vector3<Real>& rkV1 = m_akPoint[iV1];
        const Vector3<Real>& rkV2 = m_akPoint[iV2];
        fVolume += rkV0.Dot(rkV1.Cross(rkV2));
    }

    fVolume /= (Real)6.0;
    return fVolume;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::ContainsPoint (const Vector3<Real>& rkP) const
{
    for (int iT = 0; iT < m_akTriangle.GetQuantity(); iT++)
    {
        Real fDistance = m_akPlane[iT].DistanceTo(rkP);
        if ( fDistance < (Real)0.0 )
            return false;
    }

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
Real ConvexPolyhedron3<Real>::GetDistance (const Vector3<Real>& rkEye, int iT,
    vector<Real>& rafDistance) const
{
    // Signed distance from eye to plane of triangle.  When distance is
    // positive, triangle is visible from eye (front-facing).  When distance
    // is negative, triangle is not visible from eye (back-facing).  When
    // distance is zero, triangle is visible "on-edge" from eye.