Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
intersection of two surfaces

Subject: intersection of two surfaces

From: Ben

Date: 10 Nov, 2010 00:28:04

Message: 1 of 12

Hey everyone,

I want to find the intersections of two surfaces which are represented using triangular meshes. Does anyone know how to achieve it? I guess this should be a solved problem. Is there some code available somewhere?

Or does anyone know the solution for a simpler problem of finding intersections of a surface and a cylinder? Again, the surface is a triangular mesh, while the cylinder could be represented using a triangular mesh or an equation.

BTW, I did not find a solution in FEX.

Thanks a lot.

Subject: intersection of two surfaces

From: Aurelien Queffurust

Date: 16 Nov, 2010 08:44:04

Message: 2 of 12

"Ben " <gogo.xa@gmail.com> wrote in message <ibcouk$kjg$1@fred.mathworks.com>...
> Hey everyone,
>
> I want to find the intersections of two surfaces which are represented using triangular meshes. Does anyone know how to achieve it? I guess this should be a solved problem. Is there some code available somewhere?
>
> Or does anyone know the solution for a simpler problem of finding intersections of a surface and a cylinder? Again, the surface is a triangular mesh, while the cylinder could be represented using a triangular mesh or an equation.
>
> BTW, I did not find a solution in FEX.
>
> Thanks a lot

You may be interested in reading this tech-note:
How do I plot the line of intersection between two surfaces?
http://www.mathworks.com/support/solutions/en/data/1-BDNR4J/?solution=1-BDNR4J.

and this one:
How do I find the equation of the line that intersects a 3D surface and a plane passing through 3 points of interest on the surface?
http://www.mathworks.com/support/solutions/en/data/1-9XIIEQ/?solution=1-9XIIEQ

Aurélien
http://blog.developpez.com/matlab4geek/

Subject: intersection of two surfaces

From: Ben

Date: 16 Nov, 2010 19:43:03

Message: 3 of 12

Hi Aurélien,

Thought they are not the exact problem I have, they are helpful. I will try to see how the two could be a solution of my problem. And so far, there seems be a solution for the intersections of a free surface (triangulated mesh) and a cylinder (explicitly defined).

Thanks a lot!
Ben

"Aurelien Queffurust" <tug83@yahoo.fr> wrote in message <ibtg8k$a0a$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <ibcouk$kjg$1@fred.mathworks.com>...
> > Hey everyone,
> >
> > I want to find the intersections of two surfaces which are represented using triangular meshes. Does anyone know how to achieve it? I guess this should be a solved problem. Is there some code available somewhere?
> >
> > Or does anyone know the solution for a simpler problem of finding intersections of a surface and a cylinder? Again, the surface is a triangular mesh, while the cylinder could be represented using a triangular mesh or an equation.
> >
> > BTW, I did not find a solution in FEX.
> >
> > Thanks a lot
>
> You may be interested in reading this tech-note:
> How do I plot the line of intersection between two surfaces?
> http://www.mathworks.com/support/solutions/en/data/1-BDNR4J/?solution=1-BDNR4J.
>
> and this one:
> How do I find the equation of the line that intersects a 3D surface and a plane passing through 3 points of interest on the surface?
> http://www.mathworks.com/support/solutions/en/data/1-9XIIEQ/?solution=1-9XIIEQ
>
> Aurélien
> http://blog.developpez.com/matlab4geek/

Subject: intersection of two surfaces

From: Ben

Date: 16 Nov, 2010 23:24:04

Message: 4 of 12

Hi Aurelien,

I have another geometry problem.

There are two planes which are not parallel. They intersect at a line. What I am going to find is a plane which lies in the middle of these two planes and passes the intersection line.

Thank you,
Ben

"Aurelien Queffurust" <tug83@yahoo.fr> wrote in message <ibtg8k$a0a$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <ibcouk$kjg$1@fred.mathworks.com>...
> > Hey everyone,
> >
> > I want to find the intersections of two surfaces which are represented using triangular meshes. Does anyone know how to achieve it? I guess this should be a solved problem. Is there some code available somewhere?
> >
> > Or does anyone know the solution for a simpler problem of finding intersections of a surface and a cylinder? Again, the surface is a triangular mesh, while the cylinder could be represented using a triangular mesh or an equation.
> >
> > BTW, I did not find a solution in FEX.
> >
> > Thanks a lot
>
> You may be interested in reading this tech-note:
> How do I plot the line of intersection between two surfaces?
> http://www.mathworks.com/support/solutions/en/data/1-BDNR4J/?solution=1-BDNR4J.
>
> and this one:
> How do I find the equation of the line that intersects a 3D surface and a plane passing through 3 points of interest on the surface?
> http://www.mathworks.com/support/solutions/en/data/1-9XIIEQ/?solution=1-9XIIEQ
>
> Aurélien
> http://blog.developpez.com/matlab4geek/

Subject: intersection of two surfaces

From: Roger Stafford

Date: 17 Nov, 2010 03:15:06

Message: 5 of 12

"Ben " <gogo.xa@gmail.com> wrote in message <ibv3qk$end$1@fred.mathworks.com>...
> .......
> There are two planes which are not parallel. They intersect at a line. What I am going to find is a plane which lies in the middle of these two planes and passes the intersection line.
> .......
- - - - - - - - - - -
  Let the two planes be defined by equations

 a1*x + b1*y + c1*z + d1 = 0

and

 a2*x + b2*y + c2*z + d2 = 0

in which vectors [a1,b1,c1] and [a2,b2,c2] are normalized to be of unit length (a^2+b^2+c^2 = 1.) Then

 (a1+a2)*x + (b1+b2)*y + (c1+c2)*z + (d1+d2) = 0

is the equation of the desired plane which bisects the dihedral angle between the two planes. (These coefficients cannot be all zero because the two given planes are not parallel.)

  Notice that there is a second solution to this problem

 (a1-a2)*x + (b1-b2)*y + (c1-c2)*z + (d1-d2) = 0

which also is a valid plane and orthogonal to the first solution. One of these planes bisects the acute dihedral angle, and the other the supplementary obtuse dihedral angle, between the two given planes.

Roger Stafford

Subject: intersection of two surfaces

From: Ben

Date: 17 Nov, 2010 04:12:03

Message: 6 of 12

Thanks a lot, Roger! I will try this immediately!

Ben

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibvhbq$9f4$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <ibv3qk$end$1@fred.mathworks.com>...
> > .......
> > There are two planes which are not parallel. They intersect at a line. What I am going to find is a plane which lies in the middle of these two planes and passes the intersection line.
> > .......
> - - - - - - - - - - -
> Let the two planes be defined by equations
>
> a1*x + b1*y + c1*z + d1 = 0
>
> and
>
> a2*x + b2*y + c2*z + d2 = 0
>
> in which vectors [a1,b1,c1] and [a2,b2,c2] are normalized to be of unit length (a^2+b^2+c^2 = 1.) Then
>
> (a1+a2)*x + (b1+b2)*y + (c1+c2)*z + (d1+d2) = 0
>
> is the equation of the desired plane which bisects the dihedral angle between the two planes. (These coefficients cannot be all zero because the two given planes are not parallel.)
>
> Notice that there is a second solution to this problem
>
> (a1-a2)*x + (b1-b2)*y + (c1-c2)*z + (d1-d2) = 0
>
> which also is a valid plane and orthogonal to the first solution. One of these planes bisects the acute dihedral angle, and the other the supplementary obtuse dihedral angle, between the two given planes.
>
> Roger Stafford

Subject: intersection of two surfaces

From: Ben

Date: 17 Nov, 2010 04:18:04

Message: 7 of 12

Btw, Roger,

What if the plane is represented using a normal and a point on it? Thank you.

Ben
 
"Ben " <gogo.xa@gmail.com> wrote in message <ibvkmj$bcm$1@fred.mathworks.com>...
> Thanks a lot, Roger! I will try this immediately!
>
> Ben
>
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibvhbq$9f4$1@fred.mathworks.com>...
> > "Ben " <gogo.xa@gmail.com> wrote in message <ibv3qk$end$1@fred.mathworks.com>...
> > > .......
> > > There are two planes which are not parallel. They intersect at a line. What I am going to find is a plane which lies in the middle of these two planes and passes the intersection line.
> > > .......
> > - - - - - - - - - - -
> > Let the two planes be defined by equations
> >
> > a1*x + b1*y + c1*z + d1 = 0
> >
> > and
> >
> > a2*x + b2*y + c2*z + d2 = 0
> >
> > in which vectors [a1,b1,c1] and [a2,b2,c2] are normalized to be of unit length (a^2+b^2+c^2 = 1.) Then
> >
> > (a1+a2)*x + (b1+b2)*y + (c1+c2)*z + (d1+d2) = 0
> >
> > is the equation of the desired plane which bisects the dihedral angle between the two planes. (These coefficients cannot be all zero because the two given planes are not parallel.)
> >
> > Notice that there is a second solution to this problem
> >
> > (a1-a2)*x + (b1-b2)*y + (c1-c2)*z + (d1-d2) = 0
> >
> > which also is a valid plane and orthogonal to the first solution. One of these planes bisects the acute dihedral angle, and the other the supplementary obtuse dihedral angle, between the two given planes.
> >
> > Roger Stafford

Subject: intersection of two surfaces

From: Roger Stafford

Date: 17 Nov, 2010 04:32:03

Message: 8 of 12

"Ben " <gogo.xa@gmail.com> wrote in message <ibvl1s$3tf$1@fred.mathworks.com>...
> .......
> What if the plane is represented using a normal and a point on it? Thank you.
> .......
- - - - - - - - -
  If P0 is the point on the plane and N a normal to the plane. Then the equation of the plane is dot(P-P0,N) = 0. Or expressed in separate coordinates:

 nx*x + ny*y + nz*z - (nx*x0+ny*y0+nz*z0) = 0.

where P0 = [x0,y0,z0] and N = [nx,ny,nz].

  To use this to find your "middle" plane you need to use an N which is normalized. Do this:

 N = N/norm(N);

Roger Stafford

Subject: intersection of two surfaces

From: Ben

Date: 17 Nov, 2010 04:48:04

Message: 9 of 12

Thanks very much Roger, it's solved with your kind help!

Ben

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibvls3$q33$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <ibvl1s$3tf$1@fred.mathworks.com>...
> > .......
> > What if the plane is represented using a normal and a point on it? Thank you.
> > .......
> - - - - - - - - -
> If P0 is the point on the plane and N a normal to the plane. Then the equation of the plane is dot(P-P0,N) = 0. Or expressed in separate coordinates:
>
> nx*x + ny*y + nz*z - (nx*x0+ny*y0+nz*z0) = 0.
>
> where P0 = [x0,y0,z0] and N = [nx,ny,nz].
>
> To use this to find your "middle" plane you need to use an N which is normalized. Do this:
>
> N = N/norm(N);
>
> Roger Stafford

Subject: intersection of two surfaces

From: Ben

Date: 17 Nov, 2010 04:53:03

Message: 10 of 12

Hi Roger,

Do you further know how to find the intersection of two surface represented using triangulated meshes? Or one surface is a triangulated mesh while another is a cylinder represented using its axis (a normalized vector), a point on the axis, and the radius?

Thanks,
Ben

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibvls3$q33$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <ibvl1s$3tf$1@fred.mathworks.com>...
> > .......
> > What if the plane is represented using a normal and a point on it? Thank you.
> > .......
> - - - - - - - - -
> If P0 is the point on the plane and N a normal to the plane. Then the equation of the plane is dot(P-P0,N) = 0. Or expressed in separate coordinates:
>
> nx*x + ny*y + nz*z - (nx*x0+ny*y0+nz*z0) = 0.
>
> where P0 = [x0,y0,z0] and N = [nx,ny,nz].
>
> To use this to find your "middle" plane you need to use an N which is normalized. Do this:
>
> N = N/norm(N);
>
> Roger Stafford

Subject: intersection of two surfaces

From: Roger Stafford

Date: 17 Nov, 2010 20:57:03

Message: 11 of 12

"Ben " <gogo.xa@gmail.com> wrote in message <ibvn3f$f27$1@fred.mathworks.com>...
> .......
> Do you further know how to find the intersection of two surface represented using triangulated meshes? Or one surface is a triangulated mesh while another is a cylinder represented using its axis (a normalized vector), a point on the axis, and the radius?
> .......
- - - - - - - - - -
  Your question concerning triangle intersections involves a lot more work than I have time to put in on it. However I will give you a method of finding a vector pointing along the infinite line of intersection of two infinite planes and locating a point somewhere along this line, which may help you in carrying out this rather arduous task.

  Let N1 and P1 be a vector normal to a plane and some arbitrary point on the plane, respectively. Similarly, let N2 and P2 be a vector normal to a second plane and some point on this plane. If the planes are not parallel, the cross product of N1 and N2 will necessarily point along the line of intersection of the planes, and we will choose the point along this line which lies closest to the origin. Call these quantities N3 and P3 respectively. The matlab code for them is the following:

 N3 = cross(N1,N2);
 P3 = (dot(P1,N1)*cross(N2,N3)-dot(P2,N2)*cross(N1,N3))/dot(N3,N3);

  This can be shown to be true from the three conditions such a point P3 must satisfy. It must lie on the first plane which implies that dot(P3,N1) = dot(P1,N1). It must lie on the second plane so that dot(P3,N2) = dot(P2,N2). Finally, to be closest to the origin requires that dot(P3,N3) = 0. Using vector analysis techniques it can be shown that P3 as defined above will satisfy all three of these equations. (Or if you prefer you can choose random values for P1, N1, P2, and N2, and simply verify that the three equations always hold, allowing for round off error.)

  As you are probably aware you can compute the normal to a triangle with the three vertices P1, Q1, R1 by computing N1 = cross(Q1-P1,R1-P1). Once you have computed the above P3 and N3 for two triangles, you can compare the signs of the three quantities

 dot(P1-P3,cross(N1,N3))
 dot(Q1-P3,cross(N1,N3))
 dot(R1-P3,cross(N1,N3))

and similarly three others for the P2,Q2,R2 triangle using N2. In a triangle if any two of these quantities are of opposite sign, that means the corresponding pair of triangle vertices lie on opposite sides of the intersection line, so their connecting line segment must cross that intersection line, and this must necessarily occur in pairs. If both triangles have pairs of line segments that cross the intersection line then there may be an intersection between these triangles, which can be determined by finding the four points along the intersection line where those segments cross it. By examining the relative positions of these four points appropriately you can determine whether there is a common line segment of intersection between the triangles' interiors. (You can also see why I carefully avoided having to work out all these burdensome details.)

Roger Stafford

Subject: intersection of two surfaces

From: Ben

Date: 18 Nov, 2010 00:11:04

Message: 12 of 12

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ic1fiv$oi2$1@fred.mathworks.com>...
> "Ben " <gogo.xa@gmail.com> wrote in message <ibvn3f$f27$1@fred.mathworks.com>...
> > .......
> > Do you further know how to find the intersection of two surface represented using triangulated meshes? Or one surface is a triangulated mesh while another is a cylinder represented using its axis (a normalized vector), a point on the axis, and the radius?
> > .......
> - - - - - - - - - -
> Your question concerning triangle intersections involves a lot more work than I have time to put in on it. However I will give you a method of finding a vector pointing along the infinite line of intersection of two infinite planes and locating a point somewhere along this line, which may help you in carrying out this rather arduous task.
>
> Let N1 and P1 be a vector normal to a plane and some arbitrary point on the plane, respectively. Similarly, let N2 and P2 be a vector normal to a second plane and some point on this plane. If the planes are not parallel, the cross product of N1 and N2 will necessarily point along the line of intersection of the planes, and we will choose the point along this line which lies closest to the origin. Call these quantities N3 and P3 respectively. The matlab code for them is the following:
>
> N3 = cross(N1,N2);
> P3 = (dot(P1,N1)*cross(N2,N3)-dot(P2,N2)*cross(N1,N3))/dot(N3,N3);
>
> This can be shown to be true from the three conditions such a point P3 must satisfy. It must lie on the first plane which implies that dot(P3,N1) = dot(P1,N1). It must lie on the second plane so that dot(P3,N2) = dot(P2,N2). Finally, to be closest to the origin requires that dot(P3,N3) = 0. Using vector analysis techniques it can be shown that P3 as defined above will satisfy all three of these equations. (Or if you prefer you can choose random values for P1, N1, P2, and N2, and simply verify that the three equations always hold, allowing for round off error.)
>
> As you are probably aware you can compute the normal to a triangle with the three vertices P1, Q1, R1 by computing N1 = cross(Q1-P1,R1-P1). Once you have computed the above P3 and N3 for two triangles, you can compare the signs of the three quantities
>
> dot(P1-P3,cross(N1,N3))
> dot(Q1-P3,cross(N1,N3))
> dot(R1-P3,cross(N1,N3))
>
> and similarly three others for the P2,Q2,R2 triangle using N2. In a triangle if any two of these quantities are of opposite sign, that means the corresponding pair of triangle vertices lie on opposite sides of the intersection line, so their connecting line segment must cross that intersection line, and this must necessarily occur in pairs. If both triangles have pairs of line segments that cross the intersection line then there may be an intersection between these triangles, which can be determined by finding the four points along the intersection line where those segments cross it. By examining the relative positions of these four points appropriately you can determine whether there is a common line segment of intersection between the triangles' interiors. (You can also see why I carefully avoided having to work out all these burdensome details.)
>
> Roger Stafford

Thank you very much, Roger.
I will try to follow your explanations to see whether I can make it.

Once more, thank you,

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us