Я работаю над созданием слайсера me sh для игры, над которой я работаю. Все работает нормально, но я бы хотел сделать его более эффективным. Одна очень очевидная неэффективность, о которой я не упоминал ни в одном из найденных мной текстов, заключается в том, что я проверяю расстояние всех вершин от плоскости.
Это кажется ненужным - если вместо этого я сначала нахожу «l oop» (под l oop я имею в виду кривую, которая действительно является пересечением me sh и плоскости / среза), которую срез делает на me sh (при условии, что он существует, и для простоты давайте предположим, что срез может сделать только такой l oop на me sh), затем все остальные треугольники и их вершины l ie строго выше или строго ниже плоскости - так что я мог бы просто использовать поиск графа алгоритм, который рекурсивно проходит через треугольник и его соседние соседи (но никогда не проходит через l oop), и просто присваивает одно и то же значение для всех этих соседних соседей.
//
Проблема заключается в - как мне сначала найти l oop? Вот мои предложенные решения, по которым я был бы признателен за любые отзывы.
1, Выясните, есть ли у единицы какой-то интеллектуальный метод / функция, которая пересекает плоскость с me sh и возвращает индексы треугольники. Я не смог найти такой метод. Честно говоря, в конечном итоге может оказаться более эффективным сделать несколько радиопередач «внутри» плоскости среза или что-то в этом роде, поскольку они возвращают индекс треугольника, и, вероятно, они сделаны очень эффективно. Тем не менее, я мог бы в конечном итоге сделать несколько процедурных срезов после первого начального среза, возможно, сделать какую-то реализацию слияния BSP, и поэтому я бы предпочел, по крайней мере, понять, что происходит и как я мог бы сделать это сам.
2, Для выпуклого меня sh я мог бы просто начать с произвольной вершины и найти расстояние от плоскости. Например, если расстояние этой начальной вершины от плоскости равно -10, я продолжаю проходить через соседние вершины, проверяя их расстояние от плана, и я выбираю go до соседней вершины, которая повышает значение больше всего. Если я доберусь до вершины со значением $> 0 $ ($ = 0 $ соответствует плоскости), я найду al oop и остановлюсь. Для невыпуклого меня sh это не обязательно будет работать очень эффективно, потому что я могу достичь глобального максимума. Для меня sh, который не пересекается с самолетом, я пройду go через все точки, что снова проблематично c. Я также мог бы добавить немного случайности + некоторую начальную точку heuristi c, чтобы сделать его более эффективным. Другая вещь, которая может сделать вещи более эффективными, - это просто начать сначала в какой-то другой точке / go несколько шагов назад, если я найду локальный максимум, который все еще находится ниже плоскости.
3, я мог бы использовать некоторые своего рода общая реализация радиовещания. Я не знаю, как это делается профессионалами, но я полагаю, что кое-что может сработать и сделать вещи более эффективными. Во-первых, в предварительной обработке (так что это не должно быть эффективным), я делаю ограничивающий прямоугольник из me sh и разделяю его несколько раз на маленькие блоки (например, разлагаю блок 1 на скажем 2 ^ 3 или более блоков ). Я go через все треугольники, и если он пересекает один из ящиков, я назначаю этот треугольник ящику.
Затем, когда дело доходит до пересечения плоскости, я нахожу все ящики, которые пересекает плоскость. Это должно быть возможно несколько быстрее. В 2D вы можете просто найти самые внешние стороны "большого" начального блока, который был разложен, и найти части, которые пересекают плоскость / линия. Затем я просто продолжаю идти в сторону, как в алгоритме рисования линий.
Как только все это будет сделано, я просто проверяю треугольники, связанные с прямоугольниками, которые были пересечены плоскостью, и нахожу те треугольники, которые также пересекаются плоскостью.
Одна из проблем заключается в том, что если я захочу впоследствии сделать другие срезы, мне придется сохранить эту «ограничивающую» рамочную структуру и т. д. c. Во-первых, сначала я sh, это не проблема, так как это не нужно делать во время выполнения. Но для следующих я не могу создать совершенно новую коробку и назначить треугольники новой ячейки me sh соответствующим коробкам. Однако, если, например, я должен был выполнить слияние в стиле BSP, я мог бы просто использовать ту же структуру данных ограничивающего прямоугольника на новом me sh - при условии, что я отслеживаю треугольники, которых нет во вновь созданном Я sh, как только я нарезал новое Я sh на новой плоскости, я снова нахожу в штучной упаковке, но когда дело доходит до нахождения треугольников этого нового Я sh, которые пересекаются, я проверяю, был ли этот треугольник не удалено в предыдущем фрагменте me sh. Если бы я делал эти срезы рекурсивно, как при слиянии BSP, я бы просто добавил треугольники обратно в виде I go обратно в рекурсию.
Это может быть самый эффективный и потенциально надежный способ, но это тонна работы, и я не уверен, что хочу это сделать.
//
4, наконец, я хочу спросить, не слишком ли я оптимизирую не то, что здесь - что На каких еще вещах я должен сосредоточиться, если я пытаюсь сделать мой слайсер me sh эффективным? Я имею в виду, что разница здесь может быть довольно небольшой - все, что делает «сначала найти l oop», состоит в том, что вместо того, чтобы вычислять все расстояния от плоскости для всех вершин (скалярное произведение и одна операция вычитания для каждого вершина), мне все равно придется go пройти через все вершины, но вместо этого я просто проверю, каковы его соседи. Это не может быть огромной разницей? Учитывая все остальные вещи, которые еще предстоит сделать для всех вершин в обоих случаях, например, отсортировать их в соответствующие списки вершин (одинаковые для всех треугольников), скопировать нормаль / UV в списки векторов, и т. Д. c ... может быть, это не то, на чем нужно фокусироваться. (В любом случае, какой самый эффективный способ сделать эту сортировку вершин?)
Буду признателен за любой вклад в эту топи c.