Pages: 1 [2] 3
  Print  
Author Topic: Chesee finder - pathfinding and collision engine  (Read 11715 times)
Offline (Unknown gender) The 11th plague of Egypt
Reply #15 Posted on: September 25, 2010, 12:59:01 PM
Member
Joined: Dec 2009
Posts: 285

View Profile
The only script I really need is one that returns the distance of a segment from triangle, in 3d. If there is an intersection, I need it to return 0.

The other script, the one that returns the z of a x-y point inside the triangle is also necessary, but should be much easier to retrieve.

I would like it to work with GM too, but so far I have found nothing useful, be it C++ or GML.

If somebody can solve my problem I can buy him/her a Steam game. I'm tired of waiting, I'll have to learn C++ later this year at my university, but right now I want to finish this.

EDIT: maybe I got a chance. Here is a simple code that can account for ray/segment collisions with a triangle. If there is no intersection, then I suppose that the segment-triangle distance is the smallest distance between the segment the 3 sides of the triangle. On the same site, I also found some code that can do that.

I think I can convert this script by myself. There are custom types defined in order to use custom operations, but there's hope.
But I still another script to calculate the distance between 2 segments, and I can't find any straightforward code.
« Last Edit: September 26, 2010, 04:21:29 AM by The 11th plague of Egypt » Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #16 Posted on: September 27, 2010, 03:52:22 PM
Member
Joined: Dec 2009
Posts: 285

View Profile
News. I converted a 3d C++ function to find the distance between 2 segments into a GML script. Here's an example, this thing can recognized intersections too!

I'm now trying to convert another function from the same site, but i got stuck because of a vectorial cross product.

If I have 2 vectors, u(u_x1,u_y1,u_z1,u_x2,u_y2,u_z2) and v(v_x1,v_y1,v_z1,v_x2,v_y2,v_z2), how do I calculate the vector w = u x v ?

w must perpendicular to both u and w, that's all I know
Logged
Offline (Unknown gender) luiscubal
Reply #17 Posted on: September 27, 2010, 04:49:13 PM
Member
Joined: Jun 2009
Posts: 452

View Profile Email
w = u x v is pretty easy. There's a formula for that.

| i j k |
| ux uy uz |
| vx vy vz |

=

(uy * vz - uz * vy, vx * uz - ux * vz, ux * vy - vx * uy)

At least if I remember properly

I have no idea why your vectors have 6 dimensions. Be aware that this formula only works for 3D vectors.
Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #18 Posted on: September 27, 2010, 05:52:38 PM
Member
Joined: Dec 2009
Posts: 285

View Profile
Thank you. My vectors have 3 dimensions, I build them from the segments.

Your formula is correct, I found a similar one here

However, I can't get the code to work. No errors, it just returns nonsense. I think I translated the code correctly...

example here
« Last Edit: September 27, 2010, 05:58:28 PM by The 11th plague of Egypt » Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #19 Posted on: October 07, 2010, 12:00:07 PM
Member
Joined: Dec 2009
Posts: 285

View Profile
I hired a C++ coder to make the functions I needed, we are testing it out now. Probably it's easier (and better) to make a .dll out of it instead of converting the code to GML.

Anybody wants to help?
Logged
Offline (Male) Josh @ Dreamland
Reply #20 Posted on: October 07, 2010, 08:02:04 PM

Prince of all Goldfish
Developer
Location: Ohio, United States
Joined: Feb 2008
Posts: 2946

View Profile Email
*shudder*
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) retep998
Reply #21 Posted on: October 08, 2010, 01:13:24 AM

Member
Location: Where else?
Joined: Jan 2010
Posts: 248
MSN Messenger - retep998@charter.net AOL Instant Messenger - retep998 Yahoo Instant Messenger - retep998
View Profile Email
 :eng101: :eng99:
Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #22 Posted on: October 08, 2010, 06:18:21 AM
Member
Joined: Dec 2009
Posts: 285

View Profile
Com'on, I'm doing this for the community and I'll release the code as open source. The dll could have a MIT license, if you don't like GPL.

Well, I now have a complete C++ CodeBlocks project, and I need to make a dll out of it, so I can use it with Game Maker too.

Anybody knows how to make a Game Maker dlls? Is that any different from making a dll for another program?

The GMC dll topic sucks. It's full of C++ tutorials, and i can't find any useful information.
Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #23 Posted on: October 08, 2010, 07:17:51 AM
Member
Joined: Dec 2009
Posts: 285

View Profile
Thank you. I already have a topic on the GMC. Nobody answered.

Seems it's like writing a common dll, for that matter.
« Last Edit: October 08, 2010, 07:21:01 AM by The 11th plague of Egypt » Logged
Offline (Female) IsmAvatar
Reply #24 Posted on: October 08, 2010, 12:49:31 PM

LateralGM Developer
LGM Developer
Location: Pennsylvania/USA
Joined: Apr 2008
Posts: 891

View Profile Email
... try knocking up Icuurd ..., if he's free he'll probably sort you out ;)

 :eng99:
Logged
Offline (Male) Josh @ Dreamland
Reply #25 Posted on: October 08, 2010, 05:26:19 PM

Prince of all Goldfish
Developer
Location: Ohio, United States
Joined: Feb 2008
Posts: 2946

View Profile Email
Chances are, the programmer you hired doesn't specialize in geometry. I can write a set of shitty polygon collision functions for free.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) The 11th plague of Egypt
Reply #26 Posted on: October 09, 2010, 04:54:47 AM
Member
Joined: Dec 2009
Posts: 285

View Profile
I was thinking about hiring him again to do the dll part, but yeah, it took him too much time.

Here is the work he did, I'd like a judgement on efficiency.
There are:
1) a function to measure the distance from a 3d segment to a 3d planar convex, and return the closest points if there is no intersection
2) a function to return the z value of a x-y point of the convex

I could open a new job so you can participate. Here are my needs

- function 1) should return only one thing, a number representing
-- if there is an intersection, the distance from the first point of the segment to the intersection point
-- if there isn't, the distance from the first point of the segment and closest point of the convex polygon

- a function to measure the distance between 2 segments, which returns a number representing
-- if there is an intersection, the distance from the first point of the first segment to the intersection point
-- if there isn't, the distance from the first point of the first segment and the closest point of the second segment

- a function that, given a 3d point and a 3d planar convex, returns
-- if the point is above the convex or part of it, the distance from the convex
-- if the point is under the convex and not part of it, the distance from the convex as a negative value

- a function that, given a 3d point and a 3d planar convex, returns the x-y direction to take to get away from the convex as fast as possible

- take all the above functions and make a Game Maker compatible dll out of it (it has to return doubles)

- a GML function that, given the first point of a segment and a distance, returns the point of the segment with that distance from the first point

It's a lot of things, and I don't have much money nor a lot of time, but I hope we can make a deal.
« Last Edit: October 09, 2010, 05:05:16 AM by The 11th plague of Egypt » Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #27 Posted on: October 09, 2010, 08:24:55 AM
Member
Joined: Dec 2009
Posts: 285

View Profile
New project opened. Max bid is 25$, if you want to participate, I'll give you the link.

I wonder if I could implement some sort of 3d triangulation too...
« Last Edit: October 09, 2010, 08:52:29 AM by The 11th plague of Egypt » Logged
Offline (Female) serprex
Reply #28 Posted on: October 09, 2010, 11:19:32 PM
Smooth ER
Developer
Joined: Apr 2008
Posts: 106

View Profile WWW
segment_triangle.cpp: http://en.wikipedia.org/wiki/Fast_inverse_square_root
Code: [Select]
inline void normalize(float* x)
{
float len = 1.0f / sqrtf(dot_product(x, x));
x[0] *= len;
x[1] *= len;
x[2] *= len;
}
He's using inline, so that should deal with aliasing

What's the data set? If you don't have too many values, consider using doubles. If you're alright having 25% useless data thrashing your cache, consider adjusting vectors to be float[4] so to allow for tree vectorization and other such power of two goodness

get_z:
Code: [Select]
if( fabsf(normal[2]) < FUZZY_ZERO )
return 0.0f; // that means that the triangle is parallel to the Z axis (we cannot retrieve a Z value from X and Y)
// Now, the plane equation is A1*x + B1*y + C1*z + D1 = 0
// solving for "z" yields:
// z = -(A1*x + B1*y + D1) / C1
return (normal[0]*x + normal[1]*y - dot_product(normal, va)) / -normal[2];
This is a little epsilon trigger happy. Better would be to check if it is exactly 0, otherwise let the processor give you the nearly zero value (Unless you're using zero as a signal value?). Another case of overly eager number fudging is in line_segment, where if( det > FUZZY_ZERO ) is better stated as a check on whether a01 is near 1

If you're going to use FUZZY_ZERO, consider using -ffast-math
« Last Edit: October 09, 2010, 11:39:26 PM by serprex » Logged
Offline (Unknown gender) The 11th plague of Egypt
Reply #29 Posted on: October 10, 2010, 05:20:42 AM
Member
Joined: Dec 2009
Posts: 285

View Profile
Hey, thanks for the feedback!

I'll notify him. He's now working on adding the other functions and making a dll as well.

He said he already worked on dll making, so he'll make a dll that works with other languages, but i have to test the Game Maker side.

Is a Game Maker dll really that different from any other dll, except for the "doubles only" thing?
Logged
Pages: 1 [2] 3
  Print