4/27/98

Final Project Report

24-786 Geometric Modeling

1. Introduction

The recent technological advances in rapid prototyping mandates that CAD systems be developed to handle the specific needs of this unique and powerful design tool. Rapid prototyping devices such as a stereo-lithography apparatus (SLA) are all based on the concept of "printing" two-dimensional shapes on top of each other to make a stratified three-dimensional object. The "printing" of the two-dimensional shapes can accomplish smooth curves however the shapes resulting in the third dimension are confined to orthogonal edges. This limitation in making three-dimensional shapes can be minimized or even prevented by intelligently choosing the proper slicing direction. For example, in the manufacturing of a cylindrical object as seen in Figure 1, one can completely eliminate error by slicing in the axial direction (a) as opposed to the radial direction (b). This project attempts to automatically determine the best slicing direction by describing the problem as an optimization problem, where the amount of overhang or excess material is to be minimized.


2. Approach

In order to find the best slicing direction an algorithm needs to be created to accept the basic shape of the artifact to be sliced and return a three dimensional vector that will create the best quality part. For this approach, the only other parameter provided by the user is the slicing thickness. It is assumed that the thickness is uniform for all slices and that it is not a parameter which the algorithm can adjust but a constraint based on limitations of the SLA hardware. We can now phrase the problem as a traditional optimization problem with one function to be minimized and three constraints which bound the variables in the system

.

Here, the objective function, f, is the sum of the absolute values of volume difference at each slice. This requires that for a given slice i, the actual volume V_i,actual must be determined as well as the volume for the slice, V_i,slice. At every iteration of the optimization process, f will be found to provide a metric for determining the best slicing direction. Physically, f is the volume of the total overhang or error between the actual device and the sliced object. The three variables in the process, q, f, and d are the rotation about the z-axis, the azimuth angle and the starting slice length respectively. As seen in Figure 2, q is constrained to be between 0 and 2p and f is constrained to -p and p as this allows us to construct any three-dimensional vector from polar angles. The variable d is constrained to be no more than the specified slicing thickness, h, thereby allowing the process to consider the different slicing possibilities. By allowing the position of the starting slice to be determined by the algorithm, we are allowing for the possibility of slicing that might coincide with part features, as demonstrated in Figure 3.


3. Algorithm
1. Optimization Approach

The optimization approach chosen for this problem is a multi-start Sequential Quadratic Programming (SQP) algorithm. SQP is an optimization technique similar to a steepest descent method where the steepest gradient of the search space is followed in order to find a minimum. By approximating the objective function as a quadratic function at each iteration, the algorithm intelligently chooses values for the variables that would put it at the minimum for that quadratic. It then updates the state with the actual evaluation and repeats this procedure until it has converged on a state that it views as the minimum. An optimal state chosen by the SQP algorithm is guaranteed to be local minimum but are not necessarily the global minimum for the search space. This is especially true of search spaces that can have many local minima as in this slicing problem. It is for this reason that we use a multi-start SQP algorithm. This simply means that initial starting points are chosen throughout the design variable space to seed the SQP algorithm. After finding the local minimum points for each starting point the best one is returned to the user.

The reason this approach is used over other approaches is due to the nature of the slicing problem search space. Although, one cannot formulate the objective function in a way that would allow true gradient information to exist, it seems that for a given slicing direction, the gradient to the local optimal point has a tangible quantity. Clearly for the cube in Figure 4, one can see how the gradient of objective function would lead to the optimal slicing state. It is also believed that the objective function is a relatively smooth surface, thus making stochastic approaches like Simulated Annealing, or Genetic Algorithms an excessive alternative. These approaches are generally better on more erratic objective function spaces and would perform unnecessary search that would slow down the process.


2. Evaluation Approach
Initially, this project was going to include an evaluation mechanism that would be completely inline with the theoretical approach shown above. However, the volume calculations of the slice subsections (V_i,slice) and the actual sliced parts (V_i,actual) proved to be a difficult and timely task. As seen in Figure 5, the process must be able to divide the faces of the object into subfaces for each slice. This requires copying the original artifact in computer memory, dynamically adding new faces, and preserving the directionality of faces to insure proper volume calculation. After much struggling to solve these problems, a simpler approach was devised. In this new approach, slice volumes are conservatively calculated in an attempt to create an upper bound for the slice volume resulting from a given direction vector. These slices are devised to only leave material on and not perform any undercutting. The new formulation for the objective function is simplified to: f = V_slice - V_actual

The conservative slice volume is found by always using the larger of the two cross-sections of the slice faces that bound a slice. Figure 6 further illustrates how V_slice is found. Unfortunately, this method might not always produce an upper bound as initially hoped as also be seen in Figure 6. If the adjacent faces are situated in a particular fashion as to avoid bulges within the layer or such that the larger slice face does not include the smaller one.



4. Results

The implementation was based on the CFSQP algorithm (C code for Feasible Sequential Quadratic Programming) developed at the University of Maryland. The freeware package includes two basic C functions cfsqp.c and qld.c This project developed (1) the preprocessor code (start.c) to load the artifact being sliced, set up parameters for the process, and execute the cfsqp routine, (2) the post-processor code (post.c) to output data and vrml files, and (3) the evaluation code (volume.c) to determine the value of the objective function within the SQP process. The program was executed from a command line prompt by typing:

optislice h file.dat starts

where optislice is the name of the executable, h is the slicing thickness, file.dat is the data file containing the artifact information, and starts is the number of initial starting points chosen in the multi-start SQP algorithm.

The output files from optislice are data.out and slices.wrl. Data.out is a small file that includes the optimal point, the starting point that lead to the optimal point, the optimal volume of the slices and the actual volume of the slices. Slices.wrl is a vrml file depicting where the slices occur.

Optislice was tested on three test problems: cube.dat, poly.dat, and part.dat. The "cube" problem (Figure 7) tests the effectiveness of the algorithm on the simplest level. It is clear what the optimum is and the process should find it from any starting point. This proved successful and gave confidence that the SQP algorithm was communicating properly with the evaluator. As seen in Table 1, the optimal vector clearly must have p/2, 0, or -p/2 in the azimuth angle, f.

The "polygon" problem (Figure 8) proved that the evaluation mechanism was not robust enough and in fact a slicing volume is found that has a significant volume difference that is lower than that of the actual polygon. However, in the "part" problem, Figure 9, the algorithm finds a usable slicing direction that is equivalent to what we would imagine the optimal slicing direction to be.

Table 1: A tabulated form of the data reported from various data.out files.

	Cube  h = 0.1	Polygon  h = 2.0	Part  h = 0.2
Initial Vector: q f d	0.727512  1.140788  0.020550	4.996707  0.467063  1.088900	5.754900  0.220756  0.082119
Initial Vector: q f d	0.000000  1.570795  0.000000	5.639944  -0.551866 1.544450	6.283180  1.570795  0.200000
Slice Volume	0.995299	10305.12	22.600563
Actual Volume	1.000000	11812.5	15.280664

5. Conclusions

 
Get report in Acrobat format: Campbellreport.pdf