Since the convex hull optimizer that I tried caused my low detailed convex hulls to become more complex than before, I made a new convex hull optimizer that will remove every point inside the convex hull without adding any new points given that the input does not have any close pair of points. To reduce the number of points for complex models, a Quality argument affect how many planes that will search for the outmost points along it's normal.
Tell me if you find any bug in the code.
Code:
/*
Copyright (c) 2012 David Forsgren Piuva
The code does not have formal verification and is provided 'as-is'.
Use at your own risk with any non binding open source license that the Bullet physics engine use.
*/
// Some loop macros
#define LoopForward(min,var,max) for(var=min;var<=max;var++)
#define LoopBackward(min,var,max) for(var=max;var>=min;var--)
#define LoopForwardStartAndLength(var,start,length) LoopForward(start,var,((start)+(length))-1)
#define LoopBackwardStartAndLength(var,start,length) LoopBackward(start,var,((start)+(length))-1)
#define LoopForwardLengthFromZero(var,length) LoopForward(0,var,(length)-1)
#define LoopBackwardLengthFromZero(var,length) LoopBackward(0,var,(length)-1)
// A lower quality gives fewer points but a higher quality will be a better approximation. At least 4 and at most 12 is recomended for Quality.
// Treshold tells how far out a point must be from the others to remain and should only be large enough to handle rounding errors.
// Otherwise, a sphere of points would vanish from not having any edge that is sharp enough.
// 0.0001 should be enough as the Treshold unless your model is very small.
// No redundant point will remain inside the convex hull but some points may be removed to decrease detail level.
// Preconditions:
// Treshold > 0
// Quality > 0
// No points on the convex hull are at almost the same location because this is faster to remove when loading vertices from a triangle model.
// When generating the convex hull to use as input to this function, you can skip every point that is within a welding treshold from a previously added point.
// PostCondition: Returns an optimized convex shape with less or equal anount of points. If ConvexShape has less than 4 points or an allocation failed then NULL is returned so that you may keep your old shape.
// Worst case complexity: O(N*Q²) where N is the number of points in ConvexShape and Q is Quality. I am not sure about how fast the convex hull shape will reallocate it's buffer in the end.
btConvexHullShape* OptimizeConvexShape(btConvexHullShape* ConvexShape, int Quality, btScalar Treshold) {
int Side;
int U;
int V;
int Point;
int Smallest;
int SecondSmallest;
int SecondLargest;
int Largest;
btScalar SmallestValue;
btScalar SecondSmallestValue;
btScalar SecondLargestValue;
btScalar LargestValue;
btVector3 PointPos;
bool* SelectedPoints;
// Get the number of points
int NumberOfPoints = ConvexShape->getNumPoints();
// Reject trivial cases that can't even make a volume
if (NumberOfPoints < 4) {
// Invalid convex hull
// This shaped should not be used
return NULL;
} else {
// Allocate the array that will store our selection
SelectedPoints = new bool[NumberOfPoints];
// Abort if we have no memory
if (!SelectedPoints) {
return NULL;
}
// Initialize values
LoopForwardLengthFromZero(Point,NumberOfPoints) {
SelectedPoints[Point] = false;
}
// Test against each plane
LoopForwardLengthFromZero(Side,3) {
LoopForwardLengthFromZero(U,Quality) {
LoopForwardLengthFromZero(V,Quality) {
// Generate a normal by subdividing 3 sides of a cube
// Since we use both sides, negative sides are not needed
btVector3 Normal;
switch (Side) {
case 0:
Normal = btVector3(
btScalar(1.0),
((((btScalar)U + btScalar(0.5)) / Quality) * btScalar(2)) - btScalar(1),
((((btScalar)V + btScalar(0.5)) / Quality) * btScalar(2)) - btScalar(1));
break;
case 1:
Normal = btVector3(
((((btScalar)U + btScalar(0.5)) / Quality) * btScalar(2)) - btScalar(1),
btScalar(1.0),
((((btScalar)V + btScalar(0.5)) / Quality) * btScalar(2)) - btScalar(1));
break;
default:
Normal = btVector3(
((((btScalar)U + btScalar(0.5)) / Quality) * btScalar(2)) - btScalar(1),
((((btScalar)V + btScalar(0.5)) / Quality) * btScalar(2)) - btScalar(1),
btScalar(1.0));
}
// Normalize our direction for deterministic use of treshold
Normal = Normal.normalize();
// Reset minimum and maximum
Smallest = -1;
SecondSmallest = -1;
SecondLargest = -1;
Largest = -1;
SmallestValue = btScalar(0.0);
SecondSmallestValue = btScalar(0.0);
SecondLargestValue = btScalar(0.0);
LargestValue = btScalar(0.0);
// Find the minimum and maximum dot products
LoopForwardLengthFromZero(Point,NumberOfPoints) {
// Get the position of the point
PointPos = ConvexShape->getUnscaledPoints()[Point];
// Take the dot product with the normal to see if any points are outside of every other point
btScalar NewValue = PointPos.dot(Normal);
// Remember the largest dot products
if (Smallest == -1 || NewValue < SmallestValue) {
// The previous smallest is the new second smallest
SecondSmallest = Smallest;
SecondSmallestValue = SmallestValue;
// Store the new smallest
Smallest = Point;
SmallestValue = NewValue;
} else if (SecondSmallest == -1 || NewValue < SecondSmallestValue) {
// Store the new second smallest
SecondSmallest = Point;
SecondSmallestValue = NewValue;
}
// Remember the smallest dot products
if (Largest == -1 || NewValue > LargestValue) {
// The previous largest is the new second largest
SecondLargest = Largest;
SecondLargestValue = LargestValue;
// Store the new largest
Largest = Point;
LargestValue = NewValue;
} else if (SecondLargest == -1 || NewValue > SecondLargestValue) {
// Store the new second largest
SecondLargest = Point;
SecondLargestValue = NewValue;
}
}
// Any outstanding endpoints along the normal will be selected to keep in the new shape
if (LargestValue > SecondLargestValue + Treshold) {
SelectedPoints[Largest] = true;
}
if (SmallestValue < SecondSmallestValue - Treshold) {
SelectedPoints[Smallest] = true;
}
}
}
}
// Count how many points we made
int NewNumberOfPoints = 0;
LoopForwardLengthFromZero(Point,NumberOfPoints) {
if (SelectedPoints[Point]) {
NewNumberOfPoints++;
}
}
// Abort if we removed too much from the shape
if (NewNumberOfPoints < 4) {
delete[](SelectedPoints);
return NULL;
}
// Create an empty convex hull to fill with points
btConvexHullShape* NewConvexShape = new btConvexHullShape();
// Abort if we have no memory
if (!NewConvexShape) {
delete[](SelectedPoints);
return NULL;
}
// Add all selected points from the old convex hull
// This would be faster if btConvexHullShape could preallocate memory of the final size before getting the points
LoopForwardLengthFromZero(Point,NumberOfPoints) {
if (SelectedPoints[Point]) {
NewConvexShape->addPoint(ConvexShape->getUnscaledPoints()[Point]);
}
}
// Remove our selection array
delete[](SelectedPoints);
// Return a new shape with the selected points
return NewConvexShape;
}
}
This is how I called it from my graphics engine to give it points with a minimum distance from each other.
It will not run without the rest of my engine but can use used as pseudo code for how to use it.
This code assume that btScalar is a float.
Code:
// If 2 vertices are within the treshold from each other, the last one will be removed.
// If UseVertexSelection is selected then only vertices with more than 0.5 as selection value will be used to make the convex hull.
int CDFPGECtrl::CollisionShape_Create_ConvexHull_FromModel(int Model,int DetailLevel,float WeldingTreshold,int Quality,bool UseVertexSelection) {
int Result;
Result = 0;
GET_FROM_REF(Model,Model);
if BAD_REF(Model) {
REPORT_TYPE(Model,CollisionShape_Create_ConvexHull_FromModel,Model)
} else if (DetailLevel < 0 || DetailLevel > 2) {
MQ->InsertMessage(L"CollisionShape_Create_ConvexHull_FromModel: DetailLevel is not a valid detail level. Use 0 to 2 for low to high detail level.");
} else {
// Make the struct in the graphics engine
CollisionShape_Struct* NewShape = DGE.CollisionShape_Create_ConvexHull(NULL);
// Get it's convex hull shape and cast it since we know what it is
btConvexHullShape* ConvexShape = (btConvexHullShape*)(NewShape->CollisionShape);
// Fill convex hull with every vertice in the model that is not already added
int Part;
int Tri;
int Vert;
int Point;
int MinDetail;
int MaxDetail;
bool OverlapExisting;
LoopForwardLengthFromZero(Part,pModel->Model.GetNumberOfParts()) {
MinDetail = pModel->Model.GetPartMinDetailLevel(Part);
MaxDetail = pModel->Model.GetPartMaxDetailLevel(Part);
if (DetailLevel >= MinDetail && DetailLevel <= MaxDetail) {
LoopForwardLengthFromZero(Tri,pModel->Model.GetTriangleCountFromPart(Part)) {
LoopForwardLengthFromZero(Vert,3) {
// Either take everything by not using vertex selection or only take selected vertices
if (!UseVertexSelection || pModel->Model.Vertice_GetSelected(Part,Tri,Vert) > 0.5f) {
D3DXVECTOR3 VertPos;
btVector3 PointPos;
VertPos = pModel->Model.Vertice_GetPos(Part,Tri,Vert);
//See if it is too close to any previous point
OverlapExisting = false;
LoopForwardLengthFromZero(Point,ConvexShape->getNumPoints()) {
PointPos = ConvexShape->getUnscaledPoints()[Point];
if (DistVec3((D3DXVECTOR3)PointPos,VertPos) < WeldingTreshold) {
OverlapExisting = true;
}
}
// If not then include it to the convex hull
if (!OverlapExisting) {
ConvexShape->addPoint(btVector3(VertPos.x,VertPos.y,VertPos.z));
}
}
}
}
}
}
// Optimize
btConvexHullShape* OptimizedConvexShape = OptimizeConvexShape(ConvexShape,Quality,0.00001f);
if (OptimizedConvexShape) {
// Use the new shape and delete the old shape
NewShape->CollisionShape = OptimizedConvexShape;
SAFE_DELETE(ConvexShape)
} else {
// Keep the old shape because it could not be optimized
NewShape->CollisionShape = ConvexShape;
}
// Return the shape's ID
Result = DGE.IDFromPointer(NewShape);
}
return Result;
}
Login
Register
FAQ
Search
