Fluxtah

Hi,

I am using XNA to develop my game. I finally have a working octree where I can insert renderable objects based on their AABB, in my book it mentions that static geometry is best inserted into the octree and polygons should be split if they straddle.

The thing I cant get my head around is, How do I best manage static geometry that makes it suitable for polygon splitting If I am using directX (.x) models, in XNA I end up with a Model object, I can get access to the vertex and index buffer, but I am confused at how I should manipulate the vertex data in order to split them when I build my octree.

Any help on this would be greatly appreciated.



Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Inaki Ayucar

Well, it depends on how accurate you want to be.

In every case, you will have to loop through the polygons of the mesh

To do so, get access to the index buffer of the model. It gives you, for every face, 3 indices of the vertices that belong to that face. For example:

Face 0

indexBuffer[0][0] = Index of Vertex0 in Face 0

indexBuffer[0][1] = Index of Vertex1 in Face 0

indexBuffer[0][2] = Index of Vertex2 in Face 0

Then, in you access the vertexBuffer using those indices and you get the Vertex Information.

Once you know how to loop through the polygons, you will need to test if each polygon is:

1.- Outside the octree cell

2.- Inside the octree cell

3.- In between (the polygon intersects the octree cell boundaries).

To test if a polygon is inside an octree cell, you can do a in-out test with every vertex of the polygon against every plane of the cell, what is pretty fast. If every vertices are outside of one plane of the cell, the the polygon is outside of the cell (case 1). If every vertex is inside of all planes, then the polygon is inside (case 2). If not, the polygon intersects (case 3)

The easiest way to split your model is to discard the third case, assuming than an intersection polygon is inside or outside (whatever you want, but better assume "inside" to avoid artifacts).

If you want to be extremely accurate, you should keep track of the third case too, dividing the intersection polygon into 2 parts (clipping the poly against the cell plane), and moving the first part to mesh1 and the second part to mesh2. There are lots of algorithms for polygon clipping, just google that term.

Altough this task should be done in pre-processing time, I guess this second way could be too expensive. Up to you...

Hope this helps.






Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Fluxtah

Excellent thankyou that opened up my mind a little more, although I have one more question now :)

If I was to go with the first way, and avoid splitting the polygons, then I would end up with vertex data (and I guess index data) from a model that has been assigned to either side of a plane, ignoring the straddle. I am not thinking correctly on how to store this data, does this mean that my existing models vertex/index data would be split into 2 new models

Sorry if my questions seem newbie, I am very new to games programming and I find this problem quite intruiging.

I am using the book Real -Time Collision Detection by Christer Ericson, it does explain the theory, and shows an example involving dynamic objects, but the information about static world geometry abruptly ends and refers to polygon splitting algorithms later in the book, which is good, although its fairly abstract with no API specific implementation examples (no mention of index buffers or vertex buffers at all!) :(

 

 





Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Fluxtah

Ok thinking about my second question a bit more, and reading around, I should only really need to split the index buffer data, which kind of makes sense, and keep a reference to the original model in order to get at the vertex buffer data when it comes to rendering, still I am wondering about how best to implement this, I guess my current design is an evolving experimental one and there is no excuse why I cannot refactor to grow with my understanding :)





Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Inaki Ayucar

Thats it !

If you separate a model in two pieces, you will get two sets of vertex and index data. Any way the best way to handle this is just to create two different models (one of them can be the original, without the detached polygons). Anyway, I would suggest you to be smart whem modeling your scenes trying to avoid this procedure as much as possible, fitting objects inside an octree cell as a hole (without having to divide them).

If this helps: A model is made of polygons, numbered from 0..NumberOfFaces.

Every face is a triangle, with 3 vertices. So, the index buffer is nothing more than an array of structures like this:

struct mesh_face

{

short idx_vertex_a;

short idx_vertex_b;

short idx_vertex_c;

}

Each vertex index refers an entry in the array of vertices, which has 0..NumberOfVertices vertices. The structure of each vertex depends on the vertex format you declared for the vertex buffer. If you declared a vertex format that includes Position, Normal, and one set of texture coordinates, the structure would be:

struct mesh_vertex

{

Vector 3 Position;

Vector3 Normal;

float u, v;

}






Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Inaki Ayucar

Sorry, I didní»t see your last post.

I doní»t recommend you to split the index buffer only.

I find it more "clean" and efficient just to create two separate objects, instead of including in your engine the posibility of split a single modelí»s index buffer.

Anyway, ití»s also possible that way.






Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Fluxtah

Thankyou, all the information you are providing is very helpful.

I think the only problem with building the scene so it conveniently avoids the need to split is when a tool is used to develop environments that would be out of my control, I am just a programmer and wouldnt have any control of how a scene would be developed by a 3rd party user, so object placement would be out of my hands, although if I was to create my own environments I would know about the octree culling system and probably do my best to avoid plane straddling.

I think the next problem is XNA's ability to create models dynamically, something I will look at tonight when I am done with work.

The other solution is to allow my objects to occupy 2 nodes if they straddle a plane, this is probably the easiest implementation however it might not be in favour of performance, and perfomance is something I am mostly interested in.





Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Inaki Ayucar

Thatí»s right. Keep in mind performance.

You should have no problem at all creating Models dinamically.

Let me know if you need anything else !






Re: Game Technologies: General Octree - Handling static geometry, primitive splitting

Fluxtah

Hi Inaki,

After asking on the XNA forum about the Model class it seems that its not designed to instance and apparently the VertexBuffer / IndexBuffer data is read only, this makes it a problem to create one dynamically.

Its possible to create my own content processor that could preprocess model data into my own structure or even into split model files according to the octree.

This makes me wonder wether its worth while to treat all my static content in a pre-processing step that occurs during compilation before the game is even run.

If thats the case then it might even be a better idea to compile an octree structure of static content as an xnb file that represents the octree structure, some kind of map file or something, still not sure about this.

of course I could also create my own model classes, maybe a StaticModel class or something that has features to split the data into parts.

Anyway, I guess I will think of something, any thoughts on this would be appreciated :)