////  EntityTree.cpp//  libraries/entities/src////  Created by Brad Hefta-Gaub on 12/4/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// #include <PerfStat.h> #include "EntityTree.h"#include "EntitySimulation.h" #include "AddEntityOperator.h"#include "DeleteEntityOperator.h"#include "MovingEntitiesOperator.h"#include "UpdateEntityOperator.h" EntityTree::EntityTree(bool shouldReaverage) : Octree(shouldReaverage), _simulation(NULL) {    _rootElement = createNewElement();    _lightsArePickable = true; // assume they are by default} EntityTree::~EntityTree() {    eraseAllOctreeElements(false);} EntityTreeElement* EntityTree::createNewElement(unsigned char * octalCode) {    EntityTreeElement* newElement = new EntityTreeElement(octalCode);    newElement->setTree(this);    return newElement;} void EntityTree::eraseAllOctreeElements(bool createNewRoot) {    // this would be a good place to clean up our entities...    if (_simulation) {        _simulation->clearEntities();    }    foreach (EntityTreeElement* element, _entityToElementMap) {        element->cleanupEntities();    }    _entityToElementMap.clear();    Octree::eraseAllOctreeElements(createNewRoot);} bool EntityTree::handlesEditPacketType(PacketType packetType) const {    // we handle these types of "edit" packets    switch (packetType) {        case PacketTypeEntityAddOrEdit:        case PacketTypeEntityErase:            return true;        default:            return false;    }} /// Give an EntityItemID and EntityItemProperties, this will either find the correct entity that already exists/// in the tree or it will create a new entity of the type specified by the properties and return that item./// In the case that it creates a new item, the item will be properly added to the tree and all appropriate lookup hashes.EntityItem* EntityTree::getOrCreateEntityItem(const EntityItemID& entityID, const EntityItemProperties& properties) {    EntityItem* result = NULL;     // we need to first see if we already have the entity in our tree by finding the containing element of the entity    EntityTreeElement* containingElement = getContainingElement(entityID);    if (containingElement) {        result = containingElement->getEntityWithEntityItemID(entityID);    }        // if the element does not exist, then create a new one of the specified type...    if (!result) {        result = addEntity(entityID, properties);    }    return result;} /// Adds a new entity item to the treevoid EntityTree::postAddEntity(EntityItem* entity) {    assert(entity);    // check to see if we need to simulate this entity..    if (_simulation) {        _simulation->addEntity(entity);    }    _isDirty = true;    emit addingEntity(entity->getEntityItemID());} bool EntityTree::updateEntity(const EntityItemID& entityID, const EntityItemProperties& properties) {    EntityTreeElement* containingElement = getContainingElement(entityID);    if (!containingElement) {        qDebug() << "UNEXPECTED!!!!  EntityTree::updateEntity() entityID doesn't exist!!! entityID=" << entityID;        return false;    }     EntityItem* existingEntity = containingElement->getEntityWithEntityItemID(entityID);    if (!existingEntity) {        qDebug() << "UNEXPECTED!!!! don't call updateEntity() on entity items that don't exist. entityID=" << entityID;        return false;    }        // enforce support for locked entities. If an entity is currently locked, then the only    // property we allow you to change is the locked property.    if (existingEntity->getLocked()) {        if (properties.lockedChanged()) {            bool wantsLocked = properties.getLocked();            if (!wantsLocked) {                EntityItemProperties tempProperties;                tempProperties.setLocked(wantsLocked);                UpdateEntityOperator theOperator(this, containingElement, existingEntity, tempProperties);                recurseTreeWithOperator(&theOperator);                _isDirty = true;                if (_simulation && existingEntity->getUpdateFlags() != 0) {                    _simulation->entityChanged(existingEntity);                }            }        }    } else {        // check to see if we need to simulate this entity...        QString entityScriptBefore = existingEntity->getScript();            UpdateEntityOperator theOperator(this, containingElement, existingEntity, properties);        recurseTreeWithOperator(&theOperator);        _isDirty = true;         if (_simulation && existingEntity->getUpdateFlags() != 0) {            _simulation->entityChanged(existingEntity);        }         QString entityScriptAfter = existingEntity->getScript();        if (entityScriptBefore != entityScriptAfter) {            emitEntityScriptChanging(entityID); // the entity script has changed        }    }        containingElement = getContainingElement(entityID);    if (!containingElement) {        qDebug() << "UNEXPECTED!!!! after updateEntity() we no longer have a containing element??? entityID=" << entityID;        return false;    }        return true;}  EntityItem* EntityTree::addEntity(const EntityItemID& entityID, const EntityItemProperties& properties) {    EntityItem* result = NULL;     // NOTE: This method is used in the client and the server tree. In the client, it's possible to create EntityItems     // that do not yet have known IDs. In the server tree however we don't want to have entities without known IDs.    if (getIsServer() && !entityID.isKnownID) {        qDebug() << "UNEXPECTED!!! ----- EntityTree::addEntity()... (getIsSever() && !entityID.isKnownID)";        return result;    }     // You should not call this on existing entities that are already part of the tree! Call updateEntity()    EntityTreeElement* containingElement = getContainingElement(entityID);    if (containingElement) {        qDebug() << "UNEXPECTED!!! ----- don't call addEntity() on existing entity items. entityID=" << entityID                     << "containingElement=" << containingElement;        return result;    }     // construct the instance of the entity    EntityTypes::EntityType type = properties.getType();    result = EntityTypes::constructEntityItem(type, entityID, properties);     if (result) {        // Recurse the tree and store the entity in the correct tree element        AddEntityOperator theOperator(this, result);        recurseTreeWithOperator(&theOperator);         postAddEntity(result);    }    return result;}  void EntityTree::trackDeletedEntity(EntityItem* entity) {    if (_simulation) {        _simulation->removeEntity(entity);    }    // this is only needed on the server to send delete messages for recently deleted entities to the viewers    if (getIsServer()) {        // set up the deleted entities ID        quint64 deletedAt = usecTimestampNow();        _recentlyDeletedEntitiesLock.lockForWrite();        _recentlyDeletedEntityItemIDs.insert(deletedAt, entity->getEntityItemID().id);        _recentlyDeletedEntitiesLock.unlock();    }} void EntityTree::emitEntityScriptChanging(const EntityItemID& entityItemID) {    emit entityScriptChanging(entityItemID);} void EntityTree::setSimulation(EntitySimulation* simulation) {    if (simulation) {        // assert that the simulation's backpointer has already been properly connected        assert(simulation->getEntityTree() == this);    }     if (_simulation && _simulation != simulation) {        // It's important to clearEntities() on the simulation since taht will update each        // EntityItem::_simulationState correctly so as to not confuse the next _simulation.        _simulation->clearEntities();    }    _simulation = simulation;} void EntityTree::deleteEntity(const EntityItemID& entityID) {    emit deletingEntity(entityID);     // NOTE: callers must lock the tree before using this method    DeleteEntityOperator theOperator(this, entityID);    recurseTreeWithOperator(&theOperator);    _isDirty = true;} void EntityTree::deleteEntities(QSet<EntityItemID> entityIDs) {    // NOTE: callers must lock the tree before using this method    DeleteEntityOperator theOperator(this);    foreach(const EntityItemID& entityID, entityIDs) {        // tell our delete operator about this entityID        theOperator.addEntityIDToDeleteList(entityID);        emit deletingEntity(entityID);    }     recurseTreeWithOperator(&theOperator);    _isDirty = true;} /// This method is used to find and fix entity IDs that are shifting from creator token based to known ID based entity IDs. /// This should only be used on a client side (viewing) tree. The typical usage is that a local editor has been creating /// entities in the local tree, those entities have creatorToken based entity IDs. But those entity edits are also sent up to/// the server, and the server eventually sends back to the client two messages that can come in varying order. The first /// message would be a typical query/viewing data message conversation in which the viewer "sees" the newly created entity. /// Those entities that have been seen, will have the authoritative "known ID". Therefore there is a potential that there can /// be two copies of the same entity in the tree: the "local only" "creator token" version of the entity and the "seen" /// "knownID" version of the entity. The server also sends an "entityAdded" message to the client which contains the mapping /// of the creator token to the known ID. These messages can come in any order, so we need to handle the follow cases://////     Case A: The local edit occurs, the addEntity message arrives, the "viewed data" has not yet arrived.///             In this case, we can expect that our local tree has only one copy of the entity (the creator token), ///             and we only really need to fix up that entity with a new version of the ID that includes the knownID//////     Case B: The local edit occurs, the "viewed data" for the new entity arrives, then the addEntity message arrives.///             In this case, we can expect that our local tree has two copies of the entity (the creator token, and the///             known ID version). We end up with two version of the entity because the server sends viewers only the ///             known ID version without a creator token. And we don't yet know the mapping until we get the mapping message.///             In this case we need to fix up that entity with a new version of the ID that includes the knownID and///             we need to delete the extra copy of the entity.////// This method handles both of these cases.////// NOTE: unlike some operations on the tree, this process does not mark the tree as being changed. This is because/// we're not changing the content of the tree, we're only changing the internal IDs that map entities from creator/// based to known IDs. This means we don't have to recurse the tree to mark the changed path as dirty.void EntityTree::handleAddEntityResponse(const QByteArray& packet) {     if (!getIsClient()) {        qDebug() << "UNEXPECTED!!! EntityTree::handleAddEntityResponse() with !getIsClient() ***";        return;    }     const unsigned char* dataAt = reinterpret_cast<const unsigned char*>(packet.data());    int numBytesPacketHeader = numBytesForPacketHeader(packet);    int bytesRead = numBytesPacketHeader;    dataAt += numBytesPacketHeader;     uint32_t creatorTokenID;    memcpy(&creatorTokenID, dataAt, sizeof(creatorTokenID));    dataAt += sizeof(creatorTokenID);    bytesRead += sizeof(creatorTokenID);     QUuid entityID = QUuid::fromRfc4122(packet.mid(bytesRead, NUM_BYTES_RFC4122_UUID));    dataAt += NUM_BYTES_RFC4122_UUID;     // First, look for the existing entity in the tree..    EntityItemID searchEntityID;    searchEntityID.id = entityID;    searchEntityID.creatorTokenID = creatorTokenID;     lockForWrite();     // find the creator token version, it's containing element, and the entity itself        EntityItem* foundEntity = NULL;    EntityItemID  creatorTokenVersion = searchEntityID.convertToCreatorTokenVersion();    EntityItemID  knownIDVersion = searchEntityID.convertToKnownIDVersion();      // First look for and find the "viewed version" of this entity... it's possible we got    // the known ID version sent to us between us creating our local version, and getting this    // remapping message. If this happened, we actually want to find and delete that version of    // the entity.    EntityTreeElement* knownIDVersionContainingElement = getContainingElement(knownIDVersion);    if (knownIDVersionContainingElement) {        foundEntity = knownIDVersionContainingElement->getEntityWithEntityItemID(knownIDVersion);        if (foundEntity) {            knownIDVersionContainingElement->removeEntityWithEntityItemID(knownIDVersion);            setContainingElement(knownIDVersion, NULL);        }    }     EntityTreeElement* creatorTokenContainingElement = getContainingElement(creatorTokenVersion);    if (creatorTokenContainingElement) {        foundEntity = creatorTokenContainingElement->getEntityWithEntityItemID(creatorTokenVersion);        if (foundEntity) {            creatorTokenContainingElement->updateEntityItemID(creatorTokenVersion, knownIDVersion);            setContainingElement(creatorTokenVersion, NULL);            setContainingElement(knownIDVersion, creatorTokenContainingElement);                        // because the ID of the entity is switching, we need to emit these signals for any             // listeners who care about the changing of IDs            emit changingEntityID(creatorTokenVersion, knownIDVersion);        }    }    unlock();}  class FindNearPointArgs {public:    glm::vec3 position;    float targetRadius;    bool found;    const EntityItem* closestEntity;    float closestEntityDistance;};  bool EntityTree::findNearPointOperation(OctreeElement* element, void* extraData) {    FindNearPointArgs* args = static_cast<FindNearPointArgs*>(extraData);    EntityTreeElement* entityTreeElement = static_cast<EntityTreeElement*>(element);     glm::vec3 penetration;    bool sphereIntersection = entityTreeElement->getAACube().findSpherePenetration(args->position,                                                                    args->targetRadius, penetration);     // If this entityTreeElement contains the point, then search it...    if (sphereIntersection) {        const EntityItem* thisClosestEntity = entityTreeElement->getClosestEntity(args->position);         // we may have gotten NULL back, meaning no entity was available        if (thisClosestEntity) {            glm::vec3 entityPosition = thisClosestEntity->getPosition();            float distanceFromPointToEntity = glm::distance(entityPosition, args->position);             // If we're within our target radius            if (distanceFromPointToEntity <= args->targetRadius) {                // we are closer than anything else we've found                if (distanceFromPointToEntity < args->closestEntityDistance) {                    args->closestEntity = thisClosestEntity;                    args->closestEntityDistance = distanceFromPointToEntity;                    args->found = true;                }            }        }         // we should be able to optimize this...        return true; // keep searching in case children have closer entities    }     // if this element doesn't contain the point, then none of it's children can contain the point, so stop searching    return false;} const EntityItem* EntityTree::findClosestEntity(glm::vec3 position, float targetRadius) {    FindNearPointArgs args = { position, targetRadius, false, NULL, FLT_MAX };    lockForRead();    // NOTE: This should use recursion, since this is a spatial operation    recurseTreeWithOperation(findNearPointOperation, &args);    unlock();    return args.closestEntity;} class FindAllNearPointArgs {public:    glm::vec3 position;    float targetRadius;    QVector<const EntityItem*> entities;};  bool EntityTree::findInSphereOperation(OctreeElement* element, void* extraData) {    FindAllNearPointArgs* args = static_cast<FindAllNearPointArgs*>(extraData);    glm::vec3 penetration;    bool sphereIntersection = element->getAACube().findSpherePenetration(args->position,                                                                    args->targetRadius, penetration);     // If this element contains the point, then search it...    if (sphereIntersection) {        EntityTreeElement* entityTreeElement = static_cast<EntityTreeElement*>(element);        entityTreeElement->getEntities(args->position, args->targetRadius, args->entities);        return true; // keep searching in case children have closer entities    }     // if this element doesn't contain the point, then none of it's children can contain the point, so stop searching    return false;} // NOTE: assumes caller has handled lockingvoid EntityTree::findEntities(const glm::vec3& center, float radius, QVector<const EntityItem*>& foundEntities) {    FindAllNearPointArgs args = { center, radius };    // NOTE: This should use recursion, since this is a spatial operation    recurseTreeWithOperation(findInSphereOperation, &args);     // swap the two lists of entity pointers instead of copy    foundEntities.swap(args.entities);} class FindEntitiesInCubeArgs {public:    FindEntitiesInCubeArgs(const AACube& cube)         : _cube(cube), _foundEntities() {    }     AACube _cube;    QVector<EntityItem*> _foundEntities;}; bool EntityTree::findInCubeOperation(OctreeElement* element, void* extraData) {    FindEntitiesInCubeArgs* args = static_cast<FindEntitiesInCubeArgs*>(extraData);    const AACube& elementCube = element->getAACube();    if (elementCube.touches(args->_cube)) {        EntityTreeElement* entityTreeElement = static_cast<EntityTreeElement*>(element);        entityTreeElement->getEntities(args->_cube, args->_foundEntities);        return true;    }    return false;} // NOTE: assumes caller has handled lockingvoid EntityTree::findEntities(const AACube& cube, QVector<EntityItem*>& foundEntities) {    FindEntitiesInCubeArgs args(cube);    // NOTE: This should use recursion, since this is a spatial operation    recurseTreeWithOperation(findInCubeOperation, &args);    // swap the two lists of entity pointers instead of copy    foundEntities.swap(args._foundEntities);} EntityItem* EntityTree::findEntityByID(const QUuid& id) {    EntityItemID entityID(id);    return findEntityByEntityItemID(entityID);} EntityItem* EntityTree::findEntityByEntityItemID(const EntityItemID& entityID) /*const*/ {    EntityItem* foundEntity = NULL;    EntityTreeElement* containingElement = getContainingElement(entityID);    if (containingElement) {        foundEntity = containingElement->getEntityWithEntityItemID(entityID);    }    return foundEntity;} EntityItemID EntityTree::assignEntityID(const EntityItemID& entityItemID) {    if (!getIsServer()) {        qDebug() << "UNEXPECTED!!! assignEntityID should only be called on a server tree. entityItemID:" << entityItemID;        return entityItemID;    }     if (getContainingElement(entityItemID)) {        qDebug() << "UNEXPECTED!!! don't call assignEntityID() for existing entityIDs. entityItemID:" << entityItemID;        return entityItemID;    }     // The EntityItemID is responsible for assigning actual IDs and keeping track of them.    return entityItemID.assignActualIDForToken();} int EntityTree::processEditPacketData(PacketType packetType, const unsigned char* packetData, int packetLength,                    const unsigned char* editData, int maxLength, const SharedNodePointer& senderNode) {     if (!getIsServer()) {        qDebug() << "UNEXPECTED!!! processEditPacketData() should only be called on a server tree.";        return 0;    }     int processedBytes = 0;    // we handle these types of "edit" packets    switch (packetType) {        case PacketTypeEntityErase: {            QByteArray dataByteArray((const char*)editData, maxLength);            processedBytes = processEraseMessageDetails(dataByteArray, senderNode);            break;        }                case PacketTypeEntityAddOrEdit: {            EntityItemID entityItemID;            EntityItemProperties properties;            bool validEditPacket = EntityItemProperties::decodeEntityEditPacket(editData, maxLength,                                                    processedBytes, entityItemID, properties);             // If we got a valid edit packet, then it could be a new entity or it could be an update to            // an existing entity... handle appropriately            if (validEditPacket) {                            // If this is a knownID, then it should exist in our tree                if (entityItemID.isKnownID) {                    // search for the entity by EntityItemID

Lines 1–500 of 938. Load more