Выпускная квалификационная работа Процесс испускания вещества в решении задачи диффузии при симуляции растущих нейрональных структур (стр. 3 )

// inner node (105 bytes)                 

struct OctreeInnerNode                         

{                         

  OctreeInnerNode * Children[8];                         

  OctreeInnerNode * Parent;                         

  Object *  FirstObj;                         

  Vector3  Center;                         

  Vector3  HalfSize;                         

  bool  IsLeaf;                                 

};                         

// leaf node (41 bytes)

struct OctreeLeafNode

  {

  // leaf has no children

  OctreeInnerNode * Parent; // optional

  Object *  Objects;

  Vector3  Center;

  Vector3  HalfSize;

  bool  IsLeaf;

}; 

Использование данного подхода также может быть применено к следующим двум представлениям.

2.3.2.2 Блочное представление

Значительный объем памяти можно сохранить, сохраняя только один указатель на блок из восьми детей, вместо восьми указателей на восемь детей (рисунок 8). Таким образом, размер хранилища внутреннего узла может быть уменьшен с 105 байт до 49 байтов, что составляет всего 47% от исходного размера. Однако, когда листовой узел разделяется, все восемь детей должны быть выделены.

Рисунок 8. Блочное представление октодерева

Код для структуры узла

// block representation (49 bytes)

struct OctreeNode

{

  OctreeNode * Children;

  OctreeNode * Parent; // optional

  Object *  FirstObj;

  Vector3  Center;

  Vector3  HalfSize;

  bool  IsLeaf;

};

2.3.2.3 Представление типа sibling-child

Распределение по требованию может значительно уменьшить объем необходимой памяти для узлов, если мы имеем небольшое количесво задей и, следовательно, многие октанты не содержат объектов. Компромисс между стандартным представлением и представлением блока является так называемым представлением дочернего и дочернего элементов. Это представление позволяет распределять по требованию, сохраняя только два указателя узла на узел вместо восьми. Первым указателем является NextSibling, который указывает на следующий дочерний узел родительского узла. Второй указатель - FirstChild, который указывает на первый дочерний узел узла (рисунок 9).

Рисунок 9. Представление типа sibling-child

По сравнению со стандартным представлением представление sibling-child требуется только 25% памяти для указателей (два вместо восьми указателей). Пока доступ к дочерним узлам осуществляется последовательно, оба представления выполняют одинаково хорошо.

Код для структуры узла приведен ниже.

// sibling-child representation (56 bytes)

struct OctreeNode

{

  OctreeNode * NextSibling;

  OctreeNode * FirstChild;

  OctreeNode * Parent; // optional

  Object *  FirstObj;

  Vector3  Center;

  Vector3  HalfSize;

};

Выбор правильного представления на основе указателя зависит в основном от важности использования памяти и скорости перемещения. Явное хранение всех восьми дочерних указателей является потерей памяти, но делает перемещение и изменение октодерева легкореализуемым. Напротив, представление sibling-child сохраняет 50-процентную память, поскольку один узел составляет всего 48 байт вместо 92 байтов. Однако дополнительные указатели указателя могут усложнить код обхода и сделать его медленнее. Это может быть хорошим компромиссом для хранения всего одного указателя на блок из восьми подкатегорий.

2.3.3 Неявное представление узлов. Хешированные октодеревья

Хэшированные октодеревья впервые были предтавлены в 1982 году [11]. Первоначально данное решение было представлено для квадродеревьев. Данный метод сочетает в себе плюсы следующих походов:

Представление октодеревьев с указателями Представление октодеревьев с без указателей

Хешированный подход обеспечивает простой и эффективный доступ к родительским и дочерним узлам, даже несмотря на то, что никакая информация о древовидной структуре не храниться в узле.

Вместо дочерних и родительских указателей хешированный подход хранит уникальный индекс, который является локальным каждом узле. Кроме того, все узлы октордерва хранятся в хэш-карте, которая позволяет напрямую получать доступ к любому узлу на основе его локального кода. Локальный код построен таким образом, что получение локальных кодов для родительского и дочернего узлов любого узла на основе его собственного локального кода является выполнимым и быстрым. Чтобы избежать ненужных искажений хеш-карт для детей, которых не существует, структуру узла можно расширить с помощью битовой маски, указывающей, какие дети были выделены, а какие нет.

struct OctreeNode // 13 bytes

{

  Object *  Objects;

  uint32_t  LocCode; 

// or 64-bit, depends on max. required tree depth

  uint8_t  ChildExists;

// optional

};

Для создания локального кода каждый октант получает 3-битное число между 0 и 7, назначенное, в зависимости от относительного положения узла к его родительскому центру. Возможные относительные положения:

Нижний-левый-передний (000) Нижний-правый-передний (001) Нижний-левый-задний (010) Нижний-правый-задний (011) Верхний-левый-передний (100) Верхний-правый-передний (101) Верхний-левый-задний (110) верхний-правый-задний (111)

Локальный код любого дочернего узла в дереве можно вычислить рекурсивно, объединив октанные числа всех узлов от корня до рассматриваемого узла (рисунок 10).

Рисунок 10. Хешированное октодерево

Учитывая местный код, перемещение вниз или вверх по октодереву - это простая двухэтапная операция, состоящая из (1) получения локального кода следующего узла и (2) поиска узла на хэш-карте.

Для перемещения по Octree сначала необходимо определить локальный код родительского узла. Это делается путем удаления наименее значимых трех битов локального кода текущего узла. Теперь родительский узел можно получить, выполнив поиск хэш-карты с ранее вычисленным локальным кодом.

class Octree

{

public:

  OctreeNode * GetParentNode(OctreeNode *node)

  {

  const uint32_t locCodeParent = node->LocCode>>3;

  return LookupNode(locCodeParent);

  }

private:

  OctreeNode * LookupNode(uint32_t locCode)

  {

  const auto iter = Nodes. find(locCode);

  return (iter == Nodes. end() ? nullptr : &(*iter));

  }

private:

  std::unordered_map<uint32_t, OctreeNode> Nodes;

};

Для прохода вниз по октодереву сначала должен быть вычислен локальный код рассматриваемого ребенка. Это делается путем добавления числа октантов дочернего элемента к локальному коду текущего узла. После этого дочерний узел можно получить, выполнив поиск хэш-карты с ранее вычисленным локальным кодом.

void Octree::VisitAll(OctreeNode *node)

{

  for (int i=0; i<8; i++)

  {

  if (node->ChildExists&(1<<i))

  {

  const uint32_t locCodeChild

= (node->LocCode<<3)|i;

  const auto *child

= LookupNode(locCodeChild);

  VisitAll(child);

  }

  }

}

2.4 Симуляция диффузии с использованием октодерева при росте нейрональных структур

Диффузные внеклеточные сигнальные молекулы играют важную роль в развитии нейронных систем.  Они синтезируются различными источниками в нервной ткани и достигают своей цели из-за диффузионного процесса. Эти сигналы могут быть дополнительно объединены и модулированы как непосредственно на поверхности клетки, так и механизмами внутриклеточной сигнализации [12].

Моделирование распространения факторов роста в пространстве является сложной проблемой из-за сложности вычислений больших объемов данных [13]. Чтобы симуляция диффузии соответствовала реальным данными, пространство должно быть квантовано с разрешением, которое каким-то образом соответствует минимальным требованиям механизмов клеточного обнаружения. Концентрация ci = ci (rj - ri, t) фактора направленности роста в точке rj в момент t зависит от концентрации фактора направленности роста, выделяемого i-й ячейкой, расположенной в точке ri. Концентрация подчиняется стандартным уравнениям диффузии

void Diffusion::runDiffusionStep() {

  using namespace std::chrono;

  high_resolution_clock clock;

  auto begin = clock. now();

  const ConcMatrix prevConc(*conc);

  auto& cell_size = conc->cellSize();

  for (auto& p : prevConc) {

  for (auto &v : dv) {

  const auto &neighbor = prevConc. at(p. first + v * cell_size);

  auto delta = (neighbor - p. second) * params. D / 6.f;

  auto &val = conc->at(p. first);

  val += delta;

  }

  }

}

2.5 Визуализация результатов работы

       Визуализация полученных данных была произведена на языке программирования python с использованием библиотеки matplotlib. pyplot (рисунок 11).

       На изображении ниже представлен результат работы алгоритма для двух источников на поле размером 120 на 120. Для итераций 15 и 26 соответственно.