Class SubdivisionIterator

java.lang.Object
org.bzdev.geom.SubdivisionIterator
All Implemented Interfaces:
SurfaceIterator

public class SubdivisionIterator extends Object implements SurfaceIterator
Surface iterator for subdividing a surface's segments. Segments of a surface or other implementations of Shape3D will be subdivided into quarters. This is repeated recursively until a limit is reached.

When the limit is 0, there are no subdivisions. When the limit is 1, there are 4 subdivisions, and when the limit is 2, there are 16 subdivisions.

Quartering in this way is useful for 3D printing: the STL format requires that triangles meet at vertices and subdividing in this way uniformly ensures that condition will be met.

  • Constructor Details

    • SubdivisionIterator

      public SubdivisionIterator(SurfaceIterator src, int limit)
      Constructor.
      Parameters:
      src - the surface iterator for a Shape3D to subdivide
      limit - the recursion limit: the number of times each segment of a Shape3D will split into quarters
    • SubdivisionIterator

      public SubdivisionIterator(SurfaceIterator src, Transform3D transform, int limit)
      Constructor providing a transform.
      Parameters:
      src - the surface iterator for a Shape3D to subdivide
      transform - the transform to apply to each of the new segments
      limit - the recursion limit: the number of times each segment of a Shape3D will split into quarters
  • Method Details

    • isOriented

      public boolean isOriented()
      Description copied from interface: SurfaceIterator
      Determine if a segment is from an oriented surface.
      Specified by:
      isOriented in interface SurfaceIterator
      Returns:
      true if a segment is from an oriented surface; false otherwise
    • getRecursionLimit

      public int getRecursionLimit()
      Get the recursion limit.
      Returns:
      the recursion limit
    • currentSegment

      public int currentSegment(double[] coords)
      Description copied from interface: SurfaceIterator
      Get the current segment using double-precision values. The length of the argument array should be at least 48. The number of elements used depends on the mode. The format for the argument array is given by
      Specified by:
      currentSegment in interface SurfaceIterator
      Parameters:
      coords - an array to store the values
      Returns:
      one of the constants SurfaceIterator.CUBIC_PATCH, SurfaceIterator.CUBIC_TRIANGLE, SurfaceIterator.PLANAR_TRIANGLE or SurfaceIterator.CUBIC_VERTEX
    • currentSegment

      public int currentSegment(float[] coords)
      Description copied from interface: SurfaceIterator
      Get the current segment using single-precision values. The length of the argument array should be at least 48. The format for the argument array is given by
      Specified by:
      currentSegment in interface SurfaceIterator
      Parameters:
      coords - an array to store the values
      Returns:
      one of the constants SurfaceIterator.CUBIC_PATCH, SurfaceIterator.CUBIC_TRIANGLE or SurfaceIterator.PLANAR_TRIANGLE or SurfaceIterator.CUBIC_VERTEX
    • currentTag

      public Object currentTag()
      Description copied from interface: SurfaceIterator
      Return the tag for the current segment. A tag is typically a stack trace indicating where a patch was created.
      Specified by:
      currentTag in interface SurfaceIterator
      Returns:
      the segment's tag; null if there is none
    • currentColor

      public Color currentColor()
      Description copied from interface: SurfaceIterator
      Return the color for the current segment.
      Specified by:
      currentColor in interface SurfaceIterator
      Returns:
      the segment's color; null if none was defined
    • isDone

      public boolean isDone()
      Description copied from interface: SurfaceIterator
      Return true if iteration is complete.
      Specified by:
      isDone in interface SurfaceIterator
      Returns:
      true if iteration is complete; false otherwise
    • next

      public void next()
      Description copied from interface: SurfaceIterator
      Move to the next segment.
      Specified by:
      next in interface SurfaceIterator
    • midcoord

      public static double midcoord(double x0, double x3)
      Find the value for the midpoint between two points given an X, Y, or Z coordinate for each point. A straight line between the two points is 'promoted' to the corresponding cubic Bézier curve, and that curve is subdivided, splitting it at the point where the path parameter has the value 0.5.

      The result, given exact arithmetic, is (x0 + x3) / 2. The actual value returned may be slightly different because of the use of double-precision arithmetical operations, but will match the value used if an edge of a cubic patch is a straight line created by using Path3D.setupCubic(double,double,double,double,double,double) and that edge is subdivided at a point where the path parameter is 0.5. In addition, the value is computed with x0 and x3 exchanged and the two are averaged so that the returned value is independent of the line-segment direction.

      Parameters:
      x0 - the first coordinates (X, Y, or Z, matching the choice for x3)
      x3 - the second coordinate (X, Y, or Z, matching the choice for x0)
      Returns:
      the midpoint between x0 and x3
    • splitCubicBezierCurve

      public static double[][] splitCubicBezierCurve(double[] curve)
      Split a cubic Bézier curve into two parts at the midpoint of the path parameter.

      This method uses the same algorithm as the one used to subdivide a cubic patch, so that the end points and intermediate control points in both cases will match exactly. The class Model3D uses this method to subdivide a cubic vertex for tessellation so that floating-point round-off errors do not result in an unprintable object.

      Parameters:
      curve - the four control points making up a cubic Bé curve
      Returns:
      an array of vectors, each of length 12, contaiing the countrol points for the left and right partiions respectively
    • splitCubicBezierCurve

      public static double[][] splitCubicBezierCurve(double[] curve, int offset)
      Split a cubic Bézier curve into two parts at the midpoint of the path parameter, given an offset.

      This method uses the same algorithm as the one used to subdivide a cubic patch, so that the end points and intermediate control points in both cases will match exactly. The class Model3D uses this method to subdivide a cubic vertex for tessellation so that floating-point round-off errors do not result in an unprintable object.

      Parameters:
      curve - the four control points making up a cubic Bé curve
      offset - the offset into the curve array at which the cubic Bé curve starts.
      Returns:
      an array of vectors, each of length 12, contaiing the countrol points for the left and right partiions respectively
    • permuteCubicTriangle

      public static void permuteCubicTriangle(double[] coords, int offset)
      Permute coordinates so that the longest edge is bisected when splitCubicTriangle(double[],int,double[],int,double[],int) is called.

      If the u=0 edge is the longest one, the coords array is not changed. Otherwise the control points are permuted, excluding P111, whose position never changes. The final order for the control points in the coord array is

      • u=0: P003, P012, P021, P030, P102, P111, P120, P201 P210, P300.
      • v=0: P300, P201, P102, P003, P210, P111, P012, P120, P021, P030.
      • w=0: P030, P120, P210, P300, P021, P111, P201, P012, P102, P003.
      The mapping between the original control points and their offsets into the array is shown in the following table:
       
      P0030 P012 3 P021 6 P030 9 P102 12
      P111 15 P120 18 P201 21 P210 24 P30027
      Parameters:
      coords - the coordinate array
      offset - the offest into coords at which the cubic-triangle coordinates start
    • splitCubicTriangle

      public static void splitCubicTriangle(double[] coords, int offset, double[] coords1, int offset1, double[] coords2, int offset2)
      Split a cubic Bézier triangle into two triangles

      The coordinates are provided as X, Y, Z triplets in the order specified by SurfaceIterator. Midpoints of the edges are computed using splitCubicBezierCurve(double[],int) so that there will be a perfect match with cubic Bézier patches and planar triangles that may be split.

      The new triangles are stored in the argument arrays coord1 and coord2, starting at their respective offsets. The coord array with its offset, and 30 values, may overlap coord1 with its offset or coord2 with its offset.

      The algorithm used is similar to that described in the Wikipedia article for cubic Bézier triangles, but with the vertices reordered so calling this method on each of the triangles it returns will result in the remaining two edges from the original triangle being split.

      Parameters:
      coords - the coordinates of the triangle to split
      offset - the offset into the coords array where the coordinate data starts
      coords1 - the coordinates of the first split triangle
      offset1 - the offset into the coords1 array where the coordinate data starts
      coords2 - the coordinates of the second split triangle
      offset2 - the offset into the coords2 array where the coordinate data starts
    • getLeftPatch

      public static void getLeftPatch(double[] result, int offset, double[] coords, int coffset) throws IllegalArgumentException
      Get the left subpatch of a Bézier patch. The array arguments must be long enough to store 48 entries starting from their offsets. Left to right is in the direction of an increasing U parameter (the first parameter).
      Parameters:
      result - the coordinate array for a new Bézier patch that will subdivide an existing patch
      offset - the offset into the result array for the initial entry
      coords - the coordinate array for an existing patch.
      coffset - the offset for the first entry in the coords array
      Throws:
      IllegalArgumentException - an array was null, an offset was illegal, or an array length was too short
    • getBottomPatch

      public static void getBottomPatch(double[] result, int offset, double[] coords, int coffset) throws IllegalArgumentException
      Get the bottom subpatch of a Bézier patch. The array arguments must be long enough to store 48 entries starting from their offsets. Bottom to Top is in the direction of an increasing V parameter (the second parameter).
      Parameters:
      result - the coordinate array for a new Bézier patch that will subdivide an existing patch
      offset - the offset into the result array for the initial entry
      coords - the coordinate array for an existing patch.
      coffset - the offset for the first entry in the coords array
      Throws:
      IllegalArgumentException - an array was null, an offest was illegal, or an array length was too short
    • getTopPatch

      public static void getTopPatch(double[] result, int offset, double[] coords, int coffset) throws IllegalArgumentException
      Get the top subpatch of a Bézier patch. The array arguments must be long enough to store 48 entries starting from their offsets. Bottom to Top is in the direction of an increasing V parameter (the second parameter).
      Parameters:
      result - the coordinate array for a new Bézier patch that will subdivide an existing patch
      offset - the offset into the result array for the initial entry
      coords - the coordinate array for an existing patch.
      coffset - the offset for the first entry in the coords array
      Throws:
      IllegalArgumentException - an array was null, an offest was illegal, or an array length was too short
    • getRightPatch

      public static void getRightPatch(double[] result, int offset, double[] coords, int coffset) throws IllegalArgumentException
      Get the right subpatch of a Bézier patch. The array arguments must be long enough to store 48 entries starting from their offsets. Left to right is in the direction of an increasing U parameter (the first parameter).
      Parameters:
      result - the coordinate array for a new Bézier patch that will subdivide an existing patch
      offset - the offset into the result array for the initial entry
      coords - the coordinate array for an existing patch.
      coffset - the offset for the first entry in the coords array
      Throws:
      IllegalArgumentException - an array was null, an offest was illegal, or an array length was too short