QuadTree.h

Go to the documentation of this file.

/*  Copyright (C) 2003-2021 Free Electron Organization
    Any use of this software requires a license.  If a valid license
    was not distributed with this file, visit freeelectron.org. */

/** @file */

#ifndef __surface_QuadTree_h__
#define __surface_QuadTree_h__

namespace fe
{
namespace ext
{

/**************************************************************************//**
    @brief Triangular storage using divisions by quarters

    @ingroup surface
*//***************************************************************************/
class FE_DL_EXPORT QuadTree:
    public FlatTree,
    public ObjectSafeShared<QuadTree>,
    public CastableAs<QuadTree>
{
    public:
                QuadTree(void);
virtual         ~QuadTree(void);

virtual void    setRefinement(U32 a_refinement) { m_subdivMax=a_refinement; }

virtual void    populate(
                        const Vector3i* a_pElementArray,
                        const SpatialVector* a_pVertexArray,
                        const SpatialVector* a_pNormalArray,
                        const Vector2* a_pUVArray,
                        const Color* a_pColorArray,
                        const I32* a_pTriangleIndexArray,
                        const I32* a_pPointIndexArray,
                        const I32* a_pPrimitiveIndexArray,
                        const I32* a_pPartitionIndexArray,
                        U32 a_primitives,U32 a_vertices,
                        const SpatialVector& a_center,F32 a_radius);
virtual Real    nearestPoint(const SpatialVector& a_origin,
                        Real a_maxDistance,BWORD a_anyHit,U32 a_hitLimit,
                        const sp<PartitionI>& a_rspPartition,
                        Array< sp<SpatialTreeI::Hit> >& a_rHitArray)
                        const;
virtual Real    rayImpact(const SpatialVector& a_origin,
                        const SpatialVector& a_direction,
                        Real a_maxDistance,BWORD a_anyHit,U32 a_hitLimit,
                        const sp<PartitionI>& a_rspPartition,
                        Array< sp<SpatialTreeI::Hit> >& a_rHitArray)
                        const;

virtual void    draw(sp<DrawI> a_spDrawI,const fe::Color* a_pColor) const;

static  void    expandBox(SpatialVector& a_rMin,SpatialVector& a_rMax,
                        const SpatialVector& a_rLowPoint,
                        const SpatialVector& a_rHighPoint);

        Real    nearestTo(BWORD a_mutable,BWORD a_directional,
                        const SpatialVector& a_origin,
                        const SpatialVector& a_direction,
                        Real a_maxDistance,BWORD a_anyHit,U32 a_hitLimit,
                        const sp<PartitionI>& a_rspPartition,
                        Array< sp<SpatialTreeI::Hit> >& a_rHitArray,
                        U32 a_subdivMax) const;

        void    age(void);

    class Key
    {
        public:
            U32             m_ballIndex;
            SpatialVector   m_center;

    static  int     compare(const void* a_pVoid1,const void* a_pVoid2);
    };

    class FE_DL_EXPORT BaseNode:
        public DAGNode,
        public CastableAs<BaseNode>
    {
        public:
            U32             m_level;
            String          m_debugText;

            Vector4         m_boundSphere;

                            //* bounding box
            SpatialVector   m_boundMin;
            SpatialVector   m_boundMax;

                            BaseNode(void):
                                m_level(0)
                            {
                                setName("QuadTree::BaseNode");
                                set(m_boundSphere);
                            }
    virtual                 ~BaseNode(void)                                 {}

            void            subdivide(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    const Key* a_pKeys,
                                    U32 a_keyIndex,U32 a_keyCount,
                                    U32 a_level,U32 a_maxLevel,
                                    U32 a_timeStamp);

    virtual void            subdivideOne(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_triangleIndex,
                                    U32 a_level,U32 a_maxLevel,
                                    U32 a_timeStamp)                        =0;
    virtual void            subdivideAll(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_level,U32 a_maxLevel,
                                    U32 a_timeStamp)                        =0;

            void            draw(sp<DrawI> a_spDrawI,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Color* a_pColor,
                                    U32 a_level) const;
    static  void            calcFrames(
                                    SpatialTransform& a_rTransform1,
                                    SpatialTransform& a_rTransform2,
                                    const SpatialVector& a_rVertex1,
                                    const SpatialVector& a_rNormal1,
                                    const SpatialVector& a_rVertex2,
                                    const SpatialVector& a_rNormal2);
            Real            separation(const SpatialVector& a_origin) const;

            void            nearestTo(BWORD a_mutable,BWORD a_directional,
                                    const SpatialVector& a_origin,
                                    const SpatialVector& a_direction,
                                    Real a_maxDistance,BWORD a_anyHit,
                                    U32 a_hitLimit,
                                    const sp<PartitionI>& a_rspPartition,
                                    Array< sp<SpatialTreeI::Hit> >&
                                    a_rHitArray,
                                    CountedPool<Hit>& a_rHitPool,
                                    U32 a_subdivMax,
                                    SurfaceI::Accuracy a_accuracy,
                                    const Vector3i* a_pElementArray,
                                    const I32* a_pPointIndexArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    const Color* a_pColorArray,
                                    const Ball* a_pBallArray,
                                    U32 a_timeStamp) const;

    virtual I32             face(U32 a_keyIndex,
                                    const Ball* a_pBallArray) const         =0;
    virtual U32             faceCount(void) const                           =0;
    virtual
    const I32*              facePointIndex(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const I32* a_pPointIndexArray,
                                    U32 a_keyIndex) const                   =0;
    virtual
    const SpatialVector*    faceVertex(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    U32 a_keyIndex) const                   =0;
    virtual
    const SpatialVector*    faceNormal(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pNormalArray,
                                    U32 a_keyIndex) const                   =0;
    virtual
    const Vector2*          faceUV(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_keyIndex) const                   =0;
    virtual
    const Color*            faceColor(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const Color* a_pColorArray,
                                    U32 a_keyIndex) const                   =0;

    virtual I32             ballIndex(U32 a_keyIndex) const     { return -1; }
    virtual
    const Vector4           sphereData(U32 a_keyIndex,
                                    const Ball* a_pBallArray) const
                            {   return Vector4(0.0f,0.0f,0.0f,0.0f); }

            void            prune(U32 a_timeStamp);
    };

    class FE_DL_EXPORT Node:
        public BaseNode,
        public CastableAs<Node>
    {
        public:
            Key*            m_pKeyArray;
            U32             m_keyCount;

                            //* only for QuadTree::addJob()
            hp<QuadTree>    m_hpQuadTree;

                            Node(void):
                                m_pKeyArray(NULL),
                                m_keyCount(0)
                            {
                                setName("QuadTree::Node");
                            }

    virtual                 ~Node(void)                                     {}

            void            refine(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    SpatialVector* a_pVertexScratch,
                                    const Vector3u& a_divisions,
                                    const Ball* a_pBallArray,
                                    U32 a_capacity);
            void            split(U32 a_axis,Key*& a_rpKeys,U32& a_rKeyCount,
                                    U32 divisions,
                                    Key** a_rppKeys,U32* a_rpKeyCount);
    static  U32             quickSelect(Key*& a_rpKeys,U32& a_keyCount,
                                    U32 a_selectIndex,U32 a_axis);
    static  U32             select(Key*& a_rpKeys,U32 a_count,
                                    U32 a_left,U32 a_right,
                                    U32 a_selectIndex,U32 a_axis);
    static  U32             partition(Key*& a_rpKeys,U32 a_count,
                                    U32 a_left,U32 a_right,
                                    U32 a_pivotIndex,U32 a_axis);

            void            calcBounds(
                                    const SpatialVector* a_pVertexArray,
                                    const U32 a_vertexCount);
            void            calcBounds(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    SpatialVector* a_pVertexScratch,
                                    const Ball* a_pBallArray);

    virtual void            subdivideOne(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_triangleIndex,
                                    U32 a_level,U32 a_maxLevel,U32 a_timeStamp);
    virtual void            subdivideAll(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_level,U32 a_maxLevel,
                                    U32 a_timeStamp);

    virtual I32             face(U32 a_keyIndex,const Ball* a_pBallArray) const
                            {   FEASSERT(a_keyIndex<m_keyCount);
                                return a_pBallArray[ballIndex(a_keyIndex)]
                                        .m_faceIndex; }

    virtual U32             faceCount(void) const
                            {   return m_keyCount; }
    virtual
    const I32*              facePointIndex(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const I32* a_pPointIndexArray,
                                    U32 a_keyIndex) const
                            {
                                const U32 faceIndex=
                                        face(a_keyIndex,a_pBallArray);
                                const U32 startIndex=
                                        a_pElementArray[faceIndex][0];
                                return &a_pPointIndexArray[startIndex];
                            }
    virtual
    const SpatialVector*    faceVertex(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    U32 a_keyIndex) const
                            {
                                const U32 faceIndex=
                                        face(a_keyIndex,a_pBallArray);
                                const U32 startIndex=
                                        a_pElementArray[faceIndex][0];
                                return &a_pVertexArray[startIndex];
                            }
    virtual
    const SpatialVector*    faceNormal(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pNormalArray,
                                    U32 a_keyIndex) const
                            {
                                const U32 faceIndex=
                                        face(a_keyIndex,a_pBallArray);
                                const U32 startIndex=
                                        a_pElementArray[faceIndex][0];
                                return &a_pNormalArray[startIndex];
                            }
    virtual
    const Vector2*          faceUV(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_keyIndex) const
                            {
                                const U32 faceIndex=
                                        face(a_keyIndex,a_pBallArray);
                                const U32 startIndex=
                                        a_pElementArray[faceIndex][0];
                                return a_pUVArray? &a_pUVArray[startIndex]:
                                        NULL;
                            }
    virtual
    const Color*            faceColor(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const Color* a_pColorArray,
                                    U32 a_keyIndex) const
                            {
                                const U32 faceIndex=
                                        face(a_keyIndex,a_pBallArray);
                                const U32 startIndex=
                                        a_pElementArray[faceIndex][0];
                                return a_pColorArray?
                                        &a_pColorArray[startIndex]: NULL;
                            }

    virtual I32             ballIndex(U32 a_keyIndex) const
                            {   FEASSERT(a_keyIndex<m_keyCount);
                                return m_pKeyArray[a_keyIndex].m_ballIndex; }
    virtual
    const Vector4           sphereData(U32 a_keyIndex,
                                    const Ball* a_pBallArray) const
                            {   FEASSERT(a_keyIndex<m_keyCount);
                                return a_pBallArray[m_pKeyArray[a_keyIndex]
                                        .m_ballIndex].m_sphere; }
    };

    class FE_DL_EXPORT SubNode:
        public BaseNode,
        public CastableAs<SubNode>
    {
        public:
            Vector3i*       m_pSubdivPrimitiveArray;
            SpatialVector*  m_pSubdivVertexArray;
            SpatialVector*  m_pSubdivNormalArray;
            Vector2*        m_pSubdivUVArray;
            U32             m_serial;
            U32             m_subdivCount;
            U32             m_subdivLevel;
            U32             m_timeStamp;

                            SubNode(void):
                                m_pSubdivPrimitiveArray(NULL),
                                m_pSubdivVertexArray(NULL),
                                m_pSubdivNormalArray(NULL),
                                m_pSubdivUVArray(NULL),
                                m_serial(0),
                                m_subdivCount(0),
                                m_subdivLevel(0),
                                m_timeStamp(0)
                            {
                                setName("QuadTree::SubNode");
                            }

    virtual                 ~SubNode(void)
                            {
                                delete[] m_pSubdivUVArray;
                                delete[] m_pSubdivNormalArray;
                                delete[] m_pSubdivVertexArray;
                                delete[] m_pSubdivPrimitiveArray;
                            }

    virtual void            subdivideOne(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_triangleIndex,
                                    U32 a_level,U32 a_maxLevel,U32 a_timeStamp);
    virtual void            subdivideAll(
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    const SpatialVector* a_pNormalArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_level,U32 a_maxLevel,
                                    U32 a_timeStamp);

                            //* TODO redo
    virtual I32             face(U32 a_keyIndex,const Ball* a_pBallArray) const
                            {   return a_keyIndex; }

    virtual U32             faceCount(void) const
                            {   return m_subdivCount/3; }
    virtual
    const I32*              facePointIndex(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const I32* a_pPointIndexArray,
                                    U32 a_keyIndex) const
                            {
                                return NULL;
                            }
    const SpatialVector*    faceVertex(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pVertexArray,
                                    U32 a_keyIndex) const
//                          {   FEASSERT((a_keyIndex+1)*a_grain<=m_subdivCount);
//                              return &m_pSubdivVertexArray[a_keyIndex*a_grain]; }
                            {
                                const U32 startIndex=
                                        a_pElementArray[a_keyIndex][0];
                                return &m_pSubdivVertexArray[startIndex];
                            }

    virtual
    const SpatialVector*    faceNormal(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const SpatialVector* a_pNormalArray,
                                    U32 a_keyIndex) const
//                          {   FEASSERT((a_keyIndex+1)*a_grain<=m_subdivCount);
//                              return &m_pSubdivNormalArray[a_keyIndex*a_grain]; }
                            {
                                const U32 startIndex=
                                        a_pElementArray[a_keyIndex][0];
                                return &m_pSubdivNormalArray[startIndex];
                            }

    virtual
    const Vector2*          faceUV(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const Vector2* a_pUVArray,
                                    U32 a_keyIndex) const
//                          {   FEASSERT((a_keyIndex+1)*a_grain<=m_subdivCount);
//                              return m_pSubdivUVArray?
//                                      &m_pSubdivUVArray[a_keyIndex*a_grain]:
//                                      NULL; }
                            {
                                const U32 startIndex=
                                        a_pElementArray[a_keyIndex][0];
                                return m_pSubdivUVArray?
                                        &m_pSubdivUVArray[startIndex]:
                                        NULL;
                            }

    virtual
    const Color*            faceColor(
                                    const Ball* a_pBallArray,
                                    const Vector3i* a_pElementArray,
                                    const Color* a_pColorArray,
                                    U32 a_keyIndex) const
                            {
                                //* TODO
                                return NULL;
                            }
    };

    class Child
    {
        public:
                            Child(void): m_spNode(NULL),m_distance(0.0)     {}
            sp<BaseNode>    m_spNode;
            F32             m_distance;

    static  int             compare(const void* a_pVoid1,const void* a_pVoid2);
    };

    class Worker: public Thread::Functor
    {
        public:
                            Worker(sp< JobQueue<I32> > a_spJobQueue,
                                    U32 a_id,String a_stage):
                                m_spJobQueue(a_spJobQueue),
                                m_id(a_id)                                  {}

            void            operate(void);

            void            setObject(sp<Component> a_spQuadTree)
                            {   m_spQuadTree=a_spQuadTree; }

        private:
            sp< JobQueue<I32> > m_spJobQueue;
            U32                 m_id;
            sp<QuadTree>        m_spQuadTree;
    };

    class Job
    {
        public:
                            Job(void)                                       {}
                            ~Job(void)                                      {}

            sp<Node>        m_spNode;
    };

        void                    cacheSpheres(const SpatialVector& a_center,
                                        F32 a_radius);
        void                    buildGraph(void);

        void                    addJob(sp<Node> a_spNode);

const   Job                     lookupJob(I32 a_index);

        sp<Node>                m_spRootNode;
        sp<DrawMode>            m_spWireframe;

    protected:
        void                    prune(void);
        void                    lockSafe(void);
        void                    unlockSafe(void);

        Vector3u                m_divisions;
        U32                     m_capacity;
        U32                     m_subdivMax;
        U32                     m_ageStamp;
        U32                     m_timeStamp;
        U32                     m_verticesUsed;

        sp< Gang<Worker,I32> >  m_spGang;
        Array<Job>              m_jobArray;
};

} /* namespace ext */
} /* namespace fe */

#endif /* __surface_QuadTree_h__ */