[yt-dev] Fwd: Naming our software

Mon Mar 10 21:41:56 PDT 2014

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 <bogart.alex at gmail.com> 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 <bogart.alex at gmail.com>
>> 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" <jrholden at ucsc.edu> 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 <bogart.alex at gmail.com>
>>>> wrote:
>>>>
>>>> Any update on AMR?
>>>>
>>>> On Mar 6, 2014 10:18 PM, "John Holdener" <jrholden at ucsc.edu> 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 at ucsc.edu
>>>>>
>>>>>
> --
> John R. Holdener
> Research Assistant
> UCSC HiPACC
> jrholden at ucsc.edu
>
>
>
> _______________________________________________
> yt-dev mailing list
> yt-dev at lists.spacepope.org
> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.spacepope.org/pipermail/yt-dev-spacepope.org/attachments/20140310/9043a050/attachment.html>