Войти
ПрограммированиеФорумГрафика

[Геометрия] Структура данных для обработки принадлежности точек секторам

Страницы: 1 2 3 Следующая »
#0
(Правка: 11:04) 10:50, 11 мая 2019

Дана некоторая функция [cht]f(x)[/cht], заданная на дискретном множестве [cht]f_i = f(x_i),\ i \in [0..M)[/cht] обычным массивом. также имется множество углов [cht]\alpha_j: \forall j \in [0..N) :\  \alpha_j < \alpha_{j+1}[/cht], [cht]\alpha_0 = -\frac{\pi}{2},\ \alpha_{N-1}=\frac{\pi}{2}[/cht]. Требуется для каждой точки [cht](x_i, f_i)[/cht] определить, какие интервалы точек попадают в каждый из секторов, образованных парой последовательных углов, исходящих из этой точки. Объяснение может быть немного кривое, вот картинка алгоритма, который ищет искомые данные:
Изображение
Точки ищутся справа налево, при этом каждому цвету соответствует один сектор. На каждом шаге алгоритм переходит на одну точку влево и обновляет список точек, лежащих выше каждого из углов. Алгоритм работает за сложность O(N*M), что удовлетворительно(едва ли можно быстрее), но проблема в том, что в простейшей реализации он использует O(N*M) памяти, так как в ней я для каждой точки храню массив следующей точки по линии каждого из углов. Но из чисто геометрических соображений видно, что на самом деле достаточно для каждой точки хранить только одну величину — следующую точку в секторе, которому она сама принадлежит. Однако, реализовать это не так просто, как кажется.

Принципиально важные ограничния — сложность не более чем O(N*M) и память не более чем O(N+M). Возможно, у кого-то получится построить алгоритм, удовлетворяющий поставленным требованиям из того пути, по которому я начал идти или, возможно, будут альтернативные предложения. В любом случае, правильное решение (референсный алгоритм) для этой задачи известно, требуется только прийти к нему, уложившись в установленные рамки.

#1
(Правка: 19:01) 18:58, 11 мая 2019

Suslik
> Возможно, у кого-то получится построить алгоритм, удовлетворяющий поставленным
> требованиям
А через растеризацию в 1D текстуру + depth peeling не подойдет? Или важно каждую точку сохранить?
Еще глядя на картинку очевидным решением напрашивается взять обрабатывать только те точки(обрабатывать - это брать углы от этой точки, и смотреть на другие точки, которые попадают в эти углы), где первая и вторая производная от твоей функции меньше нуля.

#2
(Правка: 19:12) 19:11, 11 мая 2019

MrShoor
> А через растеризацию в 1D текстуру + depth peeling не подойдет? Или важно
> каждую точку сохранить?
вопрос не в том, на чём выполнять алгоритм(gpu или cpu), а что это должен быть за алгоритм.

MrShoor
> Еще глядя на картинку очевидным решением напрашивается взять обрабатывать
> только те точки(обрабатывать - это брать углы от этой точки, и смотреть на
> другие точки, которые попадают в эти углы), где первая и вторая производная от
> твоей функции меньше нуля.
производные надо не с нулём сравнивать, а с тангенсом соответствующего сектору угла. только это на асимптотическую сложность никак не влияет.

#3
(Правка: 19:18) 19:12, 11 мая 2019

Оптимизация с первой и второй отрицательной производной уменьшит количество обрабатываемых точек в 4 раза.
Вторая мысль: можно находить диапазоны [Xj0, Xj1], [Xj2, Xj3] и т.д. на которых первая и вторая производная отрицательная. Судя по картинке таких диапазонов будет очень немного. Далее для точки Xj0, Xj2 нужно покрасить все точки, которые справо от неё (так как это максимум), а для точек (Xj0, Xj1] покрасить только одного соседа справа.
Тут было неправильно.

А оптимизация через производную с нулем работает, потому что только красные точки смогут кого-то осветить:
red | [Геометрия] Структура данных для обработки принадлежности точек секторам
Остальные точки будут гарантированно освещены этими красными.

#4
19:23, 11 мая 2019

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

#5
(Правка: 19:35) 19:35, 11 мая 2019

MrShoor
> А оптимизация через производную с нулем работает, потому что только красные
> точки смогут кого-то осветить:
неверно, функция может быть такой:
Изображение
здесь видно, что и на участке с положительной производной лучи, у которых угол выше производной, вполне могут до куда-то дойти.

да и производных у функции вообще может не быть, так как она представлена просто массивом точек и выглядеть может, например, так:
Изображение

#6
19:38, 11 мая 2019

Я не понял, тебе только финальная окраска нужна?

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

#7
19:50, 11 мая 2019

Suslik
> достаточно для каждой точки хранить только одну величину —
> следующую точку в секторе, которому она сама принадлежит
Но ведь секторы зависят от того, которую точку берешь за центр

#8
(Правка: 19:55) 19:53, 11 мая 2019

}:+()___ [Smile]
> Я не понял, тебе только финальная окраска нужна?
неа, нужна окраска именно для каждой точки. их можно в явном виде не хранить, но в каком-то виде по ним итерироваться.

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

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

#9
(Правка: 20:15) 20:11, 11 мая 2019

Вот как-то так набросал:

RWTexture1D<float>  ptCol; //цвет всех точек
Texture1D<float2> ptCrd;   //координаты всех точек

globallycoherent RWTexture1D<uint> Depth; //буфер глубины, размер равен количеству цветов

uint viewPt; //точка, из которой растеризуем

struct VS_In {
  float4 pos: SV_Position;
  uint ptIdx: ptIdx; //индекс растеризируемой точки, должен быть гарантированно больше viewPt
};

uint MapDepth(float fDepth) { //маппим глубину на целое
  return ...;
}

void pixel_shader(VS_In Input) {
  uint newDepth = MapDepth( normalize(ptCrd[Input.ptIdx] - ptCrd[viewPt]).y ); //глубина - максимум по Y
  uint oldDepth;
  InterlockedMax(Depth[uint(In.pos.x)], newDepth, oldDepth);
  if (oldDepth < newDepth) { //прошли тест глубины, можем попытаться покрасить пиксель
    float ptColor = ptCol[Input.ptIdx];
    if (ptColor < 0) { //красим только не окрашенные точки
      ptCol[Input.ptIdx] = In.pos.x;
    }
  }
}
Потребление памяти O(N+M), сложность O(N*M).
Нужно растеризовать N раз (из каждой точки) в 1д текстуру размером M (в качестве этой 1д текстуры выступает буфер кастомный глубины globallycoherent Texture1D<uint> Depth;)
Точки растеризуем только слева-направо. Таким образом однажды покрашенную точку перекрашивать больше не нужно.
При растеризации из точки X на растеризацию отправляем только точки [X+1, N]

#10
(Правка: 20:18) 20:13, 11 мая 2019

ещё обращу внимание, что если функция меняется незначительно (например, функция 0.1 * sin(x)), то большинство секторов вообще не будут задействованы и по идее это как-то должно помочь существенно ускорить алгоритм от O(N*M) до чего-то вроде O(M) в таком случае, но я не знаю, как это оценить более точно:
Изображение

MrShoor
> При растеризации из точки X на растеризацию отправляем только точки [X+1, N]
это уже квадратичная сложность, потому что ты для каждой точки обрабатываешь все оставшиеся точки

#11
20:16, 11 мая 2019

Suslik
> неа, нужна окраска именно для каждой точки.
Тогда мне непонятна твоя идея, что можно хранить меньше O(M*N).
Для каждого положения стартовой точки есть N уникальных положений границ интервалов.
Т. е. ты либо все это хранишь, либо часть алгоритма гоняешь при каждом использовании.

#12
(Правка: 20:23) 20:22, 11 мая 2019

}:+()___ [Smile]
> Тогда мне непонятна твоя идея, что можно хранить меньше O(M*N)
на каждой стадии алгоритма каждая точка принадлежит только одному сектору. поэтому можно, например, для каждой точки хранить две ссылки: на следующую точку в её секторе и на первую точку в следующем секторе. тогда на каждой итерации алгоритма точки переходят из более высокого сектора в более низкий, обновляя их ссылки друг на друга. проще всего реализовать рекурсией. к сожалению, у такого представления есть проблемы реализации для случая, если какие-то сектора получаются вырожденные(например, в сектор ни одна точка не попала), потому что тогда вместо ссылки на первую точку следующего сектора, она будет ссылаться сама на себя и ничего хорошего из этого не выйдет.

#13
21:33, 11 мая 2019

Suslik
> тогда на каждой итерации алгоритма точки переходят из более высокого сектора в более низкий, обновляя их ссылки друг на друга.
Но в этом случае ты затираешь данные с прошлой итерации, т. е. все данные тебе одновременно не нужны.
В общем, стоило бы четко описать, какие данные и в каком порядке тебе нужны.

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

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

#14
13:14, 12 мая 2019

Suslik
Распределение по секторам для разных центр точек вообще независимо, считай для каждой центр точки отдельно - вот тебе и MN время и N память

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумГрафика