• Advertisement
Sign in to follow this  

Unity Polygon convexity test: can't get it right

This topic is 2932 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
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
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
@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
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
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
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
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Vu Chi Thien
      Hi fellow game devs,
      First, I would like to apologize for the wall of text.
      As you may notice I have been digging in vehicle simulation for some times now through my clutch question posts. And thanks to the generous help of you guys, especially @CombatWombat I have finished my clutch model (Really CombatWombat you deserve much more than a post upvote, I would buy you a drink if I could ha ha). 
      Now the final piece in my vehicle physic model is the differential. For now I have an open-differential model working quite well by just outputting torque 50-50 to left and right wheel. Now I would like to implement a Limited Slip Differential. I have very limited knowledge about LSD, and what I know about LSD is through readings on racer.nl documentation, watching Youtube videos, and playing around with games like Assetto Corsa and Project Cars. So this is what I understand so far:
      - The LSD acts like an open-diff when there is no torque from engine applied to the input shaft of the diff. However, in clutch-type LSD there is still an amount of binding between the left and right wheel due to preload spring.
      - When there is torque to the input shaft (on power and off power in 2 ways LSD), in ramp LSD, the ramp will push the clutch patch together, creating binding force. The amount of binding force depends on the amount of clutch patch and ramp angle, so the diff will not completely locked up and there is still difference in wheel speed between left and right wheel, but when the locking force is enough the diff will lock.
      - There also something I'm not sure is the amount of torque ratio based on road resistance torque (rolling resistance I guess)., but since I cannot extract rolling resistance from the tire model I'm using (Unity wheelCollider), I think I would not use this approach. Instead I'm going to use the speed difference in left and right wheel, similar to torsen diff. Below is my rough model with the clutch type LSD:
      speedDiff = leftWheelSpeed - rightWheelSpeed; //torque to differential input shaft. //first treat the diff as an open diff with equal torque to both wheels inputTorque = gearBoxTorque * 0.5f; //then modify torque to each wheel based on wheel speed difference //the difference in torque depends on speed difference, throttleInput (on/off power) //amount of locking force wanted at different amount of speed difference, //and preload force //torque to left wheel leftWheelTorque = inputTorque - (speedDiff * preLoadForce + lockingForce * throttleInput); //torque to right wheel rightWheelTorque = inputTorque + (speedDiff * preLoadForce + lockingForce * throttleInput); I'm putting throttle input in because from what I've read the amount of locking also depends on the amount of throttle input (harder throttle -> higher  torque input -> stronger locking). The model is nowhere near good, so please jump in and correct me.
      Also I have a few questions:
      - In torsen/geared LSD, is it correct that the diff actually never lock but only split torque based on bias ratio, which also based on speed difference between wheels? And does the bias only happen when the speed difference reaches the ratio (say 2:1 or 3:1) and below that it will act like an open diff, which basically like an open diff with an if statement to switch state?
      - Is it correct that the amount of locking force in clutch LSD depends on amount of input torque? If so, what is the threshold of the input torque to "activate" the diff (start splitting torque)? How can I get the amount of torque bias ratio (in wheelTorque = inputTorque * biasRatio) based on the speed difference or rolling resistance at wheel?
      - Is the speed at the input shaft of the diff always equals to the average speed of 2 wheels ie (left + right) / 2?
      Please help me out with this. I haven't found any topic about this yet on gamedev, and this is my final piece of the puzzle. Thank you guys very very much.
    • By Estra
      Memory Trees is a PC game and Life+Farming simulation game. Harvest Moon and Rune Factory , the game will be quite big. I believe that this will take a long time to finish
      Looking for
      Programmer
      1 experience using Unity/C++
      2 have a portfolio of Programmer
      3 like RPG game ( Rune rune factory / zelda series / FF series )
      4 Have responsibility + Time Management
      and friendly easy working with others Programmer willing to use Skype for communication with team please E-mail me if you're interested
      Split %: Revenue share. We can discuss. Fully Funded servers and contents
      and friendly easy working with others willing to use Skype for communication with team please E-mail me if you're interested
      we can talk more detail in Estherfanworld@gmail.com Don't comment here
      Thank you so much for reading
      More about our game
      Memory Trees : forget me not

      Thank you so much for reading
      Ps.Please make sure that you have unity skill and Have responsibility + Time Management,
      because If not it will waste time not one but both of us
       

    • By RoKabium Games
      We've now started desinging the 3rd level of "Something Ate My Alien".
      This world is a gas planet, and all sorts of mayhem will be getting in our aliens way!
      #screenshotsaturday
    • By Pacoquinha Studios
      Kepuh's Island is Multiplayer 3D Survival Game where you survive on the Kepuh's Islands, confronting challenges that are not only other players but also bosses, and even the environment itself.
      We have a lowpoly faster battle-royale idea, where about 12 players on the map fighting for survival! Also adding some more things into that style such as bosses around the map giving you abilities and much more such as vehicles, weapons, skins, etc...
      Now we are on cartase which is a crowdfunding online which purpose is to raise funds for the development of the game. Come and be part of this development.
      Link for Cartase: https://www.catarse.me/kepuhsisland?ref=project_link
      We post updates and trailers on
      Twitter: https://twitter.com/pcqnhastudios
      Facebook: https://www.facebook.com/pacoquinhastudios/
      Site: http://pacoquinhastudios.com.br
      If you could check out it would be great
      Thnks
      Some images:





  • Advertisement