2d images given precise 3d behavior?

November 07, 2006 04:41 PM

Quote:Original post by Sylon
You mean the individual pixels in the multicolored dioramas are exactly how voxels are made? Voxels use RGB representations for space?

No.
Voxels are a Concept, there are as many different ways of Implementing them as there are different programmers.

Sylon

126

Author

November 07, 2006 08:06 PM

Quote:Original post by Anonymous Poster
No.
Voxels are a Concept, there are as many different ways of Implementing them as there are different programmers.

Oh okay cool!

Dino

172

November 09, 2006 01:07 PM

Sylon,

I responded to your PM. These are my thoughts (assuming I have your goal correct):

First, and foremost, any solution we can come up with will most likely be too slow to be of any good. While 3D pixel-perfect collision is very nice to have, it's just that... a nice-to-have.

However, for the sake of learning and problem-solving, let's assume that processor speed and memory is not an issue.

What you want is for every object you have, associate a 3-dimensional array of bits which will represent what the object looks like in a 3D world. A 3D mask if you will. Every frame the object can be in that changes the space it occupies means also that you will need to have a new array for that. Some will have more than others. A rock will most likely have 1 while a living will have many arrays.

Now since all you are concerned with is collision of 2 objects that are within the same space, checking for collision is very easy. You take the 3D array of the one object and then overlap the other object, of course offsetting it correctly. If any 3D points (also known as voxels) intersect, then you have collision. It's very simple to theorize since this is how the real world works.

Implementing such a scheme efficiently is a different story. A simple 32 x 32 x 32 object will require a total of 32 thousand bits (or 4k of memory) to have it truly represented as a 3D mask. That is not realistic.

So let's try an cut that number down to something more manageable. The most efficient we could get is if we decided to only map the outer surface of our object which would (in the 32x32x32 object) still take up 512 bytes (1024 bits per side, 4 sides, 8 bits per byte). This is a simple cube. A more complex object would require more data to map the surface.

This is why people have opted to use boundary cubes for collision detection or going true 3D because given our current level of technology, having hundreds of objects using that much memory (for a single frame mind you) is just not realistic. Let say your standard character is 64 pixels tall, 24 pixels wide, and 24 pixels deep. A 3D mask of a single frame of this character would require 65,536bits (or 8k bytes). If that character has 15 frames for 1 single position or motion, then that would require 120k bytes. If that character has 20 different positions and then that 1 character would require 2.4M bytes to represent it fully in 3D space. That is actually not that much memory, but that is for 1 semi-complex character.

Now, you can do some things to take advantage of the defined 3D mask. All instances of that character can (and should) use the same 3D masks so it's only 2.4M for an infinite number of character instances. Also, while some monsters may look different, they could all share a common 3D mask.

However, even if you optimize is as much as you think is possible, you will still end up using a lot more memory than you would hope for. While PCs are coming with 1GB and 2GB of memory today, most people playing your game will have around 512kB of memory (+/- 215kB). Also, I only pointed out the memory limitations of trying to do pixel perfect 3D collision. There is then the actual collision algorithm that must be written. It could be written in such a way that it only does collision checks on the voxels that could possibly have intersected, but is still a whole lot of looping, ANDing, and memory jumping. Of the two limiting factors, though, this would be the lesser of the two evils.

I would look into have a close representation 3D model of your 2D object that you can use to do all of your collision detections on. This close representation model can be rendered on a hidden surface with 0 frills and used for collision detection only. You can use the detailed 2D sprite for display, but use the 3D model for most of the grunt work.

Dino M. Gambone
Good judgment is gained through experience. Experience, however, is gained through bad judgment.

Currently working on Rise of Praxis MUD: http://www.riseofpraxis.net/

Sylon

126

Author

November 09, 2006 10:22 PM

What a thoroughly awesome reply by Dino! I've NEVER.

For me it was like, more educational than that stuff I read from my Commodore 64 manual, and my DarkBasic manual(s). LOL! Pssh DarkBasic...

Quote:Original post by Dino
I would look into have a close representation 3D model of your 2D object that you can use to do all of your collision detections on. This close representation model can be rendered on a hidden surface with 0 frills and used for collision detection only. You can use the detailed 2D sprite for display, but use the 3D model for most of the grunt work.

Now THIS intrigues me! Because SHAME on a tad few other gamedev coders from my past 2 or 3 topics--I asked if this was possible to all of them and they said "Why not go all the way with 3d anyway," but I was like NAH, can't we make invisible polygon collision masks for my pixel art displays?!! They suggested billboarded sprites but I was hoping for something like this instead! Now I know it can be done! Thank the Lord. I have one solution down at last! Dino lit the fire. I didn't ask about this point in this topic here because I thought I would be beating a dead horse, I asked it like 4 times already. I must be smarter than I thought!

So this can be for any object, a tree, a rock, a monster, whatever? Because actually for the characters and monsters I was thinking that 3d rectangular bounding boxes would be fine in my game--but it will be a hack'n'slash, another nightmare to code I suppose, with all the weapon swinging/shooting. Would having polygonal collision boundaries save a mass more CPU power than voxel collisions, or just a small amount more?

The other thing is, the reason I really wanted pixel-perfect collisions is because I want objects to "roll" over rounded surfaces, instead of just cubic blocky heights or triangular ramp heights...I want organic hills. If there is a non-voxel collision method to get that, then awesome. Polygonal collision boundaries look like a good way to go. Someone at GarageGames told me that he's making an Isometric engine which will allow some kind of sub-cell collision checking within tiles I think...and they might be given height values too! I COULD probably ask him more about that.

Okay, now back to shadows baby!

So I was talking to guys at devmaster. One of them told me this:

-----"i think its possible, if you have absolute world coordinates for each pixel, which you could get from the base position of the sprite, then using the heightmap/coordinate map to create the exact world position of the pixel, you could use it to detect if its in shadow or not.

you could use geometry shadow volumes to do it.

you make the volume out of the outlines of the sprites (as long as you find its supposed exact 3d position) and extrude away from the light and then its
just a containment test per pixel to find out if its in shadow or not. (including ground tiles)"-----

I don't get the extrude part. BUT! I illustrated what I understand he meant by the world coordinates. So basically (correct me if I'm wrong) the world has absolute x and y values for each pixel right? Then, for objects' base pixels, x and y values are coded (absolute within the object, but relative to the world pixels?) and for any pixels in an object that supposedly have height, instead of coding their x and y values normally, we'd code say all pixels "above" x1y1, to be x1y1 as well! Then when a transparent shadow sprite crosses a world pixel, and an object's x1y1 pixel is sitting on that world pixel, THOSE pixels in the object which were coded as x1y1 will become shaded! Because the shadow will offset to those pixels! If that's confusing I drew my understanding here:

Shadow Offsetting

The first pink arrow shows an object pixel offsetting the cast shadow pixel.

The pink bracket in the 3rd diagram shows a row of pixels on that cubic object, which are all coded with the same x/y coordinates as the pixel at th base of the object, so they all get shaded by the cast shadow because it's as if it "moved" to all of them.

The last diagram has an unrealistic effect but for code purposes it has to be that way (if my understanding is right).

What we can get is that ramp-shading effect, where rounded and ramp objects can BEND cast shadows, as long as someone codes the heightmaps right?

So, how does this look for making pixel-precise cast shadows? I don't want a lighting system, just shadow sprites that follow objects and get cast over other objects, that's what I want. Does this take the same processing power as voxel collisions??

And, if I choose the polygonal collision checking method, would this kind of thing still be available?

Dino you rule!

Twincamtinman

154

November 09, 2006 11:02 PM

The method you describe isn't the one suggested to you, but the suggested one was far more complex then you need. If all you need are simple vertically projected shadows your method would work well and feasibly fast. In response to your collisions, if you used a simple heightmap for the terrain and then only used polygonal collision meshes for special objects like characters and trees it might be feasible in terms of memory and performance. I definitely recommend a hybrid approach, with simple collisions/shadows for places where the complex systems aren't needed such as terrain and then a more complex system for 'special' situations. Hope this helps.

Sylon

126

Author

November 10, 2006 07:52 AM

I LOVE THE UNIVERSE! Holy excellence!

Twincam--

Hi! Perth huh? S'where the coder that suggested the world coordinate thing was from! Are you HIM? LOL.

So "simple heightmaps for terrain" would mean I could make rounded, near-domelike hill tiles? And further can I make them any shape I want or by "simple" do I have to make them inorganic (not lumpy)? Like, if I made a tile with 80% flat heightmap and in one corner of it I made a rock with a small raised height, would the mobile objects collide with it, using their simple polygon mesh? This and the rounded hills terrain is the whole reason I thought voxels were necessary. Would the SAME heightmap that offsets the shadow pixels be the one that dictates collisions (would make it easier)?

And as long as my character sprites "roll" organically over the hills as they run, or bump into these random small objects within tiles, I wouldn't mind if their bounding box was a blocky rectangle or a cylinder.

-------------------------------------------

I think...I'm running out of questions. Somebody slap me. Miracle!

My fantasy is unfolding before my eyes! I don't believe it. Finally! After asking 23,000 questions I'm finally here!

But I apologize to all the programmers who I confused with my uneducated theoretical questions.

SO! My shadows will work, and fast too. What a relief. I will go NUTS defining heightmaps for my artwork! Sweet.

You guys rock, all of you. If I had some, I would give you money just for telling me this.

[Edited by - Sylon on November 10, 2006 8:52:04 AM]

Traveler

161

November 10, 2006 08:13 AM

Quote:Original post by Sylon
You guys rock, all of you. If I had some, I would give you money just for telling me this.

That's way GD.Net has implemented the rating system :)

[My gamedev diary]

Sylon

126

Author

November 10, 2006 08:30 AM

Yes! I award all of you exactly 1,233 rating points!

Dino

172

November 10, 2006 08:33 AM

Quote:Original post by Sylon
Now THIS intrigues me! Because SHAME on a tad few other gamedev coders from my past 2 or 3 topics--I asked if this was possible to all of them and they said "Why not go all the way with 3d anyway," but I was like NAH, can't we make invisible polygon collision masks for my pixel art displays?!! They suggested billboarded sprites but I was hoping for something like this instead! Now I know it can be done! Thank the Lord. I have one solution down at last! Dino lit the fire. I didn't ask about this point in this topic here because I thought I would be beating a dead horse, I asked it like 4 times already. I must be smarter than I thought!

The reason several coders would recommend going all 3D is because they don't deem the added 2D sprite detail worth the extra work it would entail to do a 2D/3D hybrid. However, you think it is worth it and that is all that matters.

Quote:Original post by Sylon
So this can be for any object, a tree, a rock, a monster, whatever? Because actually for the characters and monsters I was thinking that 3d rectangular bounding boxes would be fine in my game--but it will be a hack'n'slash, another nightmare to code I suppose, with all the weapon swinging/shooting. Would having polygonal collision boundaries save a mass more CPU power than voxel collisions, or just a small amount more?

I think that most 3D collision boundary implementation will do this kind of work much more efficiently than any voxel implementation. Just look at the simple numbers:
A single 3D boundary cube will require eight 3D points to represent it. Lets say one 3D point consists of 3 single-precision floats for a total of 12 bytes (32bits * 3). That means for any cube of any size, you will need 96 bytes to properly do collision checking on a cube. To determine if 1 cube is colliding with another cube (assuming you just don't use the optimized 3D libraries) would a simple check. I forget the actual formula, but it's not very CPU intensive.

Now a voxel based implementation of a small object (let's say 8 x 8 x 8) would require you to have a minimum of 64 bytes (8bits cubed). At first that doesn't sound bad at all, but this is for a small object. Increase that to 32 x 32 x 32 and now we are looking at kilobytes of memory needed to do the collision checking. Then add on algorithm needed to actually do a bit by bit check and you are talking alot of work.

So, right now, boundary collision is your best and fastest choice and is much more efficent.

Quote:Original post by Sylon
The other thing is, the reason I really wanted pixel-perfect collisions is because I want objects to "roll" over rounded surfaces, instead of just cubic blocky heights or triangular ramp heights...I want organic hills. If there is a non-voxel collision method to get that, then awesome. Polygonal collision boundaries look like a good way to go. Someone at GarageGames told me that he's making an Isometric engine which will allow some kind of sub-cell collision checking within tiles I think...and they might be given height values too! I COULD probably ask him more about that.

As long as you don't want object to be able to go under a tile, then height maps are the way to go here. It's fast and efficient and gives you pixel-perfect heights at any 1 point. By storing the information in a simple 2d array with a char offset, you can have very large rolling hills. A 3D terrain engine could also give you the same effect, but I'm not completely sure on the pixel perfect height evaluation.

The purpose of the char offset allows you to break the 256 pixel maximum height that a single 2D char array (which is what you want to use to minimize memory use) and also allow you to reuse the same tile at different heights. For every unit the offset is increase, the tile is raised 256 pixels. This allows you a maximum of 64k pixels high, but only use 1 extra byte more than the 2D char array.

Quote:Original post by Sylon
Okay, now back to shadows baby!

So I was talking to guys at devmaster. One of them told me this:

-----"i think its possible, if you have absolute world coordinates for each pixel, which you could get from the base position of the sprite, then using the heightmap/coordinate map to create the exact world position of the pixel, you could use it to detect if its in shadow or not.

you could use geometry shadow volumes to do it.

you make the volume out of the outlines of the sprites (as long as you find its supposed exact 3d position) and extrude away from the light and then its
just a containment test per pixel to find out if its in shadow or not. (including ground tiles)"-----

I don't get the extrude part. BUT! I illustrated what I understand he meant by the world coordinates. So basically (correct me if I'm wrong) the world has absolute x and y values for each pixel right? Then, for objects' base pixels, x and y values are coded (absolute within the object, but relative to the world pixels?) and for any pixels in an object that supposedly have height, instead of coding their x and y values normally, we'd code say all pixels "above" x1y1, to be x1y1 as well! Then when a transparent shadow sprite crosses a world pixel, and an object's x1y1 pixel is sitting on that world pixel, THOSE pixels in the object which were coded as x1y1 will become shaded! Because the shadow will offset to those pixels! If that's confusing I drew my understanding here:

The first pink arrow shows an object pixel offsetting the cast shadow pixel.

The pink bracket in the 3rd diagram shows a row of pixels on that cubic object, which are all coded with the same x/y coordinates as the pixel at th base of the object, so they all get shaded by the cast shadow because it's as if it "moved" to all of them.

The last diagram has an unrealistic effect but for code purposes it has to be that way (if my understanding is right).

What we can get is that ramp-shading effect, where rounded and ramp objects can BEND cast shadows, as long as someone codes the heightmaps right?

So, how does this look for making pixel-precise cast shadows? I don't want a lighting system, just shadow sprites that follow objects and get cast over other objects, that's what I want. Does this take the same processing power as voxel collisions??

And, if I choose the polygonal collision checking method, would this kind of thing still be available?

If you use a simple 2D height map, then it should work ok. There are quirks you will need to keep an eye out for, though. It's hard to explain, but oddly shaped objects will cause you the most problem and I would, in your implementation, test with objects that are concave and have the left-most points in the back (furthest from the viewer).

Dino M. Gambone
Good judgment is gained through experience. Experience, however, is gained through bad judgment.

Currently working on Rise of Praxis MUD: http://www.riseofpraxis.net/

Sylon

126

Author

November 10, 2006 10:38 AM

Hey!

Quote:Original post by Dino
However, you think it is worth it and that is all that matters.

That's what I was thinking too! Hehehe.

Quote:Original posy by Dino
So, right now, boundary collision is your best and fastest choice and is much more efficent.

Nice.

Quote:Original post by Dino
As long as you don't want object to be able to go under a tile, then height maps are the way to go here.

DANG!

Maybe I'm confusing tiles with objects? I was thinking of making stackable objects, with different floor levels and stuff.

SW of the dog character you see some blocks, with one shaded by the one above it. I was think I could make a game with elevated levels like this, and yes characters going under objects. In this case are objects different from tiles? I want my world to be basically BUILT by stacking cubic objects, and then any organic objects with rolling or lumps, would be stacked on top of the cubic objects to basically give form to hills and stuff. The "tiles" would be such as the metal floor you see in the screenshot of HOH--just at the bottom of the stacked objects. Really the objects would be what gets walked on 99% of the time.

Can I give the organic heightmaps to the objects and stack them, and make it so some of them can be traveled under?

I figured the whole 3d polygon collision mesh would allow for jumping in 3d space, such as for jumping into elevated cave hole in mountainsides, or into windows, under/between multi-level bridges, etc.

LARGE hills I was thinking could be sacrificed--to build large hills I would instead just stack cubic objects in a large 3d formation and at their tops, place an object with a ramped or lumped heightmap (there would be enough of these "top" objects that you could make it look seamless when you set them near each other). Doable?

Here is a pic to explain, don't mind the mismeasurements of tiles or the bad art!:

Hills and elevations

I would like 90 degree rotations of maps (I will make 4 sides to everything) and jumping around elevations.

Quote:Original post by Dino
If you use a simple 2D height map, then it should work ok. There are quirks you will need to keep an eye out for, though. It's hard to explain, but oddly shaped objects will cause you the most problem and I would, in your implementation, test with objects that are concave and have the left-most points in the back (furthest from the viewer).

As long as they're just quirks I'm sure I can find a way around them, or be able to sacrifice them. Thanks!

2d images given precise 3d behavior?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

2d images given precise 3d behavior?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines