根据前一点的直线距离确定Bézier曲线上的下一个点。

Question

我需要在Bézier曲线上的球之间保持相同的距离。现在我使用曲线上可能的位置的简单迭代，在每次迭代中增加一些步数，直到找到所需的距离，大于或相等的位置。它可以工作，但可以是资源密集型的，当有大量的球.https://codesandbox.io/s/bezier-with-balls-mz37y?file=/src/index.js

​

class TestScene extends Phaser.Scene {
  create() {
    // prettier-ignore
    const curve = new Phaser.Curves.QuadraticBezier(
      [
        55, 310,
        40, 0,
        250, 310
      ]
    );

    const graphicsLayer = this.add.graphics({
      lineStyle: {
        width: 2,
        color: 0x0000ff
      }
    });

    curve.draw(graphicsLayer);

    const balls = this.initBalls(6);

    this.curve = curve;
    this.balls = balls;
  }

  initBalls(quantity) {
    const balls = [];

    for (let i = 0; i < quantity; i++) {
      const ball = this.add.circle(0, 0, 12, 0x00ff00);
      ball.t = 0;

      balls.push(ball);
    }

    return balls;
  }

  calcNextBallT(previous) {
    const ballDiameter = previous.radius * 2;
    const curve = this.curve;
    const curveLen = curve.getLength();
    const previousPos = new Phaser.Math.Vector2(previous);
    const previousT = previous.t;

    const startingT = (1 / curveLen) * ballDiameter + previousT;

    const step = 1 / 1000;

    let nextT = startingT;
    let nextPos;
    let currentDistance = 0;
    while (nextT >= 0 && nextT <= 1) {
      nextPos = curve.getPointAt(nextT);
      currentDistance = previousPos.distance(nextPos);
      if (currentDistance >= ballDiameter) {
        break;
      }
      nextT += step;
    }

    return nextT;
  }

  update() {
    const {
      curve,
      balls
    } = this;
    if (!curve || !balls) {
      return;
    }

    const speed = 1;
    const curveLen = curve.getLength();
    const step = (1 / curveLen) * speed;

    balls.forEach((ball, index, array) => {
      let nextT = ball.t;

      if (index === 0) {
        nextT += step;
        if (nextT > 1) {
          nextT = 0;
        }
      } else {
        const previous = array[index - 1];
        nextT = this.calcNextBallT(previous);
      }

      ball.t = nextT;
      ball.copyPosition(curve.getPointAt(nextT));
    });
  }
}

const game = new Phaser.Game({
  width: 320,
  height: 320,
  powerPreference: 'low-power',
  audio: {
    noAudio: true
  },
  scene: [TestScene]
});

<script src="https://unpkg.com/phaser@3.55.2/dist/phaser.min.js"></script>

​

我想也许有一个数学或算法的解决方案。就像找到一个更大的圆与曲线的交点一样，但据我所知，这是不可能的。

是否有更好的方法来确定Bézier曲线上的下一个点，根据从前一点到的直线距离？

更新1:一种使用二进制搜索的解决方案，如@MBo所建议的那样，具有良好的稳定性，平均迭代次数为5-10次，即使曲线和球大小不同。https://codesandbox.io/s/bezier-with-balls-binary-search-s4foq?file=/src/index.js

​

class TestScene extends Phaser.Scene {
  init() {
    this.input.on('drag', (pointer, gameObject, dragX, dragY) => {
      gameObject.setPosition(dragX, dragY);
    });

    this.iters = [];
  }

  create() {
    // prettier-ignore
    const p0 = this.add.circle(55, 310, 4, 0xffff00),
          p1 = this.add.circle(40, 5, 4, 0xffff00),
          p2 = this.add.circle(250, 310, 4, 0xffff00);

    const curve = new Phaser.Curves.QuadraticBezier(p0, p1, p2);

    const graphicsLayer = this.add.graphics({
      lineStyle: {
        width: 2,
        color: 0x0000ff
      }
    });
    curve.draw(graphicsLayer);

    const curveDragHandler = () => {
      curve.updateArcLengths();
      graphicsLayer.clear();
      curve.draw(graphicsLayer);
    };

    [p0, p1, p2].forEach((p) => {
      p.setDepth(10).setInteractive();
      this.input.setDraggable(p);
      p.on('drag', curveDragHandler);
    });

    const balls = this.initBalls(3, 50);

    const text = this.add.text(0, 0, '', {
      color: 'yellow'
    });

    this.curve = curve;
    this.balls = balls;
    this.text = text;
  }

  initBalls(quantity, diameter) {
    const radius = diameter / 2;
    const balls = [];

    for (let i = 0; i < quantity; i++) {
      const ball = this.add.circle(0, 0, radius, 0x00ff00);
      ball.t = 0;

      balls.push(ball);
    }

    return balls;
  }

  calcNextBallT(previous) {
    const ballDiameter = previous.radius * 2;
    const curve = this.curve;
    const previousPos = new Phaser.Math.Vector2(previous);
    const previousT = previous.t;

    let nextT = 1;
    let lowT = previousT;
    let highT = 1;
    let iter = 1;
    const skip = previousPos.distance(curve.getEndPoint()) <= ballDiameter;
    while (lowT <= highT && !skip) {
      nextT = lowT + (highT - lowT) / 2;
      const nextPos = curve.getPointAt(nextT);
      const currentDistance = previousPos.distance(nextPos);

      if (fuzzySame(currentDistance, ballDiameter)) {
        break;
      }

      if (currentDistance > ballDiameter) {
        highT = nextT;
      } else {
        lowT = nextT;
      }

      iter++;
    }

    if (!skip) {
      this.iters.push(iter);
    }

    return nextT;
  }

  update() {
    const {
      curve,
      balls
    } = this;
    if (!curve || !balls) {
      return;
    }

    const speed = 1;
    const curveLen = curve.getLength();
    const step = (1 / curveLen) * speed;

    balls.forEach((ball, index, array) => {
      let nextT = ball.t;

      if (index === 0) {
        nextT += step;
        if (nextT > 1) {
          const average = findAverage(this.iters).toFixed(2);
          const maximum = findMaximum(this.iters);
          this.text.setText(`Average: ${average}\nMaximum: ${maximum}`);
          this.iters = [];
          nextT = 0;
        }
      } else {
        const previous = array[index - 1];
        nextT = this.calcNextBallT(previous);
      }

      ball.t = nextT;
      ball.copyPosition(curve.getPointAt(nextT));
    });
  }
}

const fuzzySame = (num1, num2) => {
  const tolerance = 0.2;
  return num1 >= num2 - tolerance && num1 <= num2 + tolerance;
};

const findAverage = (array) => {
  const len = array.length;
  let total = 0;
  array.forEach((num) => (total += num));
  return total / len;
};

const findMaximum = (array) => {
  return [...array].sort((a, b) => b - a)[0];
};

const game = new Phaser.Game({
  width: 320,
  height: 320,
  powerPreference: 'low-power',
  audio: {
    noAudio: true
  },
  scene: [TestScene]
});

<script src="https://unpkg.com/phaser@3.55.2/dist/phaser.min.js"></script>

​

Answer 1

与直接迭代不同，在t范围内使用二进制搜索。

数学解需要解6度方程(对于三次曲线)没有封闭公式，所以需要使用数值方法(再次迭代)。