After finishing the triangle geometry conversion, I have restarted looking at the Triangulate3D function. For some crazy reason, I still can't figure out why IsConvex() doesn't work quite right. Or rather, I know why it doesn't work right, but I am unsure how to fix it. The problem lies in the situation where when I am inserting consecutive points into a csPlane3 object, sometimes the resulting plane is defined counter clockwise, and sometimes it is defined clockwise. e.g. if one considers the polygon defined by the points:
(0, 10, 10)
(0, -10, 10)
(0, -10, -10)
(20, 5, -10)
(10, 0, -10)
(0, 10, -10)
Point number 4 (that is (10, 0, -10)) should be convex. However, what happens is that since the polygon loops back around, the plane defined by points 4, 5, and 3 is defined counter-clockwise, resulting in an incorrect result for the IsConvex() test. I am not quite sure how to fix this. Anyone who thinks they can provide some insight, feel free to look at my code. It's available in the libcrystalspace project (in MSVC) under the files triangulate3d.h and triangulate3d.cpp. It's been placed in the csgeom file, if you are not using msvc.
As a result of this problem, I am going to continue with the collada conversion by next moving to materials conversion. The fact that the collada conversion system doesn't currently support any polygons other than triangles isn't immediately a problem, since COLLADA exporting from Blender allows the user to export only triangles, which can then be used to test the collada system. I will look into the materials conversion today, and hopefully have it coded in the next few days, at which time I will re-investigate the triangulation function.
I edited the code to make sure that xml tag parameters were all lowercase (e.g. 'meshfact' instead of 'meshFact'). Also, I added a plugin tag so that it could be viewable in a scene once exported. It appears that the viewability still isn't there, though, as exported XML files can be imported into viewmesh using 'Import Lib', but the triangles don't show up. There aren't any errors, just no triangles. I wonder if there are other things that I need in the XML file (e.g. materials) before it will display.
I was able to get the triangle conversion working completely today. It doesn't yet convert vertex normals from COLLADA format to CS. What it *does* do, however, is read in all of the vertices from the COLLADA file, add them to a triangle mesh, then construct triangles from the given vertices, and index the vertices accordingly. Once completed, the triangles are retrieved from the csTriangleMesh object, and written to the CS XML document in the correct format.
For the remainder of the day, I am going to be working on Triangulate3D(), as this is still not completed. Tomorrow, I hope to be finishing general polygon conversion.
I've redesigned the triangulation routine, at the recommendation of thebolt, to utilize an ear clipping algorithm. As of right now, I have got the function working, but there are a few bugs still left in the code. Namely, the triangulation routine is returning a triangle for each vertex in the polygon, which of course is not correct. I'm fairly certain I know where in the code the bug lies.
I intend to have this bug fixed tomorrow, at which time I will extend the code to work with polygons that have holes.
I am going to postpone testing of the triangulation function until after I have the rest of the geometry code finished. I feel like I am slipping further and further behind, and I need to make sure I get the XML conversion completed, as the convertor will be near useless without it. ;)
My intention today was to get the triangulate3d code written, but unfortunately, it looks like that isn't going to happen. Things have just been going really slow today. Thus, to adapt the schedule, I think I am going to combine the Triangulation and Finishing of Geometry conversion into a single stage. The combination of these two should be done by the time I laid out for Convert Geometry to be done.
The concept I have for the triangulation code is fairly straightforward. I intend to utilize the MakeMonotone algorithm given in deBerg et. al.'s computational geometry book. (I originally intended to use a Delaunay Triangulation, but I don't think that it's necessary to do all that work - we are given a polygon in 3D, so that makes the problem a little easier than a point cloud). Now, the problem I see is that the MakeMonotone algorithm (that is, break the polygon into y-monotone pieces, then triangulate each of these and combine) works on a 2D polygon. Normally, I thought it would be easiest simply to project the 3D polygon onto a 2D plane, but this doesn't work if the polygon wraps over on itself (consider a polygon like the following: http://www.cosy.sbg.ac.at/~held/projects/triang/spiral_01.gif
). Thus, my idea is to perform the following:
The problem will be to determine the mapping (Note: The removal of holes isn't trivial, but I have an algorithm for it somewhere... I just can't remember where it is at the moment. I will find it. So, I'm going to do everything else first, then add it in later.) I thought about an LSCM-unwrap type of algorithm, but that relies on user cuts. The thing is, that if the polygon is some kind of wierd 3D shape that loops back on itself, then it's no longer a polygon, and I probably can just ignore that case.
The code I have been working on today has been mostly to add a test application, so I can visualize the two versions of a polygon. Ideally, I want to create a split window. The top has the un-triangulated polygon, and the bottom has the triangulated one. To begin with, what I want to do is show the polygon in 3D in the top (the original polygon), then show the polygon in 2D after the mapping in the bottom. I am working on this application, which will be called apptri3dtest, as this is being written.
I have been mulling over the concept of Triangulations, and I feel that I have come up with a good solution to the triangulation problem. First, I think that the class csTriangulate2 will suffice for most of what I need in the COLLADA conversion. However, I will need to adapt it to handle general polygons, including those with holes. I figured since I will be performing this, it might be a good idea to make sure that the triangulation class conforms to the SCF system, and give it an interface - say something like iTriangulator. Thus, the inheritance will look like:
iTriangulator ^ | | ------------------------------- | | csTriangulate2 csTriangulate3 (new)
I realize that my schedule has slipped a little bit, but in order to get things back on track, I plan the following re-vamped schedule for the remainder of the summer:
Triangulation: July 2 - July 3
Finish Geometry Conversion: July 4 - July 13
Materials and Texture Conversion: July 14 - July 28
Lighting/Scene Conversion: July 29 - July 31
Physics Conversion: August 1 - August 10
Animation/Rigging Conversion: August 11 - August 20
I have run into a problem which I didn't anticipate prior to two minutes ago. Unfortunately, support for <p> elements in Crystal Space is going away (as I understand it, it wasn't especially useful, anyway). This, along with the fact that it didn't previously handle general polygons anyway, presents the following problem:
* Before converting to Crystal Space format, all polygons in COLLADA format which are of type <polygons>, or <polylists>, will need to be triangulated.
So, it appears as though I will be dusting off my Computational Geometry book from last semester and attempting to find out what the best method of utilizing a Delaunay Triangulation is. I am going to look into libraries for this purpose, as I have heard the DT implementation is a nightmare. So, sorry folks, but it doesn't look like there's going to be a commit in the next couple of days.
This includes two of the new objects, csColladaMesh and csColladaAccessor. Both of these objects have, at their core, a Process() function. The Process() function essentially parses the XML document and retrieves the necessary information. The activity diagram of csColladaMesh::Process() follows:
And the activity diagram for csColladaAccessor::Process():
The next stage will be to integrate a listing of polygons into the mesh object. This should be fairly straightforward, as before, and will be composed of yet another class, csColladaPolygon, which will have as sub-classes: csColladaSimplePolygon, csColladaTriangle, csColladaTriangleFan, csColladaTriangleStrip, csColladaLine, and csColladaLineStrip. I hope to have all of these converted and ready by this afternoon.
I have decided to go back and re-think the design of the library itself. In hindsight, I think that to make the code cleaner and more robust, it will be beneficial to add another couple of classes. Namely, what I added was a class representing the mesh itself. Ideally, I want to be able to process the COLLADA file in a single pass, without having to jump around looking for different elements in the document structure multiple times. To this end, I have decided to add a csColladaMesh class, which will effectively represent data stored in a mesh object. As of right now, this consists of just vertices. I will extend it in the near future. A new class diagram, with two new classes, is given below. I am currently working on redesign of the activity diagrams. They should be done tomorrow morning.
I ran into some trouble this weekend within the conversion of triangles and triangle fans. I decided that the method I used previously to convert polygons was somewhat convoluted and much too difficult to interpret in order to effectively re-use. Thus, I have decided to redesign this conversion method, and separate it into several conversion functions:
For the first iteration, only ConvertGeometry() will be implemented, which in turn will call ConvertVertices() and ConvertPolygons(), so both of those will need to be implemented as well. The first iteration will also implement materials and scene conversion functions, at a basic level. I intend to have iteration one finished before July 9.
Unfortunately, I am currently in the middle of battling a migraine headache, and was unable to get much done today. As such, my original plan of committing this evening will have to be postponed until tomorrow or Tuesday. Once I clean up the codebase, and make sure that my implementations are cleaner than they are right now, I will commit the finished ConvertGeometry() code. As of right now, the only un-implemented functionality is the trifans and tristrips elements, however, as I previously said, I am redesigning some of these functions so they follow a more logical pattern.
|<< <||> >>|