_octree_element_8h_source.html

 //

 //  OctreeElement.h

 //  libraries/octree/src

 //

 //  Created by Stephen Birarda on 3/13/13.

 //  Copyright 2013 High Fidelity, Inc.

 //

 //  Distributed under the Apache License, Version 2.0.

 //  See the accompanying file LICENSE or http://www.apache.org/licenses/LICENSE-2.0.html

 //


 #ifndef hifi_OctreeElement_h

 #define hifi_OctreeElement_h


 //#define SIMPLE_CHILD_ARRAY

 #define SIMPLE_EXTERNAL_CHILDREN


 #include <atomic>


 #include <QReadWriteLock>


 #include <OctalCode.h>

 #include <SharedUtil.h>

 #include <ViewFrustum.h>


 #include "AACube.h"

 #include "OctreeConstants.h"


 using AtomicUIntStat = std::atomic<uintmax_t>;


 class EncodeBitstreamParams;

 class Octree;

 class OctreeElement;

 class OctreePacketData;

 class ReadBitstreamToTreeParams;

 class Shape;

 class VoxelSystem;


 using OctreeElementPointer = std::shared_ptr<OctreeElement>;

 using OctreeElementWeakPointer = std::weak_ptr<OctreeElement>;

 using ConstOctreeElementPointer = std::shared_ptr<const OctreeElement>;

 using OctreePointer = std::shared_ptr<Octree>;


 class OctreeElement: public std::enable_shared_from_this<OctreeElement> {


 protected:

     // can only be constructed by derived implementation

     OctreeElement();


     virtual OctreeElementPointer createNewElement(unsigned char * octalCode = NULL) = 0;


 public:

     virtual void init(unsigned char * octalCode);

     virtual ~OctreeElement();


     // methods you can and should override to implement your tree functionality


     virtual OctreeElementPointer addChildAtIndex(int childIndex);


     virtual void calculateAverageFromChildren() { }


     virtual bool collapseChildren() { return false; }


     virtual bool hasContent() const { return isLeaf(); }


     virtual bool hasDetailedContent() const { return isLeaf(); }


     virtual void splitChildren() { }


     virtual bool requiresSplit() const { return false; }


     typedef enum { COMPLETED, PARTIAL, NONE } AppendState;


     virtual void debugExtraEncodeData(EncodeBitstreamParams& params) const { }


     virtual int readElementDataFromBuffer(const unsigned char* data, int bytesLeftToRead, ReadBitstreamToTreeParams& args)

                     { return 0; }


     virtual bool isRendered() const { return getShouldRender(); }


     virtual bool deleteApproved() const { return true; }


     virtual bool canPickIntersect() const { return isLeaf(); }

     virtual bool findSpherePenetration(const glm::vec3& center, float radius,

                         glm::vec3& penetration, void** penetratedObject) const;


     // Base class methods you don't need to implement

     const unsigned char* getOctalCode() const { return (_octcodePointer) ? _octalCode.pointer : &_octalCode.buffer[0]; }

     OctreeElementPointer getChildAtIndex(int childIndex) const;

     void deleteChildAtIndex(int childIndex);

     OctreeElementPointer removeChildAtIndex(int childIndex);

     bool isParentOf(const OctreeElementPointer& possibleChild) const;


     bool safeDeepDeleteChildAtIndex(int childIndex, int recursionCount = 0);


     const AACube& getAACube() const { return _cube; }

     const glm::vec3& getCorner() const { return _cube.getCorner(); }

     float getScale() const { return _cube.getScale(); }

     int getLevel() const { return numberOfThreeBitSectionsInCode(getOctalCode()) + 1; }


     float getEnclosingRadius() const;

     bool isInView(const ViewFrustum& viewFrustum) const { return computeViewIntersection(viewFrustum) != ViewFrustum::OUTSIDE; }

     ViewFrustum::intersection computeViewIntersection(const ViewFrustum& viewFrustum) const;

     float distanceToCamera(const ViewFrustum& viewFrustum) const;

     float furthestDistanceToCamera(const ViewFrustum& viewFrustum) const;


     // points are assumed to be in Voxel Coordinates (not TREE_SCALE'd)

     float distanceSquareToPoint(const glm::vec3& point) const; // when you don't need the actual distance, use this.

     float distanceToPoint(const glm::vec3& point) const;


     bool isLeaf() const { return _childBitmask == 0; }

     int getChildCount() const { return numberOfOnes(_childBitmask); }

     void printDebugDetails(const char* label) const;

     bool isDirty() const { return _isDirty; }

     void clearDirtyBit() { _isDirty = false; }

     void setDirtyBit() { _isDirty = true; }

     bool hasChangedSince(quint64 time) const { return (_lastChanged > time); }

     void markWithChangedTime();

     quint64 getLastChanged() const { return _lastChanged; }

     void handleSubtreeChanged(OctreePointer myTree);


     // Used by VoxelSystem for rendering in/out of view and LOD

     void setShouldRender(bool shouldRender);

     bool getShouldRender() const { return _shouldRender; }


     void setSourceUUID(const QUuid& sourceID);

     QUuid getSourceUUID() const;

     uint16_t getSourceUUIDKey() const { return _sourceUUIDKey; }

     bool matchesSourceUUID(const QUuid& sourceUUID) const;

     static uint16_t getSourceNodeUUIDKey(const QUuid& sourceUUID);


     static void resetPopulationStatistics();

     static unsigned long getNodeCount() { return _voxelNodeCount; }

     static unsigned long getInternalNodeCount() { return _voxelNodeCount - _voxelNodeLeafCount; }

     static unsigned long getLeafNodeCount() { return _voxelNodeLeafCount; }


     static quint64 getOctreeMemoryUsage() { return _octreeMemoryUsage; }

     static quint64 getOctcodeMemoryUsage() { return _octcodeMemoryUsage; }

     static quint64 getExternalChildrenMemoryUsage() { return _externalChildrenMemoryUsage; }

     static quint64 getTotalMemoryUsage() { return _octreeMemoryUsage + _octcodeMemoryUsage + _externalChildrenMemoryUsage; }


     static quint64 getGetChildAtIndexTime() { return _getChildAtIndexTime; }

     static quint64 getGetChildAtIndexCalls() { return _getChildAtIndexCalls; }

     static quint64 getSetChildAtIndexTime() { return _setChildAtIndexTime; }

     static quint64 getSetChildAtIndexCalls() { return _setChildAtIndexCalls; }


     static quint64 getExternalChildrenCount() { return _externalChildrenCount; }

     static quint64 getChildrenCount(int childCount) { return _childrenCount[childCount]; }


     enum ChildIndex {

         CHILD_BOTTOM_RIGHT_NEAR = 0,

         CHILD_BOTTOM_RIGHT_FAR = 1,

         CHILD_TOP_RIGHT_NEAR = 2,

         CHILD_TOP_RIGHT_FAR = 3,

         CHILD_BOTTOM_LEFT_NEAR = 4,

         CHILD_BOTTOM_LEFT_FAR = 5,

         CHILD_TOP_LEFT_NEAR = 6,

         CHILD_TOP_LEFT_FAR = 7,

         CHILD_UNKNOWN = -1

     };


     struct HalfSpace {

         enum {

             None    = 0x00,

             Bottom  = 0x01,

             Top     = 0x02,

             Right   = 0x04,

             Left    = 0x08,

             Near    = 0x10,

             Far     = 0x20,

             All     = 0x3f,

         };

     };


     OctreeElementPointer getOrCreateChildElementAt(float x, float y, float z, float s);

     OctreeElementPointer getOrCreateChildElementContaining(const AACube& box);

     OctreeElementPointer getOrCreateChildElementContaining(const AABox& box);

     int getMyChildContaining(const AACube& cube) const;

     int getMyChildContaining(const AABox& box) const;

     int getMyChildContainingPoint(const glm::vec3& point) const;


     void bumpChangedContent() { _lastChangedContent = usecTimestampNow(); }

     uint64_t getLastChangedContent() const { return _lastChangedContent; }


 protected:


     void deleteAllChildren();

     void setChildAtIndex(int childIndex, const OctreeElementPointer& child);


     void calculateAACube();


     AACube _cube;


     union octalCode_t {

       unsigned char buffer[8];

       unsigned char* pointer;

     } _octalCode;


     quint64 _lastChanged;

     uint64_t _lastChangedContent { 0 };


 #ifdef SIMPLE_CHILD_ARRAY

     OctreeElementPointer _simpleChildArray[8];

 #endif


 #ifdef SIMPLE_EXTERNAL_CHILDREN

     // union children_t {

     OctreeElementPointer _childrenSingle;

     OctreeElementPointer _externalChildren[NUMBER_OF_CHILDREN];

     // } _children;

 #endif


     uint16_t _sourceUUIDKey;


     // Support for _sourceUUID, we use these static member variables to track the UUIDs that are

     // in use by various voxel server nodes. We map the UUID strings into an 16 bit key, this limits us to at

     // most 65k voxel servers in use at a time within the client. Which is far more than we need.

     static uint16_t _nextUUIDKey; // start at 1, 0 is reserved for NULL

     static std::map<QString, uint16_t> _mapSourceUUIDsToKeys;

     static std::map<uint16_t, QString> _mapKeysToSourceUUIDs;


     unsigned char _childBitmask;     // 1 byte


     bool _falseColored : 1,

          _isDirty : 1,

          _shouldRender : 1,

          _octcodePointer : 1,

          _unknownBufferIndex : 1,

          _childrenExternal : 1;


     static AtomicUIntStat _voxelNodeCount;

     static AtomicUIntStat _voxelNodeLeafCount;


     static AtomicUIntStat _octreeMemoryUsage;

     static AtomicUIntStat _octcodeMemoryUsage;

     static AtomicUIntStat _externalChildrenMemoryUsage;


     static AtomicUIntStat _getChildAtIndexTime;

     static AtomicUIntStat _getChildAtIndexCalls;

     static AtomicUIntStat _setChildAtIndexTime;

     static AtomicUIntStat _setChildAtIndexCalls;


     static AtomicUIntStat _externalChildrenCount;

     static AtomicUIntStat _childrenCount[NUMBER_OF_CHILDREN + 1];

 };


 #endif // hifi_OctreeElement_h

OctreePacketData
Handles packing of the data portion of PacketType_OCTREE_DATA messages.
Definition: OctreePacketData.h:93

OctreeElement::octalCode_t
Client and server, axis aligned box for bounds of this voxel, 48 bytes.
Definition: OctreeElement.h:222