I want to make a script/algorithm that reduces the amount of blocks in a 2D player-generated pattern which has many intersecting parts, similar to what greedy meshing achieves but with a non-voxel grid.
Sample problem
A potential solution
I’ve thought about potential ways to address this problem for a long time now, and sought out solutions to it online, but I can’t find anything about it. Some solutions I’ve considered are:
Solution: Using raycasting from left-right similar to how greedy meshing works Problem: Applying greedy meshing algorithm here wouldn’t reduce part counts in an intersecting, non-grid pattern, and could even make it worse or change the appearance.
Solution: Raycasting normal to the surface and greedy meshing the grid results (4 successful raycasts in a square shape making a result) Problem: Leaves out concave detail that is less than the raycasted square in size
(Red dots representing the raycasts, the dark red region being the greedy-meshable area, and the green areas being the left-out detail)
Ok, so loses a lot of detail, but definitely an improvement
Solution: Same as previous, but mask the edges (outline) Problem: No way to get the edge parts that I can think of, without excessively raycasting every part to see if it has no neighbors (Performance)
Basically, I’m looking for either any ideas on how to approach this problem, any similar solutions, or a way to find the edge parts of a 2D group of parts that isn’t excessively performance intensive.
What assumptions can you make? That has a big impact on what you can do here. For example:
Is this in 2D only?
Are the individual parts always the same shape and size?
Are the parts axis-aligned? Are they rectangles?
Are these parts actually made of several parts?
Are the individual parts convex?
What do you want the output to be? Do you want to limit the algorithm to outputting 45 degree right triangles + rectangles, or could it also output, for example, arbitrary triangles?
Also, you might want to double-check that you need to do this. It’s definitely an interesting problem, but if you’re trying to actually solve lag… I’m not sure it actually helps. Your potential solution image has more parts than the original problem, from what I can tell!
Thanks for the sources, but I think you misread the subject. As you can see in this image in the post, I’m not working with polygons, but a large volume of intersecting parts:
So reducing the amount of parts would greatly impact lag and memory usage, as the game I want to make with this would have a huge number of these instances (Estimated at around 4 million!) without this part reduction method. I’ve tested even a fraction of that and it eventually creates unbearable lag even on my decent gaming PC way before that, and on my phone at a fraction of that. The memory usage from just a few hundred thousand is huge too.
If there was a way to polygon-ify this without excessive raycasting, that would completely solve my problem and probably be even better than the greedy meshing that I was talking about before. If you know of any ways or any sources that hint to how to polygon-ify intersecting parts like this, that would be very much appreciated.
To answer your questions from earlier,
Is this in 2D only?
Yes. It can be assumed all the parts are lying on a 2D plane, and are all aligned in that axis.
Are the individual parts always the same shape and size?
They are the same size, however, the wedge triangles are of a different shape.
Are the parts axis-aligned? Are they rectangles?
Yes, they are all on the same local axis (but not global, as they are on an off-angle plane). They are all square rectangles in dimensions.
Are these parts actually made of several parts?
No. Each part is independent and exists alone, as seen in the image shown above.
Are the individual parts convex?
They’re squares. The overall shape can’t be assumed to be convex, as seen in the sample image
What do you want the output to be? Do you want to limit the algorithm to outputting 45 degree right triangles + rectangles, or could it also output, for example, arbitrary triangles?
As long as the output keeps the same look as before and reduces the amount of parts as much as possible, that would be perfect.
Sure—I was just generalizing the problem, because you could represent the outline of each of these parts as an octagon, compute the union operation on those polygons, and then re-triangulate the resulting polygon.
So you’re really looking at two problems here
Use a union operation to combine octagons into several larger polygons
“Triangulate” the resulting larger polygons using rectangles and right triangles
(1) is hard generally, but might be made easier because you can assume some good things like convex shapes, axis-aligned, etc.
If you were just dealing with axis-aligned rectangles, the problem is much easier. Your wedges make it a lot harder and I don’t have an answer for an existing algorithm with these constraints . Maybe that link will help you come up with a novel one though!
(2) is also hard. You can get some wacky shapes even from these simple building blocks, and I think something like Ear clipping would be easier to implement.
Once again, I would just make sure that you really need this, because I think it’s a ton of work to get right!
Not saying you shouldn’t, it’s super interesting. But if it’s just to reduce lag, I’m not sure it even will, and might even make it worse!
Unioning with scripts is definitely possible if a bit unreliable from experience. However, I would need to get the polygon data to triangulate it, which is the root of this whole problem. Considered axis-aligned rectangles but would take away a lot from the aesthetic. I’d love to implement ear clipping and that seems to be the right direction, but that just brings us back to the original problem of converting a group of parts into a polygon. Maybe using raycasting to find the edge blocks of a shape, and then using the shape’s type and size to find the edge length could be one way? Would require tons of rays though and there’s probably a better, simpler solution.
Do you know of any possible methods that could yield a polygon (or at least the data of one) out of the parts in this situation? That would completely solve the problem and I could use the ear clipping method you suggested then.
Well, first you want to make polygon representations out of the individual parts. That’s pretty easy, just hard code some points.
Then you want to perform a polygon union operation on that set of octagons.
I’ve never implemented it myself. It’s a bit of a difficult problem.
Like I linked in my first response, there’s the Clipper library in C# that does it, for inspiration. Apparently it uses the Varri clipping algorithm, whatever that is. The term you want to google is “polygon boolean operations” or something like that.
Again, you might be able to find an easier algorithm based on your assumptions, since Clipper is used for arbitrary polygons.
There’s also the library by AlexarJING I linked that was written in pure lua, for love2d. It might work if you ported it to Roblox, I haven’t tested it!
I had some time to think about it and I realized you answered my original question:
Polygon clipping seems to be the appropriate solution here. I’ll consider this problem solved and mark the solution. Turning the parts into a polygon is another problem, and I’ll try to tackle that on my own, and I have a fallback solution (raycasting), so I’ll just open another thread if I really need help. Thanks so much for pointing me to these sources
Hey, I recently had a problem similar to this one!
You could use a module by EgoMoose called PolyBool:
You could also go the other route and use another algorithm similar to the one in PolyBool to create a Doubly Connected Edge List and solve the map overlay of subdivisions problem (see chapter 2)
Something I should say is that computing map overlays requires computing segment intersections, which in the first place is difficult to do in a very fast time. Doing this by force, you end up with an O(n^2) time complexity (soooo bad).
Next best case is to use the Bentley-Ottmann algorithm with O(nlogn + k) time complexity. However, doing this leaves you with a lot of floating point imprecision errors (see numerical precision issues)
There are times when you might want to calculate the overlay with your algorithm, but due to imprecisions, still won’t be able to find an overlay to base your Polygon boolean logic off of. This makes reliably and robustly solving this problem very difficult.
There’s also another algorithm involving alpha-shapes, which is like making a concave hull but with an alpha value that represents the concavity of the shape. This one is harder to implement in my opinion, but it shouldn’t have those floating point value errors that segment intersections do
. Maybe that link will help you come up with a novel one though!