[WolfCoder]

I'm going to do something new as I'm bored working on the same stuff I have been.

Introduction

I already have the 2D stuff implemented in my engine to where I am satisfied. The only thing missing is the part of the engine that loads objects from the 2D tile maps and places them in the level- however I will design that later to be generic and use the same format for 2D and 3D maps so to save myself the problem.

Adding entities to a 2D or 3D level is simply done by loading the associated object (sprite, model, ect), looking up the action (need to register the action), and some default entity skill values (skill values are personal entity variables). In any case, placing entities, lights, sounds, assigning textures and material (shader effects) to surfaces are all trivial matters to me. WED saves everything in a text file for you to process with plenty of information to reproduce what the level looks like and even sounds like. WED feels very similar to Valve's HAMMER and they all are typically called World Editors. It's like the big IDE of everything- you can basically create a game from it by making new levels, adding entities, and linking them with special entities who simply warp the player places.

Problem

Making the level is easy, but the hard part is the collision hull. Each block in the level can have faces that have at least 3 sides to them. The information that is important is whether or not a particular polygon intersects the level. This is really complicated. It gets even worse, not only that, but every time a polygon does intersect the level hull it becomes important to know the NORMAL vector. This allows entities to slide around if a hill is too steep (like in Mario 64).

I'm going to write a map compiler (I think you can even replace the default map compiler in WED to your own) that will detect the format (so it works with more than the .WDL format, picking out all the required or useful information) and then generate the necessary stuff. After that, it will compile the textures using the image packer I already wrote. I'm not going to sort all the level polygons using a BSP yet (I have a tutorial on that already from long ago) but I will later to greatly increase the speed. The third chunk of information I need is the collision hull. The blocks need to be converted into shapes that work well with whatever checks for collision.

Here's what the function I need to write looks like:

u32 ws_3d_hull_poly(polygon *what);

It accepts a polygon type (used for collision hulls) and checks to see if it intersects the currently loaded level. It returns 0 if not, otherwise 1. Furthermore:

vector* ws_3d_hull_normal();

Returns a vector representing the normal. It's a 3D vector of length 1 pointing in the direction the hit face was. You can find out the angle of the slope with it. It's perfect for orienting and placing bullet holes and deformation marks. There's plenty of ways to do this- but the thing is I won't be able to tell if it is a bad way unless it's a REALLY bad way.

This post has been edited by WolfCoder: 24 March 2009 - 12:35 PM

[SigurdSuhm]

I'm currently working on a few of the same things for my game engine at the moment. My experience is limited but I'll try and see if I can provide any constructive feedback.

If I understand this correctly you need some sort of bounding objects to define all 3D entities within a world. I don't think this part in it self will be hard for you. My engine is written in C# so of course I'm thinking very object oriented and doing it all with polymorphism. I'd gladly explain my own approach but for now I'm not sure that it's important to you.

Also I'm guessing you would want some sort of per-vertex collision detection as well since stuff like terrain and such is very hard to represent using simple objects. Now I don't know the World Editor IDE (WED) you're using but I'm guessing that you have access to all vertex data through the ouput file? In that case it shouldn't be too hard to make a representation of the objects in your physics system. Based on the WolfCoder I know, you should be familiar with all the performance tricks often used with this kind of collision detection.

In the end I'm guessing that you could have a big collection of entities represented by some sort of bounding object. Boxes, spheres and even just meshes storing all the vertex data. And this is where I find polymorphism brilliant. You can easily check any of these against any other bounding object without know exactly how the other object is represented.

Now you also mentioned that you need to determine which kind of physical representation would fit various 3D entities. Are you thinking about doing this programatically? I've never actually given an algorithm like that much thought so I'm not sure I can help right now.

I hope this provided a bit of help or at least some food for thought. Let me know if I completely misinterpreted something.

Regards
Sigurd Suhm

[WolfCoder]

SigurdSuhm, on 25 Mar, 2009 - 04:03 AM, said:

...
I hope this provided a bit of help or at least some food for thought. Let me know if I completely misinterpreted something.
...

Oh no, you were helpful, but I already know about basic shape detection and I need precise collision hulls. The Level Hull is a single hull. The level itself is comprised of blocks (any good World Editor like WED or HAMMER makes any level out of blocks). Blocks have verticies and faces where you put the textures. The problem has nothing to do with the entities inside the level (models, sprites, ect). I already have a 3D box collision system implemented and in use even though the current game is in 2D. My engine is weird like that- built to care as little as possible of whether or not anything is 2D or not. It's just that it's really easy to have a collision hull made up of tiles that extend infinitely in the Z direction above and below the ground. Using tile index 7 is a special case tile that gets interpreted as a pit and you can fall down through it (it's the classic blank tile used to fill the upper layer by default just like RPG Maker).

Back to 3D

A single block is the atomic element in a level. It is made up of vertices which define faces- faces are not limited to triangles and can be any polygon. When compiled, a collision hull contains all the blocks that were not marked as passable, including invisible blocks that are solid (in Acknex, the collision hull had passable block parts that were commonly used as water). However... The problem is... Huh?

A function is required to test a single line to see if it intersects the collision hull. ALL blocks are required to be convex, and concave shapes are made up of multiple smaller convex shapes (for example, when using WED's CSG subtract feature, it splits things into smaller blocks). I am thinking the restriction was made for the sake of collision. That must somehow be the key, but I'm still just as lost as ever.

When moving a box entity, I can't just extend the vertices using 8 lines because I'll fall through blocks smaller than myself if I'm an entity. I'm really lost on this one. But The level is the only polygon collision I'll need, I might have some other models use polygon collision, but I'll avoid it for speed reasons.

[SigurdSuhm]

So the core problem is writing an efficient algorithm to check if a line intersects a polygon regardless of the polygon's number of vertices? Again please correct me if I got anything wrong.

If this is the case I guess you can do it as a slightly more advanced kind of ray-triangle collision test. If you generate a plane based on the orientation of a face you can start off by checking the line against the plane. Also it should be easy to use the plane to return an accurate normal for the face. In case of an intersection there are various mathematical techniques to determine whether the point where the line intersects the plane is actually inside of the polygon. It's rather simple for a triangle but should be doable for more complex polygons. And of course you could even choose to split a face into triangles if you find it easier.
I'm guessing there should be some articles around the internet concerning physics or ray casting that would describe techniques relevant to this topic.

As for the "falling through blocks smaller than myself"-issue it sounds like a containment collision problem? Again whack me with a stick if I got it wrong. I suppose you could extend the algorithm with a simple section checking whether one vertex of an object is contained within another. Now that suddenly got me thinking. I'm guessing this would actually be quite a complicated process for complex meshes. As I said my experience is limited so I might not be the best person to ask here.

I'll check in on this thread again later to see how much of my stream of words here was completely useless. Hehe...

Regards
Sigurd

[WolfCoder]

Yeah, ray tracing won't do it though. I need BOX tracing. The line must be as thick as the extruded collision hull or I will be able to fall through objects smaller than myself (all 8 ray traces will miss the object allowing it to pass through the object).

[SigurdSuhm]

Wow. This is definately an interesting topic. I've been thinking back an forth and I must admit that you've come up with quite the problem here WolfCoder.

I was thinking that the procedure of projecting onto a plane made from the orientation of the target polygon might still be a way. Perhaps you could try to project the entire polygon (the one of the moving entity) onto the plane. This way you could perhaps use the orientation of the plane as the base of a new coordinate system so to speak.

From here there would be a few options I guess. Maybe you could check if any of the projected vertices are contained within the target polygon. If this is not the case then there are two possible reasons.
1: The polygons are not in contact at all. No problem...
2: The target polygon is completely contained by the projected polygon.

To rule out option 2 you could just check a single vertex of the target polygon to see if it is contained within the projected polygon. That should leave the test returning a collision in every case where there actually is one. The only case where no vertex from one polygon would be contained within another and no polygon from the other would be contained within the first, would be if there is actually no collision at all.

Again this was just some ideas that came to me while doing some thinking. I'm not sure it would be an optimal way to implement the system, and I'm definately not sure that it's the most efficient way.
So it would be great if some of the more experienced programmers here could throw in a little feedback.

Again let me know if my thoughts were poorly explained or anything else.
Regards
Sigurd

[WolfCoder]

Here, they just released the WMB format and there's no collision info.

http://www.conitec.n...rog_mdlhmp.html

Even though it's the WMB7 format, it's heavily backwards compatible. It contains all the compiled stuff in it, and it's pretty simple. It even has those realistic lightmaps that made all my previous demos look cool. All the blocks get reduced to triangles as expected- so it's a ton of triangles and texture coordinates.

Lightmaps are just huge collages of sections, and many many triangles are mapped to them- it appears. I'll write them out as bitmaps sometime as I'm curious to see what they look like as 1024x1024 pictures.

So it's basically just box to polygon collision. This is a very simple format (relatively speaking for levels) and you can implement it too. However the collision detection is not. But at least I know it's just triangle detection. There are box exclusions (each block has a maximum size on it so you can see if you even need to resort to polygon testing).

This post has been edited by WolfCoder: 27 March 2009 - 12:16 PM

[SigurdSuhm]

I've just taken a look at the file format. Seems pretty easy to work with actually. You have direct access to all the triangles of a block through the TRIANGLE struct defined by indices from the VERTEX array. So making an efficient algorithm based on this shouldn't be too hard I figure.

Have you tried anything so far?

[WolfCoder]

No, I have to draw it before I get to do collision hulls. I'm going to dump the lightmaps first and see what they look like.