The focus of my research has been, and will continue to be, to produce tangible results obtained from the combined efforts of theory and practice of computer science. In broad terms, my research has focussed on developing accurate and efficient algorithms for evaluating surface boundaries of CSG solids (expressed as Boolean combinations of curved primitives). It has mustered concepts from geometric modeling, symbolic computation, algebraic and differential geometry, computational geometry, numerical linear algebra, and 3D computer graphics. My work has been motivated by both short-term result oriented problems and long-term research oriented driving problems. The practical importance of my research is best exemplified by the fact that both research and industry groups are using it to solve real-life problems. An abstract of my current research interests follows.

Geometric and Solid Modeling

The need to efficiently generate accurate boundary representations (B-reps) of solid objects encountered in CAD applications and simulation based design has motivated my research in sculptured surface modeling. B-rep generation is required at various stages of model design including verification and collision-free placement in complex geometric environments. Over the last few years, modeling using curved surfaces, and building complete solid representations from splines has become indispensable throughout the CAD/CAM/CAE industry. However, the main problem in building such systems is in evaluating and representing the intersection curve of parametric surfaces. As a result, most existing solid modelers resort to polygonal approximations of these surfaces. The resulting B-reps are inaccurate and suffer from data proliferation. The emphasis of my research has been to obtain a convenient representation for the intersection curve, and thereby develop efficient and accurate algorithms to evaluate it. I have also applied my surface intersection algorithm in generating B-reps of solids given in CSG form.

My surface intersection algorithm is based on combining numerical curve tracing methods along with an algebraic formulation of the intersection curve. The performance of the algorithm is output sensitive, and typically performs an order of magnitude faster than previously known robust algorithms.

This method is an advancement over existing finite-precision surface intersection algorithms, in that it guarantees the correct topology of the intersection curve. It does not suffer from robustness problems of numerical approaches, and efficiency problems of purely algebraic methods.

I generate B-reps of CSG solids in terms of trimmed parametric surfaces. The trimming curves on each patch are the result of intersections with surfaces of other solids. The accurate representation of the intersection curves guarantee accurate B-reps as well. The resulting B-reps can be used for model verification and collision-free placement during the design process. Further, the algorithm is implemented on general purpose processors, and is easily parallelized with little overhead. Using the parallelized version, we are able to perform Boolean operations on sculptured solids at interactive rates.

One of the biggest problems facing most modelers is robustness. Generating topologically correct and consistent B-reps for objects placed at degenerate orientations is a very difficult problem, especially for modelers that work with finite precision. Most of the previous work on robustness was done on polyhedral modelers using exact arithmetic. Along with other researchers at UNC, I am working on extending this technique to curved primitives as well. The premise of this work is based on developing optimized algorithms for each subproblem so that the exact B-rep can be generated without incurring too much penalty on the efficiency. I plan to extend this method so that it can be combined with symbolic perturbation techniques to handle degeneracies.

Polynomial System Solving

Finding the solution to a system of non-linear polynomial equations is a classical and fundamental problem in the computational literature. This problem arises in a number of symbolic and scientific applications. Sets of polynomial equations are used for object representation in numerous applications in the fields of computer algebra, robotics, computer graphics, molecular modeling, geometric and solid modeling, and computer vision. As a result, many geometric operations in these applications reduce to finding a solution of polynomial equations. My work, in collaboration with other researchers at UNC, has been restricted to solving zero and one dimensional algebraic sets. By combining well-known techniques from symbolic and numerical linear algebra literature, we compute the solutions efficiently. I plan to continue working on extending the algorithm to higher dimensional algebraic sets, and investigate more problems where these methods can be applied.

Model Visualization and Simulation based design

The need to navigate through increasingly complex virtual environments for simulation based design and validation has motivated my research in high-order geometric objects. The traditional polygonal representation of large models often requires millions of primitives. While current graphics systems have reached the capability to render millions of transformed, shaded and z-buffered triangles per second, this is not enough for many real applications. Further, the polygonal representation of these models along with the different ``level of detail'' representations generated off-line leads to serious data proliferation problems. The premise of my work, along with other researchers at UNC, is based on the fact that by storing objects as a collection of NURBS surfaces, or as the curved boundary representation of solids, it is possible to maintain compact and accurate models without incurring rendering penalties. We proposed an adjacency based representation of the boundary trimming curves that facilitates crack-free rendering of surfaces in an efficient way. The higher-order representation of objects allows us to generate the appropriate set of triangles at run-time, both speeding up the visualization and increasing the visual realism.

As data sets continue to grow larger, efficient memory management becomes a crucial issue. A prospective avenue for rendering speed-up is `curved surface simplification'. Depending on the requirements of the visualization application, I believe that significant savings can be obtained by simplifying these models by sacrificing a little on accuracy. Very little work has taken place in these directions, and I plan to explore such possibilities.

While navigating through large environments or during dynamic simulation of parts in a CAD model, it is critical to perform collision detection or interpenetration analysis. Currently, most collision detection algorithms work on polygonal models or polyhedral approximations of sculptured models. Performing accurate and real-time interference detection on curved surfaces is generally considered a difficult problem, and as such, has been left unexplored. Using appropriate tight-fitting bounding volume hierarchies and fast interference tests between these bounding volumes, I believe that collision detection time can be significantly improved. I plan to continue to work on these lines.

Surface Visibility and Global Illumination

In the last decade, radiosity methods have gained popularity in the computation of view-independent global illumination. Unfortunately, the number of polygonal primitives that these algorithms generate can grow quite rapidly. On the other hand approximating the radiosity function as patches of splines can reduce the model-complexity. Using techniques from curved surface rendering, we can then significantly speed-up the rendering of radiositized model. Computing radiosity directly on curved surfaces using the ideas of visibility maps developed in industrial manufacturing literature is another problem of interest to me.

• About this document ...