Adaptive method for approximating the integral of a c4d.SplineData (i.e. the area "under" the spline).

c4d_IntegrateSplineData.py

# Copyright (c) 2016  Niklas Rosenstein
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

import c4d
import collections

def IntegrateSplineData(sdata, tolerance=0.01, maxdepth=12, eps=1.0e-6):
  """
  Adaptive method for approximating the area under a :class:`c4d.SplineData`.

  :param sdata: The :class:`c4d.SplineData` object.
  :param tolerance: The accepted variance from the expected
    value of the spline assuming linear interpolation.
  :param maxdepth: The maximum number of subdivisions that should
    be performed to achieve a more precise result.
  """

  knots = [k['vPos'].x for k in sdata.GetKnots()]
  knots.sort()
  if not knots:
    return 0.0

  srange = sdata.GetRange()
  if srange is None:
    srange = {'xmin': 0.0, 'xmax': 1.0, 'ymin': 0.0, 'ymax': 1.0}

  knots.insert(0, srange['xmin'])
  knots.append(srange['xmax'])

  # The tolerance should be consistent with the actual Y range
  # of the spline data. The higher the range, the more inaccurate
  # the result may be.
  tolerance *= srange['ymax'] - srange['ymin']

  # The ranges which we start to check is between all points
  # and the start/end of the spline.
  ranges = collections.deque()
  for i in xrange(1, len(knots)):
    left, right = knots[i-1], knots[i]
    if abs(right - left) < eps: continue
    ranges.append((left, right))

  # We don't actually calculate the integral recursively,
  # we use the "ranges" list as a stack for the ranges
  # that we still have to process.
  area = 0.0
  while ranges:
    xmin, xmax = ranges.popleft()
    xval = (xmax - xmin)
    if xval < eps:
      continue
    xmid = (xmax + xmin) * 0.5
    lval, rval = sdata.GetPoint(xmin).y, sdata.GetPoint(xmax).y

    if len(ranges) <= maxdepth and xval > eps:
      # Check if we have to process a sub-range to get a more
      # accurate result.
      diff = ((lval + rval) * 0.5) - sdata.GetPoint(xmid).y
      if abs(diff) > tolerance:
        ranges.appendleft((xmin, xmid))
        ranges.appendleft((xmid, xmax))
        continue

    # First calculate the area of the rectangular area, then the
    # non-rectangular (eventually negative) area and add them.
    xval = (xmax - xmin)
    area += xval * lval
    area += (rval - lval) * xval * 0.5

  return area