Determine if two faces are "pointing" towards eachother

[Atheist]

Hey there.

The question in the title may sound weird, but I'm looking for a way to determine if the faces of two triangles "faces eachother" even the slightest.

The reason I need to know this is because I'm trying to write some logic for determining if a 3D mesh is convex or not.

In my attempts at this I have gotten as far as calculating the dot product (X) for the face normals of the two triangles in question:
If X <= 0 then the two normals are more or less pointing away from eachother, return false.
If X == 1 then the two normals are running parallell to eachother, return false.
If X > 0 && X < 1.... This is what I find tricky. There's something additional I have to do here to determine if the two normals (and thus also the faces) point towards eachother even the slightest.

Does my question make sense?
I'm very thankful for all the help and ideas I can get.

[Milk]

Not sure at all and all I can give is a sketchy assumption. I think you should be looking at this from the perspective of one of the faces where it becomes similar to the logic to whether the other face should be rendered or not. Something like transform the second face as if the first face is looking straight down its normal then derive something with the resulting normal of the transformed second face, either that or see if the transformed second face is running clockwise or anti-clockwise.

sorry, not much help there

[jemidiah]

I was going to just suggest computing the dot product of the normals, but apparently that's not sufficient. Ah, perhaps you meant to ask the following. Pick one of the triangles and create an infinite right triangular prism from it by extending the triangle along the normal. Do the same with the other triangle. Do you want to know if the two prisms intersect? If so, some plane-plane intersection logic should work.

Edit: Actually, I got to thinking that you said this was for convexity testing, in which case the above problem is very likely not what you meant. How about this version. Take the first triangle and extend it in all directions into an infinite plane, cutting 3D space into two halves. Does any part of the second triangle lie on the half with the first triangle's normal? If not, then no point of the second triangle can belong in a convex figure containing the first triangle, which is at least a way to throw out some non-convex figures.

[Atheist]

Thanks for the input guys, I really appreciate it!

I had never thought of the idea to extend the triangle into a plane and perform point-plane checks with the rest of the mesh. By doing like that I can tag an individual triangle as "part of convex geometry", which will be very beneficial for me!

I just realized something though. I initially thought of my triangles as simple faces with one normal but thats not the case. When i perform collision detection on my triangles I am calculating the normal of a point on the triangle by interpolating between the triangles vertices.

Because of this, I am lead to believe that, for one triangle, I will need to create 3 planes.
Given a triangle consisting of 3 vertices (v1, v2, v3) i would create three planes.
These planes would be centered around v1, v2 and v3 respectively. The normal of these planes would be equal to the normal described at the vertex.
Does this make sense to you guys?

Now to the problem I have run into.
How do I define a plane when all i have is a point in space and the plane normal?

I am confident you guys can help me with this. I have been struggling with it the entire day.
Thanks!

[Atheist]

Silly me, It came to me as i wrote my last post.
This is the plane equation:
Ax + By + Cz + D = 0

I have all values except D, so:
Ax + By + Cz = -D

Where (A, B, C) is the normal for my plane, and (x, y, z) is a point on the plane.

Is this correct?

[jemidiah]

Yes, your plane equation is correct. It actually has a very simple interpretation in terms of dot products. First, let (p, q, r) be a point on the plane. We have, using your equation,
(A, B, C) dot (p, q, r) = -D

Replace x, y, and z with X = x-p, Y = y-q, Z = z-r, so the equation becomes
(A, B, C) dot (x, y, z) = (A, B, C) dot (p, q, r)
<=>
(A, B, C) dot (x-p, y-q, z-r) = 0
<=>
(A, B, C) dot (X, Y, Z) = 0

Obviously, (X, Y, Z) = (x, y, z) - (p, q, r) is a vector pointing from (p, q, r) to (x, y, z). Such a vector is in the plane if and only if it is perpendicular to the vector (A, B, C), which must then be the plane's normal.


I didn't follow your other post's discussion resulting in the need to create 3 planes for each triangle. Are you trying to find ways of determining if the triangle and plane intersect? If so, a simple dot product calculation suffices. Let P be a point on the plane and N be the plane's normal. Suppose the triangle's vertexes are v1, v2, and v3. (v1 - P) is the vector pointing from P to v1. If N dot (v1 - P) is negative, then v1 is below the plane. Doing the same for v2 and v3, we can determine if each vertex is below the plane. If so, the entire triangle is below the plane, since the point of closest approach is necessarily at a vertex [rigorously, you can use some simple gradient calculations to prove this; or you can just imagine the situation and satisfy yourself]. If you wanted to figure out if the plane and triangle intersect, that occurs if and only if one of the dot products calculated is negative and another is positive, thanks to the connectedness of the triangle and the preceding property.

[Atheist]

This is all part of a preprocessing routine for 3D models that is used for my raytracer project.
If I can determine that a certain triangle is "part of a convex geometry" in a mesh, then I know that any ray that reflects off of that triangle will not need any intersection-tests against that same mesh.

When a ray intersects a triangle, I find the normal at the intersection point by interpolation, then reflect the ray around the normal. Because of this, I can not treat the triangle as "face" consisting of only 1 normal.

Here is what I' doing in some sort of semi-pseudo-code:

For each triangle in mesh
    Plane plane1 = CreatePlaneFromPointAndNormal(triangle.Point1, triangle.Normal1)
    Plane plane2 = CreatePlaneFromPointAndNormal(triangle.Point2, triangle.Normal2)
    Plane plane3 = CreatePlaneFromPointAndNormal(triangle.Point3, triangle.Normal3)

    For all other triangles in mesh
        If AnyPointAbovePlane(plane1) Or AnyPointAbovePlane(plane2) Or AnyPointAbovePlane(plane3) Then
            triangle.PartOfConvexGeometry = False
        End If

I have made an attempt at implementing this and I'm not too sure what to think of the results.

Here is a sample model (The teapot, cup and spoon are not separate meshes, they are one!):
http://i.imgur.com/Zgayd.png
And here is the result (Triangles that are "part of convex geometry" are colored green, otherwise they are red)
http://i.imgur.com/z0WQW.png

It looks "kind of" good, with the lower part of the teapot being green, and the band of green gets smaller on the front side of the teapot, possibly because of the spout (is that the correct word?) on the teapot.
There is also a spot of green on the very top of the tiny handle on the teapot (can not be seen from this angle), which is very good!
However...when I took a look on the backside of the teapot I see that the green band goes all the way around, which is undesireable. (rays reflected against the backside of the teapot, and most often will, intersect the cup!)
So despite showing promising results, something is wrong! I'm not sure how to proceed.

Going to take another stab at this tomorrow, I'm sleepy now!

[Atheist]

I see that ive made a misstake in my semi-pseudo-code... The calls to CreatePlaneFromPointAndNormal are passed normal1, normal2 and normal3 respectively. I cant edit my post at the moment...its a pain when your on an ipad. EDIT: Its easier on a Lenovo - fixed!

[jemidiah]

Yup, spout is the right word .

Can you give me a situation in which plane1, plane2, and plane3 from your pseudocode differ? They should be equal in all cases, since triangle.Point1, Point2, and Point3 should lie on the same plane, and you used the same normal, triangle.Normal1, in each case.

I'd have to see your code to attempt to explain why the green band goes all the way around. The code must not be marking teacup triangles as "below" those teapot triangles for some reason.


Perhaps it's a bit early to suggest this, but you could do multiple levels of this same optimization. That is, you could replace the plane with a cone, say with a 45 degree angle. If the angle at which the ray will be reflected off the triangle is > 45 degrees, and the cone didn't intersect the rest of the mesh, you can skip collision tests with the rest of the mesh. There are many generalizations and tweaks--keeping the results for cones at many angles; different shapes besides cones, like spherical coordinate slices, or cones with a smaller cone taken out of the middle; etc.


Edit: Ah, didn't see the second post. What precisely are normal1, normal2, and normal3? Perhaps I'm being dense.

[Atheist]

I'll give you more information and code once I get home from work!

Thanks!

[Atheist]

I am going to try explaining this a bit better, let me know if I make no sense.

In these 3D meshes, all information about normals are stored in the vertices. All triangles in the meshes share vertices. Because of this, the normals described by each vertex are kind of an "average" of the surface normals of the triangles it belongs to.

Now brace yourself for some artistic wonders...
Imagine a 3D hexagon (here depicted in 2D, easier to draw!)

Its surface normals would be pointing like so:


But since we are only storing normal information in the vertices, which are shared. The normals looks like this:


The intermediate normals are interpolated from the surrounding normals:


This causes the shape get a smoother look when rendering:


Where it would otherwise look like this:


So this is why I can not treat a triangle as a simple face with only 1 normal. Each of the 3 vertices that makes up the triangle will contain different normals. Because, looking at the normals only, it would appear more like a curved surface rather than a flat triangle.

I'll post my code shortly...

[jemidiah]

Sorry for the delay. I was on a trip and away from easy access to broadband where I was staying. The thought of browsing over dial-up was too painful to consider seriously.

I understand about the normals, and that makes it significantly more complicated. Well, I'm not certain what formulas you've used--is the "vertex normal" just an average of the three adjacent surface normals? Are they weighted by surface area? Something else?

In any case, lemme think if my method can be adapted... yes. The code you posted used the triangle vertexes as base points, which won't always work. You're reflecting from a plane passing through the interpolated point (not a vertex) determined by the interpolated normal, which is not the same plane. Especially if the triangles are large and have a large angles between them (so the vertex normals are quite different), you'd get incorrect results in some edge cases where a given point is close to, but not quite, "convex" [inasmuch as any reflected ray from that point cannot hit the same mesh].

One saving grace is that interpolated normals are simply convex combinations of vertex normals. What happens if you change your pseudocode to...

For each triangle in mesh
    Plane plane1 = CreatePlaneFromPointAndNormal(triangle.Point1, triangle.Normal1)
    Plane plane2 = CreatePlaneFromPointAndNormal(triangle.Point2, triangle.Normal2)
    Plane plane3 = CreatePlaneFromPointAndNormal(triangle.Point3, triangle.Normal3)
    Plane plane4 = CreatePlaneFromPointAndNormal(triangle.Point1, triangle.SurfaceNormal)

    For all other triangles in mesh
        If AnyPointAbovePlane(plane1) Or AnyPointAbovePlane(plane2) Or AnyPointAbovePlane(plane3) Or AnyPointAbovePlane(plane4) Then
            triangle.PartOfConvexGeometry = False
        End If