[vtkusers] recommended cell locator for IntersectWithLine tests?
Biddiscombe, John A.
biddisco at cscs.ch
Tue Mar 23 03:27:15 EDT 2010
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
More information about the vtkusers
mailing list