Freesteel Blog » 2006 » December

Tuesday, December 19th, 2006 at 5:15 pm - - Machining 2 Comments »

Sometimes you need to check if your calculations are working by plotting the normal vector at each point in the CADCAM model. Some people call this the hedgehog view, as opposed to the solid view, wireframe view, perspective view, etc.

Here I’ve finally managed to get the hedgehog view working for z-profile toolpaths of a tapered tool against a model that is composed of one line segment (not drawn). The hedgehog’s spike vectors are the normals to the plane passing through the contact point separating the model from the tool shape. For points of contact on the smooth faces of the tool, as opposed to a ridge, it’s the normal vector to the face at that point. It’s always perpendicular to the line.

Tapered tools are not simple shapes. I’m going to draw one in SVG at some point; the standard definition of them is a bit mixed up. Basically, you have the flat tip, the corner radius, the conical section, the corner between the top of the cone and the cylindrical shaft, and the cylindrical shaft. The last four components can make contact with the model when it is moved horizontally through space. These components can each collide with points, edges, and facets of the triangulated model (although not every component can touch every part of the model).

In the picture there are normals representing seven different types of contact point: point/corner-radius, point/cone, point/cylinder, edge/corner-radius, edge/cone, edge.cone-cylinder-corner, and edge/cylinder. I’ve not hedge-hogged the facet, but if I did there would also be: facet/corner-radius and facet/cone-cylinder-corner. It’s not hard to get the contact normal to a facets correct; it’s simply the normal vector of the facet.

That’s the basic calculation as it is operated on a single geometric element. Applying it to the whole triangulated model is easy — you just merge all the shapes together — as long as you don’t mind a lot of wasted calculations as the accurate contact values get calculated against elements that are subsequently masked by others. A huge amount of this happens, and optimizating it out makes the whole program super-complex.

I can phrase this claim more simply. Suppose you have a list of triangles:

T = {ti | i = 1, …, 1Billion}

and a function f(t) which takes each triangle, does a very complicated calculation with it, and returns a precise floating point value. All we really need is the maximal value over the set T, or:

max{f(ti) | i = 1, …, 1Billion}

So the deal is we need to go deep into the function f(t) and totally shatter our nice clean modular hierarchical algorithm in order to take advantage of the fact that we can sometimes extract, from the internal calculations of f(t), an early estimate of its final value, which lets us throw away unfinished calculations that aren’t going to be of any use to us. This is where you get bugs — when you do this too agressively and throw away too much.

The overall structure of these implementations is not elegant, and extremely tied to the way that you solve the geometric equations. It’s not possible to predict whether calculating the solution in a less optimal manner gives rise to better partial results along the way and allows for a sufficiently greater proportion of unnecessary calculations to be thrown out to counterbalance this inefficiency.

I’ll check the code in now and let the complaints flood in.

Sunday, December 17th, 2006 at 6:52 pm - - Machining

I wasted most of the week pursuing the wrong idea for how to implement tapered cutters, unable to work out why my calculation was failing. It was because I got it completely wrong, which I found out by finally plotting what I was trying to do in 3D and looking at it very carefully.

I already had the code for generating z-constant waterline passes for a flat-bottomed cylindrical cutter by projecting it sideways until it collided with the triangulated surface.

I was pretty sure I could extend this code to work for conical shapes, where the radius was different for the top and bottom of the cylinder, by distorting the space.

Suppose the radius of the cylinder/chopped cone at zo was ro, and r1 at z1, with zo < z1 and ro < r1. Given a node point p from the triangular mesh, I would transform this to the point (s px, s py, pz) where

s = 1 + (r1/r0 – 1)(z1 – pz) / (z1 – z0)

This would tranform the cone into a cylinder, I’d work with the transformed points against the cylinder, and then reverse the transform to get the answer for the cone.

Totally wrong, since everything not centred on the origin gets smeared and changes its angle.

The way I really should have thought of it was to imagine testing the cone against a single line segment in the triangulated surface. The cone of the cutter moves horizontally through space until it collides with the line. The relative sweep of the line therefore can be represented by a plane in space tilted up at the angle of the line as it is projected into the plane perpendicular to the motion of the cone.

By embedding the line into this plane, and imagining the plane cutting the cone, it appears I would have to be able to find the tangents to an arbitrary conic section, which includes crazy curves such as the hyperbola. No wonder it wasn’t straight-forward.

Anyways, now I’m on the right track, I’ve spent the whole weekend getting it done.

For the surface parts of the cylinder and cone, as opposed to their circular end-disks, you only need to test against points and lines, but not the triangular facets; only two-way curved surfaces such as the hemispherical ball-nose can make a single-point contact in the middle of a triangle.

Thursday, December 7th, 2006 at 2:29 pm - - Machining 9 Comments »

I have made this lovely drawing of an offset ellipse in SVG which I do declare is in the public domain. Click to download.

The geometry of the offset ellipse is fundamental to many CAM operations that involve the bull-nosed/toroidal cutter. I’ll explain the applications at some later time. When your CAM system is generating cutter paths, it may be spending up to 20% of its time working on the calculation illustrated here. It would be a great resource if someone were to make a public domain version of this calculation which we could all rely on, in the same way that we rely on other sophisticated calculations, such as the cosine or sqrt.

In the diagram, the ellipse is aligned along the xy axes, with a major radius a and minor radius b. Points on the ellipse have coordinates (au, bv) where u2 + v2 = 1.

The normal to the curve at this point is parallel to (bu, av). You can prove this by setting v = (1 – u2)0.5, differentiating with respect to u to get a tangent vector that is perpendicular to this normal direction.

While the direction of the normal vector is correct, its magnitude changes for different points along the ellipse. The curve we want, which is an offset by a fixed distance t, is defined by normalizing (changing its length to become a unit) this vector.

Let the length of our normal vector be

n = |(bu, av)| = ((bu)2 + (av)2)0.5

Then a point on the offset ellipse curve has coordinates

(au + but/n, bv + avt/n)

It’s easy to plot this curve, as I have done, by looping through successive values of (u, v), say by using (cos z, sin z), find n and apply the transformation. But what we really need to have written down in some complex subroutine is a function called E(k) which, for any x = k, provides for the point (k, E(k)) to be on this offset ellipse curve.

To solve for this, we need to find u such that k =au + but/n. Then the value of E(k) = bv + avt/n is easy to determine.

The equation simplifies to (k – au)n = but. We know that:

n2 = b2u2 + a2v2 = b2u2 + a2(1 – u2) = (b2 – a2)u2 + a2


(k – au)2((b2 – a2)u2 + a2) = b2u2t2

is the equation we must solve to get the answer.

In the past I used the approach of multiplying everything out into the great big quartic equation as follows:

a2(b2 – a2)u4 – 2ak(b2 – a2)u3 + (a4 – k2(b2 – a2) – b2t2)u2 – 2a3ku + a2k2 = 0

and solve it by applying the standard methods. I’m not so convinced with this way of doing things these days, because the value of v = (1 – u2)0.5 becomes unstable near the edge when u=1. I favour numeric methods these days which respect the geometry, rather than projecting everything into one dimension that happens to have an analytic solution.

You’ll notice that the u4 and u3 terms vanish when a=b and the ellipse is a perfect circle, and more amenable to calculation, because the offset curve of a circle is also a circle. As you can see, the offset of an ellipse is not an ellipse.

I’ll update any corrections to these equations, because I am sure I’ve typed in a mistake somewhere.

Thursday, December 7th, 2006 at 10:57 am - - Weekends, Whipping

I had another wander around Prague on foot while Joshua was at his classes. The Museum of Technology on the hill on the other side of the river was closed for two years of refurbishment. The giant metronome on the former site of Stalin’s statute wasn’t swinging. And the government offices were taking delivery of a giant Xmas tree through their front door. I changed money and bought my ticket at the real main train station, not Holesovice. It was larger and much less grey and grim.


Sunday, December 3rd, 2006 at 11:16 pm - - Weekends

Not much is going to happen on the other days, because my half brother here Joshua is going to English and German classes to learn how to travel write and speak in a foreign language, while I’ll be left in a cafe to read and rest. He led me up round the back of the Prague Castle on top of the hill on the other side of the river, and we wandered around a museum there, and walked back until my feet were entirely sore from cobble stones, bad shoes, and fallen arches. He has been very good at finding satisfactory places to eat.

At dinner in town I phoned up Martin Sluka, one of the exponents of the rival cave drawing software called therion, which is actually programmed by people in Slovakia — the other half of the country Czechoslovakia as I learned it was called when I was young — and he drove round immediately and took me to his house miles away to show me all his cave surveying equipment and old surveys.

I am trying to propose a project on knowledgeforge, which is going to archive all the cave survey data that people want to put there, in the same way that sourceforge exists for software code and is the default place for such material.

I demonstrated my fundamentally incompatible Tunnel cave program to him, and found loads of problems with it. I have to reserve some serious development time on it, along with all the other projects I am meant to be doing.

Sunday, December 3rd, 2006 at 10:54 pm - - Weekends

The weather was excellent in Frankfurt. The walk between the hotel on the south side of the river and the Messehalle where Euromold was held took about 40 minutes. Martin and I used this route, which was slower than taxi on the way there, but faster on the way back when there was a crowd of suits at the taxi stand all queuing at the same time to join the traffic jam across the city.

Our journey would have been faster had we been able to register for the call-a-bikes that were parked around the city, leaning against lamp-posts or railings within sight of any junction. The deal is that when you find a bike with a green flashing light, you telephone its serial number to get the unlocking code, wherein you are charged 1 Euro every 15 minutes until you park it and phone up to report which two roads you’ve parked it on. You are fined 5 Euros if you don’t park it in the right place. You must be a German resident to register for the scheme, so that had us stuffed, sadly.

Still, it looks like it’s getting there. A proper system would be to have a telephone and GPS built into the bike, with its batteries recharged by the hub dynamo (which these full suspension bikes were equiped with) so all you’d need to do is plug a USB key containing your details into the relevant socket, and away you’d go. If you happened to need a bike, your phone, knowing your location, would guide you to the nearest one. The system could even predict the demand rates to pay people to leave bikes in what are about to be useful locations. So in the future when all the suits swarmed out of the Messehalle, there would already be an endless row of high tech bikes for them to hop onto.

Sunday, December 3rd, 2006 at 10:44 am - - Whipping 2 Comments »

Yes, I have the response of a Freedom of Information request to Bristol City Council relating to its publicised £8.9 million deal with Northgate Information Solutions plc, as part of some Public Private Partnership deal with international corp. Skanska to rebuild all the schools and keep the capital for no reason at all. Indeed, according to their press release, they temporarily borrow from a bank invest £4.8 million, and get back a contract with £120 million to rebuild all the schools. This £120 million of state money must be paying for 100% of the goods and services provided by the company, since no one else is using these buildings, so they are not like shared assets used by a range of customers. Anyways, reversing the trend of so many home-buyers who take on the risk and financial hardship of a large mortgage because they don’t want to rent, throw money down the drain and come out with nothing, this is precisely what the UK plc is doing in our name.

Dear Mr Todd,

writes A Marshall of Bristol City Council at 4:30pm on Friday 1 December, not a minute sooner than the 20 working days maximum as stipulated by the regulations.

I write in response to your request under the Freedom of information Act 2000 on 1 November 2006, for details of the contract Bristol City Council entered into with Northgate Information Systems PLC for the procurement of Information Communications Technology (ICT) infrastructure services.

Bristol City Council entered into the contract for the provision of ICT Services for the new schools being built in the Bristol area on 3 July 2006. The contract was entered into with our chosen developers of the schools, Skanska Education Partnership, who sub-contracted the ICT work to Northgate Information Systems PLC.

In relation to your request for details of the charges for the provision of the ICT services for each school, Bristol City Council and Skanska Education Partnership has in accordance with the Freedom of Information Code of Practice identified this information in the contract as being commercially sensitive and disclosure of it would be a breach of confidence.

Bristol City Council is relying on the exemptions inS.41 and S.43 (2) of the Freedom of Information Act 2000 in relation to the charges for the provision of ICT services to each school. This is because disclosure of this information would be a breach of confidence by Bristol City Council, which can be actionable by Skanska Education Partnership and, it would or would be likely to prejudice the commercial interests of the parties.

Although Bristol City Council wishes to be transparent and accountable to the public, it is considered that disclosure at this time would prejudice the commercial interests of the parties and could lead to legal action against the Council, as such; it would not be in the public interest to release the information at this time. It is unlikely that this information will be disclosable until 2018.

This is bollocks. Bristol City Council have no right to go round signing blanket confidentiality clauses, and then claim their hands are tied because of those clauses which they have freely signed. The law applied at the time, and you can’t simply opt out of it because you feel like it. It’s not on.

I have now sent off a new request to them. Expect a reply sometime in mid January, which is how long they’ll be able to drag their heels over this:

Dear Sir,

I understand that Bristol City Council entered into a contract on 3 July 2006 for the provision of ICT equipment with “Northgate Information Systems PLC” through the body “Skanska Education Partnership”.

I understand also that information about the charges for these services has been identified as being commercially sensitive and subject to exemptions under S41 and S43 of the Freedom of Information Act 2000. I believe it is the case that, since the information was generated by the process of negotiation between the Council and the Suppliers, it is the property of both parties.

Section 31 of Part 1 of the DCA code of practice says: “When entering into contracts with non-public authority contractors, public authorities may be asked to accept confidentiality clauses… Public authorities should carefully consider the compatibility of such terms with their obligations under the Act.”

Under the terms of the Freedom of Information Act, I am requesting all relevant details relating to the Council’s consideration to accept such confidentiality requirements in the contract it signed with Northgate, as well as all parts of that contract which are not considered to be commercially sensitive.

Further relevant facts:

1. According to the contract between Becta and the suppliers such as Northgate, all the Service Orders must be reported to them. Becta do not consider these reports exempt from the FOI Act, so the information is likely to be disclosed to the public through that channel sooner than 2018.

2. Section 9.1.8 of the Becta contract, it says “the Services shall comply with all applicable statutes, enactments, orders, regulations or other similar instruments as amended from time to time.”

3. The Freedom of Information Act is a well-understood statute that was in force at the time the contracts were being negotiated.

4. According to section A11.3.5 of my copy of the “Infastructure Service Order Terms”, confidentiality provisions do not apply to any information that “is required to be disclosed by law”. This means that no legal action could be taken against the Council when it complies with its obligations under the FOI Act, and the threat of such action has no place in the public interest test.

Yours etc.

Sunday, December 3rd, 2006 at 12:24 am - - Machining 1 Comment »

It took three days, and Martin and I visited every target and then some, attempting to press our Adaptive Clearing CAM algorithm into unwilling hands. Martin had translated our single-sheet brochure from the Mach 2006 show into German, and that went down rather well. In fact, the whole German thing went well, because I don’t know a word, and had to stand by without interrupting as Martin introduced ourselves and Vorsprung Durch Techniqued at the corporate operative who had come out from the stand to greet us.

Years ago when I went to these shows as an NC Graphics employee, proud of my toolpaths in Machining Strategist, it got pretty boring because no one from the competitive CAM companies wanted to show me their products, fearing that I would steal their ideas and harm their competitive advantage. What they ought to have done was see if they could have offered me a job. I wasn’t generally happy being in Cambridge year after year, and I’d have probably taken it. But, as it is, programmers are so far below the radar that it never occurred.

Anyways, today we have something to give back, so most of the responses were positive, as they should be. We are offering trials of our unique machining toolpath generator free of charge to anyone, with an option to buy at substantially below the cost of development. I tell them that even if they believe they already have the best toolpaths in the world — as many companies do — and they have no intention of buying anything from us, they should get their programmers to examin it, and replicate it — at a guarenteed higher development cost. We offer this because we believe that if more people have this machining algorithm, more people will want it, so it is completely counter-productive to keep a tight control on the technology when it has so little market penetration and we lack the resources to advertise it. And anyway, advertising wouldn’t work because if the larger more respected companies didn’t have it, they would tell everyone it’s crap.

Because I have such extensive experience in the area of Z-level clearing algorithms, I can see the directions that programmers in other companies have developed the standard offset clearing toolpath to overcome its deficiencies. Unfortunately, CAM toolpaths are seen as extremely specialized, so usually there was no expert on the stand who could talk about this. Sometimes we got told to come back when the professor was there, and then we could discuss these esoteric matters.

Of all the companies we visited, Euklid wins the prize for being the most miserable gets, whose boss told us to go jump in a lake; they already have the best toolpaths and don’t need to look. There’s very little documentation on their website.

You expect that kind of behavoir from Tebis. We lasted about 13.5 seconds on their stand when we introduced ourselves. “We develop all our software ourselves.” They also make offset toolpaths with not very clever linking, and therefore can only use them to cut shallow layers.

One other company said: “No thanks, we don’t even look at our competitor’s stuff because we aim to go higher than them” — even if they are deliberately ignorant about what they are higher than. Since they were otherwise polite and gave me a freebee (“I tried to sell them some software and all I got was this T-shirt”) I can’t be bothered to overcome my irrational instinct not to put names to people in this blog. Later in the day we sat next to two of their guys while watching Tebis demonstrate their retro X-windows style software.

So, plenty of follow-ups to do. Blag blag blag. I’ve picked up a number of ideas, some of which will probably void all that excitement I was having about the Z-level machining within waterline areas. I was genuinely surprised when I saw Vero Software’s spiral rest area toolpaths. It reminds me not to become complacent. As usual, webpages for all these companies are universally poor, so I hadn’t noticed this development, and it’s not really shown off in any of their pictures.

I don’t particularly care if none of it follows through. I play this game to maintain my at-times flagging levels of interest in this normally thankless work. All this stuff should be done in some open academic institute where experts come at the problems from different angles, compare approaches, and share ideas; rather than by an uninterested class of programmers who are fragmented and isolated into little units for the duration of their working lives by this deranged market that favours technological stagnation over progress, when the former is more profitable. Come on guys, we’ve managed to get it together over C++, OpenGL, and many other kinds of common technology. Why can’t it work for the basic elements of machining algorithms? I’ve got to write up a big essay on offset ellipses to set the donut rolling. At least one company I saw is unaware of these calculations.

Saturday, December 2nd, 2006 at 11:43 pm - - Weekends

Now in Prague, courtesy of my American half-brother who’s doing a semester of English and German studies over here in order to soak up the culture. Martin ordered the tickets for me from Frankfurt to Prague three weeks ago, but the train company delayed sending them so they arrived in Liverpool while I was in Frankfurt. Stella, in Martin’s house, mailed them to our hotel on next-day delivery at a cost of 35 pounds, but they didn’t arrive on the next day. So I had to walk into the train station, buy tickets with cash, and ride in the smoking carriage to get a seat.

Still, it’s better than having your wallet stolen.

I washed up in an extra-grim grey train station called Praha-Holesovice where I had to elbow the tramps away from the phones in order to call this brother repeatedly until he was able to ascertain that he was searching for me in the wrong train station for over an hour. Useless. The young guy has a very deep voice, and I just look old.