[stuff] clippen von bezierkurven

[André Michelle]

Am Wochenende hat es mich gepackt und heute sind die letzten Bugs gefunden und behoben.
Mit diesen beiden Klassen kann man Bezierkurven an allen orthogonalen Achsen clippen. In diesem Beispiel gegen ein ganzes Rechteck. Wofür das gut ist zeigt sich denke ich erst, wenn man es in 3D umsetzt. Dafür sind nur keine Änderungen notwendig, denn die Clipping Funktionen (clipMin, clipMax) akzeptieren jede Koordinate. Bei den Funktionen "split", "lerp" muss man nur eine Zeile für die z-Koordinate hinzufügen und die Vertex Klasse entsprechend erweitern.

In 3D wäre es dann möglich durch eine Ansammlung von 2D Bezierkurven zu fliegen, weil man an der Front-Projektionsfläche clippen kann. Mal sehen, wann ich dazu komme. Mathematisch war das für mich in jedem Fall eine Herrausforderung, hehe.

source

Eine simple "Vertex" Klasse, um die Koordinaten zu speichern.

class Vertex
{
	public var x: Number;
	public var y: Number;
	
	public function	Vertex( x: Number, y: Number )
	{
		this.x = x;
		this.y = y;
	}
	
	public function clone(): Vertex
	{
		return new Vertex( x, y );
	}
	
	public function toString(): String
	{
		return '[Vertex x: ' + x + ' y: ' + y + ']';
	}
}

Und hier das dicke Ei zum Clippen von 2D Beizerkurven.

/**
 * @author Andre Michelle
 */

class Bezier
{
	private var v0: Vertex;
	private var v1: Vertex;
	private var v2: Vertex;
	
	public function Bezier( v0: Vertex, v1: Vertex, v2: Vertex )
	{
		this.v0 = v0;
		this.v1 = v1;
		this.v2 = v2;
	}
	
	public function clipAgainstBounds( xMin: Number, xMax: Number, yMin: Number, yMax: Number ): Array
	{
		var clipped: Array = clipMin( 'x', xMin );
		
		var i: Number = clipped.length;
		
		while( --i > -1 )
		{
			clipped = clipped.concat( Bezier( clipped.shift() ).clipMin( 'y', yMin ) );
		}
		
		i = clipped.length;
		
		while( --i > -1 )
		{
			clipped = clipped.concat( Bezier( clipped.shift() ).clipMax( 'x', xMax ) );
		}
		
		i = clipped.length;
		
		while( --i > -1 )
		{
			clipped = clipped.concat( Bezier( clipped.shift() ).clipMax( 'y', yMax ) );
		}
		
		return clipped;
	}
	
	public function clipMin( axis: String, value: Number ): Array
	{
		var a0: Number = v0[axis];
		var a1: Number = v1[axis];
		var a2: Number = v2[axis];
		
		var t0: Number = 0;
		var t1: Number = 1;
		
		var s: Number = ( value - a0 ) * a2 + a1 * a1 - 2 * value * a1 + value * a0;
		var d: Number;
		
		if( s > 0 )
		{	
			s = Math.sqrt( s );
			d = a2 - 2 * a1 + a0;
			
			if( Math.abs( d ) > .01 )
			{
				t0 =  ( s - a1 + a0 ) / d;
				t1 = -( s + a1 - a0 ) / d;
			}
			else
			{
				if( a0 > a2 )
				{
					t1 = ( value - a0 ) / ( a2 - a0 );
				}
				else
				{
					t0 = ( value - a0 ) / ( a2 - a0 );
				}
			}
		}
		else
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		
		if( t1 <= 0 && t0 >= 1 )
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		if( t0 <= 0 && t1 <= 0 )
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		if( t0 >= 1 && t1 >= 1 )
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		
		if( t0 < 0 )
		{
			t0 = 0;
		}
		if( t1 > 1 )
		{
			t1 = 1;
		}
		if( t0 > t1 )
		{
			if( t1 < 0 )
			{
				return [ split( 1, t0 ) ];
			}
			if( t0 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			if( t1 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			return [ split( 1, t0 ), split( 0, t1 ) ];
		}
		return [ split( t0, t1 ) ];
	}
	
	public function clipMax( axis: String, value: Number ): Array
	{
		var a0: Number = v0[axis];
		var a1: Number = v1[axis];
		var a2: Number = v2[axis];
		
		var t0: Number = 0;
		var t1: Number = 1;
		
		var sb: Bezier;
		
		var s: Number = ( value - a0 ) * a2 + a1 * a1 - 2 * value * a1 + value * a0;
		var d: Number;
		
		if( s > 0 )
		{	
			s = Math.sqrt( s );
			d = a2 - 2 * a1 + a0;
			
			if( Math.abs( d ) > .01 )
			{
				t0 = -( s + a1 - a0 ) / d;
				t1 =  ( s - a1 + a0 ) / d;
			}
			else
			{
				if( a0 > a2 )
				{
					t0 = ( value - a0 ) / ( a2 - a0 );
				}
				else
				{
					t1 = ( value - a0 ) / ( a2 - a0 );
				}
			}
		}
		else
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		
		if( t1 <= 0 && t0 >= 1 )
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		if( t0 <= 0 && t1 <= 0 )
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		if( t0 >= 1 && t1 >= 1 )
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		
		if( t0 < 0 )
		{
			t0 = 0;
		}
		if( t1 > 1 )
		{
			t1 = 1;
		}
		if( t0 > t1 )
		{
			if( t1 < 0 )
			{
				return [ split( 1, t0 ) ];
			}
			if( t0 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			if( t1 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			return [ split( 1, t0 ), split( 0, t1 ) ];
		}
		return [ split( t0, t1 ) ];
	}
	
	public function lerp( v0: Vertex, v1: Vertex, t: Number ): Vertex
	{
		return new Vertex
		(
			( 1 - t ) * v0.x + t * v1.x,
			( 1 - t ) * v0.y + t * v1.y
		);
	}
	
	public function split( t0: Number, t1: Number ): Bezier
	{
		if( t0 == t1 ) return null;
		
		var x0: Number = v0.x;
		var y0: Number = v0.y;
		var x1: Number = v1.x;
		var y1: Number = v1.y;
		var x2: Number = v2.x;
		var y2: Number = v2.y;
		
		var t00: Number = t0 * t0;
		var t01: Number = 1 - t0;
		var t02: Number = t01 * t01;
		var t03: Number = 2 * t0 * t01;
		
		var nx0: Number = t02 * x0 + t03 * x1 + t00 * x2;
		var ny0: Number = t02 * y0 + t03 * y1 + t00 * y2;
		
		t00 = t1 * t1;
		t01 = 1 - t1;
		t02 = t01 * t01;
		t03 = 2 * t1 * t01;
		
		var nx1: Number = t02 * x0 + t03 * x1 + t00 * x2;
		var ny1: Number = t02 * y0 + t03 * y1 + t00 * y2;

		var ncp: Vertex = lerp ( lerp ( v0 , v1 , t0 ) , lerp ( v1 , v2 , t0 ) , t1 );
		
		return new Bezier
		(
			new Vertex( nx0, ny0 ),
			new Vertex( ncp.x, ncp.y ),
			new Vertex( nx1, ny1 )
		);
	}
	
	public function clone(): Bezier
	{
		return new Bezier( v0.clone(), v1.clone(), v2.clone() );
	}
	
	public function draw( g: MovieClip ): Void
	{
		g.moveTo( v0.x, v0.y );
		g.curveTo( v1.x, v1.y, v2.x, v2.y );
	}
	
	public function toString(): String
	{
		return '[Bezier 0:' + v0 + ' 1:' + v1 + ' 2:' + v2 + ']';
	}
}

[the binary]

habs schon im aggregator gelesen...
dickes ding..
bin gespannt, was die 3d-experimente bringen.

btw:
wäre schön, wenn du, nachdem es dich gepackt hat - quasi zum chillout - noch die eine oder andere kommentarzeile einweben würdest...

gruss

[rendner[i]]

Würde mich ebenfalls freuen wenn André etwas Zeit finden würden und die Klasse "Bezier" etwas mit Kommentaren ausschmücken könnte.
Oder vielleicht ein paar leicht verständliche Links angeben, damit man sich das zur Not auch selber zusammenreimen kann.

Ist auf jeden Fall sehr Interessant.

[André Michelle]

Jeder Punkt auf einer Bezierkurve kann durch eine Formel dargestellt werden, der man einen Wert(t) 0 <= t <= 1 übergibt.

p't = (1-t)*(1-t)*p0 + 2*t*(1-t)*p1+t^2*p2

Reihenfolge ist p0: Anker, p1: Kontrolpunkt, p2: Endpunkt.
Will man die x-Werte auslesen, dann nimmt setzt man für p0,p1,p2 die entsprechenden x-Werte der Punkte ein. Für y't entsprechend y.

Möchte man jetzt an der Position x=50 clippen, muss man die möglichen beiden t-Werte berechnen (t0,t1), an denen die Kurve die Senkrechte kreuzt. Dazu stellt man die Gleichung um.

Das habe ich mir von xmaxima für 'x' machen lassen:

     SQRT((x - x0) x2 + x1^2  - 2 x x1 + x x0) + x1 - x0
t0 = - -------------------------------------------------
			      x2 - 2 x1 + x0


     SQRT((x - x0) x2 + x1^2  - 2 x x1 + x x0) - x1 + x0
t1 = -----------------------------------------------
			      x2 - 2 x1 + x0

In den Kommentaren nenne ich sie einfach 'forumlar'. Hat man die Werte gefunden, muss man entscheiden, ob sie gültige Werte sind. t kann auch größer als 1 und kleiner als 0 werden und trotzdem ein potentieller Clipkandidat sein. Ich habe dazu alle möglichen Position der Kurve ausprobiert und die t-Werte ausgelesen. Das war also eher experimentell als grundsolide durchgerechnet. Schwieriger war die Division durch Null, die die original Formel nun mal potentiell hat. Daran habe ich mir lange die Zähne ausgebissen, bis ich den linearen Zusammenhang gesehen habe.

Die Funktion split habe ich auch einem alten Flash6 fla noch übernehmen können. Daher kann ich das nicht mehr wirklich kommentieren. Ist zu lange her. Ich habe es nur sauber geputzt und etwas optimiert. fla | swf

/**
 * @author Andre Michelle
 */

class Bezier
{
	private var v0: Vertex;
	private var v1: Vertex;
	private var v2: Vertex;
	
	/*
	 * constructor
	 */
	
	public function Bezier( v0: Vertex, v1: Vertex, v2: Vertex )
	{
		this.v0 = v0;
		this.v1 = v1;
		this.v2 = v2;
	}
	
	/*
	 * clipping against rectangle
	 */
	
	public function clipAgainstBounds( xMin: Number, xMax: Number, yMin: Number, yMax: Number ): Array
	{
		var clipped: Array = clipMin( 'x', xMin );
		
		var i: Number = clipped.length;
		
		while( --i > -1 )
		{
			clipped = clipped.concat( Bezier( clipped.shift() ).clipMin( 'y', yMin ) );
		}
		
		i = clipped.length;
		
		while( --i > -1 )
		{
			clipped = clipped.concat( Bezier( clipped.shift() ).clipMax( 'x', xMax ) );
		}
		
		i = clipped.length;
		
		while( --i > -1 )
		{
			clipped = clipped.concat( Bezier( clipped.shift() ).clipMax( 'y', yMax ) );
		}
		
		return clipped;
	}
	
	/*
	 * clipping a bezier can return 2 beziercurves
	 * so we return an array
	 */
	
	public function clipMin( axis: String, value: Number ): Array
	{
		//-- only the given axis coordinate is needed
		//
		var a0: Number = v0[axis];
		var a1: Number = v1[axis];
		var a2: Number = v2[axis];
		
		//-- default (t) (full bezier curve)
		var t0: Number = 0;
		var t1: Number = 1;
		
		//-- formular get (t) for a given coordinate
		
		var s: Number = ( value - a0 ) * a2 + a1 * a1 - 2 * value * a1 + value * a0;
		var d: Number;
		
		if( s > 0 )
		{
			//-- s is positive, we can follow the formular
			s = Math.sqrt( s );
			
			//-- dividend
			d = a2 - 2 * a1 + a0;
			
			//-- avoid dividing by zero (with some tolerance)
			if( Math.abs( d ) > .01 )
			{
				//-- resulting (t) by the formular
				t0 =  ( s - a1 + a0 ) / d;
				t1 = -( s + a1 - a0 ) / d;
			}
			else
			{
				//-- resulting (t) by linear equation
				if( a0 > a2 )
				{
					t1 = ( value - a0 ) / ( a2 - a0 );
				}
				else
				{
					t0 = ( value - a0 ) / ( a2 - a0 );
				}
			}
		}
		else
		{
			//-- s is negativ, no square(s) is defined
			//-- check if anchors are outside the clipping area
			//-- if the curve is located outside the clipped area, just return itself
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		
		//-- checking if resulting (t) are valid and in clipped area
		if( t1 <= 0 && t0 >= 1 )
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		if( t0 <= 0 && t1 <= 0 )
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		if( t0 >= 1 && t1 >= 1 )
		{
			if( a0 >= value && a2 >= value ) return [ this ];
			return [];
		}
		
		//-- we have a clipping candidate
		//-- clamp (t) and split the bezier by the computed (t)
		if( t0 < 0 )
		{
			t0 = 0;
		}
		if( t1 > 1 )
		{
			t1 = 1;
		}
		if( t0 > t1 )
		{
			if( t1 < 0 )
			{
				return [ split( 1, t0 ) ];
			}
			if( t0 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			if( t1 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			return [ split( 1, t0 ), split( 0, t1 ) ];
		}
		return [ split( t0, t1 ) ];
	}
	
	/*
	 * clipping a bezier can return 2 beziercurves
	 * so we return an array
	 * clipMax is very similar to clipMin above
	 */
	
	public function clipMax( axis: String, value: Number ): Array
	{
		var a0: Number = v0[axis];
		var a1: Number = v1[axis];
		var a2: Number = v2[axis];
		
		var t0: Number = 0;
		var t1: Number = 1;
		
		var sb: Bezier;
		
		var s: Number = ( value - a0 ) * a2 + a1 * a1 - 2 * value * a1 + value * a0;
		var d: Number;
		
		if( s > 0 )
		{	
			s = Math.sqrt( s );
			d = a2 - 2 * a1 + a0;
			
			if( Math.abs( d ) > .01 )
			{
				t0 = -( s + a1 - a0 ) / d;
				t1 =  ( s - a1 + a0 ) / d;
			}
			else
			{
				if( a0 > a2 )
				{
					t0 = ( value - a0 ) / ( a2 - a0 );
				}
				else
				{
					t1 = ( value - a0 ) / ( a2 - a0 );
				}
			}
		}
		else
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		
		if( t1 <= 0 && t0 >= 1 )
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		if( t0 <= 0 && t1 <= 0 )
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		if( t0 >= 1 && t1 >= 1 )
		{
			if( a0 <= value && a2 <= value ) return [ this ];
			return [];
		}
		
		if( t0 < 0 )
		{
			t0 = 0;
		}
		if( t1 > 1 )
		{
			t1 = 1;
		}
		if( t0 > t1 )
		{
			if( t1 < 0 )
			{
				return [ split( 1, t0 ) ];
			}
			if( t0 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			if( t1 > 1 )
			{
				return [ split( 0, t1 ) ];
			}
			return [ split( 1, t0 ), split( 0, t1 ) ];
		}
		return [ split( t0, t1 ) ];
	}
	
	/*
	 * help method for splitting the curve
	 */
	
	public function lerp( v0: Vertex, v1: Vertex, t: Number ): Vertex
	{
		return new Vertex
		(
			( 1 - t ) * v0.x + t * v1.x,
			( 1 - t ) * v0.y + t * v1.y
		);
	}
	
	/*
	 * split returns a new curve section from t0 to t1
	 */
	
	public function split( t0: Number, t1: Number ): Bezier
	{
		if( t0 == t1 ) return null;
		
		var x0: Number = v0.x;
		var y0: Number = v0.y;
		var x1: Number = v1.x;
		var y1: Number = v1.y;
		var x2: Number = v2.x;
		var y2: Number = v2.y;
		
		var t00: Number = t0 * t0;
		var t01: Number = 1 - t0;
		var t02: Number = t01 * t01;
		var t03: Number = 2 * t0 * t01;
		
		//-- new anchor by t0
		var nx0: Number = t02 * x0 + t03 * x1 + t00 * x2;
		var ny0: Number = t02 * y0 + t03 * y1 + t00 * y2;
		
		t00 = t1 * t1;
		t01 = 1 - t1;
		t02 = t01 * t01;
		t03 = 2 * t1 * t01;
		
		//-- new end point by t1
		var nx1: Number = t02 * x0 + t03 * x1 + t00 * x2;
		var ny1: Number = t02 * y0 + t03 * y1 + t00 * y2;

		//-- new control point
		var ncp: Vertex = lerp ( lerp ( v0 , v1 , t0 ) , lerp ( v1 , v2 , t0 ) , t1 );
		
		return new Bezier
		(
			new Vertex( nx0, ny0 ),
			new Vertex( ncp.x, ncp.y ),
			new Vertex( nx1, ny1 )
		);
	}
	
	public function clone(): Bezier
	{
		return new Bezier( v0.clone(), v1.clone(), v2.clone() );
	}
	
	public function draw( g: MovieClip ): Void
	{
		g.moveTo( v0.x, v0.y );
		g.curveTo( v1.x, v1.y, v2.x, v2.y );
	}
	
	public function toString(): String
	{
		return '[Bezier 0:' + v0 + ' 1:' + v1 + ' 2:' + v2 + ']';
	}
}

Jetzt schlauer ? :o)

[rendner[i]]

Also ein bisschen hat sich der Nebel gelegt ( sah wilder aus als es wahrscheinlich ist ).
Danke, dass du doch Zeit gefunden hast, das mal kurz zu Kommentieren.

Werde mich gleich mal drauf stürzen und mir das noch mal genauer angucken...

EDIT:
Hier ist der Algorithmus von De Casteljau den André in seiner Beispiel-fla ( einen Beitrag weiter oben ) verwendet hat sehr gut anschaulich erklärt.

[fourtytwo]

yo andré...wieder mal geiler stuff..

du hast was von 'nach 3D umsetzen' geschrieben. etwa ne millisekunde bevor ich das las habe ich an nen projekt gedacht, an dem ich vor ca. nem jahr saß.

das befasst sich eben mit dem clipping, in diesem falle nur front-plane und geraden.
allerdings bin ich damals in der mathe nicht weitergekommen. genauer an der x_rot-achse der camera. (hab grade mal nachgesehen...über die num-key´s 2,4,6,8 lässt sich die rotation der camera steuern, pfeiltasten=translation).
es gibt zwar noch einen weiteren 'angriff' der besser ist, aber noch nicht ausgereift.

hier der 'erste angriff', sieht besser aus )
3D clipping

beziers clippen....schöne sache, werde ich beim nächsten mal mit einplanen.

vielen dank an dieser stelle für dein sourcing*respect*

gruß
42