A Boolean Algorithm for Geometric Modeling

[@jakeehrlich8113]

I have been trying to figure these algorithms out on my own. I could not manage to find a book or get google to give me an original paper on the topic. I had managed to mostly figure out and find references for the 2D case and have that mostly working but I was really struggling with how to handle extrusion and 3D curves. Thank you so much for these videos, this was so hard to find!!! I didn't know curved surfaces used UV mappings, that makes so much sense now and it lets you decompose it all into 2 2D curves instead of all the broken mess I was attempting and failing.

[@sonypriya5685]

Great video thank you

[@Adiounys]

This is nice intro. I hope I will make 3D boolean some day. I've wrote algorithm for 2D boolean and already know it's much more convoluted in practice. Rules are simple but then consider all special cases, fight rounding errors, make it robust and reasonably efficient... and I didn't even support parametric curves... It was a challenge (or is still), and in 3D - beyond my head at the moment :) It seem there are many arbitrary things to consider, like If point lies on a line, is it considered in or outside the shape? Or what happens if shape is not closed, on which side is the inside? Or like that green surface in 6:00 - what result suppose to look like? If the blue surface just touches the green surface, cutting it in the middle and creating two identical edges, should blue surface be left with duplicate edge as well? So many question... I would love to hear how you solved some of such quirks :)

[@math4every1]

Yes the devil is certainly in the details. That is pretty well true about most geometric modeling applications. Boolean operations do a lot of the underlying work for modern features but you will not find any package that works 100% of the time. There are so many issues with tolerance and tangency the best you can hope for is to work the majority of the time.

[@jamesrockford2626]

This is great... I'm curious, where/how did you learn this? Is there a book I can buy?

[@math4every1]

My background is in mathematics and I have been developing geometric modeling software for almost 30 years now. I think a good place to start learning more would be Michael Mortenson's book Geometric Modeling. It is very clear and well written.

[@jamesrockford2626]

thanks... would I be able to read about any of your software apps on the net?

[@math4every1]

Here is a link to our software package: www.zwsoft.com/zw3d/

[@jamesrockford2626]

Great product Thanks

[@karlomiletic9720]

Thank you for great videos, since you have much experience in this field, is there any new ways to represent Solids other then B rep and CSG and use winged edge data structure to represent them ? And could we preserve dependencies between edges, vertex and surface data on a different approach ?

[@chrischoir3594]

Very nice

[@d.j.peters]

First thank you for sharing this kind of math stuff and sorry about my bad english. How ever after I view this video I have more questions than before :-) (2D only) First I was missing the point that the odd even rule isn't for the intersection points self it's for the points of the rest of the shape contours. The points of intersection self are a part of the shapes border so they can't be inside or outside of the shapes. "Find all intersection" should be "Find all intersecting and parallel overlapped segments". For example two equal rectangles the right vertical segment from shape A shares the same space as the left vertical line of shape B. In this case the two vertical segments are parallel and mathematical no intersection point exists. But this kind of segments must be counted also for a UNION operation for example. In your simple example what are if the red triangle shape B are smaller and complete inside of the blue shape A. In this case there are no intersection at all but all segments of shape B are inside of shape A. How to subtract the small triangle shape B from blue shape A ? I have more open questions but enough for now. Thank you DJ

[@math4every1]

Yes if you have coincident regions you have to treat them separately. I was mainly trying to present the basic algorithm. There are a number of details I did not cover because I wanted to keep the video reasonably short. Some other things to consider are when firing a ray you have to watch out for the ray hitting a vertex. You have an intersection with 2 edges but this only counts as a single hit. Also if you hit an edge at a tangent location or point of tangent discontinuity you can get a wrong count. Usually it is just easier to try re-firing the ray in a different direction. Writing code for geometric models typically requires numerous checks for abnormal occurrences.