Original Post
I have a bit of a problem. I've been working on some kind random generated worlds. The part of generating is based on 2D CSG. The problem is that 2 of the methods from that part came up high in profiler results. One is union and the second is kind of "expand/contract". I don't know the english word for it - it pushes vertices in/out of shape. My hacked together implementation only handels convex shapes for this and I would really love to expand it to work with non-convex. So I was hoping someone here may have more experience in this to give me a push in right direction how to speed them up. Since my data is a bit of specific nature it might be possible to come up with optimized algoritems. In general: - Shapes are defined by a list of vertices in clockwise order. Shape is a simple loop over all vertices (no holes and wierd things like that). For union: - Union always happens (no need to check if 2 shapes even intersect) - Second shape is always convex - First shape has usualy more vertices than other one. (first one has 5-20, second 4-10) For "expand/contract": - max number of vertices is about 25 ps: I'm nost sure in what forum to post this? This one, math or graphic. If mod thinks it should be moved then please do. [Edited by - _DarkWIng_ on June 28, 2004 2:05:47 PM]