anyone coded Image Maps in LSL yet?

With the upcoming touch functions (see the beta grid! this is so wonderful!), there will be a need for some good imagemap library functions *coded in* in LSL. (as in, which rectangular region within a prim face got clicked)

So - Computer Graphics 101 question:

* Imagine you have a prim face with 10 arbitrary rectangular regions that may be clicked on (let's say it's a graphic of a remote control)
* figuring out point in a poly is easy, but what is a good method to know which imagemap region you have clicked in, aside from the brute force method of checking them all? I imagine there is some sorting of boundaries/vertices that can be done so that you greatly reduce the # of regions you check against? (yes.. this is CG 101/102

-- first goal is to check against non-overlapping rectangular ..
-- second goal would be to return a list of zero of more regions
hit (overlapping)

(and yes, one can only check this out on the beta grid for the moment, but it's worth the trip)

btw - this is of interest, but it's still point in poly.. not *which poly*:

http://visibone.com/inpoly/

(crash coursing basic CG ...)

A lot of useful algorithms will be inefficient to implement in LSL, unfortunately. Maybe if/once we get C# for Mono we'll be able to use some data structures that will make this feasible. Some basic algorithms should be doable, though. For example, initially sort rectangles by the left edge coordinate (or whichever is likely to eliminate the most regions) and then do a binary search, dropping everything to the right of the touch position. Resorting after that might not be worth it (and as mentioned multiple linked lists or whatever aren't likely to be), so probably linear iteration for the other edges (e.g. right, top, bottom) is the simplest solution and will be efficient enough for most applications.

Of course, there are plenty of application-specific possibilities for image maps other than simple arbitrary shapes/rectangles. For example, a grid or a set of regions divided hierarchically into sub-regions.

Yep, am thinking memory and execution times are going to be big constraints, but I hope I'm wrong...

I've been thinking about how to represent imagemaps. I think groups of two vectors in a list would do a lot:

[<x1, y1, FUNCTION_PTR>, <x2, y2, STACKING_ORDER>]

So x1, y1 are one corner, and x2, y2 are the other. This is for simple rectangles.

The interesting part is to overload Z in the vector.

For FUNCTION_PTR, it is a float, but you would cast it to an integer and compare it to a series of possible functions to call:

integer UPDATE_COLOR = 100;
integer PLAY_SOUND = 200;

and so on... when there is a region hit, grab the value of FUNCTION_PTR, cast it to an int, and do the if/then matching against the possibilities (since we dont have a switch statement.. )

For the second vector, I show something called STACKING_ORDER. This would be user defined, but I think of it as a way of specifying which FACE + WHICH MODE.

example: cube - 6 sides.. possible values for STACKING_ORDER:

100 - face 1, normal mode
110 - face 1, some other mode
...
600 - face 6, normal mode

In other words, STACKING_ORDER would give a unique number to each record in an image map, allowing you to use one overall list for all sides of a prim. I suppose you could call it FACE_MODE. It's just a float that would be cast to an int.

Anyways.. two vectors can be used to specify the coordinates of a rectangle, which function to invoke, and to map the entry to a given face & mode combination.

When registering a hit, you could filter by STACKING_ORDER first (you know which face, and which mode you are in), and from there, go through the vertices and do the point in the poly thing.

I so have to "read then post'"

though isn't the "llDetectedTouch" going to do the image mapping or am i confused ...

"llDetectedTouch is the latest thing from Qarl Linden, the man who gave you sculpties"

Uh.. if you're doing rectangular blocks on a face, isn't all you need to know is the number of blocks in each dimension and do a division and a modulo in order to get x/y block coordinates, and thus a number for the block.

Uh.. if you're doing rectangular blocks on a face, isn't all you need to know is the number of blocks in each dimension and do a division and a modulo in order to get x/y block coordinates, and thus a number for the block. At least, for a rectangular face.

I think you are stating the chessboard example.

I mean more interesting applications of imagemaps...

Think of web imagemaps, where different links are mapped to different portions of an image ... each region might be some arbitrary rectangle, but they dont map to an orderly grid.

HTML image-maps likely just use a simple loop since they rarely have many 'areas' on them. When it comes down to it you only have two types of basic shape you can really usefully have in 2D space; circles and polygons.

A circle is just a centre-point with a radius, very easy to detect if a click is in that by using:
llVecDist(centre, clickLocation);

For polygons (squares, rectangles, triangles, stars etc.) it's a little more complicated, but you can use the following algorithm:

list coords = []; // This will contain the co-ordinates of your polygon
                  // as vectors (with z ignored)
vector c = ZERO_VECTOR; // This will contain the co-ordinates of the
                        // touch

integer l = coords != []; // Get the length of coords
integer i = 0; integer j = l - 1; integer inPoly = FALSE;
while (i < l) {
    vector iv = llList2Vector(coords, i);
    vector jv = llList2Vector(coords, j);
    
    float diffY = (jv.y - iv.y);
    if (diffY == 0.0) diffY = 1000.0;
    
    if ((((iv.y <= c.y) && 
        (c.y < (jv.x - iv.x) * (c.y - iv.y) / diffY + iv.x))))
        inPoly = !inPoly;
        
    j = i++;
}

if (inPoly) llOwnerSay("Point lies within poly!");
else llOwnerSay("Point does not lie within poly!");

The following example co-ordinates would represent a square polygon 3 x 3 units big:
[<0.0, 0.0, 0.0>, <0.0, 3.0, 0.0>, <3.0, 3.0, 0.0>, <3.0, 0.0, 0.0>]

With the two above methods you can then simply create a list storing a mixture of circles and polygons, then use the appropriate algorithm to test each one in turn to see if the click was within it. The format of the list is up to you, but you'd need some way of specifying the type, the relevant values (centre + radius for a circle, or list of co-ordinates for a polygon) and then some ID value to determine what action to perform.
It occurs to me that you can 'overload' a 2D circle into a single vector like so:
<centre_x, centre_y, radius>

If you're going to be dealing with a ton of areas and think that the cost of processing them all one-at-a-time every-time will be too great then you may need to look at things such as binary space partitioning to reduce the number of actual shapes being tested, or use bounding boxes to get a rough idea of which shapes need tested more easily.

Not a bad approach, Bucky. It does constrain you to using rectangular target zones, though. Suppose you follow the same sort of logic but let the first vector in your pair be the center of the target zone and the second one be a point on the rim of the zone. Then you could use a digit in STACKING_ORDER to signal the shape of the zone. For example:

100 = face 1, square target
110 = face 1, rectangular target
120 = face 1, circular target
..
..
600 = face 6, square target

If STACKING_ORDER = 100, then the x, y values in the second vector would be interpreted as the coordinates at the center of one side of the square target. If STACKING_ORDER = 110, then x, y in that vector would mark a corner of the rectangular target (thus defining the semi-diagonal of the rectangle). If STACKING_ORDER = 120, then x, y would identify a point on the circumference of the circular target (thus defining the circle's radius).

This opens the possibility that the user might define overlapping targets and thus create ambiguous information about hits. So, you use the third digit in STACKING_ORDER to set a priority for the defined target. For example,

101 = face 1, square target, lowest priority
102 = face 1, square target, next higher priority

etc.

Then, if a user clicks in a region that might be in either target A or target B, and the second vector of B has a higher priority, the hit is registered in B rather than A.

I'm looking at this from a geometrical perspective, looking for a way to give the user some more flexibility. Not being a computer scientist, I cannot evaluate what effect this might have on memory and computing time.

Actually, instead of defining the square target area the way I suggested, it would be more interesting to let the x, y of the second vector be coordinates of a corner of the target area, as I suggested for the rectangular case. The distance between the x, y of the first vector and the x, y of the second one would then be a semi-diagonal. Because the shape was defined as a square, though, the user would effectively be defining a rotation for the target area -- the square target's sides would not need to be parallel to the edges of the prim it is on. Draw this one out .... you'll see what I mean.

Was thinking the other day about a possible method to at least narrow down a list of min/max coords to loop through... I'm probably making things way too complex, but here goes:

Maintain two lists, one of upper-left corner vectors, the other of lower-rights, with matching indicies. (The first element in each list defines the first button, the second in each defines the second, etc.) Pre-calculate two more lists of linear distances of those coordinates from the upper-left of the face, giving "near" and "far" radius parameters, strided with indicies to matching corner-list elements ( [ distance, index, distance, index, (...) ] ).

When a touch occurs, calculate the distance of that point from the upper-left. Add that value, strided with a dummy index (say, the letter "c" ) to copies of the near and far distance lists, and sort each, near descending, far ascending. Search the sorted lists for "c", and delete the "c" element and all before it on each list. Walk the shorter list, searching the other for each index value, and if found (i.e. if that index is in the overlap region), test if the clicked point falls within min/max corner designations of that index.

Of couse, I've yet written no actual code to do the above described, but after actually writing it out, it sounds like more workload than just looping through a list of button corners, unless there's a LOT of buttons.

I've come up with a means of using a list to represent an imagemap for
one or more faces. Each entry (two consecutive list elements) is made
of two vectors:

<x1,y1,FUNCTION_PTR>, <x2,y2,FACE_STACK>

* FUNCTION_PTR is just overloading the Z element of a vector to some
constant.
float PLAY_SOUND = 100.0;
float GIVE_TEXTURE = 200.0;

if (regionAction == PLAY_SOUND) {
doPlaySound();
} .. and so on...

* FACE_STACK is a number that represents a face and stacking order of regions 'over' it
Think of each face as having multiple entries:
Face 1: 110, 120, 130
Face 2: 210, 220

So, one list contains all of the imagemap entries for all of the faces on one prim.

Example:

[
<20,20,PLAY_SOUND>, <30,30,110>,
<25,25,GIVE_TEXTURE>,<35,35,120>,
<10,10,GIVE_LM>, <100,100,210>
]

When a hit comes in, just look at the FACE_STACK entries relevant to
that face (decrement by 10 in this example...)
In the example, Face 1 would be the first two groups of elements
(PLAY_SOUND and GIVE_TEXTURE) Some other variable would indicate the
height of the stack for each face (face 1 here has a height of 2)

--> start at 120, check for point in poly, then try 110,
--> check for point in poly, no? if we hit 100,
then there are no active regions for this face

Note: this is just for arbitrary rectangles. However, the stacking lets you
do overlapping. This buys a lot of flexibility.

So, two vectors for each region:

* First one gives x1, y1, and some constant so you know which function will get called
* Second one gives x2, y2, and some value that indicates a prim face and some order in which to check for points in a poly (work from 'top down' -- think of a windowing environment)

caveat: this is just for rectangles, and for single clicks. I cant see this working well with click and drag.

I understand what you're getting at. Personally, my approach for this situation would be to define rectangles or circles around the actual areas you want, to simplify things, with perhaps some other simplifications to make storage and searching of the list easier..

If your buttons are fixed, and you don't require great flexibility (the ability to drop new buttons in on-the-fly) then you can create a simple if-statement tree to divide up your image into distinct areas, allowing you to quickly narrow down the number of possible areas to test.

For example, if you have a star in the top right corner, and two circles in the bottom left, and bottom right corner of your image respectively, then you may build an if-statement tree like:

if (touch.x > 0.5) {
    if (touch.y > 0.5) // Check the star
    else // Check the bottom-right circle
} else if (touch.y < 0.5) // Check the bottom-left circle

If you need to be able to change this on-the-fly then it /is/ possible to calculate such a tree as items are added/removed, but using lists it won't be pretty or trivial to implement.

Oh I understand the simple cases with fixed sized buttons just fine (I did things in C with Xlib/XView/Motif long ago). Am just anticipating the generalized idea of an imagemap. It's a bit like a low level windowing environment