My OBJ File Importer project has grown a BSPTree Generator :)
I can now throw together static worlds in MAYA, save them to OBJ file format,
then use my BSPGenerator to load them and convert them to BSP.

At the moment, I don't actually do anything with the completed BSPTree.
I don't even save it to a file - I'm still trying to decide on the file format specifics, and I have not implemented surface textures completely in the OBJ importer.

However, my debug logfile indicates that the tree is being generated correctly, and is being generated quickly due to precalculation of surfacenormals.

I'm using the "exhaustive search" method.
Each Node creates front and back Lists of polygons from an input List, then recurses them.
Front and back lists are derived by classifying the input List against the "best splitter plane".
The "best splitter plane" is calculated by comparing every triangle's plane to every other triangle using two? heuristics (because we have two goals - fewest splits and best balance).

My leaning for the BSP file format is towards the Quake formats, which store the binary tree as a binary string, and the rest of the data as "chunks", with a "chunk directory" near the start of the file.

In retrospect, the reason why this BSPGenerator project went smoothly is because I went for the heart of the beast, writing the core procedures first, testing each, then writing each driving layer of code around the previous, working my way back toward the entrypoint.

http://homer.ultrano.com/Upload/BSPGenerator.zip

Posted on 2005-03-15 09:08:15 by Homer
Today I made a really heavily intersected test object in maya
http://www.homer.ultrano.com/Upload/intersection.jpg
and threw it at my BSPGenerator.

It fell over.

...but...

I fixed it !!
The bug was due to me forgetting to store new UV values in RawUVArray when new Polygons are created due to Splits.
I now do so, and everything is wonderful - my BSPGenerator is no longer tripped up by complex intersections :)

Posted on 2005-03-16 01:35:49 by Homer

I added optimising of UV Coordinates, including those generated by Splits.
I'm ready to write the Binary File Format, and the Save and then Load functions.
Before I do, I want to rename some of my existing structures, because they can be refined more than those required by the Importer, eg I'll rename BSPNode to BSPGeneratorNode, etc.

After I write the save/load stuff, I'll write code to render the tree with respect to the Camera.
Does anyone care?
Posted on 2005-03-16 03:49:23 by Homer
I renamed stuff, added code for printing Console text via orthoquads and for loading the Font bmp from the exe's resources, reintroduced the MeshLoader and BSPGenerator code into an OpenGL Skeleton, and partially revived my old Console class.

I designed the BSP binary file format, but did nothing about implementing it.

I don't really want to write a BSPTreeRender until I've written the Save/Load procs.
Posted on 2005-03-16 07:21:01 by Homer
The BSP binary file format is complete.
The file format is as follows:

dword HEADER = HBSP
dword VERSION = 1
dword NumTextures
stringarray TextureNames (a zeroterminated array of zeroterminated strings)
dword NumVectors
vec3array VectorsData (an array of Vec3 values for vertex Positions and Normals)
dword NumUVs
vec2array UVsData (an array of Vec2 values for TextureCoords)
dword NumFaces
facesarray FacesData (an array of POLYGONs stripped of their SurfaceNormals)
dword NumNodes
nodesarray NodesData (an array of NodeIDs in BSP Recursion Order)

The NodeIDs are actually face indices for splittingplane polys.
Special NodeID -1 means LeafNode (terminal branch of tree).

Note that a polygon is a triangle is a face.
When polygons are created, they are added to the PolygonManager, and their
index in order of creation is recorded within them as the PolygonID.
Thus face#0 has ID=0, face#1 has ID#1 etc

When polygons are selected as SplittingPlanes, their PolygonID is recorded
as the current Node's NodeID ... thus a NodeID = a Face Index.

The NodeIDs are recorded in order of appearance in the BSPTree.
The rootnode id is always first.
For each node, the front is recursed, then the back.
Thus the order of appearance of NodeIDs implies the BSPTree topology.

Is anyone reading this?

Posted on 2005-03-16 21:25:54 by Homer
I keep an eye on :)
Posted on 2005-03-17 01:37:37 by TBD
Joy - I have a total of one serious reader.
I know I haven't posted any source for this stuff yet - but nobody has asked yet either.
In fact, this is the first expression of interest in this topic at all, aside from a guy called zabnik who was interested in BSP around a year ago - as far as loading/rendering Quake files at any rate.

I am seriously disappointed in the lack of interest in this topic among asmcoders in general, as BSP is a natural solution to a number of hierarchical storage solutions (disregarding the current implementation).
At the same time, I've grown used to disappointment in others.
It's myself that I ride with a whip.

Posted on 2005-03-17 03:46:23 by Homer
yes, zabnik implementation of BSP (called ProbnikGl) was interesting, but unfortunately he disappeared after the beta release and no word from him since.
I think people will became more involved if they can "see" something - for example a simple map loaded from OBJ in a 3D viewer.

zabnik's ProbnikGl had a "wow" factor but didn't atract much response either - too complicated ? hard to modify/mantain ?
Posted on 2005-03-17 06:01:50 by TBD
Actually, zabnik's version of a BSP loader/renderer was more simple than my first attempt.
It loaded the binary BSP file, then used its data directly.
I intend to follow his example when I write my (custom BSP file) loader and render code.
There's no need, for example, to create a Tree structure in memory to hold the BSP nodes.
It's possible to walk the nodes directly from the file data.

Obviously, the main difference between my current attempt and the previous is that this time I have implemented the BSP generator itself, rather than just loading a BSP generated by someone else's tool.
This time I understand the format of the data in the BSP intrinsically and intimately. Last time I did not.
I was working blindly with linked structures of which I had little comprehension. He got it first time.

Even though his code (and his approach) was quite naive, I nonetheless learned a lot from it.
Simple Is Good.
Posted on 2005-03-17 06:54:55 by Homer
A couple of years ago I was heavily involved in asm coding for graphics and looking into several tree structures.  ( I used to work for Silicon Graphics and Pixar).  Haven't done one thing since but always look at your stuff and am jealous I can't do what I really want to do right now.  Too many other things going on...like making money.
Posted on 2005-03-17 07:09:04 by drhowarddrfine
I, as a user, don't care what is behind, that it used BSP nodes within Tree structure or another "buzzwords".
I care that it works, it is easy to use and loads fast and I dont have to start multiple conversion programs to load my 3D.

you took the right step in learning the BSP by creating a generator and not use already made BSPs. now you must take
the hardest part - create a user experience that is fun and enjoyable.

I saw a lot of interesting implementation, with complicated algorithms and great results - but all were forgotten/moved to trash bin
as they complicated too much the user interface :(

... as you said "Simple Is Good". keep that in your mind and we are looking forward for the next steps.
Posted on 2005-03-17 07:10:57 by TBD
I found and fixed a small bug in the BSP generator today.
Normally, nodes are assigned the ID of the Polygon chosen for the splittingplane.
That is to say, a node chooses a polygon to use for splitting, then copies its ID.
If a node contains only one polygon, we don't bother choosing a splitting plane.
The ID of the ONLY polygon is assigned to such a node.
I'd forgotten to do that, and as a result, I was not recursing the last node in each branch.
I was stopping one node short during BSP assessment, which meant that the last node
in each branch was not being recorded in the binary file.
I'd become sloppy with my debug logging as I figured everything was right.
It looked right, it smelled right.
The debug logfile clearly showed that the last node wasn't being assessed, and I'd not noticed.
It now contains so much information that the actual tree structure is apparent to the initiated.
I'm quite proud of finding that last lurking quirk and fixing it so quickly and effortlessly.
Earlier on, I reworked some of the Console code so that it supports embedded colour codes in text strings.
This is pretty much a gamer standard, I used the ^ hat symbol to denote the start of an ascii hex value which is the colour code, and another ^ hat, a space, or indeed any non -"capitalized ascii hex character" to delimit it.
I got the idea from a couple of games that use numeric colour codes like ^1=green, but decided
that it would be much more powerful if full RGB colour statements could be embedded, and so
I decided to embed actual hex colour codes directly as ascii hex.
This means strings can look like "^FF0000^Hello, and how are^FF YOU^8080^ today?"
The format is RGB, but you can specify the colour dword in whatever length is suitable.
The first attempt wasn't good - I'd made a wrapper for a procedure that prints whole lines, and consequently, the colour for a given line consists of the most recent colour only.
I have a solution to this problem which will allow multicolors on a single line, I expect to have it implemented later today.
At the moment the console is crippled - there's no keyboard input, no code to control it opening or closing, etc... most of that code was not stored in the Console class, and as a result it was too messy to import it into the current project. I will take the time to remedy this for future projects.

Posted on 2005-03-17 15:53:01 by Homer
As expected, I have finished implementing embedded colour tags in Console text.
Here's a screen shot (nothing extravagant, but you get the idea)
http://homer.ultrano.com/Upload/Console.JPG
Posted on 2005-03-17 19:07:48 by Homer
I reimplemented basic keyboard controls (esc=quit, F1=toggle fullscreen)
Had some annoying flickering when in fullscreen mode, resolved it by modifying messagepump.

I'll probably add a few more keys for scrolling, opening and closing the console before I write code to render the BSP (directly from its filedata).
At that point, I'll want to revisit my Camera code once more.
Posted on 2005-03-17 23:18:55 by Homer
This post isn't really in the right place, but I don't know who I'm catering to any more, so here goes:

My console is an implementation of orthographic textured tiles, via a DisplayList.
That is to say, each "printed" character is actually a 3D tile with the character's texture on it (taken from one "font bmp"), rendered with orthographic projection to some 2D screen coordinates.

There is a "glPrint" function which is independant of the Console code (but Y is at screen bottom), then there is a "ConsolePrint" function which is a wrapper for the former (it corrects Y to screen top), then there is a "ConsolePrintColour" function which wraps ConsolePrint (it handles embedded colour codes).

I create a DisplayList for all possible characters (0-255) as orthographic tile objects.
The glPrint function draws elements of the DisplayList as indexed by characters in an ascii string - cool, huh?

Would anyone like to see a tutorial on printing text in OpenGL via DisplayLists and a font image?

Posted on 2005-03-20 02:05:23 by Homer
First, to say I always look at your posts with interest - but since you are always writing on topics I know almost nothing about, I dare not post . I don't ask about src because I probably won't understand - been trying to understand 3D by your code, but the fpu instructions make it hard for me now(I got too used to C). On top of that, I barely have time to code in x86 asm lately T_T, so I can't be of much help T_T.
Now I'm finishing my last (not latest) PDA game - my 3D engine fit perfectly in it, been composing music for it all night, and I think I just have to improve my 2D artwork and add sfx. Won't be making any more PDA games, I'm not even sure on what platform will be my next assignment - but anyway I really like making games. So after a few weeks I'm planning to start making a complete x86 asm 3D game - a spaceship-shooter. I'll need to code a simple OpenGL engine, then I'll be much more open to your 3D code . But I doubt a BSP engine will be necessary ^^".

On the topic: I read somewhere that portal engines are better for high-end PCs than BSP, is that actually true?
Could you send me your BSP src now ? + the displaylists code
Ah, and I don't see you in ICQ anymore - do you use any IM (I have most of them) - it'd be nice to chat again like in the old times

Ah and don't be upset for the lack of interest here - my 2D engine "Ilix" got the same number of interested people, despite it being a very useful engine for MDI apps. Lots of C++ coders want DDraw-accelerated MDI, and lots of C++ coders want BSP code - yet the interest rate here is almost zero.
Posted on 2005-03-20 05:10:59 by Ultrano
I've emailed you directly.
I will put source on the ftp for you to survey.
I'm interested in solutions for lightweight management of object lists.
At the moment, I feel drawn back toward LinkLists.
Posted on 2005-03-20 07:03:49 by Homer
Portal rendering involves a heck of a lot of polgonal clipping (clipping polys against other polys), so I very much doubt it is faster than BSP, especially where PVS is involved.

Think of a portal as a polygonal window, through which we can see a 3D space populated by yet more polygons. The way culling works in a portal engine is that we determine (by clipping against the frustum) firstly whether a Portal is at least partially visible. If not, we ignore it. But if so, we cull each polygon against both the viewfrustum and then the Portal polygon.

Portals are useful in that they can be used to connect areas of world map which are not geometrically linked ("teleportals"), but are much more computationally expensive than a BSP with a PVS,  or BSP without a PVS.

BSP has one major drawback in that it is computationally expensive to generate the BSP (and PVS) in the first place, and it's therefore not suitable to being modified (blown up, morphed, etc) . That stuff is meant to be done beforehand, not in realtime.

Therefore portal and octree and other engines still have merit, but only if you are willing to take advantage of the flexibility of being able to mutilate your geometry.

Posted on 2005-03-21 01:29:33 by Homer
I've extended the Console class so that it internally handles Opening and Closing of the Console.


? ? ? ? ? ? pcall pConsole.Toggle, fAppTime



should be called in response to a keystroke:

? ? ? ? .if keys[192]? ? ? ? ? ? ? ? ? ? ? ?;TILDE key (topleft, below ESCAPE)
? ? ? ? ? ? mov keys[192],FALSE
? ? ? ? ? ? invoke Timer, TIMER_GETAPPTIME
? ? ? ? ? ? fstp fblah
? ? ? ? ? ? pcall pConsole.Toggle, fblah
? ? ? ? .endif


The first keypress will cause the Console to begin to scroll itself onto the screen.
If the Console is fully opened and the key is depressed again, it will begin closing.
If the key is depressed while the Console is opening or closing, it will pop open instantly (for the impatient user).

The Console is starting to look pretty good :)
Internally, it uses an instance of ObjectList class to store stringpointers.
ObjectList class internally makes calls to Ultrano's new SmAlloc memory manager.
The ObjectList class manages one pageful of pointers, and provides methods for accessing them via index etc. It is naive to what kind of pointers are stored in it.
It's simply a container for a list of objects.
Thus, the Console has an extensive History :)

I've still not reimplemented its Scrolling methods but probably will later today.

I did some work on the Loader for the binary files produced by the BSPGenerator.
It's pretty blunt stuff, so I haven't felt like doing it, but it needs doing, so yeah, I started.. wanna reload the BSP and write code to render the tree with respect to the camera.
Posted on 2005-03-21 01:57:28 by Homer
OK I've written code to reload the BSP from the binary file.
I chose to use LinkedList of node objects.

Hereis an extract from my logfile.
First is the log of the BSPTree being written to the binary,
then comes the log of the BSPTree being reconstructed from the binary.


Root 2
Front of 2 = 1
Front of 1 = 0
Front of 0 = 24
Front of 24 = 9
Front of 9 = 10
Front of 10 = TERMINUS
Back of 10 = TERMINUS
Back of 9 = ***TERMINUS
Back of 24 = ***TERMINUS
Back of 0 = 35
Front of 35 = 38
Front of 38 = 41
Front of 41 = TERMINUS
Back of 41 = TERMINUS
Back of 38 = ***TERMINUS
Back of 35 = ***TERMINUS
Back of 1 = 26
Front of 26 = 42
Front of 42 = ***TERMINUS
Back of 42 = ***TERMINUS
Back of 26 = 18
Front of 18 = ***TERMINUS
Back of 18 = ***TERMINUS
Back of 2 = 7
Front of 7 = 3
Front of 3 = 6
Front of 6 = 12
Front of 12 = 15
Front of 15 = TERMINUS
Back of 15 = TERMINUS
Back of 12 = ***TERMINUS
Back of 6 = ***TERMINUS
Back of 3 = ***TERMINUS
Back of 7 = 4
Front of 4 = 20
Front of 20 = ***TERMINUS
Back of 20 = 13
Front of 13 = 16
Front of 16 = 23
Front of 23 = TERMINUS
Back of 23 = TERMINUS
Back of 16 = ***TERMINUS
Back of 13 = ***TERMINUS
Back of 4 = ***TERMINUS

Node 2
Front of 2 = Node 1
Front of 1 = Node 0
Front of 0 = Node 24
Front of 24 = Node 9
Front of 9 = Node 10
Front of 10 = <terminus>
Back of 10 = <terminus>
Back of 9 = <terminus>
Back of 24 = <terminus>
Back of 0 = Node 35
Front of 35 = Node 38
Front of 38 = Node 41
Front of 41 = <terminus>
Back of 41 = <terminus>
Back of 38 = <terminus>
Back of 35 = <terminus>
Back of 1 = Node 26
Front of 26 = Node 42
Front of 42 = <terminus>
Back of 42 = <terminus>
Back of 26 = Node 18
Front of 18 = <terminus>
Back of 18 = <terminus>
Back of 2 = Node 7
Front of 7 = Node 3
Front of 3 = Node 6
Front of 6 = Node 12
Front of 12 = Node 15
Front of 15 = <terminus>
Back of 15 = <terminus>
Back of 12 = <terminus>
Back of 6 = <terminus>
Back of 3 = <terminus>
Back of 7 = Node 4
Front of 4 = Node 20
Front of 20 = <terminus>
Back of 20 = Node 13
Front of 13 = Node 16
Front of 16 = Node 23
Front of 23 = <terminus>
Back of 23 = <terminus>
Back of 16 = <terminus>
Back of 13 = <terminus>
Back of 4 = <terminus>


Who's a Happy Homer?

Posted on 2005-03-21 08:48:57 by Homer