Tell me if you find any bug in the code.
Code: Select all
/*
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;
}
}
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: Select all
// 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;
}