Picking

paycheck · **Joined:** Wed Nov 10, 2010 7:15 pm **Posts:** 43

I wanted to try something of a hybrid, but I'm not exactly sure how to start. Let me explain my idea and if anyone has an idea of how to implement it, please let me know.

I wanted to color the cubes based on their x,y,z location in the world in relation to the camera (but before perspective I think?) Anyways, then I wanted to be able to calculate how far that color is from the user and use that as the index to retrieve the correct block. Something like:

Code:

//use trig to figure out from the direction you were facing how much red/green/blue is in x, y, z and then:
block[cur + intensityInX][cur + intensityInY][cur + intensityInZ]

would be the selected block. I'm not sure if this is possible, (I can't seem to figure out how to make world coordinates into colors anyway, I thought it would be as simple as just dividing by the maximum select range and throwing everything else away... but this approach didn't seem to work.) But I think this would be my ideal solution because it would be pixel perfect, would take less than 1 normal frame to compute (because I would only draw local chunks, not the distant ones) and I wouldn't have to worry about ray tracing through 2 separate chunks (which may not be as difficult as it sounds).

If anyone DOES have picking done, please let me know and show me how (if you don't mind) and maybe I'll just implement that. Anyways, yea, I'm going to keep trying different things for awhile

EDIT: The reason I want to try my hybrid is because it would use absolutely NO additional memory, and would be pixel accurate, and could be scaled to a fair size distance I think (even if it was only 80-100 cubelengths deep, that would still be pretty dang far).

EDIT2: I think it is doable. I could use some help figuring out which points to take the distance between. I'm trying to figure out the vertex's position in relation to the camera. I'm pretty sure all of this can be done in the vertex program. The one crappy thing about this approach is that since you can see up to 3 faces of a cube, and each face has 2 triangles, 6 colors could map to 1 cube, but in the end that isn't really a big deal, and I can worry about it later. Anyways yea, if anyone knows how to calculate distance from camera in the vertex program, that would be awesome.

My test code right now (it doesn't work, it is always red)

Code:

outColor = float4(1,0,0,1);
   if(distance(cameraPos, outWorldPosition) > 10){
      outColor = float4(0,1,0,1);
   } 

beyzend · **Joined:** Sat Sep 18, 2010 9:45 pm **Posts:** 189

Only problem I have with color picking is what to do if you want to support a number of pickings, say with multiple entities in your world that needs to do picking, for example. Can you still use color picking in that use case? Of course, you may get around this if you put in some limits to number of picks. For networking for example, you could get the client to send in their picked selection and then process them on the server. It's doable but you will need to code around the problems.

What I *plan* to do is still try using Ogre's WorkQueue system. So I would create a channel, then for anyone that wants picking, they send a task to this queue, which then proceeds to work on this task. Eventually when it's complete, it will "call back" with the selection. From that point you can then process this selection, modify terrain for example (another task). Right now it's just going to use my delegate system for call-backs, but in the future I will use lock-free queues for communication. So I can create and handle response in different threads. I just thought this up a min ago so I don't know whether it will work or not. One problem I see is I need to do some mutexing with the Volume. Another possibility is to queue up pickings and process them in one fell swoop.

Edit: Oh btw, each selection task will walk a number of steps, then query the Volume for those points. Then walk more steps, then query. So I'm querying the Volume in an interleaved manner. Or if this is a bad idea then just don't do that...which means I will be limited...but I will be limited anyhow so who cares.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

@paycheck:

You have the right idea in priciple - here's a few things to keep in mind:

1) In Ogre you can obtain the camera position with the camera_position property in your material/program.

2) You already have the world space position as you are using it in the fragment shader code which computes the normal.

3) You will need to allow for any transformations you have performed on the mesh. I think you were scaling your ManualObject by some amount?

4) You should compute the colour per-fragment rather than per-vertex. Vertices are shared between cubes, and there are several for each cube. It doesn't make sense to do the colour per-vertex. You want the whole cube to be the same colour

5) Fragment world space positions are always ending with '.5'. You need to work out which integer position this corresponds to (i.e. the actual voxel position). You will probably want to take acount of the normal to do this.

Probably some other stuff... Start by just colouring the mesh besed on it's position in world space. Then worry about the camera. Then take it from there.

On the other hand, if you want to use the raycasting approach then here is the relevant code from Thermite. You'll need to adapt it but it's a start:

Code:

QVector3D Volume::getRayVolumeIntersection(QVector3D rayOrigin, const QVector3D& rayDir)
   {
      //Initialise to failure
      /*std::pair<bool, QVector3D> result;
      result.first = false;
      result.second = QVector3D(0,0,0);*/

      QVector3D result = QVector3D(0,0,0);

      //Ensure the voume is valid
      PolyVox::Volume<Material8>* pVolume = m_pPolyVoxVolume;
      if(pVolume == 0)
      {
         return result;
      }

      Ogre::Real dist = 0.0f;
      for(int steps = 0; steps < 1000; steps++)
      {
         //Ogre::Vector3 point = ray.getPoint(dist);
         //PolyVox::Vector3DUint16 v3dPoint = PolyVox::Vector3DUint16(point.x + 0.5, point.y + 0.5, point.z + 0.5);
         rayOrigin += rayDir.normalized();

         if(pVolume->getVoxelAt(rayOrigin.x(), rayOrigin.y(), rayOrigin.z()).getMaterial() > 0)
         {
            result = rayOrigin;
            return result;
         }

         dist += 1.0f;         
      }

      return result;
   }

[Edit:] I should point out that this isn't really pixel accurate, but I believe it could be made so with a little work.

beyzend · **Joined:** Sat Sep 18, 2010 9:45 pm **Posts:** 189

Oh wait...NVM. I will try just picking the mesh (since I will be using a physics engine anyway). It's pretty simple converting from the picked position into volume position, I think.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

beyzend wrote:

Oh wait...NVM. I will try just picking the mesh (since I will be using a physics engine anyway). It's pretty simple converting from the picked position into volume position, I think.

I think that's also fine. In the Thermite physics demo all the collision is being done directly against the mesh and it seems pretty fast. My volume was much smaller, but on the other hand you have your face merging available.

paycheck · **Joined:** Wed Nov 10, 2010 7:15 pm **Posts:** 43

@David, thank you! There is a lot of stuff in there that I can try out, especially I didn't know that the world position is .5 at the fragment level, that is awesome (I think for me it will be multiples of 8 since I scale by 16)

I seriously hate that there is absolutely no way for me to figure out what is wrong with my CG programs. The only way I know it is totally broken is if it is all white, but if it compiles, that does not mean that it works as intended, and figuring out what values are where and why they aren't doing what I want them to is seriously fking tiring... makes me get derailed so much faster - but I need picking to work before I can add anything to a real game, so it's pretty much a must have.

right now I'm, trying to just color on the distance and that doesn't even work....

EDIT: I tried some new stuff and I now have this:

Attachment:

picking.jpg [ 47.51 KiB | Viewed 3490 times ]

sadly this is not really what I want (clearly the fragments have their own positions by this point. here is my code:

Code:

void PickerVP(
    float4 inPosition    : POSITION,
   float2 inMaterial    : TEXCOORD0,
   
    out float4 outClipPosition        : POSITION,
    out float4 outWorldPosition    : TEXCOORD0,
   out float2 outMaterial        : TEXCOORD1,
   out float4 outCameraPos : TEXCOORD2,
   out float4 tmp : TEXCOORD3,
   
    uniform float4x4 world,
    uniform float4x4 viewProj,
   uniform float4 cameraPos
    )
{   
   
    //Compute the world space position
    outWorldPosition = mul(world, inPosition);    
    
   //Compute the clip space position
    outClipPosition = mul(viewProj, outWorldPosition);
   
   //Pass through the material
    outMaterial = inMaterial;
   outCameraPos = cameraPos;
   tmp = outClipPosition;
}

void PickerFP(
    float4 inPosition        : POSITION,
    float4 inWorldPosition    : TEXCOORD0,
    float4 inMaterial    : TEXCOORD1,
   float4 inCameraPos : TEXCOORD2,
    float4 tmp : TEXCOORD3,
   
    out float4 result        : COLOR)
{    
   
   float3 worldNormal = cross(ddy(inWorldPosition.xyz), ddx(inWorldPosition.xyz));
   worldNormal = normalize(worldNormal);
    
   result = float4(1,0,0,1);
   if (distance(tmp.xyz, float3(0,0,0)) < 512){
      result = float4(tmp.x/512,tmp.y/512,tmp.z/512,1);
   }
}

obviously I'm just testing the concept right now, but it seems I have a lot of work to do still

EDIT2:

Quote:

5) Fragment world space positions are always ending with '.5'. You need to work out which integer position this corresponds to (i.e. the actual voxel position). You will probably want to take acount of the normal to do this.

this is clearly the piece of the puzzle I need to understand better to make this work. Which variable is the world space position that my fs is getting? Do I need to do all the transforms in my fs instead of my vs? Overall I just don't think I understand this quite well enough to pull it off myself : /

AndiNo · **Joined:** Sun Oct 03, 2010 10:13 pm **Posts:** 73

paycheck wrote:

I seriously hate that there is absolutely no way for me to figure out what is wrong with my CG programs.

Maybe this is interesting for you:
http://developer.nvidia.com/object/nv_shader_debugger_home.html
I tried using it before, however I dropped it because I didn't know enough about shaders so I could translate my Ogre materials into stuff that the debugger understands. Maybe it'll help you, though

If you get something running please let us know, might be valuable in the future.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

paycheck wrote:

EDIT2:

Quote:

5) Fragment world space positions are always ending with '.5'. You need to work out which integer position this corresponds to (i.e. the actual voxel position). You will probably want to take acount of the normal to do this.

this is clearly the piece of the puzzle I need to understand better to make this work. Which variable is the world space position that my fs is getting? Do I need to do all the transforms in my fs instead of my vs? Overall I just don't think I understand this quite well enough to pull it off myself : /

I didn't explain it very well so I'll try again. In the volume, the voxels each have a position of (x,y,z), where x,y, and z are integers. Let's imagine that we have two adjacent voxels at (0,0,1) and (0,0,2). Let's say one of these is solid and the other one is empty space, this means that a surface will be placed between the two. The z-coordinate of this surface will be 1.5 (this is the '.5' I was referring to).

Note that I didn't say which of the two voxels was solid and which was empty - in both cases the surface will have the same z-coordinate but will be facing in opposite directions. In other words, simply knowing the position of a fragment is not enough to know which voxel it corresponds to.

In this example the z is fixed accross the generated triangles, but the x and y will change. Even a they are changing they still belong to the same voxel. You need to round them to the correct voxel.

If you assume that you have not performed any transformations yourself, then I think you need to take the fragment position and move back slightly in 3D space in the opposite direction of the normal (i.e. towards the centre of the voxel). Then you need to round the floating point values of x,y, and z to the nearest integer. I think this gives you the correct voxel position. Then you need to convert it into a colour.

I should point out that the above is completly untested as I haven't implemented selection based on a colour buffer. But that's how I think it should work...

paycheck · **Joined:** Wed Nov 10, 2010 7:15 pm **Posts:** 43

David, have I ever told you that you are the man? What you just said made perfect sence, I'll do my best to implement it tonight - It doesn't even sound to difficult and I think I'm half way there. Thanks a ton!

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

Thanks!

Now I just hope that it works...

Picking

Who is online