3d intersections of triangles algorithm - Displaying the topmost plane

Question

I am trying to calculate the top most intersection of an arbitrary number of planes, with no joy! I am using actionscript, but just need find an algorithm that i can implement.

Problem:

• consider 3 vertical axis.
• The user enters 3 points for each triangle/plane such that the points of the triangle lie on one of the axis.
• The user can enter an arbitrary number of triangles
• I need to find the topmost layer of these triangles and display it on the screen as well as the coordinates of interection.

Here is a picture to clarify what I mean with 2 triangles:

However, when we allow for more than 2 triangles, I get awkward lines of intersection.

Answer 1

I'm interested by your problem much so I described the algorithm and implemented it in C++ (I dont know AS as good as C++). The main idea of the algorithm is iterative recalculation of the top surface while adding new triangles.

After triangles have intercepted they can change their form into polygons with custom vertex number. So each triangle is initially transformed into plain polygon. Each polygon instance includes its plane equation and a set of polygon faces. Each face as a data structure includes one vertex of polygon and equation of vertical boundary plane crossing that vertex and the next vertex in polygon vertex sequence. (Thus the order of faces in a set is important.)

Lets think of the top surface as of a polygon set. While new polygon is adding we should iteratively recalculate faces of all the surface polygons. Algorithm of face recalculation includes following steps:

1. Find two points on the edge of polygon and lying on the line of polygon interception. This points should become new vertexes of the considered polygon after removing of its covered parts. Each of these points could be calculated as intersection of 3 planes: considered polygon plane, new polygon plane, one of considered polygon faces. Points not on the edge of the polygon should not be taken into account.
2. If there are less than two interception points one of polygons is fully overlap the other one. Thus we should determine the upper one. Lets consider any point of current polygon, not laying on the line of polygon interception. We could take its x and y coordinates, calculate the point inside of the new polygon plane and compare their z coordinates.
3. If there are two points the polygon face set should be modified. After the point calculation we also know indexes of the crossed faces. Considering the point inside of the index range, the faces set part to be removed can be determined.
4. Remove overlapped faces from polygon and insert into polygon the faces calculated on the interception points basis.

Not to flood on this page I've put the code into pastebin.

Answer 2

You are constructing your surface of interest between the three vertical "axes". The surface is bounded below by a base. Bound it above so that the problem is contained in a triangular prism.

The volume above your surface is a convex hull formed by intersecting planes (to wit: the cap, three sides, and triangle intersections). There is a lot of theory and code about convex hulls.

I don't know ActionScript, but a quick internet search on "convex hulls intersecting planes" and such terms led me to this code which (purports to) solve your problem:

http://nauful.com/pages/convexhull.html

Hope this helps, Glenn