- Online Community Forums » Programming Questions » 2d coordinate transformation

This thread is locked; no one can reply to it. rss feed Print
2d coordinate transformation
Member #5,114
October 2004

Yes, yes. Another question about the Amarillion Mode7 example. But this also comes down to general knowledge of working with a 3d scene. From a bit of searching I believe the technique of showing a sprite within a 3d scene is called 'billboarding'.

Now, I've come to the point where I would like to give the user the ability to 'select' certain objects that are on-screen. The problem is, I'm having troubles figuring out exactly how I should do this.

The code to render a sprite (taken, mostly, from Amarillion's article) is effectively:

    fixed obj_x = itofix(160) - cx;
    fixed obj_y = itofix(100) - cy;

    fixed space_x = fmul (obj_x, fcos (angle)) + fmul (obj_y, fsin (angle));
    fixed space_y = -fmul (obj_x, fsin (angle)) + fmul (obj_y, fcos (angle));
    screen_x = bmp->w/2 + fixtoi (fmul (fdiv (camera.s_x, space_x), space_y));
    screen_y = fixtoi (fdiv (fmul (cz, camera.s_y), space_x)) - camera.horizon;

    height = fixtoi (obj->h * fdiv(camera.obj_s_y, space_x));
    width = fixtoi (obj->w * fdiv(camera.obj_s_x, space_x));

    stretch_sprite (bmp, obj, screen_x - width / 2, screen_y - height, width, height);

Basically, what is happening here (I believe) is the render_object function is being passed a point in 3d space that is being transformed to a location on-screen (in 2d space) and rendered/stretched accordingly.

I've noticed that as a means of reference, the location in 3d space represents the bottom, centre of the sprite. (Which is why, when the sprite is rendered, you divide its width and subtract its height to get the top-left screen position).

Now, to help with various actions, I have code to transform the mouse_x and mouse_y values into 3d coordinates.

                application.m_x = 160 - fixtoi (space_x); 
                application.m_y = 100 - fixtoi (space_y);

Obviously, the easiest way (or so I assumed) to check if the user has clicked on an object that should then be marked as selected, would be to do a basic Bounding Box check against application.m_x, application.m_y and each objects location in 3d space.

The problem is, I need a way of figuring out the objects top-left and bottom-right positions in 3d space. I can figure them out easily enough in 2d space. So I suppose the best way to handle this would be to transform the 2d coordinates to 3d coordinates, right?

I'm not sure how I should do that. I'm also worried that a Bounding Box check isn't the way to go. Say, for example, I have two objecs that overlap (one is in the distance). The Bounding Box would return positive for both. The only possible way to stop this (I think) would be to just stop the check after the first 'collision'. The objects, after all, are already sorted by order of depth. So I would always select the object closest to the camera.

Arthur Kalliokoski
Second in Command
February 2005

Let me get this straight: You have sprites on the screen that you want to be able to select with the mouse?

If so, you can simply use the 2d screen coords, if you don't already have those do the divide by distance.

If your bounding box fits "snugly" to the sprite, either they wouldn't overlap each others visible pixels totally or the farther sprite shouldn't be visible anyway. If they did, perhaps you could get the color of the screen sprite under the mouse, if the sprites had different colors (even if the least significant bit in hi/truecolor) you'd be able to tell which it was.

Maybe I'm way off here, my brain is clogged with a cold.

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

Tobias Dammers
Member #2,604
August 2002


The problem is, I need a way of figuring out the objects top-left and bottom-right positions in 3d space. I can figure them out easily enough in 2d space. So I suppose the best way to handle this would be to transform the 2d coordinates to 3d coordinates, right?

Wrong. Your mouse moves in 2 dimensions only, so adding a 3rd dimension to the detection only brings in confusion. The mouse moves in screen space, so that's where you need to do your picking. There are 2 algorithms I can recommend for this, a fast one and an accuracte one.
Fast and easy solution
1. Calculate the actual screen positions of all your sprites, including size after perspective stretch.
2. Sort sprites by distance.
3. Do a bounding box check for each sprite, starting with the nearest.
4. As soon as you find a hit, return this sprite.
Alternatively, you can reverse-transform the mouse position into world space, but this is more complicated than necessary, especially since you have to transform the sprite coordinates for drawing anyway - just keep the values and you're all set.
Accurate solution
1. Set up a blending mode that renders all non-transparent pixels in the same color, and encode the sprite number (or a part of it) into that color (if it's 8bpp, you can pick from max. 255 sprites per pass). This is very easy in 256 color mode: all you need is a custom blend table which I'm sure you can hack together in less than 5 minutes.
2. Render your scene normally, but with a black (color #0) background and the blending function from step 1.
3. Get the color at mouse position (getpixel).
4. Translate the color value back into a sprite number.
If you have more sprites than colors, then you need to run the whole thing twice (or even more), using msb in the first pass and lsb in the second pass. Take special care handling the background.
Forgot to mention: Of course you don't blit the scene painted for picking, you only ever render it to the back buffer, so the user won't see it.

Me make music: Triofobie
"We need Tobias and his awesome trombone, too." - Johan Halmén

Murat AYIK
Member #6,514
October 2005


So I suppose the best way to handle this would be to transform the 2d coordinates to 3d coordinates, right?

You can convert the mouse coordinates to a 3D ray. Make a polygon which is the same as the near clipping plane(it will represent your monitor's screen in the game world), find the point on it which looks like your mouse position on the real monitor(cursor's 3D position), create a line which starts at the camera pos and ends in the 3d cursor position, convert it to a normal vector for the ray, do collision detection with the actual polygons of the sprites.

If the transparent pixels are a problem than convert the collision point on the polygon to UV coordinates and check the texture. This requires keeping a copy of the textures in RAM but that should be worth it.

I believe this is the same technique which Call Of Duty uses for shaky sniper scopes. The look_ang is stable but the crosshair image is not(like a mouse cursor)

"The world doesn't care about what storms you sailed through, it is interested in whether you brought the ship to the dock or not!"

Go to: