![[es]](/mwf/flags/es.png "Spain")
Because I fiddled around with such basic stuff as lines and the intersection thereof too much, I don't feel like coding this any more for some time. In fact, I think I will rather search for an ISC-compatible geometry library so that I can concentrate on the polygon stuff rather than be stuck with reinventing the wheel. However, now I know something about which operations are expensive and how to optimise them. I want to share this for the case that somebody else wants to continue to work on this topic.This post is just a more or less random collection of facts/experiences:
General stuff on polygons
- There are a few libraries for polygon operations out there, however most are commercial and one or two are GPL
- Polygons are saved as a number of vertices which are all connected by line segments. For better performance of inside/outside checks, it has a enclosing rectangle on which the containment checks are made first. Only if it is inside the rectangle, all lines are checked for intersections.
- Containment check for any polygon: Shoot a ray from the point to check in any direction and see with how many line segments it intersects. If the number is odd, it's inside, otherwise its outside. It's faster if the ray is shot along the X- or Y-axis. The ray may not hit any vertices of the polygon - or one has to count differently. See here http://rw7.de/ralf/inffaq/polygon.html
- Physics engines (that we can use) only support convex polygons. Creating several convex polygons out of a concave one is relatively inexpensive and easy. The check if a point is inside or not is easier: For each line segment determine if the point lies to the left or right of a line. If it always lies on the right side, it's inside.
- An intersection check with a line (e.g. like PathFree) means intersection checks for one rectangle and N line segments thereafter whereas N is the number of vertices of the polygon. It can return the point of intersection plus the normal of the surface without more effort which will save some surface/collision checks.
- Counting the area of one polygon is very fast.
- Collision checks a la PathFree can be relatively fast since not every pixel has to be checked but we look at the intersections with a segmented & directed (see below) line
- Splitting up polygons (along the X- or Y-axis) is cheap.
- Creating and deleting whole polygons is very fast
- Some physics engines support rough simulation of water & waves using polygons.
Polygons & optimisations for Clonk
- My concept in general: The polygons of the landscape may not overlap. There are (at least) two layers of material polygons which are treated differently: foreground polygons (Earth...) and and background polygons (tunnel...). Sky means there are no polygons. Material checks for points first check only foreground polygons, if there is nothing, background polygons. This means that the background can be designed individually, if the foreground is blasted away, the tunnel material doesn't have to be added, it's already there: No foreground/background materials, no "washing away" tunnel textures by liquids.
- Each polygon saves the position of the texture, which texture and other material info: Polygons can contain much more information than pixel based landscape - the number of textures, materials, etc. is not limited, properties, appearance of materials could be changed per-polygon. Landscape polygons could be converted in objects (of the physics engine), to fall down etc.
- Anitialising and rendering the landscape is easier and looks better on high zoom so that actually the "resolution" of the landscape (so: polygon count) could be decreased. Resolution of the landscape would be independent of the resolution of the game.
- Inserting polygons into the landscape is only fast if there are no other polygons in the way. If there are other polygons in the way, the polygon to be inserted must be subtracted from all polygons in the way first and then added because polygons (of one layer) may not overlap. This is expensive - see below
- For Blasting/Digging: Subtracting & merging polygons is very expensive. For every segmented line in every affected polygon, one has to check for intersections for every segmented line in the subtracting polygon. Then, for every segmented line in every affected polygon check if it is outside or inside of the subtracting polygon and use the gathered data to create new polygons. Read more here: http://revar.livejournal.com/81627.html
The polygons should be small to reduce the O(n²) fatality - Merging two non-overlapping polygons is very cheap. To merge overlapping polygons is as expensive as subtracting
- Improving performance: Freeze collision checks for objects that are stuck for each polygon. Memorise these objects and wake them up when the polygon is changed.
- To have two polygon representations in the memory wouldn't be good: A physics engine should offer to define interfaces for own polygon objects
- Improving performance: Precalculate normal vectors for each segmented line in the polygon to be able to return a normal on intersection checks faster. Collision checks (=intersection with a segmented line) are always directed in one direction. That's why the only the lines facing to object moving direction need to be checked. (Same as backface culling in computer graphics). If the segmented line is facing to the objects moving direction is determined by a scalar product which is much cheaper than an intersection check. This reduces the number of line segments that have to be touched two times.
The precalculated normal can be used for better physics and reducing the collision checks. - Important: Because the complexity to do anything with polygons grows with factor n for collisions or n² for modifications (n = count of vertices), the polygons must be small. I want to ensure this by creating a grid for the whole landscape, dividing it into boxes of, say, 200x200px that are reachable through an 2D-Array. Polygons are split if they are too big so that each polygon is only in one box. The polygons are stored per-box. For collision checks & material checks, only the polygons in the affected boxes are looked at. This reduces the number of polygons that have to be looked at for one check to a minimum, for boxes with no or only a single polygon to a single array-look-up (This method can have a similar effect than saving the landscape pixel-wise in a quadtree)
I think I missed some points but I will add them later.
Polygon landscape would be very nice, yeah, that'd offer great new possibilties for mappers! :DHm, but yes, calculating this stuff is expensive. :/
![[de]](/mwf/flags/de.png "Germany")
Not necessarily. If you f.e. want to check if one point in the map is solid it is a lot faster to just access an array of pixeldata. There you don't have to calculate whether this point lies in a polygon or not
To provide some more background information (on how they did things in the game "N"):
some nice basic tutorials on collision detection (SAT algorithm) for polygons (and round shapes):
http://www.metanetsoftware.com/technique/tutorialA.html
and a grid-based approach to speed things up (as you mentioned in your post):
http://www.metanetsoftware.com/technique/tutorialB.html
some nice basic tutorials on collision detection (SAT algorithm) for polygons (and round shapes):
http://www.metanetsoftware.com/technique/tutorialA.html
and a grid-based approach to speed things up (as you mentioned in your post):
http://www.metanetsoftware.com/technique/tutorialB.html
Yay. I read these tutorials some time ago.
it would enable landscape normals which means realistic landscape reflection (f.e. a rolling stone)
there is also an algorithm for generating landscape normals from pixel landscapes. You just have to have weighted pixels an there will be more than 8 directions for landscape normals
The formula is easily
The formula is easily
> 4. (...) For each line segment determine if the point lies to the left or right of a line. If it always lies on the right side, it's inside.
I don't understand why this is the case. Can you please explain this further or give me a link?
> 1. My concept in general: The polygons of the landscape may not overlap.
Why so restrictive? Not allowing polygons of the same material to overlap seems "obviously right" to me. However, different materials overlapping would, on the one hand, allow landscape designers to hide materials behind others (e.g. hide gold behind rock), and on the other hand, it would naturally include your "two layers of material polygons" case without making it a special rule.
> Sky means there are no polygons.
I don't like this "it's sky if nothing's there" approach, and already didn't like it in previous iterations of Clonk: Not only does it confuse newbies ("How do I insert Sky? It doesn't seem I can, there's no such material?") because it is counterintuitive, but it also removes the possibility to use any of the nice features the material polygons have. Multi-Texturing, for example, could be useful for implementing clouds.
Dynamic clouds could be nice with material polygons.
>> 4. (...) For each line segment determine if the point lies to the left or right of a line. If it always lies on the right side, it's inside.
>I don't understand why this is the case. Can you please explain this further or give me a link?
Given that the vertices of the polygon are given in a counter-clockwise order, the resulting line segments go in a counter-clockwise order, too. Each line(-segment) splits up the plane in two sides - left of the line and right of the line. Thus, for each line segment the point for which the check is conducted must be on the right side of the line. The check is less expensive than the one described earlier but only works with convex polygons.
>I don't like this "it's sky if nothing's there" approach, and already didn't like it in previous iterations of Clonk: Not only does it confuse newbies ("How do I insert Sky? It doesn't seem I can, there's no such material?") because it is counterintuitive, but it also removes the possibility to use any of the nice features the material polygons have. Multi-Texturing, for example, could be useful for implementing clouds.
We are talking about different things here:
- the "issue" with "inserting" Sky is one of the Clonk Editor - offering a rubber instead of a sky-brush. How it works technically is another thing.
- so what should be there if there is nothing? There will always be a background, what's the point of disallowing a "wallpaper" for this background? The existance of sky backgrounds do not preclude the possibility of background-polygons (such as tunnel and walls are, actually)
> Each line(-segment) splits up the plane in two sides - left of the line and right of the line.
Thank you, I get it now. I was mistakenly thinking of left/right as global directions, instead of line-relative.
> the "issue" with "inserting" Sky is one of the Clonk Editor
Mainly, but not exclusively. You also cannot insert Sky by using DrawMaterialQuad(), for example.
> so what should be there if there is nothing?
I don't know.
I should've been more clear, as I mixed two points together myself. My complaint is that Sky, even though it is treated as material in some places, is treated entirely differently in other places. E.g., you can get its material number by calling Material("Sky"), but not draw quads of it. So I'm not for disallowing "wallpapers", but for not treating Sky as a second-class citizen.
Using polygons for representing background/sky is my proposal for solving this. Obviously, when Sky is "just some material", too, the differences in its treatment are gone. (And, as a bonus, new cool tricks might become available.)
Lastly I attempt to answer your question: There could be "really nothing", as in: Black background, no Sky, no wind, no other properties Sky might have. There might also be the wallpaper you specify instead of black. Another possibility off the top of my head is specifying the rule that the whole landscape must be covered with polygons of some material, so there simply is no "nothing". Sky could also stay just as it is right now, with only "fixing" the functions dealing with materials, so that they work consistently with Sky, too. At the moment, I'm not rejecting any of these ideas.
I've taken the approach of no polygons (in this box) meaning "sky" out of considerations of performance. To solve or well-document inconsistencies in the handling of the interface for clonk developers is another issue. And actually, current handling is quite consistent in my opinion - "Sky" means "there is nothing there". You can ask that GBackSky()/Material("Sky" == -1) but you can't paint that. OK, one could add that painting sky means negative painting (rubber).Again, the approach of No polygon == Sky/Background does not exclude the possibility of polygon layers that are just for graphics and do not add to collision (Stuck) and material (GBack...) detection etc. But this is clearly not the topic here.
If Sky is a background material (like tunnel) and the whole landscape must be covered in background material, it would about double the count of background polygons, making material checks much slower. Additionally, material checks will be slower too because that the point is not in any tunnel polygon wouldn't mean automatically that it is in the sky. The complexity of painting background materials on sky will change from O(1) to something like O(n²).
More stuff- The algorithm to find the intersection between a line and a polygon must always* (see below) run through all line segments of the polygon since it has to elect the intersection closest to the line source point as the ONE (= first) intersection with the polygon. This makes it about 2x slower than I initially thought.
- Any intersections between lines and lines or lines and polygons can also be line segments and not just points. This must be taken into account in every algorithm which searches for intersections
- It is about 2x faster to check if a line intersects with a convex polygon because a convex polygon can have only two (relevant) intersections with a line. After having found two (if backface culling is activated: one) intersection, the algorithm can stop
- To calculate with anything else than absolutely precise values (and these do not exist) like floating point numbers or integers is problematic because a point which has been calculated to be on one line might not be exactly on that line any more if it is re-checked
- For the algorithms tailored for convex polygons to work properly, the polygon must be defined in a clockwise order
So far so good.
Need this for making use of physics engines possible:http://blog.touchmypixel.com/2008/06/making-convex-polygons-from-concave-ones-ear-clipping/
However, I think none of the algorithms shown there is optimal in the sense that it reliably produces polygons with a small perimeter. (All operations are faster on polygons with a small perimeter = which are more chunky and less spiky)
If a polygon landscape should be used in clonk, there are some problems apart from being able to change the polygons which need to be solved first (since they might influence the data structure and/or the algorithms for more basic operations on polygons).This is what comes to my mind but perhaps there are some more issues I didn´t think of. I´d like to hear the devs on this.
- Liquids! I´d be happy if someone can say something about common approaches and which one might be fitting for the polygon landscape. Any approaches in existing physics engines?
- Reactions between materials
- Change of materials (e.g. Lava -> Ashes, Ice<->Water)
- Graphical representation of the landscape which would make it look more 3D
Sold masks-> moveable polygonsVertices of objects-> either we stay with vertices or create a polygon out of the vertices and let a physics engine handle
maybe you make a OpenGL GUI interface (i'm working with delphi, but it should not be that problem in C++) into a branch so everyone can write parts of the poly-engine (rendering, physics etc.)
edit: i was talking about a seperate projectm not about implementing it into Clonk
edit: i was talking about a seperate projectm not about implementing it into Clonk
![[us]](/mwf/flags/us.png "United States")
For a start, I think it would be enough if the polygon landscape could work on the level of GetPixel/SetPixel and the initial landscape creation using DrawChunk. I guess SetPixel would essentially insert one small polygon and then the polygon concatenation algorithm should take care of it.This would allow us to test the landscape already, because it would be using the pixel-based PXS/MassMover system and eventually, every landscape modification call boils down to those methods. Of course those operations would be very inefficient and could be greatly accelerated by working on polygon borders instead. But that's an optimization that can be done later.
![[pl]](/mwf/flags/pl.png "Poland")
Check http://www.datarealms.com/
works fine with both pixel-based terrain, and pixel-based objects. You could ask developers what engine they are using.
works fine with both pixel-based terrain, and pixel-based objects. You could ask developers what engine they are using.
At liquids it would be great if there's a polygone-line on the surface of the liquid which can simulate waves and so on. That shouldn't be that ressource-consuming, in Blender it works in 3D =).
> # Liquids! I´d be happy if someone can say something about common approaches and which one might be fitting for the polygon landscape. Any approaches in existing physics engines?
Phun seems to use some kind of particle based approach that looks quite nice..: http://www.phunland.com/wiki/Home
Powered by mwForum 2.29.7 © 1999-2015 Markus Wichitill
