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.

CSG Algorithm for OpenSCAD(Current Implementation)

OpenSCAD is a parametric CSG based modelling software; which means objects are manipulated by editing the CSG descriptions of objects being rendered. It employs two different mechanisms for processing CSG descriptions. It uses the OpenCSG library for visualization during editing and the CGAL library for export created a meshed BREP output. However, the OpenCSG Library uses the Goldfeather and SCS algorithms to evaluate the 2D images of a CSG object from the given perspective. This is beneficial because of its speed and ability to render complex images within a short time.

However, CGAL employs the Nef Polyhedra for evaluating boolean operations on CSGs. It is robust and is able to handle non manifold input but proves incredibly slow in practice and not very suitable for time critical applications . There are also overflow issues that arise with using large size polyhedra. The used of BSP tree proves more efficient for CSG evaluations than CGAL's Nef based polyhedra . Below describes the use of BSP based algorithm for CSG evaluations than CGAL's Nef-based Polyhedra system.

BSP Tree based Implementation of Boolean Operations

Bernstein et all[1] presented an exact and more efficient method for evaluating 3D polyhedra already supported by OpenSCAD. Results from tests showed for a BSP tree implementation which 16-28X faster at performing iterative computations than CGAL's Nef polyhedra . The use of a BSP-tree based boolean algorithm allows the explicit handling of all geometric degeneracies without treating a large number of cases. There are also efficient CSG to BSP algorithms which could be used for easy representations in both formats.

BSP trees afford an alternative to B-rep algorithms that avoid their concomitant case explosion by explicitly handling all degenerate configurations of geometry. They have demonstrated to have suitable performance for interactive volumetric sculpting.

• Numeric Substrates

In this system, a plane is a quadruple of floating point numbers interpreted as coefficients of a plane equation.

• • Concidence: Two planes p, q are coincident if and only if the determinant of all 2x2 minors are 0
  • coincident orientation: if p and q are coincident and Pa.Qa, Pb.Qb, Pc.Qc, Pd.Qd are non negative.

• • Point Validity: if a point A(p,q,r) is valid if i'ts determinant is non zero

 Pa Pb Pc
 Qa Qb Qc
 Ra  Rb Rc

• • Orientation: Given a point A(p, q, r) is valid and it lies behind, on, or in-front of the plane S if and only iff the following expression is negative, zero or positive

                            Pa Pb Pc  Pd
Pa Pb Pc                    Qa Qb Qc Qd
Qa Qb Qc       *            Ra Rb Rc Rd
Ra Rb Rc                    Sa Sb Sc  Sd

These predicates are implemented as static filtered floating-point predicates in the style of shewchuk, but deviations will be done to support double precision.

• Geometric Substrates

In the preceding step, we defined planes as primitives, points as triples of planes and 4 predicates operating on these plans; now we define a convex polygon type for a constructor and splitting routine.

• • Convex polygon: This is a plane of support, s with a bounding plane {Bi} I £ Z. This vertices given by Vi = (s, Bi-1, Bi).

• • Construction of a Convex Polygon from a Plane: Given a plane h, this operation constructs a convex polygon representing h clipped by a very large box. The output polygon serves as a stand in for the infinite extent plane. A consistent axis aligned “very large box” is used for all calls to the constructor and consists of volume spaced bounded by planes X+, X-, Y+, y- , Z+, Z-.

• • Splitting a Convex Polygon by a Plane: Since polygon splitting may be viewed as two successive and complementarty instances of polygon clipping. The algorithm below similar to the Sutherland-Hodgman style polygon clippers, rather than deciding if and when to insert a crossing point to the output stream, we decide if and when to insert the splitting plane into the output stream.

Algorithm

If s is concident with h

 if s is similarly oriented to h
     Return (s, {Bi}i e Zn)
 Else 
    Return nothing

Else

  For I e Zn(in order)
     Output planes as specified by table lookup using:
      o(s, bi-2, bi-1, h)
      o(s, bi-1, bi, h);
      o(s, bi, bi+1, h)
   Return (s, output)
                 Algorithm: Clip(s, {bi}i e Zn) by h

The Above algorithm works in interoperability between input and output that is between the Point-based polygon soup and the Plane-based Representation working with Boolean operations.