Author Topic: SAT / Separating Axis Theorem math: y no werk  (Read 505 times)

ponut64

  • Full Member
  • ***
  • Posts: 175
  • Karma: +13/-0
    • View Profile
SAT / Separating Axis Theorem math: y no werk
« on: March 28, 2018, 02:27:00 am »
I have made 2 versions (well... I broke one as it is saved too late past the conversion process to the other) of some 3D collison/zone detection math using RBB [rotated bounding box] based on the separating axis theorem.

One version uses entirely FIXED data types. It generates non-zero numbers, but there are overflows due to numbers being squared (600 squared, for instance, is beyond the range of FIXED data).

One version (that can compile) I made to combat the overflows is programmed using jo_vectorf and Sint32 values and should make the final conclusion more likely/less buggy (removal of decimal points in end comparison). But there is a problem... all the numbers are zero, and I don't know why. All of the math up to slInnerProduct (replaced with jo_vectorf_dot) and JO_SQUARE (being the overflow area) worked previously, now it doesn't work at all. At some point I had that same math working with jo_vectorf and Sint32 data, but jo_vectorf_dot would not operate since this was a situation in which the vectors were not stored as pointers (and instead "stack variables" or you know, missing the * in jo_vectorf *vector_here_is_pointer_with_star ).

And the other factoid, if I remove the initialization from jo_vectorf structs, it crashes.

Here is the jo_vectorf (float/int) code that I am trying to use:
http://www.mediafire.com/file/q9xmx8cd06c2666/bounder.c

Here, for comparison, is the (broken) more-SGL-reliant code:
http://www.mediafire.com/file/kwbr3kb5xa01u3c/bounder_broke.c

Thank you for reading.
The answer is probably simple. Maybe I am trying to typecast something wrong or am using jo_float2fixed and/or toFIXED improperly.

and here's the entire project
http://www.mediafire.com/file/nypbx88obigj3x7/RTFK.zip


/e: thread has a conclusion
http://www.mediafire.com/file/do4493rxrmyqk59/bounder_share.c
« Last Edit: April 02, 2018, 03:55:59 am by ponut64 »

XL2

  • Sr. Member
  • ****
  • Posts: 341
  • Karma: +72/-1
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #1 on: March 28, 2018, 12:46:12 pm »
SGL is using tables AFAIK for the square root functions , so the cost shouldn't be higher than doing a sin/cos.
Jo Engine also has some tricks to reduce cpu usage.
I don't have time this week to look at your code, but maybe you can try that.

XL2

  • Sr. Member
  • ****
  • Posts: 341
  • Karma: +72/-1
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #2 on: March 28, 2018, 06:35:54 pm »
I just took a short look at your code, and I need to ask : are you trying to build a space rocket?
Just kidding, but seriously you are overcomplicating this.

You can just use a bounding sphere around your objects or an AABB (like for the whole mesh so it's fast).
If you want a per quad collision detection, start with the AABB/sphere detection, then find a point on each quad (a vertices) and use the quad's normal to do an innerproduct (using your position minus the verticle position).
If the result is <= 0, you can check if you are crossing this quad (AABB again should be good enough, just find the minimum and maximum points) and check if you were crossing the quad's plane before updating your position.
It should take around 30 lines of code max and should be way faster than what you are doing.

ponut64

  • Full Member
  • ***
  • Posts: 175
  • Karma: +13/-0
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #3 on: March 28, 2018, 09:14:49 pm »
I am focused on using an arbitrary RBB (rotated bounding box). Not related to the mesh, just calculated. That's in the code, it works just the values are not being changed, but I did not know how to test a point against any 8 points making a rectangle that is rotated in any way.

I don't see how an amalgamation of AABB can achieve precisely what an RBB does.

I know what I am doing is very complicated, probably way more complicated than it needs to be, but I was hoping that I could at least get a non-zero result out of jo_vectorf structs.
Per-quad collision detection is not desired, as that should be in theory more complicated than what I want to do assuming I understood how to simplify what I want to do.

I can't fathom a way to compare a point against 8 other points that make segments that are not axis-aligned... the way I figured that could be done was project all the points on the X, Y, and Z axis vectors of the box, these projections make axis-aligned segments to that particular box (that is rotated), and if the point compared against the box overlaps with the segments then it collides (found by comparing the segments of "player" to "segment max" plus "player" to "segment min" is equal to "segment max" to "segment min".
Obviously the computationally intensive act of projecting what would end up being 16 points to 6 other vectors would be something that would be triggered by an AABB "physics proximity box" to make it faster.

I am not trying to compare if the "player" collides with the "ring". The core idea is if I can compare if the "player" or any given object is in any other given rotated rectangle area.. I'm sure you know that, but I don't see how an amalgamation of AABB can achieve that precisely.

So yes, I am trying to build a space rocket. Working comes first, simplification later. The core issue is why can I not change the value of a jo_vectorf struct. I do not specifically need these structs, as I could just make another function for inner product that does not need said struct, but I'd like to figure out why. and like i said, its probably something more basic about C programming than anything, as I am a newbie.

thanks for reading & replying

« Last Edit: March 28, 2018, 09:22:00 pm by ponut64 »

XL2

  • Sr. Member
  • ****
  • Posts: 341
  • Karma: +72/-1
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #4 on: March 28, 2018, 10:03:09 pm »
I never played with the jo_vectorf, so I couldn't say.
AABB is one cheap way to do general tests, but you can easily do sphere vs sphere tests too.

So to test against rings, you could do something like : test against sphere, which gives you a pretty good idea. Then you test the distance to see if you are crossing the ring's plane  (2x dot products : before updating the player position and after, if signs are different, you crossed the plane). You would just need to calculate the normal vectors, but that's easy : just do a cross product and a distance division to find the normals, which you should do offline or as you load the map.
At the cost of max 2 dot products and sphere calculation, you would get a quite accurate collision detection.
Per quad is easy too, you just need a proper map subdivision (grid, quadtree, octree, kd tree or bsp tree).

ponut64

  • Full Member
  • ***
  • Posts: 175
  • Karma: +13/-0
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #5 on: March 30, 2018, 02:08:26 am »
Well, I would like to update this thread with a working version of the code.

At least mostly working. There are rounding errors, making some angles of the box not detect but that can be solved! and it actually doesn't crash.
http://www.mediafire.com/file/q782jq8campl0ru/bounder_good.c

As pointed out by XL2, is this good? efficient? Nope. but its a proof of concept for the separating axis theorem, at least.

XL2

  • Sr. Member
  • ****
  • Posts: 341
  • Karma: +72/-1
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #6 on: March 30, 2018, 05:17:33 pm »
Yeah, don't worry too much about optimization for now.

That being said, if you need a hand to write another collision detection function, don't hesitate to ask and I'll see what I can do.

ponut64

  • Full Member
  • ***
  • Posts: 175
  • Karma: +13/-0
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #7 on: March 30, 2018, 08:31:33 pm »
I am very thankful you are so willing to help.
If when I chop this down to its barest calculations (that I can fathom) and it still may not perform correctly, and I can't think of another way to do it, I'll be sure to ask.

ponut64

  • Full Member
  • ***
  • Posts: 175
  • Karma: +13/-0
    • View Profile
Re: SAT / Separating Axis Theorem math: y no werk
« Reply #8 on: April 02, 2018, 03:55:46 am »
So here's my conclusion to this thread
http://www.mediafire.com/file/do4493rxrmyqk59/bounder_share.c
Instead of full SAT, or a complete RBB, this just calculates the normals of the RBB and uses a dot product comparison between a point projected onto those axis and the dot product of the axis normal vectors themselves. It appears to produce correct results. Technically this is still working on the separating axis theorem, but is much simplified.

The conclusion: separating axis theorem is a working concept, but too complicated in my case.
If someone does need it for jo engine, a sample is in this thread, that is at least somewhat functional. However my warning is that sample includes many mis-labeled axis and so the physics object rotates a different way from the actual object. On top of being very sloppy.

/e: The more I snoop this stuff, the more errors I find... Heh ...

/e: I really must update this thread *one more time*. You see my previous math had so many problems since I had solved for an XYZ system. Well as you know SGL does not seem consistent in any of its axis systems; mesh rotations are in a ZYX system. There is no easy way to "translate" XYZ to ZYX, so I had to fix that. It was actually pretty easy, having spent way too much time on the trig for XYZ. So here is an updated file. It's a single file but the .h files that go with it are included in text (as im sure you can figure out). I hope no one wasted time on any of the code I have shared.
http://www.mediafire.com/file/nbxpemvrh4c1f78/bounder_final.c

« Last Edit: April 11, 2018, 01:30:53 pm by ponut64 »

 

Sitemap 1 2 3 4 5 6 7 8 9 10 
SMF spam blocked by CleanTalk