3D Line bounding box

[Icare]

Hi there,
I am trying to create a Bounding box of a 3d line, but without working solution.

I have also tried to find the coordinates of the box from coordinates of the two first points (non linear system of equation, a bit hard).

There is any functions or available source code for that ?

Thanks a lot,
icare

[vitek]

Code: Select all

core::aabbox3df box (line.start);
box.addInternalPoint (line.end);

Not incredibly difficult...

[Icare]

Actually i want to create a bigger bounding box, like a cylinder or a big cube around the line. So the user can select the line even if the mouse cursor is not exactly on the 3d line !

[JP]

Code: Select all

core::aabbox3df box (line.start + vector3df(-1,-1,0));
box.addInternalPoint (line.end + vector3df(1,1,0)); 

I guess that would work (with 1 being replaced by however much bigger you want the box to be) if your line was parallel to the Z axis.

So if it's not, which you probably can't guarantee your line's alignment you can transform the vectors being added by the transformation of the line. Though you probably only know the start and end of the line so i'm not sure how you'd do that... Maybe you'd have to just work out the 3D rotation of the line? Although the bounding boxes are axis aligned so maybe it doesn't have to be 3D rotation...

[rogerborg]

Actually i want to create a bigger bounding box, like a cylinder or a big cube around the line. So the user can select the line even if the mouse cursor is not exactly on the 3d line !

Using Irrlicht's built in collision-detection? That only supports axis aligned bounding boxes, which won't work well for selecting a line.

Perhaps if you explained your requirements fully, we could suggest an appropriate solution.

[vitek]

Code: Select all

core::aabbox3df box (line.start + vector3df(-1,-1,0));
box.addInternalPoint (line.end + vector3df(1,1,0)); 

I guess that would work (with 1 being replaced by however much bigger you want the box to be) if your line was parallel to the Z axis.

So if it's not, which you probably can't guarantee your line's alignment you can transform the vectors being added by the transformation of the line. Though you probably only know the start and end of the line so i'm not sure how you'd do that... Maybe you'd have to just work out the 3D rotation of the line? Although the bounding boxes are axis aligned so maybe it doesn't have to be 3D rotation...

Instead of trying to deal with all of that rotation stuff it would be much simpler to write...

Code: Select all

core::aabbox3df box (line.start); 
box.addInternalPoint (line.end);

// x, y and z can be any positive value, probably based on
// length of line up to some limit.
const core::vector3df delta (x, y, z);
box.MaxEdge += delta;
box.MinEdge -= delta;

Travis

[Icare]

Using Irrlicht's built in collision-detection? That only supports axis aligned bounding boxes, which won't work well for selecting a line.

Yes i am using IrrLicht bounding box collision detection. I am trying to select 3dline, representing edges of some mesh.
I didn't know that irrlicht only support axis aligned bounding box, so it's why it's not work well with my 3d line (wich can be placed randomly, depends of the mesh).
I will see if triangle selector can be used, or if you know a better way...

Thanks a lot !

[Icare]

I come back with my selection problem :
So i'm trying to create a 3d modeler (something like wings 3d).
I have several custom scene node :
- 1 flat custom scene node per face
- 1 3d line per edge
- 1 square billboard per vertex

The selection of the vertex billboard is working well.

The selection of faces is working bad, because i am using bounding box, and now i know that is because bounding box are aligned with axes.
The selection of edge is not working.

I think i can use triangle selector, but i don't know if my software will lag or not, with a lot of faces and edges ?

So my question is, there is a light way to select flat and 3d line objects ?

Thanks a lot for your answers !!

[arras]

You can try this:

you have your object (3D line) and test line going from camera position out to somewhere where your mouse points.

you also have two coordinate systems: one global and one local coordinate system of your object.

What you need to do is to create axis aligned bounding box inside local coordinate system and transform test line from global to local system.

Then check collision between test line and bounding box inside that local system.

It would require some matrix math but would not be that difficult probably.

[rogerborg]

^^^
That would be pretty good, but my rule of thumb is: if I can't knock it up over lunch, it probably is a bit "difficult". I can't immediately grok the maths to transform the ray into both object space and edge space.

- 1 3d line per edge

I'll do you this one for free. Then I will require a blood sacrifice. I like goats. Mmmm, goaty.

This builds a plane around each edge, and checks where a ray from the cursor hits it. It then works out how far the intersection is from the edge, and if it's close, and closer than any other edge, it selects the edge.

This has the advantage that it gives an easy test for the closest edge to the cursor. An AABB test would just give a hit or miss.

Code: Select all

#include <irrlicht.h>

using namespace irr;

#pragma comment(lib, "Irrlicht.lib")

class SelectableEdgesNode : public scene::ISceneNode
{
    core::aabbox3df Box;
    core::array<core::line3df> Edges;
    core::array<core::vector3df> EdgeUnitVectors;
    video::SMaterial Material;
    int SelectedEdge;

public:

    SelectableEdgesNode(scene::ISceneNode* parent, scene::ISceneManager* mgr, s32 id)
        : scene::ISceneNode(parent, mgr, id)
    {
        SelectedEdge = -1;
        Material.Wireframe = false;
        Material.Lighting = false;

        core::vector3df corners[4];
        corners[0].set(0, 14, 0);
        corners[1].set(-10, 0, -10);
        corners[2].set(10, 0, -10);
        corners[3].set(0, 0, 14);

        for(int corner1 = 0; corner1 < 4; ++corner1)
            for(int corner2 = corner1 + 1; corner2 < 4; ++corner2)
            {
                const core::line3df edge(corners[corner1], corners[corner2]);
                const core::vector3df edgeUnitVector = edge.getVector().normalize();
                Edges.push_back(edge);
                EdgeUnitVectors.push_back(edgeUnitVector);
            }

        Box.reset(corners[0]);
        for (s32 i=1; i<4; ++i)
            Box.addInternalPoint(corners[i]);
    }


    virtual void OnRegisterSceneNode()
    {
        if (IsVisible)
            SceneManager->registerNodeForRendering(this);

        ISceneNode::OnRegisterSceneNode();
    }

    virtual void render()
    {
        u16 indices[] = {   0,2,3, 2,1,3, 1,0,3, 2,0,1   };
        video::IVideoDriver* driver = SceneManager->getVideoDriver();

        driver->setMaterial(Material);
        driver->setTransform(video::ETS_WORLD, AbsoluteTransformation);

        for(u32 edge = 0; edge < Edges.size(); ++edge)
        {
            if(SelectedEdge == edge)
                driver->draw3DLine(Edges[edge].start, Edges[edge].end, video::SColor(255, 0, 255, 0));
            else
                driver->draw3DLine(Edges[edge].start, Edges[edge].end);
        }
    }

    virtual const core::aabbox3d<f32>& getBoundingBox() const
    {
        return Box;
    }

    virtual u32 getMaterialCount() const
    {
        return 1;
    }

    virtual video::SMaterial& getMaterial(u32 i)
    {
        return Material;
    }

    void testLineIntersectionWithEdges(const core::line3df & line)
    {
        core::line3df localLine(line);
        core::matrix4 inverseTransform;
        if(!AbsoluteTransformation.getInverse(inverseTransform))
            return;

        inverseTransform.transformVect(localLine.start);
        inverseTransform.transformVect(localLine.end);

        const core::vector3df lineUnit = localLine.getVector().normalize();

        const f32 VirtualEdgeThicknessSq = 3.f * 3.f; // Thicken up the edge
        f32 closestToLineSq = VirtualEdgeThicknessSq;

        SelectedEdge = -1;
        for(u32 edge = 0; edge < Edges.size(); ++edge)
        {
            core::vector3df normal = lineUnit.crossProduct(EdgeUnitVectors[edge]);
            normal = EdgeUnitVectors[edge].crossProduct(normal);

            core::plane3df plane(Edges[edge].start, normal);

            core::vector3df intersection;
            if(plane.getIntersectionWithLine(localLine.start, lineUnit, intersection))
            {
                const core::vector3df nearestPoint = Edges[edge].getClosestPoint(intersection);
                const f32 distanceToLineSq = intersection.getDistanceFromSQ(nearestPoint);

                if(distanceToLineSq <= closestToLineSq)
                {
                    closestToLineSq = distanceToLineSq;
                    SelectedEdge = edge;
                }
            }
        }
    }
};

int main()
{
    IrrlichtDevice *device =
        createDevice(video::EDT_OPENGL, core::dimension2d<s32>(640, 480), 16, false);
       
    if (device == 0)
        return 1; // could not create selected driver.

    video::IVideoDriver* driver = device->getVideoDriver();
    scene::ISceneManager* smgr = device->getSceneManager();

    smgr->addCameraSceneNode(0, core::vector3df(0,0,-40), core::vector3df(0,0,0));

    SelectableEdgesNode *myNode =
        new SelectableEdgesNode(smgr->getRootSceneNode(), smgr, 666);

    scene::ISceneNodeAnimator* anim =
        smgr->createRotationAnimator(core::vector3df(0.3f, 0, 0.3f));

    myNode->addAnimator(anim);
    anim->drop();

    while(device->run())
    {
        core::line3df cursorRay = smgr->getSceneCollisionManager()->getRayFromScreenCoordinates(device->getCursorControl()->getPosition());

        myNode->testLineIntersectionWithEdges(cursorRay);

        driver->beginScene(true, true, video::SColor(0,100,100,100));
        smgr->drawAll();
        driver->endScene();
    }

    myNode->drop();
    device->drop();
    return 0;
} 

[Icare]

Well, it was a long time ago, but i forgot to post my face selection to you.
So as a thank you for everyone (and a special thank you to rogerborg), here my face selection node :

Code: Select all

/!*
*\date : SEPTEMBER 2008
*\brief : a face scene node with selection from mouse
**/
 
#include <irrlicht.h>
#include <vector>
 
using namespace irr;
 
#pragma comment(lib, "Irrlicht.lib")
 
class SelectableFacesNode : public scene::ISceneNode
{
    core::aabbox3df Box;
    std::vector<core::triangle3df> Faces;
    std::vector<core::vector3df> corners;
    //core::array<core::line3df> Edges;
    core::array<core::vector3df> EdgeUnitVectors;
    video::SMaterial Material;
    int SelectedFace;
 
public:
 
    SelectableFacesNode(scene::ISceneNode* parent, scene::ISceneManager* mgr, s32 id)
        : scene::ISceneNode(parent, mgr, id)
    {
        SelectedFace = -1;
        Material.Wireframe = false;
        Material.Lighting = false;
       // Material.TextureLayer[0].Texture[0].
 
        corners.push_back(core::vector3df(0, 14, 0));
        corners.push_back(core::vector3df(-10, 0, -10));
        corners.push_back(core::vector3df(10, 0, -10));
        corners.push_back(core::vector3df(0, 0, 14));
 
         for(int corner1 = 0; corner1 < 4; ++corner1){
            for(int corner2 = corner1 + 1; corner2 < 4; ++corner2)
            {
                for(int corner3 = corner2+1; corner3 <4; ++corner3)
                {
                    const core::triangle3df face(corners[corner1], corners[corner2], corners[corner3]);
                    Faces.push_back(face);
                }
 
            }
         }
 
 
        /*Vertices[0] = video::S3DVertex(0,0,10, 1,1,0,video::SColor(255,0,255,255),0,1);
        Vertices[1] = video::S3DVertex(10,0,-10, 1,0,0,video::SColor(255,255,0,255),1,1);
        Vertices[2] = video::S3DVertex(0,20,0, 0,1,1,video::SColor(255,255,255,0),1,0);
        Vertices[3] = video::S3DVertex(-10,0,-10, 0,0,1,video::SColor(255,0,255,0),0,0);*/
 
 
 
  Box.reset(corners[0]);
                for (s32 i=1; i<4; ++i)
                        Box.addInternalPoint(corners[i]);
 
 
    }
 
 
    virtual void OnRegisterSceneNode()
    {
        if (IsVisible)
            SceneManager->registerNodeForRendering(this);
 
        ISceneNode::OnRegisterSceneNode();
    }
 
    virtual void render()
    {
        u16 indices[] = { 0,2,3, 2,1,3, 1,0,3, 2,0,1 };
 
        video::IVideoDriver* driver = SceneManager->getVideoDriver();
 
        driver->setMaterial(Material);
        driver->setTransform(video::ETS_WORLD, AbsoluteTransformation);
 
        for(u32 face = 0; face < 4; ++face)
        {
            if(SelectedFace == face)
                driver->draw3DTriangle(Faces[face], video::SColor(255, 0, 255, 0));
            else
                driver->draw3DTriangle(Faces[face], video::SColor(255, 0, 0, 255));
 
        }
 
    }
 
    virtual const core::aabbox3d<f32>& getBoundingBox() const
    {
        return Box;
    }
 
    virtual u32 getMaterialCount() const
    {
        return 1;
    }
 
    virtual video::SMaterial& getMaterial(u32 i)
    {
        return Material;
    }
 
    void testLineIntersectionWithEdges(const core::line3df & line)
    {
        core::line3df localLine(line);
        core::matrix4 inverseTransform;
        if(!AbsoluteTransformation.getInverse(inverseTransform))
            return;
 
        inverseTransform.transformVect(localLine.start);
        inverseTransform.transformVect(localLine.end);
 
        const core::vector3df lineUnit = localLine.getVector().normalize();
 
        const f32 VirtualEdgeThicknessSq = 6.f * 3.f; // Thicken up the edge
        f32 closestToLineSq = VirtualEdgeThicknessSq;
 
        SelectedFace = -1;
        for(u32 face = 0; face < 4; ++face)
        {
            /*core::vector3df normal = lineUnit.crossProduct(EdgeUnitVectors[edge]);
            normal = EdgeUnitVectors[edge].crossProduct(normal);*/
 
            core::plane3df plane = Faces.at(face).getPlane();
 
            core::vector3df intersection;
            if(Faces.at(face).getIntersectionWithLine(localLine.start, lineUnit, intersection))
            {
                const core::vector3df nearestPoint = Faces[face].closestPointOnTriangle(intersection);
                const f32 distanceToLineSq = intersection.getDistanceFromSQ(nearestPoint);
 
                if(distanceToLineSq <= closestToLineSq)
                {
                    closestToLineSq = distanceToLineSq;
                    SelectedFace = face;
                }
            }
        }
    }
};
 
int main()
{
    IrrlichtDevice *device =
        createDevice(video::EDT_OPENGL, core::dimension2d<s32>(640, 480), 16, false);
 
    if (device == 0)
        return 1; // could not create selected driver.
 
    video::IVideoDriver* driver = device->getVideoDriver();
    scene::ISceneManager* smgr = device->getSceneManager();
 
    smgr->addCameraSceneNode(0, core::vector3df(0,0,-40), core::vector3df(0,0,0));
 
    SelectableFacesNode *myNode =
        new SelectableFacesNode(smgr->getRootSceneNode(), smgr, 666);
 
    scene::ISceneNodeAnimator* anim =
        smgr->createRotationAnimator(core::vector3df(0.3f, 0, 0.3f));
 
    myNode->addAnimator(anim);
    anim->drop();
 
    while(device->run())
    {
        core::line3df cursorRay = smgr->getSceneCollisionManager()->getRayFromScreenCoordinates(device->getCursorControl()->getPosition());
 
        myNode->testLineIntersectionWithEdges(cursorRay);
 
        driver->beginScene(true, true, video::SColor(0,100,100,100));
        smgr->drawAll();
        driver->endScene();
    }
 
    myNode->drop();
    device->drop();
    return 0;
}
 
 

I hope my first Irrlicht code will help. (maybe admin need to move this post to snipplet).

[rogerborg]

Hmm, I'm thinking not. I'm glad the edge test was useful, but the face check has some issues. I'm not convinced that all the triangles are facing out, and the distance check should be to the start of the ray, not to the closest point on the triangle (since the intersection point on the triangle is axiomatically the closest point on the triangle to the intersection ).

Nice try though.

[Icare]

Hum, maybe i have not posted the last version (because i didnt check and run the code before post it). I will check.