My research work lies in the interactive fields amongst computational mathematics, computer graphics and mechanical engineering. It focuses on applying mathematics knowledge to solve geometry and solid modeling problems, and involves various topics in CA(G)D, algebraic geometry, reverse engineering, mesh/image processing, robotics and so on. Specifically, my current work focuses on: regularity detection, interpolation and approximation algorithms and topology computations, bio-inspired robots simulation and motion planning, and digital engineering archives. Two other research projects on mesh models are also under exploration: (1) vase project that considers part assembly, relief extraction, flattening and mapping; (2) shape structure project that combines model beautification, skeleton, normalization and deformation. Regularity detection      Figure, from left to right: (1) complete symmetries detected by our algorithm on a 4X4 grid disturbed by other 20 random points; (2) approximate Monster model with various forms of approximate local incomplete symmetries; (3) symmetries detected in the characteristic points of the Monster model---rotations and translations; (4), (5) Misu model and the detected symmetries. Symmetry, as a general form of various regularities, is mainly studied here. A symmetry is an invariant, particularly an isometric, that maps a set exactly onto itself. Many natural and man-made objects exhibit global and local symmetries, and detecting symmetries of objects in various forms has wide applications in engineering, biology, physics, architecture, and art. Our current work focuses on the reverse engineering aspect, and is usually described as "beautifying reverse engineered CAD models" , or "detecting design intent of reverse engineered CAD models". The derived symmetries, other kinds of regularities, may be used to constrain and guide editing operations. It may also allow us to improve an approximate model by enforcing intended regularities. It may enable faster analysis and more compact representation, if the model has symmetric sub-parts. It may also allow models to be more meaningfully indexed for shape search, etc. Note our ultimate goal is to find various potential geometric regularities or constraints (mainly symmetries) present in an approximate object, which may be a set of discrete points, images, meshes etc for various applications. Symmetry detection for mesh models can also be found in recent Siggraph proceedings in 2006 (on symmetry detection), 2007 (on symmetrization), 2008 (on detecting symmetric structure).
Our recent work focuses on complex approximate CAD models, and detects symmetries present in various forms: symmetry may be present approximately---the set is almost invariant, locally---only part of the model is invariant under an isometry, incompletely---not all elements building a symmetry are present, and compatibly---multiple sub-parts share the same symmetry. Moreover, under a rigorous symmetry definition, all seven elementary symmetry transformations are detected uniformly: mirror, inversion, translation, rotation, rotation-mirror, glide and screw. Our future work on this topic will focus on detecting symmetry groups present in an object, which involves various symmetry combinations in 2D and 3D spaces. This covers various regular tetrahedrons and wallpaper groups. References Symmetry Wiki Peter Brass Thomas A. Funkhouser Frank C. Langbein Ralph R. Martin Helmut Pottmann Approximation and interpolation algorithms, topology computations     Figure: from left to right, (a) our quadratic approximation for a quatic algebraic curve (tolerance bound 0.003; segment number: 8), (b) result of (Xu and Bajaj, 1997) (tolerance bound: 0.1; segment number: 34), (c) curve plot in Maple 11, (d) close-up view of the middle part of (c); the curve's original topology has been destroyed in (c). (e) our approximation result of an algebraic spacial curve ( intersection of two algebraic surfaces). Approximation and interpolation algorithms are classical problems in computational mathematics, and have wide applications in various fields such as mesh processing, image processing, robotics etc. Our current work on this topic focuses on algebraic curves and surfaces: (1) parametric approximation for algebraic curves; (2) topology computations for algebraic curves and surfaces; (3) mesh approximation for algebraic surfaces. Traditional approximation methods on such topics usually focus on the local approximation aspect, or based on local shape analysis. They hence usually use too many approximation segments/patches, suffer the approximate precision, or even lose the original model's topology. Such problems still exist in the plotting tools of algebraic curves and surfaces of the date-of-art mathematics softwares, e.g. Matlab, Maple and Mathematica. We used a novel global approximation strategy by first computing the topology of an algebraic curve/surface. The method divide the curve/surface into a set of simple primitives that are easily and nicely approximated by parametric curve segments or surface patches. It strictly preserves the original topological structure, uses much less number of approximation segments/patches, and better approximate the curve/surface. Two other important questions are also studied here: (1) computing topology of algebraic surfaces; (2) computing interpolation surfaces that interpolat a set of discrete points or spacial curves. Algebraic geometry theories are applied here to resolve these issues. Video: software demonstration for constructing symbolic surface interpolant that interpolates a set of discrete points with prescribed normal directions. It was implemented in VC++ using OpenGL. References Guolinag Xu Chandrajit Bajaj Bert Juttler Bio-inspired robot simulation Video, from left to right: (1) simulation in ODE of our designed CAD model; (2) simulation in ODE of the simplified model. Using the simplified model achieves similar dynamic performance of the original model but much reduces the simulation time.
Biologically-inspired robots can achieve functions that are hard for humanoid robot due to their special biological properties. We are particularly interested in snake robots as shown above, which have high adaptability in complex environments owning to its high degree of freedom. Simulation is referred to the process of designing a model of an actual or theoretical system, executing the model, and analyzing the execution output. Robot dynamic simulation allows us to investigate, design, visualize, and test the robot to avoid the unnecessary injuries and damages and unnecessary changes occurred in design. It essentially is trying to turn a hardware problem into a software one.
Dynamic simulation of CAD models can be implemented in two different ways. The first focuses on using of commercial programs, e.g. SolidWorks, Pro/ENGINEER, ACIS, ADAMS, MATLAB, and MAPLE. The second relies on an open source physics library e.g. for physics-based modeling (e.g. the Open Dynamics Engine) and gaming (e.g. Blender). We currently focuses on the latter way.
Our current research focuses on simplifying mechanical CAD models for accelerating dynamic simulation. Previous model simplification method, however, cannot be directly applied here---they are usually geometry-based rather than directly physics-based, and hence are hard to well keep the dynamic behavior of the original model. Moreover, although manually some kinds of simplified models were applied in accelerating dynamic simulation in previous robotics-related work, no automatic simplification method is provided, no rigorous comparison or explicit fidelity measure is considered between the dynamics behavior of the original model and its simplification. Our current work aims to resolve these issues based on the following observation: for a designed CAD model, its dynamic model consists of three main elements: collision geometry, mass property (from each model part) and mechanical constraints (relation between model parts). These elements are essential in dynamic simulation and have to be best preserved in the simulation process, while other un-essential elements can be mostly ignored.
References CMU BioRobotics Lab Motion planning of snake robots   Given a dynamic model and simulation environment, we need to find a "proper" trajectory that moves an object from a starting location to target location. This control problem is generally described as motion planning. It is widely studied in various fields such as robotics, mechanics assembly, graphic animation, surgical planning, computation biology. Rapid developments in these fields requires new planner to deal with robots with many degrees of freedom in complex environments, and techniques to generate quasi-optimal trajectories, coordinate multiple robots, and to deal with dynamic and kinematic constraints, and handle dynamic environments. Strictly, motion planning is a path planning problem that further considers time, dynamic constraints, coordination and so on. Path planning is usually referred to the pure geometric problem of finding a collision free path for an object amongst static obstacles. A classical version of path planning is sometimes referred to as the Piano Mover’s Problem, studied by a series paper of J. Schwarz. Its algorithm complexity is PSPACE-complete. Related to our snake robot simulation, we currently focuses on motion planning of snake robot on rough terrains: starting from a snake robot configuration in contact with the terrain, find a feasible trajectory (configurations, velocities and the control torques) that moves the snake to a target configuration along the terrain. The difficulty of the problem lies in several aspects: (1) the high degree of freedoms of a snake robot; (2) the complex geometric and physical condition of terrains; (3) accurate dynamic modeling of the snake robot, and its interaction with the terrains; (4) explicit expression of various task constraints (joint constraints, torque constraints, snake’s stability etc). References Jean-Claude Latombe Steven M. LaValle's book: Planning Algorithms Gamma Team of UNC Thesis: Rigid body dynamics simulation for robot motion planning Digital engineering archives  Figure: The AMBER part and its project information space. For many industries, engineering design and manufacturing data needs to be preserved over 50-to-75 year lifespans. Traditional digital data management techniques are usually dependent on the proprietary formats of commercial software systems and cannot guarantee the readability and utility of data over long periods. Hence, while 3D CAD modeling has become indispensable, the engineering part print (i.e., the 2D drawing) still remains a principal method of design knowledge archival. The rich knowledge in 3D CAD about features, manufacturing processes and artifact behavior are simply lost in translation. The project objective is to extract data to create Digitial Engineering Archives, enable answers to meaningful engineering queries on archives of 3D engineering knowledge, and support long-term engineering knowledge preservation. References Princeton Shape Retrieval and Analysis Group PRECISE of Purdue University Vase project        Figure 6: Various types of vases. Beautiful vases, antique, art. Mesh processing, structure analysis. Reference |
Research Introduction |
