Results 1 to 14 of 14

Thread: Strange create_collision_outline problem

  1. #1

    Default Strange create_collision_outline problem

    I was messing around with CL_CollidableSprite::create_collision_outline and ran into a strange problem with a specific sprite that I had.

    Below is the image that does not generate properly.
    Name:  asteroid.png
Views: 94
Size:  5.8 KB

    This is a screenshot of the resulting collision areas as generated by create_collision_outline. The red circles are the result of draw_smallest_enclosing_disc(...) while the yellow circles are the result of calling draw_sub_circles(...). The white outline is the result of calling draw(...). The actual outline is always spot-on no matter what level of accuracy I use.
    Name:  bad_collision.png
Views: 30
Size:  46.7 KB

    As you can see, the discs are way off.

    If I switch to accuracy_high, the sub-circles get better but the enclosing disc is still wrong:
    Name:  bad_collision2.png
Views: 27
Size:  42.9 KB

    The code is really basic, 2 sprites loaded from a resource file. Both are the same image. I call CL_CollidableSprite::create_collision_outline(gc, "Asteroid", &resources, 128, CL_OutlineAccuracy::accuracy_poor) twice to generate two outlines of the same image. Each collision-outline I call set_translate(...) and set_angle(...) on with the current position/angle. Both the sprites and collision-outlines are set to an alignment of origin_center. I then draw each at (0, 0) since the transforms will change their world position.

    As a result, CL_CollisionOutline::collide(...) doesn't seem to work since the overall disc never encompasses what is needed to evaluate a true collision. A collision does register when their overall-disc and some sub-circles overlap.

    Does anyone have any idea what could be causing this? The code works just fine if I swap the image out to something simpler like a box, or even a triangle with one concave side. Something about this image causes the sub-circle generation to go haywire even though the outline looks great.

  2. #2
    ClanLib Developer
    Join Date
    Sep 2006
    Location
    Bergen, Norway
    Posts
    588

    Default

    Does it help if you call the calculate...() functions on the outline ? http://clanlib.org/docs/clanlib-2.3/...e-members.html

  3. #3

    Default

    Quote Originally Posted by sphair View Post
    Does it help if you call the calculate...() functions on the outline ? http://clanlib.org/docs/clanlib-2.3/...e-members.html
    I had given this a try yesterday. The generated values change based on the angle. Below are some screenshots of when I call calculate_convex_hulls(), calculate_smallest_enclosing_discs(), calculate_sub_circles(), and calculate_radius() in the main loop for the left most asteroid. You can see the values change based on the angle.

    Name:  collision_recal1.png
Views: 9
Size:  41.3 KBName:  collision_recal2.png
Views: 7
Size:  48.5 KBName:  collision_recal3.png
Views: 8
Size:  52.5 KB

    I would think that the contours would remain exactly the same. Shouldn't the geometric data be generated based on the graphic at zero degrees and then a copy of the data get transformed and used for collision?

  4. #4
    ClanLib Developer
    Join Date
    Sep 2006
    Location
    Bergen, Norway
    Posts
    588

    Default

    I'm sorry, I don't really know. The collision code is unfortunately a black hole that noone is actively working on.

  5. #5

    Default

    Quote Originally Posted by sphair View Post
    I'm sorry, I don't really know. The collision code is unfortunately a black hole that noone is actively working on.
    Ok. I'll try and take a peek into it to see if there is anything obvious. The ease of collision detection is one of the things that lured me to this library - I was hoping to avoid having to port some routines from a C# library I wrote.

    Does anyone know what algorithms are used for the polygon detection? I've written SAT polygon collision routines before but they only work with convex polys.

  6. #6
    ClanLib Developer
    Join Date
    May 2007
    Posts
    1,824

    Default

    I would try your graphics with Tests/Display/Collision ... It tests all collision functionality if I remember correctly.

  7. #7

    Default

    Quote Originally Posted by rombust View Post
    I would try your graphics with Tests/Display/Collision ... It tests all collision functionality if I remember correctly.
    I just gave it a try and using CL_CollidableSprite::create_collision_outlines() and create_collision_outline() both crash in the example collision program. I added the asteroid.png file 60 times via:

    Code:
    <sprite name="teapot">
      <image file="asteroid.png" />
      <image file="asteroid.png" />
      <image file="asteroid.png" />
      ...
    </sprite>
    And then commented out the original teapot. create_collision_outline() (no "s") works fine in my original program. But the plural version also crashes in my original program as well.

    Just to further the test in the example, I resulted to just manually loading 60 copies of the collision by doing:
    Code:
    teapot_collisions.push_back(CL_CollisionOutline("resources/asteroid.png"));
    teapot_collisions[i].calculate_convex_hulls();
    teapot_collisions[i].calculate_radius();
    teapot_collisions[i].calculate_sub_circles();
    teapot_collisions[i].calculate_smallest_enclosing_discs();
    This "sorta" works as shown below:
    Name:  coll.png
Views: 12
Size:  103.8 KB

    I say "sorta" because the outline isn't quite right. If you look closely and compare with the original pictures you'll notice that there should be a dip in the outline of the asteroid where it is more concave. This gets eliminated by the calculate_convex_hulls() function (which is also what allows the radii to be properly calculated).

    This is the same behavior in my original program.

    Below is a screenshot where I commented out the calculate_convex_hulls() function. Notice the outline is then correct but the radii are wrong.
    Name:  coll2.png
Views: 13
Size:  105.6 KB

  8. #8
    ClanLib Developer
    Join Date
    May 2007
    Posts
    1,824

    Default

    I did not mean the collision example, I mean the collision test - They are different.

    I think that you will have to find the problem, there are no active developers who know the collision code base.

    I know some other developers use the Box2D library instead, but I don't know if it has the same functionality as CL_Collision.

  9. #9

    Default

    Woops.

    Ok, ran with the test bed and it still fails. I guess I've happened to stumble across an image (my first damned image ) that breaks the circle calculations but I don't yet know why.

    Here's a definite overlap with no collision detected:
    Name:  coll-bad.png
Views: 10
Size:  64.8 KB

    And if I move it over the center, then it's detected:
    Name:  coll-good.png
Views: 10
Size:  73.6 KB

    I also tried adding an even bigger border to see if that would help but it didn't. There's something about the "smallest enclosing disc" that's wrong so I'll start my search there.
    Name:  coll-bad2.png
Views: 10
Size:  67.8 KB

    Edit: Also, my previous post about calculate_convex_hulls() being wrong was incorrect. I thought what it did was break a concave polygon into convex polygons but in reality what it does it create a single convex polygon from the concave one ... so it's behavior is correct. My understanding was wrong.

  10. #10

    Default

    The problem is definitely inside the CL_PointSetMath::calculate_minimum_enclosing_disc( ...) function. I replaced it with a different (non-optimal, from here: http://softsurfer.com/Archive/algori...htm#fastBall()) implementation and the collisions work properly.

  11. #11
    ClanLib Developer
    Join Date
    May 2007
    Posts
    1,824

    Default

    Since you have fixed it, and nobody else understands the existing code.

    I suggest we replace the function, assuming other developers agree.

    Please can we have a patch?

  12. #12

    Default

    I would hold off on replacing it. The implementation I currently replaced it with is fast (O(n)) but again it does not always generate the optimal circle. For example, when generating a circle for the triangle-'sh shape in the testbed, it generates an oversized circle.

    It looks like the current code is either Welzl's algorithm or a variant of it. I'm pretty sure I'll be able to figure out what's going on and either fix it or replace it with another implementation of it. I just need time to really look at it (which I haven't had). If nobody else is running into problems but me, I'd just hold off.

    Though, you are completely welcome to the existing code if you want, it's a direct port of what's on that page I posted above:

    Just replace the body of calculate_minimum_enclosing_disc(...) with this:
    Code:
        // The following is a port of the code listed at http://softsurfer.com/Archive/algorithm_0107/algorithm_0107.htm#fastBall()
        // which falls under the below copyright.
        //
        // Copyright 2001, softSurfer (www.softsurfer.com)
        // This code may be freely used and modified for any purpose
        // providing that this copyright notice is included with it.
        // SoftSurfer makes no warranty for this code, and cannot be held
        // liable for any real or imagined damage resulting from its use.
        // Users of this code must verify correctness for their application.
        CL_Pointf C;
        float rad;
        float rad22;
        float xmin, xmax, ymin, ymax;
        int Pxmin, Pxmax, Pymin, Pymax;
    
        xmin = xmax = points[0].x;
        ymin = ymax = points[0].y;
        Pxmin = Pxmax = Pymin = Pymax = 0;
        for(int i=start+1; i<=end; i++) {
            if(points[i].x < xmin) {
                xmin = points[i].x;
                Pxmin = i;
            }
            else if(points[i].x > xmax) {
                xmax = points[i].x;
                Pxmax = i;
            }
            if(points[i].y < ymin) {
                ymin = points[i].y;
                Pymin = i;
            }
            else if(points[i].y > ymax) {
                ymax = points[i].y;
                Pymax = i;
            }
        }
    
        CL_Pointf dVx = points[Pxmax] - points[Pxmin];
        CL_Pointf dVy = points[Pymax] - points[Pymin];
        float dx2 = dVx.dot(dVx);
        float dy2 = dVy.dot(dVy);
        if(dx2>=dy2) {
            C = points[Pxmin] + (dVx / 2.0f);
            CL_Pointf tmp = points[Pxmax] - C;
            rad22 = tmp.dot(tmp);
        }
        else {
            C = points[Pymin] + (dVy / 2.0f);
            CL_Pointf tmp = points[Pymax] - C;
            rad22 = tmp.dot(tmp);
        }
        rad = sqrtf(rad22);
    
        CL_Pointf dV;
        float dist, dist2;
        for(int i=start; i<=end; i++) {
            dV = points[i] - C;
            dist2 = dV.dot(dV);
            if(dist2<=rad22)
                continue;
            dist = sqrtf(dist2);
            rad = (rad + dist) / 2.0f;
            rad22 = rad * rad;
            C = C + (dV * ((dist-rad)/dist));
        }
    
        smalldisc.position = C;
        smalldisc.radius = rad;

  13. #13
    ClanLib Developer
    Join Date
    May 2007
    Posts
    1,824

    Default

    I have found the bug and fixed it in ClanLib 2.3 SVN

    It will be in the ClanLib 2.3.5 release.

    The CL_PointSetMath::minimum_disc_with_3points() calculation used CL_LineSegment's instead of CL_Line's for interception, thus not working as expected.

    See attached patch
    collision.patch

  14. #14

    Default

    Wow, good find. I definitely would not have found that. I was looking for an algorithmic problem, not the misuse of an API.

Similar Threads

  1. collision points strange problem
    By tet2brick in forum Official ClanLib SDK Forums
    Replies: 4
    Last Post: 01-21-2010, 10:58 AM
  2. I'm getting strange error
    By Homer89 in forum Official ClanLib SDK Forums
    Replies: 2
    Last Post: 05-28-2007, 07:11 PM
  3. Integer strange error (for me)
    By andreaszdw in forum Official ClanLib SDK Forums
    Replies: 0
    Last Post: 04-16-2007, 07:52 PM
  4. Strange scrolling bug in OSX version:
    By whisperstorm in forum Novashell Game Creation System
    Replies: 3
    Last Post: 03-22-2007, 05:20 AM
  5. Strange problems
    By File Sponge in forum Funeral Quest
    Replies: 4
    Last Post: 08-29-2004, 07:16 AM

Bookmarks

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •