Fast, Easy, Cheap: Pick One

Just some other blog about computers and programming

3D Geometry

Alright, lets get technical again. Pull up a chair, grab a drink, or better yet.. go to sleep and go to do something else, this will probably be boring :)

As you should know by now, I work at a company that develops software that performs all sorts of calculations on 3D CAD data. You can see some examples at our website. If there’s one thing I’ve learned so far on my term here is that doing computations with 3D geometry is hard. Even things that are conceptually simple become difficult or just impractical when implemented on a computer. Programming software that does computation on CAD data is mostly the art of avoiding doing computations.

Part of my project involves detecting when one face overlaps (partially or completely) another face. Visually it’s pretty easy to tell, but not so when you need to compute it. In the CAD world, a face is defined as a parametric surface and a set of parametric trim curves. Essentially the surface is like rectangular piece of sheet metal bent in to the general shape that you want your face to appear. This surface is combined with a set of trim curves that define the shape of your face, the trim curves could be arranged in a triangle or whatever arbitrary shape you want and essentially cut out anything not within their boundary. Each face contains one or more loops of trim curves: the primary outside loop which defines the face boundary, and optionally some additional loops that essentially cut holes within the face.

If this were the math world, you could pull some fancy formulas and find the amount of overlapping area of the faces by performing a parametric integration over the equation of the functions that define the face. Unfortunately on the computer, calculating even one point on a face is an expensive operation because the equation is a high order polynomial. In order to just estimate the area inside of one face, you need to not only sample many points on the surface itself by plugging in some U and V parameters in to the equation, but also to find if the resultant point lies within the curves. And that’s just for one face. Then you need to do it for the intersection. Then you need to perform that for each pair of faces, of which there may be hundreds if not thousands of potentially overlapping pairs within your model (how to find potentially overlapping pairs slightly easier, using some bounding box and bounding curve tests, but I’ll leave the details of that out… it still takes a long time!)

So what’s the point of all this? Well, basically, you can’t do things the proper way, so you have to devise simplifications and estimations that will get you close to the desired result. Often they work, most of the time. Part of the job is to find out how often they work, and if it’s good enough, you just ignore the corner cases when processing.

In my case, to solve the overlap detection, I have been testing only the endpoints of a face’s bounding curves and testing their projection on to the surface of the other potentially adjacent face. Unfortunately this method doesn’t work quite often enough for my purposes so now I am devising ways to refine it and handle the exceptional cases… Developing and testing a change like that easily takes several days or more, and this is just one tiny component of my overall project.

That’s why I’ve been working on the same thing for 5 months now, with the end still seeming far in the distance. Recently I’ve been running in to harder and harder problems and when I ask my coworkers for help they often struggle too and go “wow, that’s hard”, and some of these guys have a masters in math. For some time I was thinking maybe I’m taking way too long and I’m just too dumb to understand and solve this problem, but based on the glowing feedback from my supervisor and coworker reactions I guess I feel better about it now.