Sign in to follow this  
Meai

Unity Polygon convexity test: can't get it right

Recommended Posts

Meai    161
I looked at this topic and implemented a few ideas, but nothing ever covers every special case I get. I have a list of vertices in clockwise or anti clockwise order and need to know if they are convex. There are no duplicate vertices. I will post my own take on it, maybe it's just a simple error I can't find. Appreciate any help! http://www.gamedev.net/community/forums/topic.asp?topic_id=467104 I need this to work in 3d space, but I check beforehand in a different function if all the vertices lie in the same plane. This means my vertex list is essentially 2d. Now I still need to know which axis I can drop, so I loop for all axis values, calculate the difference and sum the difference up. The two axis which have the biggest sum, get taken for consideration. e.g: Vertex 1: x = 5; z = -5; y = 5; Vertex 2: x = 6; z = -5; y = 10; x-axis sum = abs(5-6) = 1 z-axis sum = abs(-5--5) = 0 y-axis sum = abs(5-10) = 5 I determine that x and y must be the dominant axis to form the polygon. This is how I try at the moment: (i left the parts out, where I determine the dominant axis, because the code would be too long. Here I always drop the y values. I essentially check if the sign of the dotproduct between two vectors pointing outwards from one vertex ever changes.
bool positive = false;
	for (int i = 0; i < points.size(); ++i)
	{
		vector3 A = points.at((i+1) % points.size()) - points.at(i);
		vector3 B = points.at((i+2) % points.size()) - points.at((i+1) % points.size());
		float dot_product;

			float temp_ax = A.x;
			A.x = -A.z;
			A.z = temp_ax;
			A.y = 0;
			B.y = 0;
			dot_product = A * B;
		
		if (i == 0 && dot_product > 0)
		{
			positive = true;
		}
		if (i == 0 && dot_product <= 0)
		{
			positive = false;
		}
		if (dot_product > 0 && !positive) return false;
		if (dot_product <= 0 &&   positive) return false;
	}
	return true;

The next thing I'm gonna try, is this: http://demonstrations.wolfram.com/AnEfficientTestForAPointToBeInAConvexPolygon/ I was a bit reluctant to use this method, because I usually make mistakes implementing mathematical texts, since I'm not a native english speaker.

Share this post


Link to post
Share on other sites
mzeo77    168
You should probably be using crossproduct in 2d instead.

Assume polygone is checked in x-y plane and p is circular array of size N:


for n in 1..N
if sign(cross(p[n].xy, p[n+1].xy).z) != sign(cross(p[n].xy, p[n+2].xy).z)
return false
return true;


Share this post


Link to post
Share on other sites
Decrius    100
Alright, took me a while to do, first time I did something in illustrator; but the following picture shows some things you can use to determine convexity:

Triangle convexity

So, you'd iterate over all vertices, and determine the direction (length not necessary, so just the sign is enough) of the cross-product between the 2 line-segments from the next and previous vertices to your current vertex. These signs should be equal for all vertices (either positive or negative).

Then the special case is when all angles ARE inward, but the total angles added are N * 360 degree, with N > 1 (ie. is goes 'round' twice or more, and thus overlap itself). Where ultimately the angle in total, as described in the picture, is (round-a-bout, take care with float in-precision) 360 degree.

I'm not aware if this is the most efficient method.

Share this post


Link to post
Share on other sites
Meai    161
Do you mean, that just the neighbouring line segments have to have the same sign in z, or do they all have to have the same. Because mzeo77 describes it so, that only neighbouring z signs have to be equal. But overall, there could be any number of change in signs.

This doesn't work either:


vector3 signs(0,0,0);
for (int i = 0; i < points.size(); ++i)
{
vector3 A = points.at((i+1) % points.size()) - points.at(i);
vector3 B = points.at((i+2) % points.size()) - points.at((i+1) % points.size());

vector3 tempsigns = Navigation::CrossProduct(A,B).normalize();
if (i == 0)
{
signs = Navigation::CrossProduct(A,B);
signs = signs.normalize();
}
if (signs.x != tempsigns.x || signs.y != tempsigns.y || signs.z != tempsigns.z)
{
return false;
}

}
return true;



@Decrius:
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?

Share this post


Link to post
Share on other sites
Decrius    100
Quote:
Original post by Meai
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?


Almost. All cross-products must have the same sign! If one has a positive cross-product, it means that the angle as in the picture is to the left (or right, but lets say left) from the "current" line segment. It "turns" a number of degree's to the left.
If it is negative, it turns to the other side. So the next line-segment would not turn some degree to the left, but to the right when viewed from the "current" line-segment.
If you have 2 different cross-products, this means it is not convex! Get some paper and draw some cases. What if one segment points to the left after the previous, and the next to the right? Can it ever be convex?

So, first test if all cross-products have the same sign. If not, break out (this can be an early breakout) and return false for not being convex. if all cross-products have equal signs, you can iterate again (or have done this in the cross-product-calculating loop) and make sure the angles added are not larger then 2*PI (or larger then 3*PI, since radians added will only ever yield N*2*PI, and you have to be aware of floating point in-precision).

By angles I mean the angles shown in my picture, not the angles _within_ the polygon.

Share this post


Link to post
Share on other sites
iMalc    2466
When I came up with such a function myself, I came up with a simple method. You don't need to discard one axis for it either.

All I do is that for every line segment, detect if all other points in the polygon lie on the same side of that segment. If there is any line segment with points from the polygon that lie on either side, then it's concave.
To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.

This method also detects self-intersecting polygons where the total angles add up to 720 etc as not being convex. With a careful selection of points to use for sided-ness testing, this method can be O(n).

Share this post


Link to post
Share on other sites
Decrius    100
Quote:
Original post by iMalc
With a careful selection of points to use for sided-ness testing, this method can be O(n).


How do you want to make a careful selection? If done the naive way this is O(n^2).
The method I described is neither optimal I guess, but it does only 1 dot and 1 cross product per vertex, so it is O(n) without any careful selection.

Share this post


Link to post
Share on other sites
Meai    161
@Decrius:
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?
Quote:
Then the special case is when all angles ARE inward

What is an inward angle? Angles < 90?

Quote:

and make sure the angles added are not larger then 2*PI (or larger then 3*PI, since radians added will only ever yield N*2*PI

So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?


Well I'll keep trying, but currently I don't have any success. Here is my take on iMalc's idea:
@iMalc: I didn't understand this part fully:
Quote:

To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.

but I took the idea, and implemented it a way I could think of:

for (int i = 0; i < points.size(); ++i)
{
vector3 lineSegment = points.at((i+1)%points.size()) - points.at(i);
for (int j = 0; j < points.size(); ++j)
{
// finding the normal to the line segment
float distanceToClosest = lineSegment * (points.at(j) - points.at(i));
vector3 closestPoint = points.at(i) + (distanceToClosest * lineSegment.normalize());
vector3 lineSegmentNormal = points.at(j) - closestPoint;
// the line segment normal * the vector from one of the line segment points (=closestPoint) to the point we currently test must be > 0
float result = lineSegmentNormal * (points.at(j) - closestPoint);
if (result < 0.0f)
{
return false;
}
}

}
return true;



But that isn't working in all cases either! If this code is correct, maybe my vertices just arent always in the same order. Very unlikely, but heck, I'd believe in anything right now.

Share this post


Link to post
Share on other sites
Decrius    100
Quote:
Original post by Meai
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?


No, c and a. In the picture A-C means a to the right pointing vector of length |c| starting in C (|c| = |A - C| = sqrt((A.x - C.x)^2 + (A.y - C.y)^2 + (A.z - C.z)^2)). B-A is a to the top-left pointing vector starting in A. So, around vertex A we have a vector pointing from the previous vertex (C) to the current vertex (A), and a vector pointing from the current vertex (A) to the next vertex (B).

Quote:
Original post by Meai
What is an inward angle? Angles < 90?


Sorry, that was vague. With inward I meant an angle that makes the next line-segment turn to the same direction as all other line-segments seen from the previous line-segment.

Imagine we traverse the contour of the polygon with a car in positive (counter-clockwise) direction. We start at vertex A, we go to B. At B we need to turn an angle 'beta' to the left. Riding on we come to C, then again we need to turn left, with angle 'gamma', at A with angle 'alpha' and we're back at the begin position.

We keep going left. If we'd go right at one vertex, it means the polygon is concave aka. not convex! With the car, we keep going "inward", sorry somehow that word feels natural... ;)

Quote:
Original post by Meai
So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?


No, the cross-product can also give negative numbers. Namely: (I x J) = -(J x I) (think about this!). It doesn't matter thus what order we apply the cross-product, as long as we're consistent throughout the algorithm. We only need to know if they are equal in sign.

If the angle between 2 vectors is 0 or 180 degree, the cross-product is zero.

In the car example above, the car turned exactly 360 degree (to the left). However, if we only check, we can allow contours like below, because all cross-products have the same sign!

Star

In this case, the angles added are 720 degree = 4 * PI; so the polygon is not convex!

Share this post


Link to post
Share on other sites
Meai    161
Thank you Decrius, it's pretty clear now. Tomorrow I have to study for an unrelated test, but then I'll implement it...and probably find something to ask you again :)

btw: fancy graphics!

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by Meai
@iMalc: I didn't understand this part fully:
Quote:

To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.

but I took the idea, and implemented it a way I could think of:
*** Source Snippet Removed ***

But that isn't working in all cases either! If this code is correct, maybe my vertices just arent always in the same order. Very unlikely, but heck, I'd believe in anything right now.

Okay, lets see if I can get the formula for the perpendicular component correct from memory:
Line segment from A to B, point to test is C.
vAB = B - A; vAC = C - A;
ParallelPartC = vAB * Dot(vAB, vAC) / Dot(vAC * vAC);
PerpendicularPartC = vAC - ParallelPartC;
Then you do the same with point D instead of C, giving PerpendicularPartD.
Now you check the sign of Dot(PerpendicularPartC, PerpendicularPartD) and it's convex if that's negative.

As for picking points in such a way as to make the algorithm O(n), you start with the previous and next points from that segment, but if say the next point lies on the line given by the line segment, then move to the next point, and skip the one that you found to be on the line later.

I doubt it has much advantage over any other method, but it's just another way to do it, that I realised would do what I wanted at the time.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Partner Spotlight

  • Similar Content

    • By Levgre
      I have a design doc I can share, either contact me here, at levgree@yahoo.com, or on Discord (tag is levgre#1415). I am only going over some of mechanics in this post, with more focus on combat than campaign, as combat is the core of the game.  designers could possibly be welcome, at the least I don't ever mind getting additional ideas/feedback.
      Like said in the title, the game is inspired by Darkest Dungeon, but aspiring for deeper and more varied combat/campaign mechanics.
      Theme: the player controls a party of raiders that go on missions, getting loot, building up reputation and experience, etc.  These missions would often be populated areas like towns and forts, but also could be caves, forests, and other settings.  
      The player will control a party of 6 characters.  Changing group formation and individual character positions will be an essential part of strategy for all party compositions.   However, most characters will still be in melee combat, as often the party will be fighting off enemies from both sides (just less often from the rear).
      Characters, both friendly and enemy, will be able to die or be severely injured in one hit, and no magical healing available.  However they will be able to dodge or deflect most attacks until they run out of "stamina", at which point they become sluggish and easier to kill.  So gameplay wise, stamina behaves sort of like the regenerating shield in halo.  However if the player makes a tactical error or puts a character in a situation where they are outmatched, characters could still be wounded even at full stamina.  So individual battles are not the only threat, but also tiring  from waves of enemies.
       The player's group can rest when needed, but that will allow the enemies to ready their defenses or get reinforcements.  So speed and smart stamina management is encouraged.  Although, there will be some level of variety in approach, the player could have a more heavily armored team that slogs through tougher fights, or a lightly armored quick characters for a fast team that relies more on the element of surprise. 
      Weapon and armor choices for each character will be significant strategic decisions, based on battle formation and also the strengths and weaknesses of the party comp/individual characters.
      The exact setting is not yet decided, it could be realistic medieval, high fantasy medieval with demihumans and magical creatures and some level of magic, steampunk, etc..  The "raiders" could be seafaring viking types, fighting in a religious conflict like crusaders, or some of both.
      Thanks for reading, and lmk if you are interested or have any questions.
    • By Spronx
      Hi guys,
      I'm Andy from StriX Interactive and we are
      LOOKING FOR A LEVEL DESIGNER
      to join us on this incredible adventure of developing Blood Oath. Open world fantasy 3rd person RPG in the style of The Witcher.
      We plan to launch a Kickstarter campaign by the end of the year. So it's not a paid job yet.
      We need someone capable of making terrain according to the world map that we have and over all level design. We have a great team and want YOU to be a part of it.
      Contact us on our facebook page https://www.facebook.com/StriXInteractive/

    • By Java Nigga
      Hi there!
      We are JN Studios, we are looking for people to work with us in our project.
      About US:
      JN Studios is a 2 people amateur studio. we have like 1 year making games, but this is our first professional project to show it to the public. We are a programmer guy(Me) and a 3d modeller.
      About the game:
      Strategist Sniper is a RPG/FPS game, yes RPG and fps :v you awake in the middle of the unknown and a small voice tells you that you have to go through the world killing other snipers to get out of there. the mechanics of the game are based on the basic controls of games like League of Legends and in FPS games like Counter Strike.
      What we are looking for?
      actually we are looking for another c# programmer, a musician and an artist(for game illustrations for the marketing of the game).
      Profits Share:
      when the game is in a stable alpha phase we will create a campaign in Idiegogo to obtain money to finance the game. each of the project participants will receive a percentage depending on the work done.
      How to apply?
      just send us a email with a portfolio and in what you can help our team -       trabajojava1@gmail.com


      Devblog1.mp4
    • By cursetalegame
      Hello! I am building the main scene in Unity for a 3D cards game. My goal is creating "card slots" to place the different cards from a deck and use it as "buttons". The image below represents somehow what I want to develop. I have been reading and I think that I have to generate a canvas and place in my scene the slots where I want to place the cards, but I am not sure about it. Also, to use the cards, I don't know if setting buttons is the best option (maybe I should use images instead).
      All recommendations and tips are welcome

    • By cursetalegame
      Hi! We are looking for a unity 3D developer to join our small "beginners" team. We are 3 artists (illustration, concept and 3D modeling), 2 designers and 1 programmer (me). We are developing an online video game that we have already designed. Our goal is to create a small studio and build up this game to take it to video game events around Europe and try to find publishers. Also we want to learn step by step how to develop games, so, is better if you don't have a huge experience in developing
      For more information, or any question, you can send us an email to cursetalegame@gmail.com 
      Cheers
  • Popular Now