===Week 7 report===<br><br>==This week==<br>This week i mainly worked on data structures, read papers and explored some experimental stuff.<br><br> *added submodule bf_render_raytrace (C++), to be able to code C++ for the raytracer. The code although C++ is very C style (C++ is mainly used for templates and std algorithms).<br>
*coded a variable way bvh (which i called vbvh) (that means each node can have a any/variable number of childs)<br> *coded LCTS (longest commum transversal sequence) hint ability in the vbvh... for now only BB hints were codded and they proved not to be very usefull (read as: there's no clear speedup, nor clear slowdown). Later this can be expanded on a cone hint, allowing to speedup mainly localized and spot lamps. (this type of stuff is usually used on primary rays but blender uses Zbuffer fot that)<br>
<br> *coded an experimental stuff (read as: never saw that on any paper) to reduced expected number of BB tests:<br><br> 1) Specially on binary trees it happens that a node is actually "useless", and so it can be removed from the tree, a node is considered useless when it probabilisticaly increases the expected number of BB tests. Any node with N childs should have an hit probability inferior to (N-1)/N otherwise its better to discard that node and "pushup" the childs of that node.<br>
This pass is O(N) and should always reduce the number of BB tests per ray (if they are coherent with the hit probability model).<br>Eg.: Lone ballon went from 76BB tests/45BB hits to 67BB tests / 27BB hits.<br><br> 2) If you are not allowed to remove any nodes from a BVH tree and/or change their BB but you are allowed to move childs arround, whats the best BVH tree you can do?<br>
Given a possible set of parents for a node, and using the surface area model, a node should be the child of the parent with the smallest hit probability and that is the one with the smallest area. (the number of parents until root is useless).<br>
I guess this might be doable in some linear time, i believe current code does a O(NlogN) (worst case N^2)<br> this also reduces the expected number of BB tests, but it doenst seems to be as much as "pushups"<br>
<br>^^ "best tree" refers to a tree where casting a full-space-search rays would yeild a equal or smaller number of BB tests.<br><br>*tested diferents raycast stack size (didnt seem to have any influence on speed :S)<br>
<br>*played with single tree (vs hierarquich trees), single trees are as expected faster (atm they render "ballon scene" 20times faster, showing that the BVH after the build optimizations can deal well with diferent mixed types off geometry), build time is still N log^2 N, and thats the main reason for not rendering faster on all cases)<br>
<br>*did some local experiences with sse, but I did not have time to start implementing it.<br><br>==Next week==<br>As said before, I will be camping until 31july.<br>When I get back I plan to start looking on things like: sse, memory organization.<br>
<br>==Questions==<br>I hope people don't mind big reports.<br>
None.<br><br>==Schedule==<br>The idea was to start appling SSE this week, but I was quite busy thinking and reading and drawing (algorithms, papers and graphs).<br><br>I will be camping until 31july (on iceland).<br><br>
--<br>André<br>