Кривые безье третьего порядка.

incoob · 15.04.2008, 09:41

Кто нибудь сталкивался с проблемой аппроксимации кривых безье третьего порядка кривыми безье второго порядка с минимальными погрешностями?

etc · 15.04.2008, 10:36

http://bezier.ru/

Iv · 16.04.2008, 16:34

К сожалению, на bezier.ru нет готового решения на AS3.
Вот прекрасная статья на эту тему: Адаптивное разбиение кривых Безье
Если потребуется помощь, обращайся, рад буду помочь.

Iv · 16.04.2008, 16:51

Да, и еще добавлю: если делается собственный редактор, а не используются чужие данные, то вполне можно использовать псевдо кубические кривые - две гладко состыкованные квадратичные кривые.
Пример имеется, жми цифорку 4 увидишь пример.
На странице проекта http://code.google.com/p/bezier/ ты можешь качнуть классы через SVN, там есть эта демка.

incoob · 21.04.2008, 11:34

Спасибо за статью.

undefined · 25.04.2008, 13:31

внесу свои 5 копеек
Поверхности безье, писалось на AS2. Сейчас на работе исходника нету, но если надо - могу выложить как домой приду.

†‡Paladin‡† · 25.04.2008, 19:00

Ну и мои 5 копеек.

Код:

package {
	
	import flash.display.*;
	import flash.geom.*;	
	
	/**
	* Based on Math2 class writed by Helen Triolo, with inclusions from Robert Penner, Tim Groleau
	* @author Ilya (WYPaladin) Plotnikov
	* 
	*/
	public class QubicBezier {	
		/**
		* @method getQuadBez_RP (Penner)
		* @description  Approximates a cubic bezier with as many quadratic bezier segments (n) as required 
		*			to achieve a specified tolerance
		* @param p1 (Object) endpoint
		* @param c1 (Object) 1st control point
		* @param c2 (Object) 2nd control point
		* @param p2 (Object) endpoint
		* @param k: tolerance (low number = most accurate result)
		* @param qcurves (Array) will contain array of quadratic bezier curves, each element containing
		*		p1x, p1y, cx, cy, p2x, p2y
		*/
		public function getQuadBez_RP(p1:Point, c1:Point, c2:Point, p2:Point, k:Number, qcurves:Array):void {
				// if something is wrong, abort function
				try {
					// find intersection between bezier arms
					var s:Point = intersect2Lines(p1, c1, c2, p2);
					// find distance between the midpoints
					var dx:Number = (p1.x + p2.x + s.x * 4 - (c1.x + c2.x) * 3) * .125;
					var dy:Number = (p1.y + p2.y + s.y * 4 - (c1.y + c2.y) * 3) * .125;
				} catch (e:Error) {
					return;
				}
				
				// split curve if the quadratic isn't close enough
				if (dx*dx + dy*dy > k) {
					var halves:Object = bezierSplit(p1.x, p1.y, c1.x, c1.y, c2.x, c2.y, p2.x, p2.y);
					var b0:Object = halves.b0; 
					var b1:Object = halves.b1;	
					// recursive call to subdivide curve
					getQuadBez_RP(p1, b0.c1, b0.c2, b0.p2, k, qcurves);
					getQuadBez_RP(b1.p1, b1.c1, b1.c2, p2, k, qcurves);
				} else {
					// end recursion by saving points
					qcurves.push({p1x:p1.x, p1y:p1.y, cx:s.x, cy:s.y, p2x:p2.x, p2y:p2.y});
				}
			}

		/**
		* @method intersect2Lines (Penner)
		* @description Returns the point of intersection between two lines
		* @param p1, p2 (Objects) points on line 1
		* @param p3, p4 (Objects) points on line 2
		* @returns Object (point of intersection)
		*/
	
		private function intersect2Lines (p1:Point, p2:Point, p3:Point, p4:Point):Point {
			var x1:Number = p1.x; 
			var y1:Number = p1.y;
			var x4:Number = p4.x; 
			var y4:Number = p4.y;
		    var dx1:Number = p2.x - x1;
		    var dx2:Number = p3.x - x4;
	
		   if (!(dx1 || dx2)) return undefined;
		   var m1:Number = (p2.y - y1) / dx1;
		   var m2:Number = (p3.y - y4) / dx2;
		   if (!dx1) {
		      return new Point(x1, m2 * (x1 - x4) + y4);
		   } else if (!dx2) {
		      return new Point(x4, m1 * (x4 - x1) + y1);
		   }
		   var xInt:Number = (-m2 * x4 + y4 + m1 * x1 - y1) / (m1 - m2);
		   var yInt:Number = m1 * (xInt - x1) + y1;
		   return new Point(xInt, yInt);
		}	
				 
		/**
		* @method bezierSplit (Penner)
		* @description    Divides a cubic bezier curve into two halves (each also cubic beziers)
		* @param p1x (Number) pixels, endpoint 1
		* @param p1y (Number) pixels
		* @param c1x (Number) pixels, control point 1
		* @param c1y (Number) pixels
		* @param c2x (Number) pixels, control point 2
		* @param c2y (Number) pixels
		* @param p2x (Number) pixels, endpoint 2
		* @param p2y (Number) pixels
		* @returns Object (object with two cubic bezier definitions, b0 and b1)
		*/

		private function bezierSplit(p1x:Number, p1y:Number, 
										   c1x:Number, c1y:Number, 
										   c2x:Number, c2y:Number, 
										   p2x:Number, p2y:Number):Object {
										   	
			var p1:Point = new Point(p1x, p1y);
			var p2:Point = new Point(p2x, p2y);
			var p3:Point = new Point(c1x, c1y);
			var p4:Point = new Point(c2x, c2y);
			
		    var p01:Point = getMiddle(p1, p3);
		    var p12:Point = getMiddle(p3, p4);
		    var p23:Point = getMiddle(p4, p2);
		    var p02:Point = getMiddle(p01, p12);
		    var p13:Point = getMiddle(p12, p23);
		    var p03:Point = getMiddle(p02, p13);
	
			return { b0:{p1:p1, c1:p01, c2:p02, p2:p03}, b1:{p1:p03, c1:p13, c2:p23, p2:p2} };
		}		
		 
		/**
		* @method getMiddle
		* @description Returns the midpoint (x/y) of a line segment from p1x/p1y to p2x/p2y
		* @param p1x (Number) pixels
		* @param p1y (Number) pixels
		* @param p2x (Number) pixels
		* @param p2y (Number) pixels
		* @returns Object (midpoint)
		*/		
		private function getMiddle(pA:Point, pB:Point):Point {
		 	return new Point((pA.x+pB.x)/2, (pA.y+pB.y)/2);
		 }	
	}	
}

incoob · 08.09.2008, 19:28

По теме:

Адобовцы решили не изобретать велосипед

Код:

////////////////////////////////////////////////////////////////////////////////
//
//  ADOBE SYSTEMS INCORPORATED
//  Copyright 2003-2006 Adobe Systems Incorporated
//  All Rights Reserved.
//
//  NOTICE: Adobe permits you to use, modify, and distribute this file
//  in accordance with the terms of the license agreement accompanying it.
//
////////////////////////////////////////////////////////////////////////////////

package flex.graphics
{

import flash.display.Graphics;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.events.EventDispatcher;

/**
 *  The CubicBezierSegment draws a cubic bezier curve from the current pen position 
 *  to x, y.  The control1X and control1Y properties specify the first control point; 
 *  the control2X and control2Y properties specify the second control point.
 *
 *  See http://en.wikipedia.org/wiki/B%C3%A9zier_curve#Cubic_B.C3.A9zier_curves for
 *  details about cubic bezier curves.
 *
 *  Cubic bezier curves are not natively supported in the flash player. This class does
 *  an approximation based on the fixed midpoint algorithm and uses 4 quadratic curves
 *  to simulate a cubic curve.
 *
 *  Details on the fixed midpoint algorithm can be found here:
 *  http://timotheegroleau.com/Flash/articles/cubic_bezier_in_flash.htm 
 *  (scroll down to the last section before the Conclusion)
 */
public class CubicBezierSegment extends PathSegment
{
	include "../core/Version.as";

    //--------------------------------------------------------------------------
    //
    //  Constructor
    //
    //--------------------------------------------------------------------------

    /**
     *  Constructor.
     */
	public function CubicBezierSegment(
				control1X:Number = 0, control1Y:Number = 0,
				control2X:Number = 0, control2Y:Number = 0,
				x:Number = 0, y:Number = 0)
	{
		super(x, y);
		
		_control1X = control1X;
		_control1Y = control1Y;
		_control2X = control2X;
		_control2Y = control2Y;
	}   


    //--------------------------------------------------------------------------
    //
    //  Variables
    //
    //--------------------------------------------------------------------------
	
	private var qPts:QuadraticPoints;
	
    //--------------------------------------------------------------------------
    //
    //  Properties
    //
    //--------------------------------------------------------------------------
	
	//----------------------------------
	//  control1X
	//----------------------------------

	private var _control1X:Number = 0;
	
	[Bindable("propertyChange")]
    [Inspectable(category="General")]
    
	/**
	 *  The first control point x position.
	 */
	public function get control1X():Number
	{
		return _control1X;
	}
	
	public function set control1X(value:Number):void
	{
		var oldValue:Number = _control1X;
		
		if (value != oldValue)
		{
			_control1X = value;
			dispatchSegmentChangedEvent("control1X", oldValue, value);
		}
	}
	
	//----------------------------------
	//  control1Y
	//----------------------------------

	private var _control1Y:Number = 0;
	
	[Bindable("propertyChange")]
    [Inspectable(category="General")]

	/**
	 *  The first control point y position.
	 */
	public function get control1Y():Number
	{
		return _control1Y;
	}
	
	public function set control1Y(value:Number):void
	{
		var oldValue:Number = _control1Y;
		
		if (value != oldValue)
		{
			_control1Y = value;
			dispatchSegmentChangedEvent("control1Y", oldValue, value);
		}
	}
	
	//----------------------------------
	//  control2X
	//----------------------------------

	private var _control2X:Number = 0;
	
	[Bindable("propertyChange")]
    [Inspectable(category="General")]

	/**
	 *  The second control point x position.
	 */
	public function get control2X():Number
	{
		return _control2X;
	}
	
	public function set control2X(value:Number):void
	{
		var oldValue:Number = _control2X;
		
		if (value != oldValue)
		{
			_control2X = value;
			dispatchSegmentChangedEvent("control2X", oldValue, value);
		}
	}
	
	//----------------------------------
	//  control2Y
	//----------------------------------

	private var _control2Y:Number = 0;
	
	[Bindable("propertyChange")]
    [Inspectable(category="General")]

	/**
	 *  The second control point y position.
	 */
	public function get control2Y():Number
	{
		return _control2Y;
	}
	
	public function set control2Y(value:Number):void
	{
		var oldValue:Number = _control2Y;
		
		if (value != oldValue)
		{
			_control2Y = value;
			dispatchSegmentChangedEvent("control2Y", oldValue, value);
		}
	}
	
    //--------------------------------------------------------------------------
    //
    //  Methods
    //
    //--------------------------------------------------------------------------
	
    /**
     *  Draws the segment.
     *
     *  @param g The graphics context where the segment is drawn.
     */
	override public function draw(g:Graphics, prev:PathSegment):void
	{
		if (!qPts)
			calculateQuadraticPoints(prev);
				    
	   	if (qPts)
	   	{
		    g.curveTo(qPts.control1.x, qPts.control1.y, qPts.anchor1.x, qPts.anchor1.y);
		    g.curveTo(qPts.control2.x, qPts.control2.y, qPts.anchor2.x, qPts.anchor2.y);
		    g.curveTo(qPts.control3.x, qPts.control3.y, qPts.anchor3.x, qPts.anchor3.y);
		    g.curveTo(qPts.control4.x, qPts.control4.y, qPts.anchor4.x, qPts.anchor4.y);
	    }
	}

	
	/**
	 *  @private
	 */
	override protected function notifySegmentChanged():void
	{
		super.notifySegmentChanged();
		
		// Need to recalculate our quadratic points
		qPts = null;
	}
	
	/** 
	 *  @private
	 *  Tim Groleau's method to approximate a cubic bezier with 4 quadratic beziers, 
	 *  with endpoint and control point of each saved. 
	 */
	private function calculateQuadraticPoints(prev:PathSegment):void
	{
		var p1:Point = new Point(prev ? prev.x : 0, prev ? prev.y : 0);
		var p2:Point = new Point(x, y);
		var c1:Point = new Point(control1X, control1Y);		
		var c2:Point = new Point(control2X, control2Y);
			
	    // calculates the useful base points
	    var PA:Point = Point.interpolate(c1, p1, 3/4);
	    var PB:Point = Point.interpolate(c2, p2, 3/4);
	
	    // get 1/16 of the [p2, p1] segment
	    var dx:Number = (p2.x - p1.x) / 16;
	    var dy:Number = (p2.y - p1.y) / 16;

		qPts = new QuadraticPoints;
		
	    // calculates control point 1
	    qPts.control1 = Point.interpolate(c1, p1, 3/8);
	
	    // calculates control point 2
	    qPts.control2 = Point.interpolate(PB, PA, 3/8);
	    qPts.control2.x -= dx;
	    qPts.control2.y -= dy;
	
	    // calculates control point 3
	    qPts.control3 = Point.interpolate(PA, PB, 3/8);
	    qPts.control3.x += dx;
	    qPts.control3.y += dy;
	
	    // calculates control point 4
	    qPts.control4 = Point.interpolate(c2, p2, 3/8);
	
	    // calculates the 3 anchor points
	    qPts.anchor1 = Point.interpolate(qPts.control1, qPts.control2, 0.5); 
	    qPts.anchor2 = Point.interpolate(PA, PB, 0.5); 
	    qPts.anchor3 = Point.interpolate(qPts.control3, qPts.control4, 0.5); 
	
		// the 4th anchor point is p2
		qPts.anchor4 = p2;		
	}
}
}

import flash.geom.Point;
	
/**
 *  Utility class to store the computed quadratic points.
 */
class QuadraticPoints
{
	public var control1:Point;
	public var anchor1:Point;
	public var control2:Point;
	public var anchor2:Point;
	public var control3:Point;
	public var anchor3:Point;
	public var control4:Point;
	public var anchor4:Point;
	
	/**
     * Constructor.
     */
    public function QuadraticPoints()
    {
    	super();
    }
}

Iv · 08.09.2008, 20:26

Офигительно полезный класс.
Ну прям в трубочку свернуть и засунуть по назначению.

incoob · 11.09.2008, 15:28

Цитата:

Сообщение от Iv

Офигительно полезный класс.

Полностью с вами согласен!
Конечно, этот класс не является работоспособным примером, но если его немного поправить, то получим

Код:

package 
{
	import flash.display.Graphics;
	import flash.geom.Point;
	
	public class CubicBezier
	{
		public static function cBez(g:Graphics, prevX:Number, prevY:Number, control1X:Number, 
			control1Y:Number, control2X:Number, control2Y:Number, x:Number, y:Number):void
		{
			var qPts:QuadraticPoints
			if (prevX && control1X && control2X && x)
			{
				var p1:Point = new Point(prevX, prevY);
				var p2:Point = new Point(x, y);
				var c1:Point = new Point(control1X, control1Y);		
				var c2:Point = new Point(control2X, control2Y);
			
				// calculates the useful base points
				var PA:Point = Point.interpolate(c1, p1, 3/4);
				var PB:Point = Point.interpolate(c2, p2, 3/4);
	
				// get 1/16 of the [p2, p1] segment
				var dx:Number = (p2.x - p1.x) / 16;
				var dy:Number = (p2.y - p1.y) / 16;

				qPts = new QuadraticPoints;
		
				// calculates control point 1
				qPts.control1 = Point.interpolate(c1, p1, 3/8);
	
				// calculates control point 2
				qPts.control2 = Point.interpolate(PB, PA, 3/8);
				qPts.control2.x -= dx;
				qPts.control2.y -= dy;
	
				// calculates control point 3
				qPts.control3 = Point.interpolate(PA, PB, 3/8);
				qPts.control3.x += dx;
				qPts.control3.y += dy;
	
				// calculates control point 4
				qPts.control4 = Point.interpolate(c2, p2, 3/8);
	
				// calculates the 3 anchor points
				qPts.anchor1 = Point.interpolate(qPts.control1, qPts.control2, 0.5); 
				qPts.anchor2 = Point.interpolate(PA, PB, 0.5); 
				qPts.anchor3 = Point.interpolate(qPts.control3, qPts.control4, 0.5); 
	
				// the 4th anchor point is p2
				qPts.anchor4 = p2;
				
				g.curveTo(qPts.control1.x, qPts.control1.y, qPts.anchor1.x, qPts.anchor1.y);
				g.curveTo(qPts.control2.x, qPts.control2.y, qPts.anchor2.x, qPts.anchor2.y);
				g.curveTo(qPts.control3.x, qPts.control3.y, qPts.anchor3.x, qPts.anchor3.y);
				g.curveTo(qPts.control4.x, qPts.control4.y, qPts.anchor4.x, qPts.anchor4.y);
			}

		}
	}
}
import flash.geom.Point;

class QuadraticPoints
{
	public var control1:Point;
	public var anchor1:Point;
	public var control2:Point;
	public var anchor2:Point;
	public var control3:Point;
	public var anchor3:Point;
	public var control4:Point;
	public var anchor4:Point;
	
	/**
     * Constructor.
     */
    public function QuadraticPoints()
    {
    }
}

,что является значительно более приятной реализацией рисования, чем все вышепредставленные.

Так что

Цитата:

Сообщение от Iv

Ну прям в трубочку свернуть и засунуть по назначению.

- все же перебор.