Automatic Collision Polygon Generation
by James Young · in Torque X 2D · 03/25/2008 (7:50 am) · 3 replies
Hi,
I am posting an idea I am going to try in case anyone has tried this previously or knows of any algorithms that may be of use to me. I have had a search around the internet and not found much of use, though I may not be using the correct terminology.
I am going to implement an alogirthm which will find the outline of a sprite and from that data generate the collision polygon(s). My reason for doing this is I intend on having some complex sprites with curved surfaces and I would like to get an accurate collision polygon.
I will find the edges by examining the alpha channel of the sprite and generate a list of transparent pixels that have a non-transparent adjacent neighbour. The degree of transparency will be modifiable. The edges will then be defined by ordering the list of pixels based on finding a pixels two nearest neighbours, I think this could potentially introduce some glitches. I shall then reduce the data by finding the start and end points of edges removing all the pixels in the middle that have the same gradient. Depending upon in-game performance I will probably end up introducing further schemes for compressing the data and thereby reduce the accuracy of the polygon. The final step will be to decompose the whole polygon into a set of convex polygons. The simplest way I can think of doing this is to turn it into a collection of triangles. However, that could result in a large collection of polygons. Does anyone have any tips regarding testing if a polygon is concave and if not how to decompose it to the minimum number time into a serises of concave polygons?
Any advice or hints from prior experience will be greatly appreciated!
Cheers
Jim
I am posting an idea I am going to try in case anyone has tried this previously or knows of any algorithms that may be of use to me. I have had a search around the internet and not found much of use, though I may not be using the correct terminology.
I am going to implement an alogirthm which will find the outline of a sprite and from that data generate the collision polygon(s). My reason for doing this is I intend on having some complex sprites with curved surfaces and I would like to get an accurate collision polygon.
I will find the edges by examining the alpha channel of the sprite and generate a list of transparent pixels that have a non-transparent adjacent neighbour. The degree of transparency will be modifiable. The edges will then be defined by ordering the list of pixels based on finding a pixels two nearest neighbours, I think this could potentially introduce some glitches. I shall then reduce the data by finding the start and end points of edges removing all the pixels in the middle that have the same gradient. Depending upon in-game performance I will probably end up introducing further schemes for compressing the data and thereby reduce the accuracy of the polygon. The final step will be to decompose the whole polygon into a set of convex polygons. The simplest way I can think of doing this is to turn it into a collection of triangles. However, that could result in a large collection of polygons. Does anyone have any tips regarding testing if a polygon is concave and if not how to decompose it to the minimum number time into a serises of concave polygons?
Any advice or hints from prior experience will be greatly appreciated!
Cheers
Jim
About the author
#2
I'd had a think about sprites with holes in them and decided that I wasn't going to worry about them for the first release because 1. my current game won't be effected by it and 2. it will add a further degree of complexity to the problem.
I'm confident about processing the sprite and compressing it into a manageable data set, I think my main challenges are going to be decomposing the polygon efficiently and integrating it with TXB. If it does work however, it will be save a lot of work for my future developments!
Cheers
Jim
03/26/2008 (7:09 am)
Hi John,I'd had a think about sprites with holes in them and decided that I wasn't going to worry about them for the first release because 1. my current game won't be effected by it and 2. it will add a further degree of complexity to the problem.
I'm confident about processing the sprite and compressing it into a manageable data set, I think my main challenges are going to be decomposing the polygon efficiently and integrating it with TXB. If it does work however, it will be save a lot of work for my future developments!
Cheers
Jim
#3
John K.
03/26/2008 (9:23 pm)
Jim, I think this is a great idea. I really can't wait to see it in action. John K.
Associate John Kanalakis
EnvyGames
John K.