Sign in to follow this  
perroned

Check if objects intersects between two points?

Recommended Posts

Hi :)
So I have two position vectors, whats the best way to determine if a mesh intersects inbetween the two points. I was getting confused with ray picking so I developed an alternative to get the points, but how can I now check if anything is inbetween the 2 points?
thank you

Share this post


Link to post
Share on other sites
I'll be honest I don't know the math for this. My first tact would be to do a ray-triangle intersection test ( first result on google, maybe not the best source: http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm ) on a bounding box surrounding my meshes and then on every triangle in the mesh when the first check works. There are likely quicker methods and with at least D3DX for Direct3D 9 there is a function just for this ( http://msdn.microsoft.com/en-us/library/bb172882%28v=vs.85%29.aspx ).

In your case you are talking about having a line segment which is basically a ray with an extra condition. I don't see how the math could possibly be easier with a line segment than with a ray but I'm happy to be wrong!

Share this post


Link to post
Share on other sites
nobodynews basically covered it, but it sounds like you're looking for a segment-mesh intersection function.

The first things I'd do would be:

1. Determine if you really need an exact segment-mesh intersection test, or if using a simpler approximating shape would suffice.

2. See if any of the APIs you're using already offer this functionality.

If the answers to the above two questions are 'yes' (you need an exact test) and 'no' (you don't already have the functionality available), then the first thing you'll want to do is early-out if you can based on a simple bounding volume test (e.g. sphere or box - of these, the segment-sphere test is a little easier to implement).

The next issue is numerical robustness. For intersection tests between a linear component and an arbitrary mesh, you have to handle things in a certain way or risk intersections falling 'between the cracks' due to numerical error. This can be done by ensuring that the necessary calculations for each edge are performed in exactly the same way whenever that edge is encountered.

Finally, you'll need to decide if a broad phase is needed, which will depend on the average number of triangles in the mesh and the frequency with which the test is performed. (Whether the mesh deforms at all will also be a factor.) If you need a broad phase and the mesh does not deform, a local-space octree or grid (you could use 3D-DDA with the latter) might be a reasonable choice.

Share this post


Link to post
Share on other sites
[quote name='nobodynews' timestamp='1298265614' post='4776910']
I'll be honest I don't know the math for this. My first tact would be to do a ray-triangle intersection test ( first result on google, maybe not the best source: [url="http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm"]http://www.softsurfe...orithm_0105.htm[/url] ) on a bounding box surrounding my meshes and then on every triangle in the mesh when the first check works. There are likely quicker methods and with at least D3DX for Direct3D 9 there is a function just for this ( [url="http://msdn.microsoft.com/en-us/library/bb172882%28v=vs.85%29.aspx"]http://msdn.microsof...v=vs.85%29.aspx[/url] ).

In your case you are talking about having a line segment which is basically a ray with an extra condition. I don't see how the math could possibly be easier with a line segment than with a ray but I'm happy to be wrong!
[/quote]


Well I tried to use ray picking for a while but was never able to get it. I searched for weeks and posted threads on websites all over for help but was never able to get any help as to get the ray working so I basically did it another way where I just get two points, cuz I was hoping there'd b a simple method for testing it

Share this post


Link to post
Share on other sites
[quote name='jyk' timestamp='1298285735' post='4776980']
nobodynews basically covered it, but it sounds like you're looking for a segment-mesh intersection function.

The first things I'd do would be:

1. Determine if you really need an exact segment-mesh intersection test, or if using a simpler approximating shape would suffice.

2. See if any of the APIs you're using already offer this functionality.

If the answers to the above two questions are 'yes' (you need an exact test) and 'no' (you don't already have the functionality available), then the first thing you'll want to do is early-out if you can based on a simple bounding volume test (e.g. sphere or box - of these, the segment-sphere test is a little easier to implement).

The next issue is numerical robustness. For intersection tests between a linear component and an arbitrary mesh, you have to handle things in a certain way or risk intersections falling 'between the cracks' due to numerical error. This can be done by ensuring that the necessary calculations for each edge are performed in exactly the same way whenever that edge is encountered.

Finally, you'll need to decide if a broad phase is needed, which will depend on the average number of triangles in the mesh and the frequency with which the test is performed. (Whether the mesh deforms at all will also be a factor.) If you need a broad phase and the mesh does not deform, a local-space octree or grid (you could use 3D-DDA with the latter) might be a reasonable choice.
[/quote]

A simple bounding box for my purpose will suffice, I do not need exact precision. And I am using DirectX9 & C++

Share this post


Link to post
Share on other sites
If you use ray picking, you'll end up with an intersection point on the ray somewhere. You can then compare the length from the ray origin to the intersection point to determine if that length falls within the two distances you're interested in - which I think is what nobodynews is suggesting.

In any case, if your ray-picking doesn't work, the most common errors are not setting up the ray origin and direction correctly, or not considering the mesh's world transform in the intersection test.

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298303677' post='4777055']
If you use ray picking, you'll end up with an intersection point on the ray somewhere. You can then compare the length from the ray origin to the intersection point to determine if that length falls within the two distances you're interested in - which I think is what nobodynews is suggesting.

In any case, if your ray-picking doesn't work, the most common errors are not setting up the ray origin and direction correctly, or not considering the mesh's world transform in the intersection test.
[/quote]


Well my problem is getting the direction of the ray. I am using a first person camera with the DXUT class, and I have been trying everything and just cant seem to get the ray to work properly. Because since there is no mouse that you move around in first person, I dont know what I need to change in the formula.

And I know there are very easy intersection functions for a ray and the direction, thats why I wanted to do that, but I was never able to get the ray to work properly

Share this post


Link to post
Share on other sites
It sounds like you're looking to shoot a ray from the eyepoint of the viewer. That's likely just screen center and your "mouse" position would be ( screenWidth/2, screenHeight/2 ). Unproject* the points p0=(mx, my, 0) and p1=(mx, my, 1). The ray position (in world space) is then (after unprojection) p0, and the ray direction is p1-p0 (the difference between unprojected p1 and unprojected p0).

*You can use D3DXVec3Unproject.

Share this post


Link to post
Share on other sites
@The OP: Another option for computing the direction vector for the ray would be to use the forward direction vector of the (uninverted) camera transform.

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298304637' post='4777061']
It sounds like you're looking to shoot a ray from the eyepoint of the viewer. That's likely just screen center and your "mouse" position would be ( screenWidth/2, screenHeight/2 ). Unproject* the points p0=(mx, my, 0) and p1=(mx, my, 1). The ray position (in world space) is then (after unprojection) p0, and the ray direction is p1-p0 (the difference between unprojected p1 and unprojected p0).

*You can use D3DXVec3Unproject.
[/quote]


Everyone kept telling me to go here [url="http://www.toymaker.info/Games/html/picking.html"]http://www.toymaker.info/Games/html/picking.html[/url] but I wasn't sure exactly how to implement it. So are you saying all I would really need would be to do this -> Unproject* the points p0=(mx, my, 0) and p1=(mx, my, 1) , and then I have the ray?

Also could you just clarify the second and third parameters to D3DXVec3Unproject for me please? Im not sure exactly what to pass

and THANKYOU sooo much!! :)

Share this post


Link to post
Share on other sites
[quote]So are you saying all I would really need would be to do this -> Unproject* the points p0=(mx, my, 0) and p1=(mx, my, 1) , and then I have the ray?[/quote]
No, take a look at my post. The ray [b]direction[/b] is p1-p0. That's a necessary step.

In the D3DXVec3Unproject call the 2nd parameter is the input vector (either p0 or p1). You'll make that call twice, once each for p0 and p1.

The 3rd parameter is the current viewport. You can use device->GetViewport(...) to get that parameter.

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298307233' post='4777097']
[quote]So are you saying all I would really need would be to do this -> Unproject* the points p0=(mx, my, 0) and p1=(mx, my, 1) , and then I have the ray?[/quote]
No, take a look at my post. The ray [b]direction[/b] is p1-p0. That's a necessary step.

In the D3DXVec3Unproject call the 2nd parameter is the input vector (either p0 or p1). You'll make that call twice, once each for p0 and p1.

The 3rd parameter is the current viewport. You can use device->GetViewport(...) to get that parameter.
[/quote]

well I am almost done but the 4th parameter is giving me trouble (I think Ive been staring @ it too long and can't recognize it)
I have

[size="2"]D3DXVECTOR3 v;

v.x = [/size][size="2"][color="#0000ff"][size="2"][color="#0000ff"]float[/color][/size][/color][/size][size="2"](pd3dsdBackBuffer->Width /2);

v.y = -([/size][size="2"][color="#0000ff"][size="2"][color="#0000ff"]float[/color][/size][/color][/size][size="2"](pd3dsdBackBuffer->Height /2));

v.z = 1.0f;



[/size][size="2"][color="#0000ff"][size="2"][color="#0000ff"]const[/color][/size][/color][/size][size="2"] D3DXMATRIX* pmatProj = g_Camera.GetProjMatrix();

[/size][size="2"][color="#0000ff"][size="2"][color="#0000ff"]const[/color][/size][/color][/size][size="2"] D3DXMATRIX matView = *g_Camera.GetViewMatrix();

[/size][size="2"][color="#0000ff"][size="2"][color="#0000ff"]const[/color][/size][/color][/size][size="2"] D3DXMATRIX matWorld = *g_Camera.GetWorldMatrix();

D3DVIEWPORT9 tempmatViewPort;

g_pd3dDevice->GetViewport( &tempmatViewPort );

[/size][size="2"][color="#0000ff"][size="2"][color="#0000ff"]const[/color][/size][/color][/size][size="2"] D3DVIEWPORT9 matViewPort = tempmatViewPort;

D3DXVECTOR3 p0, p1;

D3DXVec3Unproject(&p0, &v, &matViewPort, &pmatProj, &matView, &matWorld );

[/size]

But I keep getting
error C2664: 'D3DXVec3Unproject' : cannot convert parameter 4 from 'const D3DXMATRIX **' to 'const D3DXMATRIX *'

Thank you so very much

Share this post


Link to post
Share on other sites
Is there a reason just using the forward direction vector for the camera wouldn't work for you? (It should give you the same results as picking using a point at the center of the screen, and would be a lot more straightforward.)

Share this post


Link to post
Share on other sites
[quote name='jyk' timestamp='1298309282' post='4777110']
Is there a reason just using the forward direction vector for the camera wouldn't work for you? (It should give you the same results as picking using a point at the center of the screen, and would be a lot more straightforward.)
[/quote]


oh, how exactly would I go about doing that? :)

Share this post


Link to post
Share on other sites
[quote name='perroned' timestamp='1298308710' post='4777108']
error C2664: 'D3DXVec3Unproject' : cannot convert parameter 4 from 'const D3DXMATRIX **' to 'const D3DXMATRIX *'
[/quote]

To answer this specific concern: you have a pointer to D3DXMATRIX and you're taking the address of that pointer and passing the result to the function. Just pass the pointer directly.

Share this post


Link to post
Share on other sites
[quote name='nobodynews' timestamp='1298310564' post='4777121']
[quote name='perroned' timestamp='1298308710' post='4777108']
error C2664: 'D3DXVec3Unproject' : cannot convert parameter 4 from 'const D3DXMATRIX **' to 'const D3DXMATRIX *'
[/quote]

To answer this specific concern: you have a pointer to D3DXMATRIX and you're taking the address of that pointer and passing the result to the function. Just pass the pointer directly.
[/quote]


even without the ampersand, it still produces the same error

Share this post


Link to post
Share on other sites
Post your code. It sounds like you may just have a typo. Check everything carefully.

Also, take a closer look at my post about unprojecting p0. You're using v with a z-value of 1, not 0.

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298328652' post='4777269']
Post your code. It sounds like you may just have a typo. Check everything carefully.

Also, take a closer look at my post about unprojecting p0. You're using v with a z-value of 1, not 0.
[/quote]


This is all I have in this function

[code]
HRESULT Pick()
{
HRESULT hr;
D3DXVECTOR3 vPickRayDir;
D3DXVECTOR3 vPickRayOrig;
IDirect3DDevice9* pD3Device = DXUTGetD3D9Device();
const D3DSURFACE_DESC* pd3dsdBackBuffer = DXUTGetD3D9BackBufferSurfaceDesc();

D3DXVECTOR3 v;
v.x = float(pd3dsdBackBuffer->Width /2);
v.y = -(float(pd3dsdBackBuffer->Height /2));
v.z = 0.0f;

const D3DXMATRIX* pmatProj = g_Camera.GetProjMatrix();
const D3DXMATRIX matView = *g_Camera.GetViewMatrix();
const D3DXMATRIX matWorld = *g_Camera.GetWorldMatrix();

D3DVIEWPORT9 tempmatViewPort;
g_pd3dDevice->GetViewport( &tempmatViewPort );
const D3DVIEWPORT9 matViewPort = tempmatViewPort;
D3DXVECTOR3 p0, p1;
D3DXVec3Unproject(&p0, &v, &matViewPort, &pmatProj, &matView, &matWorld ); // here

return S_OK;
}
[/code]

And on the unproject line I get the same error regardless of passing &matView, or *matView or matView.
It says [size="1"]

error C2664: 'D3DXVec3Unproject' : cannot convert parameter 4 from 'const D3DXMATRIX **' to 'const D3DXMATRIX *'[size="1"]

Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast

[size="2"]Thank you once again :)[/size][/size][/size]

Share this post


Link to post
Share on other sites
[quote name='perroned' timestamp='1298336895' post='4777323']
[size="2"][code][size="2"] D3DXVec3Unproject(&p0, &v, &matViewPort, &pmatProj, &matView, &matWorld ); // here
[/size][/code]

And on the unproject line I get the same error regardless of passing &matView, or *matView or matView.
It says [size="1"]

error C2664: 'D3DXVec3Unproject' : cannot convert parameter 4 from 'const D3DXMATRIX **' to 'const D3DXMATRIX *'[size="1"]

Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast
[/size][/size][/size][/quote]
I think you need to work on your counting :) Parameter 4 isn't using matView it is using pmatProj. If you've been modifying matView that is probably why you get the same error.

Share this post


Link to post
Share on other sites
@Buckeye @nobodynews thankyou you both
I thot the parameters were like parameter 0, 1, 2, 3, 4 not 1, 2, 3, 4

So yes I fixed that :)

So I unprojected p1 as well after changing v.z to one, then did the subtraction like you said
So is this correct?

[code]D3DXVECTOR3 v;
v.x = float(pd3dsdBackBuffer->Width /2);
v.y = -(float(pd3dsdBackBuffer->Height /2));
v.z = 0.0f;

const D3DXMATRIX* pmatProj = g_Camera.GetProjMatrix();
const D3DXMATRIX matView = *g_Camera.GetViewMatrix();
const D3DXMATRIX matWorld = *g_Camera.GetWorldMatrix();
D3DVIEWPORT9 tempmatViewPort;
g_pd3dDevice->GetViewport( &tempmatViewPort );
const D3DVIEWPORT9 matViewPort = tempmatViewPort;
D3DXVECTOR3 p0, p1;
D3DXVec3Unproject(&p0, &v, &matViewPort, pmatProj, &matView, &matWorld );// origin

v.z = 1.0f;
D3DXVec3Unproject(&p1, &v, &matViewPort, pmatProj, &matView, &matWorld );// direction

p1 -= p0;
[/code][size="2"]

Thank you all very much :)

[/size]

Share this post


Link to post
Share on other sites
Looks good. If you want to double check (and give yourself some headaches), you can use D3DXVec3Project() to convert p0 back to screen space and check that it matches ( width/2, height/2, 0 ).

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298344334' post='4777360']
Looks good. If you want to double check (and give yourself some headaches), you can use D3DXVec3Project() to convert p0 back to screen space and check that it matches ( width/2, height/2, 0 ).
[/quote]


Well I projected like u said, and have a small headache :P

p0.x equals 633867
and
p0.y equals 356376

while
pd3dsdBackBuffer->Width equals 1366
and
pd3dsdBackBuffer->Height equals 768

And
1366/2 = 683
768/2 = 384

So i guess because they are floating points with numerous digits, is 633 == 683, and 384 == 356 close enough? Like should they be EXACTLY the same or is this normal? :)

Share this post


Link to post
Share on other sites
While it's true that:
1366/2 = 683
768/2 = 384

683 certainly does [i]not[/i] equal 633867. Did you forget a decimal point?

Your projected values immediately obtained from the unprojected values should be nearly identical. No, 633 is not nearly close enough to 683. If you get 683.001 or something similar, that's close.

You should be able to do something like:

[code]
D3DXVec3Unproject( &p0, &v, ...parameters...);
D3DXVECTOR3 vreturn;
D3DXVec3Project( &vreturn, &p0, ... SAME parameters..);
[/code]

vreturn and v should be within fractions of a decimal point.

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298346966' post='4777372']
While it's true that:
1366/2 = 683
768/2 = 384

683 certainly does [i]not[/i] equal 633867. Did you forget a decimal point?

Your projected values immediately obtained from the unprojected values should be nearly identical. No, 633 is not nearly close enough to 683. If you get 683.001 or something similar, that's close.

You should be able to do something like:

[code]
D3DXVec3Unproject( &p0, &v, ...parameters...);
D3DXVECTOR3 vreturn;
D3DXVec3Project( &vreturn, &p0, ... SAME parameters..);
[/code]

vreturn and v should be within fractions of a decimal point.
[/quote]

ok thankyou so I tested the code you wrote and yes they match exactly :)

So I just have one last question :P
So with this ray if I was going to test it against a bounding box would I just do it like this:
[size="2"][color="#0000ff"][size="2"][color="#0000ff"][color="#000000"](Assuming vMin [/color][color="#000000"]and vMax are already filled out)[/color][/color][/size][/color][/size][size="2"]
[size="2"][/size]D3DXBoxBoundProbe( &vMin, &vMax, &p0, &p1 )

[/size]Thankyou once again for all you help. Much appreciated :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this