[Scummvm-devel] That pesky CMI walkbox problem... (fwd)

[Max Horn]

At 16:55 Uhr +0100 05.02.2003, torbjorn.e.andersson at tietoenator.com wrote:
>Max Horn [mailto:max at quendi.de] wrote:
>
>>  COMI walkboxes, like the walkboxes in other Scumm games, are=20
>>  tetragons (i.e. polygons with four vertices and four edges).
>
>...
>
>>  Our code to check whether a point is inside the walkbox assumes the=20
>>  walkbox is konvex, a very reasonable assumption, and I would be=20
>>  surprised if they were  using non-convex walkboxes, it makes no sense =
>
>>  to do so.
>
>That's what I thought/hoped.
>
>But obviously something is wrong with it, or the walkbox 7 case
>described earlier wouldn't fail. This is what it looks like, as far as
>I can tell:
>
>      750,473                882,473  =20
>      LL +----------------------+ LR
>         |              861,503 |
>         |                 X    |
>         |                      |
>      UL +----------------------+ UR
>      750,533                882,533

Hm, so do you want to say that the rect is upside-down or what?


>The first part of the checkXYInBoxBounds() function looks ok to me,
>since it just seems to checks if the point is outside the walkbox's
>bounding rectangle.
>
>I haven't looked closer at the "is the walkbox a line" case, but I'll
>assume that's correct for now.
>
>Which leaves the four calls to compareSlope():

It's standard code to check whether a point is inside a konvex 
polygon or not. You compare the slopes between vertice A and the next 
vertice (B) to the slope between vertice A (again) and the point X. 
Then, you know whether X is left or right of the edge AB. So the 
above code could be read as...


>     if (!compareSlope(box.ul.x, box.ul.y, box.ur.x, box.ur.y, x, y))
>             return false;

   if (point X is not above UL-UR)
     return false


>     if (!compareSlope(box.ur.x, box.ur.y, box.lr.x, box.lr.y, x, y))
>             return false;

   if (point X is not left of UR-LR)
     return false



>     if (!compareSlope(box.ll.x, box.ll.y, x, y, box.lr.x, box.lr.y))
>             return false;

   if (point X is not below LL-LR)
     return false


>     if (!compareSlope(box.ul.x, box.ul.y, x, y, box.ll.x, box.ll.y))
>             return false;

   if (point X is not right of UL-LL)
     return false


>Where we fail on the very first one. This is the part of the function
>that I haven't made sense of yet.

I hope the above explanation helps a bit. Erhm, looking at it now, 
it's possible that I swapped left/right and up/down (as I based this 
on the "picture" above, which is clearly upside down, thus leading to 
a reversal of directions). Still the general notion holds. I need to 
look at the code what compareSlope actually computes to tell which of 
the two intepretions is implemented, but have no access to the 
ScummVM source right now.



I actually combed that code quite thouroughly in the past when I was 
fixing walk box issues in ScummVM a couple of month ago.


Cheers,

Max