Page MenuHomeWildfire Games

ConvexPolygonPlacer optimization in rmgen.
Needs ReviewPublic

Authored by nani on Sep 22 2018, 2:16 AM.

Details

Reviewers
FeXoR
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Summary

Improves performance of the placer by minimum 2 fold with the same results.

Test Plan

No test plan.

Diff Detail

Repository
rP 0 A.D. Public Repository
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

nani created this revision.Sep 22 2018, 2:16 AM
nani created this object with visibility "nani".
nani changed the visibility from "nani" to "Public (No Login Required)".Sep 22 2018, 5:55 PM
nani updated this revision to Diff 6909.Sep 24 2018, 7:20 PM

Standardization of code, removed duplicated function and added more comments.

Stan added a subscriber: Stan.Sep 24 2018, 7:33 PM

What about that code's license ?

nani added a comment.EditedSep 24 2018, 8:24 PM
In D1640#65070, @Stan wrote:

What about that code's license ?

Aside from what I wrote there are three sources:

  1. ConvexPolygonPlacer.prototype.place

https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/ has https://fgiesen.wordpress.com/2013/03/10/on-epubpdf-versions-of-my-posts-and-licensing/
which is CC-0, basically meaning "No Rights Reserved".

  1. ConvexPolygonPlacer.prototype.pruning

http://mindthenerd.blogspot.com/2012/05/fastest-convex-hull-algorithm-ever.html
The code was made from the seudo-code provided in the page and there is no mention of any copyright or license in that page or any that linked from/to it from what I could find.

  1. ConvexPolygonPlacer.prototype.getConvexHull

https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#JavaScript
Has "Creative Commons Attribution-ShareAlike License".

I will update comments to add url of each license

nani updated this revision to Diff 6911.Sep 24 2018, 8:42 PM

Added license

Stan added a reviewer: Restricted Owners Package.Sep 24 2018, 11:13 PM

Thanks, just making sure, so we don't get into trouble later.

nani updated this revision to Diff 6916.Sep 29 2018, 8:53 AM

Corrected some typos.

FeXoR added a subscriber: FeXoR.Nov 9 2018, 2:56 PM

What exactly is to be optimized here? Speed?
AFAICS there's a lot more code and no tests to show the benefit.
(It also seems to be a lot more code then in the links BTW ;p)

Please make the effort to clearly state what is to be achieved here and gather some data to back that up ;)

If you understand the text describing the algorithm and write the code yourself there's no need for licenses or links to be added to 0 A.D. trunk (which I would be glad about).

FeXoR added a reviewer: FeXoR.Nov 9 2018, 2:56 PM
FeXoR added a subscriber: elexis.EditedThu, Nov 15, 1:12 PM

So I figure this is part of #5305 which also have some data backing up the claims but not for this specific patch.
Also it would be very preferable to not having to add code that needs additional license comments so please try to wright this from your own understanding.
I don't think using pseudo code as a source for writing your own needs license reference.
What do you say, @elexis ?

The question is how much faster this is. It must be worth the code complexity. If it's only a fraction of a second, that may be meh.
(Also my alarm goes off when I see variables storing X and Z coordinates that arent vectors)

FeXoR added a comment.EditedThu, Nov 15, 2:48 PM
In D1640#66297, @elexis wrote:

The question is how much faster this is. It must be worth the code complexity. If it's only a fraction of a second, that may be meh.

Agreed, as I wrote.

(Also my alarm goes off when I see variables storing X and Z coordinates that arent vectors)

x1, x2, y1, y2 are x/y ranges so it's absolutely valid to store them in variables IMO (just that they are constants).

I manly wanted to ask about the needed license additions BTW ^^
(Other comments still welcome ofc.!)

In D1640#66298, @FeXoR wrote:
In D1640#66297, @elexis wrote:

The question is how much faster this is. It must be worth the code complexity. If it's only a fraction of a second, that may be meh.

Agreed, as I wrote.

(Also my alarm goes off when I see variables storing X and Z coordinates that arent vectors)

x1, x2, y1, y2 are x/y ranges so it's absolutely valid to store them in variables IMO (just that they are constants).

In general on Vector2D:
If one does something to a 2D or 3D coordinate, then one performs vector algebra.
If one uses the Vector2D prototype, then one can use vector operations, such as rotate, add, mul, cross, perpendicular, dot, length, lengthSquared and whatnot.
If one uses X/Z coordinate pairs, it means one has to write down the solved vector equations. At least one line of JS statement per dimension of the resulting vector.
X/Z pairs may be easy to read if there are only 2 operations. But if there are 3 or more, it quickly becomes unreadable, geometrically unintelligible.
The commits in #4805 contain some of the worst examples of geometrically unintelligible equations that became readable when using Vector2D operations.
Most illustrative were the paintRiver and path-creation ones. It was virtually impossible to understand these functions unless solving algebraic equations, in order to logically (= geometrically) comprehend the written equations.

If the geometric meaning of the vector operations is obscured or unrecognizable, the code cannot be audited, let alone be inviting for newcomers to extend.
In particular equations of 4+ operations that contain rotation or cross products operations can take hours to decipher if one doesn't already know what's happening in that code.

The commits in #4992 and #4845 established code consistency by replacing the remaining minority of X/Z pair variables with Vector2D instances.
In the last measurement I recall, the Vector operations were even slightly faster (possibly because only half the variables were allocated and garbage collected).

Using the more scalable syntax (Vector2D) prevents the possibility of reintroducing the non-scalable syntax (X/Z pair) and ending up in having to rewrite the code in case one wants to extend it to the point where the more scalable syntax is definitely needed.
(Introduce code correctly, then you don't need to rewrite it from scratch later.)

To use X/Z pairs instead of Vector2D objects, there must be a very good reason to (overriding all the reasons that speak for using vector algebra explicitly).

I manly wanted to ask about the needed license additions BTW ^^

In general I don't mind if there is a link to an external work, as long as the link is informative and any required licensing is compatible, reasonable. Better with less references than more though. Also often a custom implementation can be faster, safer or better suited than an imported one.
The important part about license additions is that LICENSE.txt is kept up to date.
Indeed nani copied the code 1:1 from that website. That's more problematic if we didn't understand the code (improper coding, missed possibility for optimization, missed possibility to make the code more inviting to newcomers) than the licensing being a problem here.

binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
17

Missing semicolon, this is an assigment x = y;.

Would be better in Vector2D, possibly as a "static" function?
Is this equation paresent in other places of the code too and could be reused there? (we can easily search for cross products, as we use Vector2D everywhere...)

21

The imported code is CC-0 licensed. Afaik CC-0 grants anything, so it also grants release under GPL v2+.

However if we say this function is CC0 licensed, then this function is not GPL v2+ licensed, because CC-0 also grants everything that GPL v2+ forbids (such as distribution of the application without the source).

In particular if we add our own contributions to this function, they will be licensed under CC-0 instead of GPL v2+ according to that line.

It seems more simple to state that this is a derived work licensed as GPL v2+ where the original work is licensed as CC-0.

37
67

Bitwise-or? I didn't really examine it, but isn't it equivalent to w0 >= 0 || w1 >= 0 || w2 >= 0, or (w0 || w1 || w2) >= 0? it faster or slower than that (If so, by how much?)

109

What is happening here?

FeXoR added inline comments.Thu, Nov 15, 6:04 PM
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
109

This spans a quadrangle with:
A the bottom right most point
B the top right most point
C the top left most point
D the bottom left most point

A rectangle (with an angle of Pi/4 between it's side and the axis) with these pints on it's sides will contain all given points.
A rectangle (with it's sides parallel to the axis) with the x range between the lower of the 2 upper points x value and the upper of the two lower points - and the same in y direction - will only contain "inner" points not part of the convex hull - so they can be dismissed (see below).

FeXoR added a comment.Thu, Nov 15, 6:15 PM

@elexis : On Vectors: Uhm, yes, I agree on using vectors can make things easier and they should be widely used (Though much less to those "unreadable", "impossible to understand", " obscured or unrecognizable" for those are IMO obscured references to properties of the reader, not the code... This depends strongly on habituation IMO). But, yes. I think we are on the same page here. Just ... which part of this specific patch are you referring to?

In D1640#66306, @FeXoR wrote:

@elexis : On Vectors: Uhm, yes, I agree on using vectors can make things easier and they should be widely used (Though much less to those "unreadable", "impossible to understand", " obscured or unrecognizable" for those are IMO obscured references to properties of the reader, not the code... This depends strongly on habituation IMO).

I wasn't kidding when I said unrecognizable, unreadable code in the sense that it with only few operations can sometimes takes hours instead of 5 minutes to understand the geometric meaning of a handful of vector operations. It took 6 months from my life to rewrite this to a point where it could be read quickly. Now we can open a file, read it from top to bottom and understand it on first read, rather than having to reiterate 10+ times with each iteration adding understanding of one more operation of the function. Even the spahbod posted on the forums that he didn't understood his own code anymore: https://wildfiregames.com/forum/index.php?/topic/15580-random-map-scriptrivers/&tab=comments#comment-233079 "took me 3 days and a major overhaul of old river code", "I can't remember now what each part of the code does". That's the pattern that went through all random/maps/ files to different degrees of severity (rP20308).

which part of this specific patch are you referring to?

I mentioned the topic of Vector algebra briefly because the patch doesn't use Vector algebra where it presumably easily could.
(For example the inline comment, there is Vector algebra which after some transformations would probably look much more readable. Notice the ConvexPolygonPlacer.prototype.orient function didn't came across either until I lobbied on the lobby for using the cross function, you can see it in the first version of this upload.)
But "In general" is marked in bold above and I elaborated on this topic extensively to you not because the coding convention violation of this patch is so relevant, but because I am afraid that you didn't see the reason behind the coding convention yet and might let others get away with this code style in other patches or introduce it yourself in future maps, when there might not be a very good reason to. Resist the beginnings or something.

binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
109

How is it written in vector algebra? The unequation A.x - A.y <= p.x - p.y is unintuitive, because subtracting the X coordinate from the Y coordinate makes no sense. After some transformations I suppose it will be more transparent (I won't solve it).

smiley added a subscriber: smiley.EditedFri, Nov 16, 6:19 AM

I am going to have to side with elexis on this one. Apart from what he has said, using a position vector instead of an x and y variable makes more sense to me.
let point = new Vector2D(10, 10);
vs.

let point_x = 10;
let point_y = 10;

Now imagine trying to manipulate it.
This of course doesn't mean that stray coordinates are bad. But they should be avoided and only used when necessary.

Stan added inline comments.Fri, Nov 16, 8:50 AM
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
109

Could be replaced by an arrow function as well.

140

++i

149

--i

smiley added inline comments.Fri, Nov 16, 10:52 AM
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
67

That but with && I think. I suspect it would be pretty much the same or just slightly slower. Bit-wise operations in JS is pretty slow compared to c/c++.

smiley added inline comments.Fri, Nov 16, 2:25 PM
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
109

It’s trying to find the bottom right corner I guess. i.e the point where x-y is the largest. Hence, the largest x with the smallest y. Same for the other inequalities.
I am pretty sure it can be made more transparent. It is not clear what the code is doing quickly.

FeXoR added a comment.Fri, Nov 16, 7:44 PM
In D1640#66314, @elexis wrote:

[...]
I wasn't kidding when I said unrecognizable, unreadable code in the sense that it with only few operations can sometimes takes hours instead of 5 minutes to understand the geometric meaning of a handful of vector operations.

And I wasn't when I said it's an obscured property of the reader, not the code. But since I agree with you and smiley seems to join us I don't see a problem here. And thanks for your devotion to make the code more appealing to at least us 3 (and - I expect - most of the readers).

which part of this specific patch are you referring to?

I mentioned the topic of Vector algebra briefly because the patch doesn't use Vector algebra where it presumably easily could.

No need to presume since I answered your question in the first reply on your comments on using vectors: It's ranges, not vectors.
And, yes, you can use vector algebra to calculate the volume of a cuboid that has given length of edges a, s and c by choosing an arbitrary point, say O, and an arbitrary coordinate system with an orthonormal basis (hopefully) linked to it and then determine three vectors, say v_a, v_b, v_c that have the properties that v_a.dot(v_a) == a², v_b.dot(v_b) == b², v_c.dot(v_c) == c² and v_a.dot(v_b) == 0, (v_a.dot(v_c) == 0, v_b.dot(v_c) == 0 and finally volume = v_a.dot(v_b.cross(v_c)).length() if one wants desperately to use Vectors. It also happens to be a*b*c which is shorter, faster and - I estimate - more readable to most readers. Also the prototype "length" should be called "abs" because the meaning of the resulting value depends on the case the lib's code usually doesn't know - in this case it happens to be the volume. So, no, I don't agree it's always better to use vectors, even if one could. And I originally thought that would be rather a consensus than a single point of view.

(For example the inline comment, there is Vector algebra which after some transformations would probably look much more readable. Notice the ConvexPolygonPlacer.prototype.orient function didn't came across either until I lobbied on the lobby for using the cross function, you can see it in the first version of this upload.)

And what do you expect to happen now? The author is trapped in this situation, having copied the code (well, maybe just lazy) probably not easily able to convert that to vector algebra. You demanding, but not willing to do it yourself (or check yourself if your concern is valid). And I would rather write an own patch than excepting this one due to the licensing.

But "In general" is marked in bold above and I elaborated on this topic extensively to you not because the coding convention violation of this patch is so relevant, but because I am afraid that you didn't see the reason behind the coding convention yet and might let others get away with this code style in other patches or introduce it yourself in future maps, when there might not be a very good reason to. Resist the beginnings or something.

What code convention violation? And thus what code convention's reason? I'll get code "away" after checking a long list of pros and cons when the outcome is positive. While I can write the list down (and had written it down for you more than once) it's still a mostly arbitrary decision - as is yours. The only difference I see is you think that "is" and I think that "I think". I don't allow patches in to "allow" myself to use that stile later myself ;D I don't even thing that far! If I want to have code that does something I write code that does that. If it makes sense to me to use vectors I do that. If It doesn't I don't.

I see the goal of libraries to support the user to do things more easily. If the libraries are enforced to be used in a specific way they might actually become a hindrance.
If that's true for a user I expect them to not use them if the aim (e.g. a random map) can be achieved that way. Because otherwise the libraries would prevent possible achievements and thus fail to fulfill their purpose. And, yea, here we might actually fundamentally disagree.

But otherwise - at least I thought until your last comment - we are on the same track...

FeXoR added inline comments.Fri, Nov 16, 8:15 PM
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
109

Oh, replace Pi/4 by Pi/8 in my last comment ^^

A.x - A.y <= p.x - p.y

can be read as : If (P.x|P.y) is more bottom right from the straight line between x- and y-axis than (A.x|A.y)

One could rotate all position vectors by Pi/8 and check for the point with the maximum x value (right most) and set A to it.
Same with B just with max y (top most), C just min x (left), D min y.
(If one stores the indices one doesn't have to rotate back. Still that will be a lot slower)

Still the next part is about intervals on x/y axis.

FeXoR added inline comments.Fri, Nov 16, 8:17 PM
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
109

Oo, Pi/4 was correct ofc and Pi/8 isn't x)

Also the prototype "length" should be called "abs" because the meaning of the resulting value depends on the case the lib's code usually doesn't know - in this case it happens to be the volume.

abs might have a double meaning, but so does length. It should technically be magnitude, no? But length is more intuitive when thinking about 2D space.
I mostly agree with the rest of the thing with regard to readability and vectors. Although, thats a pretty extreme example.

FeXoR added a comment.EditedSat, Nov 17, 4:47 PM
In D1640#66354, @smiley wrote:

abs might have a double meaning,[...]

What is the double meaning in respect to vectors? Different objects in math have an Absolute Value but each object type's absolute is unambiguous.

It should technically be magnitude, no?

You are correct: No! ^^ The Magnitude is a ranking and thus in general less strict than a Norm. However, the norm of vector spaces can't usually be used to order them for multiple non-equal elements can have the same absolute value (see Vector spaces with additional structure).

But length is more intuitive when thinking about 2D space.

Yea, not a big deal IMO but why not make the libs as clean and clear as possible? (And what would be more clean as mathematical rigorous definitions or more widely available like Wikipedia article's sayings?)
Also you said "let point = new Vector2D(10, 10);" would make more sense to you and there is Vector.distanceTo() ... which is exactly what I would have hoped to avoid for Points are not Vectors, They don't even have the same dimensions (Point: 0, Vector: 1, the vector spaces themselves usually have n - 2 or 3 in our case). Vectors have no distances but points have, points have no differences but vectors have, especially vectors have a length and signed direction while points have positions and relations as unsigned distances.

Although, thats a pretty extreme example.

I agree, but, well, the first thing that came to mind ;)

What is the double meaning in respect to vectors? Different objects in math have an Absolute Value but each object type's absolute is unambiguous.

Exactly what I had in mind while I was writing that. In case of a simple number, it is the “value” of it. Which could be misunderstood as a "simple getting rid of the minus". Obviously, this is not the case with vectors. Not a big deal, pretty unlikely scenario anyway.