CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
Lyes BEN
Lyes BEN

Reputation: 1010

Algorithm to check if a polygon is a projection of a polyhedron

I am trying to develop an algorithm that performs the following :

Given a 2D polygon and a 3D polyhedron, determine if the 2D polygon is a projection of the 3D polyhedron (a perspective projection to be precise) without knowing which transformation matrix we may have possibly used for the projection.

input

output

I am not asking for code, but I would simply like to know if this is feasible in polynomial time.

Any help will be greatly appreciated.

Upvotes: 1

Views: 190

Answers (3)

user1196549
user1196549

Reputation:

A 3D to 2D perspective projection has 7 degrees of freedom (6 for the relative motion of the scene with respect to the camera, 1 for the focal length).

Select four vertices in the 2D projection and consider all possible correspondences with polyhedron vertices (there is a polynomial number of such associations). Then form a system of 7 equations in the 7 unknown parameters (unfortunately a nonlinear one; maybe the eighth equation can be useful to select among multiple solutions).

Knowing the parameters, you can check a solution by re-projecting the polyhedron and comparing to the polygon (with further search for correspondences with vertices and edges).

All of this will take polynomial time (quartic if I am right), if one admits that the solver takes bounded time (hence bounded precision).

If the focal length is known, then a better approach is possible. Indeed, with only 6 unknowns, you can find the projection parameters from the projection of just three points. This problem is known to have an analytical solution (actually up to 4 of them), as described at length in "New Algorithms for the Perspective-Three-Point Problem, GAO Xiaoshan & CHEN Hangfei, Vol.16 No.3 J. Comput. Sci. & Technol."

This should lead to an O(N³) exact procedure.

More generally speaking, you form putative correspondences between N pairs of points, solve the corresponding Perspective-N-point problem, and check the hypothesis by reprojecting the polyhedron and comparing to the known projection to validate the hypothesis.

Upvotes: 4

mohsenmadi
mohsenmadi

Reputation: 2377

I think it is possible but you have to do a fair amount of reverse engineering. A 2D sketch that represents a 3D object is known as an Orthographic Projection. The link shows you the transformation matrices you need apply to transform the 3D point onto its 2D projection. Now, how do you go the opposite way? Inverse matrices with a mix of some inverse transformations (translation, scaling, rotation...)? I think this is a good lead to follow.

Upvotes: -1

Stefan Haustein
Stefan Haustein

Reputation: 18813

Just an idea for an algorithm:

Take a triangle of the projection made of three points next to each other not on the same line. Iterate through all corresponding triangles of the original. For all possible projections that solve the pair of triangles, check if the rest matches.

I must admit I am not sure right now if there could be infinite solutions for triangles (which would be hard to iterate)? If so, start with four points.

Upvotes: 1

Related Questions