343 lines
12 KiB
PHP
343 lines
12 KiB
PHP
<?php
|
|
|
|
namespace swf2ass;
|
|
|
|
/*
|
|
* Contains adapted code from http://antigrain.com/research/adaptive_bezier/index.html
|
|
* Anti-Grain Geometry (AGG) - Version 2.5
|
|
* A high quality rendering engine for C++
|
|
* Copyright (C) 2002-2006 Maxim Shemanarev
|
|
* Contact: mcseem@antigrain.com
|
|
* mcseemagg@yahoo.com
|
|
* http://antigrain.com
|
|
*
|
|
* AGG is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU General Public License
|
|
* as published by the Free Software Foundation; either version 2
|
|
* of the License, or (at your option) any later version.
|
|
*
|
|
* AGG is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*/
|
|
|
|
class CubicCurveRecord implements Record {
|
|
private const RECURSION_LIMIT = 32;
|
|
private const CURVE_COLLINEARITY_EPSILON = PHP_FLOAT_EPSILON; //1E-30?
|
|
private const CURVE_ANGLE_TOLERANCE_EPSILON = 0.01;
|
|
|
|
public Vector2 $start;
|
|
public Vector2 $control1;
|
|
public Vector2 $control2;
|
|
public Vector2 $anchor;
|
|
|
|
public function __construct(Vector2 $control1, Vector2 $control2, Vector2 $anchor, Vector2 $start) {
|
|
$this->control1 = $control1;
|
|
$this->control2 = $control2;
|
|
$this->anchor = $anchor;
|
|
$this->start = $start;
|
|
}
|
|
|
|
public function getStart(): Vector2 {
|
|
return $this->start;
|
|
}
|
|
|
|
public function getEnd(): Vector2 {
|
|
return $this->anchor;
|
|
}
|
|
|
|
public function reverse(): CubicCurveRecord {
|
|
return new CubicCurveRecord($this->control2, $this->control1, $this->start, $this->anchor);
|
|
}
|
|
|
|
public function applyMatrixTransform(MatrixTransform $transform, bool $applyTranslation = true): CubicCurveRecord {
|
|
return new CubicCurveRecord($transform->applyToVector($this->control1, $applyTranslation), $transform->applyToVector($this->control2, $applyTranslation), $transform->applyToVector($this->anchor, $applyTranslation), $transform->applyToVector($this->start, $applyTranslation));
|
|
}
|
|
|
|
public static function fromQuadraticRecord(QuadraticCurveRecord $q): CubicCurveRecord {
|
|
return new CubicCurveRecord(
|
|
$q->start->add($q->control->multiply(2))->divide(3),
|
|
$q->anchor->add($q->control->multiply(2))->divide(3),
|
|
$q->anchor,
|
|
$q->start
|
|
);
|
|
}
|
|
|
|
/**
|
|
* @return LineRecord[]
|
|
*/
|
|
public function toLineRecords(float $scale = 1.0) : array{
|
|
$points = [];
|
|
$distance_tolerance_square = 0.5 / $scale;
|
|
$distance_tolerance_square *= $distance_tolerance_square;
|
|
|
|
self::recursive_bezier($points, 0.0, 0.0, $distance_tolerance_square, $this->start, $this->control1, $this->control2, $this->anchor, 0);
|
|
$points[] = $this->anchor;
|
|
|
|
$result = [];
|
|
$current = $this->start;
|
|
foreach ($points as $point){
|
|
$result[] = new LineRecord($point, $current);
|
|
$current = $point;
|
|
}
|
|
|
|
return $result;
|
|
}
|
|
|
|
/**
|
|
* @param Vector2[] $points
|
|
* @param float $angle_tolerance
|
|
* @param float $distance_tolerance_square
|
|
* @param Vector2 $v1
|
|
* @param Vector2 $v2
|
|
* @param Vector2 $v3
|
|
* @param int $level
|
|
*/
|
|
private static function recursive_bezier(array &$points, float $cusp_limit, float $angle_tolerance, float $distance_tolerance_square, Vector2 $v1, Vector2 $v2, Vector2 $v3, Vector2 $v4, int $level){
|
|
if($level > self::RECURSION_LIMIT){
|
|
return;
|
|
}
|
|
|
|
// Calculate all the mid-points of the line segments
|
|
//----------------------
|
|
$x12 = ( $v1->x + $v2->x) / 2;
|
|
$y12 = ( $v1->y + $v2->y) / 2;
|
|
$x23 = ( $v2->x + $v3->x) / 2;
|
|
$y23 = ( $v2->y + $v3->y) / 2;
|
|
$x34 = ( $v3->x + $v4->x) / 2;
|
|
$y34 = ( $v3->y + $v4->y) / 2;
|
|
$x123 = ( $x12 + $x23) / 2;
|
|
$y123 = ( $y12 + $y23) / 2;
|
|
$x234 = ( $x23 + $x34) / 2;
|
|
$y234 = ( $y23 + $y34) / 2;
|
|
$x1234 = ( $x123 + $x234) / 2;
|
|
$y1234 = ( $y123 + $y234) / 2;
|
|
|
|
|
|
// Try to approximate the full cubic curve by a single straight line
|
|
//------------------
|
|
$dx = $v4->x- $v1->x;
|
|
$dy = $v4->y- $v1->y;
|
|
|
|
$d2 = abs((( $v2->x - $v4->x) * $dy - ( $v2->y - $v4->y) * $dx));
|
|
$d3 = abs((( $v3->x - $v4->x) * $dy - ( $v3->y - $v4->y) * $dx));
|
|
|
|
|
|
|
|
$da1 = $da2 = $k = null;
|
|
|
|
switch(((int)( $d2 > self::CURVE_COLLINEARITY_EPSILON) << 1) +
|
|
(int)( $d3 > self::CURVE_COLLINEARITY_EPSILON))
|
|
{
|
|
case 0:
|
|
// All collinear OR p1==p4
|
|
//----------------------
|
|
$k = $dx* $dx + $dy* $dy;
|
|
if($k == 0)
|
|
{
|
|
$d2 = $v1->distanceSquare($v2);
|
|
$d3 = $v4->distanceSquare($v3);
|
|
}
|
|
else
|
|
{
|
|
$k = 1 / $k;
|
|
$da1 = $v2->x - $v1->x;
|
|
$da2 = $v2->y - $v1->y;
|
|
$d2 = $k * ( $da1* $dx + $da2* $dy);
|
|
$da1 = $v3->x - $v1->x;
|
|
$da2 = $v3->y - $v1->y;
|
|
$d3 = $k * ( $da1* $dx + $da2* $dy);
|
|
if( $d2 > 0 && $d2 < 1 && $d3 > 0 && $d3 < 1)
|
|
{
|
|
// Simple collinear case, 1---2---3---4
|
|
// We can leave just two endpoints
|
|
return;
|
|
}
|
|
if( $d2 <= 0){
|
|
$d2 = $v2->distanceSquare($v1);
|
|
}
|
|
else if( $d2 >= 1) {
|
|
$d2 = $v2->distanceSquare($v4);
|
|
}
|
|
else {
|
|
$d2 = $v2->distanceSquare($v1->add(new Vector2($d2 * $dx, $d2 * $dy)));
|
|
}
|
|
|
|
if( $d3 <= 0) {
|
|
$d3 = $v3->distanceSquare($v1);
|
|
}
|
|
else if( $d3 >= 1) {
|
|
$d3 = $v3->distanceSquare($v4);
|
|
}
|
|
else {
|
|
$d3 = $v3->distanceSquare($v1->add(new Vector2($d2 * $dx, $d2 * $dy)));
|
|
}
|
|
}
|
|
if( $d2 > $d3)
|
|
{
|
|
if( $d2 < $distance_tolerance_square)
|
|
{
|
|
$points[] = $v2;
|
|
return;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if( $d3 < $distance_tolerance_square)
|
|
{
|
|
$points[] = $v3;
|
|
return;
|
|
}
|
|
}
|
|
break;
|
|
|
|
case 1:
|
|
// p1,p2,p4 are collinear, p3 is significant
|
|
//----------------------
|
|
if( $d3 * $d3 <= $distance_tolerance_square * ( $dx* $dx + $dy* $dy))
|
|
{
|
|
if($angle_tolerance < self::CURVE_ANGLE_TOLERANCE_EPSILON)
|
|
{
|
|
$points[] = new Vector2($x23, $y23);
|
|
return;
|
|
}
|
|
|
|
// Angle Condition
|
|
//----------------------
|
|
$da1 = abs(atan2( $v4->y - $v3->y, $v4->x - $v3->x) - atan2( $v3->y - $v2->y, $v3->x - $v2->x));
|
|
if( $da1 >= M_PI) {
|
|
$da1 = 2 * M_PI - $da1;
|
|
}
|
|
|
|
if( $da1 < $angle_tolerance)
|
|
{
|
|
$points[] = $v2;
|
|
$points[] = $v3;
|
|
return;
|
|
}
|
|
|
|
if($cusp_limit != 0.0)
|
|
{
|
|
if( $da1 > $cusp_limit)
|
|
{
|
|
$points[] = $v3;
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
break;
|
|
|
|
case 2:
|
|
// p1,p3,p4 are collinear, p2 is significant
|
|
//----------------------
|
|
if( $d2 * $d2 <= $distance_tolerance_square * ( $dx* $dx + $dy* $dy))
|
|
{
|
|
if($angle_tolerance < self::CURVE_ANGLE_TOLERANCE_EPSILON)
|
|
{
|
|
$points[] = new Vector2($x23, $y23);
|
|
return;
|
|
}
|
|
|
|
// Angle Condition
|
|
//----------------------
|
|
$da1 = abs(atan2( $v3->y - $v2->y, $v3->x - $v2->x) - atan2( $v2->y - $v1->y, $v2->x - $v1->x));
|
|
if( $da1 >= M_PI) {
|
|
$da1 = 2 * M_PI - $da1;
|
|
}
|
|
|
|
if( $da1 < $angle_tolerance)
|
|
{
|
|
$points[] = $v2;
|
|
$points[] = $v3;
|
|
return;
|
|
}
|
|
|
|
if($cusp_limit != 0.0)
|
|
{
|
|
if( $da1 > $cusp_limit)
|
|
{
|
|
$points[] = $v2;
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
break;
|
|
|
|
case 3:
|
|
// Regular case
|
|
//-----------------
|
|
if(( $d2 + $d3)*( $d2 + $d3) <= $distance_tolerance_square * ( $dx* $dx + $dy* $dy))
|
|
{
|
|
// If the curvature doesn't exceed the distance_tolerance value
|
|
// we tend to finish subdivisions.
|
|
//----------------------
|
|
if($angle_tolerance < self::CURVE_ANGLE_TOLERANCE_EPSILON)
|
|
{
|
|
$points[] = new Vector2($x23, $y23);
|
|
return;
|
|
}
|
|
|
|
// Angle & Cusp Condition
|
|
//----------------------
|
|
$k = atan2( $v3->y - $v2->y, $v3->x - $v2->x);
|
|
$da1 = abs($k - atan2( $v2->y - $v1->y, $v2->x - $v1->x));
|
|
$da2 = abs(atan2( $v4->y - $v3->y, $v4->x - $v3->x) - $k);
|
|
if( $da1 >= M_PI) {
|
|
$da1 = 2 * M_PI - $da1;
|
|
}
|
|
if( $da2 >= M_PI) {
|
|
$da2 = 2 * M_PI - $da2;
|
|
}
|
|
|
|
if( $da1 + $da2 < $angle_tolerance)
|
|
{
|
|
// Finally we can stop the recursion
|
|
//----------------------
|
|
$points[] = new Vector2($x23, $y23);
|
|
return;
|
|
}
|
|
|
|
if($cusp_limit != 0.0)
|
|
{
|
|
if( $da1 > $cusp_limit)
|
|
{
|
|
$points[] = $v2;
|
|
return;
|
|
}
|
|
|
|
if( $da2 > $cusp_limit)
|
|
{
|
|
$points[] = $v3;
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
break;
|
|
}
|
|
|
|
// Continue subdivision
|
|
//----------------------
|
|
self::recursive_bezier( $points, $cusp_limit, $angle_tolerance, $distance_tolerance_square, $v1, new Vector2($x12, $y12), new Vector2($x123, $y123), new Vector2($x1234, $y1234),$level + 1);
|
|
self::recursive_bezier( $points, $cusp_limit, $angle_tolerance, $distance_tolerance_square, new Vector2($x1234, $y1234), new Vector2($x234, $y234), new Vector2($x34, $y34), $v4,$level + 1);
|
|
}
|
|
|
|
/**
|
|
* Finds if Cubic curve is a perfect fit of a Quadratic curve (aka, it was upconverted)
|
|
*
|
|
* @return ?QuadraticCurveRecord
|
|
*/
|
|
public function toSingleQuadraticRecord() : ?QuadraticCurveRecord{
|
|
$control1 = $this->control1->multiply(3)->sub($this->start)->divide(2);
|
|
$control2 = $this->control2->multiply(3)->sub($this->anchor)->divide(2);
|
|
if($control1->equals($control2)){
|
|
return new QuadraticCurveRecord($control1, $this->anchor, $this->start);
|
|
}
|
|
|
|
return null;
|
|
}
|
|
|
|
public function equals(Record $other): bool {
|
|
return $other instanceof $this and $this->start->equals($other->start) and $this->control1->equals($other->control1) and $this->control2->equals($other->control2) and $this->anchor->equals($other->anchor);
|
|
}
|
|
} |