Intersections maths

[REDDemon]

Hi I just looked at intersection methods used in irrlicht, there are some that needs some improvements (better algorithsm mostly), also I don't understan exactly why certain signature of functions are done in certain ways, so probably I could add few extra methods, and also improve their documentation.

If you feel uncomfortable with some math functions just tell me about your use case so I can add (of course I will ask other developers first! but I can start a draft anyway) better methods and improve documentation!:

cheers.

[CuteAlien]

Hm, I might know reasons for implementations at least for some of them, so pm when in doubt.

Got some notes about that stuff on my todo (all kind of tiny stuff which I just put on todo and never cared about *sigh*):
irr::core::line3df::getClosestPoint should have a onlySegments parameter like line2df

irr::core::line2d::intersectWith allows line-line and segment-segment intersections. line-segment would be nice. Maybe also ray vs X.

irr::core::line3d needs same fixes for integer instancing as line2d got in r4076.

irr::core::line2d (and probably 3d) getUnitVector sucks for integer instancing. Maybe add getUnitVectorf32 (or getUnitVector2df)

irr::core::plane3d::classifyPointRelation has problems (maybe only for integer instancing): http://irrlicht.sourceforge.net/forum/v ... 5&p=265944

[REDDemon]

Ah I see now. Yes I understand why most things was done like that. The problem with intersections is that there are specific (and most times) better algorithms for most cases, also it makes sense sometimes to have the specialization for other types. I will post shortly some of the possible improvements so we can discuss them. Incidentally you already pointed most of the problems I found

[CuteAlien]

OK. Sometimes also worth take a look at history of a file - I remember we removed for example once an algorithm which was fast, but never returned exact enough results - which did lead to some tricky problems with collisions.

[REDDemon]

this is the list of changes so far, I'm creating some tests for it right now. The algorithms are accurate, those are quick versions (have to profile anyway).

it is pretty similiar to original this one, but without al the branching of the intersectsWith method.
line2d

Code: Select all

 
        /*! Check if this segment intersects another segment,
            or if segments are coincindent (colinear). */
        bool intersectAsSegments( const line2d<T>& other)
        {
            // Taken from:
            // http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
 
            // Find the four orientations needed for general and
            // special cases
            s32 o1 = start.checkOrientation( end, other.start);
            s32 o2 = start.checkOrientation( end, other.end);
            s32 o3 = other.start.checkOrientation( other.end, start);
            s32 o4 = other.start.checkOrientation( other.end, end);
 
            // General case
            if (o1 != o2 && o3 != o4)
                return true;
 
            // Special Cases to check if segments are coolinear
            if (o1 == 0 && start.onSegment( other.start, end)) return true;
            if (o2 == 0 && start.onSegment( other.end, end)) return true;
            if (o3 == 0 && other.start.onSegment( start, other.end)) return true;
            if (o4 == 0 && other.start.onSegment( end, other.end)) return true;
 
            return false; // Doesn't fall in any of the above cases
        }
 
        /*! Check if 2 segments are incident (intersects in exactly 1 point).*/
        bool incidentSegments(const line2d<T>& other)
        {
            return 
                start.checkOrientation( end, other.start) != start.checkOrientation( end, other.end);
            &&  other.start.checkOrientation( other.end, start) != other.start.checkOrientation( other.end, end);
        }
 

vector2d

Code: Select all

 
    /*! Test if this point and another 2 poitns taken as triplet
        are colinear, clockwise, anticlockwise. This can be used also
        to check winding order in triangles for 2D meshes.
        \return 0 if points are colinear, 1 if clockwise, 2 if anticlockwise
    */
    s32 checkOrientation( vector2d<T> b, vector2d<T> c)
    {
        // Example of clockwise points
        //
        //   ^ Y
        //   |       A
        //   |      / \
        //   |     /   \
        //   |    C-----B
        //   +---------------> X
 
        s32 val = (b.y - y) * (c.x - b.x) -
            (b.x - x) * (c.y - b.y);
 
        if (val == 0) return 0;  // colinear
 
        return (val > 0) ? 1 : 2; // clock or counterclock wise
    }
 
    /*! Returns true if points (a,b,c) are clockwise on the X,Y plane*/
    inline bool areClockwise( vector2d<T> b, vector2d<T> c)
    {
        s32 val = (b.y - y) * (c.x - b.x) -
            (b.x - x) * (c.y - b.y);
 
        return val > 0;
    }
 
    /*! Returns true if points (a,b,c) are counterclockwise on the X,Y plane*/
    inline bool areCounterClockwise( vector2d<T> b, vector2d<T> c)
    {
        s32 val = (b.y - y) * (c.x - b.x) -
            (b.x - x) * (c.y - b.y);
 
        return val < 0;
    }
 
    // Given three colinear points p, q, r, the function checks if
    // point q lies on segment 'pr'. The point "p" is this one.
    bool onSegment( vector2d<T> q, vector2d<T> r)
    {
        //   (this)p .
        //            \
        //             \   
        //              \ 
        //               . r
        //                -
        //                 -
        //                  . q (hei there! Am I on the segment or outside?)
        //
        if (q.x <= max_( x, r.x) && q.x >= min_( x, r.x) &&
            q.y <= max_( y, r.y) && q.y >= min_( y, r.y))
            return true; // inside
 
        return false; // outside
    }
 

[CuteAlien]

Yeah, ok. Minor note - pass variables as const references when possible (like: const vector2d<T>& b).
Spelling: coolinear is collinear :-) colinear also more often spelled as collinear, so we should probably use that.

[REDDemon]

sure!

[devsh]

we got rid of the entire collision engine of irrlicht and wrote our own which is more manageable for picking with a huge set of instances.... you know where the source is

[CuteAlien]

@devsh: This is about intersections, not about geometry picking. Thought in case you haven't noticed - geometry picking (aka ITriangleSelector stuff) was also somewhat changed in Irrlicht recently (to allow for meshbuffer picking). Without breaking downward compatibility.

[REDDemon]

why implement a collision engine if we have bullet/Newton/ODE ? XD

http://irrlicht.sourceforge.net/forum/v ... 75&start=0

Those are just simple goemetric utilities that can make life easier and are nice for playing with irrlicht. If that are bad Idea just tell me and I move on doing something else

[CuteAlien]

About collisions: You can often go somewhat faster when you know the concrete case you need stuff for, so I guess if you write a Minecraft alike game there are probably specific optimizations for that. I suppose where Irrlicht could profit would be better/more space partitioning options (grid/quadtree). I implemented some of those for own projects, but never in a general way that fit into Irrlicht well (I want the switch to STL first - it makes those things easier).

And please go on with those functions :-) Btw... that checkOrientation might also fit in triangle3d.