//============================================================================================ // Spirenkov Maxim, 2004, 2008 //============================================================================================ // ObjectFindManager (quad tree) //============================================================================================ #include "ObjectsFindManager.h" #define ENABLE_NAN_CHECK //#define ENABLE_NAN_STOP //============================================================================================ //Abb //============================================================================================ __forceinline ObjectsFindManager::Abb::Abb() { } __forceinline ObjectsFindManager::Abb::Abb(const Abb & abb) { minX = abb.minX; maxX = abb.maxX; minZ = abb.minZ; maxZ = abb.maxZ; } __forceinline ObjectsFindManager::Abb::Abb(long _minX, long _maxX, long _minZ, long _maxZ) { minX = _minX; maxX = _maxX; minZ = _minZ; maxZ = _maxZ; } __forceinline bool ObjectsFindManager::Abb::IsInclude(const Abb & abb) const { if(minX <= abb.minX && maxX >= abb.maxX) { if(minZ <= abb.minZ && maxZ >= abb.maxZ) { return true; } } return false; } __forceinline bool ObjectsFindManager::Abb::IsIntersection(const Abb & abb) const { if(minX <= abb.maxX && maxX >= abb.minX) { if(minZ <= abb.maxZ && maxZ >= abb.minZ) { return true; } } return false; } __forceinline long ObjectsFindManager::Abb::MinSize() const { return coremin(maxX - minX, maxZ - minZ); } __forceinline bool ObjectsFindManager::Abb::Set(Vector min, Vector max, bool isChecker) { //Границы const float roundValue = 0.999999f; if(isChecker) { if(min.x > max.x) { Swap(min.x, max.x); } if(min.z > max.z) { Swap(min.z, max.z); } } min.x -= roundValue; min.z -= roundValue; max.x += roundValue; max.z += roundValue; //Проверяем на попадание ректа в рабочий диапазон const float range = 1000000.0f; bool inRange = true; if(!isChecker) { if(min.x < -range || min.x > range) inRange = false; if(min.z < -range || min.z > range) inRange = false; if(max.x < -range || max.x > range) inRange = false; if(max.z < -range || max.z > range) inRange = false; }else{ const float clampValue = range*1.1f; min.x = Clampf(min.x, -clampValue, clampValue); min.z = Clampf(min.z, -clampValue, clampValue); max.x = Clampf(max.x, -clampValue, clampValue); max.z = Clampf(max.z, -clampValue, clampValue); } //Преобразуем результат к целым числам if(inRange) { minX = long(min.x); maxX = long(max.x); minZ = long(min.z); maxZ = long(max.z); /* #ifndef STOP_ASSERTS if(AssertInRange("ObjectsFindManager::Abb::Set", true)) { api->Trace("Inc abb: min = %f, %f; max = %f, %f", min.x, min.z, max.x, max.z); } #endif */ } return inRange; } #ifndef STOP_ASSERTS __forceinline bool ObjectsFindManager::Abb::AssertInRange(const char * prefix, bool noStop) const { const long range = 2000000; bool outOfRange = false; if(minX < -range || minX > range) { outOfRange = true; } if(minZ < -range || minZ > range) { outOfRange = true; } if(maxX < -range || maxX > range) { outOfRange = true; } if(maxZ < -range || maxZ > range) { outOfRange = true; } if(outOfRange) { LogOut(prefix); Assert(noStop); } return outOfRange; } #endif __forceinline void ObjectsFindManager::Abb::LogOut(const char * prefix) const { #ifndef STOP_DEBUG api->Trace("%s Abb: min(x: %i, z: %i) max(x: %i, z: %i)", prefix, minX, minZ, maxX, maxZ); #endif } //============================================================================================ //TreeObject //============================================================================================ ObjectsFindManager::TreeObject::TreeObject(MissionObject * _mo, ObjectsFindManager * _mng) { //Заполняем поля Assert(_mo); Assert(_mng); flags = f_invalidateAbb; node = null; mng = _mng; nextInNode = null; prevInNode = null; nextInList = null; prevInList = null; abb.minX = 0; abb.maxX = 0; abb.minZ = 0; abb.maxZ = 0; center = 0.0f; size = 0.0f; mo = _mo; userData = null; cppFile = null; cppLine = 0; pullCode = 0; tmp = 0; //Добавляемся в список неактивных MoveToInactiveList(); } //Освободить ресурсы void ObjectsFindManager::TreeObject::Release() { //Исключаемся из всех возможных списков Assert(mng); RemoveFromNode(); RemoveFromLists(); //Чистим нужное flags = f_deleted; node = null; mo = null; userData = null; //Удаляем объект Delete(this); // api->Trace("Release object = %x", this); } //Изменить активность void ObjectsFindManager::TreeObject::Activate(bool isActive) { if(isActive) { //Если активны то ничего не делаем if(flags & f_active) { return; } //Пометим флажёк что хотим быть активными flags |= f_active; //Если бокс кривой то больше ничего не делаем if(flags & f_invalidateAbb) { return; } //Переходим в список обновления MoveToUpdateList(); }else{ if(!(flags & f_active)) { return; } //Переходим в список неактивных RemoveFromNode(); MoveToInactiveList(); } } //Активен ли объект bool ObjectsFindManager::TreeObject::IsActivate() { return (flags & f_active) != 0; } //Получить указатель на объект миссии MissionObject & ObjectsFindManager::TreeObject::GetMissionObject() { Assert(mo); return *mo; } //Установить пользовательские данные void ObjectsFindManager::TreeObject::SetUserData(void * data) { userData = data; } //Получить пользовательские данные void * ObjectsFindManager::TreeObject::GetUserData() { return userData; } //Установить матрицу void ObjectsFindManager::TreeObject::SetMatrix(const Matrix & mtx) { #ifdef ENABLE_NAN_CHECK #ifndef STOP_DEBUG if(_isnan(mtx.pos.x) || _isnan(mtx.pos.y) || _isnan(mtx.pos.z) || _isnan(mtx.vx.x) || _isnan(mtx.vx.y) || _isnan(mtx.vx.z) || _isnan(mtx.vy.x) || _isnan(mtx.vy.y) || _isnan(mtx.vy.z) || _isnan(mtx.vz.x) || _isnan(mtx.vz.y) || _isnan(mtx.vz.z)) { api->Trace("%x, matrix = pos(%f, %f, %f), 3x3 = (%f, %f, %f, %f, %f, %f, %f, %f, %f)", this, mtx.pos.x, mtx.pos.y, mtx.pos.z, mtx.vx.x, mtx.vx.y, mtx.vx.z, mtx.vy.x, mtx.vy.y, mtx.vy.z, mtx.vz.x, mtx.vz.y, mtx.vz.z); #ifdef ENABLE_NAN_STOP Assert(false); #endif return; } #endif #endif matrix = mtx; SetToUpdate(); } //Получить матрицу const Matrix & ObjectsFindManager::TreeObject::GetMatrix() const { return matrix; } //Установить локальную позицию описывающего бокса void ObjectsFindManager::TreeObject::SetBoxCenter(float centerX, float centerY, float centerZ) { #ifdef ENABLE_NAN_CHECK #ifndef STOP_DEBUG if(_isnan(centerX) || _isnan(centerY) || _isnan(centerZ)) { api->Trace("%x, ObjectsFindManager::TreeObject::SetBoxCenter(%f, %f, %f)", this, centerX, centerY, centerZ); #ifdef ENABLE_NAN_STOP Assert(false); #endif return; } #endif #endif center.x = centerX; center.y = centerY; center.z = centerZ; SetToUpdate(); } //Установить размер описывающего бокса void ObjectsFindManager::TreeObject::SetBoxSize(float sizeX, float sizeY, float sizeZ) { #ifdef ENABLE_NAN_CHECK #ifndef STOP_DEBUG if(_isnan(sizeX) || _isnan(sizeY) || _isnan(sizeZ)) { api->Trace("%x, ObjectsFindManager::TreeObject::SetBoxSize(%f, %f, %f)", this, sizeX, sizeY, sizeZ); #ifdef ENABLE_NAN_STOP Assert(false); #endif return; } #endif #endif size.x = sizeX; size.y = sizeY; size.z = sizeZ; SetToUpdate(); } //Получить размеры коробки OBB const Vector & ObjectsFindManager::TreeObject::GetBoxSize() { return size; } //Получить центр OBB const Vector & ObjectsFindManager::TreeObject::GetBoxCenter() { return center; } //Получить квадрад, занимаемый на дереве bool ObjectsFindManager::TreeObject::GetQTAbb(Vector & minAbb, Vector & maxAbb) { if(CheckAbb()) { minAbb.x = (float)abb.minX; minAbb.y = 0.0f; minAbb.z = (float)abb.minZ; maxAbb.x = (float)abb.maxX; maxAbb.y = 0.0f; maxAbb.z = (float)abb.maxZ; return true; } return false; } //Следующий в списке нода __forceinline ObjectsFindManager::TreeObject * ObjectsFindManager::TreeObject::NextInNode() { return nextInNode; } //Следующий в мэнеджера списке __forceinline ObjectsFindManager::TreeObject * ObjectsFindManager::TreeObject::NextInList() { return nextInList; } //Получить текущий abb __forceinline const ObjectsFindManager::Abb & ObjectsFindManager::TreeObject::GetAbb() { return abb; } //Получить нод __forceinline ObjectsFindManager::Node * ObjectsFindManager::TreeObject::GetNode() { return node; } //Поставить в список обновления __forceinline void ObjectsFindManager::TreeObject::SetToUpdate() { flags &= ~(f_invalidateAbb | f_isUpdatedAbb); if(flags & f_active) { //Встанем в очередь обновления MoveToUpdateList(); } } //Проверить и если надо пересчитать бокс __forceinline bool ObjectsFindManager::TreeObject::CheckAbb() { if((flags & f_isUpdatedAbb) == 0) { Vector min, max; Box::FindABBforOBB(matrix, center - size*0.5f, center + size*0.5f, min, max, false); bool inRange = abb.Set(min, max, false); /* #ifndef STOP_ASSERTS if(abb.AssertInRange("ObjectsFindManager::TreeObject::CheckAbb - 2", true)) { api->Trace("object = %x", this); api->Trace("f_active = %i", (flags & f_active) != 0); api->Trace("f_isUpdatedAbb = %i", (flags & f_isUpdatedAbb) != 0); api->Trace("f_inUpdateList = %i", (flags & f_inUpdateList) != 0); api->Trace("f_inInactiveList = %i", (flags & f_inInactiveList) != 0); api->Trace("f_invalidateAbb = %i", (flags & f_invalidateAbb) != 0); api->Trace("f_deleted = %i", (flags & f_deleted) != 0); api->Trace("center = %f, %f, %f", center.x, center.y, center.z); api->Trace("size = %f, %f, %f", size.x, size.y, size.z); api->Trace("matrix = pos(%f, %f, %f), 3x3 = (%f, %f, %f, %f, %f, %f, %f, %f, %f)", matrix.pos.x, matrix.pos.y, matrix.pos.z, matrix.vx.x, matrix.vx.y, matrix.vx.z, matrix.vy.x, matrix.vy.y, matrix.vy.z, matrix.vz.x, matrix.vz.y, matrix.vz.z); api->Trace("CheckAbb: min = %f, %f; max = %f, %f", min.x, min.z, max.x, max.z); Assert(false); } #endif */ flags |= f_isUpdatedAbb | f_invalidateAbb; if(inRange) { flags &= ~f_invalidateAbb; } } return (flags & f_invalidateAbb) == 0; } //Добавить себя в список нода __forceinline void ObjectsFindManager::TreeObject::AddToNode(Node * n) { Assert(n); RemoveFromNode(); nextInNode = n->first; if(nextInNode) { nextInNode->prevInNode = this; } prevInNode = null; n->first = this; n->count++; node = n; } //Удалить себя из списка нода __forceinline void ObjectsFindManager::TreeObject::RemoveFromNode() { if(node) { if(nextInNode) { nextInNode->prevInNode = prevInNode; } if(prevInNode) { prevInNode->nextInNode = nextInNode; prevInNode = null; }else{ Assert(node->first == this); node->first = nextInNode; } nextInNode = null; node->count--; Assert(node->count >= 0); node = null; } } //Поместить объект в список обновления __forceinline void ObjectsFindManager::TreeObject::MoveToUpdateList() { if(flags & f_inInactiveList) { Assert((flags & f_inUpdateList) == 0); RemoveFromList(mng->firstInactive); flags &= ~f_inInactiveList; } if((flags & f_inUpdateList) == 0) { AddToList(mng->firstUpdate); flags |= f_inUpdateList; } } //Поместить объект в список неактивных __forceinline void ObjectsFindManager::TreeObject::MoveToInactiveList() { if(flags & f_inUpdateList) { Assert((flags & f_inInactiveList) == 0); RemoveFromList(mng->firstUpdate); flags &= ~f_inUpdateList; } if((flags & f_inInactiveList) == 0) { AddToList(mng->firstInactive); flags |= f_inInactiveList; } } //Удалить из списков __forceinline void ObjectsFindManager::TreeObject::RemoveFromLists() { if(flags & f_inInactiveList) { Assert((flags & f_inUpdateList) == 0); RemoveFromList(mng->firstInactive); flags &= ~f_inInactiveList; } if(flags & f_inUpdateList) { Assert((flags & f_inInactiveList) == 0); RemoveFromList(mng->firstUpdate); flags &= ~f_inUpdateList; } } //Добавить в список __forceinline void ObjectsFindManager::TreeObject::AddToList(TreeObject * & first) { nextInList = first; if(nextInList) { nextInList->prevInList = this; } prevInList = null; first = this; } //Удалить из списка void ObjectsFindManager::TreeObject::RemoveFromList(TreeObject * & first) { if(nextInList) { nextInList->prevInList = prevInList; } if(prevInList) { prevInList->nextInList = nextInList; prevInList = null; }else{ Assert(first == this); first = nextInList; } nextInList = null; } //Шагнуть по списку обновления __forceinline ObjectsFindManager::TreeObject * ObjectsFindManager::TreeObject::ExtractFirstFromUpdateList() { Assert(!prevInList); TreeObject * obj = nextInList; if(nextInList) { nextInList->prevInList = null; } nextInList = null; Assert(flags & f_inUpdateList); flags &= ~f_inUpdateList; return obj; } //Создать объект дерева __forceinline ObjectsFindManager::TreeObject * ObjectsFindManager::TreeObject::Create(ObjectsFindManager * manager, MissionObject * mo) { Assert(ObjectsFindManagerStorage::ptr); dword code; void * ptr = ObjectsFindManagerStorage::ptr->objects.Alloc(code); TreeObject * obj = new('a', ptr) TreeObject(mo, manager); obj->pullCode = code; return obj; } //Удалить объект дерева __forceinline void ObjectsFindManager::TreeObject::Delete(TreeObject * obj) { Assert(ObjectsFindManagerStorage::ptr); ObjectsFindManagerStorage::ptr->objects.Delete(obj->pullCode); } //============================================================================================ //Node //============================================================================================ __forceinline ObjectsFindManager::Node::Node(const Abb & nodeABB) { abb = nodeABB; cx = (abb.minX + abb.maxX + 1)/2; cz = (abb.minZ + abb.maxZ + 1)/2; child[s_minx_minz] = null; child[s_maxx_minz] = null; child[s_minx_maxz] = null; child[s_maxx_maxz] = null; parent = null; first = null; count = 0; pullCode = 0; } __forceinline ObjectsFindManager::Node::~Node() { Assert(false); } //Найти объекты, касающиеся abb void ObjectsFindManager::Node::FindObjects(const Abb & checkAbb, array & list) { if(checkAbb.IsIntersection(abb)) { //Объекты for(TreeObject * obj = first; obj; obj = obj->NextInNode()) { if(checkAbb.IsIntersection(obj->GetAbb())) { list.Add(obj); } } //Дети if(child) { if(child[s_minx_minz]) { child[s_minx_minz]->FindObjects(checkAbb, list); } if(child[s_maxx_minz]) { child[s_maxx_minz]->FindObjects(checkAbb, list); } if(child[s_minx_maxz]) { child[s_minx_maxz]->FindObjects(checkAbb, list); } if(child[s_maxx_maxz]) { child[s_maxx_maxz]->FindObjects(checkAbb, list); } } } } //Получить нод для размещения объекта с заданным abb ObjectsFindManager::Node * ObjectsFindManager::Node::GetTreeNode(const Abb & objAbb) { //Уже точно известно что objAbb внутри данного нода, смотрим на попадание в детей if(objAbb.maxX < cx) { //Объект лежит полностью в левой половине нода if(objAbb.maxZ < cz) { //Объект лежит полностью в левой-задней половине нода if(child[s_minx_minz]) return child[s_minx_minz]->GetTreeNode(objAbb); //Если объектов на ноде мало, то не рыпаемся if(count < maxObjectsPerNode) return this; //Пробуем углубляться return AddChild(s_minx_minz, abb.minX, cx - 1, abb.minZ, cz - 1); }else if(objAbb.minZ >= cz) { //Объект лежит полностью в левой-передней половине нода if(child[s_minx_maxz]) return child[s_minx_maxz]->GetTreeNode(objAbb); //Если объектов на ноде мало, то не рыпаемся if(count < maxObjectsPerNode) return this; //Пробуем углубляться return AddChild(s_minx_maxz, abb.minX, cx - 1, cz, abb.maxZ); } }else if(objAbb.minX >= cx) { //Объект лежит полностью в правой половине нода if(objAbb.maxZ < cz) { //Объект лежит полностью в правой-задней половине нода if(child[s_maxx_minz]) return child[s_maxx_minz]->GetTreeNode(objAbb); //Если объектов на ноде мало, то не рыпаемся if(count < maxObjectsPerNode) return this; //Пробуем углубляться return AddChild(s_maxx_minz, cx, abb.maxX, abb.minZ, cz - 1); }else if(objAbb.minZ >= cz) { //Объект лежит полностью в правой-передней половине нода if(child[s_maxx_maxz]) return child[s_maxx_maxz]->GetTreeNode(objAbb); //Если объектов на ноде мало, то не рыпаемся if(count < maxObjectsPerNode) return this; //Пробуем углубляться return AddChild(s_maxx_maxz, cx, abb.maxX, cz, abb.maxZ); } } //Объект пересекает границы детей и не может быть положен глубже return this; } //Получить нод для размещения объекта с заданным abb __forceinline ObjectsFindManager::Node * ObjectsFindManager::Node::AddChild(long index, long abb_minX, long abb_maxX, long abb_minZ, long abb_maxZ) { if(abb_maxX - abb_minX >= minNodeSizeForSplit && abb_maxZ - abb_minZ >= minNodeSizeForSplit) { //Размеры позволяют создать ребёнка Node * n = Create(Abb(abb_minX, abb_maxX, abb_minZ, abb_maxZ)); Assert(!child[index]); child[index] = n; n->parent = this; //Маркируем объекты что необходимо будет обновиться объектам for(TreeObject * obj = first; obj; obj = obj->NextInNode()) { obj->SetToUpdate(); } return n; } return this; } //Нарисовать узел, детей и объекты void ObjectsFindManager::Node::Draw(IRender * render, dword level, float levelScale) { #ifndef STOP_DEBUG static const Vector endAbb(0.99999f, 0.0f, 0.99999f); //Рисуем детей for(dword i = 0; i < s_numChilds; i++) { if(child[i]) { child[i]->Draw(render, level + 1, levelScale); } } //Рисуем себя float flevel = level*levelScale; Vector vmin(float(abb.minX), (parent ? level - 1 : level)*levelScale, float(abb.minZ)); Vector vmax(float(abb.maxX), flevel, float(abb.maxZ)); render->DrawBox(vmin, vmax + endAbb, Matrix(), first ? 0xff00ff00 : 0xff0000ff); //Рисуем объекты for(TreeObject * obj = first; obj; obj = obj->NextInNode()) { const Matrix & mtx = obj->GetMatrix(); //Рисуем мировой ящик объекта Vector vmin = obj->GetBoxCenter() - obj->GetBoxSize()*0.5f; Vector vmax = obj->GetBoxCenter() + obj->GetBoxSize()*0.5f; render->DrawBox(vmin, vmax + endAbb, mtx, 0xffffff00); Vector worldCenter = mtx*((vmin + vmax)*0.5f); //Рисуем квадрат на дереве Vector nodeCenter; if(obj->GetQTAbb(vmin, vmax)) { vmin.y = flevel; vmax.y = flevel; vmax += endAbb; render->DrawBox(vmin, vmax, Matrix(), 0xff909f20); nodeCenter = (vmin + vmax)*0.5f; render->Print(nodeCenter, 30.0f, 0.0f, 0xff909f20, "%u", level); }else{ nodeCenter = worldCenter; nodeCenter.y = flevel; } //Линия до нода render->DrawLine(nodeCenter, 0xff0000ff, worldCenter, 0xffffff00); //Подпись render->Print(worldCenter, 100000.0f, 0.0f, 0xff00ff00, "MO: %s%s, 0x%.8x", obj->GetMissionObject().GetObjectID().c_str(), obj->CheckAbb() ? "" : " [invalidate box]", obj); } #endif } //Создать нод __forceinline ObjectsFindManager::Node * ObjectsFindManager::Node::Create(const Abb & nodeABB) { Assert(ObjectsFindManagerStorage::ptr); dword code; void * ptr = ObjectsFindManagerStorage::ptr->nodes.Alloc(code); Node * n = new('a', ptr) Node(nodeABB); n->pullCode = code; return n; } //Удалить нод void ObjectsFindManager::Node::Delete(Node * n) { if(!n) return; Assert(ObjectsFindManagerStorage::ptr); //Удаляем детей Delete(n->child[s_minx_minz]); Delete(n->child[s_maxx_minz]); Delete(n->child[s_minx_maxz]); Delete(n->child[s_maxx_maxz]); //Отписываем от нода объекты while(n->first) { n->first->RemoveFromNode(); } //Удаляем себя ObjectsFindManagerStorage::ptr->nodes.Delete(n->pullCode); } //Вывести ветку в лог void ObjectsFindManager::Node::Dump(dword offset = 0) { #ifndef STOP_DEBUG char buffer[256]; memset(buffer, ' ', sizeof(buffer)); if(offset > sizeof(buffer) - 1) offset = sizeof(buffer) - 1; buffer[offset] = 0; abb.LogOut(buffer); api->Trace("%sCenter: (x: %i, z: %i)", buffer, cx, cz); api->Trace("%sObjects count: %i", buffer, count); const char * names[4]; names[s_minx_minz] = "s_minx_minz"; names[s_maxx_minz] = "s_maxx_minz"; names[s_minx_maxz] = "s_minx_maxz"; names[s_maxx_maxz] = "s_maxx_maxz"; for(long i = 0; i < 4; i++) { if(child[i]) { api->Trace("%s%s = ", buffer, names[i]); api->Trace("%s{", buffer); child[i]->Dump(offset + 2); api->Trace("%s", buffer); api->Trace("%s}", buffer); }else{ api->Trace("%s%s = null", buffer, names[i]); } } #endif } //============================================================================================ //ObjectsFindManager //============================================================================================ ObjectsFindManager::ObjectsFindManager() { root = null; firstUpdate = null; firstInactive = null; } ObjectsFindManager::~ObjectsFindManager() { if(root) { Node::Delete(root); root = null; } } //Создать объект в дереве IMissionQTObject * ObjectsFindManager::CreateObject(MissionObject * mo, const char * cppFile, long cppLine) { TreeObject * obj = TreeObject::Create(this, mo); obj->cppFile = cppFile; obj->cppLine = cppLine; return obj; } //Найти объекты, попадающие в область void ObjectsFindManager::FindObjects(const Vector & minVrt, const Vector & maxVrt, array & list) { //Обновим дерево UpdateTree(); //Получаем целочисленный объём Abb abb; abb.Set(minVrt, maxVrt, true); //Очистим список list.Empty(); //Собираем попадающих в область if(!root) return; root->FindObjects(abb, list); } //Нарисовать дерево и подписать объекты void ObjectsFindManager::Draw(IRender * render, float levelScale) { #ifndef STOP_DEBUG //Обновим дерево UpdateTree(); //Рисуем активные объекты if(root) { root->Draw(render, 0, levelScale); } //Пишем список неактивных объектов под 0 if(firstInactive) { float h = 3.0f; float k = Clampf((h - render->GetView().GetCamPos().y)/h); dword color = (dword(k*255.0f) << 24) | 0x00ff4040; Vector drawPoint = Vector(0.0f, -1.0f, 0.0f); float line = 0.0f; float step = 1.25f; render->Print(drawPoint, 100000.0f, line, color, "Inactive list:"); for(TreeObject * obj = firstInactive; obj; obj = obj->NextInList()) { line += step; render->Print(drawPoint, 100000.0f, line, color, "MO: %s%s, 0x%.8x", obj->GetMissionObject().GetObjectID().c_str(), obj->CheckAbb() ? "" : " [invalidate box]", obj); } } #endif } //Вывести ноды дерева в лог void ObjectsFindManager::Dump() { #ifndef STOP_DEBUG //Обновим дерево UpdateTree(); //Выводим в лог if(root) { root->Dump(); } #endif } //Обновить дерево void ObjectsFindManager::UpdateTree() { //Проходим по списку объектов, ожидающих обновление while(firstUpdate) { TreeObject * obj = firstUpdate; //Исключим из списка firstUpdate = obj->ExtractFirstFromUpdateList(); //Посчитаем границы объекта if(obj->CheckAbb()) { const Abb & objAbb = obj->GetAbb(); #ifndef STOP_ASSERTS objAbb.AssertInRange("ObjectsFindManager::UpdateTree"); #endif //Надо подобрать объекту нод Node * n = obj->GetNode(); if(n) { if(n->abb.IsInclude(objAbb)) { n = n->GetTreeNode(objAbb); obj->AddToNode(n); }else{ //Поднимаемся на верх n = n->parent; //Поднимаемся от нода, пока не начнём влазить while(n) { if(n->abb.IsInclude(objAbb)) { break; } n = n->parent; } if(n) { //Добавляем n = n->GetTreeNode(objAbb); obj->AddToNode(n); continue; } } } //Надо добавлять начиная от корня дерева ExtrudeTree(objAbb); Assert(root); n = root->GetTreeNode(objAbb); Assert(n); obj->AddToNode(n); }else{ //Объект имеет неправильный ящик obj->MoveToInactiveList(); } } } //Расширить дерево до размеров включающих abb void ObjectsFindManager::ExtrudeTree(const Abb & abb) { if(root) { while(!root->abb.IsInclude(abb)) { //Определяем размер стартового нода Abb newAbb(root->abb); long index = 0; if(newAbb.maxZ < abb.maxZ) { //Вперёд newAbb.maxZ += newAbb.maxZ - newAbb.minZ + 1; }else{ //Назад newAbb.minZ -= newAbb.maxZ - newAbb.minZ + 1; index |= s_maxz_mask; } if(newAbb.maxX < abb.maxX) { //Вправо newAbb.maxX += newAbb.maxX - newAbb.minX + 1; }else{ //Влево newAbb.minX -= newAbb.maxX - newAbb.minX + 1; index |= s_maxx_mask; } //Добавляем уровень иерархии Node * n = root; root = Node::Create(newAbb); root->child[index] = n; n->parent = root; //Проверить, чтобы при увеличении были правильные размеры ребёнка #ifndef STOP_DEBUG if(index & s_maxx_mask) { if(root->cx != root->child[index]->abb.minX) { abb.LogOut("ObjectsFindManager::Extrude "); root->Dump(); Assert(root->cx == root->child[index]->abb.minX); } }else{ if(root->cx != root->child[index]->abb.maxX + 1) { abb.LogOut("ObjectsFindManager::Extrude "); root->Dump(); Assert(root->cx == root->child[index]->abb.maxX + 1); } } if(index & s_maxz_mask) { if(root->cz != root->child[index]->abb.minZ) { abb.LogOut("ObjectsFindManager::Extrude "); root->Dump(); Assert(root->cz == root->child[index]->abb.minZ); } }else{ if(root->cz != root->child[index]->abb.maxZ + 1) { abb.LogOut("ObjectsFindManager::Extrude "); root->Dump(); Assert(root->cz == root->child[index]->abb.maxZ + 1); } } #endif } }else{ //Добавляем квадратный нод float centerX = (abb.minX + abb.maxX)*0.5f; float centerZ = (abb.minZ + abb.maxZ)*0.5f; long dX = abb.maxX - abb.minX; long dZ = abb.maxZ - abb.minZ; float size = (coremax(dX, dZ))*0.5f + 0.999999f; Abb quadAbb; quadAbb.minX = long(centerX - size); quadAbb.maxX = long(centerX + size); quadAbb.minZ = long(centerZ - size); quadAbb.maxZ = long(centerZ + size); root = Node::Create(quadAbb); } } //============================================================================================ //ObjectsFindManagerStorage //============================================================================================ CREATE_SERVICE(ObjectsFindManagerStorage, 100000) ObjectsFindManagerStorage * ObjectsFindManagerStorage::ptr = null; ObjectsFindManagerStorage::ObjectsFindManagerStorage() { Assert(!ptr); ptr = this; } ObjectsFindManagerStorage::~ObjectsFindManagerStorage() { Assert(ptr == this); ptr = null; nodes.Clear(); objects.Clear(); }