<br><br><div class="gmail_quote">On Sat, Feb 25, 2012 at 3:13 AM, Mark Roden <span dir="ltr"><<a href="mailto:mmroden@gmail.com">mmroden@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
We need to display the contour itself, not voxels that are inside the<br>
contour. </blockquote><div><br></div><div>Then why would you be generating the stencil ? Just cut the polydata with the slice plane and display it.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
It seems that Eclipse has trained everyone to expect this<br>
appearance, and the rtstruct itself is based around this premise.<br>
<br>
Unless we can get a contour through that approach?<br>
<div><div></div><div class="h5"><br>
On Fri, Feb 24, 2012 at 1:40 PM, Karthik Krishnan<br>
<<a href="mailto:karthik.krishnan@kitware.com">karthik.krishnan@kitware.com</a>> wrote:<br>
> But isn't vtkPolyDataToImageStencil, extrusion etc overkill for your<br>
> specific problem. Why not compute the mask by looping over all voxels within<br>
> the bounds of the contour on a slice and using vtkPolygon::PointInPolygon<br>
> for every such voxel. It evaluates inside-outside by using rayfiring and<br>
> that should run much faster; in the order of milliseconds<br>
><br>
> On Sat, Feb 25, 2012 at 2:21 AM, Mark Roden <<a href="mailto:mmroden@gmail.com">mmroden@gmail.com</a>> wrote:<br>
>><br>
>> Hi David,<br>
>><br>
>> Sorry for being extremely tardy on continuing this thread, but the<br>
>> issue took a back burner to more pressing problems that arose pretty<br>
>> suddenly.<br>
>><br>
>> Anyway, I think I see what's going on here, and I have some hypotheses.<br>
>><br>
>> We have a vtkPolyData read in by GDCM. This structure is read in via<br>
>> double precision (a change I've made recently that may or may not have<br>
>> any bearing).<br>
>><br>
>> If we use the following series of vtk classes, the data can be<br>
>> visualized on a CT Dicom image (whose z coordinates are in float<br>
>> space, as best as I can tell):<br>
>><br>
>> vtkLinearExtrusionFilter<br>
>> vtkPolyDataToImageStencil<br>
>> vtkImageStencil<br>
>><br>
>> This series of operations, on one test data set, requires 25 seconds<br>
>> on a fairly fast machine to produce contours for all the organs in the<br>
>> structure set. On our testers' machines, that number is roughly<br>
>> triple, meaning that they are going nuts with waiting times.<br>
>><br>
>> If we remove the extruder, then the time drops to 10 seconds, a pretty<br>
>> significant speedup (using vtk git source from 10 jan 2012). Problem<br>
>> is, now the data are not visible on the CT image at all. I suspect<br>
>> that they are not visible because the coordinates do not match<br>
>> _exactly_ in z, but I really have no way to back up that hypothesis.<br>
>><br>
>> It seems that the extruder, in this case, is acting as an error range<br>
>> in z; ie, allowing the stencil a bit more leeway to finding the proper<br>
>> plane in Z. Trouble is, that code path is triggering the slow path<br>
>> you talked about.<br>
>><br>
>> Is there a way to set a kind of z tolerance to the stencil to achieve<br>
>> the same effect? Or am I off-base as to why the contours would not<br>
>> appear on the data?<br>
>><br>
>> Thanks,<br>
>> Mark<br>
>><br>
>><br>
>> On Wed, Jan 25, 2012 at 4:20 PM, David Gobbi <<a href="mailto:david.gobbi@gmail.com">david.gobbi@gmail.com</a>><br>
>> wrote:<br>
>> > Hi Mark,<br>
>> ><br>
>> > In all my previous replies to your questions, I assumed that your data<br>
>> > consisted of a surface (i.e. with polygonal faces). If your data is a<br>
>> > series of polylines, then that changes things... particularly with<br>
>> > respect to what version of VTK you are using.<br>
>> ><br>
>> > If your data consists of a series 2D polyline contours in 3D space,<br>
>> > prior to VTK 5.8, vtkPolyDataToImageStencil could not use this kind of<br>
>> > data, it required a 3D surface and it would cut that surface to<br>
>> > generate contours. In VTK 5.8, the ability to directly process a<br>
>> > series of 2D contours was added, but very inefficiently. In VTK git,<br>
>> > the code for handling a series of 2D contours was modified to become<br>
>> > much more efficient.<br>
>> ><br>
>> > For the vtkPolyDataToImageStencil in VTK 5.8, the PolyDataCutter<br>
>> > function does this: if the input contains any only polylines, then the<br>
>> > "if (cell->GetCellDimension() == 1)" branch is used. If the input<br>
>> > contains any polygons, however, then the "if (cell->GetCellDimension()<br>
>> > == 2)" branch is used. Only this latter branch actually does any<br>
>> > cutting/contouring of the data.<br>
>> ><br>
>> > In VTK git, the code for polylines uses its own efficient subroutine<br>
>> > called PolyDataSelector. So for polyline contours, this is the best<br>
>> > version to use. Also, for polyline contours, the "loose end" code will<br>
>> > not find any loose ends (and therefore not eat up any CPU) if the<br>
>> > polylines that make up your contours are already closed. You can<br>
>> > always run your contours through vtkCleanPolyData and vtkStripper to<br>
>> > ensure that this is the case.<br>
>> ><br>
>> > - David<br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> > On Wed, Jan 25, 2012 at 4:08 PM, Mark Roden <<a href="mailto:mmroden@gmail.com">mmroden@gmail.com</a>> wrote:<br>
>> >> OK, so I've looked further into this problem, and it seems that I was<br>
>> >> optimizing the wrong thing.<br>
>> >><br>
>> >> If I comment out everything other than the PolyDataCutter method<br>
>> >> (specifically, the call to 'contour' in there), then contours take the<br>
>> >> same amount of time to load as they do with everything turned on. All<br>
>> >> of the time is being spent in the Contour routine.<br>
>> >><br>
>> >> However, rtstructs are already organized into contours. Each set of<br>
>> >> three numbers corresponds to a point in 3D space, and then each<br>
>> >> succeeding group corresponds to the next point in the contour. From<br>
>> >> what I can determine, there is no need for this PolyDataCutter<br>
>> >> routine.<br>
>> >><br>
>> >> How can I tell the vtkPolyDataToImageStencil class that the data are<br>
>> >> already properly organized, that each point that follows is connected<br>
>> >> to the one previous, and in the case of a CLOSED contour, the last<br>
>> >> connects to the first?<br>
>> >><br>
>> >> On Mon, Jan 23, 2012 at 11:27 AM, David Gobbi <<a href="mailto:david.gobbi@gmail.com">david.gobbi@gmail.com</a>><br>
>> >> wrote:<br>
>> >>> On Mon, Jan 23, 2012 at 12:09 PM, Mark Roden <<a href="mailto:mmroden@gmail.com">mmroden@gmail.com</a>><br>
>> >>> wrote:<br>
>> >>>> Hi David,<br>
>> >>>><br>
>> >>>> Thanks for the response, I'll take a look at the clipclosedsurface<br>
>> >>>> class. That may be what I want anyway (does it allow for any one<br>
>> >>>> plane to have a hollow interior?), but if you've already done the<br>
>> >>>> hashing there, then I'll take a look at porting it to this class as<br>
>> >>>> well. Or should there be a shared routine that both classes use, if<br>
>> >>>> the work done is very similar?<br>
>> >>><br>
>> >>> A shared routine would be ideal, I had hoped to eventually write a<br>
>> >>> vtkCutClosedSurface filter for that purpose.<br>
>> >>><br>
>> >>> The vtkClipClosedSurface class does allow holes. It is described<br>
>> >>> here: <a href="http://vtk.org/Wiki/VTK/Closed_Surface_Clipping" target="_blank">http://vtk.org/Wiki/VTK/Closed_Surface_Clipping</a><br>
>> >>><br>
>> >>> - David<br>
>> >>><br>
>> >>><br>
>> >>><br>
>> >>>> On Mon, Jan 23, 2012 at 11:04 AM, David Gobbi <<a href="mailto:david.gobbi@gmail.com">david.gobbi@gmail.com</a>><br>
>> >>>> wrote:<br>
>> >>>>> On Mon, Jan 23, 2012 at 11:19 AM, Mark Roden <<a href="mailto:mmroden@gmail.com">mmroden@gmail.com</a>><br>
>> >>>>> wrote:<br>
>> >>>>>> Hi David,<br>
>> >>>>>><br>
>> >>>>>> I'm looking to make the vtkpolydatatoimagestencil class faster.<br>
>> >>>>>> Right<br>
>> >>>>>> now, on a core i7 machine and in using release-compiled code,<br>
>> >>>>>> translating a body mask in an rtstruct to pixels using this filter<br>
>> >>>>>> is<br>
>> >>>>>> prohibitively expensive in time (upwards of a minute for the mask).<br>
>> >>>>>><br>
>> >>>>>> There are three possible speedups to do here, in my mind. I wanted<br>
>> >>>>>> to<br>
>> >>>>>> clear them by you, because I don't want to fork vtk to solve this<br>
>> >>>>>> problem, but the problem has become a serious problem for us.<br>
>> >>>>>><br>
>> >>>>>> First, treat each plane independently of one another, and then have<br>
>> >>>>>> each plane processed by different threads. This change is fairly<br>
>> >>>>>> straightforward theoretically, and something you mentioned you were<br>
>> >>>>>> looking into a while back<br>
>> >>>>>> (<a href="http://www.vtk.org/pipermail/vtkusers/2011-January/114538.html" target="_blank">http://www.vtk.org/pipermail/vtkusers/2011-January/114538.html</a>).<br>
>> >>>>>> Is<br>
>> >>>>>> this something you're still investigating?<br>
>> >>>>><br>
>> >>>>> There were three things that I was considering:<br>
>> >>>>> 1) multi-threading so that each CPU gets N slices to work on<br>
>> >>>>> 2) increasing the efficiency of the polygon cutting code, I added<br>
>> >>>>> some<br>
>> >>>>> nice cutting code to vtkClipClosedSurface and planned to eventually<br>
>> >>>>> also use it in vtkPolyDataToImageStencil<br>
>> >>>>> 3) improving the efficiency or extent insertion for the stencils<br>
>> >>>>><br>
>> >>>>> So far I've only done #3, which was the least important but was the<br>
>> >>>>> easiest. Right now my own apps are bottlenecking on my segmentation<br>
>> >>>>> algorithms, rather than on vtkPolyDataToImageStencil, so improving<br>
>> >>>>> vtkPolyDataToImageStencil hasn't been a high priority.<br>
>> >>>>><br>
>> >>>>>> For my work on other projects, I've found that the intel tbb<br>
>> >>>>>> (<a href="http://threadingbuildingblocks.org/" target="_blank">http://threadingbuildingblocks.org/</a>) makes multithreading this<br>
>> >>>>>> kind<br>
>> >>>>>> of work very easy; the library is free and works with any c++<br>
>> >>>>>> project<br>
>> >>>>>> that uses the C++0x standard and can use lambda expressions.<br>
>> >>>>><br>
>> >>>>> VTK will have to continue to support pre-C++0x compilers for a long<br>
>> >>>>> time, several more years at least. So if threading is to be done,<br>
>> >>>>> it<br>
>> >>>>> should be done with VTK's threading classes.<br>
>> >>>>><br>
>> >>>>>> Second, change the interior while/for loop collision detection to<br>
>> >>>>>> be a<br>
>> >>>>>> hash table. Right now, in the ThreadedExecute function, there is<br>
>> >>>>>> this<br>
>> >>>>>> code:<br>
>> >>>>>><br>
>> >>>>>> for (vtkIdType i = 0; i < numberOfPoints; ++i)<br>
>> >>>>>> {<br>
>> >>>>>> ...<br>
>> >>>>>> while( lines->GetNextCell(npts, pointIds) )<br>
>> >>>>>> {<br>
>> >>>>>> for (vtkIdType j = 0; j < npts; ++j)<br>
>> >>>>>> if ( pointIds[j] == i )<br>
>> >>>>>> {<br>
>> >>>>>><br>
>> >>>>>> But what if collision detection was changed to uses a hash table<br>
>> >>>>>> where<br>
>> >>>>>> the hashing function automatically detected point collisions<br>
>> >>>>>> through a<br>
>> >>>>>> single pass through the data?<br>
>> >>>>><br>
>> >>>>> I use a hash vtkClipClosedSurface to accelerate the clipping (i.e.<br>
>> >>>>> #2<br>
>> >>>>> on my to-do list above). Take a look at the vtkClipClosedSurface<br>
>> >>>>> code, specifically the vtkCCSEdgeLocator class.<br>
>> >>>>><br>
>> >>>>>> Third, there does not appear to be an iterator over the points<br>
>> >>>>>> vector,<br>
>> >>>>>> but a Get and Set function. These functions appear to be pretty<br>
>> >>>>>> slow,<br>
>> >>>>>> and go through several thunking layers before data can actually be<br>
>> >>>>>> set<br>
>> >>>>>> or not. Is there an iterator class for points as there is for<br>
>> >>>>>> lines?<br>
>> >>>>>> If not, how hard would it be to create such a class?<br>
>> >>>>><br>
>> >>>>> The vtkPoints::GetData() method returns an array (either a<br>
>> >>>>> vtkFloatArray or a vtkDoubleArray) that contains the points. Once<br>
>> >>>>> you<br>
>> >>>>> have this array, the GetTupleValue() method is a purely inlined<br>
>> >>>>> method<br>
>> >>>>> that can be used to efficiently get the points. If you know ahead<br>
>> >>>>> of<br>
>> >>>>> time whether the points are double or float, then this is probably<br>
>> >>>>> the<br>
>> >>>>> most efficient way of accessing them, apart from getting the raw<br>
>> >>>>> "float *" or "double *".<br>
>> >>>>><br>
>> >>>>> - David<br>
>> _______________________________________________<br>
>> Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
>><br>
>> Visit other Kitware open-source projects at<br>
>> <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
>><br>
>> Follow this link to subscribe/unsubscribe:<br>
>> <a href="http://www.vtk.org/mailman/listinfo/vtk-developers" target="_blank">http://www.vtk.org/mailman/listinfo/vtk-developers</a><br>
>><br>
><br>
><br>
><br>
> --<br>
> --<br>
> karthik<br>
><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>--<div>karthik</div><br>