VTK/Closed Surface Clipping

From KitwarePublic
< VTK
Revision as of 09:32, 12 April 2010 by Dgobbi (talk | contribs) (→‎Problem)
Jump to navigationJump to search
A clipped surface with generation of color scalars.

The main goal of this project is to make it possible to clip a surface, and then create a "cap" polygon (or polygons) that fill in the area that is enclosed by all the new edges that were created by the clipping. In other words, the goal is to close the surface after the clipping has been performed. For this purpose, a new filter called vtkClipClosedSurface has been created.

This class was contributed to VTK by David Gobbi on March 30, 2010.

Features

A skin isosurface with a reversed bone isosurface.

The vtkClipClosedSurface filter has the following features:

  • A vtkPlaneCollection is used to set the clip region (arbitrary implicit functions are not allowed).
  • When given a closed surface as input, it will produce a closed surface as output.
  • When given an open surface as input, it will create a closed surface if it is supplied with a clipping plane that clips away all open edges.
  • The input surface can be concave, but cannot self-intersect.
  • The input can have multiple surfaces, where any surfaces that are inside-out will be treated as holes within larger, enclosing surfaces. The inner and outer surfaces must not intersect each other.
  • If an input surface is inside-out, but does not have a larger surface enclosing it, then the cut faces will be left open.

Note: inside-out surface can be created by applying vtkReverseSense to a regular surface.

Caveats

The newly-created clip surfaces have the following limitations:

  • If the contours at the clip plane are not closed, or if they don't have simple topology, then an incorrect surface might be generated.
  • The triangles that are generated are often very narrow. The code does not attempt to generate high-quality triangles.
  • This filter ignores vtkVertex cells, and the output will contain no verts.
  • Similarly, input lines will be discarded unless the GenerateOutline option is on.

Options

Clipping a cube and displaying the outline only.
  • GenerateFaces - On by default. If turned off, the output will have no polygons, which useful if only the outlines are desired.
  • GenerateOutline - Off by default. If turned on, contours will be generated where the planes intersect the surface.
  • GenerateColorScalars - Off by default. Generate color scalars for the output, see below for more.

The GenerateColorScalars option creates color cell scalars so that the cut surfaces are displayed with a different color than the rest of the surface. Cell scalars are used instead of point scalars because the use of point scalars would require point duplication where the cut surfaces meet the rest of the surface. If GenerateOutline is on, then the lines will be the same colors as the faces. If you need the lines to be a different color, then you could use two instances of vtkClipClosedSurface: one to generates faces, and another to generates outlines.

If GenerateColorScalars is on, then three colors can be set:

  • ClipColor for the clip surfaces
  • BaseColor for the rest of the surface
  • ActivePlaneColor to color one clip surface in a different color

The purpose of ActivePlaneColor is to color one cut plane differently, e.g. the plane that the user is interacting with. The ActivePlaneId can be set to specify which of the cut planes is the active plane.

The BaseColor will be ignored if the input already has 3-component color cell scalars. If this is the case, the original scalars will be used instead of BaseColor. This is useful if you want to chain two vtkClipClosedSurface filters together, or if you want to use vtkClipClosedSurface on the output of vtkOutlineSource or vtkVolumeOutlineSource.

Note that many VTK filters that create new cells (e.g. vtkStripper) will erase the cell scalars. So if you use GenerateCellScalars, you should avoid using vtkStripper to post-process the data.

Algorithm

Wireframe rendering, to show triangle quality.

This filter uses many of the functions that are built into vtkCell and its subclasses, but it also has several internal functions for polygon manipulation. An overall description of what is done for each of the clipping planes is as follows:

  1. Clip scalars are generated for all points.
  2. The data is clipped and contoured, using the clip scalars.
  3. The contours are used to generate the cut faces.
  4. The process is repeated for the next cut plane

Generation of the cut faces from the cut contours is a multi-step process:

  1. The contour lines are joined end-to-end to form polygons.
  2. If the polygons self-intersect, they are split at the intersection points.
  3. Any polygon points that aren't at a corner of the polygon are removed.
  4. The sense of the polygons is checked against the cut plane normal to find out which polygons are holes.
  5. Two cuts are made between each hole and its containing polygon in order to generate two simple polygons.
  6. The ear-cut triangulation method of vtkPolygon is used to triangulate the polygons.
  7. Some of the new triangles are subdivided in order to add back the points that were removed in step 3.

Future Work

Guaranteeing a watertight output

Problem

The vtkFeatureEdges filter can check a polydata to see if it is watertight: a watertight surface will have no boundary edges and no non-manifold edges. The vtkClipClosedSurface filter should guarantee in the strictest sense that it will produce a watertight surface if given a watertight surface as an input. Unfortunately, VTK's low-level clipping and triangulation code makes this difficult to achieve.

  1. VTK clipping, as implemented in the vtkCell subclasses, requires the use of a point locator (usually vtkMergePoints) that merges coincident points. Unfortunately, point merging can change connectivity and therefore change topology. Specifically, a manifold input can, after point merging, become non-manifold.
  2. VTK triangulation, as implemented in vtkPolygon, will sometimes leave holes rather than create degenerate or nearly-degenerate triangles. So if the clipping produces polygons that (a) have any 180 degree vertices or (b) have vertices that are very close to each other, or vertices that are very close to a non-adjacent edge, then the output will have free edges.

Solution

Unfortunately, the solution is to write clipping and triangulation code that is specific to this filter, rather than use the clipping/triangulation facilities already provided by VTK.

For the triangulation issue, if we use a tolerance for creating new points along clipped edges, then the number of free edges in the output can be reduced. By this I mean that when an edge is clipped, if the new point is within epsilon of either of the edge end points, then that endpoint will be used instead of the new point. This helps to avoid the creation of nearly-degenerate polygons, which in turn keeps the VTK triangulation from leaving micro-thin holes in the output.

Reducing the number of triangles produced

Problem

This class uses the clipping/contouring methods in the vtkCell subclasses, which triangulate polys while clipping or contouring them. This produces many more points and cells than are actually needed to describe the geometry. Also, when multiple cut planes are used, these cells can be clipped multiple times, causing a proliferation of small, sharp triangles.

Solution

There are two parts to the solution:

  1. Write new clipping/contouring code that doesn't triangulate the polys while clipping and contouring them. (DONE)
  2. Improve the triangulation of the cap polygons, or even go as far as not triangulating them at all.

The ideal solution is to write clipping/contouring code that can deal with concave polygons. Then, in RequestData where the filter applies each clipping plane in sequence, the code can deal directly with the concave polygons produced by the previous clip-plane, and triangulation of the polygons can be deferred to the very end of RequestData. The result will be that the final output will have the minimum possible number of triangles.

There is another good reason for writing specialized clipping/contouring code: it allows the orientation of the contours to be correctly set from the orientation of the clipped polygons. This will eliminate the need to do an orientation check while creating the cap polygons, and will further guarantee that correct cap polygons are created. For instance, right now vtkClipClosedSurface will create incorrectly-oriented cap polygons if its input is an inside-out surface. But if the orientation of the cap polygons is set from the orientation of the original polygons (instead of being set according to the clip-plane normal like they are now), then cap polygons will be correctly generated even for inside-out surfaces.

Handling non-closed inputs

Problem

The algorithm for creating new polygons assumes that all contours are closed. Currently, when a non-closed contour is found, it's two ends are connected in order to close it. This produces some odd results when the filter is given non-closed inputs.

Solution

There are three possible solutions:

  1. Generate an error when non-closed contours are found, but otherwise continue with the current behaviour.
  2. Throw out these non-closed contours. Probably not a good idea.
  3. Add heuristics for optimally joining non-closed contours. (DONE)

The following heuristics have been added for joining the contours:

  1. When joining contours, the new edge must be on the hull of the total point set of all contours.
  2. The new edge must be of the correct sense, i.e. counterclockwise around the hull.
  3. If there are multiple candidate new edges for a loose end, the shortest is chosen.
  4. If there are no new edge candidates for a loose end, then that contour is removed.

Only joins along the hull are permitted, since it is assumed that the loose ends are the result of contours that intersect the bounds of the data set.