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) |
− | ** | ||
**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 44: | Line 45: | ||
− | + | *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. | 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. | ||
Line 51: | Line 52: | ||
Below describes the use of BSP based algorithm for CSG evaluations than CGAL's Nef-based Polyhedra system. | 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. | |
− | 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. | 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 | + | **Numeric Substrates |
In this system, a plane is a quadruple of floating point numbers interpreted as coefficients of a plane equation. | 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 | + | ***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. | + | ***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 | + | ***Point Validity: if a point A(p,q,r) is valid if i'ts determinant is non zero |
Pa Pb Pc | Pa Pb Pc | ||
Qa Qb Qc | Qa Qb Qc | ||
Ra Rb Rc | 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 | + | ***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 Pd | ||
Pa Pb Pc Qa Qb Qc Qd | Pa Pb Pc Qa Qb Qc Qd | ||
Line 75: | Line 75: | ||
These predicates are implemented as static filtered floating-point predicates in the style of shewchuk, but deviations will be done to support double precision. | 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 | + | **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. | 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). | + | ***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-. | + | ***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. | + | ***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 concident with h | ||
if s is similarly oriented to h | if s is similarly oriented to h | ||
Line 101: | Line 101: | ||
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. | 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. | ||
− | = | + | = Links = |
− | + | = Deliverables = | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | =Deliverables= | ||
− | |||
− | |||
− | |||
= Development Schedule/Timeline = | = Development Schedule/Timeline = | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= Time availability = | = Time availability = | ||
− | |||
= Why BRL-CAD = | = Why BRL-CAD = | ||
− | |||
= Why Me = | = Why Me = | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |