Development

Offset Bézier Curves

Perfect Solution

Short answer it’s impossible to create a perfect offset curve.

The curve at a fixed offset from a given Bézier curve, often called an offset curve (lying “parallel” to the original curve, like the offset between rails in a railroad track), cannot be exactly formed by a Bézier curve (except in some trivial cases). However, there are heuristic methods that usually give an adequate approximation for practical purposes.

-Wikipedia

Imperfect Solution

So here is a heuristic method. Convert the Curve to a poly line spline. Then merge/clip the expanded lines.

  1. Subdivide the Curve into Line Segments
  2. Offset Line Segments
  3. Merge/Clip Intersections

Step #1: Subdivide the Curve into Line Segments

To convert the curve to line segments we use De Casteljau’s algorithm.

public function subDivide( time:Number ):Vector.<CubicBezierCurve>
{
	//Outside Guide Lines
	var outerA:StraightLine = new StraightLine( pointA, controlPointA );
	var outerBridge:StraightLine = new StraightLine( controlPointA, controlPointB );
	var outerB:StraightLine = new StraightLine( controlPointB, pointB );

	//Inner Guide Lines
	var innerA:StraightLine = new StraightLine( outerA.lerp( time ), outerBridge.lerp( time ));
	var innerB:StraightLine = new StraightLine( outerBridge.lerp( time ), outerB.lerp( time ));

	//Point at time
	var newPoint:Point = new StraightLine( innerA.lerp( time ), innerB.lerp( time )).lerp( time );

	//Return Vector
	var newCurves:Vector.<CubicBezierCurve> = new Vector.<CubicBezierCurve>();

	//Left Curve
	var leftCurve:CubicBezierCurve = new CubicBezierCurve();
	leftCurve.pointA = pointA;
	leftCurve.controlPointA = outerA.lerp( time );
	leftCurve.controlPointB = innerA.lerp( time );
	leftCurve.pointB = newPoint;
	newCurves.push( leftCurve );

	//Right Curve
	var rightCurve:CubicBezierCurve = new CubicBezierCurve();
	rightCurve.pointA = newPoint;
	rightCurve.controlPointA = innerB.lerp( time );
	rightCurve.controlPointB = outerB.lerp( time );
	rightCurve.pointB = pointB;
	newCurves.push( rightCurve );

	//Return Vector containing new curves.
	return newCurves;
}

When your flattening a curve some curves need more subdivision than others. You can check the flatness level to determine if the curve needs to be sub divided again and again. This will help optimize your algorithm for offsetting, by breaking the curve into as few of lines as visually required.

Here is a cool method to find flatness of a line.

public function get flatness():Number
{
	var ux:Number = Math.pow( 3 * controlPointA.x - 2 * pointA.x - pointB.x, 2 );
	var uy:Number = Math.pow( 3 * controlPointA.y - 2 * pointA.y - pointB.y, 2 );
	var vx:Number = Math.pow( 3 * controlPointB.x - 2 * pointB.x - pointA.x, 2 );
	var vy:Number = Math.pow( 3 * controlPointB.y - 2 * pointB.y - pointA.y, 2 );

	if( ux < vx )
		ux = vx;

	if( uy < vy )
		uy = vy;

	return ux + uy;
}

This is converted from the great article about curve flattening.
Piecewise_Linear_Approzimation

So now we use these function to subdivide the curve. Here are sample results. This is when using a tolerance of <= 0.15

Original Curve

Subdivided Line Segments (16 lines)

Original Curve

Subdivided Line Segments (26 lines)

Step #2 Offset Line Segments

Next we create parallel lines for each of the lines in our line segment spline.

Offsetting lines is easy and mathematically supported 😉 Here is a sample function.

public function createParrallelLine( difference:Number ):StraightLine {
	var perp_x:Number = -rise
	var perp_y:Number = run;
	var len:Number = Math.sqrt(( perp_x * perp_x ) + ( perp_y * perp_y ));

	perp_x = ( perp_x / len ) * difference;
	perp_y = ( perp_y / len ) * difference;

	var parrallelLine:StraightLine = new StraightLine( new Point( pointA.x - perp_x, pointA.y - perp_y ), new Point( pointB.x - perp_x, pointB.y - perp_y ));

	return parrallelLine;
}

Basically it creates use perpendicular slopes and linear interpolation to create perfectly positioned parallel line. It will also always stay on the correct edge of the curve, as long as the direction of all the lines are the same. Clockwise or Counter-Clockwise.

Offset of 1px

Step #3: Merge/Clip

The next step we connect the expanded curve lines, and we determine if the best course of action is to create a new line between them, or if we should remove/cut a existing line.

Check for intersections if your lines intersect, then clip. else create new line between, or if your fancy, you can use another curve, and use the intersection point as the control point.

Examples

I highlighted the intersections with blue. You can see how they mesh nicely.

Final Results

Here is some final results with a 2px offset curve. Original is red, offset is blue.

Related Documents

Advertisements

Ant Macros

Macros are a very slick way to consolidate, simplify, and configure your ANT scripts. For example, if your running a bunch of targets that executes sql queries. Your code could look something like this.

Without Macros (build.xml)

<project default="test">
	<extension-point name="DB.Install.1.0.0.Baseline" />

	<target name="DB.Install.1.0.0.Baseline.Clean" extensionOf="DB.Install.1.0.0.Baseline">
		<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installer}" userid="postgres" password="" autocommit="true"><![CDATA[
			DROP DATABASE IF EXISTS ${DB.Database};
			DROP ROLE IF EXISTS ${DB.Username};
		]]></sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Users" extensionOf="DB.Install.1.0.0.Baseline">
		<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installer}" userid="postgres" password="" autocommit="true"><![CDATA[
			CREATE ROLE ${DB.Username} WITH PASSWORD '${DB.Password}' LOGIN;
		]]></sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Database" extensionOf="DB.Install.1.0.0.Baseline">
		<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installer}" userid="postgres" password="" autocommit="true"><![CDATA[
			CREATE DATABASE ${DB.Database} WITH OWNER ${DB.Username};
		]]></sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Schemas" extensionOf="DB.Install.1.0.0.Baseline">
		<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installee}" userid="postgres" password="" autocommit="true"><![CDATA[
			CREATE SCHEMA ${DB.Schema};
			ALTER SCHEMA ${DB.Schema} OWNER TO ${DB.Username};
			COMMENT ON SCHEMA ${DB.Schema} IS 'My Cool Database Schema';
		]]></sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Tables" extensionOf="DB.Install.1.0.0.Baseline">
		<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installee}" userid="postgres" password="">
			<transaction src="tables.sql"/>
		</sql>
	</target>
<project>

Lots of redundant configurables being used

  • This means if you ever decide to change how you run queries you’ll need to modify each one of these calls to reflect the change
  • This also adds lots of bulk/waste code

Here is a example of how macros can help clean up your code.

With Macros (macros.xml)

<project>
	<!-- ============= -->
	<!-- = My Macros = -->
	<!-- ============= -->
	<macrodef name="run-sql-file">
		<attribute name="file"/>
		<attribute name="delimiter" default=";"/>
		<sequential>
			<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installee}" userid="postgres" password="" delimiter="@{delimiter}">
				<transaction><![CDATA[SET search_path = ${DB.Schema};]]></transaction>
				<transaction src="@{file}"/>
			</sql>
		</sequential>
	</macrodef>

	<macrodef name="run-sql">
		<text name="query"/>
   		<attribute name="transaction" default="false"/>
		<sequential>
			<if>
				<equals arg1="@{transaction}" arg2="true" />
				<then>
					<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installee}" userid="postgres" password="">
						<transaction><![CDATA[SET search_path = ${DB.Schema};]]></transaction>
						<transaction>@{query}</transaction>
					</sql>
				</then>
				<else>
					<sql driver="${JDBC.Driver}" url="${JDBC.URL.Installee}" userid="postgres" password="" autocommit="true">
						<transaction>@{query}</transaction>
					</sql>
				</else>
			</if>
		</sequential>
	</macrodef>
</project>

With Macros (build.xml)

<project default="test">
	<!-- ====================== -->
	<!-- = Include The Macros = -->
	<!-- ====================== -->
	<include file="macros.xml"/>

	<extension-point name="DB.Install.1.0.0.Baseline" />

	<target name="DB.Install.1.0.0.Baseline.Clean" extensionOf="DB.Install.1.0.0.Baseline">
		<run-sql><![CDATA[
			DROP DATABASE IF EXISTS ${DB.Database};
			DROP ROLE IF EXISTS ${DB.Username};
		]]></run-sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Users" extensionOf="DB.Install.1.0.0.Baseline">
		<run-sql><![CDATA[
			CREATE ROLE ${DB.Username} WITH PASSWORD '${DB.Password}' LOGIN;
		]]></run-sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Database" extensionOf="DB.Install.1.0.0.Baseline">
		<run-sql><![CDATA[
			CREATE DATABASE ${DB.Database} WITH OWNER ${DB.Username};
		]]></run-sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Schemas" extensionOf="DB.Install.1.0.0.Baseline">
		<run-sql transaction="false"><![CDATA[
			CREATE SCHEMA ${DB.Schema};
			ALTER SCHEMA ${DB.Schema} OWNER TO ${DB.Username};
			COMMENT ON SCHEMA ${DB.Schema} IS 'Cool Database Database Scheme';
		]]></run-sql>
	</target>

	<target name="DB.Install.1.0.0.Baseline.Tables" extensionOf="DB.Install.1.0.0.Baseline">
		<run-sql-file file="tables.sql" />
	</target>
<project>

Now if we ever want to change how we run our queries, we just modify our macros and all our code is updated. Also in large scale projects, this simplifies the code and shrinks it pretty dramatically.

foreach with Ant

I’ve been building a cool little ANT Compiler script, and found I could really use the ability to loop through a set of files. Namely sql files and then execute each file. I ended up finding a cool little add-on to ant. Ant-Contrib Adds in a bunch of functionality. The piece I used was the foreach task. Check it out below.

The Code (build.xml)

<!-- ===================================== -->
<!-- = Include The Ant-Contrib Functions = -->
<!-- ===================================== -->
<taskdef resource="net/sf/antcontrib/antcontrib.properties"/>

<!-- ====================================== -->
<!-- = Function to exececute foreach file = -->
<!-- ====================================== -->
<target name="DB.SQL">
	<sql driver="${JDBC.Driver}"
		url="${JDBC.URL}"
		userid="postgres"
		password="">
		<transaction src="${SQLFile}"/>
	</sql>
</target>

<!-- ================================ -->
<!-- = Scans Folder for *.sql Files = -->
<!-- ================================ -->
<target name="runSQLScripts">
	<foreach target="DB.SQL"
		param="SQLFile">
		<path>
			<fileset dir="." casesensitive="yes">
				<include name="Scripts/*.sql"/>
			</fileset>
		</path>
	</foreach>
</target>

It loops through every .sql file in the Scripts folder and executes it with the DB.SQL task. 😉

ANT Property Files

Properties are a good way to keep your ant tasks customizable. Here is a example of how to use property files.

build.properties

Flex.SDK = /opt/flex_sdk_4
Flex.Source = source
Flex.Build = build
Flex.Working = working

local.properties

Flex.Source = my_custom_source
Flex.Build = my_custom_build
Flex.Working = my_custom_working

build.xml

<?xml version="1.0" encoding="utf-8"?>
<project name="Test" basedir=".">
	<property file="local.properties"/>
	<property file="build.properties"/>
	<echo>${Flex.SDK}</echo>
	<echo>${Flex.Source}</echo>
	<echo>${Flex.Build}</echo>
	<echo>${Flex.Working}</echo>
</project>

Outputs

Buildfile: build.xml
     [echo] /opt/flex_sdk_4
     [echo] my_custom_source
     [echo] my_custom_build
     [echo] my_custom_working

BUILD SUCCESSFUL
Total time: 0 seconds

You’ll notice that I included the local.properties file first and the variables in there are the true values once everything is loaded. I would have thought this would be backwards. But the easy fix for overwriting properties is to switch the load order.

Source Code

Robot Legs & FlexUnit4 – EventDispatchers wo/Injector

This should be obvious, but in case you have a brain fart like I did earlier. If your looking to test a Robot Leg Actor. And you want to listen for events coming out of the Actor. Here is a easy way to do it.

The main purpose of this is to be able to test a individual actor. Such as a web service to make sure it as a individual is performing correctly.

Actor


public var myActor:CoolActorClass;

[Before]
public function setupActor():void {
	myActor = new CoolActorClass();
	myActor.eventDispatcher = new EventDispatcher();
}

And if your using Joel’s Modular Utility. You can do something like this.

ModularActor


public var myActor:CoolModularActorClass;

[Before]
public function setupModuleActor():void {
	myActor = new CoolModularActorClass();
	myActor.eventDispatcher = new EventDispatcher();
	myActor.moduleEventDispatcher = new ModuleEventDispatcher();
}

Now you can perform your test as if it’s running in a full blown RL Application.

I'm on the RobotLegs bandwagon!

I’ve been doing lots of research on Flex/AS3 Framework’s lately and found an awesome one.

http://www.robotlegs.org/

You basically create seperate objects for each part of your application.

  • View
  • Commands (Controllers)
  • Mediators (Object’s That Control the Views)
  • Context (Maps Everything Together)
  • Services (DataCalls)
  • VO (Store Data)
  • Events

The key is that every object only worries about it’s responsibilities, making it very structured and easy to debug. They for the most part don’t call direct functions of each other. Instead they create custom events and shoot them to each other. This is especially cool for Modular Apps. You can blast a event to all modules and they can each handle there own responsibility.

Very cool. You should check it out.