Jump to content

  • Log In with Google      Sign In   
  • Create Account

__Homer__'s Journal



You wish, but you don't have the cahones

Posted by , 23 December 2011 - - - - - - · 586 views

I went from -2 to -33 from a single post.
Well on track for my -666 !!!

In the meanwhile I've been quite busy, working on commercial projects.
I bet the people who voted me down have not even got a job in the industry !!
Vote me down more!! I need to reach my goal!


Wankers

Posted by , 05 December 2011 - - - - - - · 611 views

Now my current score on this crap forum is minus 2 - after they agreed minus scored would not happen.
Can i reach - 666? :)

Yours Truly, for saying nothing more than the truth.


GCAP

Posted by , 29 November 2011 - - - - - - · 413 views

I was invited to gcap - and stood around outside, hawking my wares like a whore, and it felt so right.
Thanks to all the people who stopped to play it!


Metal Clad Men On Horsies - With Sticks!

Posted by , 29 October 2011 - - - - - - · 382 views

Announcing the upcoming IGF student division finalists, http://studentgame.caswal.com/Jousting/index.html


I like cheese and zombies and the rest is commercial in confidence

Posted by , 27 October 2011 - - - - - - · 281 views

Today I got my fledgling newchool opengl engine launched.
It flapped around, at no stage did it fly, but it did not fall over, and it did not disgrace itself on the way out!


"Infinite" number of lights - breaking the hardware limits

Posted by , 15 October 2011 - - - - - - · 300 views

It's a small blog mention @ http://www.asmcommunity.net/board/index.php?blog=751;sa=topic;id=51

Here I describe a way to breach regular hardware limits for the total number of lights, without sacrificing the minimum framerate, and while considering shadowcasting in the same step.


Bullet physics 0, game implementation stuff 1

Posted by , 25 August 2011 - - - - - - · 778 views

So on another topic, I'm currently working on a game involving medieval jousting (yes, horsies, mounted by metal-clad men..) and we've glued some kinematic rigid bodies to various joints of our warriors (shields, lances, so forth).
I was happy to set up physics under Bullet to drive the kinematic bodies around via a custom MotionState,
But when it came to finding collisions between two kinematic bodies, I was deeply depressed.
You see, Bullet does not apply physics response forces to kinematic bodies.. only dynamic ones (the third type, static, are not even worth mentioning). Since it doesn't need a response, it won't bother to generate any contacts for those collisions. So you can't use a 'OnContactSomething' callback to receive notification of a collision.. you are left with having to poll for it, or you will never know it happened. I guess that Erwin expected that there will only ever be one kinematic body and it's your guy smashing stuff out of the way? Not good enough.

So why were we using kinematic bodies in the first place, if dynamic bodies generate contacts like we wanted? Because you can't directly control dynamic bodies as such - you have to use forces to push them around, and this doesn't give you a reliable control mechanism when you just wanted to specify where something is at a particular time.

Our workaround was rather novel so I thought I would blog it here.
For each animation-driven kinematic body, glued to some bone (joint) by a MotionState, we would create a dynamic body, which shared the same CollisionShape, had the same world translation and orientation, and had the same local origin/pivot - and we would then create a constraint to glue the dynamic child to the kinematic parent.
We used a "Generic 6DOF" constraint, with "all degrees of freedom locked" to basically transfer motion from the kinematic body to the dynamic one.
This made the collision pipeline go absolutely crazy (debug build) since there was some bodies that are always 'perfectly intersecting' - the GJK separation solver runs about 1000 iterations per frame and keels over, ugh this is not good...
Then we used the most coarse level of collision filtering offered ('Collision Groups' basically) to eliminate the kinematic bodies from the collision pipeline, leaving only the dynamic ones to collide.

Now we were able to 'directly' drive dynamic bodies from outside the simulator, as well as rely on the contact callback notification of the collision event(s).


Portals are almost correct too

Posted by , 22 June 2011 - - - - - - · 209 views

Re-enabling the culling of portal polygons during their Clipping phase paid off - I am now detecting five portal quads are being eliminated during the search for 'true portals', and their geometry matches that of the inner box faces - I have eliminated my 'fake portals' correctly.
The sixth and final leaf now contains 4 portal references, none of which lead into the interior of the inner box :)

I can see one remaining problem: two of my portals contain 5 polygons, where there should be 4.
Furthermore, there appears to be a pair of quads with the same geometry (actually they differ by 0.00000002).
I need to look into that.


STAGE ONE COMPLETE

Posted by , 20 June 2011 - - - - - - · 355 views

I found a very fast way to get the results I was looking for in terms of dealing with the 'closed, unreachable space' in the test model (ie, the space inside the inner box).

I modified the ChoosePartitioningPlane function so that it will always return a plane from the input geometry, as long as there is one that has not already been used before. It will prefer to divide the geometry evenly, however if it can't find a plane that partitions the geometry, it will just return a plane that hasn't been used yet.

The results are similar to before, but important differences exist... and the results are actually NOT what I expected.

We still get six convex leaf nodes, however they are now all closed convex hulls - they are correct !!
The tree contains geometry in all leaf nodes, INCLUDING the last leaf node - there are NO empty leaf nodes representing places we can't go - the empty space is not part of our bsp tree at all !!!

We now get 10 planes examined, instead of 5.
They are marked as being Used, but in fact only the 6 planes of the inner box are used to construct the tree, and of those, only 5 represent Portals.
The BSP Tree is not made unnecessarily complex.

GREAT STUFF !!! WOOHOO !!!
Now on to the Portalizer again :)

We are still only getting 5 Portals - this is correct.
The extra planes are generating a lot of extra portal polygons due to more 'shattering', however I have implemented code to Weld them together later, where I detect that they were split unnecessarily.. the current result is a grand total of 14 portal polygons connecting our 6 subspaces.

There are definitely some redundant portal polygons being generated, which are not being appropriately Clipped.
They are coincident with some of the visible faces in the leaves they connect... that is to say, they not only share the same plane as one or more triangles, they are likely to be overlapping with them on said plane - conceptually, we wish to use the triangles to 'mask out' parts of the polygons that are within their bounds.
My portal-poly clipping function ignores polygons which are behind or coplanar with the clipping plane, so they slipped through the net.
I was hoping to avoid clipping of coplanar polygons as this is non trivial and prone to error... and I've had enough trouble with polygonal splitting and merging operations as it stands.
However, maybe I can still avoid it.
I have a theory that, if all previous operations were correct, the redundant portal polygons coincide EXACTLY with some coplanar triangles in the leaf. I should be able to use a process of elimination to decimate each polygon against coplanar triangles, and do it from my existing clipping function. I know it will work for this example model, I THINK it will work generally... this is revisiting the concept that a convex subspace is completely closed by the planes of its faces and portals.


A special case of a closed subspace

Posted by , 20 June 2011 - - - - - - · 401 views

Wrapping my Line/Plane intersection tests in a simple Macro helped to make the case handlers for the triangle splitter more consistant and helped knock out the bugs.

I have been studying the logged output of my tree generator, and using that information to step through the same process in the 3D modelling tool originally used to construct the current test model ('Box In A Box').
Attached are some screen shots.

My implementation chooses to make the first cut through +Z side of the inner box.
This results in 16 triangles on the 'front' side of the plane, and 24 on the 'back' side, when I perform this step in my modeller, the result is the same.

My impl. next chooses to cut through the -X side of the inner box.
The results this time are 13 to the front, and 20 to the back, again this agrees with my modeller.

My impl. then chooses to cut through the +Y side of the inner box.
The results now are 13 to the front, and 16 to the back.. My modeller disagrees, it does a better job than me of triangulating the polygons - My triangle code does not attempt to optimize/simplify the tesselation.
Its results are 11 to the front, and 16 to the back. Not bad though.

This goes on, until 5 of the 6 planes of the inner box have been used as splitting planes.

Anyway, the problem I currently have is related to the very last subspace we discover, and is due to the fact that my model contains a CLOSED SUBSPACE which is SOLID, ie UNREACHABLE (we think!)
Consider this last face of the inner box, surrounded by four of the five used splitting planes.
As we used each splitting plane to carve away at our model, we 'stole' a face of the inner box.
These faces are now in the other leaf nodes.. leaving only this one unused face, plus a bit of the outer box, in the last leaf node, parallel faces pointing at each other. This is actually a convex set, we can't choose either of these two planes to split the set. The problem is that our node thinks that it includes all the space INSIDE the inner box, as well as the remaining space outside of it.
It is worth noting that this problem subspace is a BACK LEAF, and in this example, happens to be the last and only back leaf.

One possible solution I am considering is to impose a constraint that states all back-facing leaf nodes must be EMPTY of polygons - if a leaf node is discovered which is found to be the back leaf of its parent, we will shove the faces down one node further, forcing selection of a splitting plane from those available. This means that only FRONT leaf nodes represent OPEN subspaces where the player can go, and BACK leaf nodes represent illegal void subspaces.

This solution seems perfectly viable until we reconsider our example, and note that we don't actually have any way to determine which plane from a convex set is actually valuable to us !! We know that it can't have been already used as a splitting plane, but otherwise, our plane selection algorithm doesn't know how to choose among these convex faces which plane to use in this final step.
Of course we know that a face which is part of the world's outer boundary is a VERY POOR CHOICE - this will always be true.
But there are bound to be cases where simply choosing the face closest to the world bounds will be the wrong choice.

Actually, it might be more appropriate to make my constraint even more forceful.... I might stipulate that every face in a subset must exist on a used splitting plane. This will absolutely guarantee that all potentially problematic closed subspaces are indeed fully closed in the bsp sense (unreachable subspaces will not be reachable by the point-in-open-leaf test), at the cost of unnecessary (but minor) tree depth due to the mindless inclusion of planes on the world's outer bounds - however I can think of lots of reasons FOR including these planes, so I am happy to go along with this as the final solution unless anyone has a better idea.

I would love to hear your thoughts, people!

Attached Thumbnails

  • Attached Image
  • Attached Image
  • Attached Image
  • Attached Image
  • Attached Image
  • Attached Image



Almost Normal

Posted by , 14 June 2011 - - - - - - · 247 views

Major bug located in my triangle-splitting implementation.
My algorithm for finding the intersection of a line segment (ie 'edge') and a plane expects the two endpoints of the line segments to be handed in a particular order, which I was not observing in all cases.
The result was that some child triangles were being created with incorrectly interpolated vertices, directly leading to them being incorrectly classified in subsequent iterations of the tree generating algorithm.
I hope I fixed all the cases, I will check them over today. I don't want to continue to examining the portal generator output until I am absolutely convinced that the tree is correct.
This brings me to a small point of contention.
The surface normals for some of my planes are being returned as 0.99999994 rather than 1.0 , and although this inaccuracy might seem acceptable given my planar tolerance of +/- 0.005, rounding errors such as this quickly add up over several recursive iterations - and especially so when we are bisecting space !!!
Should I be clamping normals to 0 and 1 when they are very close to being so? This assumes that there is much orthogonality in the 3D world, which I guess is a common scenario, even today. But given that I expect to handle organic shapes too, is clamping a good idea?
The fact that my Normal is not always exactly unit length for a plane aligned to a Major Axis is a bit of a concern.
What would you do?


Progress Report

Posted by , 07 June 2011 - - - - - - · 228 views

More bugfixes and improvements.
The ChooseSplittingPlane method no longer returns planes which don't partition the input set, and its heuristic has been changed to take note of the number of triangles split by a candidate plane.
A bunch of small code changes and bug fixes were made, some enumerations were modified, the ClassifyTrianglePlane method has been changed to return more information, etc.

I am now getting 6 subspaces, separated by 5 planes... the subspaces contain different numbers of portal references, and the portal geometry contains references to the two leaves connected by each portal polygon.

Things are a lot better, however I'm not convinced yet that they are perfect.
Regardless, it's probably time for me to add some DebugRender stuff so I can digest the results of each iteration more quickly without having to study all the output data too much.

I'll probably post an update from Uni tomorrow.


It's Not Too Late - to Clip it, Into Shape.

Posted by , 03 June 2011 - - - - - - · 319 views

Shave and a Haircut?


When a problem comes along, you must Clip it ;)

At this point, most of the BSP tree will no longer be of any use to us - our leaf nodes, which represent our convex subspaces, each contains a list of 'portal fragments', some of which are actually 'duds', which must die, and others need some cosmetic attention.

For each leaf node, we will clip its portal fragments to the planes of the visible geometry in that leaf.
We will discard any resulting fragments that are found to be 'back' ie 'behind the plane' since they are not inside this subspace. This may involve discarding entire polygons..if its point away from us, or its totally behind any plane of our hull, then its not part of this subspace.
The front parts and the coplanar parts we will keep. These are the parts that are within the bounds of the current subspace. Actually I expect not to get any front parts, but we'll see.

What we are doing is constraining the portal geometry to the exact shape of the voids in our otherwise closed convex subspace, without violating their geometric constraints, such as existing apon one of the planes that bounds the subspace's closed hull.
To be clear, our subspace is an open convex hull, which is closed by planes of its portals. So our subspace has visible, solid surfaces, and it has some 'holes' that lead to other places. We have just discovered the exact shape of these holes. All that remains is to determine where they lead to, and do something useful with that information.
OK Wait - there is one final tricky special case to handle, but it can wait for my next post.

Planar Polygonal Mating Rituals


So, we have reduced our set of fragments per leaf to a relatively small number. As a matter of fact, the only remaining portal polygon fragments are those which fit inside the shape of the holes, on the planar surfaces of our subspaces, ie, collectively, they represent the shapes of all the holes that connect any two subspaces in our world.
Note that each fragment is tagged with the ID of the Portal that originally owned it.
Now we reach the moment of truth - Connectivity.
For each leaf, and for each unique portal ID in that leaf, find another leaf which contains a portal fragment with the same ID.
These two leaf nodes are connected by this portal! Only two leaf nodes can contain pieces of the same portal, due to the fact that our partitioning scheme is bi-fold.
Move all the portal fragments which bear that Portal ID back into the owner portal, discarding the fragments in the 'other' of the two leaves (since they're 'clones'), and add to each Leaf a reference to said owner portal, and tag the Portal with a reference to each Leaf it leads to.
End Loop.

Now, each leaf contains no portal fragments - just visible triangles once more.
Each leaf contains a list of Portals that lead to adjacent subspaces, and each Portal knows which two subspaces it connects, and the shape of the connecting hole as projected apon a unique 3d plane on the surface of both subspaces, with respect to the first of the two (order of discovery).

We now have everything we need to construct a cell and portal graph - in fact, we have already created it :)


Improving the Partitioning Heuristic, and Marching On

Posted by , 02 June 2011 - - - - - - · 236 views

The problems in the tree generator and portal generator seem to be fixed.
I am now able to discover all the convex subspaces, construct the portals as BFQ's and then 'shatter' them against one another.
However before I post the updated sourcecode, I need to eliminate a bunch of runtime tracing/debugging stuff that helped me track down the bugs, and I'd like to have a go at improving the heuristic for selection of splitting planes (in the bsp tree gen).

I will note here that this endeavor is pretty much redundant, since I do not intend to use the BSP tree structure at runtime (as such).
However I will for the sake of completion go on to explain what its about.

Can we do better?


The current heuristic treats the input set of triangles as a 'point cloud', choosing the plane which most equally bisects the vertices for 'best balance', without considering the geometry - the shapes involved. It does not care how many triangles the plane passes through, and makes no attempt to avoid doing so. This generates an inordinately high number of fragment triangles during bsp tree generation, and for me it's going to mean more duplicate triangle references to either filter or pay for in terms of pixel overdraw.
.
Our heuristic for selecting splitting planes should attempt to fulfill two goals simultaneously: good balance (don't favor one side of the tree too much), and fewest possible splits (avoid generating too many extra triangles, leading to extra tree depth). These goals both seem to make the tree not be too deep.
Although not immediately obvious, these two goals are in fact mutually exclusive. That, however, does not prevent us from designing and implementing a heuristic which tries its best to meet both objectives.

What we can do is attribute a 'fitness score' to each potential splitting plane, based apon the number of vertices falling on either side of the plane being similar (good), and the number of triangles that are cut by the plane (bad). Then we'll just return the candidate whose score is 'best' (which is a subjective term, depends on how we calculate our fitness score, but will typically be 'highest' or 'lowest').

What's Next?


Now we have our Portals (one per non-leaf node), which were constructed as big fat quad, each apon one of the unique 3D planes we used to construct our tree. Each Portal object is a container for a bunch of convex fragment polygons resulting from the shattering of the convex BFQ polygons. We will now 'march' all the fragment polygons down the tree starting right from the very top (root node) until they each have landed in a leaf node.

Important note about this process:
Since the fragments are, collectively, the result of splitting every BFQ against every possible splitting plane, we can never have a case of a fragment being split by a plane during its 'walk' down the tree. If we do, we did not shatter the BFQs correctly.
We can take advantage of this fact... it implies that ANY point in a polygon will return a point/plane result that is true for the WHOLE polygon.
There are two small exceptions - the first is when our test point returns a Coplanar result - we'll need to try another point (or points) until we get a definitive result. But the odds of us picking a valid point on the first try are very good.
The second exception occurs when all the points of the fragment turn out to be coplanar (with the current node's plane). The implication is that all OTHER fragments of this current portal will also be coplanar with this current plane. This case needs special handling.
If we detect a fragment is coplanar with the current plane:
For every fragment in the current portal, duplicate (clone) the fragment, send the original down to the front child, flip the cloned fragment's surface normal (ie, the x,y,z components of its plane), and send the clone down to the back child.
The reasoning behind this will become clear in the final step, where we seek to mate the matching 'sides' of each Portal (since a Portal has two sides, each facing into an adjacent subspace). We have just ensured that there are indeed two sides, and that they indeed face into the correct subspaces - the last part ensures that they survive our next step: Culling and Clipping our Portal Fragments.

So, for each fragment, get a polygon/plane result (whether the 'long way' or the shortcut I've suggested), and (excepting those special coplanars) send the fragment intact to the corresponding child node, and repeat, until we can't anymore.
We should end up with our portal fragments in a jumbled mess, neatly contained in a single list in each and every leaf node.
We expect that all leaf nodes will receive portal fragments. If they don't, it indicates a 'solid subspace' which is somewhere the player should never be. Anyway, so each leaf now has a list of portal fragments, each tagged with the identity of its 'owner' portal. And we have our list of portals, now completely empty of any portal fragments.
We will now clip and cull the fragments - many will not survive this process. Those that do are our 'true portals', and their shape represents the exact silhouette of the portal, the shape of the 'hole'. I'll talk about that more in my next post :)


Trials and Tribulations

Posted by , 31 May 2011 - - - - - - · 309 views

I've decided to spend a few hours hardening the current codebase through a series of exhaustive tests apon the triangle splitting code in the tree generator - I seem to be getting unreliable results for some reason (occasionally the output is not the same) and I need to understand why this is so.

I've been thinking about changing my Triangle class in the bsp tree gen too - and you haven't even seen it yet.
Looks like this:
// Defines a renderable triangle during tree generation
class Triangle
{
public:
	Triangle(int iOrig, int iA, int iB, int iC):iOriginalIndex(iOrig), ivA(iA),ivB(iB),ivC(iC)	{	}
	~Triangle() {};
	// Vertex Indices
	int ivA, ivB, ivC;
	// Index of original triangle (since this triangle may have been 'fragmented' during tree generation)
	int iOriginalIndex;
	D3DXVECTOR4 Plane;
};

As you can see, each Triangle records its own Plane, this eliminates looking up the plane at runtime, a trivial optimization of a frequently performed lookup operation, which adds up quickly to provide a nice overall speedup.
Now, even though I am providing the plane for each triangle explicitly, the code for selecting a partitioning plane seems unreasonably slow (maybe its just my ASM background)... I am considering either replacing the vertex indices with pointers directly to the vertices, or just keeping the vertices in the triangles themselves. Either would effectively eliminate vertex lookups during the extremely cpu intensive task of selecting a partitioning plane. It also means I never have to record any geometric data that was generated solely due to splitting visible triangles (except within the triangles themselves) - I can leave my VBs and IBs alone.






August 2016 »

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28 293031   


PARTNERS