[vtkusers] recommended cell locator for IntersectWithLine tests?

[Dean Inglis]

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