By: Gary Crocker
Note: This White Paper is public domain. You may print and this page
freely.
If it is possible, what would you like to build with a toolbox full of Robust Geometry Functionality? Is there a "Better Mouse Trap" you have been thinking about? Do you have an itch to build something totally new?
In this white paper we will propose a definition for "Robust Geometry" and then propose a set of criteria by which we may judge robustness.
Is Robust Geometry Possible? The answer to this all important question is very much based on your perspective. A theoretical mathematician might take a look at the floating point operations on a typical computer and easily conclude that the only reliable geometry that is possible would be one where integer arithmetic only was possible. We could take the same theoretical view and consider the typical computer we would see that it is impossible to guarantee any result produced on a machine where each of its hardware components had the distinct possibility of failure. From this same perspective we would look at the software on the computer and throw up our hands and give up all hope of using such an unpredictable machine for anything of true value. (No offense intended to my theoretical friends. Us engineer types owe them much. Without their work, we would have no solid foundation to build upon.)
The perspective of an engineer might look totally different. An engineer is typically trying to get something built. Just like a carpenter building a house he is looking for tools that will help him do his job better and faster then he is currently able to do it. A carpenter does not go to a hardware store and buy a hammer because the hammer will never miss the mail. He buys a hammer because it drives in a nail straighter much faster than a rock. It is probably easier to hold and lighter than the rock. Another interesting advantage of the hammer is that it has a V shaped slot on one side which does the opposite job that hitting side of the hammer does. Not only can the carpenter drive in a lot more nails a lot faster, he can also correct mistakes that he makes along the way with the same tool.
To an engineer a computer is beautiful tool if properly equipped with software that the engineer can utilize. Even though it may crash occasionally, these crashes typically represent only a small loss of data or time. The "Three Fingered Salute" or a flip of a switch the engineer is back in business. On the rare occasion that the hard disk fails or gets corrupted, recovery may be more difficult but often still possible. All we have to do is to look that the number of sales attributed to CAD/CAE/CAM/PDM packages to see that engineers are utilizing software in vast numbers.
In this White Paper we are going to take the Engineer's definition of "Robustness" and equate it to overall productivity. If in the final analysis a job is done significantly better, faster, and/or at a lower cost, the tool has a significant value. For the purposes of this paper, the user is one or more software developers of an application that makes use of 3D geometry in some way. Typical 3D application areas include CAD/CAM/CAE/PDM, graphics, animation, GIS, industrial design, game development, simulation, scientific research, modeling of geophysical or medical data, etc.
Having worked over many years in the Graphics and CAD/CAM/CAE development industry, I have had the privilege of working with many different component software libraries and developing several of my own. Some of these libraries were externally developed libraries such as Hoops, OpenGL, PADL, MFC, PHIGS, X-Windows, and others I have long since forgotten about. Some of these libraries were internally developed such as GE's TRUCE, Kevin Weiler's NMT, GE's SMIL, CALMA's NTP, Prime/CV's NURBS Library, Prim/CV's Cxx, and many other smaller packages. The remainder of this White Paper contain my somewhat biased opinions about what constitutes "Robust Geometry" and what we have done at IntegrityWare, Inc. to produce products measure up to these standards.
The initial quality of a product is often measured in MTBF (Mean Time Between Failures). What this essentially means is on the average how long can you go without encountering a problem. Something like today's hard disk drives have very large MTBF. Some disks average 20,000 hours before some sort of failure. This does not mean that if you buy a disk drive that it will run 20,000 hours before your first failure. It may only run 10 hours or it may run 100,000 hours. There are so many factors that are involved in addition to the initial quality of the disk, these include heat, humidity, power supply quality, vibration, dropping it on the floor, etc.The same is true of geometry software to a certain degree. Depending upon what geometry function you utilize and the data you give it, you may go for years without a failure or you may encounter one the very first time you utilize the software. It is a difficult enough problem when dealing with analytical geometry like lines, circle, planes, cylinders, etc.. It becomes even more difficult when dealing with freeform mathematical shapes such as may be defined by NURBS representations.
During the design and implementation of IntegrityWare's GSLib, TSLib and ASPin products we have employed classical mathematics, recent geometry research and a lot of personal experience. The specific details about the techniques employed are trade secret information which IntegrityWare, Inc. deems proprietary and will not be discussed in this paper. Our experience with our customers over the first release and updates of these two have convinced us that we have produced products with exceptionally high MTBF. We confident enough about the MTBF of our products that we have started a program called "The Bug Challenge" for Release 2.0 of GSLib, TSLib, and ASPin. If a customers finds 5 legitimate bugs in GSLib, 10 in TSLib/GSLib, or 5 in ASPin then we will give them a 50% discount on their next maintenance payment. If we had offered this with release 1.0 only two or three of our customers would have qualified for the discount. We are literally putting our money where our mouth is in terms of the quality of our products.
Performance is a critical aspect of Robust Geometry because without sufficient performance the "Overall Productivity Gain" will not be sufficient to justify the usefulness of a tool. In our example with the hammer, if it takes 5 times as long to drive a nail with a hammer as it does with a rock, even if the hammer drives the nail straighter with less mistakes, most carpenters would be building houses with rocks.
There is a story about an old woodsman from Maine who finally gets talked in to trading his ax in for a chain saw. The chain saw salesman convinces the woodsman that he could cut 10 chord of wood a day. The next day the woodsman, looking extremely exhausted, brings back his chainsaw and demands to have his ax back. The ever persistent salesman asks, "Why are you bringing it back?" The woodsman responds, "Well I normally cut 2 chord of wood a day with my ax. You guaranteed me that I could cut 10 chord this @#$% chainsaw. You were wrong. I worked harder than I have ever worked yesterday and I only 1 chord of wood." The undaunted salesman grabs the chainsaw and says, "Let me see, perhaps something is wrong with this one." He gives the chord a crank and starts it up. The woodsman jumps back with a startled look on his face and yells, "WHAT IS THAT NOISE?"
Just like in the story of the woodsman, the key to getting good performance is often a matter of knowing how to utilize a tool properly. Within GSLib/TSLib/ASPin there are tools to help you to optimize performance. You can create and maintain curve, surface, trimmed surface, and Brep caches. These caches are used for nearly every solver in the libraries. It allows you as a user to select the size of the cache to control the speed vs.. memory usage tradeoff. Many functions also allow input of a tolerances to control of the quality of approximated results. The smaller the tolerances the longer the operation will take but the more precise the results. By giving the user control over the caching sizes and tolerances, we allow them to tune the performance to suit their requirements.
When designing and implementing geometric algorithms there are always tradeoffs made between reliability and performance. Sometimes the performance of specific algorithms make them unusable even if they are more slightly more reliable. This is the case for many of the recursive subdivision algorithms. Sometimes the reliability of the algorithm make it unusable as is the case for many of the analytical techniques that employ high ordered polynomial equations. When neither of these cases exist, we tend to choose the algorithm that first and foremost gives us good reliability. This does not mean that it is not fast. These libraries have been primarily designed for post creation application development. In other words, the library has been optimized with the idea that query and interrogation will be the primary operations performed.
The real question most of you are probably asking is how is the performance relative to other available geometric toolkits such as ACIS and Parasolid. Judging from some feedback we have received from customers who have had experiences with these packages, there are many query and interrogation operations we perform much faster (dropping curves to surfaces, rayfiring, minimum distance measurement). We believe that in the domain of sculptured surfaces we are probably comparable or much faster for most operations. For Release 1.0 in the domain of analytical surfaces (plane, sphere, cone, torus, etc.), they were probably an order of magnitude or more faster for some operations (intersection, dropping points to surfaces, silhouette curve, evaluation, etc.). In Release 1.0 all operations were done based on NURBS representations. In Release 2.0 we have augmented the NURBS with analytical information when appropriate. For example a cylinder is still a NURBS but it also carries along its center, axis, and radius. We no plans to do comprehensive of a job implementing each and every analytical case as has been done for ACIS and Parasolid. We have add the most common analytical cases. For Release 2.0 we have added analytical information for lines, circles, conics, planes, cylinders, cones, revolutions and extrusions. This should give us comparable performance for a majority analytical operation relative to the other toolkits.
Another important factor in "Overall Productivity" has to do with the ability to obtain a fast response when you have questions or problems of some kind. Questions usually fall into two categories: "How do I...?" and "Is this the correct way to...?". Problems are typically caused by improper usage, invalid data, a legitimate bug in the software. Just like the woodsman with the chainsaw, most of the users of geometry toolkits are using the tool to make a living. The woodsman could not wait 6 months for Release 2.0 of the chainsaw. He probably would not be willing to wait one month or even one week to get it fixed. The developer or team of developers utilizing a geometry tookit need to have their questions answered, their problems addressed, and sometimes their bugs fixed as quickly as possible to maintain their "Overall Productivity".
As a company, IntegrityWare, Inc. has made the commitment to put the needs of our existing customers at the very top of our priority list. We attempt to respond to all questions and within 24 hours. When problems or bugs are sent in, we will respond and give a projected time when we will look into the problem. Most problems are sent to us via. E-mail with the corresponding data and code snippet that generates the problem. If there is an actual bug we need to fix. We can usually send back one or two source files which contain the fix. Because the customer can then replace the files or code segments in his version, recompile, and continue on with his development. In other cases, we can send information about how to use the software differently to fix the problem. Typically we turn around over 50% of our fixes within 24 hours. Another 30% takes us less than 48 hours to address. The remainder take longer than 48 hours.
Different toolkit users have different kinds of tasks to perform and different geometric functionality needs. It is doubtful that any single geometry tookit can satisfy all of the geometry needs of all of its users. There are several options available to the toolkit user when encounters a geometric need not satisfied by the toolkit. They can find some way to do without it. They can implement it themselves. They can have it developed by a third party.
Instead of taking the "Black Box" approach to the development of the libraries, we have taken the "Open Box" approach. The solvers and many of the other classes in IntegrityWare's libraries have been implemented in a way that they can be easily extended. In some cases our users choose to extend the functionality themselves. This is a relatively easy task because the libraries are supplied as full source code. They can leverage existing classes by subclassing. They can also leverage existing code by copying it and modifying it to suit their needs. The tutorials contain examples of how to create a new customized local solver and global solver.
Some of our users prefer to contract IntegrityWare to implement additional functionality on a consulting basis. As a full service provider, IntegrityWare is committed to both development of software libraries and customization of those libraries for specific applications and requirements.
There are many additional factors which contribute or detract from the "Overall Productivity" of a geometry toolkit such as: Error Handling; Clarity; Consistency; and Documentation Quality. We have put considerable effort into producing a geometry toolkit with unequaled "Robustness". It appears that we have achieved our goals. Most of our users have successfully implemented and distributed either commercial or in-house products based on our libraries. This is in fact the final measurement of "Robustness."