Given a set of points, computes the minimum bounding sphere of those points
| 865 | |
| 866 | // Given a set of points, computes the minimum bounding sphere of those points |
| 867 | float vm_ComputeBoundingSphere(vector *center, vector *vecs, int num_verts) { |
| 868 | // This algorithm is from Graphics Gems I. There's a better algorithm in Graphics Gems III that |
| 869 | // we should probably implement sometime. |
| 870 | |
| 871 | vector *min_x, *max_x, *min_y, *max_y, *min_z, *max_z, *vp; |
| 872 | float dx, dy, dz; |
| 873 | float rad, rad2; |
| 874 | int i; |
| 875 | |
| 876 | // Initialize min, max vars |
| 877 | min_x = max_x = min_y = max_y = min_z = max_z = &vecs[0]; |
| 878 | |
| 879 | // First, find the points with the min & max x,y, & z coordinates |
| 880 | for (i = 0, vp = vecs; i < num_verts; i++, vp++) { |
| 881 | |
| 882 | if (vp->x < min_x->x) |
| 883 | min_x = vp; |
| 884 | |
| 885 | if (vp->x > max_x->x) |
| 886 | max_x = vp; |
| 887 | |
| 888 | if (vp->y < min_y->y) |
| 889 | min_y = vp; |
| 890 | |
| 891 | if (vp->y > max_y->y) |
| 892 | max_y = vp; |
| 893 | |
| 894 | if (vp->z < min_z->z) |
| 895 | min_z = vp; |
| 896 | |
| 897 | if (vp->z > max_z->z) |
| 898 | max_z = vp; |
| 899 | } |
| 900 | |
| 901 | // Calculate initial sphere |
| 902 | |
| 903 | dx = vm_VectorDistance(min_x, max_x); |
| 904 | dy = vm_VectorDistance(min_y, max_y); |
| 905 | dz = vm_VectorDistance(min_z, max_z); |
| 906 | |
| 907 | if (dx > dy) |
| 908 | if (dx > dz) { |
| 909 | *center = (*min_x + *max_x) / 2; |
| 910 | rad = dx / 2; |
| 911 | } else { |
| 912 | *center = (*min_z + *max_z) / 2; |
| 913 | rad = dz / 2; |
| 914 | } |
| 915 | else if (dy > dz) { |
| 916 | *center = (*min_y + *max_y) / 2; |
| 917 | rad = dy / 2; |
| 918 | } else { |
| 919 | *center = (*min_z + *max_z) / 2; |
| 920 | rad = dz / 2; |
| 921 | } |
| 922 | |
| 923 | // Go through all points and look for ones that don't fit |
| 924 | rad2 = rad * rad; |
nothing calls this directly
no test coverage detected