Axis-AlignedBounding BoxCreation: Axis-Aligned bounding box(AABBaxis-aligned- the box is parallel to the x,y,z axisboundingboxof the world coordinate system Creation- For each axis direction (x,y,z), calculate x min, x max,(y_min,y_max;z_min,z_max) of the object- The box (x _min,x_max,y_min,y_max,z_min, z_max) isthe resulting axis-aligned bounding box
Axis-Aligned Bounding Box Creation • Axis-Aligned bounding box(AABB) – the box is parallel to the x,y,z axis of the world coordinate system • Creation – For each axis direction (x,y,z), calculate x_min, x_max, (y_min,y_max;z_min,z_max) of the object – The box (x_min,x_max,y_min,y_max,z_min, z_max) is the resulting axis-aligned bounding box
Non-Axis-Aligned Bounding Box: Non-Axis-Aligned bounding box- Also called oriented bounding box (OBB)- anOBB is more optimal than an AABBOBB ‘“matches" more than AABBnon-alignedboundingbox an optimal OBB is an approximation of the minimalbounding box, usually obtained by a complexoptimization process.HowtoconstructanOBB?
Non-Axis-Aligned Bounding Box • Non-Axis-Aligned bounding box – Also called oriented bounding box (OBB) – an OBB is more optimal than an AABB. OBB “matches” more than AABB. – an optimal OBB is an approximation of the minimal bounding box, usually obtained by a complex optimization process. • How to construct an OBB ?
Bounding Spherebounding: bounding spheresphere- A bounding sphere only has twoparameters: radius and center. When objectrotates, bounding sphere does not need to rotate.- However, the ideal minimal-radius bounding sphere ishard to calculate.- Here, we introduce a method for finding a near optimalbounding sphere for a set of n points in 3D space. It israther fast, O(n) time complexity. The generated sphereis about 5% larger than the ideal bounding sphere
Bounding Sphere • bounding sphere – A bounding sphere only has two parameters: radius and center. When object rotates, bounding sphere does not need to rotate. – However, the ideal minimal-radius bounding sphere is hard to calculate. – Here, we introduce a method for finding a near optimal bounding sphere for a set of n points in 3D space. It is rather fast, O(n) time complexity. The generated sphere is about 5% larger than the ideal bounding sphere
boundingsphereBounding Sphere: This algorithm is executed by 2 steps:- First step: Make one (quick) pass through the N pointsFind these six points:: The point with minimum x, the point with maximum x,The point with minimum y, the point with maximum y,The point with minimum z, the point with maximum z.This gives three pairs of points. Each pair has themaximum span for its dimension. Pick the pair with themaximum point-to-point separation. Calculate the initialsphere, using this pair of points as a diameter
Bounding Sphere • This algorithm is executed by 2 steps: – First step: Make one (quick) pass through the N points. Find these six points: • The point with minimum x, the point with maximum x, The point with minimum y, the point with maximum y, The point with minimum z, the point with maximum z. This gives three pairs of points. Each pair has the maximum span for its dimension. Pick the pair with the maximum point-to-point separation. Calculate the initial sphere, using this pair of points as a diameter
Bounding Sphere- Make a second pass through the N points: for eachpoint outside the current sphere, update the currentsphere to the larger sphere passing through the point onone side, and the back side of the old sphere on the otherside. Each new sphere will (barely) contain the oldsphere, and the new point. As shown in the figure, oldsphere (the red sphere)is enlarged to the new sphere (Thegreen sphere).P
Bounding Sphere – Make a second pass through the N points: for each point outside the current sphere, update the current sphere to the larger sphere passing through the point on one side, and the back side of the old sphere on the other side. Each new sphere will (barely) contain the old sphere, and the new point. As shown in the figure, old sphere (the red sphere) is enlarged to the new sphere (The green sphere). C P