EDIT: The library can be found on github. If you would like to test the library, I built a simple raytracer here.
Hello everyone. I'm a PhD student working on computational soft matter. One of my group's interests is the equilibrium properties of hard particle systems (e.g. particles without any interactions), and as such, we frequently use collision detection algorithms in simulations.
I have written such code myself, and would like to write a library with a nice API which is easy to use, perhaps even make it a single file library. I always find it difficult designing a good API, and I seek your advice for this matter. In this gist, I have written two simple examples of what the API could look like for the GJK algorithm. In the first case, the user has to explicitly cast his shapes to convex_t, while in the latter case, there is one more level of indirection, i.e. a shape_t. The advantage of the second case, is that the user doesn't have to explicitly cast the shape, he can store all shapes in a single array, and since the type is stored using an enum, we can specialise algorithms for different types (e.g. for spheres GJK is overkill). On the other hand, in the second case the user cannot directly view the content of the struct, and the extra level of indirection, could hurt readability and performance slightly.
Another issue is memory allocation. Most shapes I'm intending to implement, don't need any allocations, but meshes need to store the vertices, faces, and vertex neighbours for faster support functions. I think it would be inconvenient if you have to i.e. call '_destroy()' on all types of shape structs even though only one meshes need to be freed. I know that stb libraries avoid memory allocations by e.g. preallocating enough memory, but I think this can be cumbersome since you can either exceed the memory limit, or allocate too much memory for a very small mesh. There is also this question on stack overflow, which discusses a similar API design issue.
Hello everyone. I'm a PhD student working on computational soft matter. One of my group's interests is the equilibrium properties of hard particle systems (e.g. particles without any interactions), and as such, we frequently use collision detection algorithms in simulations.
I have written such code myself, and would like to write a library with a nice API which is easy to use, perhaps even make it a single file library. I always find it difficult designing a good API, and I seek your advice for this matter. In this gist, I have written two simple examples of what the API could look like for the GJK algorithm. In the first case, the user has to explicitly cast his shapes to convex_t, while in the latter case, there is one more level of indirection, i.e. a shape_t. The advantage of the second case, is that the user doesn't have to explicitly cast the shape, he can store all shapes in a single array, and since the type is stored using an enum, we can specialise algorithms for different types (e.g. for spheres GJK is overkill). On the other hand, in the second case the user cannot directly view the content of the struct, and the extra level of indirection, could hurt readability and performance slightly.
Another issue is memory allocation. Most shapes I'm intending to implement, don't need any allocations, but meshes need to store the vertices, faces, and vertex neighbours for faster support functions. I think it would be inconvenient if you have to i.e. call '_destroy()' on all types of shape structs even though only one meshes need to be freed. I know that stb libraries avoid memory allocations by e.g. preallocating enough memory, but I think this can be cumbersome since you can either exceed the memory limit, or allocate too much memory for a very small mesh. There is also this question on stack overflow, which discusses a similar API design issue.
Edited by Nick
on
One of the things I really dislike about most GJK desciptions is the name of the "support" function. A more descriptive name like "CalculateFurthestPointAlong" would help in understanding what it needs to do.
Besides that why have a convext_t when all it contains is a function pointer? If you need to group the data and function pointer make it also contain a void*
Then the call is "gjk_boolean(convex1, convex2);"
One of the strengths of the GJK algorithm is that you can compose shapes through union and minkowski sum. Having a few utility supports for that would be nice.
Note that there aren't any allocation needed, fi you have a custom mesh just create a custom CalculateFurthestPointAlong function for it and point the void* to the mesh root.
IMO the transform should be a util wrapper, all that it needs to do is inversely rotate the direction vector and pass that along then transform the resulting point.
Also there should be variants for the number of dimensions you are working with, When doing collision detection I would expect it to handle up to 4 dimensions to be able to do swept 3D collisions.
Besides that why have a convext_t when all it contains is a function pointer? If you need to group the data and function pointer make it also contain a void*
1 2 3 4 | typedef struct{
support_t support;
void* data;
}convex_t;
|
Then the call is "gjk_boolean(convex1, convex2);"
One of the strengths of the GJK algorithm is that you can compose shapes through union and minkowski sum. Having a few utility supports for that would be nice.
1 2 3 4 5 6 7 | gjk_box box = build_box(...);
gjk_sphere sphere = build_sphere(...);
convex_t conv[] = {{CalculateFurthestPointAlong_box, &conv_box},
{CalculateFurthestPointAlong_sphere, &conv_sphere}};
gjk_union _union = {&conv[0], arrayCount(conv)};
convex_t conv_union = {CalculateFurthestPointAlong_union, &_union};
|
Note that there aren't any allocation needed, fi you have a custom mesh just create a custom CalculateFurthestPointAlong function for it and point the void* to the mesh root.
IMO the transform should be a util wrapper, all that it needs to do is inversely rotate the direction vector and pass that along then transform the resulting point.
Also there should be variants for the number of dimensions you are working with, When doing collision detection I would expect it to handle up to 4 dimensions to be able to do swept 3D collisions.
I would second ratchetfreak's suggestions, generally speaking expose the simplest components of GJK to the user first, you can always add the helpers you need (like handling memory allocation) later. Plus, once you have a few people using it (I def would, a nicely done gjk lib would be fun to play with) you'll have a better idea of how to reduce work for the average end user. And even if you don't add it yourself, i'd argue that memory management is orders more simple than understanding and implementing GJK, people can just do it themselves.
Thank you for your response ratchetfreak. I think you misunderstand the use case. This is primarily for fellow scientists. I don't want every one of them to have to know how GJK works, i.e. it should be as simple to use as possible. libccd does what you're describing very nicely.
I was initially thinking of perhaps adding a couple of more functions (such as the inscribed sphere radius). I agree that it can be reduced to just the function pointer typedef.
The idea of casting to 'convex_t' in my case, is that it avoids keeping another struct around.
I'm not sure I understand how you would do this to fit the rest of the api you suggested. How would you implement 'build_mesh(...)'?
My experience tells me that generalising mathematical code to different dimensions doesn't work as well as expected; it's best to separate code for different dimensions. In this case, it will be only in 3D. Doing 4D could be nice for swept volumes, but as I have implemented GJK using the geometric method, instead of the algebraic one, I think it would be tough to generalise. Instead, I have implemented the ray casting algorithm by Gino van den Bergen.
ratchetfreak
Besides that why have a convext_t when all it contains is a function pointer?
I was initially thinking of perhaps adding a couple of more functions (such as the inscribed sphere radius). I agree that it can be reduced to just the function pointer typedef.
ratchetfreak
If you need to group the data and function pointer make it also contain a void*
typedef struct{ support_t support; void* data; }convex_t;
Then the call is "gjk_boolean(convex1, convex2);"
The idea of casting to 'convex_t' in my case, is that it avoids keeping another struct around.
ratchetfreak
Note that there aren't any allocation needed, fi you have a custom mesh just create a custom CalculateFurthestPointAlong function for it and point the void* to the mesh root.
I'm not sure I understand how you would do this to fit the rest of the api you suggested. How would you implement 'build_mesh(...)'?
ratchetfreak
Also there should be variants for the number of dimensions you are working with, When doing collision detection I would expect it to handle up to 4 dimensions to be able to do swept 3D collisions.
My experience tells me that generalising mathematical code to different dimensions doesn't work as well as expected; it's best to separate code for different dimensions. In this case, it will be only in 3D. Doing 4D could be nice for swept volumes, but as I have implemented GJK using the geometric method, instead of the algebraic one, I think it would be tough to generalise. Instead, I have implemented the ray casting algorithm by Gino van den Bergen.
Garyuutensei
Thank you for your response ratchetfreak. I think you misunderstand the use case. This is primarily for fellow scientists. I don't want every one of them to have to know how GJK works, i.e. it should be as simple to use as possible. libccd does what you're describing very nicely.
The support name thing it really just a gripe. Otherwise anyone looking at the code needs to understand what gjk actually wants support while another name makes it much clearer.
Garyuutensei
I was initially thinking of perhaps adding a couple of more functions (such as the inscribed sphere radius). I agree that it can be reduced to just the function pointer typedef.
The idea of casting to 'convex_t' in my case, is that it avoids keeping another struct around.
keeping stuff around is only for the duration of the gjk call so it can just linger on the stack of the calling function if need be.
Garyuutensei
I'm not sure I understand how you would do this to fit the rest of the api you suggested. How would you implement 'build_mesh(...)'?
The mesh struct really only needs a list of vertices preferably only the convex hull of it, perhaps with some kind of partioning to speed things up a little bit. So that's what build_mesh should provide.
Sure that probably requires a heap allocation but that's part purely of the mesh structure not of the convex_t. If you don't do any acceleration and just loop over all vertices of the mesh then you can even reuse however you loaded it in.
My point is that the the actual object is separate from the gjk algorithm. All the algorithm needs is what the "support" function requires it's kinda elegant in that way. If the supporting state needs cleanup then that's on the object itself.
Garyuutensei
My experience tells me that generalising mathematical code to different dimensions doesn't work as well as expected; it's best to separate code for different dimensions. In this case, it will be only in 3D. Doing 4D could be nice for swept volumes, but as I have implemented GJK using the geometric method, instead of the algebraic one, I think it would be tough to generalise. Instead, I have implemented the ray casting algorithm by Gino van den Bergen.
That's what I meant with variants. The lower dim version can reuse code from the higher dim version.
Edited by ratchetfreak
on
ratchetfreak
keeping stuff around is only for the duration of the gjk call so it can just linger on the stack of the calling function if need be.
That has some cost involved.
ratchetfreak
Sure that probably requires a heap allocation but that's part purely of the mesh structure not of the convex_t.
So in the end, you do need a 'destroy_mesh()' function (at least in case where you store data to accelerate the support function). In addition, to keep everything symmetric, you need a 'destroy_T()' for every shape type T you define. This is not a problem if the user has to define the shapes himself, but as I mentioned, this is not the direction I want to go. Although it has the most flexibility, it leads to code duplication, and requires a better knowledge of the underlying algorithm.
I have chosen to go with the API shown here. I didn't find a reason to have a 'convex_t' struct like suggested by ratchetfreak, and instead now pass the shape structs as void pointers and let the library functions retrieve the function pointer from the struct. The previous API version didn't really add any type safety by letting the user convert the shape struct to 'convex_t' -- it was pretty pointless.
I'll post a reply with a link to the library when I'm done. At first instance I'll probably only support quaternions for rotation as this is what I have currently implemented, but I'm thinking of also supporting axis-angle and matrix -based rotations.
I have implemented the library which can be found on github. If you would like to test the library, I built a simple raytracer here.
There is no documentation yet, but I hope it is clear enough how to use.
I've often wanted to try and use a collision detection library for my research, but usually they come with their own transformation (body) types, which means you have to keep two sets of transformation data. At the moment the transformation struct, ntcd_transform, is fixed, and the rotation is expected to be a quaternion, but I would like to allow the user to define his own. One possibility is to make the ntcd_transform struct opaque and introduce an additional ntcd_rotation struct, along with ntcd_transform_point(double*, const ntcd_transform*, const double*) , ntcd_rotation_inverse(ntcd_rotation*, const ntcd_rotation*), and ntcd_rotate_point(double*, const ntcd_rotation*, const double*).
I would appreciate some feedback!
There is no documentation yet, but I hope it is clear enough how to use.
I've often wanted to try and use a collision detection library for my research, but usually they come with their own transformation (body) types, which means you have to keep two sets of transformation data. At the moment the transformation struct, ntcd_transform, is fixed, and the rotation is expected to be a quaternion, but I would like to allow the user to define his own. One possibility is to make the ntcd_transform struct opaque and introduce an additional ntcd_rotation struct, along with ntcd_transform_point(double*, const ntcd_transform*, const double*) , ntcd_rotation_inverse(ntcd_rotation*, const ntcd_rotation*), and ntcd_rotate_point(double*, const ntcd_rotation*, const double*).
I would appreciate some feedback!
Edited by Nick
on