Freesteel

I had reason to consult some early and embarrassing 2005/2006 entries in this blog, specifically Patent Schmatent, Patent part deux, and Nothing happened.

These concerned software patent 7451013 applied for by Surfware which had just been published while I was at Euromold that year. After running around all excited for a few hours about how this theoretical threat had manifested into something real, I got told by one of the red shirted folks on the Esprit stand (to whom we were attempting to hawk our Adaptive Clearing algorithm) that there was a way to submit our evidence of prior art to the US Patent Office before the patent was granted.

We looked into this, but it seemed to involve a submission on just the right grade of paper, plus $150 in the appropriate format for the patent office to accept — no doubt some kind of hard-to-obtain currency bank bond that would have cost us $500 in the way of these things. For details, see CFR 1.99 Third-party submission in published application.

However, there was another way. Under CFR 1.555 Information material to patentability in ex parte reexamination and inter partes reexamination proceedings:

Each individual associated with the patent owner in a reexamination proceeding has a duty of candor and good faith in dealing with the Office, which includes a duty to disclose to the Office all information known to that individual to be material to patentability in a reexamination proceeding.

So we mailed a CD with some videos to their lawyers Akin Gump Strauss Hauer & Feld LLP.

…And didn’t hear anything back.

Not being a professional patent wrangler (my job is to write code that does something, not push papers around containing useless gibberish for the purpose of preventing other people from writing code), I didn’t know of portal.uspto.gov where you could see all the documents relating to the patent process.

And in among all these documents I found the following scan:

Hint: Maybe if you read exhibit (B), the Letter accompanying the CD, then the author and dates of publication of the files in exhibit (A) would not have been unknown. Dipsticks!

Just when you thought your opinion of patent attorneys could sink no lower.

Update: Filed under the It’s Worse Than You Thought department, 35 U.S.C. 122(c) states:

(c) Protest and Pre-Issuance Opposition. The Director shall establish appropriate procedures to ensure that no protest or other form of pre-issuance opposition to the grant of a patent on an application may be initiated after publication of the application without the express written consent of the applicant.

The regulatory explanation is set forth like so:

The American Inventors Protection Act of 1999 (AIPA) contained
a number of changes to title 35 of the United States Code…

The USPTO interprets the provisions of 35 U.S.C. 122(c) as
requiring, rather than simply empowering, the USPTO to ensure that no
protest or other form of pre-issuance opposition to an application may
be initiated after its publication without the express written consent
of the applicant…

Following enactment of 35 U.S.C. 122(c), the USPTO revised 37 CFR 1.291 and 1.292 to prohibit third parties from submitting any protest or initiating any public use proceedings… To balance the mandate of 35 U.S.C. 122(c) that the USPTO establish “appropriate procedures” to ensure that third parties may not initiate protest or other pre-issuance opposition to an application after its publication… the USPTO promulgated 37 CFR 1.99 to permit third parties to submit patents and publications (i.e., prior art documents that are public information and which the USPTO would discover on its own with an ideal prior art search) during a limited period after publication of an application. However, 37 CFR 1.99 prohibits third parties from submitting any explanation of the patents or publications, or submitting any other information…

The USPTO considers any third-party inquiry or submission that is not provided for in 37 CFR 1.99 in a published application in which the applicant has not provided an express written consent to protest or pre-issuance opposition to be inappropriate…

I always did wonder why the avenue for challenging a patent application was so awesomely crappy.

Two things:

(1) It looks like we did exactly as much as we could, having found a loophole in this deliberate fortress of unaccountability.

(2) Anyone hoping that the legislative branch is going to clamp down on the patent excesses promulgated by an over-active judicial branch should be disappointed.

A few weeks ago, while doing some background homework on this here Autodesk company that appears to have bought out my life, my work and my life’s work, I did some homework and uncovered this 2009-05-10 article:

Autodesk CEO Carl Bass said in a recent interview that he wants to see the government “mandate” the use of 3-D technology to prevent mistakes, reduce waste and achieve the best results.

…[Autodesk] sees a potential windfall in such requirements and has a lobbyist in Washington, D.C., as well as advocates talking to state officials who oversee how federal funds will be used.

I approve of the idea of forcing the administration of the built landscape to get beyond the paper and pencil age and into the era of proper digitization, so we could browse live maps on the internet that accurately represented all the current infrastructure — and all proposed plans of changes submitted by developers to that landscape.

Such a map could lead towards cracking the much more severe issue of the screwed-up legal infrastructure — Who owns this piece of land that I am standing on? — for the law is totally tangled and obscured and cannot be wrangled by the simple application of a shovel. It is far easier to dig a ten foot hole to find out whether an electricity cable passes underneath than to determin who controls the corporate entity that owns the corporate being that has shares in the commercial organization that leases a particular parcel of land.

(more…)

This is part one of a two part posting that deals with one component of the 5-axis drop cutter function. (It’s also the programming problem given to me when I applied for a job at Parasolid in about 1995.)

There’s a big problem with the finite cylinder because you need to deal with 3 separate surfaces.
As usual with mathematics, there’s a lot of setting up for the equations.

Consider the cylinder C of radius r whose axis goes from a to b, and the point p.

Let:

  v = b - a
  vsq = v . v
  m = (p - a) . v / vsq
      ==> (a + v m - p) . v == 0  [the vectors are perpendicular]
  d = | a + v m - p |

Then p is inside the cylinder when

  d <= r  and
  0 <= m <= 1

Now take the line L that goes from p to q. Which values of s will the interpolated point (p (1 – s) + q s) on L be inside the cylinder C?

Because the cylinder is convex, the intersection is either empty or defined by the interval
s₀ <= s <= s₁

Without loss of generality, assume that a = 0, (so that b=v) and the line L is parallel to the Z-axis, so that points on it are of the form

  p = (qx, qy, z) = q + (0, 0, z)

We want to calculate the values of entry and exit, z₀ <= z₁.

This method requires that we find the set Z of all points of intersection across each of the three surfaces (cylindrical surface, and two flat end disks) and, if Z is not empty, then z₀ = min(Z), and z₁ = max(Z).

At an intersection with the cylindrical surface:

 
r2 = (v m - p)2 
   = (v m - p) . v m - (v m - p) . p  [first term is zero]
r2 + v . p m - p . p = 0

where:
  v . p = v . q + vz z
  p . p = q . q + z2
  m = p . v / vsq = (v . q + vz z) / vsq

As an equation in z:

 
0 = r2 vsq + (v . q + vz z)^2 - p . p vsq
  = z2 (vz2 - vsq) + 2 z (v . q vz) + (v . q)2 + r2 vsq - q . q vsq 

This is a quadratic equation with either 0 or 2 solutions. For each solution value of z, calculate m and,
if 0 <= m <= 1, add it to the set of intersections Z.

At an intersection with the flat end disk at a [at the origin]:

   0 = v . p
     = v . q + vz z
   za = -v . q / vz

If this point on the plane is within the circular boundary of the disk, then:

r2 >= p . p
    = q . q + za2
    = q . q + (v . q)2 / vz2

in which case add it to the set of intersections Z.

At an intersection with the flat end disk at b [same as v because a is the origin]:

   0 = v . (p - v)
     = v . q + vz z - vsq
   zb = vsq - v . q / vz

If this point is on the disk, then:

  r2 >= (p - v)2

in which case add it to the set of intersections Z.

As already stated: z₀ = min(Z), and z₁ = max(Z). We expect Z to contain either 0 or 2 values.

This algorithm works for convex volumes bounded by surfaces. However, it suffers from the obvious problem of cracks. What happens if the line intersects exactly through the edge between the cylindrical surface and one of the flat disks at the ends? Well, since floating point calculations on such a boundary can go either way, there is a 25% chance of accepting an intersection from both surfaces, and a 25% change of missing both of them.

A surplus intersection isn’t a problem because it is masked by the min() and max() functions, but missing the intersections completely means we return a measurement of the cylinder that is paper thin, missing its bulky volume and probably causing a collision to result from an algorithm that depends on this function down the line.

How likely is it that the line will hit this edge? Very likely, because geometrical assemblies tend to line these edges up so that the worst always happens.

If it’s okay to over-estimate the range of the line that intersects with the cylinder, then all we need to do is extend the surfaces slightly by small value, such as 0.00001, and rewrite our three inequalities as:

 -0.00001 <= m <= 1.00001
(r + 0.00001)2 >= p . p
(r + 0.00001)2 >= (p - v)2

thus papering over any possible gap, so the bug is fixed and we break for lunch satisfied.

Unfortunately, this leads to code-rot by littering the system with fixed values that just felt right at the time, and which now limits the scale at which this function will be reliable. And what happens if v is close enough to horizontal or vertical such that the crack opens up again? If the bug recurs, your only option will be to increase the epsilon value from 0.00001, or scale it in a specific case
(eg setting it to 0.001 when |v_x|+|v_y|<0.001).

Pretty soon, everything is kludged, and the results are wider than they should be, and subsequent code becomes dependent on this over-estimate to cover for its flaws.

There’s no way back once you let the epsilon fix in.

This is a small digression. The finite cylinder can be defined as the intersection volume between the infinite cylinder and the slab volume between the two planes through a and b perpendicular to v.

Take the interval [z_-, z₊] from the quadratic equation for the intersections with the infinite cylinder, and intersect it with the interval [z_a, z_b] from intersecting with the two planes (assuming v_z > 0), and that’s the value.

This is much better, but it doesn’t necessarily generalize (see part 2 when I write it), and does not lend to optimization when we need to find the answer for multiple parallel lines at the same time.

Let’s look at that diagram again.

By projecting the geometry down the Z-axis, the problem becomes one of locating a 2D point within a shape made up of two ellipses and a rectangle between them.

This dimensional reduction is what makes the calculation work. Next we need to reduce the problem to 1 dimension, which is the only level that computational geometry operates.

First, let f be the flattened unit vector of v (assuming v_z >= 0):

   f = (vx, vy) / |(vx, vy)|
   e = vz / |v|  [the eccentricity of the ellipses] 
   d = f . v

   m = f . p
   s = fT . p   [the 2D perpendicular of f]

We know that we completely miss the cylinder if:

   |s| > r   or
   m < r e   or
   m > d + r e

So, subject to the precalculations of f, e and d, we can filter out most cases when the line misses the cylinder with two dot-products. That’s very efficient.

And, given the value of s, we can see that the red line intersects the two ellipses at four different points
{-k, k, d-k, d+k} where k = e sqrt(r² – s²).

From the position of m in between these four values, we can determine exactly which components of the cylinder with which we must find an intersection with the line, and produce an optimal solution that will always be reliable and does not depend on any epsilon fudge factors.

In part two, the line gets replaced by a rectangular volume in a problem that took me four complete attempts (of at least 600 lines of wasted code each) to get it right. The code is not intended to be looked at again, because it is as fast as it can be and should not have any failure cases, until it becomes necessary to extend it by the cylinder becoming a truncated cone.

I took this picture of a wall within the Copenhagen Rathouse during culture night when all the interesting buildings in the city were open and the streets were packed with badge-wearers. It’s of two gold plated walrus skulls from Greenland with a shield in the top right depicting hot sun and palm trees representing the little known Danish West Indies. The nation must have liked that tropical holiday home. One of the venues we went to had a rock band from Greenland called “Copy Paste”. We didn’t stay long.

(more…)

We’ve seen this performance before from the finance press with the 2007 takeover of NC Graphics by PTC.

(more…)

Last month in Austria I woke up and got out of my tent to be greeted by some fusspot who had just washed all my dirty dishes from the night before and was now lecturing me about what a slob I was for never doing my washing up. She was on safe ground because it was now impossible to disprove her as to my actual intentions because it was too late, the dishes were already washed up. And if I dutifully washed up before her every morning for the next seven days she would have been vindicated for telling me off and making me to get my act together. So it’s a lose-lose situation. The answer is you have to wash up immediately when there are fusspots on the loose who are looking for social credit to steal that they intend to cash in at the end of the expedition when it is time to clean out the toilets and it suddenly be your job by default.

Ideas are like dirty dishes. You have to publish them immediately before someone else washes them for you and leaves you with the job of merely making them work for the next 20 years.

(more…)

Here is an example random part which the great folks over in Copenhagen have been throwing at my scallop routine.

The problems thrown up by these computer generated random parts are easy to ignore — there is always something better to work on — because no one is actually getting let down by them. But when a bug showed up on a genuine customer part that mattered, I spent a week working through it, which was long enough for the flood-gates to be opened. The random part generator was kicking out failures at the rate of six a day and chucking them into the bug tracker by the bucket load until I told them to STOP!.

(more…)

About 3 weeks ago I got sent a big part to have a look at which took about 5 hours to process. This wasn’t too disruptive as I was at Europython and could keep popping back to the hotel room to read the output, change the print statements and set it running again.

The problem traced down to this image where a 6-way cell was connecting up wrongly.

The black lines are going up a wall, and the contours are in this vertical wall. We are getting a sharp internal corner of offset from a contour that runs to the left and then to the right around that tip. And the tip is almost coincident with another corner at the bottom of the wall in XY. The rectangle with the 6-way cell is actually a square in XY space of about 0.02mm on each side and has reached its limit of subdivision.

(more…)

Another interesting calculation bug, to go with the previous one, that has been in my code for decades, occurred as a result of not properly factoring down a quadratic equation.

The danger area is when such an equation approaches a perfect square, and the calculation isn’t at the margin.

A very simple example of a safe situation is the line y = m x + c intersecting a circle radius r centred on the origin, so that:
r^2 = y^2 + x^2 = (m x + c)^2 + x^2
0 = x^2 (m^2 + 1) + 2 x (m c) + (c^2 – r^2) = x^2 a + 2 x b2 + c
Solving this quadratic equation using the standard formula gives:
x = -b2 / a +- sqrt(b2^2 – a c) / a
= -m c / (m^2 + 1) +- sqrt(m^2 c^2 – (m^2 + 1) (c^2 – r^2)) / (m^2 + 1)
The value inside the square root expands to -c^2 + m^2 r^2 + r^2, and you’re going to get no solution when this is negative, corresponding to no intersection with the circle. (As a sanity check, set r = 0 and no line that is not through the origin hits it.)

The margin, when this value is 0, corresponds to a double contact point (a tangency) between the line and the circle, and it really doesn’t matter if you get it completely accurate; you’re barely intersecting the geometry at all.

In the following case I found such a use of the quadratic equation where the margin was not at all marginal, and the presence of a collision mattered.

(more…)

No one thought there could be a bug in something as fundamental as the drop cutter onto triangles function, which has been in use at the heart of most every machining algorithm since I had started writing these functions 20 years ago. But the farm found one.

(more…)