Success tracking down that bug!
Here's a screen shot that shows a discovered portal.
The 'clip to faces' code is still missing.

Posted on 2009-06-02 03:33:19 by Homer
Having a few problems with the 'clip to faces' code.
My Portal Discovery algorithm is generally superior to the whitepapers set forth by Nathan Whitaker and Alan Baylis because each Portal is initially created to fit the dimensions of the boundingbox of the set of faces that was input to that BSPNode during tree generation.
This means that I don't need to clip portals to ALL the faces in the two leaves that they connect, I only need to worry about clipping portals which happen to be coplanar with those faces. Essentially its a 2D clipping problem, expressed apon a 3D plane.
Since the Planes (apon which our Portals are constructed) were sourced from one of the faces input to each BSPNode, we can be SURE that for any Portal, there MUST be AT LEAST ONE such coplanar face that we'll need to clip the Portal against.
In actual fact, many Portals have been constructed apon world surfaces that DONT HAVE ANY HOLES, so these are actually FAKE portals, and the Coplanar Clipping code should completely destroy them.
That's logical if you think about it - a Portal is a hole in the world geometry that connects two places... if theres no hole, there can't really be a portal, can there?
Anyway, I'm having trouble clearly defining the 'edge planes' which pass through the edges of a triangle, are orthogonal to its surfacenormal, and point outwards, away from the triangle's interior.
The technique which 'back-crosses' the surfacenormal against each 'edge vector' contains a singularity.
I am developing an alternative solution using trig-based rotation of the surfacenormal about an arbitrary axis (defined by each edge vector) in order to construct these plane normals while avoiding the singularity.

Posted on 2009-06-04 00:44:55 by Homer
I just spent hours going through the verbose debug spew to determine whats going wrong.
Turns out that the BSP Generator produces some triangle faces which are precariously close to being 'illegal' in that they are so long and thin that they are getting close to collapsing into a single Edge - and these kind of triangles dont produce very good cross products, leading to numerical errors.

I'm thinking about scrapping my triangle splitting code, replacing the Face structure with my new Polygon class (currently being used by the Portal class). This will require extensive changes to the BSPGenerator code, but will result in the BSPGen producing fewer and nicer shapes. This leads to the observation that the face geometry stored in the BSP leaves doesnt need to be used for Rendering, so it doesnt need real vertices.
If I mark my face polygons with the id of the IMPORT triangle from which they were formed, then I can easily generate a list of unique import triangles which are partially visible at runtime from the IDs of the faces in the visible leaves. This will lend itself to batching too.

Posted on 2009-06-07 13:04:27 by Homer
Making good progress.
Have replaced all the BSPGen stuff with Polygon class, and so far its good.
I import Polygons from the input Mesh instead of Faces, and I mark them with the index of the Import Triangle from which they were sourced. Then as the BSPGen splits that polygon, each resulting fragment knows which original input triangle it came from.
This allowed me to get rid of the D3D_VertexBuffer entirely, since I no longer intend to render the geometry I collect in the BSPTree leafnodes, I'll instead use them to build a list of which original Import triangles need to be drawn.

The geometry we're collecting in the leaves has three purposes:
We use this geometry to determine what triangles to draw, for collision detection (physics etc), and we use (the coplanar) geometry to clip our Portals into shape.

Yet to implement the 'coplanar polygon clipper' method, shouldnt be painful since I've just been playing with that stuff.
Moving the splitting and clipping methods into the Polygon class makes more sense than ever.
The Portal class is starting to look a bit redundant, but I'll keep it for now as its good to have a logical container for a related set of portal polygons.
Posted on 2009-06-08 02:32:38 by Homer
Well, one thing I did is to define two types of geometry.
One is a D3D-optimized geometry format, aimed at maximum efficiency for the hardware.
The other is a more generic format, useful for importing/exporting with modeling software, or for your own toolset.

In my generic format, I store all vertex elements in separate arrays, which are indexed in parallel. This way you can add and remove elements very easily. I also use 32-bit indices, so I don't run into any size problems/restrictions with things that I want to consider as a single mesh. I can also store additional topological info, such as convex polygon shapes rather than just triangle strips or lists etc. Or in the case of shadowvolumes and such, you'd want edge/adjacency lists...
I also don't have to worry about texture/material/shader issues if I don't want to. In D3D you'll want a single mesh to have a single set of textures, materials and shaders, because you can't switch in the middle of a Draw() call. But with most geometry processing, I'm not interested in that at all, I just want to process everything in a generic way.

With this intermediary format I do all preparations, and then I 'compile' it to D3D form. Mostly I'll use 16-bit indices to save memory. Most objects will fit into a single mesh with 16-bit indices. If not, they can be split up into multiple indexbuffers automatically. The vertices can also be sorted on index for maximum vertexcache efficiency, and that sort of thing.
But I don't want these restrictions during the earlier stages of processing.

You'll shoot yourself in the foot sooner or later if you want to do everything directly with D3D-structured data.
An additional bonus of having your own format is that you can recycle your tools more easily when you want to move to a different type of renderer or a different vertexformat etc.
Posted on 2009-06-16 08:33:46 by Scali
Scali - Yeah I have been using my own representations for some time, but nothing as clever or stream-friendly as you have decribed.
In this case, I've determined that I don't need to render the geometry stored in the leaf nodes of a BSP tree - those are fragments of the import geometry, to which I can refer.

Everyone - I've been moving code out of the class into the Portal and Polygon classes.
This caused a number of small headaches, which I am happy to say have been resolved.
However, I am STILL yet to complete the implementation of 'coplanar polygon clipping' required in the final stages of Portal Discovery... but I am much happier with the model overall, and believe it was worth it.
The 'utility' classes became more powerful, and the 'driving' class became more simple.
Also, I determined that the Direct3D intersection tests are inaccurate... far too inaccurate for me.
They use MMX code which is very fast, at the expense of accuracy.
In the end I have implemented my own Edge/Plane intersection test with a fair balance between speed and accuracy.
I think that's a positive outcome.

Back to that last lingering issue !

Posted on 2009-06-17 07:28:16 by Homer
Ideas on intermediate formats:
Posted on 2009-06-17 07:34:55 by Ultrano
Maybe I should write a small blog of my own... Last night I decided to try and port my D3D10 code to D3D11. It only took a few hours to get it up and running. So I'm ready whenever Bill decides to release the final :)
I'm currently thinking of actually porting my current shader-based engine back to D3D9. Some of the modifications I did for going from D3D10 to D3D11 could also be done to incorporate D3D9 back into the codebase. The old D3D9 engine wasn't fully shader-based, becasue it was built on a D3D7/8 base, back in the early days. If I remove that legacy, the remaining functionality can mostly be wrapped with a few functions and ifdefs, I think. At least I'd still have something that people on XP could run then :)
Posted on 2009-06-18 02:22:40 by Scali
Here's a screenshot showing how much nicer things are when using the new Polygon class.
My code built one big rectangular portal on the plane where the 'shelf' is (that the tigers are standing on), and then the portal was sliced with the (planes of the) left and right walls.

It's worth noting that the triangles I'm drawing for you do not exist - these are three polygons, each with 4 points, I am triangulating them for your benefit. Furthermore, I am storing all three polygons in one Portal object... all these triangles you see belong to just one portal that connects two leaf nodes !!! If I processed a real game level, I'd get lots of portals, and more complex polygons. My test model is deliberately simple and deliberately orthogonal.

Next, I need to remove any parts of the portal which are obscured by coplanar world triangles.
This will knock out the left and right ones, and trim the middle one so that only the shape of the 'hole' in the foreground should remain.

Posted on 2009-06-18 04:32:46 by Homer
Think I've been working too hard.

Here's the problem: we have two polygons which are coplanar (irrespective of whether they face the same way or not)... polygon A is permanent, it must remain untouched... we wish to clip away any parts of polygon B which are obscured by (are inside) polygon A.

My solution was to construct planes which pass through each edge of polygon A (and are orthogonal to its surfacenormal and point away from the polygon), and use those planes to ATTEMPT to slice polygon B.

Since I had other problems in my code, results at this stage were not what I expected, and so I went away to develop an intersection test for coplanar polygons to determine if slicing was actually worth doing... no intersection, no need for the clipping.

Well, after much fuss, the best way to do the intersection test turns out to be SAT.
And the best implementation, in this case, would be to transform the problem into 2D.
Then perform a bunch of edge/edge intersection tests.
I was considering using a Change of Basis (3x3 Matrix) solution, where we transform the problem into a coordinate system where X=1 and represents the surfacenormal, and Y and Z are our 2D axes for our polygon points.

I think I thought too much.

I could just TRY to perform the clipping function using those planes I mentioned, since if these polygons do not intersect, they will not be sliced. It's just a 3D version of the SAT test, a little more expensive.

Do you think the Basis Transform - based intersection test is worth doing?
Remember, the polygons are convex, but of arbitrary complexity.

Posted on 2009-06-19 23:59:08 by Homer
I'm of the opinion that even though it may sound expensive to perform the preliminary intersection check using the Mat33 ChangeOfBasis transform, but...
A) its still cheaper than the planar slicing, given we process the same number of edges
B) most of the time, the polygons wont actually intersect, so an early-out is warranted

So yes, the case of actual intersection just became more expensive, but its also the least likely / least common case.


Oh - and we dont strictly NEED to use a 3x3 Matrix solution - it can be implemented using a bunch of vec3 crossproducts and such, however noone benefits from convoluted and complex looking sourcecode, especially when it generates exactly the same binary code as a single macro invocation (a single line of sourcecode).
I just think that this is a good example of a problem that we can clearly define and solve using matrices, rather than simply using them because they are there.
The other really cool use I've found for obscure matrices in recent years is to use the Skew-Symmetric matrix to create a new orientation matrix (from an existing one) representing a rotation about a given axis.

Posted on 2009-06-21 00:26:19 by Homer
Got my problem code working, so no weird intersection tests were required.
It uses the 'edge-planes' (binormals) method I mentioned to solve the problem of clipping coplanar polygons in 3D space. The bug was that I needed to flip my Binormal and PlaneD values for my edge-planes.

Attached are a couple of images showing my results.
The BSP tree has two Leaf nodes, connected by a single Portal.
Interestingly, we can see that TWO HOLES were discovered - the Portal contains two Polygons, each containing 4 points. This is legal - these holes both connect the same subspaces, so they ARE parts of the same Portal.

This is great, I'm very happy indeed.
We have extracted portal geometry and connectivity information from a BSP Tree.
This connectivity information can be 'walked' such as an acyclic graph, and can be used with A-* pathfinding techniques to guide our AI around the world.
I was tempted to construct a 'nav-mesh' to further that end, however it might be nice if my AI can walk on the walls and ceilings etc, so I'll leave that alone for now.

Next I will be considering carefully how to represent and implement a Constructive Solid Geometry object.
These are simple objects represented by small (preprocessed) BSP trees that we can 'add' together to create more complex geometries which we might instance in our game.

When you 'add' two CSG objects, their BSP Trees are merged.
During this process, the shapes are clipped against each other, such that any 'hidden faces' are removed, and we end up with the 'union' of the two shapes.
It's a very fast and natural way to model 3D geometry, as opposed to so-called 'edge modellers', I am hoping that eventually it will help to accelerate development / level editing.
Speaking of which, I'll have to start implementing the networked editor soon.

Posted on 2009-06-22 08:39:55 by Homer
I've written a method to perform CSG addition, allowing the importing of static geometry from other models directly into our BSP Tree. However, it's NOT a BSP Merge function.

Given an input set of polygons, it feeds them through our existing tree, splitting them as required, until they land in the leaf nodes.
Then for each Leaf node, it clips the imported polygons against the faces already in that Leaf.

The result is that our imported geometry is constrained to the interior of our leaf nodes.... the imported model is clipped so that none of it lays outside our bsp tree, and its polygons fall neatly into our leafnodes. And thats where they end up - at the end of this function, the imported geometry has been merged into the leafnode.pFaces collections.

I see an obvious problem in that I need to deal with the Materials.
I'll probably tag my polygons with a ptr to the Mesh from which they were sourced, that way I avoid having to import Materials and rewrite the imported polygon material ids.

Anyway, I like this implementation because (unlike true bsp merge) it does not increase the complexity of the tree.
Instead, the imported geometry is forced to conform to the tree.
So its ideal for interactively adding smaller features to a greater world model :)

Next, I'd like to plug my physics code back in, and have a physical entity interacting with the portal system.
Physical entities can move, so they can collide with walls and portals.
If they collide with portals, we set a variable indicating which Leaf they have moved into, and let them continue on their merry way. The physics engine will need to be updated to incorporate my new Polygon scheme.

In fact, since it appears that they'll be sort of, well, not partners but maybe co-workers, I think its time for me to wrap the BSP and Physics classes (and some of the other components I've already written) under a GameEngine class :)

Posted on 2009-06-23 04:21:59 by Homer
I've added code to render the World more efficiently, leveraging the Portal information to collect a list of references to renderable polygons, and then rendering them by material. It's a recursive process which is based apon Portal visibility, it's faster than walking the BSP tree and sends less triangles to the videocard... a kind of realtime PVS. This technique is based on democode by Alan Baylis.

Posted on 2009-06-23 12:06:51 by Homer
You mean you actually go down to the polygon level when compiling a list of visible items for a given frame?
That's generally not a very smart thing to do, because it's very hard to generate efficient batches of polygons for the hardware. They don't like small batches, and they don't like the CPU poking in their vertex buffers all the time.

I just use simple bounding volumes, and test for visibility on a per-mesh basis (it's hierarchical though, if at any level it sees the volume is completely 'inside', it stops checking). In my engine, a mesh essentially means a single object that can be fired off by a DrawPrimitive() call in D3D. Essentially a batch of polygons in a static vertexbuffer, with a material (shaders, texures etc) attached to it. So that is the most 'primitive' thing D3D can render in one go.
Under about 1000 triangles it's actually more overhead to send the draw call to the hardware than it is for the hardware to draw the actual triangles.
In other words, if I had 1000 batches of 1 triangle, it'd take about 1000 times as long as rendering 1 batch of 1000 triangles. I get the other 999 'for free', so I don't really need to worry about each single triangle being visible or not. It's faster, WAY faster to just let the hardware figure that out.
Posted on 2009-06-24 19:02:17 by Scali
I wont be touching the vertex buffer - I will be rewriting the index buffer - filling it, issuing a DrawIndexedPrimitive call, and repeating if necessary. This way I am making as few Draw calls as possible, with the largest batch possible.
I've done this before with my DLOD terrain engine, it performed admirably.

Your world is obviously constructed from a large number of small meshes.
I have to pay for lock and unlock calls, but you have to make more Draw calls and touch more pages of memory than I do..

I won't be using meshes for ANY static features in my world - I'll only be using them for things that can move, like swinging doors and animated skinmeshes.

As for visibility culling, well in the past I have done exactly as you suggest - and I still use sphere tests for various things, in fact our mesh instancing class does support boundingsphere visibility testing specifically for this reason.
But I'm using a partitioning scheme and a portal system to reduce the need to perform visibility testing much beyond the immediate area around you (realtime PVS culling) - so I expect to be drawing very few polygons indeed, unless the camera is in a subspace that contains LOTS of visible portals, such as outdoor areas.
I can switch the culling scheme based on that premise I think.

Posted on 2009-06-25 01:41:34 by Homer
Well, as you say, even touching indexbuffers has its toll.
And no, my world is not constructed from a large set of small meshes. The 1000 poly thing was just an example. I make my meshes as large as they can be. I try to keep the number of meshes as small as necessary. This way I can maximize the throughput, which means I can have very high polycount while maintaining high framerates. Most of the polys are "free" in the sense that making the meshes smaller doesn't really make them faster anyway, because of the draw call overhead.

I'm just saying that it's faster to not try and cull them on a polygon level, since the hardware is much faster at drawing and rejecting at polygon or even pixel level than whatever you can think of on a CPU.
BSP has been a performance problem ever since the introduction of hardware T&L.
For terrain it might work, because terrain is not THAT highpoly. But if you start doing it on entire worlds with animated characters and objects and things, you're probably going to get relatively poor efficiency from the hardware, because you'll be holding the hardware up by constantly modifying its memory. It takes you far longer to sort out the polys and fill a new indexbuffer than it would take the hardware to just draw the polys.

A portal system optimized for hardware should just create a viewing volume based on a portal and test it against objects/meshes with bounding volumes, if you ask me. Not individual polygons. Just reject any object or mesh that is completely out. When it's partially or completely in, just draw it, let the hardware handle the per-poly and per-pixel cases. It's better at it.

Not sure what you mean by "I won't be using any meshes"... To me, a collection of polygons is a mesh by definition. You're always using meshes.
Posted on 2009-06-25 03:01:43 by Scali
I wont be making any Mesh interface calls with respect to rendering the static world.
The realtime PVS algorithm is based on work by Alan Baylis, and works like this:

I have a world which has been partitioned (via BSP) into convex subspaces, each of which contains a minimal number of polygons, and a minimal number of portals leading to other subspaces.

I (the camera) am standing in a subspace...
I check the Portals in this subspace for visibility (a sphere test COULD be used here!) .
If they are visible (to the camera), I recurse them, using a flag to ensure I don't visit the same subspace twice.
The function ends by drawing all the polygons in the current subspace, returning through recursion to the subspace which contains the camera, where it does the same thing.

The recursion depth depends on the view frustum and the style of world geometry (ie, indoors or outdoors makes a big difference here), but generally won't be more than five or six levels deep.

So I'm drawing all the faces in five or six nodes (times #visible portals, worst case) - but it gets better... Some of those are repeats, since a polygon can lay across two leaves under my model (I do break polygons, but I keep track of what original imported triangle they came from)... so I end up with a short list of triangles that need drawing, and those are tagged with their material id... so I then collect the indices of the visible triangles in per-material sets and render them as mentioned.

Posted on 2009-06-25 05:17:15 by Homer
Well, you see my problem.. You need to do all kinds of sorting and rewriting of indexbuffers. That's going to scale very poorly with polycount. It sounds like the algorithm you picked has become obsolete because of modern T&L hardware.
Posted on 2009-06-25 09:33:35 by Scali
Portal schemes are most useful where visibility is impeded.
Could be a boring old orthogonal tunnel system, or it could be a forest.
The only time it doesn't work is when the far Z is massive, and the view is not obscured.
A well designed level easily overcomes this limitation.
In this case, the polygon count has realistic bounds.
Posted on 2009-06-25 09:39:54 by Homer