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

Answer 3

Probably not efficient, but here is an idea.
You calculate intersection lines between each two individual triangles.
Then you add triangle edges to this set, and calculate intersection points between each two lines inside it.
Find out which of these points are invisible from the top, and remove them from the set. This can be done using ray casting and looking for intersection, but there are probably more efficient ways.
You end up with a set of points that are the vertices of the topmost mesh.

Answer 4

You can look at this as height field on triangle B=[(0,0),(0,1),(1,0)].

Since plane is defined as heights on corners of B, height of plane on B inner point can be calculated with barycentric coordinates. With given:

• plane with heights (a,b,c) on corners of B
• point P in B with barycentric coordinates (x,y,z) [x+y+z=1, x,y,z>=0],

height of plane on point P is x*a + y*b + z*c.

Natural barycentric coordinates for point P=(x,y) in B is (x,y,1-x-y).

With this it is easy to calculate intersection line of 2 planes, (a1,b1,c1) and (a2,b2,c2), in barycentric coordinates. Just equalize where 2 planes have same height

x*a1 + y*b1 + (1-x-y)*c1 = x*a2 + y*b2 + (1-x-y)*c2
=>
x*(a1-c1-(a2-c2)) + y*(b1-c1-(b2-c2)) + c1-c2 = 0

With 0 <= x,y <= 1 and x+y <= 1, 2 planes this is equation of 2 planes intersection line in B.

I think that there are 2 approaches that can be used for creation of resulting height field (top most layer):

Iterative adding new triangle

To support it, it is needed to have structure that is partition of triangle B into polygons. Polygon is region of triangle where one plane is the highest. Since we are dealing with planes, polygons will be convex and one plane can produce at most one polygon. Adding new triangle and calculation of intersections with existing height field polygons will produce new polygon (intersection lines and border of B). This new polygon is added to height field. If existing polygon is intersected than part is removed. If existing polygon is overlapped than polygon is removed.

Propagation of intersection front line

1. Start from one corner and take plane that is the heighest on it (e.g. plane wiht max(a_i)). Set front line to that corner.
2. Find planes that intersect starting plane with intersection lines nearest to front. Move front to these intersection lines.
3. Take one (any) plane that is on front line and make intersection with not processed planes with intersection lines nearest to front. Move front to these intersection lines.

Repeat 3. until front line covers triangle B.

I prefer second algorithm.