Делал такое для ломаных линий. Там нельзя посчитать нормаль по понятным причинам, поэтому просто в первой точке выбирал произвольное направление нормали, перпендикулярное направлению. А потом просто в каждой новой точке поворачивал координатную систему на угол поворота вектора направления (т.е. осью вращения было векторное произведение векторов предыдущего направления и нового).
Странно, кстати, что в статье нет упоминания про проблему пересечения сечений. Для заданных значения кривизны кривой и радиуса сечения всегда существует минимальный шаг между сечениями при котором сечения начнут пересекаться, в результате чего модель получается некорректной.
100 метровые файлы у него бинарные. А ASCII файл, про который речь в статье, судя по тому, что в нем 7982 треугольников, занимает всего несколько десятков килобайт.
По моему автор этого комментария просто не понял смысл правок. В том месте (parse_args.c ), которое, как я понял, он назвал «оптимизацией», на мой взгляд цель в другом — сделать так, чтобы аргументы остались лежать в памяти подряд, как они и лежали до этого.
Но баг то как раз не в этом месте, а в правке в первом файле (sudoers.c).
Речь не про конкретный формат, а про потерю точности. В DICOM обычно минимум 12 бит на пиксель, а бывает и больше. При конвертации в картинку обычно все обрезается до 8 бит, соответственно точность теряется.
Можно ведь и в 16-битный grayscale конвертировать. Не знаю точно, поддерживает ли PNG 16-битный цвет, но думаю да. Для КТ вообще проблем не должно быть, т.к. там единая шкала Хаунсфилда, просто нужно все аккуратно сконвертить. Для МРТ придется как то нормализовывать конечно, т.к. там нет единой шкалы.
Здесь, как я понял, они даже со шкалой Хаунсфилда не разобрались и из-за этого у них какие то проблемы были.
Томографы пишут файлы в стандарте DICOM, но интерпретация стандарта и форматы записи могут сильно отличаться, поэтому много времени и нервов ушло на поддержку файлов, которые пишут все КТ аппараты.
Похоже вы просто не разобрались, как хранятся изображения в формате DICOM. И скорее всего в итоге работали с RGB картинками, а не с исходными DICOM изображениями. Хотя не могу сказать, влияет ли это на результат.
Судя по коду (оригинальному и исправленному) нового героя можно купить только через 7 дней после покупки предыдущего. Флаг здесь означает — прошло или нет 7 дней с покупки предыдущего героя, при этом параллельно ведется количество прошедших дней. От номера недели, на которой был куплен герой, ничего не зависит и в коде номер недели никак не фигурирует.
Если так, тогда не факт, что и ваш патч правильный, т.к. он вполне может изменить задуманную логику совместной работы этого флага, выставленного другими способами, и сброса через количество дней.
Приведенный код — хороший пример того, как не надо писать. Зачем заводить две сущности — флаг доступности таверны и число дней с момента покупки героя, когда достаточно одной — числа дней? Из-за этого код и получается запутанным и в нем легко ошибиться. С одной сущностью (числом дней) логика была бы гораздо проще и ошибиться в ней было бы гораздо сложнее.
Но к самому патчу это, конечно, не имеет отношения. Понятное дело, что приходится работать с тем, что есть :)
По-моему с прямоугольниками очень даже понятно. Хотя возможно это индивидуально. Но конечно нужно уже иметь какое то представление, что такое floating point.
Имелось ввиду, что алгоритм можно переписать так, чтобы не считать длину дуги от начальной точки на каждой итерации, а использовать значение длины, вычисленное на предыдущей итерации, и считать длину участка дуги между предыдущей точкой и текущей.
Алгоритм выглядит весьма неоптимальным — много раз (столько, сколько итераций в методе Ньютона) считается длина дуги от начальной точки, вместо того, чтобы считать длину дуги на интервале. И похоже это число итераций метода Ньютона весьма велико — возможно всегда равно 100 и условие
if (Mathf.Abs(f) < 0.01f)
break;
никогда (или очень редко срабатывает). Иначе не знаю как объяснить такую медленную скорость работы — почти 1 секунда для 100000 точек.
Ну там есть вроде какая то реализация Radix, не знаю в библиотеках она типа npp или просто в примерах, никогда ее не использовал. Да и здесь она будет не очень эффективна. Проще реализовать свою. Тут все достаточно просто.
Как я понимаю информация о частицах в каждой ячейке уже есть в каком то виде. Из нее эта сортировка получается достаточно просто: для начала нужно знать количество частиц в каждой ячейке. Алгоритм такой:
1. Выделяется массив целых чисел размером равным общему количеству частиц. Значение каждого элемента этого массива будет номером частицы.
2. Выделяется массив смещений, являющийся массивом целых чисел размером равным общему количеству ячеек.
3. Массив (2) заполняется следующим образом: нулевой элемент содержит 0, каждый следующий i-й элемент равен сумме i-1'го элемента и количества частиц в i-1'й ячейке. Заполнять проще на обычном cpu, т.к. заполнение должно происходить последовательно, если будет являться узким местом, можно написать специальную редукцию на gpu.
4. Для каждой ячейки записываются в массив (1) последовательно номера принадлежащих ей частиц, начиная со смещения из массива (2) для этой ячейки.
На этом сортировка закончена. После этого при вычислении каждый поток просто должен обрабатывать частицу, номер которой хранится в массиве (1) по индексу, равному глобальному индексу потока.
поправил, в temp_scale убрал только в начале, в конце — неважно, какой из блоков это сделает.
Я бы все таки перенес это присваивание в другое место, например туда, где вычисляется и присваивается md->k. Просто чтобы код был понятнее, но это уже, понятное дело, относится к стилю, а не к корректности кода.
думаете, что два раза считать корни, экспоненты и т.д. быстрее, чем один раз, но с атомик?
По моему опыту — да, гораздо быстрее. Как я уже писал, чистые вычисления на gpu в большинстве случаев не являются узким местом. В большинстве случаев все упирается в доступ к глобальной памяти, ну а глобальные атомики — это еще медленнее.
Как следующий этап оптимизации я хотел предложить не просто обработку каждой частицы в отдельном потоке, но обработку их в порядке их расположения в ячейках. Т.е. частицы, расположенные в одной ячейке должны обрабатываться подряд — в идеале потоки каждого warp'а или даже блока обрабатывают частицы из одной ячейки. Тогда потоки каждого warp'а будут синхронно обращаться к одним и тем же соседям, а не разным и случайным, что должно давать очень существенное ускорение. Именно про это и написано в презентации, ссылку на которую дал pavel_kudinov. И там уже рассматривается как раз способы сортировки частиц, чтобы они шли в порядке принадлежности к ячейкам. И как раз уже время выполнения этой задачи становится основной проблемой.
Странно, кстати, что в статье нет упоминания про проблему пересечения сечений. Для заданных значения кривизны кривой и радиуса сечения всегда существует минимальный шаг между сечениями при котором сечения начнут пересекаться, в результате чего модель получается некорректной.
А на примеры данных где то посмотреть можно? Хотелось попробовать как будет выглядеть в нашем софте.
Но баг то как раз не в этом месте, а в правке в первом файле (sudoers.c).
А U/N может быть гораздо больше чем N, как в вашем же примере из этого комментария.
Можно ведь и в 16-битный grayscale конвертировать. Не знаю точно, поддерживает ли PNG 16-битный цвет, но думаю да. Для КТ вообще проблем не должно быть, т.к. там единая шкала Хаунсфилда, просто нужно все аккуратно сконвертить. Для МРТ придется как то нормализовывать конечно, т.к. там нет единой шкалы.
Здесь, как я понял, они даже со шкалой Хаунсфилда не разобрались и из-за этого у них какие то проблемы были.
Похоже вы просто не разобрались, как хранятся изображения в формате DICOM. И скорее всего в итоге работали с RGB картинками, а не с исходными DICOM изображениями. Хотя не могу сказать, влияет ли это на результат.
Но к самому патчу это, конечно, не имеет отношения. Понятное дело, что приходится работать с тем, что есть :)
никогда (или очень редко срабатывает). Иначе не знаю как объяснить такую медленную скорость работы — почти 1 секунда для 100000 точек.
Как я понимаю информация о частицах в каждой ячейке уже есть в каком то виде. Из нее эта сортировка получается достаточно просто: для начала нужно знать количество частиц в каждой ячейке. Алгоритм такой:
1. Выделяется массив целых чисел размером равным общему количеству частиц. Значение каждого элемента этого массива будет номером частицы.
2. Выделяется массив смещений, являющийся массивом целых чисел размером равным общему количеству ячеек.
3. Массив (2) заполняется следующим образом: нулевой элемент содержит 0, каждый следующий i-й элемент равен сумме i-1'го элемента и количества частиц в i-1'й ячейке. Заполнять проще на обычном cpu, т.к. заполнение должно происходить последовательно, если будет являться узким местом, можно написать специальную редукцию на gpu.
4. Для каждой ячейки записываются в массив (1) последовательно номера принадлежащих ей частиц, начиная со смещения из массива (2) для этой ячейки.
На этом сортировка закончена. После этого при вычислении каждый поток просто должен обрабатывать частицу, номер которой хранится в массиве (1) по индексу, равному глобальному индексу потока.
Я бы все таки перенес это присваивание в другое место, например туда, где вычисляется и присваивается md->k. Просто чтобы код был понятнее, но это уже, понятное дело, относится к стилю, а не к корректности кода.
По моему опыту — да, гораздо быстрее. Как я уже писал, чистые вычисления на gpu в большинстве случаев не являются узким местом. В большинстве случаев все упирается в доступ к глобальной памяти, ну а глобальные атомики — это еще медленнее.
Как следующий этап оптимизации я хотел предложить не просто обработку каждой частицы в отдельном потоке, но обработку их в порядке их расположения в ячейках. Т.е. частицы, расположенные в одной ячейке должны обрабатываться подряд — в идеале потоки каждого warp'а или даже блока обрабатывают частицы из одной ячейки. Тогда потоки каждого warp'а будут синхронно обращаться к одним и тем же соседям, а не разным и случайным, что должно давать очень существенное ускорение. Именно про это и написано в презентации, ссылку на которую дал pavel_kudinov. И там уже рассматривается как раз способы сортировки частиц, чтобы они шли в порядке принадлежности к ячейкам. И как раз уже время выполнения этой задачи становится основной проблемой.