 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic Page: «« 1 2 |
Last Thread Next Thread |
| Combining Octrees and BSP trees... is it possible? |
|
 |
Anonymous Poster |
|||
 Posted - 11/18/2002 5:00:22 AM |
||||
| Yann, you mentioned that it's possible to incorporate shader state changes into the construction of the tree. Could you go into a little bit of detail on how to go about that? Also, could you comment on performance impact incorporating it versus not. Thanks a lot. |
||||
|
||||
|
Blitz Member since: 11/11/2000 From: Stockholm, Sweden |
|||
 Posted - 11/20/2002 11:51:04 AM |
||||
| I'm to lazy to read all that text, but i don't agree with your anti bsp/pvs propaganda. I think solid leaf bsp's are still awesome for indoor scenes where there are surfaces that are translucent and for collision detection. And pvs and is still the fastest alternative for VSD in indoor scenes and unlike portals the artist does not need to mark them. |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 11/20/2002 12:59:51 PM |
||||
quote: Just sort your faces depending on their respective leaf and shader state ID (that's the number of the shader, and all required shader parameters, for every face). Then for each leaf, create a list of all faces, sorted by their shader state ID: Eg, if your sorted faces look like this, after the tree has been created: face leaf ID Shader state ID 1 123 0x12345678 2 123 0xABCDEF00 3 123 0xABCDEF00 4 123 0xABCDEF00 5 200 0x12345678 6 200 0x12345678 7 200 0xABCDEF00 then the lists attached to leaf 123 and 200 would look like this:
leaf start face face count Shader state ID
123 1 1 0x12345678
2 3 0xABCDEF00
200 5 2 0x12345678
7 1 0xABCDEF00
When rendering, traverse the tree as explained above. But instead of directly rendering each leaf, create a render state list, and sort it by shader state ID (using a fast sorting alogrithm, it's not going to be a big performance hit, as typically there won't be many entries). You can attach the respective vertex array/buffer to the entries: start face face count Shader state ID vertex array pointer 1 1 0x12345678 0x.... 5 2 0x12345678 0x.... 2 3 0xABCDEF00 0x.... 7 1 0xABCDEF00 0x.... Now, go through the list, set the new state if it changed from the last one, and call the render command for the buffer:
for( each entry in render state list) {
if( Entry->ShaderStateID != LastEntry->ShaderStateID ) {
SetNewState( Entry->ShaderStateID );
}
RenderVertexArray( Entry->VAPointer );
LastEntry = Entry++;
}
That's it. quote: Well, nope, it's not. Technology advances, you know... Perhaps you should actually read all that text...  / Yann |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 11/24/2002 2:28:57 AM |
||||
| So from an implementation standpoint, what's the best way to associate leafs with tris? I had originally thought that each leaf in the Octree/ABT/whatever data structure would have a list of tris. But your explanation above seems to imply that instead each tri has the leaf ID associated with it. You see, I'm trying to implement it in something I'm working on, but my architecture as it is right now won't support it. In my program there's no concept of a triangle, just 'objects' with textures and vertex arrays. Every rendering operation deals strictly with objects, the rest of the app doesn't even know what a triangle is. Any suggestions on how this should be restructured? |
||||
|
||||
|
Impossible Member since: 11/1/2000 |
|||
|
Posted - 11/24/2002 8:48:17 PM |
||||
| You don't need to look at individual triangles while you're rendering (unless objects are breaking apart or changing materials or something), but you have to in preprocess. There is a lot of benefit to using lots of repeated high detail objects (keeps down vertex buffer size, etc.) so do that when you can, and otherwise group triangles into objects based on material\leaf and draw objects with the same material. You're just sorting objects instead of faces. |
||||
|
||||
|
JD Member since: 11/3/1999 From: USA |
|||
|
Posted - 12/1/2002 6:33:12 AM |
||||
| The bsp trees are helpful in low poly scenes(less traversing) when drawing cost higher than traversing the tree. Like in a game using shadow volumes where fill rate will kill your fps. In those situations not drawing shadows that aren't visible is better than drawing them anyways because they have high fill rate cost. Basically, it's visibility test vs. brute force rendering speeds type issue. Portals(removal/addition of hand placed portals) and Octrees can be dynamically sized(before game starts playing) thru a benchmark. If over fps cap then less portals and less octree subdivisions and the opposite when fps dips too low. You want to minimize tree traversal on non-fill rate limited games and use brute force rendering. I've played with a terrain demo that used octrees and it was faster to draw the entire terrain by turning off octrees altogether, this was on a small terrain though as hw speed increase moderate levels might be rendered by brute force instead. Collision is different, this is done on cpu where every cycle counts so quick dismissal of geometry is preferable. Thus collision system should be decoupled from rendering system, using hand placed portals for rendering and using octree inside the sector or bsp for collisions or something like that. |
||||
|
||||
|
LtJax Member since: 4/19/2002 From: Karlsruhe, Germany |
|||
|
Posted - 12/1/2002 10:42:48 AM |
||||
| what really bothers me is that noone here seems to take collision detection into account. Of course, kd-trees ( and all forms of it, including octrees ) are a lot better for renderer culling, but not for CD where you still need a perfect set of geometry. I'm really curious what you guys are doing about that.. are you using a BSP at leaf level of the octree? or just brute force poly-soup vs |
||||
|
||||
|
JuNC Member since: 2/5/2002 From: Plymouth, United Kingdom |
|||
|
Posted - 12/1/2002 11:50:42 AM |
||||
| Well, any of the methods here can help with per-poly collision detection, it all depends on exactly how you want to go about it. For instance, to use the 'expanded BSP' line clipping technique you'll obvious need a solid-leaf BSP, if you just have a bunch of objects (say a space game), a loose octree might work best. If you have a fairly poly-soupish level, the ABT might be a good choice. Where did you get the idea you need a perfect set for CD? A conservative set will do you fine, just will take a little longer. |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 12/1/2002 3:16:27 PM |
||||
| As JuNC said, you don't need a perfect set for collision detection. What is important (even more important than for rendering) is a good localization of the tree nodes. Most structures that work well for rendering will generally work well for collision detection (although there are exceptions). Octtrees, however, are particularily well suited for CD, due to their extremely regular localization behaviour. But OTOH, that can be problematic for rendering. It's not so much a problem with smaller scenes. But with large and complex geometry, one should consider using two seperate tree structures for rendering and CD. / Yann |
||||
|
||||
|
Ingenu Member since: 1/3/2000 From: Horsham, United Kingdom |
|||
 Posted - 2/6/2003 7:28:46 AM |
||||
| Games aren't using a simpler mesh, called collision Mesh to compute collision detection ? I know a few that did or will when released. I think most do, not sure, just thinking about going upstairs makes your character move like it was on a non horizontal plane, but not on stairs... -* So many things to do, so little time to spend. *-  |
||||
|
||||
|
sBibi Member since: 3/18/2003 From: France |
|||
|
Posted - 6/21/2003 8:41:51 PM |
||||
quote: stairs are a bad example... when you climb stairs and you have the feeling to climb on a plane (like in Q3), it's stair climb smoothing, but when you go down, you'll fall on each step (or if you also go down along a plane, it isn't very realistic..) |
||||
|
||||
|
Lithic Member since: 2/10/2003 From: Kent, USA |
|||
|
Posted - 7/14/2003 6:16:49 PM |
||||
| Adding on to a way-old post... i was thinking about modifying my octree into an ABT and came across this. You said you compute your division locations via a neural net. How does this work? |
||||
|
||||
|
Lithic Member since: 2/10/2003 From: Kent, USA |
|||
|
Posted - 7/31/2003 12:32:47 AM |
||||
| Since yann seems to not be interested in giving me an answer, do any of you others know anything about this? --===LITHIC===-- --===WWW.HaVoKsite.TK===-- |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 7/31/2003 12:00:17 PM |
||||
quote: It not a question about me not being interested, but more that I can't monitor each thread 24/7, only waiting for a question directed at me. To answer your question: yes, I use(d) neural nets to get the location. But I can't really go into the details, because: A) I didn't write the NN, so I don't know all the details. B) Neural net theory is an extremely vast and complex topic, that fills entire libraries. You can't simpy explain that in a forum post. If you are interested in NN theory, and how to apply them to mathematical minimization and optimization problems, there is lots of good literature available. This subject undergoes very active research, and lots of online resources are also available. Ask in the AI forum about some good pointers. Besides this, I would strongly recommend using a conventional approach to get the division plane instead. Writing a NN solely for that task is total overkill. We happened to have one lying around, that was written for a related problem a long time ago, and so we just plugged it in. But it has many drawbacks, especially performance requirements. |
||||
|
||||
|
Page: «« 1 2 All times are ET (US) |
Last Thread Next Thread |
|
