Robust CSG Boolean Evaluation (a.k.a. Robust Facetization for Geometry Export)

[brlcad]

Outline

Make CSG Boolean evaluation work 100% of the time!

Details

Central to BRL-CAD's geometric representation is the ability to evaluate Constructive Solid Geometry (CSG) Boolean expressions on geometry (i.e., "UNION", "INTERSECTION", and "SUBTRACTION"). There are many possible techniques but BRL-CAD does not yet have an implementation that reliably works all the time except for ray tracing which is robust and numerically deterministic.

Your goal will be to implement a new/unexplored method that will always work for evaluation to an explicit surface geometry representation (e.g., NURBS or polygonal mesh). This can be something based on any existing method including BSP-based methods in polygonal space, intermediate evaluation in voxel space, interval arithmetic, NURBS evaluation, error tracking methods, or simply re-implementation an existing method (e.g., Weiler’s n-manifold method) with exhaustive unit testing.

For example, OpenVDB has a boolean evaluation method implementation that works in voxel space. One could create an evaluator that voxelizes BRL-CAD geometry using ray tracing (which is 100% reliable), evaluates in OpenVDB, and then converts to polygons.

Alternative example, BRL-CAD has NURBS boolean evaluation logic that works some of the time, but hasn't been extended to cover all cases of surface-surface intersection. One could create a test suite that identifies all configurations and their current status, and work towards resolving failures one by one.

Yet another example, BRL-CAD has an implementation of n-manifold geometry boolean evaluation. You could work on re-implementing the boolean evaluation from scratch with an eye towards unit testing and performance.

Expected Outcome

Robust export of geometry to triangle mesh format using some method that reliably works every time.

Future Possibilities

• Expanded unit testing, coverage testing.
• Accelerate boolean evaluation on the GPU.
• Create an online conversion service.

Project Properties

Skills

C/C++

Difficulty

hard

Size

long (350h)

Additional Information

• Potential mentor(s): Sean Morrison
• Organization website: https://brlcad.org
• Communication channels: https://brlcad.zulipchat.com

[Neeraj8949]

I want to contribute in this project. I am good in cpp so can you tell me how I contribute in this project and also contribute from Gsoc.

[brlcad]

This is a very challenging task so you will need to demonstrate familiarity with whatever method or approach you end up proposing. You will need to research independently and ask specific technical questions as this is not a project with a prescribed solution as noted in the detailed description.

[Neeraj8949]

so CSG is right now working in BRL cad or its working but not all the time . Have we design the whole CSG or make it robust only can I get older implemented code of CSG so I can go through and see the problem and try to resolve

[brlcad]

CSG works very well for ray tracing all the time. Evaluating CSG for purposes of converting geometry to an explicit surface representation like evaluated NURBS or evaluated polygonal mesh does not work robustly (it's about 85-90% reliable). You will need to study the code and do some of your own research to understand the differences for all the possible solutions. There is a big difference between evaluating CSG in NURBS space or in polygonal mesh space.

[Neeraj8949]

can you help me to reach out the code of CSG which is using in our software .From where to I can go through it and try to sole the problem .

[brlcad]

@Neeraj8949 the primary code in question depends on the method of evaluation. There's an entire library in src/libnmg that performs Weiler's n-manifold method. There's separate logic in src/libbrep that implements CSG evaluation for NURBS geometries.

[Neeraj8949]

Thanks @brlcad I will go through the code and try to understand.

[brlcad]

This project topic is pending due to recent developments and interactions with Manifold.

[KeithSloan]

Might be wrong but see this as also applicable to FreeCAD's mesh facilities, will post something in the Forum https://forum.freecad.org/viewtopic.php?t=85496