4

I have an issue that I can't quite seem to find a starting point on; I'm not even sure I can describe it well enough to get an answer.

I need to find the normal of an equilateral triangle in 3D space without knowing the points of the triangle beforehand. Think about taking a photo of a triangular "yield" street sign from any angle, and determining the out-facing normal of the sign from that photo. (I'm not doing that, exactly, but similar - so I'll use the sign/photo metaphor from here on).

** UPDATE **: This same question came up the day before I asked my version, which you can view here. Thanks to BlueRaja for pointing me there. I think the discussion there will answer the question. However, a computational approach is presented below which is also very interesting.

I know how to find the normal of a triangle when I create the triangle in code, but am unsure of how to map points to the triangle in the photo in 3D. I know the length of each side, so I know how far apart the points should be in any orientation. I can build an interactive tool that I can overlay a triangle and rotate it into location and get the points from that, but I need to do this without interaction. Doing that also doesn't help me figure out the math involved.

I'm not even sure I need to determine the points as much as just finding the correct rotation matrix.

I'm just not able to figure out where to start... Searches for the concept come up empty or just not what I'm looking to do (e.g.: they are 2D transforms not 3D)

It's also possible I'm overly complicating things and there is a simple transform equation that would do this in its sleep.

Thoughts? Thanks in advance!

Community
  • 1
  • 1
  • Be prepared to get 2 results from your calculations; one for the triangle "in front" of the projection plane, and one for "behind". – Ignacio Vazquez-Abrams Jan 17 '10 at 04:47
  • Indeed, I'm used to dealing with this for 2D line normals too. But thanks for the reminder. –  Jan 17 '10 at 04:51
  • Have you tried searching for computer vision resources? This seems like the sort of problem they'd tackle often. There's also a computer-vision tag on SO that might be appropriate. – celion Jan 17 '10 at 14:54
  • @celion: Good point - added CV tag. Thanks. I had searched many many resources before asking here; hard to search for what i'm not exactly sure i'm looking for :-) –  Jan 17 '10 at 15:28

2 Answers2

0

I feel like I just answered this yesterday.

Community
  • 1
  • 1
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • 2
    No, that answer is for three known points. Here the points are completely unknown. All you have to go on is the foreshortened projection onto a plane. – Ignacio Vazquez-Abrams Jan 17 '10 at 04:43
  • Read the comments - I tell you how to find the points in 3d, knowing what they are in 2d (ie. knowing the distance between them) – BlueRaja - Danny Pflughoeft Jan 17 '10 at 04:54
  • Thanks! That post didn't come up in searches (i may have used different terms). That definitely sounds similar to my problem, and there are several paths to explore there-in. In regards to your comments in that post, can you expand on what you say there so i can better grasp the full concept? (Specifically, how does that work out to 9 equations/unknowns to solve, just based on the equation you present) –  Jan 17 '10 at 05:17
  • @gw: Ian Boyd has edited his response (in the post I linked to); I believe it is correct and very well written, I refer you to his answer now. – BlueRaja - Danny Pflughoeft Jan 20 '10 at 19:27
  • Wow - thorough. Thanks for pointing that out. I've been in client meetings the past week so I've not had time to look at everything. –  Jan 25 '10 at 17:48
0

This can be solved (aside from the built-in quadruple ambiguities) either mathematically or computationally. Since this is SO, I'll describe a computational approach.

In overview, the approach is to look at the projected angles, and since you know the true angles you can calculate the orientation. To get specific, start with the following visualization: imagine the triangle flat in the x-y plane and it's normal along the z-axis, and put a sphere here that touches all corners of the triangle, with everything centered at the origin. Now rotate the normal to all points of the sphere and note the projected angles. The key point here is that now for each possible projected angle you can draw an iso-angle path on the sphere (i.e. the path of the normal that indicates all the positions for which you observe the same projected angle -- which is probably a circle, but I'm not certain without working out the math). So to solve the original problem, take two of the observed angles, draw the iso-angle paths, and the possible solutions will be the intersection of these paths.

Computationally, construct your iso-angle paths by moving the normal in, say, 1 degree increments over the sphere, and note the three angles for each position, and then rearrange this data into iso-angle paths, by sorting it by angle. Then for two of the angles in an observed projection, find where the two iso-angle paths intersect. Note that the paths will have two intersections which corresponds to the built-in ambiguity of whether a particular corner is near or far from the observer, and also, depending on how you choose deal with reflections of the normal, the paths my be disconnected (though other than reflections I think the iso-angle paths will not be disconnected).

tom10
  • 67,082
  • 10
  • 127
  • 137
  • Neat! This is how I think, and this I can relate to. This brings up a new, different path (no pun intended) in my head that I'll try out on paper and see how it works. Thanks! Will update in a bit. –  Jan 18 '10 at 22:06