User:NyahCheck/Survey of CSG Algorithms

Project Title

Survey of CSG Algorithms

Personal Information

Name: Nyah Watad Check Email: check.nyah@gmail.com IRC Nick: Ch3ck, Ch3ck_

Background Information

I am a third year Computer Engineering student of the University of Buea and one of the two first GSoC participants in Francophone Africa; worked with BRL-CAD in GSoC 2013, participated in the Google Doc Camp where I documented the BRL-CAD, OpenMRS and GNome projects. Participated as an X.org Evoc participant with X.org in 2014. I participated in as a Mentor in the 2014 Google Code-In for BRL-CAD.

Programming Background

• X.org Evoc Participant, X.org, July – October 2014
  • Added Shatter Support to the X server project using Xephyr.
  • Clip Impedance layer to Xephyr and ran unit tests like Xts fixing bugs

• Google Summer of Code Participant, BRL-CAD, April - September 2013
  • Implemented a pull routine to reverse the effects of a push on Geometry, **integrating command into MGED interface. (C, XML, 500+ lines of code)
  • Tested the polynomial and matrix math routines, improving the speeds of the inverse matrix and matrix determinant routines by over 10%. (C, 300+ lines of code)
  • Integrated the xpush routine which pushes objects having more than a single matrix transformation into the push which pushes object matrix transformations to leaf nodes. ( C, 1000 lines of code.)

• Book Sprint Participant, Google Doc Camp, October 2013
  • Participated in creating a contributors guide to BRL-CAD which will encourage a greater number of contributors to working on the BRL-CAD project.

• SKILLS
  • Languages: C(Excellent), Java( Excellent ), C++( Beginner), Bash(Excellent), SQL(Proficient)
  • Tools: Secure Shell, subversion, Git, Linux, Netbeans, gdb, valgrind.

Synopsis/ Proejct Summary

This project aims at performing a comparison studies of 2D and 3D CSG algorithms, looking at the efficiency and robustness vis a vis the current implementations in OpenSCAD. Constructive Solid Geometry being one of the primary modeling techniques in the CAD industry is a major part of OpenSCAD. This involves studying the Clipper and CGAL library implementations in OpenSCAD and coming up with improvements on existing implementations.

Detailed Project Description

Introduction

Constructive Solid Geometry is a technique used in Solid modeling which allows a modeler to create a complex surface using Boolean operators to combine objects. This is often referred to as procedural modeling and can be performed on polygonal meshes. Here, the simplest solid objects used for representation are called primitives which are used to construct more complex objects using allowable Boolean operators such as union, intersection, difference and well as geometric transformations on those sets of objects. OpenSCAD uses the Clipper Library to implement CSG in 2D and CGAL libraries to model 3D surfaces. My objective in this study is to look at the CSG Algorithms implemented by OpenSCAD and do a comparative study with other CSG algorithms, performing and algorithmic analysis and implement prototypes which can be useful in the OpenSCAD framework. This entails studying 4 main research papers together with various implementations of the algorithms associated with them and implementing the most efficient on the OpenSCAD platform.