Домашни работи - лекция 5/hard (6т)
- Forums:
Считаме, че тази задача е трудна - try it on your own risk! Не поемаме отговорност в случай на изгубени много часове в коденето й :)
Задачата е за всички студенти.
Целта на задачата е да се оптимизира алгоритъма за пресичане с булеви обекти, като се направи малко по-умно. В момента се търсят всички пресечни точки на лъча с геометриите, а това може да е излишно в много от случаите. Булевата функция може да се окаже удовлетворена още на първата или втората пресечна точка: например, ако имаме CsgDiff обект, при който лявата геометрия е доста по-голяма от дясната (да речем, един голям куб, на който едното ъгълче е леко изрязано от сфера: в болшинството случаи е достатъчно да проверим къде е първата пресечна точка с куба, и да видим, че лъча не пресича сферата въобще). По-точно, искаме да реализираме следния алгоритъм:
1. Намираме дали сме вътре в геометриите - но ще ползваме друг метод, който не е базиран на пресичания.
2. Намираме най-близките пресечни точки с всяка от двете геометрии.
3. Взимаме по-близката от двете пресечни точки и проверяваме дали булевото условие е изпълнено при нея (като, подобно на стария алгоритъм, трябва да обърнем isInside флага за съответната геометрия преди да направим проверката). Ако функцията връща истина - край, намерили сме пресечна точка -> изход.
4. В противен случай, изхвърляме по-близката от двете пресечни точки, и, за нейната геометрия, намираме следващата пресечна точка чрез Geometry::intersect(), и отиваме на стъпка 3.
5. Ако в даден момент се окаже, че и двете пресечни точки са +INF, значи лъчът въобще не пресича булевия обект - CsgOp::intersect() трябва да върне също +INF.
Архитектурно, трябва да се направят следните промени:
1. Да се добави абстрактен метод isInside() на класа Geometry, и да се имлементира за Cube и Sphere (за Plane можете да сложите просто едно return false; тъй като не го ползваме).
2. Да се слеят функциите на CsgOp::getAllIntersections и CsgOp::intersect; т.е. getAllIntersections не трябва да се вика въобще.
Докато пишете вашата реализация, водете се от RenderTime-a, който програмата ще ви изписва - то е ориентир как сте се справили с оптимизацията. При добро решение, би трябвало да можете да смъкнете времето поне с 30-40%.
Можете да аранжирате и гореспоменатия пример с CsgDiff на голям куб и малка сфера, там ползата от оптимизацията трябва да е дори по-голяма.
Comments
въпроси
Имам два въпроса (единия по задачата, другия не съвсем) .. първо, очаква ли се решението да постига за примерната сцена 30-40% ? Аз го докарах около 20% под vs2008 (като build-вам в release) и си мисля че освен ако нещо не променя самия алгоритъм дето е описан, по-бързо няма да стане ..
Второ, Sphere::intersect и Cube::intersect (но не и CsgOp::intersect) не променят параметъра info когато връщат +INF (няма пресичане), т.е. ако направя dist = geometry.intersect (ray, &info), може да се окаже че dist != info.dist, и например изрази от типа geom.intersect (ray, &oldinfo) просто ще оставят в oldinfo старата пресечна точка (което и беше мойта грешка която търсих около един час :P ). Та въпроса ми е .. така ли се очаква да бъде или не ?
Здравей, по първия въпрос:
Здравей,
по първия въпрос: ускорението зависи от машината, на която го тестваш, но би трябвало да е там някъде (към 35% беше на моята машина, затова съм писал такива граници). Ако си сигурен, че няма накъде повече да се оптимизира без фундаментални размествания, прати го така, пък ще го погледнем, ако си изпуснал нещо, ще ти пишем да си го оправиш.
По втория: да, така трябва да бъде. Info структурата е предназначена изцяло за шейдърите... рейтрейсинг алгоритъма не се интересува от нея, а само от разстоянието, и ако искахме да правим чист рейтрейсинг (само пресичане), можеше въобще да нямаме структура info. В случая, в който intersect() на някоя геометрия върне безкрайност, то пресечна точка няма, и няма защо да се променя info структурата.
Цифрите 30-40% са малко
Цифрите 30-40% са малко подвеждащи. Не ги взимай чак толкова сериозно.
Ако в сцената въобще нямаш булев примитив, едва ли ще постигнеш повече от 0% бързодействие.
Ако пък имаш, зависи от това колко пиксела той покрива, колко е нагънат (т.е. колко точно трасирания прави getAllIntersections; за 100-глава ламя прави макс 200, а за сфера макс 2) и т.н.
В домашното е описано каква горе долу трябва да е сцената, върху която да тестваш.
Да не говорим, че за 1 кадър,
Да не говорим, че за 1 кадър, при това немного тежък, е трудно да се усети този процент, защото има много фактори. Хардуер софтуер, настройки и т.н. За да се направи качествен анализ на производителността ни трябват поне 100 кадъра с различни сцени и осредняване на резултатите.
Sors salutis et virtutis michi nunc contraria, est affectus et defectus semper in angaria.
There Is No Gene For The Human Spirit.
The Bird is the word...
Е то си е казано върху коя
Е то си е казано върху коя сцена се постигат въпросните проценти - върху тестовата, която е в SVN (rev 182). Иначе, доколкото разбирам от досега предадените домашни, на моята машина (AMD Opteron) разликата е доста по-голяма отколкото при останалите, така че точните цифри са наистина подвеждащи. Накратко: ако решението ви постига поне 20% и считате, че няма какво повече да се ускори, пращайте смело.
А и още нещо: ако имате някакви power management услуги, които да намалят процесорната честота в idle - изключвайте ги преди да правите каквито и да е тестове - иначе резултатите не са акуратни.