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

Tharindu De Silva tsameera1 at gmail.com
Tue Jul 12 12:38:02 EDT 2011


Thanks John for the ideas.  So I will subclass vtkAbstractCellLocator and
implement FindCell method first.  I'll let you know when my implementation
is done.

Thanks

Tharindu


On Tue, Jul 12, 2011 at 11:40 AM, Biddiscombe, John A. <biddisco at cscs.ch>wrote:

>  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>
> 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> 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>
> 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>
> 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>
> 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>
> 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>
> > 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/3237ec7c/attachment.html>


More information about the vtk-developers mailing list