[fixed]Problem with "closest node" order in getSce

[Josh1billion]

Here's a frustrating problem I've been trying to solve for the past couple of hours...

Note: I have uploaded a video, at the bottom of this post, to show the problem in action.

I have a scene node which is supposed to move forward whenever the player is in its "field of vision" and stop when the player is not. The "field of vision" is a simple 3D line (not a cone or anything). So far, my code works correctly for the most part, except for one thing...

You see, here is how the scene node (the "guard" enemy, since this is a sort of spy game) determines whether the player is in its field of vision (all should make sense, and getVisionLine() is defined below):

Code: Select all

bool Guard::playerIsInFOV()
{
	ISceneNode * nodeInVision = smgr->getSceneCollisionManager()->getSceneNodeFromRayBB(getVisionLine(), PLAYER | WALL);
	if (nodeInVision && nodeInVision->getID() == PLAYER)
		return true;
	
	return false;
}

As you can see, the code simply asks the scene's ISceneCollisionManager for the nearest PLAYER or WALL node which collides with this "field of vision" line. getSceneNodeFromRayBB(), according to documentation, returns the node which is nearest to the start of the line (in this case, nearest to the enemy guard). It is important that this is the nearest node to the guard (and this is what's causing the problem), because the guard is (and is meant to) only see the nearest object, whether it be a wall or a player, so that the enemy guard cannot see through walls.

The problem here is that the "nearest" order is apparently being reversed.. or something (and I just tried switching the "start" and "end" of the field of vision line, and that didn't help). The guard is seeing the "wall" as the closest node, even when the player is between the wall and the guard. You can see this in the video at the bottom of this post (as I said earlier, the guard is supposed to move forward whenever it "sees" the player).

For the sake of completion, here is the less important getVisionLine() function, which calculates the field of vision (which, as I stated earlier, is simply a 3D line, not a cone or anything complicated):

Code: Select all

line3df	Guard::getVisionLine()
{
 	vector3df guardPosition = node->getPosition() + vector3df(0, 10, 0); // y is increased by 10 so that the line starts just below the guard's eyes, not at its origin
	line3d<f32> visionPath(guardPosition, guardPosition + (vector3df(500, 0, 10)));
	return visionPath;
}

Summary of problem: I'm not sure whether I'm doing something wrong (please tell me if so-- also note that on a different "level" I tested [created in irrEdit, as was this one], everything worked fine).

YouTube upload of the problem in action: http://www.youtube.com/watch?v=H9-WGXpCdX8

[Josh1billion]

Got it.. almost.. I don't know how I did, though. :O

In irrEdit, I changed the wall (which is a cube)'s scaling a bit, and possibly the position, and that seems to have fixed things...

?

[Josh1billion]

Problem is appearing again.

Any ideas?

[vitek]

If I remember right, the code in CSceneCollisionManager::getPickedNodeBB() will get you the node whose farthest bounding box corner is nearest to the start of the ray (and is intersected by the ray). This will cause problems if the ray is inside the bounding box of one of the nodes in question. There may be other scenerios that this fails.

Could you create a simple testcase to illustrate the problem so that I can debug it? If not it'll have to wait until I have some free time.

Travis

[Josh1billion]

Aha! Here we go.. I just figured out what makes it work/not work.. (seems an Irrlicht bug)

Vitek, if by "testcase," if you mean an explanation of what works and what doesn't, here you are.

The wall is a cube, created in irrEdit, with a scale many times larger than the normal 1,1,1 scale. Now, the X scale is determining whether this will work or not work.

Right now, I have the scale working correctly at 1, 30 300. But if I increase the X scale from 1 up to 10, the problem shown in the video occurs.

Here are two screenshots to give a visual demonstration..

working (X scale 1) / not working (X scale 10)

(the screenshots are similar, but not identical, to the video -- note that the rainbow triangle toward the left is the position at which the enemy starts)

Results of more testing: actually, it doesn't matter that it's the X scale that's large (10 instead of 1)-- it matters that all scales are large. In other words, the problem occurs only when all scales are large-- everything will work fine if at least one scale is small (1 instead of 10+). But if all scales are 10 or higher, problems happen.

Sorry if this is confusing; it's hard to describe.

If you need any more details, don't hesitate.

[vitek]

if by "testcase," if you mean an explanation of what works and what doesn't, here you are.

No. I'm hoping that you'll take the time to write a simple, self contained, program that will show the problem on its own. Ideally all I'd have to do is compile, link, and run the program and I'd see the problem here. If you could write the program so that it requires no user input (i.e., I don't have to press keys to move characters to specific locations).

Sorry if this is confusing; it's hard to describe.

Exactly. That is why it is ideal for you to create a testcase. You might describe it well, but I may not understand what you are saying, or I may find some other issue and spend many hours trying to isolate something that isn't even the right problem...

Regardless, I think that if what you've found is correct, I should be able to create such a testcase later tonight.

Travis

[JP]

I would advise rather than using the collision manager needlessly for this you should just do an intersection test with the FOV ray and the player's bounding box....

[vitek]

It appears to be a bug. The distance that is calculated is in model space, but each model has a different scaling factor. Testcase follows...

Code: Select all

#include <irrlicht.h>
using namespace irr;

#ifdef _IRR_WINDOWS_
#  pragma comment(lib, "Irrlicht.lib")
#endif

int main()
{
    IrrlichtDevice *device =
        createDevice(video::EDT_OPENGL);

    video::IVideoDriver* driver = device->getVideoDriver();
    scene::ISceneManager* smgr = device->getSceneManager();
    scene::ISceneCollisionManager* coll = smgr->getSceneCollisionManager();
    irr::ITimer* timer = device->getTimer();

    scene::ISceneNode* wall = smgr->addCubeSceneNode(1.f);
    wall->setScale(core::vector3df(100.f, 100.f, 10.f));
    wall->setPosition(core::vector3df(0.f, 0.f, 500.f));

    scene::ISceneNode* player = smgr->addCubeSceneNode(10.f);

    scene::ISceneNode* robot = smgr->addCubeSceneNode(8.f);
    robot->setID(0);

    scene::ICameraSceneNode* camera = smgr->addCameraSceneNode();
    camera->setPosition(core::vector3df(110.f, 0.f, 500.f));
    camera->setID(0); // disable picking on camera    

    const core::vector3df beg (robot->getPosition());
    const core::vector3df end (wall->getPosition());

    video::SMaterial mtl;
    mtl.Lighting = false;

    core::matrix4 mtx;
    mtx.makeIdentity();

    u32 then = timer->getTime();

    f32 elapsed = 0.f;

    bool fail = false;

    while(device->run())
    {
        const u32 now = timer->getTime();
        elapsed += (now - then) / 1000.f;
        then = now;

        // limit to 10 seconds of moving
        if (10.f < elapsed)
            elapsed = 0.f;

        if (driver->beginScene(true, true, video::SColor(255, 80, 80, 80)))
        {
            // robot walks toward wall

            if (!fail) {
                robot->setPosition (end.getInterpolated(beg, elapsed / 10.f));

                const core::vector3df a = robot->getPosition();
                const core::vector3df b = wall->getPosition();

                // player is halfway between robot and wall
                player->setPosition (a + (b - a) / 2.f);

                camera->setTarget (player->getPosition());
            }

            smgr->drawAll();

            core::vector3df z (0.f, 0.f, 1.f);
            robot->getAbsoluteTransformation().rotateVect(z);

            core::line3df ray;
            ray.start = robot->getAbsolutePosition();
            ray.end   = ray.start + (z * 100.f);

            //
            driver->setMaterial(mtl);
            driver->setTransform(video::ETS_WORLD, mtx);
            
            scene::ISceneNode* hit = coll->getSceneNodeFromRayBB(ray, 1);
            if (hit == player) {
                driver->draw3DLine(ray.start, ray.end, video::SColor(255, 0, 255, 0));
            }
            else if (hit == wall) {
                driver->draw3DLine(ray.start, ray.end, video::SColor(255, 255, 0, 0));
                fail = true;
            }
            else {
                driver->draw3DLine(ray.start, ray.end, video::SColor(255, 0, 0, 255));                
            }

            driver->endScene();
        }
    }

    device->drop();

    return 0;
}

[vitek]

Sadly, it looks like I introduced this problem long ago in an attempt to fix a different one. See this thread. The good thing is that it looks like the fix is simple, but it will require that you rebuild the Irrlicht library if you apply the change.

Here is the patched part of CSceneCollisionManager::getPickedNodeBB().

Code: Select all

         // do intersection test in object space. we do this because the object
         // space bounding box is more accurate than a world space box
         if (box.intersectsWithLine(line))
         {
            box.getEdges(edges);
            f32 distance = 0.f;

            for (u32 e = 0; e < 8; ++e)
            {
               // transform corner back into world coordinates
               current->getAbsoluteTransformation().transformVect(edges [e]);

               // and compare it against the world space ray start position
               const f32 t = edges[e].getDistanceFromSQ(ray.start);
               if (t > distance) {
                  distance = t;
               }
            }

            if (distance < outbestdistance)
            {
               outbestnode = current;
               outbestdistance = distance;
            }
         }

Honestly, the best solution is to not use the box corners, but to look at where the intersection between the line and bounding box occured. That would be much more accurate.

I'll try to provide an enhancement to do that when I get some time.

Travis

[Josh1billion]

Alright, thanks a ton Vitek. Re-building the library right now.

[Josh1billion]

Hmm.. it doesn't seem to be fixed.

[vitek]

You need to make sure that the updated Irrlicht library is being used. If you have multiple copies of the library, you need to make sure that you're updating the right one. On Windows systems, you can just put the dll in the same directory as the executable.

If necessary, you should be able to set a breakpoint in the library and make sure that the correct code is being used. If it isn't, the debugger should tell you that the library is out of date.

Otherwise, I'm back to step 1. I need you to create a simple testcase that shows the problem. Something similar to what I've posted earlier in this thread.

Travis

[rogerborg]

Thanks for the report and investigation. I'll pick this up and steal all the glory now.

OK, the partial fix is in on the trunk in SVN 1991, with a new test case (and I verified that it got the wrong node without the patch). I agree that we should test the actual intersection point; I'll hold off on doing that in case Travis already has it in hand. Thanks again.

[rogerborg]

I'm hopeful that SVN 2050 fixes this. The new behaviour is:

If the ray starts outside the box, determine the actual distance as the distance from the ray start to where it enters an outside face of the box. Once we've hit a face, skip checking the other faces of that box, and truncate the ray so that it won't hit boxes that are further away. I'm hopeful that that last improvement will balance the extra calculations for the ray/face checks.

However, if the ray starts inside the box, consider the distance to be from the start of the ray to the centre of the box (i.e. don't consider where the ray leaves the box).

I'm not entirely happy with that "inside the box" thinking, so am open to suggestions about what to do in that case.

Since this is a significant functional change, I've only put it on the trunk, not the 1.5 branch. Testing, further fixes and suggestions are all very welcome.

[Yoran]

rogerborg,

some people including me lost the ability to use
"flat" nodes which do not have a height.
because you assume we can only hit one face, but in a flat node
this might not be true.

revision 2048 works like a charm, revision 2049 stopped working (where you added the gotHit in the for loop.