[vtkusers] recommended cell locator for IntersectWithLine tests?

Biddiscombe, John A. biddisco at cscs.ch
Wed Mar 24 09:59:05 EDT 2010


I've implemented an IntersectWithLine which stores all intersections and sorts them by T. CVS is locked now (I think), so when you want to try it, let me know and I'll send it for experimentation before getting it put into CVS.

JB


> -----Original Message-----
> From: vtkusers-bounces at vtk.org [mailto:vtkusers-bounces at vtk.org] On Behalf
> Of Biddiscombe, John A.
> Sent: 23 March 2010 08:27
> To: Dean Inglis; vtkusers archive
> Subject: Re: [vtkusers] recommended cell locator for IntersectWithLine
> tests?
> 
> Dean
> 
> I've been working on the BSP tree code during the last few days, so I'll see
> if I have a minute to implement the test. From the snippet you posted below,
> I'd say yes. Simply don't terminate - using a large T value would work, then
> sort the intersections afterwards. I'm out of the office right now, but will
> certainly have a look at it before the end of the week. Branching today I
> think (for ParaView anyway), but I'm sure we can sneak a fix in.
> 
> Do a CVS update today of BSP - as I added a bit yesterday - and if you want
> to try your idea and send me a snippet later, then please do.
> 
> JB
> 
> > -----Original Message-----
> > From: Dean Inglis [mailto:dean.inglis at camris.ca]
> > Sent: 23 March 2010 01:20
> > To: vtkusers archive
> > Cc: Biddiscombe, John A.
> > Subject: Re: [vtkusers] recommended cell locator for IntersectWithLine
> > tests?
> >
> > Hi John,
> >
> > Im looking at vtkModifiedBSPTree to add the functionality
> > I was querying about earller.  If I base
> >
> >   int IntersectWithLine(const double a0[3], const double a1[3],
> >                         vtkPoints *points, vtkIdList *cellIds);
> >
> > on
> >
> > int vtkModifiedBSPTree::IntersectWithLine(double p1[3], double p2[3],
> double
> > tol,
> >   double &t, double x[3], double pcoords[3], int &subId, vtkIdType
> &cellId)
> >
> > then in the latter method, it seems all one need do is
> > modfiy the hit test to store the hit point as soon as its found:
> >
> >             if (t_hit<closest_intersection) {
> >               HIT = true;
> >               closest_intersection = t_hit;
> >               cellId = cell_ID;
> >               x[0] = ipt[0];
> >               x[1] = ipt[1];
> >               x[2] = ipt[2];
> >             }
> >
> > becomes
> >
> >             if (t_hit<closest_intersection) {
> >               HIT = true;
> >               closest_intersection = VTK_LARGE_FLOAT;  // keep on looking
> > for hits
> >               cellId = cell_ID;
> >               x[0] = ipt[0];
> >               x[1] = ipt[1];
> >               x[2] = ipt[2];
> >               points->InsertNextPoint( x );
> >               cellIds->InsertNextId(cellId);
> >               tvalues->InsertNextTuple( t_hit );
> >             }
> >
> > after all hits are found, one would have to sort the points in order of
> > parametric distance (tvalues).  Does this seem right or am I missing
> > something?  I don't suppose you could help writing some jiggery-pokery to
> > get all
> > intersections with a line before the upcoming VTK release?
> >
> > regards,
> > Dean
> >
> > ----- Original Message -----
> > From: "Biddiscombe, John A." <biddisco at cscs.ch>
> > To: "Dean Inglis" <dean.inglis at camris.ca>; "vtkusers archive"
> > <vtkusers at vtk.org>
> > Sent: Thursday, December 17, 2009 4:15 AM
> > Subject: RE: [vtkusers] recommended cell locator for IntersectWithLine
> > tests?
> >
> >
> > Dean
> >
> > Adding a routine to return all intersections along the line was always on
> my
> > to-do list for vtkModifiedBSPTree. I don't think I have any spare time
> right
> > now, but it is actually quite simple to implement.
> >
> > The ray is intersected with spatial regions (tree nodes) and a stack of
> > bboxes is created with ray fragments associated with them, when an
> > intersection is found, the intersection is terminated (providing no cells
> > remain in the current leaf node that could intersect earlier). When the
> > termination criteria is met, the loop exits, the stack is left and the
> > intersection is returned.
> >
> > All one needs to do is - not terminate - simply add the intersection to a
> > list and keep going until the end of the stack walking is complete. There
> > may be some jiggery-pokery required to get the correct ray fragment as I
> > can't remember if everything needed is on the stack too.
> >
> > If I can't sleep one night soon, I'll implement it for you.
> >
> > JB
> >
> >
> >
> > > -----Original Message-----
> > > From: vtkusers-bounces at vtk.org [mailto:vtkusers-bounces at vtk.org] On
> Behalf
> > > Of Dean Inglis
> > > Sent: 17 December 2009 02:48
> > > To: vtkusers archive
> > > Subject: Re: [vtkusers] recommended cell locator for IntersectWithLine
> > > tests?
> > >
> > > Hi David,
> > >
> > > thanks but the signature I am looking for (I just found out) is only
> > > implemented in
> > > vtkOBBTree.  I need all the points of intersection along the line.
> > > All the other child classes of vtkAbstractCellLocator just
> > > call the Superclass method in which case it just says:
> > >   vtkErrorMacro(<<"The locator class - " << this->GetClassName()
> > >     << " does not yet support this IntersectWithLine interface");
> > >
> > > Dean
> > >
> > > >I highly recommend the vtkModifiedBSPTree. It sped up my intersections
> > > >over the OBBTree about 40x. I didn't ever play with those kind of
> > > >settings so I can't recommend any, I just used the defaults and it
> > > >seemed to work fine for my application.
> > >
> > >
> > > > I am revisiting some old code I wrote to do stereology measurements
> > > > (mean intercept length).  I am rotating a set of evenly spaced
> parallel
> > > > test lines (in the x-y plane) and during each rotation I need to find
> > > > all
> > > > the intersection points
> > > > of the lines with a set of perpendicular planes defined by a
> vtkPolyData
> > > > ( imagine the planes as being the walls of a maze ).  I was using
> > > > vtkOBBTree
> > > > with the following settings:
> > > >   this->OBBTree->CacheCellBoundsOff();
> > > >   this->OBBTree->AutomaticOff();
> > > >   this->OBBTree->SetMaxLevel( 100 );
> > > >   this->OBBTree->SetNumberOfCellsPerNode( 1 );
> > > >
> > > > but there are some cases wherein not all the interesection points are
> > > > found.
> > > > The number of "walls" in the "maze" are in the hundreds but less than
> a
> > > > thousand.
> > > > The walls do not necessarily form closed polygons.  Can anyone
> recommend
> > > > a more robust locator and if so with some suggested settings?
> > > >
> > >
> > >
> > > _______________________________________________
> > > Powered by www.kitware.com
> > >
> > > Visit other Kitware open-source projects at
> > > http://www.kitware.com/opensource/opensource.html
> > >
> > > Please keep messages on-topic and check the VTK FAQ at:
> > > http://www.vtk.org/Wiki/VTK_FAQ
> > >
> > > Follow this link to subscribe/unsubscribe:
> > > http://www.vtk.org/mailman/listinfo/vtkusers
> 
> _______________________________________________
> Powered by www.kitware.com
> 
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
> 
> Please keep messages on-topic and check the VTK FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
> 
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers



More information about the vtkusers mailing list