[Resource] Method to solve if reference is inside complex re : V

» Sun Jun 15, 2014 5:17 am

In some bizarre circumstance, you may ask yourself, "How can I determine if the player is inside a region that can't easily be described using a trigger volume cube?" In my case, I needed to determine if the player was in a non-cube-like space that spanned across many, many cells; far too big and complex for a trigger box to be a reasonable solution. So what we want to know is if the player is inside a shape, or (more simply) if a point (the player) is inside a space represented as a polygon. This is actually a rather common problem in computer graphics, called the point in polygon problem. There are several methods to solve it, but here is the one I went with. It is from a http://alienryderflex.com/polygon/, converted from C to Papyrus.

bool function IsPointInPolygon(float[] polyX, float[] polyY, float x, float y)
Attempts to determine if a given point (x, y) lies inside the bounds of a polygon described as a series of ordered pairs described in the polyX[] and polyY[] arrays.

Spoiler

bool function IsPointInPolygon(float[] polyX, float[] polyY, float x, float y)	;-----------\	;Description \	;----------------------------------------------------------------	;Attempts to determine if a given point (x, y) lies inside the bounds of a polygon described as a series	;of ordered pairs described in the polyX[] and polyY[] arrays.	;If (x, y) lies exactly on one of the line segments, this functiom may return True or False.	;From http://alienryderflex.com/polygon/, converted to Papyrus by Chesko		;-------------\	;Return Values \	;----------------------------------------------------------------	;		True				=		 Point is inside polygon	;		False				 =		Point lies outside polygon OR polygon arrays are of different lengths	;float[] polyX = array that describes the polygon's x coordinates	;float[] polyY = array that describes the polygon's y coordinates	;float x	   = the x coordinate under test	;float y	   = the y coordinate under test		;Polygon arrays must be the same length	if polyX.Length != polyY.Length		return false	endif		int polySides = polyX.Length	int i = 0	int j = polySides - 1	bool oddNodes = false	while i < polySides		if (((polyY[i] < y && polyY[j] >= y) || (polyY[j] < y && polyY[i] >= y)) && (polyX[i] <= x || polyX[j] <= x))			if (polyX[i] + (y- polyY[i]) / (polyY[j] - polyY[i]) * (polyX[j] - polyX[i])) < x				oddNodes = !oddNodes			endif		endif		j = i		i += 1	endWhile		return oddNodesendFunction

The function returns true if the point given by x, y is inside the polygon described by the arrays. It will return false if the point is not inside, or if the arrays that you provided as parameters are not the same length. Returning false in the latter case was more ideal to me than dumping a ton of (array index out of range) errors in your papyrus log in the off chance that this occurred.

This function may return true or false if the point is directly on top of a vertex or segment. The function values speed over high levels of accuracy.

Example scenario:

Let's say I want to know if the player is inside a section of river near Riverwood. http://i.imgur.com/zrMHp.jpg (in red) that we care about.
We want to describe the area as a polygon by http://i.imgur.com/Jlp2V.jpg. It ends up being a 10-sided polygon.
Next, we can take those coordinates and plug them into a script, such as this example:

Spoiler

Scriptname _TEST_myPointInPolygonRiverTest extends QuestActor property PlayerRef autofloat[] myRiverPolyXfloat[] myRiverPolyYimport debugEvent OnInit()	;Initialize the array	myRiverPolyX = new float[10]	myRiverPolyY = new float[10]	;Populate array values that describe the polygon	myRiverPolyX[0] = 14889.85	myRiverPolyX[1] = 13869.10	myRiverPolyX[2] = 16938.22	myRiverPolyX[3] = 17743.47	myRiverPolyX[4] = 16763.15	myRiverPolyX[5] = 16811.10	myRiverPolyX[6] = 17797.28	myRiverPolyX[7] = 17823.37	myRiverPolyX[8] = 16988.59	myRiverPolyX[9] = 16098.66	myRiverPolyY[0] = -46124.05	myRiverPolyY[1] = -45167.48	myRiverPolyY[2] = -43011.81	myRiverPolyY[3] = -43976.84	myRiverPolyY[4] = -45001.36	myRiverPolyY[5] = -45582.18	myRiverPolyY[6] = -45775.87	myRiverPolyY[7] = -46529.61	myRiverPolyY[8] = -46465.85	myRiverPolyY[9] = -45956.11		RegisterForSingleUpdate(1)endEventEvent OnUpdate()	;Is the player inside the 10-sided polygon?	bool isInRiverPoly = IsPointInPolygon(myRiverPolyX, myRiverPolyY, PlayerRef.GetPositionX(), PlayerRef.GetPositionY())		if isInRiverPoly		notification("I'm inside the river polygon!")	else		notification("I'm not inside the river polygon!")	endif		RegisterForSingleUpdate(1)endEventbool function IsPointInPolygon(float[] polyX, float[] polyY, float x, float y)	;-----------\	;Description \	;----------------------------------------------------------------	;Attempts to determine if a given point (x, y) lies inside the bounds of a polygon described as a series	;of ordered pairs described in the polyX[] and polyY[] arrays.	;If (x, y) lies exactly on one of the line segments, this functiom may return True or False.	;From http://alienryderflex.com/polygon/, converted to Papyrus by Chesko		;-------------\	;Return Values \	;----------------------------------------------------------------	;		True				=		 Point is inside polygon	;		False				 =		Point lies outside polygon OR polygon arrays are of different lengths	;float[] polyX = array that describes the polygon's x coordinates	;float[] polyY = array that describes the polygon's y coordinates	;float x	   = the x coordinate under test	;float y	   = the y coordinate under test		;Polygon arrays must be the same length	if polyX.Length != polyY.Length		return false	endif		int polySides = polyX.Length	int i = 0	int j = polySides - 1	bool oddNodes = false	while i < polySides		if (((polyY[i] < y && polyY[j] >= y) || (polyY[j] < y && polyY[i] >= y)) && (polyX[i] <= x || polyX[j] <= x))			if (polyX[i] + (y- polyY[i]) / (polyY[j] - polyY[i]) * (polyX[j] - polyX[i])) < x				oddNodes = !oddNodes			endif		endif		j = i		i += 1	endWhile		return oddNodesendFunction

We then attach this script to a quest that will run our script for us and see what happens. As you can see, when the player is in the river, http://i.imgur.com/NDask.jpg, and when he's not, http://i.imgur.com/Rzv9j.jpg.

Since this area could easily be described as a set of carefully placed trigger boxes, this probably isn't the best example, but if you expand the size of the polygon to encompass a very large space (multiple cells), then you can see how this might become useful. For example, you could create a space that runs the entire length of a river across many cells to determine if the player is standing in it. Or whatever large-scale application you may need something like this for.

This function should accommodate severely concave polygons, but since the polygon is described as a series of ordered pairs, it will not solve for polygons with http://docs.oracle.com/html/A88805_01/sdo_objb.gif (since there is no way to describe the hole in a polygon described as a series of connected verticies). A possible way to do this is to describe the hole as a second polygon, and do a test for "if inside "hole" polygon, do x, elseif inside "actual" polygon but not "hole", do y".

Also, because of the maximum size restriction of Papyrus arrays, a polygon could have no more than 128 sides.

Enjoy, I hope someone finds this useful.

» Sat Jun 14, 2014 5:20 pm

It seems a good idea, probably better than the crappy (and long) "little fish" trick. But how would you get the float values on the fly ?

» Sun Jun 15, 2014 4:29 am

Thanks for this, I was JUST looking into a way to do this very task.

» Sat Jun 14, 2014 5:38 pm

Part of the idea is that the polygon's parameters are known ahead of time. It could be possible to get them at runtime IF you knew the exact shape of the polygon, and could determine the coordinates based on some other relative position (probably the player). What circumstance would you need to get it at runtime?

Another idea would be to use a spell that fired invisible rays from a point, recorded where the impacts occurred, and made those positions the vertices of your polygon.

» Sat Jun 14, 2014 5:11 pm

Runtime because, even with 128-sided polygons, wouldn't it be a hell of work to cover all waters of the map ?

This method would be efficient also for some MovableStatic like FXCreek ones, because they have both water & non-water parts, in a way that GetDistance() is really not accurate to detect water.

» Sat Jun 14, 2014 4:11 pm

You could do a version of that with ref-linked x-markers. Pass the first marker to the function and it talks the chain taking co-ords and adding them into the array. You'd need a fixed size array of course, and a limit function.

You could also bind the array to a script on a MiscObject and create a new instance for each polygon you need to solve for and get some true OO in the process. You could even create a special sort of XMarker for the first node in the chain and use that.

» Sat Jun 14, 2014 3:44 pm

It depends entirely on your application, but if that's what you want to do, sure. The river was just an example. You can use this anywhere for arbitrarily boxing up any given space. The difficulty of recording vertices is directly related to how many you have and to what level of accuracy you want. If the mesh has a gentle curve that might take 8 line segments to curve naturally with it, but you only require a rough degree of accuracy, you could use a single angle to describe the curve instead.

DocClox's method of getting the position of a set of ordered markers would be a good idea, though I only recommend getting the marker's position once and then reusing the data, since that many Gets that frequently would take an undesirably long time to execute.

» Sat Jun 14, 2014 10:12 pm

Very cool. Would it be possible to pull the coordinate data out of a region record? Or does Papyrus already have functions to determine if the player is within a defined region?

» Sun Jun 15, 2014 5:50 am

To my knowledge, no; this was a large reason why I investigated this. I needed to check if the player was in a Dawnguard weather region, and regions aren't exposed to Papyrus. So, I recorded (roughly) the coordinates of the vertices of the regions I cared about as they appeared in the Region Editor (with slight modification to ensure adjacent regions didn't overlap) and plugged them into arrays that this function checks. Works like a charm /biggrin.png' class='bbc_emoticon' alt=':D' />

» Sun Jun 15, 2014 12:30 am

Bummer, all I was able to find is a blank entry for IsPlayerInRegion, so there's a function in the code somewhere for this purpose but I guess it would require SKSE to expose it.

Your method works though, and for the purpose you PM'd me about I already have the coordinates I'd need, I'd just need to pull them out of the region data.

» Sun Jun 15, 2014 2:44 am

I have an idea, this might speed up development time by placing XMarkers (or Activator Triggers with a distinctive primitive color to see in the CK) at each point of the region your outlining, and adding them to a Form List / Array and obtaining the X,Y positions via Log file-output

Of course you wouldn't do this with your original mod, but a dummy test ESP to create the region points etc. This way you can make your array for your mod with the X,Y Values to use this specific function

» Sun Jun 15, 2014 2:45 am

That's actually an old command left over from FO3's (maybe Oblivion, too) legacy scripting language.

» Sun Jun 15, 2014 4:41 am

The condition function IsPlayerInRegion works just fine.

» Sun Jun 15, 2014 2:04 am

Sure, for dialogue and other condition based actions, but I had assumed you thought it was an undocumented Papyrus function or something. Sorry about that!

» Sat Jun 14, 2014 11:04 pm

No, that was me who thought that. The wiki entries for condition functions aren't always clear on what they're there for.

And for the record, that was introduced in GECK. The Oblivion CS had no such nicety.

» Sat Jun 14, 2014 11:58 pm

I'm not necro'ing this thread, it's relevant and invaluable sometimes. I just wanted to say this is superb.