Math “expert” wanted… Algorithm for finding line of two crossing areas

I’m going to create a shape-class containing a lot of flat polygon areas.
I will make it possible to subtract one shape from another and then I need an algorithm to se if two polygon-areas in the 3D-space crosses each other, and if in which line the crossing is.

I see there should bee some kind of linear algebra calculations but I do not really know how to start constructing my c++ shape classes.

Looks like your doing something similar to CSG (Constructive Solid Geometry) with the use of BSP (Binary Space Partitioning) trees. Do a google for sites about BSP trees and you should get the idea about how to do it.

I also have an unfinished site (doesn’t look like I will have time to finish) which may give you an idea about one way of doing it. If you are using 2D shapes, they must be convex or concave but constructed entirely out of convex sub-polygons. If you are using 3D shapes, they must be convex or concave but constructed entirely out of convex sub-polyhedra.

http://pages.cpsc.ucalgary.ca/~hassana/csg/csg_tut.html

As for creating classes, it might help to start with a Point and Vector class, then a Polygon class (array of points), and finally a Shape class (which is an array of polygons).

P.S. I am not a math “expert”, just a guy with some experience, so I like to use a lot of pictures :slight_smile:

Thank you for that “BSP trees”-tip.

I’ve searched for CSG implementations but no success.

The BSP method that hkyProgrammer88 mentioned is an excellent one. Turn your polygon edges into hyper-planes (walls coming out of the plane), build a BSP from these planes, and use a tree-merging strategy to perform the CSG. I used to have an implementation of Bruce Naylor’s tree-merging algorithm around, but I can’t find it.

Note that if your polygons will always be convex, things get quite a bit easier, as this reduces the process to splitting polygons along the edge hyper-planes, and keeping/eliminating the desired bits. This will work for non-convex polygons as well, but requires that you tesselate them prior to the CSG operation.

Check out question 11 here:
http://www.faqs.org/faqs/graphics/bsptree-faq/

By the way, this stuff doesn’t require an advanced degree in mathematics. If I can understand it, anyone can :slight_smile: .