Freesteel Blog » 2008 » October
It’s taken nearly a week and 400 lines of C++ code to complete the algorithm shown in the above picture, where a series of trapeziums, representing the conical sections of a tool holder, are merged into one continuous monotonic (in radius distance from the axis) piecewise linear curve.
We get these kinds of non-joined up segments when thickness is applied to the toolholder shape and all the previously consistent sections start to overlap in various ways depending on how much material you’re adding. It’s important to have a consistent contour to work with because you can code things much faster than checking the collisions of all the independent segments individually. For example, when you lower the cutter down in Z onto a point, the distance between the point and the axis tells you the unique conical segment that it will collide with. No need to check any others.
You notice in the drawing the big triangle contributes three individual segments to the final red line. This aligned envelope finding algorithm — pain though it is — is about a 100 times easier than the polygon intersecting algorithm which you have to implement if you want to find the offset contour from an arbitrarily shaped pocket slice. That’s an algorithm many CAD programmers have foolishly tackled, not having the wit to recognize the extreme difficulty of it. In fact, if I was giving CAD developers interviews for my job I’d ask them to tell about how they would approach the problem of finding the offset of a polygon, and if they showed any confidence of being able to do it, they’d fail the shortlist. Only by suspecting that you’ll have a hard time doing it by brute force (which results in a debugging project for the next 20 years) are you likely to hunt for and find out about the real solution, which involves Voronoi diagrams of lines (not the simpler one of just points).
For some reason I’ve stupidly implemented it in C++ rather than Python, probably because I needed to use my Along(lam, a, b) function and other little quirks in my small functions library. This means that we need to provide accessor functions to get the results back out of the C++ objects and into the Python, which is the interface to the graphical visualization tools. Maybe when I’m feeling I’ve got the time I’ll convert it from one language to the other (or someone else can volunteer if they want to — I’ll give you the code). Like I said, I made the wrong choice. I’ve been having a heavy cold all week, which may have clouded my judgment.
Wednesday, October 22nd, 2008 at 7:16 pm - UN
I was checking out the real UN site to work out what’s the hold up with the General Assembly transcripts. I haven’t had one arrive on my server since A/62/PV.103 in June, and we’re already way into the 63rd session.
The list of Session 62 resolutions is here and it records meetings all the way up to A/62/PV.122 in September, without links to the verbatim transcript documents. (The videos all go on-line right away, because that’s easy to do.) The resolutions passed in those meetings are also on-line, so I perused them and stumbled onto A/RES/62/278 which said:
The General Assembly Recognizes the usefulness of the existing online mandate registry, and… Notes that one of the important findings of the process is the difficulty of identifying resources associated with one particular mandate, which limited the potential of the review process to fulfil its objective of strengthening and updating the programme of work of the Organization and improving the allocation of resources for the effective implementation of mandates;
The Online Mandate Registry?
Search for it: It’s here.
I had a good look and noted this finding down onto the Wikipedia Page for United Nations so other people could find it, as not everyone reads this blog. It’s been going since 2006. The Introduction explains:
Legislative mandates express the will of the Member States and are the means through which the membership grants authority and responsibility to the Secretary-General to implement its requests. The resolutions adopted from year to year by each of the principal organs are the primary source of mandates. Mandates are both conceptual and specific; they can articulate newly developed international norms, provide strategic policy direction on substantive and administrative issues, or request specific conferences, activities, operations and reports.
For this reason, mandates are not easily defined or quantifiable; a concrete legal definition of a mandate does not exist. Resolutions often signify directives for action by employing words such as “requests”, “calls upon”, or “encourages” but an assessment to distinguish the level of legal obligation arising from the use of these different words has yielded no definitive answers. Such ambiguity in resolutions may be deliberate “to make it easier for Member States to reach decisions.” But since the membership has indicated a wish to use its review of mandates to examine opportunities for programmatic shifts, it is both necessary and desirable to identify a working definition of the unit of analysis and delineate the scope of the exercise.
Guided by the 2005 World Summit Outcome and subsequent discussions in the plenary, I have defined a mandate as a request or a direction, for action by the United Nations Secretariat or other implementing entities, that derives from a resolution of the General Assembly or one of the other relevant organs.
To facilitate the review and as a companion piece to this report, the Secretariat has compiled an electronic registry of mandates originating from the resolutions of the General Assembly, the Security Council and the Economic and Social Council. The registry of mandates, along with accompanying guidance for users, is accessible at www.un.org/mandatereview.
The executive summary is more forthright:
The single greatest symptom of the lack of a coherent system for evaluating mandates and their effectiveness is the uncoordinated and burdensome mass of reports requested from the Secretariat. The quantity of the reports obscures their quality and impact, overwhelming the Member States and overburdening the Secretariat. Because information is not often provided on the overall picture of the Organization’s work in an area, it is difficult through those reports to judge the effectiveness of mandates in meeting the Organization’s objectives.
Year after year, the General Assembly, the Economic and Social Council and the Security Council continue to adopt new mandates on the same issues, sometimes even under more than one agenda item in the same organ, usually without introducing new ideas or approaches. While some overlap of mandates from different organs is inevitable and different perspectives desirable, the existence of many interrelated mandates is generally confusing, redundant and wasteful.
The proliferation of mandates has in some cases led to overlapping, uncoordinated and inconsistent architecture for implementing mandates, in which the whole may be less than the sum of the parts. Little guidance is provided on what to do with older mandates that address the same issues, which therefore linger on over the years.
A fundamental and recurring challenge has been the adoption, year after year, of hundreds of mandates which must be implemented within resource constraints that do not keep pace. Member States confer additional responsibilities with neither corresponding funds nor guidance on how resources should be reallocated. This gap leads to real costs for the Organization and the people it serves.
So, to be clear, the semi-disastrous 2005 World Summit had its outcome adopted as a resolution, in which paragraph 164(b) said: “The General Assembly and other relevant organs will review all mandates older than five years”, and the secretariat quite reasonably decided that the first thing they needed to do was make an online registry of all mandates.
Just in case you aren’t completely clear what a mandate is, Paragraph 164 was indeed itself interpreted as a mandate, number 17171 in the database, to be precise.
I found the meeting where Secretary-General Ban Ki Moon presented this registry to the UN:
That is why the decision to conduct the review, even if it was not the most glamorous that heads of State and Government made last September, was one of the most meaningful and potentially historic. It is also a daunting challenge. While there are real opportunities to achieve results in the short term, to conduct a full review of mandates will take time and sustained commitment. But the outcome could be extremely rewarding, particularly for those we serve around the world.
Members of the Assembly, it is your review; you are the ones who are going to undertake it. I am only giving you the tools to conduct it: an online registry of mandates and, in the report before you, an analytical framework.
The registry, which responds to requests from several Member States, is a searchable electronic inventory of still-active mandates originating from the resolutions of the General Assembly, the Security Council and the Economic and Social Council. It will enable you to find all the mandates you have adopted and to view them in a convenient way.
See, computerization is important for organization. Pity they chose such a poorly laid out and utterly cludgy java servlet database for it, rather than using on a copy of MediaWiki with all its high level Web2.0 structures. Out here in wikipedialand, we’ve been constructing our own mandate registry. Just think how cool it would be if the UN staff inserted their information in this place rather than burying it behind horrible codes and 1980s style database interfaces.
Oh well, never mind. I’m sure it looks all completely reasonable to the e-Envoy in his experience.
Tuesday, October 21st, 2008 at 7:46 pm - Whipping
It’s taken about two solid days to build, not to mention the time already invested in my Crewe byelection candidate quiz from earlier in the year. So here it is:
I can’t spare any more time, and I have to know when to stop. Not all of the bells and buttons work yet, and there may be some tinkering at the edges, but this has got to be what I run with. Any comments suggesting substantial changes are welcome, but I may store them for later.
The leaflet we will deliver to addresses in the Glenrothes constituency hasn’t yet been finalized. I’ll now have time to look at that now. Meanwhile, Becka, me and Aidan have made arrangements to go to Glenrothes on the weekend of the 1 November with our bikes.
(I am spectacularly crap at organizing things and getting people to join in. “Not I,” said the people on the byelection pledge. “Then I will,” I said, and I’ve done it about as well as I can speak French. I have a lot of other talents to offer the world; just not these!)
Becka and me have booked the train from Liverpool to arrive in Edinburgh at 12:19 on Friday 31 October. Depending on conditions, we’ll either cycle to Glenrothes or catch the train. We don’t know where we’re staying. Aidan hopefully comes up on Saturday 1 October with his folding bike and we do some deliveries and testing of the website on in the street. The three of us are booked in to the budget Glenrothes Travelodge for that night. It’s got wifi access, so I’ll be able to do some tinkering with the website. Aidan probably goes home on Sunday, but Becka and me stay the extra night in the Travelodge and head home from Edinburgh on Monday afternoon, unless something really interesting crops up, such as an invitation to an all-night party somewhere to watch the US election, which will no doubt be stolen again by that Republican death-cult they have there. We really don’t have it so bad.
A good website for catching up on news from the Glenrothes byelection is www.glenrothesbyelection.com. I don’t know who maintains it.
Something closely related to this current election quiz website is going to be available from PublicWhip at the General Election.
I am well-known for my way-out radical ideas among the mySociety-related community. One of my most way-out and wacky concepts at the moment is that there is going to be a General Election in a year or two. I say, Wouldn’t it be nice to have the website all dusted up, polished and ready by the time, rather than attempting to cram something together in the last three weeks, like I’m doing for these by-elections? Eh? Whatever.
In her efforts to delay the democratic revolution, Becka hauled me off for a weekend of crawling through the lead mines in Nenthead with the North Wales Caving Club (someone has got to add some details to that wikipedia article) — when I had a whole lot of better things to do. “But you had all that fun messing around down in London and Cambridge this week,” she said. The revolution has to be put on hold.
We visited the upper levels of the mine on Saturday and eventually found the calcited ladderways down to the lower levels where there are several kilometres of wading neck deep water just below the dry stone arched ceiling before you come out of another entrance. We did this trip about five years ago with the Red Rose Pothole Club, but Becka had completely forgotten it. Mines are sumped. Who knew? They are not natural drainage formations, like caves are, so they trap the water and fill up when the pumps are stopped.
It’s not working out as I had hoped.
The grand plan was to run the Windows-only software HSMWorks and the C++ development compiler from Linux through a VirtualBox session that hosted a copy of Windows. That would mean that while the whole of the “we need high performance and to play games” CADCAM world chose Windows, I wouldn’t be stuck with it in order to develop the software.
Now Windows, and especially the new Vista, acts like it is the one true operating system in the world. When you install it on your machine, it takes ownership and blocks access to all other operating systems that might be there. The software is a lazy, arrogant bully, and most people give in to bullies if they want an easy life. Therefore bullies predominate. Even when ugly.
I should have known that my grand scheme couldn’t possibly work. I would have had more success if I bought a 100% Windows machine and ran Linux in a virtual box session within Windows, because things can get along that way. Linux is an effete wimp that does its best to get along in a world with a bully. But since now only 30Gig of disk is in the Windows partition, there isn’t enough space for that.
Here’s my log of the day.
9:47 Insert HSMWorks disc
10:06 Run HSMWorks
10:08 Download Firefox
10:09 Install Firefox
10:10 “Detected change in activated licensing components. You need to run HSMWorks as an administrator”
10:11 Firefox complete.
10:12 Control panel suggests the vista Julian account is an administrator.
10:13 Skype to Copenhagen – bug in old version. “update from web”
10:20 Download the experimental version from hsmworks.com
10:23 Copy out license codenumber into form
10:24 “Failed to update machine configuration. Please make sure that you have administrative privileges”
10:28 Although when you list the user accounts it says Julian (Administrator), the “Make changes” page has the radio button for “Standard user” set to On and “Administrator” set to Off; when you click on this the “Change Account Type” goes grey.
10:31 Becka, who has the password in her office, is not there.
10:32 Install the Chinese Government IM service
10:33 Try to download putty and save in System32 directory. It won’t let me.
10:35 Read the net for a while.
10:41 Copenhagen gets back with the idea of running a remote Netviewer session. Software was installed with HSMWorks
10:42 All sessions in use now. come back later.
10:50 I misinterpreted the administrator privileges dialog on Vista.
10:56 Run Skype and take a .reg file from Copenhagen
10:59 HSMWorks still doesn’t work (administrator error)
11:00 Get another .reg file from Copenhagen
11:01 Failed again. “Make sure you have administrator privileges”
11:13 My old computer, which I’m taking these notes, rebooted for an operating system update whether I like it or not. I’m getting screwed over by Windows in stereo. Martin tells me to stop swearing.
11:15 Still waiting for remote viewer key thing so Copenhagen can work out why my UAC (User Access Control) is blocking HSMWorks security key installation. I couldn’t save putty.exe directly to system32 directory; I had to copy it in and go through dialog boxes.
11:17 Windows comes with java installed.
11:20 Try to install python. Fail due to lack of administrator privileges. Conclude there is some irritating dialog box obstructing administrators from doing administratory things.
11:31 Check through the internet and discover the Run as… technique
11:34 Download the JDK 1.6
11:35 Download TortoiseCVS and TortoiseSVN
11:42 Voluntarily register with Sun for the JDK
11:43 Run netviewer and hand control of the computer to Copenhagen
11:46 My computer is now possessed.
11:49 Watch him do the Run as… hack
11:50 Debugging appears to be happening
11:57 Install TortoiseCVS at my own risk
12:00 Install Audacity to see if there’s a mic. Is none.
12:05 Install Open Office
12:10 Install HSMWorks 2008
12:14 Decide to install C++ while they look into it.
12:30 Run As… hack on HSMWorks works.
12:37 Now downloading 0.5Gig service packs for the C++ compiler
12:48 Go to lunch
14:00 Back from lunch. Finish installing C++ Studio updates
14:20 Down to 3Gig disk space out of a total of 30Gig in the Windows partition
14:29 Begin SVN checkout of HSMWorks codebase
14:36 Back to 4.7Gig free. Uninstall Open Office
15:10 Get the C++ environment working
15:13 Install Swig. SVN checkout HSMWorks thirdparty code
15:37 Uninstall JDK and extra Java versions
16:00 SVN checkout the vroni code
16:05 Do more recompiling because I selected the wrong solution (so many old ones floating around not cleaned out)
16:08 Struggling over getting the python24 that we use in HSMWorks compiled. Ask Copenhagen for help.
16:10 Getting itchy to log in to Ubuntu, but then I won’t get any workwork done. The point here is to build the development environment the Danes use in Solidworks, which I have got by without until now.
16:43 still struggling with getting the python in HSMWorks to function.
17:00 Shutdown, reboot to Ubuntu. Find that all the software I’d installed before sending it back to the Emporium is still there
19:06 Still fighting over getting one of virtualbox or vmware to work
19:49 Have discovered I should be loading virtualbox2.0 not virtualbox-ose. Then chown-ing all the /dev/sda disks
19:57 The virtualbox works, Ubuntu boots in it, but Vista is sick when it does so.
20:20 Serious error with apt. Try rebooting
20:23 fsck error. go into root and let it try to fix everything
Fed up, I went home without my computer.
Using a dual boot, my working habits are going to be different. I am either going to do some actual machining work in Windows and not have any room to do anything else, or reboot into Linux and do all the fun stuff with undemocracy, publicwhip, tunnelx, and other projects. I won’t be able to change jobs so easily in the middle of the day, so I will be forced to remain focused on finding the intersection between a line and a torus if that’s what I have to do. I’ll try it. Maybe it’s all for the best.
Wednesday, October 15th, 2008 at 7:31 pm - Whipping
There is a vast scheme for computerizing Her Majesty’s Courts Service (HMCS). I don’t know anything about the job specifically, but I do know about the computerization of the Acts of Parliament — the DNA of the legal system, if you will — and how ineffectively done it is.
I contend that if the powers that be weren’t so concerned about printing them on vellum for the benefit people 500 years hence who may or may not give a flying frog about it long after all the UK government buildings have sunk beneath the waters of the Thames, they might have time to get something useful done for the people to whom the law applies to today as it is drafted by people today.
One obvious feature involving the Acts of Parliament and the legal system would be a method for tagging every argument, hearing or legal decision on the public record to the Act, Section, or Regulations it specifically references.
From this, we could generate the big picture, a poster shot of how the legal code is performing, where it is defective, misapplied, buggy, and what needs to be fixed. The UK Parliament is the sovereign body with the power to patch this code, and through our electoral process we are supposed to influence how this works.
At every level of indirection there is a loss of control and influence to whom it effects.
We don’t vote for whether the coordinated action of the state can do one thing or another; instead we have judges to decide on this, and the judges interpret the written law.
We don’t vote for what that law is; instead we have political representatives who argue about it and ratify it for us.
And over the very long term, usually without considering the effects on the law, or the effects of the law, we, thrice removed from the actual application of effective coercion, we get to chose from a narrow selection of party appointed operatives those political representatives.
There is, for example, an identity card system underway which the government is going to impose upon us, and people who don’t like it are going to get busted under Section 7(5) of the Identity Cards Act by a judge. An effective and democratically enabled court filing system would note each case against that section in the Act, and these notations would connect back to the decision in Parliament where they passed this section of the Act as well as the Act as a whole, and thence back to the individual MPs who voted for these sections whom we have no alternative but to hold personally liable for committing these fellow citizens to civil proceedings and possibly to jail, as well as wasting vast quantities of our national treasure on this boondoggle. With effective accountability of this nature would come the responsibility to fix it. It is within the power of our Parliament to change any law at any time without limitation. That’s what the Home Secretary told us yesterday when she promised to have a draft Bill to extend the time period people could be arrested without telling them what for, available on stand-by to be voted on in the event of a “national emergency”. Presumably an emergency as good as that other public emergency threatening the life of the nation which they declared without anyone noticing, and which stood for three and a half years.
Of Course, none of these interesting features are present in the plans for the computerization of the courts service through the Ministery of Justice’s new multi-million pound Electronic Filing and Document Management (EFDM) contract.
Here are the vision statements.
From the Business Operating Model V1.
The EFDM vision is to provide a more cost effective, accessible and speedy service to litigants, court staff and the judiciary through a transformation of the way court services are accessed and delivered by adopting e-Enabled justice through e-transmission of documents and universal access to an e-case file.
(BTW, I met the former e-Envoy last night. This experience will be blogged later.) From the Business Prospectus 1.0:
e-Enabled justice through e-transmission of documents and universal access to an e-case file; producing a transformation of the way court services are accessed and delivered, and a more cost effective, accessible and speedy service to litigants, court staff and the judiciary.
As you can see, the system will be fundamentally limited to the task of busting people efficiently, and not anything towards helping answer questions like: What’s law doing here that’s any good? Who’s getting hit? How can we get it changed?
Because it’s not open source, there is no possible way for someone with an interest in these questions (that’s all of us, unless we have been propagandized not to give a damn until it’s too late) to retro-fit these features into it.
The EFDM contract is interesting because it’s not only out-sourced. The outsourcing itself has been outsourced to two private consulting firms who appear to have drawn up an utterly vague and vacuous set of designs and operating structures with not one use case scenario or piece of recognizable functionality anywhere. But they’ve got an “implementation approach” (p14 of Business Prospectus) seen here now:
Someone I showed these documents to said immediately: “That looks like Microsoft Sharepoint.” And it probably is, because designers always copy “neutral” specs from what they know. Limited experience is in general a mental prison.
There is some dreadful blue block-diagram flow chart that’s repeated several times in different forms throughout the documents, and it looks like nothing more than the organization chart for Amazon.com, the on-line book-seller, with its Front and Back Offices and National Bulk Centres, delivery flows, and arrows to icons showing that it can send your invoices for fines or fees by Fax or Email. By page 30 my brain had died.
From Business Prospectus – Annex A:
Critical Success Factor
- The operational time taken for HMCS court staff to complete the full
range of case related activities is reduced.
- The delivery of new and improved modern channels for ease of access to court services and appropriate case information [Internal & External Channels – Areas 1 & 2 and 3 & 7]
- To deliver efficient and effective management of case files and case records within the court services operation through the removal of paper and the provision of IT tools and revised working practices [Input & Output Management and Business Information Management – Areas 4, 5 & 6]
- To introduce standardised management of case records
from creation through to archiving [Areas 4, 5]
- To free up office space by the removal of paper and the streamlining of operational procedures [Back Office capability – Area 9]
- Enhance the reputation of HMCS [All areas of BOM]
- Improved capture of management statistics, to facilitate better understanding of business operations. [Back Office – Area 9]
We Know It’s Achieved When
- The service levels for responses to a case are within the timescales set, i.e. the administrative process steps to be completed within 5 days for 94% of cases.
- BMS times for case file related processes are revised downwards
- HMCS court staff can to locate a case file in under 10 seconds and therefore able to answer a query made by the litigant or defendant – fewer case files are lost or incomplete.
- Case documents are easily stored and accessed and associated with other documents which have already been filed for that case.
- The reduction in time of the overall court processes mean that judges can increase by 5-10% the number of small claims cases processed. Similar increases in processing will also apply to fast-track and multi-track cases.
Annex B is very boring. Annex C is where you look up the definitions of Service Upgrade Projects (SUPS), Work(flow|load|force) Management, and e-bundles.
Then finally the Pre Qualification Questionaire which “has been developed to enable Logica to recommend to the MoJ an initial longlist of Bidders suitable to be invited to negotiate to meet the requirements of the EFDM Programme.”
The PQQ ensures that nothing good whatsoever can come of this project:
Please provide a copy of your senior management organisation chart.
Please describe (using diagrams where appropriate) the proposed structure of the organisation which would deliver the services envisaged for EFDM, and the reporting lines within your organisation.
Give your view of the benefits of the organisational approach you are choosing and, if relevant, the strengths that the different companies bring (where appropriate).
The successful supplier will be required to use a recognised Programme and Project Management methodology, consistent with or interfacing to Government standards such as Managing Successful Programmes (sic), PRINCE 2, etc.
Describe in outline your preferred methodology and management tools that you have applied to your existing Government contracts.
The MoJ strategic preference for the delivery of IT solutions is to “buy not build” and the re-use of existing components and services, or Commercial Off The Shelf (COTS) products, (integrated and configured as necessary to meet the business and technical requirements) is therefore the preferred approach for EFDM.
Bidders should describe the components that they have used and implemented in similar systems, highlighting their use of Commercial Off The Shelf components in these solutions and identify the business and technical benefits provided by the use of each product.
Most importantly, from my point of view as a coder who understands the purpose of free software, the PQQ Annex A has in 7.1
As a general principle, IPR in software that is specially written for the project is owned by the party best placed to exploit those rights. This will usually be the Contractor.
So the general principle is to gift a monopoly on this publicly funded capital so we don’t get to use it or add features. The government looks after its own interests thus:
The Contractor the
Authority should ensure that it is given a perpetual and royalty free licence to use the specially written software providing as a minimum rights to:
- use it within the Authority’s organisation without restriction;
- allow other public sector users to use the services provided by the
- transfer the benefit of the licence to other public sector bodies;
- allow other service providers to deliver inter-connecting services; and
- allow other service providers to provide the services or replacement
services upon termination of the Agreement, the triggering of step-in
rights or upon the expiry of the Agreement.
What would I have done?
Well, for 2 million quid which it cost to do the feasibility study, write no code at all, and spread any kind of knowledge anywhere, the Government and the court service could have run a series of open days on its premises to show technically minded people and companies what it does, what it needs, and hold week long workshops that heard about and took advantage of the community knowledge and experience before committing to anything tedious. Some of the people who went to these conferences might find that it’s really interesting, and so within their capabilities that they start up a business to help supply the government’s needs, and the wealth and capital spreads, and everything improves with good software and people who are interested open and care.
Anything but set up a system where the money goes to the usual suspects who have no intellectual interest in the process whatsoever, and wish that anyone out in the wider world who does have a technical interest in the problem — as distinguished from making lots of money by servicing a crappy contract — would just go jump in a lake, or get lost in some other way. We don’t need them. All they’ll do is interfere with profit making. Good bye.
You don’t begin a project that will take the rest of the year and more without evading it as long as you can. Finally I’ve begun to break ground on this.
Background: Almost all industrial algorithms for generating toolpaths for 3-axis machining are based on the Drop Cutter function, where the tool is lowered along its axis towards a triangulated surface until it makes contact. I have discussed this here, where I also add my usual complaint about how almost all of published academic literature on 3-axis machining is based on the contact point offset from a point in a parametric surface, and so is of no use. The problems raised by that approach are insurmountable, and you don’t need to solve them because there is a better way.
For most CAM systems, if you speed up the Drop Cutter function (which for toroidal cutters often depends on solving the quartic equation), then everything runs faster. The other determination of performance is if the implementation of the machining strategy calls this Drop Cutter function too frequently. That’s how fundamental the function is.
The only 3-axis machining algorithm that does not depend on the Drop Cutter function is the Horizontal Projection function used in the calculation of constant Z (waterline) contours. (A visualization of a bug in it is shown here.) This Horizontal Projection function finds the points of intersection when the cutter moves in the plane perpendicular to its axis. In Machining Strategist/Depocam I never solved it for the toroidal case (because I didn’t know the answer to an order six polynomial which you get instead of the quartic), and used a neat little fudge where I could get to the same answer by measuring the contours for a ball-nosed cutter and then offsetting the contour in its plane by the radius of the circular axis of the torus. In HSM Works/Adaptive Clearing I finally worked out how to do it, which is fortunate because I’m going to need it here, and there’s no way round it.
The obvious fundamental 5-axis cutter location function is shown in the diagram above. The cutter is in an arbitrary orientation (the red dotted line is its axis) and is dropped in an arbitrary direction (the thick green vector) to find the point of contact with the triangulated surface (outlined in blue).
We can transform everything into a better position and make the green vector the vertical Z-axis. Then, if the dotted red line (axis) is in line with this green vector, we’re back to the 3-axis condition. If the dotted red line is horizontal (perpendicular to the green vector), then that’s Horizontal Projection function. Otherwise we can rotate the assembly so that the dotted red line is in the X-Z plane to observe that the only new parameter we need to include is the angle between the axis of the cutter and the direction of projection. (If the red axis line is below the horizontal I’m going to reflect about the horizontal X-Y plane.)
Makes it seem simple. The interface into the big calculation engine that solves the Horizontal Projection function merely needs to take a unit 2D vector in the X-Z plane representing the tilt from the red vector to the green vector. A value of (1,0) is the Horizontal Projection, and (0,1) is the Drop Cutter function.
At least that gives it a home and a tiny tweak to the interface for the other developers to access. But there’s going to be thousands of lines of hard code coming up real soon over the next few months.
BTW this doesn’t unify the Horizontal Projection and Drop Cutter functions, because the Drop Cutter, being as fundamental as it is, is unbelievably optimized. In its case there is a rotational symmetry about the Z-axis that can be heavily exploited. Once there is a tilt from this axis, the symmetry is broken.
And so to work.
Last Saturday we went to the Low Carbon Communities conference in Llangollen, a charming location without any convenient public transport for arriving on the day. Several non-depressing talks were attended. But we’re doomed. And that extends from the bottom of civil society like there, to the top where even today the minister in charge of the new Department of Energy and Climate Change (DECC) is too cowardly to concede that an 80% reduction in carbon emissions is utterly inconsistent with a 50% expansion of airplane capacity at Heathrow. Even when the entire financial system has exposed itself for trading while bankrupt and the business community should be at its weakest. We have nothing to fear from them. Their threat was always that they were going to pull out of the country and ruin the economy, and they’ve achieved the latter without doing the former.
Here’s a computational geometric problem I found in the course of work with no obvious good algorithm to solve it.
Take this picture below. The dotted line provides orientation and shows you where the endpoints are. We’ve got red dots and blue dots, and we start with a green piece of string threaded above the red dots and below the blue dots. (We can assume it’s in order along the orientation of the dotted line.)
Now pull the green string tight through those endpoints to get a nice zig-zaggy result like so:
I need a clean algorithm that will get to this answer. For the moment I am confounded.
The actual problem relates to smoothing a 5-axis milling machine toolpath with respect to one of its rotational axes while avoiding collisions. For this, the situation is a little more complex (I don’t want to calculate the positions of the blue and red points unless I absolutely have to), but an answer to the simplified version could lead the way.
Meanwhile, out in the real computational geometry world where there are professors, you’ll discover endless amounts of study of a similar, but somewhat less interesting problem of finding the convex hull of a set of points.
To get to this uninteresting problem, simply throw away all the red points and put the starting line all on one side.
The algorithm for pulling the red dotted line tight to get to the green line over all the points is easy to see: Consider each sequence of three points in order; if the middle point is below the line joining the other two points, then delete it.
If you run this trivial algorithm twice, once for above and once for below, and you started by finding the extreme left and right end points, you get Andrew’s Monotone Chain Algorithm for the convex hull of a set of points, published in 1979.
Finding the convex hull of a set of points has occupied quite a bit of attention over the years. We start with the Graham scan of 1972, the Jarvis march gift wrapping algorithm of 1973, the Alk-Toussaint heuristics of 1978, the Kirpatrick-Seidel algorithm of 1986, and Chan’s algorithm of 1996.
Never has so much mathematical honour been accorded for so little over so many years as has been the case for the computation of convex hulls. New students come to this field and wonder what the hell the whole fuss is about, because it looks just obvious. It is obvious. All the algorithms are pretty much O(nlogn) because they apply a sort function at some point and, in my opinion, are absolutely equivalent. The later advances merely involved partitioning the points into smaller sets, finding the convex hull for each set individually, and merging the result.
As these students grow older and eventually become professors, they realize what the game is, which is to have an easy life in a comfy job doing stuff that isn’t very hard, but just looks like it is because it has lots of equations so no one is going to say it’s silly. At least not anywhere that matters. (Blogs don’t count.)
The last thing you want is for anyone to find an application in your area. You don’t want some random machine tool programmer coming along and saying: “Oh, you look like the sort of person who ought to be able to solve this computational geometric problem I have here,” because they might find you out.
I can rephrase the problem in terms of the fruitful convex hull situation:
I want to see a slick algorithm to go from this:
where the string is pulled tight, with the blue birch trees on the inside and the red maple trees on the outside of the perimeter.
Then you can get one of your colleagues to name it after you (if your name sounds cool enough), and then later, after they’ve done something with one of the numerous variations of the problem (eg higher dimensions — the string passes through a set of polygons in space — or made-up geometries), you can return the favour by naming their invention after them.
But be warned. The older professors are going to say, “No no no no no. You don’t understand. Convex hull algorithms are the foundation stone of all computational geometry for the last thirty years.” Let’s not be too hasty and get beyond into stuff involving tori, and triangulations, and hundreds of other things it would be useful for someone to look at. You wouldn’t want the subject to become too difficult and sophisticated by the time you grow up. Next you’ll be telling me I should be releasing my code under some new-fangled public license so other people can make advances on it, and that I shouldn’t be using FORTRAN, which is a perfectly good language, I’ll tell you, because it makes moderately straightforward things into a terribly complex scramble without any effort. I am not going to put up with you telling me that your sloppy Python language is so much better and that I should learn something new. You young people always think you know everything.
The point of a university academic is to produce papers. You’re not supposed to get involved with any curious applications that are someone else’s problem. Unless they pay you. And you certainly don’t want to be maintaining libraries of free software functions in use out there in the wider world, like it is some kind of public service.
* Have I mentioned how many implementations of the quartic equation I believe are out there in the industry? I keep wanting someone in a university to maintain a really good one, and part-exchange it for the copies of this routine implemented in all the different CADCAM systems in the world, and do a sort of interesting archaeological code-study on them.
The researcher wouldn’t actually need to write their own. They’d only have to pick the one which is the best. The game is that all the CADCAM companies have a version of this and many other fundamental algorithms, and nobody knows who has the best. But if ten companies all got together and put their implementations into a pot and chose the best, each one would have a 90% chance of improvement in efficiency for free in each case.
Usually, the companies who are most unwilling to consider this game — even as a thought experiment — are the ones with the worst quality software. It’s the lack of curiosity that’s the give-away. They guard their source code jealously, because “someone might learn a secret from it and gain a competitive advantage”, yet they are the last ones who would ever comb through someone else’s code if they got access to it.
As with a lot of concealed secrets in business, the real revelation is that there’s nothing there. It’s just a game of Poker. Fun, but a waste of time, ultimately. It would be nice if someone clever went round the table telling everyone what to play so we could all win big against the House. It’d be more fun for those who want to move things forwards, rather than just maximizing the money. Eh?
Regular blogging has been delayed due to a lack of pictures. Becka keeps swiping the camera, downloading the files onto her computer because mine is full, and stashing everything away in her own office. But plenty has been happening.
The North Wales Caving Club scheduled a rescue practice in Parys Mountain, Anglesey for Sunday 21 September. The weather was sunny and flat calm, so we got in gear and got out there on Saturday for a paddle out of Amlwch harbour