[vtk-developers] Cell location for unstructured grids - Plan

Tue Jul 12 11:40:17 EDT 2011

By coincidence I asked Ken about this paper yesterday  - so I'll chip in.

Subclassing vtkAbstractCellLocator would be the right approach.

[the algorithm for vtkCellTree is very similar in some repects to the Modified BSP tree in that overlapping cells are handled using a modification of the ideal BSP tree, in the cell tree the intervals are traversed doubly, but in the modBSP an extra node is created]

Although the paper only mentions a find cell function, there is no reason why you can't intersect a box with the bound/intervals and compute all leaves that overlap and from there, find all cells that intersect a sphere/box/other.

On a side note, the modBSP tree was created a for a particular raycasting app way back in the 1990's and stores a lot of unnecessary stuff for most uses, 6 copies of cells sorted by all 6 dominant ray axis directions, I considered removing a lot of this for a simpler version that would just do cell searches and this was partly why I was searching for stuff on the web and found the cellTree paper that you are working on. I needed to add 'Find Cells within radius' to the BSP code and was planning on doing this, but now I would like to implement the CellTree instead because I very much like the way the overlapping intervals are handled and the reduced storage. I also needed to add some functions to the BSP tree to find all leaf nodes with radius and then iterate over the cells contained inside, calling a functor for my own special algorithm. I had planned on a big overhaul of the BSP code to do this.

the vtkCellTree code will actually be quite similar in some respects to the modBSP tree code for all the bounds caching and some of the list sorting. It ought to be quite simple to simply cut out a load of stuff from modBSP and insert the relevant new build and traversal functions from the cellTree paper (+visit code). I had a quick look at the visit code and it looks fine.

I would be happy to help create the vtkCellTree class, it looks like a small job given the existing code - and since I need the extra functions like find cells in radius etc, I have a motivation.

JB

From: vtk-developers-bounces at vtk.org [mailto:vtk-developers-bounces at vtk.org] On Behalf Of Andy Bauer
Sent: 12 July 2011 17:05
To: Tharindu De Silva; vtk-developers at vtk.org
Subject: Re: [vtk-developers] Cell location for unstructured grids - Plan

Hi Tharindu,

I'm also sending this email to the vtk developers list in case other people have insight into your work.

I'm not sure I completely understand the problem.  Can you just replace the implementation for FindCell() with a better implementation without affecting other class methods?  If you can do that, I'd just worry about that first and then do some profiling/performance testing to see where it's at.  After that it may be worthwhile to see if some of the other class methods can be improved too.  If a decent amount of changes have to be made in order to implement that algorithm though then it may make sense to subclass from an existing concrete cell locator class.

HTH,
Andy
On Mon, Jul 11, 2011 at 11:54 PM, Tharindu De Silva <tsameera1 at gmail.com<mailto:tsameera1 at gmail.com>> wrote:
Hi Andy,

       When I go through vtkCellLocator and vtkModifiedBSPTree classes, I find that in addition to finding the containing-cell of a given point (findCell method), they have some extra functionality (e.g. Finding cells which intersect a given line, closest cell within a radius). With what I understood from the paper, it describes an efficient method to locate the cell given a point.  I am not sure at this point, whether that algorithm can be extended to improve  other functionality such as line intersection.  At this point, I can subclass vtkCellLocator and implement FindCell method in that subclass according to the algorithm given in the paper.  This is in contrast to the initial idea I had to have another class like vtkCellLocator to implement the given algorithm.  Please let me know, what you think about subclassing vtkCellLocator and implementing the FindCell method.

Thank you,

Regards,

Tharindu

On Fri, Jul 8, 2011 at 9:18 AM, Andy Bauer <andy.bauer at kitware.com<mailto:andy.bauer at kitware.com>> wrote:
There's a list of examples at http://www.vtk.org/Wiki/VTK/Examples

Doing "ctest -R CellLocator -N" gives me one cell locator test.

I'm not sure if any of them are specific to unstructured grids but since any VTK grid can be converted to an unstructured grid you should be able to modify them to work as desired.

Andy

On Thu, Jul 7, 2011 at 4:17 PM, Tharindu De Silva <tsameera1 at gmail.com<mailto:tsameera1 at gmail.com>> wrote:
Hi Andy,

     Could you please point out to me if there is any existing example that tests cell location in unstructured grids.  If there is, I can use that as an initial check during my implementation.

Thank you very much,

Tharindu
On Thu, Jul 7, 2011 at 11:00 AM, Andy Bauer <andy.bauer at kitware.com<mailto:andy.bauer at kitware.com>> wrote:
Hi Tharindu,

I'd be interested in taking a look at what you're doing.  Is www.idav.ucdavis.edu/~garth/pdfs/vis10a.pdf<http://www.idav.ucdavis.edu/%7Egarth/pdfs/vis10a.pdf> the paper you're talking about?  I haven't gone through it yet so I can't give much feedback now.  I'll try to answer any questions you have and if you want me to review your code, feel free to push it to gerrit and add me as a reviewer.

Andy

On Thu, Jul 7, 2011 at 10:50 AM, Berk Geveci <berk.geveci at kitware.com<mailto:berk.geveci at kitware.com>> wrote:
That sounds like a good plan. I included Will and Andy. They probably
know most about locators and can provide some additional guidance.
What do you think guys?

PS: Tharindu is the Google Summer of Code student working on
implementing 2 papers from last VisWeek in VTK.

On Fri, Jul 1, 2011 at 3:12 PM, Jeff Baumes <jeff.baumes at kitware.com<mailto:jeff.baumes at kitware.com>> wrote:
> Berk may have some guidance on the cell locator, or may direct you someone
> else who can help.
> Jeff
>
> On Mon, Jun 27, 2011 at 4:17 PM, Tharindu De Silva <tsameera1 at gmail.com<mailto:tsameera1 at gmail.com>>
> wrote:
>>
>> HI Jeff and Marcus,
>>      I started with the second paper, "Fast memory efficient cell location
>> in unstructered grids for visualization" paper.  I have been going through
>> vtkCellLcoator and vtkModifiedBSPTree classes.  My plan is to implement
>> another class like this subclassing vtkAbstractCellLocator class. I am
>> sorry, that I was a little slow in understanding the paper due to my lack of
>> background in especially the data structures being used.  Now, I understand
>> most of the paper, but there is still more to be done.  In the next couple
>> of weeks I will implement that paper.
>>   Meanwhile, I requested the author of tick label paper for the data that
>> he used to try an replicate all the results he got.  But he didn't get back
>> to me yet.  Some figures have a lot of tiny data points that it is hard to
>> trace it visually.  I will write an interface that I can trace that data by
>> clicking points and replicate all the results in the paper.
>> Thank you,
>> Tharindu
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20110712/f5640f71/attachment.html>