# Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

### Dark GDK / Is a point within an object?

Message
Posted: 10th Feb 2012 22:09 Edited at: 10th Feb 2012 22:14
How could I go about finding out if a 3dpoint is withing an object.?

|\
|-\
|--\
|---|
|-.-|
|---|
|--/
|-/
|/

That is a picture of imaginary vertices with a point within them...

I've tryed raycasting from the point to the center of the object, checking to see if it collides with the inside of another object. Mind you my normals are facing inward. This method works unless the objects are like so close that there sides are past the center of the other.
AND I dont need something that only works sometimes you know what I mean.
If your wondering what exactly Im trying to do, then I tell you. BUT you have to ask first ;P
Posted: 10th Feb 2012 22:18
if the object's shape is a cube or a sphere or something you can do it simply by comparing positions and rotations
if it's not, i'm not really sure but you could look it up on google, could be as simple as finding the min/max x/y/z values and then treating it as a cube, depends on the shape itself

Posted: 10th Feb 2012 22:21 Edited at: 11th Feb 2012 00:10
Not all objects are cubes Hassen! This isn't MineCraft!!!

 Looking it up.

Ok I found a bunch of confusing crap about it that I really have attention-span to try to undertand it. So I went and had a smoke to think on it and.. right now my raycast is going from the point to the center of the object that it belong to. But if I change the cast to go from the point to some distance away from the center of the object Im checking it should collide with that objects insides if the point is within otherwise it will never contact that object.
I'll see how that works.
Its more of a fo-check, but i think it'll work.

[after implementation] Yep that seems to work considerably better?

Although this will prolly work well enough for me I think that if someone know a method for accomplishing this then they should post it in the code base.

I found this inside the codebase...
Posted: 11th Feb 2012 02:00 Edited at: 11th Feb 2012 02:01
Quote: "How could I go about finding out if a 3dpoint is withing an object.?"

Procedure:
1. for every poly in an object calculate a plane (from o vertex point and a poly normal)
2. Check if a point is at the same side of all the planes

if it is below the planes the point is inside an object, otherwise it's on outside

Posted: 11th Feb 2012 03:45
@Benjames8
Be sure to use a large, simple polly to do an initial approximation test. Polly collisions are expensive, so only use them if you have a reasonable chance to be colliding with it.

The fastest code is the code never written.
Posted: 11th Feb 2012 07:27
Brendy boy, that method wont work for all objects. Like what if the
object was in an S sorta shape.

___________
________/
_______
____
_
_____
_______
__________
________.__
_________

Imagine the lines are an object and the period its our point, some of the faces
Would be angled away from the point.

I do admit though that the method you mentioned would work with spheres and cubes.

It prolly also could work if you some how discluded those faces
Posted: 11th Feb 2012 14:12 Edited at: 11th Feb 2012 14:15
1) Fire a ray from the point in an arbitrary direction.
2) Count the number of polys it intersects within the object.
-> If the count is even, then the point is outside;
-> else if the count is odd, then the point is inside.

Do a google search for the Jordan Curve Theorem.

Probably not the fastest method but will work every time.

I would try to optimize a bit by checking an axis-aligned-box that contains the object first. If those 6-checks fail, there will be no need to check the unknown number of polys that the object contains...

Regards,
JTK

Edit: Here's a specific link to the algorithm I am talking about above...
Posted: 11th Feb 2012 19:47 Edited at: 11th Feb 2012 20:22
The Jordan Curve Theorem seems really legit and easy to implement, but I can think of one critical issue in using with GDK or sparky's.
And that is you can only check one side of a face.

So another question. Is there a way to check both sides of a face for a collision

btw sorry if I keep shutting everyone down

Here is a post about flipping normals by scaling the objects Y by -100;
http://forum.thegamecreators.com/?m=forum_view&t=166984&b=7

perhaps you could use the Jordan Curve by doing two raycasts, one with the normal object and one with the object scaled. Does anyone concur.

[] I checked and scaling the object does work. although at first I thought it didnt work
Posted: 11th Feb 2012 23:00
I think that maybe you're misunderstanding the ray-poly intersection test.

Unless the test point is actually a part of the poly itself, any ray that's cast and passes through the poly will pass through at exactly one point. There is no distinction between the collision being in front of or behind the poly. Only that it is on the poly.

You can, however, determine which side the originating point is on by using cross-products and dot-products which is what Brendy Boy was suggesting above.

Regards,
JTK
Posted: 11th Feb 2012 23:06
It won't return a collision at all when the ray passes through the back side of the face is what I was saying.
Posted: 12th Feb 2012 03:08
A ray is defined as: R = P + (D * t).

Where:

D = an "arbitrary" direction, and;
t = time.

So, to determine if your ray intersects a poly, do as Brendy Boy says and extend the poly (a triangle defined by points a, b and c) into a plane by calculating the plane's normal value (N):

N = Cross((b-a), (c-a));

Then, using the plane's normal (N), calculate another value for a determinate (d):

d = Dot(N,P);

Note: In some cases, the value of d can be so close to (but not exactly) zero, that you may never really receive a stable value. Instead of using an absolute value of zero for the below tests, most programs (including this example) use an EPSILON value instead, such as:

#define EPSILON 0.0000001f

If (::fabs(d)==EPSILON), then either:

a) No intersection takes place (it's PARALLEL), or;
b) The point (P) already lies within the plane (it's COINCIDENT).

Else if (d<0), then the intersection is from behind the plane.
Else if (d>0), then the intersection is from in front of the plane.

So then, if the result is not EPSILON (neither parallel or coincident), then we can (if we want) determine exactly *where* in the plane the ray collided by calculating the (t) value and adding
it to the ray's origin (P) to create a collision point (C):

t = d / Dot(N,D);

Cx=Px+t;
Cy=Py+t;
Cz=Pz+t;

At this point, we've determined whether or not the ray has intersected the plane that the triangle is extended into; but we do not know if it actually intersects the triangle itself... To do that we must then add up the angles between the three line-segments (a seg b), (b seg c) and (c seg a) that make up the triangle and the point of collision (C):

First: transform/normalize the points around the origin (0,0,0);

Ta=Normalize(C-a);
Tb=Normalize(C-b);
Tc=Normalize(C-c);

Second: Add up all angles (Angle) between the line-segments and the collision point:

Angle = ::acos(Dot(Ta,Tb)) +
::acos(Dot(Tb,Tc)) +
::acos(Dot(Tc,Ta));

Finally, check to see if the angle is equal to 360-degrees (remember from high-school that the sum of all interior angles within a polygon is equal to 360-degrees)...

Note: Again, in some cases, the result may be so close to (but not exacly) zero that you may not always get a stable result when comparing value to zero. And, again we will use an EPSILON value to test against.

If (::fabs(Angle - (2*3.14))<EPSILON) then the ray has hit the poly (triangle);
else the ray missed the poly (triangle).

To satisfy the checks for the Jordan Curve Theorum, if we've hit the poly, we increase a counter.

Once all checks are done, we test to see if the counter is odd or even...

I never said this was an efficient process, only that it works.

For efficiency, I would use an axis-aligned-bounding-box (aabb) around the object in test (is the point within the object) and test the six-planes of the aabb for an odd/even count before even attempting the individual poly(s) of the ojbect.

In short, yes, a collision *can* be detected if the ray is cast from behind the poly; and all of this is explained in the link I posted above as that link points to an "e-book" of sorts (I have the original physical book myself).

I hope this helps,

JTK
Posted: 15th Feb 2012 20:55
how do i get the cross product?
Posted: 15th Feb 2012 21:30
I am wondering what you're working on to actually want to find if a point is within a (possibly complex) object. Why?

I've been reading this for the last few days and trying to figure that question out. Why? (probably a silly question)

The way I'd do it: Using spherical distance checking is very likely the fastest way to check whether a point is within the radius of a sphere. So if you set up numerous sphere zones over an object then this would be the fastest way to do it.

Mental arithmetic? Me? (That's for computers) I can't subtract a fart from a plate of beans!
Warning! May contain Nuts!
Posted: 17th Feb 2012 14:31
There's a whole slew of vector / matrix math stuff with dx9. Just #include <d3dx9math.h> to gain access to them...

An excerpt of what's offered:

Regards,

JTK
Posted: 17th Feb 2012 21:44
I need to check if a point is in a possibly complex object. So I can remove triangles that the point belongs to.
pretty much two objects collide and all the triangles involved with the collision are deleted.
after that I join the two objects together at the empty sides

I have it working pretty good but it's not perfect
I am using this an attempt to make procedurally generated levels

I can figure out if a point is in a complex object, as ive posted. I've just heard a bit about cross product before and when jtk mentioned it I figured I could learn a little.

perhaps I can post a sample later if you'd like
Posted: 18th Feb 2012 15:05 Edited at: 18th Feb 2012 15:09
My recent projects for procedurally generated 3d levels I started out trying to check whether a point was in a polygon, actually within each triangle. It worked to a point but wasn't perfect so I checked out line intersections which where 100% accurate.

In my code I've stored 3 sets of data arrays, vertex table, edge table and triangle table. All I have to do now is to check the intersections between edges only. At the end of the whole generation algorithm the edge table isn't used (only for creating the wall mesh) but it is the most important during the generation.

Once the base map (ie the floor) has been done, it get's tessellated, copied to the roof and the edges are used to create the walls. And using a noise algorithm the floor is turned into a sloping dungeon.

See here on my current progress: http://forum.thegamecreators.com/?m=forum_view&t=193276&b=8

I'm at the stage now where the mesh is being created into separate groups so that rendering can be done quicker by hiding sectiond of the dungeon that are too far away.

This is the current line intersection code I'm using:

Which is better than searching for a point in a triangle or polygon...

EDIT: One thing to note now if you're going down this route that if you are comparing edges with this method then you might find that a newly generated edge's points might just need "nudging" a little. The source to my code is available on the above page if you want to have a look at it to see what I mean...

Mental arithmetic? Me? (That's for computers) I can't subtract a fart from a plate of beans!
Warning! May contain Nuts!
Posted: 28th Feb 2012 01:48 Edited at: 28th Feb 2012 01:48
OK here is a sample of what I'm doing, I've worked out a many a kinks since last I said I would post an example.

I have a new question though.. How can I UV map the new triangles?

The triangles that come from the objects loaded are UV mapped. Perhaps I could use that info to help UV map the new triangles. But the only thing I really know about UV mapping with GDK is its a number between 1 & 0.

#### Attachments

Posted: 28th Feb 2012 02:15 Edited at: 28th Feb 2012 02:30
Just downloaded the project so I'll look at it and re-post here after I've nosed at it.

yes, UV coords do essentially do go from 0.0 to 1.0, but you can also set a UV coord to any value. If your UV coords on a rectangle went from 0.0 to 2.0 then the texture would be tiled twice.

EDIT: Wow, forgot how DX eats my ram on this thing...

After looking at the program and very interesting too, then you have a few options of UV'ing the cave scene:

1. Pinch the UV coords from the objects themselves. You can grab these when you load the object and store them elsewhere temporarily. You will get artifacts appearing when a face collides with another objects face (after CSG'ing). There may be a way around it.

2. Tile the UV coords over the faces. You may need to look into 3d cube mapping coords. At least you will get a reasonably seamless tiling.

3. Youtube has some videos of procedural 3d caves with some excellent texturing. I'm considering emailing one particular guy about how he did it on one of the examples.

Mental arithmetic? Me? (That's for computers) I can't subtract a fart from a plate of beans!
Warning! May contain Nuts!
Posted: 18th Mar 2012 19:02 Edited at: 18th Mar 2012 19:04
So this is how I ended up doing it. The code is simple and so is the mapping but I like simple.

I remember just not being able to figure out how I was going to UV map my caves, it was frustrating.
Then I was remembering what I read in a book,it was that UV goes from 0 to 1. I was also remembering one of WLGfx's posts that talked about the texture repeating or wrapping if you went to 2 or 13.8 or something.
So then while I was at work I was all like duh! I should use coordinates to UV map lol.

 Oh ya I also sped up the generation and fixed some issues with gaps in the walls and such.
Posted: 19th Mar 2012 03:45
It's great when something clicks. Glad to hear you got it working.

Have you thought more about the vertex normals to give the edges a smoother appearance?

Mental arithmetic? Me? (That's for computers) I can't subtract a fart from a plate of beans!
Warning! May contain Nuts!