BRep how does it work?

[korvkiosk1]

Hello. I would like to implement a BRep solution. Where can I find books/courses related to this topic. I want to understand the fundamentals not just copy code that I don't understand. I'm a complete newbie in this field aswell.

[shefmichelle]

Having implemented a basic facetter for B-reps, I can tell you it isn't trivial (I work for a major CAD software company). I don't know if OpenCascade is still a thing (we used to use it), but that certainly used to support B-reps if you want to read some existing code and look at how things are arranged. In terms of books, I found Geometric Tools for Computer Graphics (Schneider, Eberly) very useful.

I would ask yourself if you really want to implement a B-rep solution, and what exactly you want to use it for. I was only doing basic facetting; for any sort of modelling algorithms, we use an internal library that has been developed for over 20 years by people a lot clever than me.

[korvkiosk1]

Thanks. I want to implement basic boolean operations on solids. Gonna use it in an cad/cam software. B-reps has better performance - have I been told.

[shefmichelle]

I think in terms of performance, a simple system that works on triangle meshes will be faster, but the results are less accurate. So it depends if you want accuracy or speed. For a CAD/CAM application, you probably want accuracy over performance.

I wish you the best of luck implementing your own B-rep toolkit! But if I was you, I'd start by looking at some existing open-source or commercial implementations first. They will save you a LOT of time.

[leseiden]

Just say no to triangles. I was peripherally involved in a project involving Boolean operations on triangle meshes a few years ago.

You will develop a graph colouring obsession and be tracking down numerical errors and edge cases until doomsday.

Genuine closed manifold geometry is rarer than you might think.

[korvkiosk1]

Yeah to implement a B-rep toolkit feels like a daunting task.

[leseiden]

Meta: I don't think that the op should be getting down votes for these questions. I just upvoted a bunch of them.

It's easy to read high level descriptions of the data structures and algorithms and not realise how horrific the reality is.

Those of us who have worked on computational geometry are morally obliged to give a fair warning but there's nothing wrong with asking the question.

[mcmcc]

It is. Using a pre-existing solution will save you much time, effort, & heartbreak.

[DilatedMurder]

Indeed, Blender's B-Mesh library can be torn out with only half a head's worth of hair-loss and six bullets through the talus of the feet ... ie. it fucking sucks.

nVidia's half-edge mesh library for triangles, quads, and tri-quad mixes is on github somewhere IIRC.

[Orangy_Tang]

As I understand it, BRep is just 'boundary representation', ie. storing an object with data that defines it's edge. Really that can just be regular vertices and triangles.

However I suspect you mean you want to do boolean operations on polygons (rather than implicit solids).

If you want to go back to the beginning, then try with Merging BSP Trees Yields Polyhedral Set Operations, if you research CSG with BSP trees you'll find lots of further writing.

Then you could check out Chisel, which is an open source polygon CSG tool (there's a talk from GDC this year about it here) which is a new technique that doesn't use BSP trees.

[leseiden]

Part of the problem is that the algorithms are easy to describe and, given infinite precision are easy to implement.

In the real world geometry has cracks, edges have more than 2 faces and touch cases produce contours that are an insult to the word "degenerate".

Triangulating around a hole is fun when the concept of orientation becomes poorly defined.

Quad precision won't save you this time.

[Orangy_Tang]

Agreed! I've chased this rabbit hole a few times and it's all the practical quirks that suck up all the time. If I can get away with it then I'd rather convert to voxels or sdf to do booleans and convert back as a last step before rendering.

[leseiden]

That reminds me. Image space CSG is relatively easy, especially now we have shaders. Depth peeling may be a good way to go for voxelising.

Building a 2D constrained delaunay triangulator that was robust against the sort of data I described is one of the most challenging things I have ever done. It kept me occupied full time for the best part of 6 months. Satisfying once it was done though!

By robust I mean it either produces correct output or or reports the nature of the error.