I have some 3D planes information. When all planes join together, it will form a 3D convex hull.
Here is an example of input.
Each 3D plane is denoted by a point on the plane and its normal.
All normals point to inside :-
- (-1,0,0) with normal = (1,0,0)
- ( 1,0,0) with normal = (-1,0,0)
- (0,-1,0) with normal = (0,1,0)
- (0,1,0) with normal = (0,-1,0)
- (0,0,-1) with normal = (0,0,1)
- (0,0,1) with normal = (0,0,-1)
- (0.142,-7.18,10.12) with normal = (0.001,0.31,-0.95)
- note: some planars can be redundant (contribute nothing) e.g. the last one
Question: How to calculate AABB from it?
The solution from the above example is ((-1,-1,-1),(1,1,1))
.
(At first, I want center of mass, but I realized that is a Hard problem.
AABB should be good enough for me. )
My poor solution is to find all hull vertices using Constructive solid geometry then do MIN & MAX on them, but the performance is too bad.
In real case, I want to find the center point of 3D hull when two convex hulls are overlapping.
This information can be useful for more accurate Collision Response in Physics Engine.
It"s the classical problem of linear programming. Given a set of linear inequalities (represented by planes in your case, say ax+by+cz+d>=0) and a linear function (say f(x,y,z)=x), find a point that minimises the function while satisfying all the inequalities. The AABB is the solution of 6 such problems, for functions x, -x, y, -y, z and -z.
There are several methods of solving this problem, the most known being the simplex algorithm, and many ready-made libraries (including some that utilise GPUs).