[Soc-2009-dev] Raytrace api

[André Pinto]

===Week 7 report===

==This week==
This week i mainly worked on data structures, read papers and explored some
experimental stuff.

  *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).
  *coded a variable way bvh (which i called vbvh) (that means each node can
have a any/variable number of childs)
  *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)

  *coded an experimental stuff (read as: never saw that on any paper) to
reduced expected number of BB tests:

    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.
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).
Eg.: Lone ballon went from  76BB tests/45BB hits to 67BB tests / 27BB hits.

   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?
 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).
 I guess this might be doable in some linear time, i believe current code
does a O(NlogN) (worst case N^2)
  this also reduces the expected number of BB tests, but it doenst seems to
be as much as "pushups"

^^ "best tree" refers to a tree where casting a full-space-search rays would
yeild a equal or smaller number of BB tests.

*tested diferents raycast stack size (didnt seem to have any influence on
speed :S)

*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)

*did some local experiences with sse, but I did not have time to start
implementing it.

==Next week==
As said before, I will be camping until 31july.
When I get back I plan to start looking on things like: sse, memory
organization.

==Questions==
I hope people don't mind big reports.
None.

==Schedule==
The idea was to start appling SSE this week, but I was quite busy thinking
and reading and drawing (algorithms, papers and graphs).

I will be camping until 31july (on iceland).

--
André
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.blender.org/pipermail/soc-2009-dev/attachments/20090717/594ee5f9/attachment.htm