<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 12 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">By coincidence I asked Ken about this paper yesterday - so I’ll chip in.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Subclassing vtkAbstractCellLocator would be the right approach.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">[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]<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">JB<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> vtk-developers-bounces@vtk.org [mailto:vtk-developers-bounces@vtk.org]
<b>On Behalf Of </b>Andy Bauer<br>
<b>Sent:</b> 12 July 2011 17:05<br>
<b>To:</b> Tharindu De Silva; vtk-developers@vtk.org<br>
<b>Subject:</b> Re: [vtk-developers] Cell location for unstructured grids - Plan<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-bottom:12.0pt">Hi Tharindu,<br>
<br>
I'm also sending this email to the vtk developers list in case other people have insight into your work.<br>
<br>
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.<br>
<br>
HTH,<br>
Andy<o:p></o:p></p>
<div>
<p class="MsoNormal">On Mon, Jul 11, 2011 at 11:54 PM, Tharindu De Silva <<a href="mailto:tsameera1@gmail.com">tsameera1@gmail.com</a>> wrote:<o:p></o:p></p>
<p class="MsoNormal">Hi Andy,<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> When I go through <i>vtkCellLocator</i> and <i>vtkModifiedBSPTree</i> 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 <i>vtkCellLocator</i> 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
<i>vtkCellLocator </i>to implement the given algorithm. Please let me know, what you think about subclassing vtkCellLocator and implementing the FindCell method.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thank you,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Regards,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">Tharindu</span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Fri, Jul 8, 2011 at 9:18 AM, Andy Bauer <<a href="mailto:andy.bauer@kitware.com" target="_blank">andy.bauer@kitware.com</a>> wrote:<o:p></o:p></p>
<p class="MsoNormal">There's a list of examples at <a href="http://www.vtk.org/Wiki/VTK/Examples" target="_blank">
http://www.vtk.org/Wiki/VTK/Examples</a><br>
<br>
Doing "ctest -R CellLocator -N" gives me one cell locator test. <br>
<br>
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.<br>
<span style="color:#888888"><br>
Andy</span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Thu, Jul 7, 2011 at 4:17 PM, Tharindu De Silva <<a href="mailto:tsameera1@gmail.com" target="_blank">tsameera1@gmail.com</a>> wrote:<o:p></o:p></p>
<p class="MsoNormal">Hi Andy,<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> 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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thank you very much,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="color:#888888">Tharindu</span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal">On Thu, Jul 7, 2011 at 11:00 AM, Andy Bauer <<a href="mailto:andy.bauer@kitware.com" target="_blank">andy.bauer@kitware.com</a>> wrote:<o:p></o:p></p>
</div>
<div>
<div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal">Hi Tharindu,<br>
<br>
I'd be interested in taking a look at what you're doing. Is <a href="http://www.idav.ucdavis.edu/%7Egarth/pdfs/vis10a.pdf" target="_blank">
www.idav.ucdavis.edu/~garth/pdfs/vis10a.pdf</a> 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.<br>
<span style="color:#888888"><br>
Andy</span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Thu, Jul 7, 2011 at 10:50 AM, Berk Geveci <<a href="mailto:berk.geveci@kitware.com" target="_blank">berk.geveci@kitware.com</a>> wrote:<o:p></o:p></p>
<p class="MsoNormal">That sounds like a good plan. I included Will and Andy. They probably<br>
know most about locators and can provide some additional guidance.<br>
What do you think guys?<br>
<br>
PS: Tharindu is the Google Summer of Code student working on<br>
implementing 2 papers from last VisWeek in VTK.<br>
<br>
On Fri, Jul 1, 2011 at 3:12 PM, Jeff Baumes <<a href="mailto:jeff.baumes@kitware.com" target="_blank">jeff.baumes@kitware.com</a>> wrote:<br>
> Berk may have some guidance on the cell locator, or may direct you someone<br>
> else who can help.<br>
> Jeff<br>
><br>
> On Mon, Jun 27, 2011 at 4:17 PM, Tharindu De Silva <<a href="mailto:tsameera1@gmail.com" target="_blank">tsameera1@gmail.com</a>><br>
> wrote:<br>
>><br>
>> HI Jeff and Marcus,<br>
>> I started with the second paper, "Fast memory efficient cell location<br>
>> in unstructered grids for visualization" paper. I have been going through<br>
>> vtkCellLcoator and vtkModifiedBSPTree classes. My plan is to implement<br>
>> another class like this subclassing vtkAbstractCellLocator class. I am<br>
>> sorry, that I was a little slow in understanding the paper due to my lack of<br>
>> background in especially the data structures being used. Now, I understand<br>
>> most of the paper, but there is still more to be done. In the next couple<br>
>> of weeks I will implement that paper.<br>
>> Meanwhile, I requested the author of tick label paper for the data that<br>
>> he used to try an replicate all the results he got. But he didn't get back<br>
>> to me yet. Some figures have a lot of tiny data points that it is hard to<br>
>> trace it visually. I will write an interface that I can trace that data by<br>
>> clicking points and replicate all the results in the paper.<br>
>> Thank you,<br>
>> Tharindu<br>
><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>