Editing User:NyahCheck/Survey of CSG Algorithms

From BRL-CAD

User account "NyahCheck" is not registered. Please check if you want to create/edit this page.

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 5: Line 5:
 
= Personal Information =
 
= Personal Information =
  
Name: Nyah Watad Check.
+
Name: Nyah Watad Check
Email: check.nyah@gmail.com.
+
Email: check.nyah@gmail.com
IRC Nick: Ch3ck, Ch3ck_.
+
IRC Nick: Ch3ck, Ch3ck_
  
 
== Background Information ==
 
== Background Information ==
Line 19: Line 19:
  
 
* Google Summer of Code Participant, BRL-CAD, April - September 2013
 
* Google Summer of Code Participant, BRL-CAD, April - September 2013
**Implemented a pull routine to reverse the effects of a push on Geometry.
+
**Implemented a pull routine to reverse the effects of a push on Geometry, **integrating command into MGED interface. (C, XML, 500+ lines of code)
**Integrated 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)
 
**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.)
 
**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.)
Line 30: Line 29:
 
**Languages: C(Excellent), Java( Excellent ), C++( Beginner), Bash(Excellent), SQL(Proficient)
 
**Languages: C(Excellent), Java( Excellent ), C++( Beginner), Bash(Excellent), SQL(Proficient)
 
**Tools: Secure Shell, subversion, Git, Linux, Netbeans, gdb, valgrind.
 
**Tools: Secure Shell, subversion, Git, Linux, Netbeans, gdb, valgrind.
 +
 +
  
 
= Synopsis/ Proejct Summary =
 
= Synopsis/ Proejct Summary =
Line 103: Line 104:
 
= Sample Algorithms/Links =
 
= Sample Algorithms/Links =
  
* Gilbert Bernstein and Don Fussell: Fast, Exact, Linear Booleans
+
1.) Gilbert Bernstein and Don Fussell: Fast, Exact, Linear Booleans
*Sebastian Steuer: Methods for Polygonalization of a Constructive Solid Geometry Description in Web-based Rendering Environments
+
2.) Sebastian Steuer: Methods for Polygonalization of a Constructive Solid Geometry Description in Web-based Rendering Environments
 
+
3.) MEPP: Exact and Efficient Booleans for Polyhedra
* MEPP: Exact and Efficient Booleans for Polyhedra
+
4.) Cork - by Gilbert Bernstein
*Cork - by Gilbert Bernstein
+
5.) CGAL: http://www.cgal.org/
* CGAL: http://www.cgal.org/
+
6.) http://liris.cnrs.fr/mepp/
*http://liris.cnrs.fr/mepp/
 
 
 
=Testing and Verification=
 
  
Test would be written to verify and test the robustness of the BSP-tree based algorithm for CSG evaluations. This could apply Octoball tests from single operations between sizable meshes to Random Boxes tests and Sculpt Bunny depending on the efficiency. Also, the heat sink test which has proven to have a worst case performance of O(n2) in the size of input can be applied to the aforementioned implementation. Unit tests will be developed to handle different aspects of the BSP-tree evaluations and appropriate documentation attached for later works on the system.
+
= Deliverables =
Also, any bugs coming up during this process will be fixed and documentation of this work done during development since OpenSCAD is actively developed and this will keep other developers informed on any changes taking place in the CSG module for OpenSCAD.
 
 
 
=Deliverables=
 
*A paper containing the CSG Algorithm survey and it's relation to OpenSCAD
 
*Prototype implementations integrated with OpenSCAD on the more efficient and robust CSG Algorithms.
 
*An Evaluation of how more advanced modeling techniques could be realised with each algorithm.
 
  
 
= Development Schedule/Timeline =
 
= Development Schedule/Timeline =
This is a tentative plan which will be modified and developed as GSoC proceeds.
 
 
*May 17 – June 06( 3 weeks)
 
**Study papers on this topic
 
**Discuss with developers on implementation specifics and further clarifications on CSG Algorithms supported by OpenSCAD.
 
 
*May 24 – June 13 ( 3 weeks)
 
**Check current implementation of the BSP tree algorithm for evaluating CSGs and porting to OpenSCAD.
 
**Implement the BSP-tree representations  in OpenSCAD or optimize current implementation.
 
**Testing, debugging and documentation.
 
 
*June 14  – June 20( 1 week)
 
**Unit tests for BSP-tree routines
 
**Testing degenerate cases.
 
 
*June 21 – July 4 ( 2 Weeks) Mid Term Evaluations
 
**Add functionality for CSG to BSP-tree conversion
 
**Testing for robustness and degenerate cases.
 
 
*July 5 – July 11( 1 week)
 
**Implement testing suite for BSP tree implementation of the Bernstein algorithm.
 
**Adding documentation to OpenSCAD framework
 
 
*July 12 – July 25 ( 2 weeks)
 
 
**Implement and test subroutines for Numeric substrates.
 
**Testing and debugging.
 
 
**July 26 – August 8 ( 2 Weeks)
 
**Add functionality for Geometric Substrates together with sub routines.
 
**Testing and debugging of Convex polygon constructor for clipped plane
 
 
*August 9 – August 22( 2 Weeks)
 
**Inside-out tests, address robustness issues with modules and improve performance of libraries.
 
**Write paper on Comparison of CSG based algorithms in relation to OpenSCAD Implementations.
 
**Check code for memory leaks and performance analysis, with unit tests added for implemented modules.
 
 
*August 23 – August 29( 2 weeks)
 
**Pencils Down, Code clean up.
 
**Review documentation and Finalize paper writing.
 
**Final evaluation, Submission of code to melange.
 
  
 
= Time availability =
 
= Time availability =
I would be able to offer over 40 hours on the project. However, since the project would start during our second Semester; I would be coding mostly during the nights up to late June or early July when our semester ends. Also, to meet up with the demands of the project, I would be coding during weekends  and regularly informing my mentors on the status of the project and regularly updating my logs in this respect.
 
  
 
= Why BRL-CAD =
 
= Why BRL-CAD =
After participating in GsoC 2013 with BRL-CAD, I fell in love with CAD and will love to spend my summer contributing code to improve BRL-CAD software.
 
  
 
= Why Me =
 
= Why Me =
First of all hailing from Africa with lack of computing infrastructure posed a lot of great challenges to  ascend to hackerdom especially with the scarcity of good programmers and lack of Internet access. Working with BRL-CAD in 2013 taught me a great deal especially working with the brightest researchers in this field. I believe my participation in GSoC this year would not only give me a great learning experience but also heighten my ambition of being a great Computer Science researcher in Africa. I see this  project as both an intellectual challenge to impact change through open source software.
 
 
= Contributions =
 
 
 
== Past Coding Work ==
 
 
*GSoC 2013:
 
**http://www.google-melange.com/gsoc/project/code_samples/google/gsoc2013/ch3ck/5721450489053184
 
 
*Xorg Evoc 2014
 
**https://github.com/Ch3ck/xorg-xserverhttps://github.com/Ch3ck/xorg-xserver
 
 
*Other Projects
 
**https://github.com/Ch3ck/SAMS
 
**https://github.com/openmrs/openmrs-core
 
 
 
==Current OpenSCAD work ==
 
 
Here are my current and ongoing contributions on OpenSCAD
 
* Rework AbstractFunction::evaluate to virtual function only fixing calls
 
**https://github.com/openscad/openscad/pull/1285
 

Please note that all contributions to BRL-CAD may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see BRL-CAD:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)