Войти
ФлеймФорумПрограммирование

Не смог решить тестовое задание (3 стр)

Страницы: 1 2 3 4 542 Следующая »
#30
(Правка: 6:07) 6:05, 4 янв. 2020

именно на такой подзадаче основан мой рендер здесь: https://www.youtube.com/watch?v=e8Jsq1K-nPk

в простейшем случае идея в том, чтобы разбросать частицы по ячейкам вроде shadow map'ы, где размер ячейки примерно равен растеризованному размеру частицы, а частицы хранятся в связанном списке. далее каждая ячейка сортируется и считается перекрывание частиц front-to-back в компьют шейдере по одному треду на ячейку.

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

ещё один способ (более простой, приближённый) заключается в том, чтобы растеризовать по одному пикселу на частицу в фреймбуффер в первом проходе, а потом в image space циклом по соседям или jump fill'ом расширить каждую частицу до её растеризованного радиуса, пробегаясь по всем соседям.

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


#31
6:48, 4 янв. 2020

Suslik
> но все методы кроме последнего здесь — явный оверкилл для тестового задания
Там максимум 1024 частицы. Впринципе разбрасывание по ячейкам уже оверкилл имхо.

#32
6:53, 4 янв. 2020

MrShoor
1024 частицы можно хоть за квадратичную сложность в 1 треде на gpu посчитать. вопрос в том, как это решение скейлится. моё решение работает для миллионов частиц.

#33
6:58, 4 янв. 2020

Suslik
> вопрос в том, как это решение скейлится. моё решение работает для миллионов
> частиц.
Само собой твое решение скейлится, вот только в задании по всей видимости нужно не такое решение :)

#34
(Правка: 7:05) 7:05, 4 янв. 2020

возможно, если им надо просто "меньше, чем за O(n^2)", то можно решить за O(n*(sqrt(n) + log(n)), если отсортировать все частицы по оси, перпендикулярной sunDir (n log(n))  и далее просто найти бинарным поиском (log(n)) диапазон частиц, с которыми она пересекается по этой оси, таких частиц будет в среднем sqrt(n). это решение плохо скейлится, но оно удовлетворяет условию "быстрее чем O(n^2)" и пишется за время тестового задания.

#35
7:12, 4 янв. 2020

Suslik
> то можно решить за O(n*(sqrt(n) + log(n)), если отсортировать все частицы по
> оси
Как сортировать будешь в одном диспатче? Куда будешь складывать промежуточный результат? И уверен ли ты, что константа будет достаточно дешевой, чтобы в абсолютном времени оно обогнало n^2? :)
И насколько я понял ТС - условия сделать меньше чем за n^2 не было. Это он сам себе его придумал.

#36
(Правка: 7:26) 7:21, 4 янв. 2020

MrShoor
> Как сортировать будешь в одном диспатче? Куда будешь складывать промежуточный результат?
да никак, реализовать нормальный merge sort на GPU — это уже отдельное тестовое задание. сказать, что оно реализовано во внешнем коде, либо отсортировать на CPU.

> И уверен ли ты, что константа будет достаточно дешевой, чтобы в абсолютном времени оно обогнало n^2? :)
оно может хоть миллион лет выполняться для 1024 частиц, но если асимптотическая скорость выше, то всегда найдётся достаточно больше количество частиц, для которого оно окажется быстрее.

> И насколько я понял ТС - условия сделать меньше чем за n^2 не было. Это он сам себе его придумал.
если такого условия действительно нет, то это ж тогда вообще тупо, потому что можно решить за n^2, но это решение будет напрочь бесполезным в результате. вообще в задании написано:
> Напишите на hlsl оптимальный по быстродействию compute шейдер (Shading Model 5)
я, если честно, не знаю, что вообще понимается под "оптимальный по быстродействию". чтобы нормально определить, что является оптимальным, надо гораздо более подробно описать условия.

#37
7:24, 4 янв. 2020

Suslik
> но это решение будет напрочь бесполезным в результате
Почему? Задача же - проверить кандидата. Со своей задачей спавляется? Значит не бесполезное.

#38
7:49, 4 янв. 2020

Учитывая, что эта компания может отправить покупать тебя чертежи истребителей, а потом когда тебе будет грозить 10 лет тюрьмы в США, отказаться от какой-либо связи с тобой, то работать в ней за 200к+ точно не стоит. https://app2top.ru/industry/eagle-dynamics-podtverdila-chto-ee-so… a-140915.html

#39
11:05, 4 янв. 2020

foxes, все таки подумав, решение даже за n ^ 2 невозможно без дополнительных структур.

#40
(Правка: 14:57) 11:08, 4 янв. 2020

lookid
> Обычно графических программистов 1% от команды. Работал на проекте, где было
> всего 2 программиста графики

это шо за проекты такие ? 15% в среднем

#41
11:14, 4 янв. 2020

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

ты много был на собеседованиях ? за 5 минут отсекаются

#42
(Правка: 12:13) 12:08, 4 янв. 2020

foxes

+ Показать
#43
12:22, 4 янв. 2020

innuendo
Насколько я помню, ты интересовался этой вакансией. Что в итоге, если не секрет?

#44
12:23, 4 янв. 2020

Алмаз
этой точно нет - может про алигн или адалиск

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