Sign in to follow this  

Problems with Picking (Ray intersection)

This topic is 4727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm trying to create a Dungeon-Keeper like game in C++ and DirectX. I have a map created of meshes loaded from x-files, each 20*20 pixels. To save memory, I have only loaded each of these meshes once, and my render function calls "DrawSubset()" on the relevent mesh, decided via a switch statement. Nothing keeps a handle on the meshes as they are rendered, as all the 2D arrays I tried to create of ID3DXMesh* caused errors when I tried to run the program (although compiled fine). All the above is largely irrelevent, all I need (absolutely desperately, this is my final year, 30 credit project for Uni!) is a picking algorithm that A> deals with squares not spheres and B> Deals with [u]multiple[/u] objects, preferabally at render time. Once I have this, I can adapt it to suit my nefarious purposes... I looked 4 pages deep on this forum, didn't see anything ("Search is temporarily disabled") and all the other resources I have found deal in bounding spheres. I can provide any bits of code anyone may want / screenshots as required. Very very grateful for any help anyone can offer me, Darker_Rage

Share this post


Link to post
Share on other sites
Unfortunately, I did :-S The stuff I turned up is next to useless to me.

At render time, the program selects from one of 3 ID3DXMesh* to render, renders one and moves 20 pixels on, then repeats. After 50 have been rendered, it moves 20 to the right and back to the beginning, then continues. It doesn't render from a 2D array, because I get exceptions whenever I try to write to the array. This means that there are no handles on the 1000 meshes that have been rendered.

All the algorithms I found select a single mesh, and only a single mesh is rendered. Any algorithm I use needs to select a single mesh from 1000 rendered

Share this post


Link to post
Share on other sites
Quote:
Original post by Darker_Rage
At render time, the program selects from one of 3 ID3DXMesh* to render, renders one and moves 20 pixels on, then repeats. After 50 have been rendered, it moves 20 to the right and back to the beginning, then continues. It doesn't render from a 2D array, because I get exceptions whenever I try to write to the array. This means that there are no handles on the 1000 meshes that have been rendered.

I didn't understand anything. But, getting exceptions on writing to an array means you've been doing something wrong.

Quote:
All the algorithms I found select a single mesh, and only a single mesh is rendered. Any algorithm I use needs to select a single mesh from 1000 rendered

You have a 'basic' building-block algorithm that checks for ray-AABB intersection. Run it on the 1000 meshes, and you'll get the selected meshes. Or am I misunderstanding something here?

Did you mean you want to drag a rectangle (RTS style) and pick the meshes it covers?

Share this post


Link to post
Share on other sites
Quote:

You have a 'basic' building-block algorithm that checks for ray-AABB intersection. Run it on the 1000 meshes, and you'll get the selected meshes. Or am I misunderstanding something here?

Yeah, I agree with Coder.

Have you looked at the DirectX PickMesh sample? I don't think it is in the latest SDKs unfortunately. I use managed DX, but try something like the D3DXPickMesh function.

Hope that helps,

Share this post


Link to post
Share on other sites
Hookay, i'm confusing myself now :S I'm going to try and ASCII what i'm doing... My ASCII art sux a bit, so please bear with me. [] represents a tile, the number represents what it is a tile of

[1][1][1][1][1][1][1][1][1][1]
[1][1][1][1][1][1][1][1][1][1]
[1][1][1][1][1][1][1][1][1][1]
[1][1][1][2][2][2][2][2][1][1]
[1][1][1][2][3][3][3][2][1][1]
[1][1][1][2][3][3][3][2][1][1]
[1][1][1][2][2][2][2][2][1][1]
[1][1][1][1][1][1][1][1][1][1]
[1][1][1][1][1][1][1][1][1][1]
[1][1][1][1][1][1][1][1][1][1]

I have a 2D array storing those numbers, just as ints. A switch statement in my "render" function reads the number at [x][y] and renders the mesh that corresponds to that number.

Quote:
You have a 'basic' building-block algorithm that checks for ray-AABB intersection. Run it on the 1000 meshes, and you'll get the selected meshes. Or am I misunderstanding something here?


There is NOTHING that keeps track of the meshes once they are rendered. Anything I try to make to do this takes the form of a 2D array, and always generates
"Unhandled exception at 0x0011fc98 in Damien.exe:
0xC0000005: Access violation reading location 0x0011fc98."

no matter what I try (i've made the array bigger, changed the number being fed to the statement that puts the meshes into the array, all for naught). The errors show up in the most bizarre places when I debug however, usually in the font code.

I have just managed to get the program so that it changes a random, single block of type [1] to type [2], where before the best I had managed was to make _everything_ change. All I _think_ I need now is a way to store a 2D array of ID3DXMesh* without causing exceptions.

Still very grateful for any help anyone can offer, and for that that which has already been offered, Darker_Rage

Share this post


Link to post
Share on other sites
Quote:
There is NOTHING that keeps track of the meshes once they are rendered. Anything I try to make to do this takes the form of a 2D array, and always generates
"Unhandled exception at 0x0011fc98 in Damien.exe:
0xC0000005: Access violation reading location 0x0011fc98."

no matter what I try (i've made the array bigger, changed the number being fed to the statement that puts the meshes into the array, all for naught). The errors show up in the most bizarre places when I debug however, usually in the font code.

Well, that indicates you've been writing/reading incorrectly to/from the array. If you still have the old code, you can post it to find out what's wrong.

Anyway, now I understand the problem. One way to solve it, given the ray:

For every tile in your grid:
Based on tile type, construct AABB
Translate AABB based on tile position
Intersect AABB with ray


However, this is horribly inefficient. A better way to do it would be to use a quad-tree whose leaves are the tiles. You intersect the ray with the 4-top level AABBs (quads), and this saves you 3/4 of the intersection checks. Then do the same for the 4 children of the intersected top-level AABB, and so on, until you reach a leaf - that's your tile.

Share this post


Link to post
Share on other sites
I _think_ that's what i've managed to achieve last night. Now, on left mouse click, a single tile changes, rather than the whole map, but it seems to be completely random. Anyway, here's the array code:

int const static X_VALUE = 50; //The maps X axis
int const static Y_VALUE = 50; //The maps Y axis

ID3DXMesh* meshes[X_VALUE][Y_VALUE];

ID3DXMesh* MR = 0;
std::vector<D3DMATERIAL9> MRMtrls(0);
std::vector<IDirect3DTexture9*> MRTextures(0);

//code to load MR, materials and textures from x-file

for(int i=0; i<=X_VALUE; i++)
{
for(int j=0; j<=Y_VALUE; j++)
{
switch (tracker.getCompAt(i,j)) //Returns what type of tile belongs at [i][j]
{
case 0:
meshes[i][j] = MR;
break;
//Other identical cases for other tile types
}
}
}

Now to go look up quad trees.... Thanks again for any help you can offer!

Share this post


Link to post
Share on other sites
Berrrr.... and i've been coding for nigh on 6 years! And I didn't spot that.

OK, i've put a workaround in place now for that problem. However, I'm still in trouble. As the meshes in my newly created 2D array are all identical, I can't use the D3DXIntersect macro (it always chooses the tile at 0,0 in the array, although it's stopped picking ones at random now).

I am using this code:


struct BoundingBox
{
BoundingBox();
D3DXVECTOR3 min;
D3DXVECTOR3 max;

bool intersect(const Ray &) const;
};

BoundingBox* MRBB; //will not compile if declared any other way, errors at
//MRBB->min and MRBB->max

if( d3d::gDInput->mouseButtonDown(0))
{
ray = CalcPickingRay((int)d3d::gDInput->mouseDX(), (int)d3d::gDInput->mouseDY());
D3DXMATRIX v;
d3d::gd3dDevice->GetTransform(D3DTS_VIEW, &v);

D3DXMATRIX viewInverse;
D3DXMatrixInverse(&viewInverse, 0 , &v);
TransformRay(&ray, &viewInverse);

for(int i=0; i<X_VALUE; i++)
{
for(int j=0; j<Y_VALUE; j++)
{
D3DXVECTOR3* raf; //Should be BYTE *, but fails

MR->LockVertexBuffer(0,(void**)&raf);
HRESULT hr = D3DXComputeBoundingBox(
raf, //Should be(D3DXVECTOR3*)raf
MR->GetNumVertices(),
D3DXGetFVFVertexSize(MR->GetFVF()),
&MRBB->min,
&MRBB->max);
MR->UnlockVertexBuffer();
if(FAILED(hr))
{
::MessageBox(0, "Twatit", 0,0);
}
}
}
}




I'll leave off listing the CalcPickingRay and TransformRay methods for now. The problem is that the HRESULT from D3DXComputeBoundingBox is always fail (at least, that's what the message box says). No bounding box means no using the shiny Intersect method on my ray :-(

Help is appreciated, as ever! Darker_Rage

EDITED to change the "should be's"

Edited by Coder: source tags. Check GDNet Forums FAQ

[Edited by - Coder on January 4, 2005 3:49:31 AM]

Share this post


Link to post
Share on other sites
ok, using DXTRACE_ERR_MSGBOX I get this:

File:
Line: 681
Error code: D3DERR_INVALIDCALL(0x8876086c)
Calling: Funciton failed:
Do you want to debug the program.

If I hit "yes" I get:

Unhandled exception at 0x77f767cd in Damien.exe: User breakpoint.
followed closely by: There is no source code for the current location.

In the output section, the error is:
Direct3D9: (ERROR) :GetTransform does not work in pure-device

Sooo... the question probably is now how do I not use pure-device :-S except I don't even know what that means!!

EDITED TO ADD:

I also get this:
c:\documents and settings\darker rage\my documents\visual studio projects\damien\damien\dicamera.cpp(681): function failed: hr=D3DERR_INVALIDCALL (0x8876086c)
D3DX: D3DXComputeBoundingBox: NULL min output parameter

Thanks again for help, especially that last bit (didn't know the usage of my debugger at all!)

Share this post


Link to post
Share on other sites
IIRC pure devices do T&L in hardware, thus D3D doesn't have access to the world transformation matrix. Change your device creation code to use hardware vertex processing instead. Look up your CreateDevice code and check which vertex-processing flag you use.
[edit]
The last one is simple to solve - just provide all necessary parameters and double check whether they are NULL (e.g. set a break-point and look up the parameter values in the debug window).
[/edit]

Share this post


Link to post
Share on other sites
Ach! Sorry to keep on with the same problem yet again...

You said earlier that I needed to:
For every tile in your grid:
Based on tile type, construct AABB
Translate AABB based on tile position
Intersect AABB with ray

I am doing this. I am calculating and transforming the pick ray by robbing the code from Microsoft's Pick sample (from the old SDKs). I am using this code to check for intersection:



D3DXMATRIXA16 matProj;
d3d::gd3dDevice->GetTransform( D3DTS_PROJECTION, &matProj );

POINT ptCursor;
GetCursorPos( &ptCursor );
ScreenToClient( d3d::ghMainWnd, &ptCursor );

// Compute the vector of the pick ray in screen space
D3DXVECTOR3 v;
v.x = ( ( ( 2.0f * ptCursor.x ) / d3d::gd3dPP.BackBufferWidth ) - 1 ) / matProj._11;
v.y = -( ( ( 2.0f * ptCursor.y ) / gd3dPP.BackBufferHeight ) - 1 ) / matProj._22;
v.z = 1.0f;

// Get the inverse of the composite view and world matrix
D3DXMATRIXA16 matView, matWorld, m;
d3d::gd3dDevice->GetTransform( D3DTS_VIEW, &matView );
d3d::gd3dDevice->GetTransform( D3DTS_WORLD, &matWorld );

m = matWorld * matView;
D3DXMatrixInverse( &m, NULL, &m );

// Transform the screen space pick ray into 3D space
ray.origin.x = v.x*m._11 + v.y*m._21 + v.z*m._31;
ray.origin.y = v.x*m._12 + v.y*m._22 + v.z*m._32;
ray.origin.z = v.x*m._13 + v.y*m._23 + v.z*m._33;
ray.direction.x = m._41;
ray.direction.y = m._42;
ray.direction.z = m._43;
for(int i=0; i<X_VALUE; i++)
{
for(int j=0; j<Y_VALUE; j++)
{
D3DXVECTOR3* raf;

meshes[i][j]->LockVertexBuffer(0,(void**)&raf);
HRESULT hr = D3DXComputeBoundingBox(
raf,
meshes[i][j]->GetNumVertices(),
D3DXGetFVFVertexSize(meshes[i][j]->GetFVF()),
&MRBBmin,
&MRBBmax);
MR->UnlockVertexBuffer();
//DXTRACE_ERR_MSGBOX("function failed:", hr);
if(FAILED(hr))
{
::MessageBox(0, "Twat",0,0);
}
if(Intersect(ray, MRBBmin, MRBBmax))
{
tracker.setComp(i,j,2);
return 0;
}


If I leave the "return 0" statement, only the first tile (at 0,0 in my array of ID3DXMesh*) is changed in the tracker array (which the render funcion gets it's information from) regardless of where I click on the screen. If I add these two statements:

map[i][j] = 2; //map is the workaround for errors earlier, and ixj int array
meshes[i][j] = FN; //FN is the mesh that i'm trying to change things to, meshes is an ixj array of ID3DXMesh*

The first tile in the array turns briefly to an FN then deletes its self.

If I comment out the "return 0," whatever was happening to the first tile happens to every tile on the grid

Edited by Coder: Source tags: [source]code[/source] [smile]

[Edited by - Coder on January 4, 2005 1:54:39 PM]

Share this post


Link to post
Share on other sites

This topic is 4727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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