[vtkusers] vtkStripper limitation

[Carl Hetherington]

On Mon, 14 Jan 2002, Will Schroeder wrote:

> Hi Carl-
> 
> There is always room for improvement and your ideas seem good. I am looking 
> forward to seeing your code contribution ;-)

Below is a patch (against the VTK 4.0 release candidate version of
vtkStripper.cxx) which solves my problems and works for my (rather
limited) range of datasets.

I'd be interested in any comments.

Cheers,
Carl



--- vtkStripper-rc.cxx	Tue Jan 22 17:42:04 2002
+++ vtkStripper-proposed.cxx	Tue Jan 22 18:58:54 2002
@@ -348,11 +348,128 @@
     }
 
   // output poly-lines
-  if ( newLines )
-    {
-    newLines->Squeeze();
-    output->SetLines(newLines);
+  if ( newLines ) {
+
+    // In some cases it may be possible to optimise the output
+    // poly-lines a bit.  The algorithm thus-far sometimes outputs
+    // polylines that could be joined together but are not.  We now
+    // go through joining any lines that we can.
+    //
+
+    // compressedLines will be our output line set, possibly
+    // with some lines joined together.
+    vtkCellArray* compressedLines = vtkCellArray::New();
+
+    bool* used = new bool[newLines->GetNumberOfCells()];
+    for (i = 0; i < newLines->GetNumberOfCells(); i++)
+      used[i] = 0;
+
+    bool done = false;
+    while (!done)
+      {
+      int out_n = 0;
+      vtkIdType* out_p = new vtkIdType[newLines->GetNumberOfConnectivityEntries()];
+
+      newLines->InitTraversal();
+      int id = -1;
+      vtkIdType n;
+      vtkIdType* p;
+
+      // Find a line from the original set that has not yet been used
+      do
+	{
+	if (newLines->GetNextCell(n, p) == 0)
+	  done = true;
+	id++;
+        } while (!done && (used[id] == 1));
+
+      if (done == false)
+	{
+	// Write it into our output line
+	memcpy(out_p + out_n, p, n * sizeof(vtkIdType));
+	out_n += n;
+	used[id] = 1;
+
+	// Now add any unused lines that adjoin this current line
+	bool done_this = false;
+	while (!done_this)
+	  {
+
+	  // Here's the start and end of our current line
+	  vtkIdType ca = out_p[0];
+	  vtkIdType cb = out_p[out_n - 1];
+
+	  vtkIdType ta;
+	  vtkIdType tb;
+	  bool found = false;
+
+	  // Look for any lines which adjoin this one
+	  while (!done_this && !found)
+	    {
+
+	    if (newLines->GetNextCell(n, p) == 0)
+	      done_this = true;
+	    id++;
+
+	    if (!done_this && (used[id] == 0))
+	      {
+	      ta = p[0];
+	      tb = p[n - 1];
+	      if ((ca == ta) || (ca == tb) || (cb == ta) || (cb == tb))
+		found = true;
+	      }
+	    }
+
+	  if (found)
+	    {
+	    // Here's a line which adjoins this one somehow; add it in
+	    vtkIdType* add_to;
+
+	    if (ca == ta || ca == tb)
+	      {
+	      // This line will go in before our current one; move
+	      // the current one forwards to make room
+	      memmove(out_p + n, out_p, out_n * sizeof(vtkIdType));
+	      add_to = out_p;
+	      }
+	    else
+	      {
+	      // This line will go in after our current one
+	      add_to = out_p + out_n;
+	      }
+
+	    // Add the new line to our current one, either forwards
+	    // or backwards as appropriate
+	    if (ca == ta || cb == tb)
+	      {
+	      for (vtkIdType x = 0; x < n; x++)
+		add_to[x] = p[n - x - 1];
+	      }
+	    else
+	      {
+	      memcpy(add_to, p, n * sizeof(vtkIdType));
+	      }
+
+	    out_n += n;
+	    used[id] = 1;
+
+	    }
+	  else
+	    done_this = true;
+	}
+
+	// We've finished this new line, so add it to the list
+	compressedLines->InsertNextCell(out_n, out_p);
+        }
+
+      delete out_p;
+      }
+
     newLines->Delete();
+    compressedLines->Squeeze();
+    output->SetLines(compressedLines);
+    compressedLines->Delete();
+    delete used;
     vtkDebugMacro (<<"Reduced " << numCells << " cells to " << numLines 
                    << " poly-lines \n\t(Average " << (float)numCells/numLines 
                    << " lines per poly-line, longest poly-line = "