I am trying to do some OBB algorithm by processing Convex Hull edges in 3D. But i am struggling with calculation of 2 orthogonal planes flush with any 2 edges.
To the point. Let's assume for a moment that edges are vectors. Consider following:
Given two vectors: (1,0,1) and (0,1,1), their dot product clearly is not 0. Therefore they are not perpendicular.
But when we take a different look, from above, their projections on plane with normal (0,1,0) are perpendicular. Therefore there exist 2 planes that are orthogonal and flush with those 2 vectors (In that case, planes with normal (1,0,0) and (0,0,1)).
Example 1: Orthogonal when projected
This is trivial case and would require to project edges onto axialy aligned plane, but that would result only in checking such cases.
We would have to go deeper. Consider following:
Given two vectors: (1,0,1) and (1,1,1), both dot products with and without projection on axially aligned planes are not perpendicular.
But when we take a look from a different angle, there exist 2 planes that are orthogonal and flush with them (seen from above and some angle):
Example 2: Orthogonal when projected
Calculated planes normals would have to be projections of those edges on some unknown plane and that's where i failed. Of course for now i neglected the fact there that planes consist not only of normal vector but also the offset. This seems like it should be possible but i couldn't come up with anything.
The question: Is it possible to calculate such two orthogonal planes from those two vectors? Maybe it would be possible with more data? Or maybe i actually lack some basic knowledge on vectors, planes and perpendicularity?
Thanks in advance for any help.
Two planes in $\mathbb R^3$ are orthogonal iff their normals are. The normals of the planes that contain (i.e., are flush with) an edge are orthogonal to that edge’s direction vector. Your problem therefore reduces to finding a pair of vectors that are respectively orthogonal to a pair of given vectors—the edge direction vectors—and to each other.
Since you’re working in $\mathbb R^3$ there’s an easy way to generate such a pair using cross products. Let $\mathbf v_1$ and $\mathbf v_2$ be the two edge direction vectors. Set $\mathbf n_1=\mathbf v_1\times\mathbf v_2$ and $\mathbf n_2=\mathbf n_1\times\mathbf v_2$. By the properties of the cross product, $\mathbf n_1$ is orthogonal to $\mathbf v_1$, $\mathbf n_2$ is orthogonal to $\mathbf v_2$, and $\mathbf n_1$ is orthogonal to $\mathbf n_2$, as required: $\mathbf n_1$ and $\mathbf n_2$ are the normals of an orthogonal pair edge-flush planes. By symmetry, you could of course take $\mathbf n_2=\mathbf v_1\times\mathbf v_2$ and $\mathbf n_1=\mathbf n_2\times\mathbf v_1$ instead.
Applying this to your examples produces $\mathbf n_1=(-1,-1,1)$, $\mathbf n_2 = (-2,1,-1)$ for the first, and $\mathbf n_1=(-1,0,1)$, $\mathbf n_2=(-1,2,-1)$ for the second.
There are other ways to find these orthogonal normal pairs, but they don’t necessarily lend themselves to as direct a computation as the preceding. For instance, given a non-zero vector $\mathbf v = (a,b,c)$, at least two of the elements $(0,c,-b)$, $(-c,0,a)$ and $(b,-a,0)$ of its orthogonal complement are also non-zero. Choose two that are linearly independent (this is always possible) and call them $\mathbf v_1^\perp$ and $\mathbf v_2^\perp$. Every vector orthogonal to $\mathbf v$ is then a linear combination $\alpha_1\mathbf v_1^\perp+\alpha_2\mathbf v_2^\perp$ of them. Given two edge vectors $\mathbf v$ and $\mathbf w$, then, the problem of finding orthogonal planes that contain them is equivalent to solving the equation $$(\alpha_1\mathbf v_1^\perp+\alpha_2\mathbf v_2^\perp)\cdot(\beta_1\mathbf w_1^\perp+\beta_2\mathbf w_2^\perp)=0$$ for the unknown coefficients $\alpha_1$, $\alpha_2$, $\beta_1$ and $\beta_2$. To reduce the number of solutions, many of which are redundant because they’re scalar multiples of other solutions, you can add additional constraints such as requiring the the vectors have unit length, but there will generally still be an infinite number of solutions even with these additional constraints, so you’ll need some other criteria for selecting ones that are convenient for your application.
Using your first example, a basis of the orthogonal complement of $(1,0,1)$ is $\{(0,1,0),(-1,0,1)\}$. The affine combination $(1-\lambda)(0,1,0)+\lambda(-1,0,1)=(-\lambda,1-\lambda,\lambda)$ is a one-parameter family of vectors orthogonal to $(1,0,1)$, all of which are pairwise linearly-independent, so represent unique planes that contain the edge. This doesn’t describe all of the edge-flush planes since no multiple of $(0,1,0)-(-1,0,1)=(1,1,-1)$ can be represented by this affine combination, but fortunately there are plenty of solutions even without this one plane. (Note, too, that this is the normal of the plane generated by the first method above, so you already know how to find an orthogonal plane to it.) Similar considerations result in the family $(-\mu,1-\mu,\mu-1)$ of vectors orthogonal to $(0,1,1)$. Solving the equation $$(-\lambda,1-\lambda,\lambda)\cdot(-\mu,1-\mu,\mu-1) = (1-\lambda)(1-\mu)+\lambda(\mu-1)+\lambda\mu = 0$$ for $\mu$ gives $\mu={2\lambda-1\over3\lambda-1}$, $\lambda\ne\frac13$, which means that for almost any plane that is flush with $(1,0,1)$ there is a plane flush with $(0,1,1)$ orthogonal to it.