Hi Yves,<br><br>I have only started to care about SIMD since last week, this is because I can't even be sure that SSE will be enabled on official builds.<br><br>So far optimizations tricks used during tree build make a creation of a QBVH (or other structure with groupped childs) not that direct.<br>
<br>The build with SAH builds a 2-way tree.. but then the tree optimizations (done in O(N) and O(NLogN)) (which reduce the expected number of BB-tests) transform it into a tree where each node can have any number of childs.<br>
This "any number of childs" make it harder to implement groupped childs.<br><br>eg.: some sample data of a subset of the overlap2 scene (witouth tree optimization / with tree optimization):<br>BB tests per ray: 96.979 / 76.210<br>
BB hits per ray: 64.598 / 33.964<br><br>About ray-coherency, I decided to only exploit it using hints to build tree-cuts (like a LCTS), as other type of approach would be too troublesome and a waste of time considering the modifications on BI code that will probably be modified soon.<br>
<br>
As so my initial approach to SIMD, was the simplest as possible, 1ray-4bvhs.<br>The current SoC tree structures was not organized for it, and so an initial try was implemented by poping 4nodes at a time from the dfs stack.<br>
(This allowed to test simd ray-bb code, improve BLI_arena for doing 16aligned mallocs, and for me to get use to simd code)<br><br>During this week I plan to optimize the data structure not only for grouping childs of BVH's, but also to yeild better memory access for non-SIMD builds.<br>
<br>So I think I am going on a good direction!<br>thanks for the feedback (nice to know people read what I do :)<br><br>André<br><br><div class="gmail_quote">2009/8/8 Yves Poissant <span dir="ltr"><<a href="mailto:ypoissant2@videotron.ca">ypoissant2@videotron.ca</a>></span><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">> Date: Fri, 7 Aug 2009 20:03:57 +0100<br>
> From: Andr? Pinto<br>
<br>
> *Tested some memory organization and started some SIMD stuff.<br>
> (SIMD recursion, 4 nodes are pop-ed from stack and theirs BB tested at<br>
> same<br>
> time, this doens't seems to scale that well, probably due to memory<br>
> reorganization time and somehow bad assembly code). As so I have tried<br>
> some<br>
> compile optimization flags to try to make it worth it.<br>
<br>
I'm not sure how you are doing the SSE data organization. Your description<br>
is not detailed enough.<br>
N-ary BVH traversal with SSE needs a priori data organization at tree build<br>
time. Not on demand data organization when traversing. Your 4 nodes BBox<br>
data should already be organized as structure of arrays. The leaf nodes<br>
should also have 4 triangled also organized as structure of arrays.<br>
<br>
Papers discussing this technique (Ernst & Greiner, Dammertz, Hanika & Keller<br>
and Wald, Bentin & Boulos) have reported between 1.5 to 2.5 traversal speed<br>
improvement using this technique witn 4-ary BVHs. It is less efficient than<br>
bundle traversal for coherent rays but much more efficient than bundle<br>
traversal for very incoherent rays. Current BI does not have a big use of<br>
incoherent rays except for AO and to a lesser extent for soft reflections.<br>
<br>
Another technique that adapts well to BVH and n-ary BVH for coherent rays is<br>
Multi-Level Ray Tracing Algorithm (MLRTA) by Reshetov where you can push a<br>
bundle of coherent rays inside the tree before starting to test the<br>
individual rays.<br>
<br>
Yves<br>
<br>
<br>
_______________________________________________<br>
Soc-2009-dev mailing list<br>
<a href="mailto:Soc-2009-dev@blender.org">Soc-2009-dev@blender.org</a><br>
<a href="http://lists.blender.org/mailman/listinfo/soc-2009-dev" target="_blank">http://lists.blender.org/mailman/listinfo/soc-2009-dev</a><br>
</blockquote></div><br>