Re: [yt-dev] Fwd: Naming our software

Hi Alex, I think there are a couple things to clear up here -- hopefully this will help. First a little background. For the case of patch-based AMR volume rendering, a popular technique is to first decompose the dataset into a kd-tree of single-resolution bricks that form the leaf nodes. This helps both ray traversal ordering and provides a way to tile the multi-resolution dataset into single-resolution bricks. When writing the AMRKDTree object in yt, we based the majority of the design off this paper: http://vis.lbl.gov/Publications/2002/LBNL-49954-AMRVolumeRendering.pdf The technique is: 1. Take as input the AMR patches 2. Find splitting planes that produce as minimal set of bricks and to maximize load balance. This uses heuristics, and effects parallelization and i/o balance. 3. Provide an interface to iterate through these bricks in an arbitrary ordering defined by viewing positions. 4. For datasets larger than what can be held in memory, one needs to either stream in data from disk or decompose the volume in a way that can be later combined in a composite step. A key thing to note here is that a single patch may be composed of many kd-tree bricks. This is why you see a mismatch between 'dims' of the brick and 'ActiveDimensions' of the grid (same goes for edge positions). In yt, the steps are implemented as: 1. Use the hierarchy object as input 2. Look at the build() and add_grids function that hangs off the (internal API, maybe not well named) Tree object in yt/utilities/amr_kdtree/amr_kdtree.py 3. Look at depth_traverse, viewpoint_traverse, slice_traverse, etc. 4. There is a bunch of logic on how to decompose a kd-tree in parallel, and combine using reduce_tree_images. We domain decompose the tree in a breadth-first traversal over N processors. Other notes: For tri-linear interpolation, vertex centered data is generated through initialize_source and get_brick_data. I hope to work with folks to make the data access a bit simpler for different fields during the yt workshop in a few weeks. For GPU volume rendering of AMR data, make sure to take a look at some of the literature out there, for example http://arxiv.org/abs/1212.3333 I am happy to help go through some of this at UCSC in a few weeks. I'm afraid I won't be able to dedicate a ton of time on this until then, however. The code in yt shouldn't be too difficult to parse though, if you want to really dive in you'll have to look in yt/utilities/lib/amr_kdtools.pyx for the Cython pieces. yt-3.0 has some more improvements -- I'm not sure what codebase you are working from. Cheers, Sam On Mon, Mar 10, 2014 at 1:20 PM, Alex Bogert wrote:

Moving our discussion about AMR hard ware volume rendering to yt-dev.:

Hey Matt,

The variables I need are the corners of the bounding box (which I call mi, ma, basically left and right edges), number of cells in a grid, grid data itself, children of a grid, and parent of a grid. This data itself works.

I notice children aren't referenced. Is that because everything is defined just in terms of who the parent is, and where the tile exists within the parent? (Which if that's the case, since a top-down traversal is necessary in CUDA, the structure would have to be reversed).

Another thing, I notice that 'dims' and g.ActiveDimensions do not match up a majority of the time. If they don't match up, how do you take a point in space and determine what grid element it maps to? (Trivial, but if these two don't match, I'm not sure who I should trust when doing the computation).

On 3/10/14, 10:59 AM, Matthew Turk wrote:

...

Hi Alex,

We can have these discussions on yt-dev, too:

http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org

Other people have developed this stuff. You're right, the patches are (by design) *not* kD-trees. To get kD-trees, you have to use the .tiles interface, like so:

pf = load(...) data_source = pf.h.some_object_type(...) for (g, node, (sl, dims, gi)) in data_source.tiles.slice_traverse(): ...

here g is the grid object, node is the node of the kD-tree (for things like neighbor searching and the like), slice is the slice into the grid object that defines the node of the kD-tree, dims is the dimensions of the kD-tree brick, and gi is the left-edge in integers of the grid object. You can also do traverse, which just iterates and returns the partitioned grid data and which takesa viewpoint.

-Matt

On Mon, Mar 10, 2014 at 1:45 PM, Alex Bogert wrote:

...

Hi Matt,

I remeber you saying yt can give us AMR in a kd-tree. Was this something like .get_grids or .get_tiles ?

Thanks, Alex

On Mar 10, 2014 10:21 AM, "John Holdener" wrote:

...

I'll be in lab shortly near 11. There is a serious complication that I need to talk to Matt about on the phone (when he gets time). I've been playing with patches, which are not kt-trees (there are many elements with no parent or children). This format would take forever searching every grid for samples.

Once yt gives me a kt-tree, namely whatever class gives it to me, it should become just CUDA coding.

Everything will need to be global memory, due to texture count constraints anyways. I suspect the first images will look awful (until some estimated interpolation happens). Until we get trees sorted out, AMR is at a standstill.

Sent from my iPhone

On Mar 10, 2014, at 10:04 AM, Alex Bogert wrote:

Any update on AMR?

On Mar 6, 2014 10:18 PM, "John Holdener" wrote:

...

I could buy that. However the number of typos typing Theia is going to drive me nuts!

On 3/6/14, 3:03 PM, Alex Bogert wrote:

...

Both Joel and I agree we need a good name for the software. I found "Theia" goddess of tracing and the origin of all light. The greeks believe she casted light from their eyes to see the world. Super literal encapsulation. Im open for suggestions! No more acronyms or anything to do with what languages we use. I think only programmers appreciate these type of names :)

--

John R. Holdener Research Assistant UCSC HiPACC jrholden@ucsc.edu

-- John R. Holdener Research Assistant UCSC HiPACC jrholden@ucsc.edu

_______________________________________________ yt-dev mailing list yt-dev@lists.spacepope.org http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org