Worklog for Warner
Worklog Warner
Return to Worklogs
| ||
| Last week I was working on new CSG routines. I was looking for a cleaner and more reliable version. I've allways thought that BSP's were the more advanced method, in comparision to Laidlaw. But I learnt Laidlaw creates less unneeded polygons, so I gave it a second chance. I wrote an OOP version of the Laidlaw algorithm in BlitzMax. I feel more confident about this version: it has no strange patches, everything tested seems to work, and I understand the routines it uses. However, I've learnt not to trust these CSG routines I write too easily, so I'm a bit cautious before claiming success. Here is a screenshot: |
| ||
|
Now for the dropper, I'm working on terrains. I've posted two of the
things I did so far. I translated a Russian ROAM algo. On the MacBook
I'm working on this holiday, it runs at about 400 fps, but on my own
laptop PC it runs at only 60 fps. Without terrain, minib3d runs at 170
fps. Anyway, still working through. |
| ||
| I'm working on a Mac for the last few days, and the program is coming down nicely. I did underestimate what a huge task nearly everything is. When an object is updated, it needs to be replaced in the TreeView, the icon has to be updated, and the mesh. When an object is removed from the object panel, I need to check if a copy was made from it, and if that copy still exists in the main editor. If the copy is still there, the user cannot delete the prototype from the object panel. Anyway, I included Lathe and Extrude. You can realtime alter objects made with these functions. When done, you can convert them to a common mesh. Lathe allready generates uv coords, Extrude still does not. When a normal mesh is edited, you can drag around it's vertices. It is a nice feature, but it makes the program too slow, so I need to upgrade that. After that, todo: tween button for animations, most likely several bugfixes, and then on to the world editor. (sort of dropper) |
| ||
| http://www.youtube.com/watch?v=y1Hr0MrxMak |
| ||
|
Again, a lot of progress. I stripped bones from .b3d files so I can
attach new objects to them. I created a global turnentity for minib3d,
and I created a basic loft tool. Also, I downloaded wxmax, which seems to work nicely, and I made a testing program where wxmax and minib3d are combined. Everything is still in a basic stage, but I'm hoping to make progress soon. Combining everything will be a big challenge. I'm not sure how to create a single editor that has all the functions I wrote and still maintain a certain level of simplicity. Still working on that. |
| ||
| The second 'workaround' works much better than trying to merge trees. Also, before adding new objects, I'm adding their bounding box, to avoid the final mesh from getting too fragmented. The editor is updated as well, you can now also add spheres to the scene. http://abcbasic.comyr.com/csg.zip Note that the editor is not a well-written program. I simply patched it together quite fast to be able to test the CSG routines. The height differences in the floor are a result of the editor, not the CSG routines. |
| ||
| Right, instead of trying to merge the BSP's, which I can only partially get to work, I'm now using the same workaround as I did before. Except the method is now a bit more optimized. I create a list of all BSP trees. If a polygon ends up in an 'outside' leaf, it is pushed through the next tree, else it is not. That way, as soon as a polygon is inside a solid, the determination process is terminated. I figured that would take the same amount of calculations, and that way, the nodes are not fragmented too much. It seems to work sofar. Every test I did that failed with the previous method, is passed correctly. Still, I've learnt not to get too optimistic too soon. I guess back to some more testing for now.. |
| ||
| Right, I did solve the problem partially. And I now see that it can be done. It is just the merging function that is incorrect. The workaround is attaching Tree2 to each 'front' leaf of Tree1. That is quite overdone, and it slows down the BSP routines heavily when meshes increase their complexity. I would only need to attach subtrees of Tree2 to certain frontleaves of Tree1. However, I need to work out a routine that can determine which subleaf should be attached at what frontleaves. Still, it's progress. |
| ||
| @#$%&! The merging routine doesn't seem to work properly. Adding cubes, pyramids and cylinders seem to work, but when I started using spheres the trouble began. Actually, the method was incorrect, it only shows when shapes are getting more complex. Spheres just brought up the problem sooner. Well, back to the drawing board. This CSG is costing me years of my life. |
| ||
| I've made an editor to try out the csg routines. Here is the download: http://abcbasic.comyr.com/csg.zip It contains a small bug, but I didn't want to upload another version. The picking plane that goes upwards doesn't point itself towards the camera. Basically, you'll have to stay 'in front' of the world to be able to draw. |
| ||
| Again good news! It works splendidly. I've added the wrapper functions, and the code is now pretty neat: b1.TCSGBrush = CSG_LoadBrush("tex.bmp")
b2.TCSGBrush = CSG_LoadBrush("tex2.bmp")
m1.TCSGObject = CSG_CreateCylinder(0, 0, 0, 20, 20, 20, 24)
cbe = CreateCube()
ScaleMesh cbe, 20, 20, 20
PositionMesh cbe, 20, 20, -20
m2.TCSGObject = CSG_MeshToObject(cbe)
FreeEntity cbe
cbe = CreateCube()
ScaleMesh cbe, 5, 22, 5
PositionMesh cbe, -8, 0, 8
m3.TCSGObject = CSG_MeshToObject(cbe)
FreeEntity cbe
CSG_PaintObject(m1, b1)
CSG_PaintObject(m2, b2)
CSG_PaintObject(m3, b2)
CSG_Add(m1, m2)
CSG_Substract(m1, m3)
mesh = CSG_Render(m1)
I've included materials, and an _Add and _Substract function. Every test I've done seems to work. I will knock up a small editor to try it out further. I should include optimisation, so that if a polygon is split, but none of the halfs are deleted, it should be reverted to it's unsplitted state. But I don't really feel like doing that. Maybe later on. |
| ||
| Wh00t, again a new victory! Merging BSP trees. That was quite difficult for me, because their structure is beyond my abstract capabilities. My first step was a workaround. I could allready merge two objects using their BSP trees. Object1's polies are pushed through the BSP tree of Object 2 and vice versa. Each object is rendered, and both are collapsed to a single mesh. However, I could not merge the two BSP trees. So whenever I wanted to add a 3rd shape, things went wrong. The workaround was as follows: I made a list with all objects that were added. Then, when a new object is added, I push it though each object on this list, and then I push each object on the list though this mesh. Finally, each mesh is rendered and collapsed into the endresult. (AddMesh) That worked, but offcourse it wasn't the 'right' way. I can imagine that merging the trees is faster. Finally, after trying, thinking, drawing and a bunch of trial and error, it seems to work. At least, so far. So now I have the following code: PushDownCSGMesh(m1, root2, True) ;mesh1->BSP mesh2 PushDownCSGMesh(m2, root1) ;mesh2->BSP mesh1 For p.TPoly = Each TPoly If p\parent = m1 Then If p\side = -1 Then DeletePoly p ElseIf p\parent = m2 Then If p\side = 1 Then DeletePoly p End If Next CSG_FlipMesh m2 CSG_FlipNodes root2 AddPolies m2, m1 It substracts object2 from object1 and adds the object2 BSP tree to object1's tree. It's still WIP offcourse. I'll now write a function that automates the above. |
| ||
| Today, I finally got the BSP's down. Luckily I found a page describing an algorithm in Google's cache. The page itself has dissapeared. The Laidlaw approach didn't work for me. The code for that I posted in the archives. Allready I could use planes to split objects. The step to change from triangles to polygons really paid off. But now, I can generate a mesh defined by planes. Each plane is defined by a normal and a 'd' value that indicates the distance from the origin. First, I create a big quad for each plane, then I chop off the outside pieces with a BSP tree. Each polygon is pushed down a BSP tree. That is a binary tree using planes. A function checks on which side the poly is. If it is in front, the poly is pushed down the front leaf. If it is in the back, the poly is pushed down the back leaf. If the poly is on both sides, it is split into two parts, and each half is pushed down the according tree. If the poly ends up on a front side, it remains, and if it ends up on a back side, it is deleted. To determine on which side a polygon is, I use PointOnPlane. If a poly is coplanar with the plane, I look at their normal and d values. If it is the same as the plane's, the poly is pushed down the front leaf, otherwise, it is pushed down the back leaf. Polygons are defined by a number of points. Automatically, each point is connected with the previous point, and the end is closed. That way, if I remove points from this triangle, it remains closed. Since all polygons in this program are convex, it is not difficult to triangulate them: each side is connected with the first point. The method leaves small artifacts, but they are really small. And a proper meshweld allready solves a big part of that problem. Beside that, it is robust, and it works consistently. I did need to cut off epsilon values, when using ray_plane (elias_t), PointOnPlane (leadwerks) and Compare. Also, I can take another shape, and chop off the pieces that are outside the first shape, using it's BSP tree. Later on, I shall build in the possibility to add the second shape's planes to the BSP tree. Then, hopefully, I can perform boolean operations using BSP's. A lot of hard work went into this, and I'm glad it all works out finally. |