Archive

Posts Tagged ‘Geometry’

The CompGeoJS Project

December 10, 2013 1 comment

I’ve received a few emails from readers of this (now closed) blog regarding my current development direction.  I’m actually taking some time off after working on a very long Flex gig to get involved in some new stuff.  As I look back over the span of time from 2004 (when I started this blog) to nearly 2014, my two favorite open-source projects were Degrafa and Singularity.  The Singularity project provided an Actionscript library for commonly used tools from the field of computational geometry.  I wrote a series of free TechNotes to explain the mathematics behind the techniques.  Unfortunately, the TechNotes did not follow any reasonable pedagogical order, and I kind of regret the approach.

I’m very interested in reviving this development for the new wave of interactive developers who are concentrating their efforts in HTML 5 and JS.  The goal of the CompGeoJS project is to provide interactive developers with a comprehensive, open-source library for addressing problems arising from the fields of analytic and computational geometry.  Unlike Singularity, the library will be developed first, along with a robust collection of demos and online documentation.  The process will be much more organized this time around and will eventually enable developers to tackle a wide variety of applications such as architecture, floor planning, advanced programmatic animation, and gaming.

Once the library reaches a solid ‘version one’ state, I will write an eBook to accompany the online documentation that discusses the mathematics behind all the tools.  I hope this will be of use to developers who wish to modify the library for very customized uses as well as instructors of numerical analysis and computational geometry.

It’s at a VERY early stage of development, but you can check out what is available right now and where the library is going at the CompGeoJS project home page.

Thanks and enjoy!

Rotate A Point Collection About Another Point

December 24, 2012 1 comment

Well, this will probably be the last, or nearly last post of a busy year that involved a lot of work on gigs and little focus on this blog.  Sorry, maybe next year will be better 🙂

In the previous example, I showed how to rotate a box (rectangle) around an arbitrary point, but the algorithm and code never presumed anything about the geometric nature of the object.  It’s possible to extend the exact same algorithm to a collection of points and that is the subject of the current post.

Instead of maintaining variables for the four vertices of a rectangle, the code was modified to work with an arbitrary point collection.  A RotatablePoint class was used to hold data points and offload some of the computations.  This greatly simplifies the actual demo and provides you with ample means for experimentation.

The online example starts with a small collection of points as shown below.

rotate

These points are rotated about the fixed point, drawn as a red dot.  The drawing may be cleared after each rotation increment or continually updated from the prior drawing as shown below.

rotate1

View online demo.

View source.

Have a Merry Christmas and I’ll try to post more next year!

Trig Plus Algebra Plus Geometry Plus Vectors Equals Fun

November 8, 2012 Comments off

Math teachers hear the most often-uttered student phrase in history a lot more than I do, but my ears have twitched to the infamous, “I’ll never use that” or its many variants over the years.  Funny how people know right now what will and will not be needed or used for the rest of their lives 🙂

Now, taken in strict isolation, a single trig or algebra formula might appear to have limited or no use in the myriad of life situations in someone’s future.  It is, however, quite interesting how often problems can be solved by strategic use of a single formula from multiple areas of study.  The problem discussed in this post is one such example.

In the prior post, I illustrated how some basic trig concepts could be used to solve a rotation and bounding-box problem without any presumptions or special considerations of the programming environment.  This example is similar in that it illustrates how to rotate a box around an arbitrary point in its interior.  The box is represented by a sequence of four coordinate pairs.  It is not a Flash symbol or anything other than a sequence of coordinates.  The drawing environment is simple; it can move the pen, draw lines, and draw filled circles.  The programming environment contains the typical set of math functions.

Our math background includes a semester of trig, analytic geometry, and algebra.  We know the very basics of vectors, but have not been introduced to matrices or matrix/coordinate transforms.  As it happens, all we need to know to solve the stated problem is

1 – Polar coordinates, i.e. x = r cos(a) , y = r sin(a)

2 – Parametric equation of a straight line, i.e. P = (1-t)P0 + tP1

3 – How to add and subtract vectors

4 – How to compute the distance between two points

Refer to the diagram below.

The four points of the box are A (x1,y1), B (x2,y2), C (x3,y3), and D (x4,y4).  The rotation point is R (rx,ry). The example code was written in Flex and the coordinate system in the Flash player is y-down.  We are not given the coordinates of R.  In fact, the box may be at an angle to the horizontal as shown in the lower, right part of the diagram.  The only thing we know about R is that the component parallel to each side of the box is a fraction of that side’s length.  This is where vector math can be useful.

The coordinates of R can be computed by adding the vectors V1 and V2.  The percentage inputs can be converted into numbers t1 and t2 in [0,1].  The exact coordinates of the terminal points of these vectors are obtained from the parametric equation of a line.  Let the non-bolded notation V1 and V2 refer to vectors from the origin representing these terminal points.  Then, V1 = (1-t1)A + t1B and V2 = (1-t2)A + t2D. Since the initial point of both V1 and V2 is A, the vector constituents (Δx and Δy) are immediately available.  Add the vectors and add the result to A to obtain the coordinates for R.  So, we can adjust sliders that change the percentage along each side and quickly compute R regardless of any prior rotation since we should always recompute the correct coordinates for A, B, C, and D.

When R is set, imagine lines drawn from R to each of the vectors A, B, C, and D.  Let the distances be r1, r2, r3, and r4, respectively.  Also compute the angle each line segment makes with the horizontal using the atan2() function.  Since this returns a value in [-Π, Π], a small adjustment is made to always record the angles in [0, 2Π].  This makes studying the angle computations a bit easier if you want to trace out the results as part of deconstructing the code.

Also record the initial rotation angle when R is assigned.  Subsequent changes to this value rotate the box around R by some delta.  If the initial angle of the box is θ, and the delta is δ, then the four points are rotated around R by an angle θ+δ. Compute the coordinates of each new vector, A, B, C, and D by using the formula for polar coordinates and add the center, R.

These concepts are illustrated in an online demo.

The percentage along each side used to compute R is adjusted by sliders as well as the rotation angle.  The red dot visually identifies the rotation point, R.  You may optionally display the circle traced by each of the four corner points as the box is rotated.  There is a _clear (Boolean) variable in the code that you may adjust to either clear the drawing each rotation update or choose to draw over each update of the box.  If the value is false, you can produce some spirograph-style drawings.

The UI was created in Flex, but the actual code is very straightforward and does not rely on anything unique to Actionscript.  It could be ported to many other environment quite easily.  There is also some internal documentation on how to use trig identities to reduce the number of trig computations at each rotation update.

Even more importantly, there is nothing in the code or the algorithm that relies on a box being rotated other than computing R.  The actual rotation is applied to a sequence of points using the simplest of concepts from a few math disciplines.  I hope this provides some sense of appreciation of problems that can be solved using only the most fundamental techniques from a few branches of applied math.

View demo

View source

Categories: General, Math Tags: , , , ,

Trig 101

October 23, 2012 Comments off

In the previous post, I promised to discuss the math behind rotating a rectangular sprite about its upper, left-hand registration point; that is, the origin of the sprite in its local coordinate space is the upper, left-hand corner.  This is actually a segue into a more general discussion of rotation about an arbitrary point.

While some programming environments offer more direct capability than others, low-level math serves as a common denominator between them.  If you understand the math, then it’s easy and efficient to port capability from one environment to another.  There are also times where inlining direct computations offers opportunities for performance optimization in mobile apps or games.  So, let’s start with that age-old question of what will I ever use trig for?

The programming example in the prior post dealt with computing the axis-aligned bounding box of a rectangular sprite after rotation about its origin.  Refer to the diagram below.

The original sprite in light blue is rotated through an angle, a, to the orientation shown in light red.  The origin (upper, left-hand corner) remains the same while the points A, B, and C are rotated to new positions A’, B’, and C’.  Once the coordinates of these new points are known, it is trivial to compute the AABB (axis-aligned bounding box) shown in red.

From the outset drawing to the lower, right, let the width and height of the sprite be represented by w and h, respectively.  The distance, r, is simply sqrt(w2 + h2) and the angle, b, may be precomputed using the atan2 function available in most any programming language.  Using the base definitions of sine and cosine, the coordinates of point A’ are ( w*cos(a), w*sin(a) ).  The coordinates of B’ are ( r*cos(a+b), r*sin(a+b) ).  If a+b = c, then the coordinates of C’ are computed as ( h*cos(c+Π/2), h*sin(c+Π/2) ) .

There is no need for an additional trig computation for C’ since we can use the well-known identity, sin(x+y) = sin(x)*cos(y) + sin(y)*cos(x).  cos(x+y) = cos(x)*cos(y) – sin(x)*sin(y).   cos(Π/2) = 1 and sin(Π/2) = 0.  Plug these into the identities and you should see that we can re-use the computation of cos(c) and sin(c).  Refer to the code (the rotation() mutator function) in the prior post to check your computations.  It should be easy to follow whether Actionscript, Javascript, C++, or Obj C is your language of choice.

Once we have the coordinates, the AABB is trivially computed and the computations can be easily ported to any programming environment or further optimized inside the application.  All with some very basic trig and your friendly, neighborhood pythagorean theorem 🙂  The operations could be optimized beyond what is illustrated in the code and that is left as an exercise.

Notice that we computed the rotated points in the sprite’s local coordinate space.  The AABB is often computed in parent space, so it’s necessary to translate to the origin of that space.  This is illustrated in the boundingBox() accessor function.

There is, of course, nothing special about rotation about the upper, left-hand corner.  The next example will cover rotation about the centroid of the sprite, which is a special case of rotation about an arbitrary point in the sprite’s coordinate space.  No matter what application you are working on or language you are working with, understanding what is happening ‘under the hood’ can go a long way.  I hope you found something useful in this post.

Categories: Math Tags: , , ,

Privatizing Freehand Drawing Library

September 7, 2012 1 comment

I’m into an extension of my prior gig, so time is still very limited.  In addition to family issues, what little time remains is dedicated to supporting existing beta users of the Freehand Drawing Library.  And, these users just scored big time.  I’ve decided to keep the library private and license it only to customers, providing requested customization at an hourly rate.

Existing beta users will continue to receive free updates of the core library and the current beta period is now permanently closed.  I will blog about development of the library as a segue into discussing some of the math behind the programming.  I also hope to start a series on computational geometry in Javascript some time this fall.

Thanks for bearing with the extreme lack of posts this year 🙂

Editing A Cubic Bezier Spline

May 7, 2012 Comments off

A couple months ago, this was something I believed I would never say about the Freehand Drawing Library.  Now, the library is and always will be a drawing library. Editing is not part of the core library architecture, however, it is something that requires a level of support inside the library.  In the past, this was accomplished by caching the sequence of mouse motions used to define a stroke.  The points could be edited and manually assigned to a stroke, either all at once or in an ENTER_FRAME event to animate the stroke.

This works cleanly with a simple interface for typical strokes, i.e. touch-move-release motions.  Now that the FDL supports splines and possibly other constructs that stretch the definition of a stroke, what about editing more complex drawings?  I want to maintain a light interface and not make editing operations an integral part of the library.  That inevitably leads to interface and code bloat in an attempt to satisfy every possible combination of customer-created editor.

I think it was the movie ‘War Games’ that popularized the phrase, ‘always leave yourself a back door.’  The back door to stroke manipulation outside normal FDL methods is to use arbitrary name-value parameters.  Every stroke has the ability to access or mutate arbitrary data objects.  It’s only two methods in the API, but they provide a wide variety of capability to custom strokes.

I added a simple spline editor to the PolyLine demo as an illustration.  After creating a spline (by clicking the end button), the knot/tangent display is overlaid on top of the stroke as shown below.

The spline knots are already available since they were manually assigned to the stroke.  The tangent information is entirely encapsulated inside the drawing engine, inside the stroke.  That information is obtained by the demo via a parameter request,

__stroke.getParam( “tangent” + i.toString() );

It is the responsibility of each stroke class to document all custom parameter queries and settings.  The above query returns in- and out-tangent values in an Object and that information is passed to the editor.  Knots may be dragged, which cause a parallel shift in the tangent.  The new knot and tangent information is conveyed back to the stroke with a sequence of parameter settings,

__stroke.params = { “changeKnot”:{vertex:index, x:editor.knotX, y:editor.knotY} };

or

__stroke.params = { “changeInTangent”:{vertex:index, x:editor.inTangentX, y:editor.inTangentY} };

__stroke.params = { “changeOutTangent”:{vertex:index, x:editor.outTangentX, y:editor.outTangentY} };

If a spline drawing engine is assigned to the PolyLine, it passes this information onto the internal FDLIntepolatingSpline instance.  A non-spline engine (line segments) ignores the parameters.

The screenshot below shows the result of a knot drag.

After dragging the middle vertex, the following screenshot shows the result of editing the first-vertex out-tangent.

This is all supported by the existing architecture, but there is one wrinkle.  If the edited spline is to be saved and then redrawn at a future time, we must have the facility to record the tangent edits *and* bypass the tangent Command when the spline is reconstructed.

I added an auxData parameter to the StrokeDataVO, which allows arbitrary auxiliary data to be recorded for a stroke.  It’s easy to deep-copy an Object with a ByteArray, so preserving immutability was no problem.  Now, by adding support for a ‘redraw’ parameter in the PolyLine stroke, the spline can be redrawn with arbitrary tangents supplied by external data instead of the tangents computed by the injected tangent Command.

FDL Cubic Bezier Spline

April 30, 2012 1 comment

The cubic bezier spline drawing engine in the Freehand Drawing Library is now complete.  As I mentioned in the prior post, the drawing engine fits into the FDL architecture and allows a spline to be treated as a stroke.  The CubicBezierSpline drawing engine contains a reference to a FDLCubicBezierSpline, which handles all the spline computations except for tangents.  Tangents are implemented via a Command pattern (with the spline as the receiver of the Command).  Three tangent commands are now available for cubic splines.  The NormalBisector Command uses the same algorithm as described in this TechNote.  The CatmullRom Command uses an algorithm similar to that in Catmull-Rom splines.  The Corner Command can be applied on a per-vertex basis and constructs splines with hard ‘corners’ or only G-0 continuity at a join point.

While the CubicBezierSpline engine manages the internal spline and tangent commands, the spline and tangent computations can be easily used outside the FDL in a purely computational context.

Every FDL spline is arc-length parameterized by default, using a fast algorithm for on-the-fly parameterization.  So, every coordinate request, i.e. getX(t) and getY(t) is actually computed based on normalized arc length in [0,1].  So, getX(0.5) returns the x-coordinate at approximately half the length along the spline.

Splines are implemented as drawing engines for a PolyLine stroke.  As always, a drawing engine is injected into the stroke,

__data.drawingEngine = “net.algorithmist.freehand.engine.CubicBezierSpline”;

Arbitrary parameters (name-value pairs) may be assigned to any drawing engine.  All splines require a ‘tangentCommand’ parameter to inject the Command used for tangent computations.  The normal bisector algorithm is applied as follows.

__data.engineParams  = {“tangentCommand”:”net.algorithmist.freehand.commands.NormalBisector”};

or, substitute the Catmull-Rom algorithm, if desired,

__data.engineParams  = {“tangentCommand”:”net.algorithmist.freehand.commands.CatmullRom”};

then, assign the data provider to the stroke,

__stroke.data = __data;

The cubic bezier spline supports auto-closure with G-1 continuity across the full set of tangent commands since the closure algorithm is inside the Command itself. Here is a screenshot,

and here is a screenshot of an open spline using the Catmull-Rom algorithm for tangent computations,

The next step is editing the spline by adjusting knots and tangents.  I was originally skeptical how far the architecture could be pushed in terms of a ‘drawing’ that was not in line with a traditional stroke motion, i.e. press-move-release.  Editing the mathematical properties of something like a spline seemed out of the question at first thought.  So far, I’m glad the architecture is holding up without having to hack anything in.  I suppose a demo containing a spline editor will be the ultimate test 🙂

As an aside, spline editing facilities are not part of the library; they are provided as one of the many demos available to FDL users.