Here's the virtually completed SplitPolygon procedure.
All cases are handled for tri and quad polygons being split with a plane.
The only thing I'm not doing at the moment is constructing the output geometry from the resulting intersection data.

http://homer.ultrano.com/Upload/BSP_SplitPolygon.inc
Posted on 2005-05-03 02:36:17 by Homer
Addendum : Regarding Triangle : I've added code for all cases of two edges of a triangle being intersected by a plane. These result in a new Triangle and a new Quad.

I've realized I forgot totally about the cases where one vertex is on the plane, and the other two are either side of plane. These should result in two Triangles.

The code for Quads won't be difficult as long as I don't lose the piece of paper I've been scratching diagrams on :)

How's the weather?
Posted on 2005-05-03 04:06:04 by Homer
I've now handled all the abuttment cases for both polys, and I've handled the bisection cases for triangles, and the diagonal bisection cases for quads (results in two triangles).

I have also handled the two-edge intersection of a triangle (results in a triangle and a quad), and the two-edge intersection of a quad where the edges share a vertex (are neighbours, results in two triangles and a quad)

The only remaining case : two-edge intersection of a quad where the edges share no vertices (are opposing edges, results in two quads)

If I can gather the sanity to face this one again tonight, I'll finish SplitPoly tonight.
Posted on 2005-05-03 06:30:43 by Homer
I completed SplitPoly, all cases handled, output polygons are calculated,etc.
Yay me !!

Tomorrow I'll post updated code and tie any loose ends up, then it's time to work on the BuildBSPNode recursive method which drives ChooseBestFace and SplitPoly.
Should have the new BSP generator up and running in a few more days, or less.
It should prove faster than the old one, as well as being more efficient in terms of producing less overall faces (due to ability to split arbitrary polygons into both triangle and quad fragments).
More to the point, it's built on top of the HSM code, which is recent and appears solid.

It seems like the more views a thread gets, the less people are actually reading it..
I've just made a fundamental improvement above the current generation of BSP generators, which will give me a clear advantage when it comes to collision detections (reduced plane count, plus ability to test quad plane instead of 2*tri plane)

Does this stuff interest nobody but myself?
Posted on 2005-05-03 11:02:34 by Homer
Does this stuff interest nobody but myself?

I'm trying to follow, but you're too fast :P I'm writing something like car-racer game (just to test what I've learned). Right now I'm implementing car-track collision. I think the stuff you discuss here is too complex for what I want to do now :)
Posted on 2005-05-03 12:25:59 by ti_mo_n
Not really - the track surfaces in your car game are a perfect candidate for BSP subdivisiion.
In fact, any time you have a fairly large number of "world surfaces" which you'd like to render AND be able to collide with is ok to use a BSP.
BSP is really just an organized way of storing a mess of geometry.

My new BSP generator takes HSM files as input - this is a custom format I designed for storing static models - 3d models that don't need to bend and are not animated.
I wasn't happy with the existing file formats I'd come across as they are decidedly non coder-friendly, I wanted something that kept the geometry sorted by material.
The HSM file format is the property of Homerware Studios, inc.
You may use it as you wish, provided you supply your own sourcecode with regards to Importing and Exporting these models to and from your own application(s) and/or other file format(s).
I will release public documentation on the file format soon... if you want it sooner, ask.

I've written an OBJ to HSM converter module, meaning you can make your "world" , car track or castle wolfenstein in Maya or other 3D editing software, export to OBJ format, and take it from there.

Once the world model has been converted from OBJ to HSM to BSP, we save it again, so we never need to reprocess the BSP unless the model is altered.

Using a BSP is actually very easy. Generating one in the first place is more difficult.
Once I've finished this code module, I'll be publishing three documents describing its inner working, my findings, and documentation for usage in your own games / game engines / large scale visualisation tools. As always, any code I post in public remains 100% public property, free to use, modify, use as a doorstop, etc. as you see fit.

Have a nice day :)
Posted on 2005-05-03 19:38:45 by Homer
I know at least 30 people a day are watching this thread.. who are you? :)

I'd like to talk biefly about real application of BSP in games.
As any of you who have bothered to do your homework would have surmised, a BSP is a tree data structure.
What some of you may not be aware of is that the "leaf nodes" of the BSP tree are special.
Each leafnode can be thought of as a "cell" , "room", or other empty partitioned 3D space.
If we trace back up through the tree from any leafnode to the tree root, all the splitting planes we discover actually define a hull surrounding an empty space in our world.
We can for example calculate which leafnode the camera is in, and thereby only perform collision checks against the planes which surround the camera at any given moment.
We can do this for any moving object.
Leafnodes in a BSP are special indeed !!
The partitioned spaces defined by leafnodes are not TOTALLY enclosed generally, because they have entrances and exits.
We can calculate "portal planes" which totally separate the spaces defined by leafnodes.
These are totally invisible surfaces which we can nonetheless perform collision checks against.
Portals are planes which connect two leafnodes - on one side is leafnode A, on the other is leafnode B. If objects (or the player-camera) collide with a portal plane, that object is moving from one leafnode to another - meaning we can calculate which leafnode an object is in ONCE, then track it from there.
Knowing which leafnode a moving object is in allows us to eliminate most of the world surfaces during our planar collision detection per object.
Faster physics means more time for other eyecandy, and/or more moving objects.

Honk if you love beer :)
Posted on 2005-05-05 05:10:47 by Homer
Is anyone else starting to see the motivation behind all this partitioning crap?
I'm beginning to think that I am speaking over everyone.
When I joined this board, Scronty was posting regularly in this forum.
Where are you mate?

Where are the ambitious young coders of tomorrow? Off playing Neopets?
I'd really appreciate a little more feedback, otherwise I may as well not be posting.
Posted on 2005-05-05 13:01:11 by Homer
Hey EvilHomer. I am interested in writing a lightweight (and fast) software renderer as the first step towards a full fledged game engine. I'm primarily interested in visible surface determination and scene graph render/culling, so I find your work on BSP trees interesting. I'm particularly interested in the application of BSP trees to scene rendering as a means of partitioning the drawing surface into drawn and undrawn areas.

At the moment I am debating over what language(s) or SDKs to use. Although I find assembly language very intriguing (obviously for its speed) I am a bit inexperienced at it (really more of a C/C++ programmer) and also a bit worried over the lack of support for DirectX. I don't want to spend all my time maintaining a good set of DirectX include files. At the moment I am considering programming in MVC++ for the framework and using inline asm and MASM compiled subroutine modules for the dirty work, although I am disappointed that there is no good free optimizing compiler for windows (unless you count gcc w/ MinGW ug!) Oh well, I guess that's why god made #define.

Anyway, so I'd love to hear your opinion on the matter.
Posted on 2005-05-06 07:59:54 by wildgnu
The lack of DX support has been partially addressed by several individuals including myself, but nobody has yet bothered to translate the entire set of dx headers at once, which makes sense, since dx is modular in nature, most applications don't require all of it anyway.
To put it bluntly, DX is only a lib based api anyway, so keeping up with version changes isn't too difficult its just that its COM based and so we have to use COM calling convention (which is as simple as pushing one extra parameter in our dx calls, or using a dx call macro).

What kind of software renderer did you have in mind? Realtime or not?

BSP ensures theres that occluded surfaces are not rendered.
It achieves this at the BSPGenerator stage, by splitting all the world poygons against the planes of other world polygons, so that the occluded portions of surfaces are physically split away from the original polygon into one or more fragment polygons, which are then associated with the "other" side of that splitting plane. If we walk around the corner we can see them, they are "in the next room" in bsp terms we say they "belong to the neighbouring leafnode, not the one we're standing in".
A BSPGenerator repeatedly splits the world into two using flat, infinite splitting planes which we get from the surface plane of other polygons in the world.
A good BSPGen will split as few polygons as possible through careful selection of the splitting plane during this repeated subdivision of the world, while simultaneously attempting to maintain the balance of the BSPTree by selecting a plane which splits the world into most equal halves in terms of the number of polygons which fall on either side of it.
If you think about it, these goals are mutually exclusive, but we can prevail, by using two heuristics.
My generator differs from the usual suspects in its ability to understand more than triangle polygons. I don't mean just in terms of being able to split quads with it, I mean that we can use quads when we create fragments during splitting, resulting in fewer polygons and also fewer surface planes, faster bsp generation times, faster render times, fewer collision detection calculations, etc.. leading to more time for more eye candy, more objects, etc.
An example is the splitting of an equilateral triangle.
If we split it one way, we get two equal half triangles.
If we split it the other way, we get a triangle and a quad.
Splitting a quad yields more but similarly simple cases.

We can build the output polygons in the correct direction by observing the order of appearance of the vertices in the input polygon, so it becomes quite simple to write a polygon splitter, but making a smart and efficient splitter is a little more challenging.
It's the code which drives that splitter which requires closer attention.

When you see how easy rendering a BSP is, you will reconsider its application as a VSD mechanism.
Of course, nothing can move around, or we have to alter the BSP in realtime, but that's doable too :D
Posted on 2005-05-06 08:36:51 by Homer
Yes, I would like to design a real time software renderer. I want to focus on the rendering end of the game engine equation. As I said hidden surface removal interests me. BSP trees have a lot of applications in this regard especially if you implement a quake style portal system which it sounds like you are describing. Portals are inefficient though when the number of portals is large. Also, as you said, you have to handle moving walls with care.

Besides BSP trees l am also interested in heirarchical oriented bounding boxes (OBB) as a means of culling whole scene graph subtrees before rendering as well as using quatrees and octrees to created a kind of visibility map. Not sure exactly how this would work but I have some ideas...

Anyway, it sounds like you know a lot more about the relationship between DirectX and MASM than I do, perhaps you can help me find a good small set of macros to help me get started on my way. I don't like borrowing other people's include files, I find it tedious to sift through it all and I hate not understanding the code that I am relying on. I would much rather learn the theory behind it and create my own libraries. Again my only fear is that I would end up spending so much time maintaining the library and not working on the code... Really, I want something that will work on any windows platform, I'm thinking of using DirectDraw and avoiding the whole D3D thing.

After working on the renderer I plan to focus on scene graph management issues, collision detection, dynamic objects, "AI", finite state machines perhaps... Also I am not particularly interested in the modeling side of the equation though obviously I will have to implement something with which to create test models.

Thanks.
Posted on 2005-05-06 10:18:36 by wildgnu
What you need is one of the oop object call methods.
These are almost universally macro wrappers that push "pThis" and then all other params onto the stack and then perform the call as normal.
Several well-known variants include MCALL, DXINVOKE and ICALL.

using these macros is simplicity itself. The standard format is:
mcall pClassObject, ClassName, MethodName, MethodParams

DirectX has standard exported functions you use to create class objects.
But after that you have to use the returned objectpointer in your method calls as above.
Think of it as "calling a procedure APON an instance of the object".
If we want to call code specifically apon a given "target" object, we obviously have to hand a pointer to the object in with our calls.
That's all the "pThis" parameter is, and what all the COM calling fuss is about.

Now, even though using the call macro(s) is easy and even though we don't actually have to "create" object instances ourselves, we still have to "define the class" for the call macro to work properly.

Defining a class in masm depends on which macro you choose, because each macro is from a different oopasm implementation.

Therefore, you'll need to look at an existing example in order to understand how to translate the C headers for the classes to masm. This currently HAS to be done by hand for all the above reasons, but doesn't take long once you get going. (Who knows, perhaps we'll convert you to oopasm too :) )

Personally I don't like BSP that much, but I do see untapped potential there.
I am quite taken by something you mentioned though, which is "hierarchical object oriented bounding boxes", otherwise known as OSP2.

This system is great for sparse worlds and handles moving objects better than bsp, and has a mechanism for grouping surfaces belonging to an entity.
It's a flop when applied in dense worlds however, and so its best application is really in outdoors engines.
Still, it does make me think about something thats been bugging me for a while - collision detection against the planes of hierarchical objects.
I concluded a while ago that its much faster to transform the test ray into each "bone space" than it is to transform each "bone face" back to world space.
It's something that I'm yet to actually apply.
Posted on 2005-05-06 10:40:20 by Homer
An example of what my masm based oop code looks like:

mov pBSP, new (BSP) ;<-- create instance of class
icall pBSP, BSP, LoadFromBinaryFile, CTEXT("MyWorld1.bsp") <-- call class method on my object

.. do something ...


delete pBSP ;<-- delete the object (causes class destructor to be called)


New, icall and delete are macros from "ATC", which is a set of macros written primarily by Ultrano.
You can find posts about it on this board, but they understate its potential and perhaps are not as clear as they could be considering how simple ATC macros are to apply.
I developed my D3D9 includes for/with ATC/masm.
Posted on 2005-05-06 10:55:11 by Homer
I think a combination of a BSP and OBB could be useful, the BSP part for spatial sorting during the render phase and the OBB part for the culling phase. Anyway, this is all just talk, I'd like to implement something and see just how it really performs...

As for DirectX and "oopasm" (what a word!) the part I find confusing is the vtables... So when we get an instance of the object in order to call these functions don't we have to call via a pointer in a vtable? How do we know what order the functions are in the table and what about virtual functions and baseclass functions etc???
Posted on 2005-05-06 11:07:07 by wildgnu
If we define a class using ATC, we are really defining two things, with the same Name as the Class.
ATC creates these definitions internally.
So do other oop models, but I understand ATC best so I'll talk using it as an example.

ATC creates,as I was saying, two Named thingies whose name = classname.
One is a data structure definition, whose fields are named the same as the data element fields from the class definition, plus one hidden dword used internally by ATC (so if you had three dword vars in your classdef, then the struct is 16 bytes in size).
This struct happens to be exactly what gets allocated each time we call new() to create an instance, and is basically also how COM instances are created.
New() allocates an object using Heap memory, of the size described.

The second thing that ATC defines internally from the classdef is the vtable.
This is a hardcoded jumptable which is compiled in the data segment by ATC.
We can totally forget it exists in practise, but that's what it is.

So - in response to your question regarding vtables, the whole point of using an oop macro to call class methods on class object instances is that the macro, in combination with the macro(s) used to define the classdef, do all that dirty work for you.
In reality, icall() uses the classname you gave in the method call as a guide to which vtable it should be calling a function from, and then it calls the method using a hardcoded index into the jumptable (calculated at build time).
So ATC does all the real work at build time, calls are fast (very little overhead), objects are on a growable heap, anything else? :)
Posted on 2005-05-06 11:20:28 by Homer
Note that we can apply this stuff to existing classes like with DX, and/or with our own classes.
Writing code using oop and asm at once is extremely liberating and addictive.
Your code gains the best from both worlds so to speak.
Not only that, but we can use this as a bridge to call code written in VB for example.
Or we can write a superfast OCX in sweet oopasm and market it to VB coders.
I'm sure you can think of ways you can gain from using this stuff.
For me, it began with ATC's malloc() macro, which it internally uses for heap allocations but which me may also merrily use along with its partner free() macro.
I hadn't even looked at the oop aspect and I was already hooked by the elegance of these macros, and their seemingly limitless application potential.
Posted on 2005-05-06 11:28:58 by Homer
Ok, so how do I sign up? I'd like to digest the inc's though and really understand what is happening below the surface. No matter how easy it may be to use these macros I still think ignorance is not always bliss when it comes to programming.
Posted on 2005-05-06 12:02:39 by wildgnu
Ultrano hosts ATC at his site, http://www.ultrano.com
You can get the very latest version there.

He also hosts a little dump for me :) http://homer.ultrano.com
You can find some related junk there, which was written for prior versions.

ATC is now in version 34, which equates to roughly one version update per year up until this point, however don't hold your breath waiting for a new version as it's pretty much finalversion now.

There are other oop models to investigate too, I am most familiar with / prefer this one
Posted on 2005-05-06 23:17:20 by Homer
Actually, the link is http://www.ultrano.com/ilix
Also, there are some tutorials that cover the basic stuff of ATC (they're 1 year old) there . Some of the tutorials show you how to make ATC show all the code it generates - which is exactly what you said you want :) .
Other tute iirc shows how to make ATC generate automatically the skeleton of all methods (procs) your new classes need.



A brief tute to the newest features in ATC can be found here:
http://www.asmcommunity.net/board/index.php?topic=17987.0

Ah and "equates to one version per year" ... hmm I thought this month I turn out only 21 years old :)
Those "versions" are actually the count of features ATC has at some point. When I add some new feature (or a group of features) , I increment that "version". ATC started off like a simple C++ class wrapper to turn out like a tool to aid me complete much more work faster ;)
Posted on 2005-05-07 06:45:50 by Ultrano
Roughly one version per year since I first got involved with it, it was an educated guess..
It's a feature count? Now I know something else I don't care about and will never use :)

Ultrano - Hope all is well in your world mate.
Mine sucks at the moment, you could write a song about it.
First my dog went missing, then my girlfriend left me for her ex who happens to be a friend just to complicate things, then my epox based box decided to spontaneously combust...
I'm struggling to smile as I install masm on a 333 and look around for my wallet...

wildgnu - I did not elaborate on the shortcomings of ATC, which is unjust.
It is single-inheritance, like C++ is.
Each class can inherit from one, and only one, previously-defined class.
I am unaware of a depth limit, but if there is one, it would be masm's 30-something nesting depth limit.
Base classes don't inherit from IUnknown, they don't inherit from anything.
If you want to use ATC with COM, you need to look at my example D3D9 stuff.
You will see that I either define IUnknown class and inherit from it, or I redefine it at the start of each class, depending on which example you are looking at (I left my early examples in their original state so that other authors could follow my trail).
As Ultrano stated, ATC was written as a C++ wrapper.
He wanted to call C++ stuff from asm.
Then he saw he could do the reverse.
Then I pointed out that it could be adapted for COM support.
Then my code started looking very different..

Personally, I am totally in love with ATC.
Nonetheless, as I have said previously, there ARE other models to investigate.
Some of them are more elaborate than ATC.
They inevitably pay a price for it (generally in call overhead), and since I am into speed and lowlevel code, I love ATC. If you are smart you will shop around. I am sticking with what works for me until I have a damn good reason not to.

Posted on 2005-05-07 07:42:33 by Homer