photo credit: rednivaram via photopin cc
Most readers of this blog won’t have realised (mainly because I queued up last week’s blog posts in advance of my trip) that I was in India for the whole of last week. Not that I’m under any illusions that there are people out there wondering where I am, but I did want to talk a little about my trip – and my connection to India – as the topic of today’s post.
I’ve been visiting Bangalore since I was a child: my parents met when my father was working there as an ex-pat for Monotype Corporation Ltd. in the 1960s, and while (due to an accident of fate and, to some degree, politics) they ended up moving to the UK before I was born, I regularly visited my family in India during my childhood and retained a strong connection to the city.
Some time after starting work at Autodesk – and specifically within the Autodesk Developer Network team – I was happy to find that we were planning to build a small team based in Bangalore, and that I would end up having the opportunity to visit the city regularly (I went there for the first time for work in 1998, I think, and have been travelling back there regularly since).
I even ended up moving to Bangalore from 2003-2005, to help build a much larger team that would deliver consulting projects for customers as well as services through ADN. And while my wife and I hadn’t originally planned on having our first child there, being close to my family in India during that period did have some benefits. It was also during this period that I had my first experience with blogging: I started writing an internal (meaning “only visible to Autodesk employees”) blog about my experiences of living in India. I’m pretty sure it was mostly read by the “desi” community in the US (who apparently – and happily – found my experiences entertaining).
Looking back, over the years I’ve been heavily involved in hiring and educating our Bangalore-based team – many of whom have now moved to other locations and to other roles within the company – and perhaps have a stronger connection to that team than to any of our other teams around the world.
So while this trip was primarily about the last of our DevDay events of the season – as Jim reported on his blog – it was also an opportunity to spend time with the members of the team there. A fitting “final trip” within my current role in ADN.
Thanks to all of DevTech India for (as ever) making me feel so welcome. Viru, Partha, Balaji, Anand and Sandeep: I hope to see you all again, soon (although next time I expect it’ll be with my family, which will also be fun :-).
To follow on from this recent topic, today’s post looks at a simple script to generate various hyperbolic tessellations, laying them out in an order that makes some sense of the progressive nature of the patterns that can be generated using the HT command.
Here’s an AutoCAD script (which can be saved as an .scr and executed using the SCRIPT command) to generate all the valid {n k} patterns where n <= 11 and k <= 7 (n being the number of sides in each polygon, k is the number of polygons that meet at each vertex). The application module implementing the HT command (using the code in the previous post, must be NETLOADed before this script will function properly, of course).
_zoom _w 0,0 50,25
; k=3 series
_text _j _m 25,5 0.2 0 {7 3}
_circle 25,5 2 _ht l 7 3 _s
_text _j _m 30,5 0.2 0 {8 3}
_circle 30,5 2 _ht l 8 3 _s
_text _j _m 35,5 0.2 0 {9 3}
_circle 35,5 2 _ht l 9 3 _s
_text _j _m 40,5 0.2 0 {10 3}
_circle 40,5 2 _ht l 10 3 _s
_text _j _m 45,5 0.2 0 {11 3}
_circle 45,5 2 _ht l 11 3 _s
; k=4 series
_text _j _m 15,10 0.2 0 {5 4}
_circle 15,10 2 _ht l 5 4 _s
_text _j _m 20,10 0.2 0 {6 4}
_circle 20,10 2 _ht l 6 4 _s
_text _j _m 25,10 0.2 0 {7 4}
_circle 25,10 2 _ht l 7 4 _s
_text _j _m 30,10 0.2 0 {8 4}
_circle 30,10 2 _ht l 8 4 _s
_text _j _m 35,10 0.2 0 {9 4}
_circle 35,10 2 _ht l 9 4 _s
_text _j _m 40,10 0.2 0 {10 4}
_circle 40,10 2 _ht l 10 4 _s
_text _j _m 45,10 0.2 0 {11 4}
_circle 45,10 2 _ht l 11 4 _s
; k=5 series
_text _j _m 10,15 0.2 0 {4 5}
_circle 10,15 2 _ht l 4 5 _s
_text _j _m 15,15 0.2 0 {5 5}
_circle 15,15 2 _ht l 5 5 _s
_text _j _m 20,15 0.2 0 {6 5}
_circle 20,15 2 _ht l 6 5 _s
_text _j _m 25,15 0.2 0 {7 5}
_circle 25,15 2 _ht l 7 5 _s
_text _j _m 30,15 0.2 0 {8 5}
_circle 30,15 2 _ht l 8 5 _s
_text _j _m 35,15 0.2 0 {9 5}
_circle 35,15 2 _ht l 9 5 _s
_text _j _m 40,15 0.2 0 {10 5}
_circle 40,15 2 _ht l 10 5 _s
_text _j _m 45,15 0.2 0 {11 5}
_circle 45,15 2 _ht l 11 5 _s
; k=6 series
_text _j _m 10,20 0.2 0 {4 6}
_circle 10,20 2 _ht l 4 6 _s
_text _j _m 15,20 0.2 0 {5 6}
_circle 15,20 2 _ht l 5 6 _s
_text _j _m 20,20 0.2 0 {6 6}
_circle 20,20 2 _ht l 6 6 _s
_text _j _m 25,20 0.2 0 {7 6}
_circle 25,20 2 _ht l 7 6 _s
_text _j _m 30,20 0.2 0 {8 6}
_circle 30,20 2 _ht l 8 6 _s
_text _j _m 35,20 0.2 0 {9 6}
_circle 35,20 2 _ht l 9 6 _s
_text _j _m 40,20 0.2 0 {10 6}
_circle 40,20 2 _ht l 10 6 _s
_text _j _m 45,20 0.2 0 {11 6}
_circle 45,20 2 _ht l 11 6 _s
; k=7 series
_text _j _m 5,25 0.2 0 {3 7}
_circle 5,25 2 _ht l 3 7 _s
_text _j _m 10,25 0.2 0 {4 7}
_circle 10,25 2 _ht l 4 7 _s
_text _j _m 15,25 0.2 0 {5 7}
_circle 15,25 2 _ht l 5 7 _s
_text _j _m 20,25 0.2 0 {6 7}
_circle 20,25 2 _ht l 6 7 _s
_text _j _m 25,25 0.2 0 {7 7}
_circle 25,25 2 _ht l 7 7 _s
_text _j _m 30,25 0.2 0 {8 7}
_circle 30,25 2 _ht l 8 7 _s
_text _j _m 35,25 0.2 0 {9 7}
_circle 35,25 2 _ht l 9 7 _s
_text _j _m 40,25 0.2 0 {10 7}
_circle 40,25 2 _ht l 10 7 _s
_text _j _m 45,25 0.2 0 {11 7}
_circle 45,25 2 _ht l 11 7 _s
_zoom _e
Just looking at the output results (extracted manually from the command-line output), we can see the level used and the number of polygons created for each tessellation:
{7 3} (level 5) => 617 polygons.
{8 3} (level 4) => 609 polygons.
{9 3} (level 3) => 271 polygons.
{10 3} (level 3) => 421 polygons.
{11 3} (level 3) => 617 polygons.
{5 4} (level 4) => 761 polygons.
{6 4} (level 3) => 505 polygons.
{7 4} (level 2) => 127 polygons.
{8 4} (level 2) => 177 polygons.
{9 4} (level 2) => 235 polygons.
{10 4} (level 2) => 301 polygons.
{11 4} (level 2) => 375 polygons.
{4 5} (level 4) => 913 polygons.
{5 5} (level 3) => 841 polygons.
{6 5} (level 2) => 199 polygons.
{7 5} (level 2) => 295 polygons.
{8 5} (level 2) => 409 polygons.
{9 5} (level 2) => 541 polygons.
{10 5} (level 2) => 691 polygons.
{11 5} (level 2) => 859 polygons.
{4 6} (level 3) => 673 polygons.
{5 6} (level 2) => 221 polygons.
{6 6} (level 2) => 361 polygons.
{7 6} (level 2) => 533 polygons.
{8 6} (level 2) => 737 polygons.
{9 6} (level 2) => 973 polygons.
{10 6} (level 1) => 41 polygons.
{11 6} (level 1) => 45 polygons.
{3 7} (level 4) => 496 polygons.
{4 7} (level 2) => 181 polygons.
{5 7} (level 2) => 351 polygons.
{6 7} (level 2) => 571 polygons.
{7 7} (level 2) => 841 polygons.
{8 7} (level 1) => 41 polygons.
{9 7} (level 1) => 46 polygons.
{10 7} (level 1) => 51 polygons.
{11 7} (level 1) => 56 polygons.
And here are the patterns, themselves:
Just to see the difference, here are the same tessellations with curved geometry (as per the implementation in the second post in the series). Created using a simple search & replace in the above script, from “_s” to “_c”.
Thinking about future directions for this investigation… (some of which have been suggested by Alex Fielder, after previewing drafts of these posts…)
If you have your own ideas on uses and directions for this implementation, please post a comment!
Following on from the post introducing this series, and the last post focused on generating simple hyperbolic geometry, this post looks at generating hyperbolic tessellations inside AutoCAD.
Having “borrowed” some C++ code, last time, today we’re going to borrow some Java. That’s one of the great things about the C family of languages: the relatively small amount of work that’s often needed to move code between environments. :-)
This article, written by David E. Joyce, Professor of Mathematics and Computer Science at Clark University, has provided the best information I could find with regards to a hyperbolic tiling algorithm (especially thanks to its posted source code).
The algorithm works by creating a central polygon of the specified number of sides, and then – based on the other primary parameter into the algorithm, the number of polygons that meet at each vertex – it mirrors this polygon again and again in the hyperbolic plane (which means it gets smaller and a bit squished as it gets mirrored out towards the edge of the circle) in order to make up our pattern. The number of mirroring operations – and the number of resultant polygons – will depend on the number of levels (or layers): 0 means we have just the central polygon, 1 means we have that plus the layer around it, etc.
The number of levels needed to effectively fill a circle depends on the resolution needed but also greatly on the pattern. Interestingly the more even patterns (such as 7-sided polygons meeting 3 per vertex) create fewer polygons per level, but need more levels to fill a circle adequately. The patterns with larger central polygons create many more polygons per level (which is probably not that surprising, thinking about it), and so need fewer levels to fill a circle.
Rather than ask the user for the number of levels, this implementation has a coded limit on the number of polygons (which, of course, could also be asked of the user, if needed). The code starts with a default level of 6 (which is pretty high for most patterns), but quickly reduces the level by one if it finds it would result in more than 1000 polygons being created. Once it has found a level number that creates a small enough of set of polygons, it goes ahead and uses that.
In addition to the HyperbolicEngine we saw in the last post, we’re now introducing a PolygonEngine to generate polygons for a particular pattern. Here’s the C# file:
using Autodesk.AutoCAD.Geometry;
using System;
namespace HyperbolicGeometry
{
public class Polygon
{
public Point2dCollection Vertices = new Point2dCollection();
}
public class PolygonEngine
{
// The list of polygons
Polygon[] _polys;
// Previously created neighbors for the polygons
int[] _rules;
// The total number of polygons in all the layers
int _totalPolygons;
// The number through one less layer
int _innerPolygons;
public Polygon[] GetPolygons(
int n, int k, ref int layNum, int max
)
{
do
{
CountPolygons(layNum, n, k, max);
if (_totalPolygons > max)
layNum--;
}
while (_totalPolygons > max);
DeterminePolygons(n, k);
return _polys;
}
private static Polygon ConstructCenterPolygon(int n, int k)
{
// Initialize P as the center polygon in an n-k regular tiling
// Let ABC be a triangle in a regular (n,k0-tiling, where
// A is the center of an n-gon (also center of the disk),
// B is a vertex of the n-gon, and
// C is the midpoint of a side of the n-gon adjacent to B
double angleA = Math.PI / n;
double angleB = Math.PI / k;
double angleC = Math.PI / 2.0;
// For a regular tiling, we need to compute the distance s
// from A to B
double sinA = Math.Sin(angleA);
double sinB = Math.Sin(angleB);
double s =
Math.Sin(angleC - angleB - angleA) /
Math.Sqrt(1.0 - sinB * sinB - sinA * sinA);
// Determine the coordinates of the n vertices of the n-gon.
// They're all at distance s from center of the Poincare disk
Polygon p = new Polygon();
for (int i = 0; i < n; ++i)
{
p.Vertices.Add(
new Point2d(
s * Math.Cos((3 + 2 * i) * angleA),
s * Math.Sin((3 + 2 * i) * angleA)
)
);
}
return p;
}
private void CountPolygons(int layer, int n, int k, int max)
{
// Determine
// totalPolygons: the number of polygons there are through
// that many layers
// innerPolygons: the number through one less layer
_totalPolygons = 1; // count the central polygon
_innerPolygons = 0;
int a = n * (k - 3); // polygons in 1st layer joined by vertex
int b = n; // polygons in 1st layer joined by edge
int next_a, next_b;
for (int l = 1; l <= layer; ++l)
{
_innerPolygons = _totalPolygons;
if (k == 3)
{
next_a = a + b;
next_b = (n - 6) * a + (n - 5) * b;
}
else
{ // k > 3
next_a =
((n - 2) * (k - 3) - 1) * a +
((n - 3) * (k - 3) - 1) * b;
next_b = (n - 2) * a + (n - 3) * b;
}
_totalPolygons += a + b;
// If we've reached our maximum threshold, just return,
// as we won't be using this layer, anyway
if (_totalPolygons > max)
break;
a = next_a;
b = next_b;
}
}
/* Rule codes
* 0: initial polygon. Needs neighbors on all n sides
* 1: polygon already has 2 neighbors, but one less
* around corner needed
* 2: polygon already has 2 neighbors
* 3: polygon already has 3 neighbors
* 4: polygon already has 4 neighbors
*/
private void DeterminePolygons(int n, int k)
{
_polys = new Polygon[_totalPolygons];
_rules = new int[_totalPolygons];
_polys[0] = ConstructCenterPolygon(n, k);
_rules[0] = 0;
int j = 1; // index of the next polygon to create
for (int i = 0; i < _innerPolygons; ++i)
{
j = ApplyRule(i, j, n, k);
}
}
private int ApplyRule(int i, int j, int n, int k)
{
int r = _rules[i];
bool special = (r == 1);
if (special) r = 2;
int start = (r == 4) ? 3 : 2;
int quantity = (k == 3 && r != 0) ? n - r - 1 : n - r;
for (int s = start; s < start + quantity; ++s)
{
// Create a polygon adjacent to P[i]
_polys[j] = CreateNextPolygon(_polys[i], s % n, n, k);
_rules[j] = (k == 3 && s == start && r != 0) ? 4 : 3;
j++;
int m;
if (special) m = 2;
else if (s == 2 && r != 0) m = 1;
else m = 0;
for (; m < k - 3; ++m)
{
// Create a polygon adjacent to P[j-1]
_polys[j] = CreateNextPolygon(_polys[j - 1], 1, n, k);
_rules[j] = (n == 3 && m == k - 4) ? 1 : 2;
j++;
}
}
return j;
}
// Reflect P thru the point or the side indicated by the side s
// to produce the resulting polygon Q
private Polygon CreateNextPolygon(
Polygon P, int s, int n, int k
)
{
Point2d start = P.Vertices[s],
end = P.Vertices[(s + 1) % n];
Polygon Q = new Polygon();
for (int i = 0; i < n; i++)
Q.Vertices.Add(Point2d.Origin);
for (int i = 0; i < n; ++i)
{
// Reflect P[i] thru C to get Q[j]}
int j = (n + s - i + 1) % n;
Q.Vertices[j] = Reflect(start, end, P.Vertices[i]);
}
return Q;
}
// Reflect the point R across the line through A to B
public Point2d Reflect(Point2d A, Point2d B, Point2d R)
{
// Find a unit vector D in the direction of the line
double den = A.X * B.Y - B.X * A.Y;
bool straight = Math.Abs(den) < Tolerance.Global.EqualPoint;
if (straight)
{
// The less interesting case - we could do this less
// manually using AcGe
Point2d P = A;
den =
Math.Sqrt(
(A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y)
);
Point2d D =
new Point2d(
(B.X - A.X) / den,
(B.Y - A.Y) / den
);
// Reflect method
double factor =
2.0 * ((R.X - P.X) * D.X + (R.Y - P.Y) * D.Y);
return
new Point2d(
2.0 * P.X + factor * D.X - R.X,
2.0 * P.Y + factor * D.Y - R.Y
);
}
else
{
// Find the center of the circle through these points
// (this is what we really need to use this for)
double s1 = (1.0 + A.X * A.X + A.Y * A.Y) / 2.0;
double s2 = (1.0 + B.X * B.X + B.Y * B.Y) / 2.0;
Point2d C =
new Point2d(
(s1 * B.Y - s2 * A.Y) / den,
(A.X * s2 - B.X * s1) / den
);
double r = Math.Sqrt(C.X * C.X + C.Y * C.Y - 1.0);
// Reflect method
double factor =
r * r / (
(R.X - C.X) * (R.X - C.X) + (R.Y - C.Y) * (R.Y - C.Y)
);
return
new Point2d(
C.X + factor * (R.X - C.X),
C.Y + factor * (R.Y - C.Y)
);
}
}
}
}
Here’s the updated command class that includes a new command, HT, to generate polygons for a hyperbolic tessellation with a given set of parameters:
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.Colors;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System;
namespace HyperbolicGeometry
{
public class Commands
{
[CommandMethod("HT")]
public static void CreateHyperbolicTiles()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;
PromptEntityOptions peo =
new PromptEntityOptions("\nSelect circle: ");
peo.AllowNone = true;
peo.SetRejectMessage("\nMust be a circle.");
peo.AddAllowedClass(typeof(Circle), false);
PromptEntityResult per = ed.GetEntity(peo);
if (per.Status != PromptStatus.OK &&
per.Status != PromptStatus.None
)
return;
int n, k;
bool done;
do
{
PromptIntegerOptions pio =
new PromptIntegerOptions(
"\nNumber of sides for polygons"
);
pio.AllowZero = false;
pio.AllowNegative = false;
pio.AllowNone = true;
pio.DefaultValue = 7;
pio.UseDefaultValue = true;
pio.LowerLimit = 3;
pio.UpperLimit = 20;
PromptIntegerResult pir = ed.GetInteger(pio);
if (pir.Status != PromptStatus.None &&
pir.Status != PromptStatus.OK)
return;
n = pio.DefaultValue;
if (pir.Status == PromptStatus.OK)
n = pir.Value;
pio.Message =
"\nNumber of polygons meeting at each vertex";
pio.DefaultValue = 3;
pir = ed.GetInteger(pio);
if (pir.Status != PromptStatus.None &&
pir.Status != PromptStatus.OK)
return;
k = pio.DefaultValue;
if (pir.Status == PromptStatus.OK)
k = pir.Value;
done = ((n - 2) * (k - 2) > 4);
if (!done)
{
ed.WriteMessage(
"\nPlease increase values for a successful tiling."
);
}
}
while (!done);
PromptKeywordOptions pko =
new PromptKeywordOptions(
"\nUse curved or straight segments"
);
pko.Keywords.Add("Curved");
pko.Keywords.Add("Straight");
pko.Keywords.Default = "Straight";
PromptResult pr = ed.GetKeywords(pko);
if (pr.Status != PromptStatus.Keyword &&
pr.Status != PromptStatus.OK)
return;
bool straight = pr.StringResult == "Straight";
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
Circle cir = null;
if (per.Status == PromptStatus.OK)
{
cir =
tr.GetObject(per.ObjectId, OpenMode.ForRead) as Circle;
}
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, cir, straight, ptLay, lnLay, htLay
);
PolygonEngine pe = new PolygonEngine();
if (cir == null)
{
he.DrawUnitCircle();
}
// We'll default to level 6, but this will get reduced
// if resulting in > 1000 polygons
int level = 6;
Polygon[] polys = pe.GetPolygons(n, k, ref level, 1000);
if (HostApplicationServices.Current.UserBreak())
return;
ed.WriteMessage(
"\n{{{0} {1}}} (level {2}) => {3} polygons.",
n, k, level, polys.Length
);
foreach (Polygon p in polys)
{
he.DrawPolygon(p.Vertices.ToArray());
p.Vertices.Clear();
p.Vertices.Capacity = 0;
}
tr.Commit();
}
}
[CommandMethod("HGT")]
public static void CreateHyperbolicTriangles()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, null, false, ptLay, lnLay, htLay
);
he.DrawUnitCircle();
he.DrawTriangle(
new Point2d(0.8, -0.3),
new Point2d(0.2, -0.6),
new Point2d(-0.61, -0.6),
true, true
);
tr.Commit();
}
}
[CommandMethod("HGS")]
public static void CreateHyperbolicSpiro()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, null, false, ptLay, lnLay, htLay
);
he.DrawUnitCircle();
int max = 13;
for (int k = 0; k < (max - 1); k++)
{
he.DrawTriangle(
new Point2d(1, 0),
new Point2d(
Math.Cos(k * 134 / (double)max),
Math.Sin(k * 134 / (double)max)
),
new Point2d(
Math.Cos((k + 1) * 134 / (double)max),
Math.Sin((k + 1) * 134 / (double)max)
),
true, true
);
}
tr.Commit();
}
}
private static ObjectId CreateLayer(
Transaction tr, LayerTable lt,
string lname, short col, bool on
)
{
if (lt.Has(lname))
return lt[lname];
LayerTableRecord ltr = new LayerTableRecord();
ltr.Color = Color.FromColorIndex(ColorMethod.ByAci, col);
ltr.Name = lname;
ltr.IsFrozen = !on;
ObjectId layId = lt.Add(ltr);
tr.AddNewlyCreatedDBObject(ltr, true);
return layId;
}
}
}
When we run the HT command we have a number of options. We can either select a circle to fill, or hit Enter to have it create a standard circle at the origin, and then are asked to enter the number of sides of the polygons, the number meeting at each vertex, and the number of levels. We’re also asked whether to straight or curved segments (and it’s in the case of curved segments that the code we showed in the last post gets exercised).
Let’s see the results of running the HT command with the default option values selected:
Command: HT
Select circle:
Number of sides for polygons <7>:
Number of polygons meeting at each vertex <3>:
Use curved or straight segments [Curved/Straight] <Straight>:
{7 3} (level 5) => 617 polygons.
We can see that our {7 3} tessellation has resulted in 617 polygons being created. The various patterns generated by this algorithm have a single, central polygon. Other algorithms can also generate a group of polygons centered on the circle – this shouldn’t be overly difficult to implement, but has been left as an exercise for the engaged reader. :-)
Just to see, we can try the same operation with curved segments instead of straight, which will exercise the code in the last post but not actually make a very noticeable difference to the results (the resultant arcs mostly have very low curvature).
I’ll follow up with one more post in this series, to script the HT command to create a varied range of the patterns that can be created with the current implementation.
Also, if people are interested in thinking about how this might be taken to the next dimension (i.e. 3D), then this document should be interesting: it even looks at the possibilities around printing 3D hyperbolic tessellations, although it tends to do so more from an artistic – rather than structural – perspective.
As mentioned in the last post, today’s post looks at how to draw hyperbolic geometry using the Poincaré disk model inside AutoCAD.
This is an interesting exercise, but probably won’t ultimately help us with the hyperbolic tessellations we’re aiming to create: it’s interesting as it will end up with us having a mechanism for mapping hyperbolic geometry onto an arbitrary circle inside AutoCAD, but as we’re probably going to end up creating straight-lined segments for the polygons we use to create our pattern, it’s mostly an exercise (and will probably be largely irrelevant to our end result). The tough part actually comes in the next post, when we move on to the tessellation algorithm.
To get started, I managed to find a straightforward C++ implementation of a set of functions to create hyperbolic geometry on a Poincaré disk. This library was developed by by David Coeurjolly, Research Director for the team focused on Multiresolution, Discrete and Combinatorial Models at LIRIS (Laboratoire d'InfoRmatique en Image et Systèmes d'information), part of the CNRS (Centre National de la Recherche Scientifique) in France. David’s implementation makes use of the Cairo graphics library, so there was a modest amount of work needed to generate geometry inside AutoCAD, instead. Indeed this was the main focus of my efforts: I fully admit I haven’t spent much time looking at the underlying mathematics (in particular, please don’t ask me to explain how the radius is calculated in the ComputeCircleParameters() method… ;-).
Here’s the resultant C# file containing the library class I’ve named HyperbolicEngine (for want of a better term):
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Geometry;
using System;
namespace HyperbolicGeometry
{
public class HyperbolicEngine
{
// We'll hold some AutoCAD objects to provide quick access
// to the drawing database
Transaction _tr;
Database _db;
BlockTableRecord _btr;
// We'll also hold information about the target circle
double _radius;
Point3d _center;
Matrix3d _disp;
// Whether we'll draw curved or straight lines
bool _straight;
// Target layers for points, supporting lines and our
// actual geometry
ObjectId _ptLay, _lnLay, _hgLay;
// Constructor
public HyperbolicEngine(
Transaction tr,
Database db,
Circle cir,
bool straight,
ObjectId? ptLay = null,
ObjectId? lnLay = null,
ObjectId? hgLay = null
)
{
_tr = tr;
_db = db;
if (cir == null)
{
_radius = 400;
_center = Point3d.Origin;
}
else
{
_center = cir.Center;
_radius = cir.Radius;
}
_disp = Matrix3d.Displacement(_center - Point3d.Origin);
_btr =
(BlockTableRecord)tr.GetObject(
db.CurrentSpaceId, OpenMode.ForWrite
);
_straight = straight;
_ptLay = ptLay.HasValue ? ptLay.Value : db.Clayer;
_lnLay = lnLay.HasValue ? lnLay.Value : db.Clayer;
_hgLay = hgLay.HasValue ? hgLay.Value : db.Clayer;
}
// Functions to map a point from the unit disk to WCS
private Point3d WcsPoint(double x, double y)
{
Point3d pt = new Point3d(cX(x), cY(y), 0);
return pt.TransformBy(_disp);
}
private double cX(double x)
{
return x * _radius;
}
private double cY(double y)
{
return y * _radius;
}
/*
* Compute the circle containing points a and b, and
* orthogonal to the unit circle (a.k.a shortest path between
* a and b in the hyperbolic sense).
*
* Return true if the output is a circle. False if the
* shortest path is a straight line (diameter of the unit
* circle).
*/
private static bool ComputeCircleParameters(
Point2d a, Point2d b,
out double cx, out double cy, out double radius
)
{
double ax = a.X, ay = a.Y, bx = b.X, by = b.Y;
cx = 0; cy = 0; radius = 0;
if (Math.Abs(ax * by - ay * bx) < Tolerance.Global.EqualPoint)
return false;
cx =
(-1 / 2.0 *
(ay * bx * bx + ay * by * by -
(ax * ax + ay * ay + 1) * by + ay
)
/ (ax * by - ay * bx)
);
cy =
(1 / 2.0 *
(ax * bx * bx + ax * by * by -
(ax * ax + ay * ay + 1) * bx + ax
)
/ (ax * by - ay * bx)
);
radius =
-1 / 2.0 * Math.Sqrt(
ax * ax * ax * ax * bx * bx +
ax * ax * ax * ax * by * by -
2 * ax * ax * ax * bx * bx * bx -
2 * ax * ax * ax * bx * by * by +
2 * ax * ax * ay * ay * bx * bx +
2 * ax * ax * ay * ay * by * by -
2 * ax * ax * ay * bx * bx * by -
2 * ax * ax * ay * by * by * by +
ax * ax * bx * bx * bx * bx +
2 * ax * ax * bx * bx * by * by +
ax * ax * by * by * by * by -
2 * ax * ay * ay * bx * bx * bx -
2 * ax * ay * ay * bx * by * by +
ay * ay * ay * ay * bx * bx +
ay * ay * ay * ay * by * by -
2 * ay * ay * ay * bx * bx * by -
2 * ay * ay * ay * by * by * by +
ay * ay * bx * bx * bx * bx +
2 * ay * ay * bx * bx * by * by +
ay * ay * by * by * by * by -
2 * ax * ax * ax * bx -
2 * ax * ax * ay * by +
4 * ax * ax * bx * bx -
2 * ax * ay * ay * bx +
8 * ax * ay * bx * by -
2 * ax * bx * bx * bx -
2 * ax * bx * by * by -
2 * ay * ay * ay * by +
4 * ay * ay * by * by -
2 * ay * bx * bx * by -
2 * ay * by * by * by +
ax * ax - 2 * ax * bx +
ay * ay - 2 * ay * by +
bx * bx + by * by
)
/ (ax * by - ay * bx);
if (radius < 0.0)
radius =
1 / 2.0 * Math.Sqrt(
ax * ax * ax * ax * bx * bx +
ax * ax * ax * ax * by * by -
2 * ax * ax * ax * bx * bx * bx -
2 * ax * ax * ax * bx * by * by +
2 * ax * ax * ay * ay * bx * bx +
2 * ax * ax * ay * ay * by * by -
2 * ax * ax * ay * bx * bx * by -
2 * ax * ax * ay * by * by * by +
ax * ax * bx * bx * bx * bx +
2 * ax * ax * bx * bx * by * by +
ax * ax * by * by * by * by -
2 * ax * ay * ay * bx * bx * bx -
2 * ax * ay * ay * bx * by * by +
ay * ay * ay * ay * bx * bx +
ay * ay * ay * ay * by * by -
2 * ay * ay * ay * bx * bx * by -
2 * ay * ay * ay * by * by * by +
ay * ay * bx * bx * bx * bx +
2 * ay * ay * bx * bx * by * by +
ay * ay * by * by * by * by -
2 * ax * ax * ax * bx -
2 * ax * ax * ay * by +
4 * ax * ax * bx * bx -
2 * ax * ay * ay * bx +
8 * ax * ay * bx * by -
2 * ax * bx * bx * bx -
2 * ax * bx * by * by -
2 * ay * ay * ay * by +
4 * ay * ay * by * by -
2 * ay * bx * bx * by -
2 * ay * by * by * by +
ax * ax - 2 * ax * bx +
ay * ay - 2 * ay * by +
bx * bx + by * by
)
/ (ax * by - ay * bx);
return true;
}
// Draw the unit circle
public void DrawUnitCircle()
{
if (_tr != null && _btr != null)
{
Circle c = new Circle(_center, Vector3d.ZAxis, _radius);
c.LayerId = _hgLay;
_btr.AppendEntity(c);
_tr.AddNewlyCreatedDBObject(c, true);
}
}
// Draw a point in the Poincare disc
public void DrawPoint(Point2d a)
{
if (_tr != null && _btr != null)
{
DBPoint p = new DBPoint(WcsPoint(a.X, a.Y));
p.LayerId = _ptLay;
_btr.AppendEntity(p);
_tr.AddNewlyCreatedDBObject(p, true);
}
}
// Draw a hyperbolic line through a and b
public void DrawSupportingLine(
Point2d a, Point2d b, bool withPoints
)
{
if (withPoints)
{
DrawPoint(a);
DrawPoint(b);
}
double ax = a.X, ay = a.Y, bx = b.X, by = b.Y;
double cx, cy, r;
bool result =
ComputeCircleParameters(a, b, out cx, out cy, out r);
Entity ent;
if (!result)
{
// We project a and b points onto the unit circle
double theta = Math.Atan2(ay, ax);
double theta2 = Math.Atan2(by, bx);
ent =
new Line(
WcsPoint(Math.Cos(theta), Math.Sin(theta)),
WcsPoint(Math.Cos(theta2), Math.Sin(theta2))
);
}
else
{
ent =
new Circle(WcsPoint(cx, cy), Vector3d.ZAxis, r * _radius);
}
if (ent != null)
{
ent.LayerId = _lnLay;
if (_tr != null && _btr != null)
{
_btr.AppendEntity(ent);
_tr.AddNewlyCreatedDBObject(ent, true);
}
else
{
ent.Dispose();
}
}
}
// Draw a hyperbolic edge between a and b
public void DrawEdge(
Point2d a, Point2d b, bool withPoints,
bool straightSegments = false
)
{
if (withPoints)
{
DrawPoint(a);
DrawPoint(b);
}
double ax = a.X, ay = a.Y, bx = b.X, by = b.Y;
double cx = 0.0, cy = 0.0, r = 0.0;
bool result =
_straight ? false :
ComputeCircleParameters(a, b, out cx, out cy, out r);
// Near-aligned points -> straight segment
Entity ent = null;
if (!result)
{
ent = new Line(WcsPoint(ax, ay), WcsPoint(bx, by));
}
else
{
double theta = -Math.Atan2(-ay + cy, ax - cx);
double theta2 = -Math.Atan2(-by + cy, bx - cx);
// We recenter the angles to [0, 2Pi]
while (theta < 0)
{
theta += 2 * Math.PI;
}
while (theta2 < 0)
{
theta2 += 2 * Math.PI;
}
Point3d cen = WcsPoint(cx, cy);
double delta = Math.Abs(theta - theta2);
if (
(theta > theta2 && delta > Math.PI) ||
(theta < theta2 && delta < Math.PI)
)
{
ent = new Arc(cen, r * _radius, theta, theta2);
}
else
{
ent = new Arc(cen, r * _radius, theta2, theta);
}
}
if (ent != null)
{
ent.LayerId = _hgLay;
if (_tr != null && _btr != null)
{
_btr.AppendEntity(ent);
_tr.AddNewlyCreatedDBObject(ent, true);
}
else
{
ent.Dispose();
}
}
}
// Draw a hyperbolic triangle with vertices (a,b,c)
public void DrawTriangle(
Point2d a, Point2d b, Point2d c,
bool withPoints = false, bool withSupportLines = false
)
{
DrawPolygon(
new Point2d[] { a, b, c }, withPoints, withSupportLines
);
}
// Draw a hyperbolic polygon with the provided vertices
public void DrawPolygon(
Point2d[] pts, bool withPoints = false,
bool withSupportLines = false
)
{
if (withPoints)
{
foreach (Point2d pt in pts)
{
DrawPoint(pt);
}
}
int numPts = pts.Length;
if (withSupportLines && !_straight)
{
for (int i = 0; i < numPts; i++)
{
DrawSupportingLine(
pts[i], pts[(i + 1) % numPts], withPoints
);
}
}
for (int i = 0; i < numPts; i++)
{
DrawEdge(
pts[i], pts[(i + 1) % numPts], withPoints
);
}
}
}
}
Here’s the command class implementation:
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.Colors;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System;
namespace HyperbolicGeometry
{
public class Commands
{
[CommandMethod("HGT")]
public static void CreateHyperbolicTriangles()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, null, false, ptLay, lnLay, htLay
);
he.DrawUnitCircle();
he.DrawTriangle(
new Point2d(0.8, -0.3),
new Point2d(0.2, -0.6),
new Point2d(-0.61, -0.6),
true, true
);
tr.Commit();
}
}
[CommandMethod("HGS")]
public static void CreateHyperbolicSpiro()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, null, false, ptLay, lnLay, htLay
);
he.DrawUnitCircle();
int max = 13;
for (int k = 0; k < (max - 1); k++)
{
he.DrawTriangle(
new Point2d(1, 0),
new Point2d(
Math.Cos(k * 134 / (double)max),
Math.Sin(k * 134 / (double)max)
),
new Point2d(
Math.Cos((k + 1) * 134 / (double)max),
Math.Sin((k + 1) * 134 / (double)max)
),
true, true
);
}
tr.Commit();
}
}
private static ObjectId CreateLayer(
Transaction tr, LayerTable lt,
string lname, short col, bool on
)
{
if (lt.Has(lname))
return lt[lname];
LayerTableRecord ltr = new LayerTableRecord();
ltr.Color = Color.FromColorIndex(ColorMethod.ByAci, col);
ltr.Name = lname;
ltr.IsFrozen = !on;
ObjectId layId = lt.Add(ltr);
tr.AddNewlyCreatedDBObject(ltr, true);
return layId;
}
}
}
The code implements two commands, both of which have been lifted fairly directly from David’s test cases.
Here are the results of running the HGT command:
And if you turn on the layer showing the supporting lines (HG_LNS), you’ll see the circles used to generated these arcs:
The HGS command creates more interesting geometry:
Which, of course, also has more interesting supporting lines along with it:
You can certainly see similarities between geometry on a Poincaré disk and the hypocycloids generated by Spiro.
Next time we’ll look at hyperbolic tessellations and how to generate them inside AutoCAD.
A regular follower of this blog and someone I now consider a friend through our online interactions, Alex Fielder, recently laid down the gauntlet for the topic of the coming series of posts.
He started with Twitter…
… and then moved on to The Swamp (which he thankfully also brought to my attention using Twitter).
Alex has become interested in an area that I can see becoming increasingly relevant: given the fact that 3D printing is an additive, rather than subtractive or mold-based, process, shouldn’t we take advantage of this fact to optimise the composition of an object’s internal structure? This optimisation could bring benefits in terms of cost and weight (as we can use less material) or strength (as we can add structure that increases tensile strength). And it seems he’s not alone, in thinking along these lines.
The more I think about it, myself – and I admit this is a long way from being my field of specialization – this feels like it has the potential to be a real game-changer. And when you can hook up simulation and analysis tools to provide information on optimal fill patterns, things become really interesting.
But anyway – first things first. Clearly the ideal would be to tackle this kind of challenge in 3D (I don’t know of any 3D printers that take third angle projection input ;-), but you have to start somewhere.
Alex’s post pointed us, quite specifically, at hyperbolic tessellation as a technique for generating fill patterns (see this article for an idea of the possibilities):
Alex had suggested my Spiro app (which is also posted as a Plugin of the Month on Autodesk Labs), as being a potential starting point for this.
After looking into it, it seemed to make more sense to attack this a bit differently than my work on Spiro (which used an approach of collecting a set of points to generate a single polyline).
Also, getting my head around the underlying mathematics was going to be a challenge, so I knew I was going to need to borrow some code from somewhere for this, anyway. Alex also suggested that my series of posts on turtle graphics might also be a good starting point – and this also occurred to me – although a lot would depend on the ultimate algorithm I ended up finding (and whether this kind of tiling could be generated in the hyperbolic plane using L-systems).
To get started on this, I decided to look into two main areas, each of which will be addressed by posts next week:
There seem to be a few approaches for defining hyperbolic geometry: the most popular appears to be the Poincaré disk model – which connects points using circular arcs – and the Klein disk model – which connects points using straight lines (at least that appears to be the difference from my – probably ill-informed – viewpoint… I have no doubt there are more subtle differences that I’m missing).
We don’t care very much about the underlying mathematics, at the end of the day, as this is really about the generated pattern. In the next post, we’ll look at getting a straightforward Poincaré disk (something akin to this one) implemented inside AutoCAD, and then (most likely) disregard it in the following post, where we generate hyperbolic tessellations using straight-line segments to connect our points. At least that’s my expectation. :-)
Incidentally, for those interested in the domain of 3D printing, there’s a Singularity University live webcast coming up on January 24, 2012 that you’re likely to find interesting (it also has Carl Bass, Autodesk’s CEO, as guest speaker):
Advances in fields such as artificial intelligence, robotics, and digital manufacturing are undoubtedly going to revolutionize manufacturing during this decade, enabling us to design and “print” complex products and “manufacture” these in our own homes. Exponentially advancing technologies will provide major new opportunities for entrepreneurs to create world-changing technologies. But they also may threaten industries and jobs across the world.
What are these technologies, where exactly do the opportunities lie, and where will the jobs go? These are some of the topics that Autodesk CEO Carl Bass and Singularity University VP of Academics and Innovation Vivek Wadhwa will discuss in the next Which Way Next?
Which Way Next?
A Singularity University Live Webcast
Guest: Carl Bass, CEO of Autodesk Inc.
Commentator: Vivek Wadhwa, Singularity University
Topic: AI, Robotics and Digital Manufacturing
Date: Tuesday, January 24, 2012
Time: LIVE at 12:30 PM (Pacific)
Log-in to participate & submit questions: www.singularityu.org
I mentioned some time ago that our Localization Services (LS) team was embarking on a community-based translation of Homestyler into Russian.
The fruits of this labour are now ready for testing: the various translation projects, for the application, for its content and for supporting web-pages are now 100% complete. But that’s not to say things haven’t been missed or mis-translated, so we would love to get feedback from Russian speakers on the quality of the work performed.
The below information has been provided by our LS team for people who are interested in taking Russian Homestyler for a spin (and ideally providing feedback, of course).
Be warned that these steps involve editing a core system file, and so clearly require a certain level of comfort with making such changes as well as appropriate permissions on your testing machine.
%windir%\System32\drivers\etc\hosts
107.22.29.153 www.ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 it.ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 ru.ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 en.ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 es.ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 pt.ec2-107-22-29-153.compute-1.amazonaws.com
107.22.29.153 fr.ec2-107-22-29-153.compute-1.amazonaws.com
You should then be able to use the Homestyler application – just as you would in English – but with the various parts of the product translated into Russian:
To provide feedback on the quality of the translated products, please send us an email. If you’re reporting a problem, please make sure your email contains this information:
And finally, a huge thanks to the top community contributors to this translation effort. Without your efforts this groundbreaking project would not have been a success!
Update
The Russian version of Homestyler has now joined the list of official languages in the product, so there's no need to follow steps 1-3 above to gain access to it (simply click here).
A couple of recent posts have covered different ways of checking whether a point is on a curve. This post looks at a rudimentary way of profiling the relative performance of these various methods, in order to determine the best approach to use, in general.
There are various performance profiling technologies available on the market, but given the specificity of the cases we wanted to test and compare, I rolled my own very simple approach. Nothing at all earth-shattering, just a helper function that will call one of our methods (passed in as a delegate with a specific signature) a set number of times, and return the elapsed time (in seconds) for that set of operations.
For instance, we are typically calling our various functions 100K times, and in each set of calls using different combinations of object type, function and point (whether on or off the curve in question). The duration of each set of 100K operations gets returned to the calling function, which then saves the information for the various sets out to a CSV file for easy loading into Excel.
Each run of the POC command creates a new CSV file, so there is some manual work still involved to copy & paste into a central file to compare the results: this could also be automated, but the law of diminishing returns led me to draw the line here (it’s really a one-off investigation, not a regularly-run performance benchmark). You may choose to drawn the line elsewhere in your own, regularly-run performance analyses, of course.
A few things to bear in mind: our ProfileMethod() function checks for the elapsed time between the beginning and the end of the set of calls. Lots of things can contribute to the operations taking time, so it's worth running the various tests multiple times and comparing the results. That's certainly what I did before settling on the results at the bottom of this post.
Here’s the C# code:
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System.IO;
using System;
namespace CurveTesting
{
public delegate bool IsPointOnCurveDelegate(Curve cv, Point3d pt);
public class Commands
{
[CommandMethod("POC")]
public void PointOnCurve()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;
PromptEntityOptions peo =
new PromptEntityOptions("\nSelect a curve");
peo.SetRejectMessage("Please select a curve");
peo.AddAllowedClass(typeof(Curve), false);
PromptEntityResult per = ed.GetEntity(peo);
if (per.Status != PromptStatus.OK)
return;
PromptPointResult ppr = ed.GetPoint("\nSelect a point");
if (ppr.Status != PromptStatus.OK)
return;
Transaction tr = db.TransactionManager.StartTransaction();
using (tr)
{
Curve cv =
tr.GetObject(per.ObjectId, OpenMode.ForRead) as Curve;
if (cv != null)
{
StreamWriter sw =
File.CreateText(GetFileName(cv));
sw.WriteLine(
"GCP (On),GCP (Off),GDAP (On),GDAP (Off),PL (On),PL (Off)"
);
// Let's repeat each method call 100K times
const int reps = 100000;
// We measure up to 6 sets of calls per object
// (6 for Polylines, 4 for other Curves)
// The calls with Point3d.Origin being passed as the
// point should result in the point being off the curve
// (unless the test data happens to have geometry
// going through the origin)
double d1, d2, d3, d4, d5, d6;
d1 =
ProfileMethod(
IsPointOnCurveGCP, cv, ppr.Value, reps
);
d2 =
ProfileMethod(
IsPointOnCurveGCP, cv, Point3d.Origin, reps
);
d3 =
ProfileMethod(
IsPointOnCurveGDAP, cv, ppr.Value, reps
);
d4 =
ProfileMethod(
IsPointOnCurveGDAP, cv, Point3d.Origin, reps
);
// For Polylines we have an additional method we can use
Polyline pl = cv as Polyline;
if (pl != null)
{
d5 =
ProfileMethod(
IsPointOnCurvePL, cv, ppr.Value, reps
);
d6 =
ProfileMethod(
IsPointOnCurvePL, cv, Point3d.Origin, reps
);
sw.WriteLine(
"{0},{1},{2},{3},{4},{5}", d1, d2, d3, d4, d5, d6
);
}
else
{
sw.WriteLine(
"{0},{1},{2},{3}", d1, d2, d3, d4
);
}
sw.Close();
}
tr.Commit();
}
}
// Return a unique filename in the root folder on C:\
private string GetFileName(Curve cv)
{
int i = 0;
string fname;
do
{
fname =
"c:\\results for " + cv.GetType().Name +
(i > 0 ? i.ToString() : "") + ".csv";
i++;
}
while (File.Exists(fname));
return fname;
}
// Run a specific function a certain number of times, returning
// the elapsed time in seconds
private double ProfileMethod(
IsPointOnCurveDelegate fn, Curve cv, Point3d pt, int reps
)
{
DateTime start = DateTime.Now;
for (int i = 0; i < reps; i++)
{
fn(cv, pt);
}
TimeSpan elapsed = DateTime.Now - start;
return elapsed.TotalSeconds;
}
// A generalised IsPointOnCurve function that works on all
// types of Curve (including Polylines), but catches an
// Exception on failure
private bool IsPointOnCurveGDAP(Curve cv, Point3d pt)
{
try
{
// Return true if operation succeeds
cv.GetDistAtPoint(pt);
return true;
}
catch { }
// Otherwise we return false
return false;
}
// A generalised IsPointOnCurve function that works on all
// types of Curve (including Polylines), and checks the position
// of the returned point rather than relying on catching an
// exception
private bool IsPointOnCurveGCP(Curve cv, Point3d pt)
{
try
{
// Return true if operation succeeds
Point3d p = cv.GetClosestPointTo(pt, false);
return (p - pt).Length <= Tolerance.Global.EqualPoint;
}
catch { }
// Otherwise we return false
return false;
}
// A manual approach that works specifically for polylines
private bool IsPointOnCurvePL(Curve cv, Point3d pt)
{
bool isOn = false;
Polyline pl = cv as Polyline;
if (pl != null)
{
for (int i = 0; i < pl.NumberOfVertices; i++)
{
Curve3d seg = null;
SegmentType segType = pl.GetSegmentType(i);
if (segType == SegmentType.Arc)
seg = pl.GetArcSegmentAt(i);
else if (segType == SegmentType.Line)
seg = pl.GetLineSegmentAt(i);
if (seg != null)
{
isOn = seg.IsOn(pt);
if (isOn)
break;
}
}
}
return isOn;
}
}
}
Here’s a graph plotting the CSV file from various objects the POC command has been executed against:
Some observations:
Let’s take a look at just the data for the GetClosestPoint implementation, the best overall approach to use for testing whether a point is on a curve:
Interestingly circles have quite a high relative cost. That said, I assume the first three are fixed, while polylines and splines will presumably get more expensive as the number of segments/control points increase: the test data used a 10-segment polyline and a spline with 7 control points – both of a modest size.
If anyone has additional thoughts on this analysis – whether you’ve seen similar behaviour or there’s something I’ve missed – please do post a comment.
I’m delighted to be announcing that Jim Quanci, Director of the Autodesk Developer Network, has started a blog on partnering with large companies such as Autodesk: Dances with Elephants. I know Jim has been considering writing a blog for some time, and I’m really happy he’s managed to find the time in his busy schedule to get this one going.
I’ve worked with Jim pretty much since I started at Autodesk, and have reported directly to him for the last 6.5 years (although that will change in a few short weeks). I’m definitely going to miss being part of his team – and having him as a boss – but I fully expect to be in regular contact with him in my new role, and may even see him more often, depending on the frequency of my trips to the Bay Area.
Be sure to bookmark Jim’s blog and check it from time to time – I have no doubt it’ll be a great read, whether you’re currently partnering with Autodesk, considering doing so, or just have an interest in understanding the dynamics between independent software developers and their platform providers.
photo credit: jidanchaomian via photopin cc
As expected, Microsoft has announced at CES 2012 that Kinect for Windows devices will become available from February 1st, priced at $249. Those of you who attended my Kinect class at AU 2011 will probably remember me speculating about the eventual cost for this device, and that it would preferable for Microsoft to recoup more of their technology investment from the physical devices than they had from the equivalent devices for Xbox 360, and therefore avoid developers having to pay Microsoft directly for the use of their SDK. I think I suggested it’d be fine to pay $200 or more for the device (it’s a bit of a blur, at this stage), and Microsoft’s proposed $249 doesn’t strike me as at all excessive.
We have chosen a hardware-only business model for Kinect for Windows, which means that we will not be charging for the SDK or the runtime; these will be available free to developers and end-users respectively. As an independent developer, IT manager, systems integrator, or ISV, you can innovate with confidence knowing that you will not pay license fees for the Kinect for Windows software or the ongoing software updates, and the Kinect for Windows hardware you and your customers use is supported by Microsoft.
Clearly I see this as being really good news: while the existing Kinect for Xbox 360 hardware can be used when developing applications, when they are released commercially (or even non-commercially) they will only be able to target the more expensive Kinect for Windows hardware, and developers will be able to continue to use the excellent Kinect SDK to their heart’s content. Fair enough.
I know at least a few people left AU with the intention to investigate using Kinect technology in interesting ways. Has anyone come up with any interesting uses for it, as yet? (Feel free to drop me an email, if you’re shy about posting a comment.)
Subscribe via RSS