27/01/05
This is a render of the puget sound data set. It is fairly flat and should show off the shadows fairly well. I guess this would also be a good candidate for self-shadowing. I'll probably add vertex colours or a texture to the mesh at some stage.
Wow, my video driver is old.
24/09/04
On the trail of a bug somewhere in the re-triangulation, sometimes the best way to find the problem is to draw the mesh topology out on paper and re-triangulate by hand to see what the program trace does wrong. Drawing the topology is usually pretty time consuming so I wrote some code to output a region topology to a dot file to use with graphviz.
The result is not as good as could be drawn by hand, but it is alot quicker and I hope I can get this layout better using manual positioning of the nodes.
16/09/04
07/09/04
21/07/04
Similarly coloured vertices belong to the same root node. The bunny has 29 root nodes, 2 of which are leafroots.
xgmodel->merge_tree->roots = (29) 33388 33521 41341 55599 61657 64122 65229 66431 68669 68945 69053 69094 69119 69251 69265 69419 69423 69525 69531 69544 69563 69604 69612 69613 69617 69635 69636 69637 69638 num_leafroots = 2 root 0 has 1 active children root 1 has 1 active children root 2 has 2 active children root 3 has 3 active children root 4 has 3 active children root 5 has 8 active children root 6 has 13 active children root 7 has 21 active children root 8 has 19 active children root 9 has 36 active children root 10 has 53 active children root 11 has 114 active children root 12 has 131 active children root 13 has 118 active children root 14 has 206 active children root 15 has 178 active children root 16 has 325 active children root 17 has 339 active children root 18 has 914 active children root 19 has 492 active children root 20 has 393 active children root 21 has 933 active children root 22 has 1424 active children root 23 has 1453 active children root 24 has 993 active children root 25 has 3656 active children root 26 has 4865 active children root 27 has 9147 active children root 28 has 8993 active children xglod->active_nodes_list->length = 34834
So you can see the roots are poorly balanced, some roots have many more children than others. Within each root, the trees are well balanced.
02/06/04
First go at finding the silhouette. Not very good at all. This will do for the moment, I have other stuff to work on.
31/05/04
Drawing the triangle bounds spheres at each node on the surface of the mesh. Each sphere is drawn 99% transparent. The areas of the surface that are oblique to the view-vector have many spheres drawn on top of each other and hence are very apparent.
28/05/04
27/05/04
The backfacing nodes are very coarse.
28/04/04
23/04/04
07/10/03
The Dragon. 33.8Mb. 437645 Vertices. 871414 Polygons. Consummate V's! I said CONSUMMATE!
08/09/03
Here are some recent screenshots, the view-dependent refinement is working quite well. The green cone represents the view-cone from which the refinement is being performed. A single model at multiple adaptive resolutions. Screen space projection also works but needs another look. The jump-collapse and jump-split are fine. Other models also work, like cow horse and happy.
18/03/03
The two nodes at the top of the screen are two roots. Green means fully visible. Yellow is partially visible. Red is not visible. A blue outline means the node is part of the active nodes list. This particular screenshot shows that there are quite a few bugs still in the program. Also, this tree is quite unbalanced, the left root has few children and the right root has many.
06/02/03
22/01/03
22/08/02
Images
Image 1: The camera is positioned on the right side of the object, looking left along the x-axis. Polygons in the model that face away from the model are merged together.
Image 2: As above, but with the object rotated to get a better view of the simplification.
Image 3: A view from the camera position, no approximation is visible.
Image 4: Another view of the simplified side of the object.
05/04/02
I have spent the last few days writing code to let me trace the execution of the program more easily. It has payed off as I have found three really good bugs today.
The work I had done in adding boundary edge opposites into the mesh for data sets with boundaries had exposed errors in sections of the code I thought were working properly. The collapse_edge() and split_edge() methods in xev_model both had to be updated to take notice of the cases where the edge or its opposite are boundary edge opposites.
The collapse_edge() and split_edge() methods in xev_model also have to be updated to set next and previous pointers in those cases where edges are boundary edge opposites are invloved. This is easy to fix, but I THINK IT IS CAUSING the infinite walk around a vertex in the Region of Influence code. This could solve alot of problems.
Also xev_merge_tree_builder::build(xev_model* m) was not updating its collapsed_edges array properly in cases where boundary edge opposites were involved.
27/03/02
I went back and fixed the problem with importing PLY's with edges that have no opposite. I generate a bunch of new edges and setup all the opposites and end_vertex, left_face etc. This took a while because it made me aware of various other problems with the way the importer was working. As well as problems with the way a model is stored. It is reasonably messy at the moment.
I havent yet tested the way I solved the problem below (the multiple edge per vertex pair problem), I need to test this next with some simple data sets.
I still get errors with some of the models when making the merge trees due to an infinite walk around a vertex. I figured this should have been solved by the two things above. But since it is not, either the above things aren't correct solutions in some cases or there is some other problem i'm not aware of. More investigation required.
14/03/02
It seems sensible to group the intersection into consecutive pairs to be the opposite edge of each other. I hope it is sensible. In the last example, if the edges 2,3,70 and 71 all connect vertex 0 and 1. Then 2 and 3 will be opposites and 70 and 71 will be opposites. I have implemented this and it hasnt broken anything else yet. I might write some more code to check that one of the edges in each pair starts at the vertex the other one ends at and vice versa.
The other problem with the models is the boundary edges. These boundary edges have NO opposite. One solution to this is to identify the number of boundary edges then add the same number of edges to the edge list. Each of these new edges would connect the same vertices as a boundary edge, just in the opposite direction. Then each of the new edges would be an opposite for one of the boundary edges.
Once the boundary edge stuff is done, I should be able to load many more models.
I downloaded a few more models from stanford, including the skeleton hand model (327323 verts, 654666 faces). This model has no problems with its structure at all, in fact I could load it before any of the above adjustments. The only problem is that it is so large, I cant malloc enough memory for a merge tree. I think ill try it on a machine with more RAM.
UpdateI changed the line of code doing the mallocing from
type big_array[big_number];
to
type* big_array = new type[big_number];
Now malloc can give me enough memory, only to much thrashing takes place to run anything quickly. I'm not sure why this makes a difference. Voon Li suggested it might be the difference between getting the memory from the heap instead of the stack.
Also, now that I think about it, I dont know how to create an opposite edge for each boundary edge. Each edge needs to hae pointers to the next, previous and opposite edges, the left_face and the end_vertex. The next and previous edges and the left_face dont make sense for a opposite-boundary edge as it is not part of a triangle.
Maybe I can tag these opposite-boundary edges, so that the region-of-influence method can avoid following the pointers that dont make sense. I may as well just tag the boundary edges instead, and forget about making opposite-boundary edges.
12/03/02
Worked on the model_loader some more. Put in some functionality to determine more clearly what parts of the models have more than one triangle sharing one edge of the model. This problem may be more easily solvable than I thought. The way I determine adjacent edges is to make lists of the edges adjacent to each vertex. Then the intersection of two lists ought to contain the two edges that are adjacent to those two vertices. However, sometimes the intersection of these lists is more than two edges.
For example, say the intersection of the lists for vertex 0 and vertex1 is {2, 3, 70, 71}. This means that edges 2,3,70 and 71 all connect vertex 0 and 1. My simple implementation sets the opposite of edge 2 to 3, the opposite of edge 3 to 2. So far so good. Then it sets the opposite of edge 70 to 2 and the opposite of edge 71 to 2. This is a problem which I hope to solve tomorrow.
09/03/02
I cant simply add edges and faces to the merge-tree and the lod. The edges and faces arrays have lots of pointers that become useless when copied into other data structures. I might have to do some pointer arithmetic when copying the edges array.
06/03/02
Written a function called xev_model::split_edge(). It splits a vertex and restores the geometry of the model.
Triangles. Add edges and faces to lod? Yes, must. Add edges and faces to the merge-tree? Yes, if we want a lod to be able to be made from the merge-tree only (without reference to the original model).
If the edges and faces are in a lod, the edges can be maintained using collapse_edge() and split_edge() inherited from xev_model. As an edge is split or collapsed, it can set a flag for its left_face() and right_face() to be visible or not.
View-dependent refinement. Working. Logic is not quite right. A small number of node oscillate between visible and invisible. Split one frame, then collapse the next. Portal code camera is broken so camera.frame.origin does not change.
Next: get logic for view-dependent working properly. Check that addition of normal cones is correct.
04/03/02
I have had some thoughts on building the triangles for a lod. As I build the merge-tree, by removing edges, I use a function called xev_model::collapse_edge(). What I want for building a lod is the opposite of this function.
02/03/02
Time since the last update was spent writing a double linked list. This list is used to store the set of nodes that forms the "front" in the merge tree. In my last update this was done using an array. The array was particularly slow in that it changed size whenever a merge or split too place (very often). The changes in size required allocating a new array and copying elements, then deleting the old array, very slow.
The new double linked list is much quicker. The interface is also reasonably nice, which made implementing merges much easier. The code now loops through the list of nodes in the front, and passes each of them to view_test(). This function makes the correct decision for the node (SPLIT, COLLAPSE, DO_NOTHING). Then the appropriate changes are made to the double linked list.
So, the code as it is now can produce the set of vertices in a LOD, determined by the function view_test(). At the moment view_test() does a pretty simple test based on the size of the bounding spheres at each node. This means the LOD's are not view-dependent but this can be changed just by editing the view_test() function such that it also looks at the normal cone of each node when deciding whether to split, collapse or do nothing.
Here are some examples. The Original Sphere, where view_test() requires that the bounding sphere for each visible node be at least 5 units radius. Then detail decreases as minimum bounding sphere size increases to 35, 60, 120 and 250 units radius. As usual, the model gets pretty crummy at low detail.
As you can see, there are no triangles. I havent yet thought much about how to regenerate the triangles using only the merge-tree. One approach may be to keep a record of all triangles that are produced at all stages of the building of the merge-tree. Then as each split or collapse takes place, record the triangles that are removed during the operation and those that are produced. Then when recreating the lod from the merge-tree, use those records. The problem is there are a HUGE number of triangles produced. I think a better approach may be more algorithmic, but I have no clear way to proceed here yet.
I have put some documentation online. Interesting classes/methods may be xev_node_list, xev_lod, xev_merge_tree::getlod() and xev_merge_tree::update().
23/02/02
I have written some code to produce LODs, of a sort. The execution model is to maintain a "front" or set of nodes in the tree that comprise the current LOD. Then, when the viewpoint (or other conditions) change, all nodes in the front are tested, to check for merges and splits.
To do this, I have written a function called get_lod() which returns the simplest front possible, just the root node. Other options for the original front are a random front or some other calculated approximate front, but I think the a front with just the root node is reasonably elegant.
Once get_lod() has been called. I use another function called update(lod* l, scene* s). It will check through all the nodes ina given front and perform merges or splits. At present only splits are implemented. However, update() only performsa one split per function call. For example, calling update() on the original root node front will produce a lod with two nodes (the children of the root). These children may also be suitable for splits but at the moment these splits are not done until the next call to update.
This means it takes approximately sqrt(n) calls to the update() to produce a front with n nodes. The lod is slowly (its not slow at all) built over a number of update calls.
The poor part about the current implementation of update() is that once it is done merging and splitting the nodes, it copies the vertices of all the nodes in the front into an array from which they can be rendered. A better way to do this might be to maintain a vertex array of the vertices in ALL the nodes. Then use the entries in the front as indices into the vertex array. This would save alot of copying, of course at the expense of memory.
The idea of a LOD is that it is smaller than the original model. The structure that produces a LOD, the merge tree, must be larger than the original model but a LOD should be smaller. If each LOD contained a vertex array of the vertices in every node in the merge_tree, then each LOD would use as much memory as the merge_tree itself. I wonder if this matters, as soon as you save, transmit or render the LOD, only those verts in the front are saved/sent or rendered. So a LOD would be conceptually smaller but physically larger.
If a similar thing were done for the polys in the model, each LOD would get REALLY large.
22/02/02
Added bool leaf to node class.
18/02/02
Chased a bug all day. The parents of many nodes were not set correctly. I found that this was because they were not being merged. Other nodes were being merge twice instead! The bug was in the upkeep of the parents array. It was keeping information about the immediate parent rather than the highest ancestor. Solved this and completed the last merge in the tree as well. All that remains for the tree is the bounding spheres. I think ill come back to this, I want to start getting LODs.
14/02/02
The tree is almost complete. Havent added the last merge yet.
I have finished the normal cone stuff. The cone is initialised with angle zero for the leaves of the merge tree as the cone contains only the vertex normal. When the hierarchy of the merge tree is built, the normal cone for new merge tree nodes is calculated. The bounding spheres are a little more complex. It is easy enough to calculate new bounding spheres based on the size of the child spheres. The problem arises when trying to determine the size of the bounding spheres for the leaf nodes. The implementation of the half-edges prevents me from determining which edges start (or end) at a given vertex.
The edges have pointers to the vertex at which they end but the vertices have no info on which edges are adjacent. If I can get just one adjacent edge, I can find all the others with simple lookups. The way I see it, the length of the longest edge from a given vertex is the radius of the bounding sphere.
07/02/02
Work on the bounding cone of normals. I have read more of Pajarola's paper (FastMesh: Efficient View-dependent Meshing), he uses a bounding sphere at the end of every edge as well. He uses both the cone and sphere for 4 methods for view-dependent merge/split determination.
view frustum - if the bounding sphere centered at the end of a half-edge does not intersect the view frustum, it can be collapsed.
back-faces - if the normal cone associated with the end of a half-edge is back-facing (no normal within it can be front-facing), it can be collapsed.
silhouettes - if the left and right faces of an edge have different orientations with respect to the view-point, collapse should NOT take place. pajarola provides computationally inexpensive tests for this.
screen projection - takes into account the size of the triangle when projected onto the view-plane. If sufficiently small in size, the edge is collapsed. again pajarola provides tests for this.
So, im thinking of adding the bounding sphere to each node in the tree, and replacing the xev_cone structure I currently use for a normal cone with a float for the sinus of the normal cone semi-angle (as in pajarola). This is much simpler.
Once the cone and sphere are initialised in the leaf nodes and calculated during the creation of new nodes, the merge-tree will be close to complete. I still havent added the very last merge, ill do this too. Then, complete. I can start calulating a "front" in the tree and hopefully render some LODs.
I would like to start building trees from some other models, like the buddha, drill and bunny. The problems with these models are with the triangulations of the surfaces. They either have holes in the surfaces (bunny) or they have edges shared by >2 triangles. Im not sure how hard it is but I would like to re-triagulate thses models to ensure they are useable for my purposes.
06/02/02
This is what the merge tree of the sphere looks like.
It is less regular than I expected. This is what it looks like when rotated to the left and down a bit.
04/02/02
Busy with DICTA/ACCV and moving office since last update.
I have taken alot of code from the portal engine project and adapted it for my LOD work. It should now be much easier to start writing renderers with multiple lights and objects in a scene. The portal engine also has mouse support in it, something I dont want to recode. As it stands the xev_model format doesnt use colour or textures, I will leave it this way to simplify development.
17/01/02
Worked on the model viewer for a while to make it a little more generic. Then copied the code to create a merge-tree viewer. I think I will make the merge-tree builder code manually merge the last two vertices. Even though there is no edge between them, my merge-tree viewer requires that every node have a parent.
The merge-tree viewer is mostly working. Its a mess of white lines. Some colour will help with understanding. I have added a depth variable to the node class and added code to update this as the merge-tree is built. This info is in the merge-tree and a model generated from the merge tree is being rendered so I have to think about how to get the depth data into the model. The best way might be to add a colour to the vertex class. Then, when the model is being generated, I can calculate a colour based on the depth value and enter this into the model.
15/01/02
I figured out why there is one fewer collapses than expected. When there is two collapses left (ie. 3 verts, 2 faces), the next collapse removes 6 edges (both faces). The last two verts are left with no edges to join them. At this stage no further edge collapses are possible. This seems ok, in practice a limit is placed on the maximum simplification required for a given model. This limit is sure to be higher than 2 vertices.
Starting to think about the design of the merge-tree. What information does it require to allow rendering? The structure of each node in the merge-tree is not clear. I dont yet set the upswitch and downswitch values. These values are thresholds that activate further splits or merges on this node. The normal cone is important, i need to calculate normals for all the verts and calculate cones for the leaves, then write a function to enclose two cones whenever a merge takes place.
The other two structure that Varshney suggests should be within the merge-tree nodes are two lists. A list of adjacent vertices and a list of dependent vertices. I think I should be able to compute the adjacent vertices by performing a vertex split. I havent thought about enough. The list of dependent vertices hasnt become an issue yet as I have been using the sphere dataset which is perfect. It may be necessary to add this dependency list if I start to use other data.
I would like to write an application to show the tree structure as it exists on the surface of the model. Render all the verts and then render a line between the verts of each child-parent pair. Maybe using colour to signify depth in the tree or length of the edge that was merged. I think ill start this soon.
14/01/02
Thought more about collapsing and realised that a collapse actually removes 6 half-edges from a mesh. The behaviour of the merge-tree building code is more sensible now. Also added code to update the geometry of the mesh after a collapse. This involves setting the opposites of 4 half-edges and setting the new end_vertex for a number of other edges. This code can be optimised further.
Once the geometry updating code was in, I tried the merge-tree builder on the sphere dataset. It is able to produce 420 collapses. The dataset consists of 422 vertices so 421 collapses should be possible. Not sure where the last collapse has gone.
The remaining step is to produce a node in the merge-tree corresponding to this collapse. Not easy as I first thought, but not too bad.
11/01/02
I have stopped the merge_tree_builder trying to delete nodes from the rb-tree twice by first checking whether or not the node has been deleted before. Once I delete a node the first time, I set the pointer to the node to NULL, then when I come to delete it a second time, I check if the pointer is NULL and if so do nothing. This is a bit dodgy as the ROI algorithm returns incorrect results. I'll come back to it later.
Once the merge_tree_builder gets going, there are fewer and fewer edges that are not collapsed or in the ROI of a collapsed edge. The ROI walker doesnt know anything about this so it still returns long lists of 190 or so edges (in the case of the sphere), yet when the merge_tree_builder tries to delete these from the rb-tree, only a small proportion still exist in the rb-tree. I can probably make this faster.
The next step is to add a node based on each collapse to the merge tree (easy) and update the geometry of the model after each edge collapse (some explanation of this in a paper).
10/01/02
To allow me to make progress on the code I have created my own dataset that satisfies all the constraints. I have made high resolution regular sphere on which to test code. As any edge is shared by only two polygons, the ROI algorithm doesnt get stuck in infinite loops and returns useful results.
The code is still broken of course but this is because the list of edges returned from the ROI algorithm contains duplicates. When I try to remove an edge from the rb-tree a second time, the rb-tree complains politely. Keeping a set rather than a list requires more processing.
09/01/02
Back working on the region of influence(ROI) problem. I decided against writing the two functions outlined below. This would over-walk the mesh too much. Instead I have written a proper non-recursive mesh walking algorithm, it is more efficient. Im sure this algorithm can be optimised further.
I then tried this ROI algorithm on the happy_vrip_res4.ply data set. It got caught in a loop. Im unsure of the exact behaviour but I am sure the data set is not as good as I thought it was. I think the reason the algorithm gets caught is that 4 faces in the mesh use vertices 3192 and 3556. I think there ought to be only two faces in a mesh that use this pair of vertices.
Also, I dont really like the way the interface with this method working. It must return an unsorted variable-length list. I dont know the list length before I start walking so I cant alloc memory before I start. On the other hand, I dont want to have to allocate the memory in lots of small amounts as I find each edge. This is a small problem, its just ugly. At the moment I alloc more space than is necessary just so I dont have to alloc more than once.
19/12/01
I have implemented the solution below and it works well. The next step is to write some code to determine the region of influence for a given edge collapse. All edges in the region of influence become ineligible for collapses until the next round, so we remove them from the rb-tree.
I have done a few sketches on paper and I think for an average mesh where verts have degree 6, the number of edges that must be invalidated is approximately 80. This is much larger than I expected.
A reasonably clean way of getting all edges in the region of influence is to define two functions
- list* adjacent_vertices(vertex*)
- list* adjacent_edges(vertex*)
18/12/01
Solution: As we use rb_insert() to place edges within the red-black tree, we keep track of the return values of the inserts. This return value is a pointer to the node in the red-black tree that holds this edge. We still have to do the first rb_find() to get the smallest edge in the tree. However, once we have this first edge, we can calculate the region of influence of this edge and use the return values to directly delete all the nodes in the rb-tree that hold these edges. Its all good.
17/12/01
Slow progress getting the Red-Black tree to work. I dont think the comparison function I have written is being used correctly by the tree. On the upside, it is very fast. Voon-Li suggested I use the STL Map or Set. This seems like a good idea, I probably should do some reading on the STL. The problem is, as far as I know, that the Map and Set dont have methods for returning the smallest element.
Figured out the problem with the rbtree. Yeah, stupid mistake. rbtree is real quick.
So, now we put the rb_tree.findmin() in a loop until rb_tree.isEmpty(). In each loop we do the things in the list below.
Problem: When we want the shortest edge length from the rb-tree, we query the tree for a key of zero. The tree retruns the value with the key closest to zero. The shortest edge. Its all good. BUT, when we want to remove all the edges in the region of influence from the rb_tree, we have to search the tree based on value, not key. Cant do it.
14/12/01
Gian gave me some code for a Red-Black tree. Amitava suggested this would be a much better structure in which to store the edges. If we use something like a Red-Black tree, the space allocation is only for one node and the rebalancing is over logarithmic depth.
To begin, we insert all the edges into the red-black tree, then findmin() to get a pointer to the shortest edge. Then we perform this edge collapse. The collapse will have effects on the surrounding edges and faces. These operations include:
- Record the edge collapse in the merge tree.
- Update the connectivity of the triangle mesh. (Pajarola Section 3.1)
- Determine the region of influence of the edge and use rbtree.delete() to remove all the edges that are now invalid in this round from the red-black tree.
Building a new tree each round is time-consuming but hopefully the number of rounds will not be very high.
I have figured out how to use the red-black tree code today. Just a small problem with using float edge lengths instead of ints. This means I will have to use the rb_insertg() function instead of the rb_inserti() function. A comparison function pointer must be supplied with the rb_insertg() function. I'll do this tommorow.
12/12/01
From Xia, El-Sana and Varshney, Adaptive Real-Time Level-of-detail-based Rendering for Polygonal Models.
"A better alternative is to sort the edges by their edge lengths and collapse the shortest edges first. Collapsing an edge causes the neighbouring edges to change their lengths. However as mentioned above, since changes are local we can maintain the sorted edge length in a heap for efficient updates."
I have written a class xev_edge_heap. This has two operations, add(xev_half_edge* e) and remove(). At the moment add does a simple insert into the sorted array. Unfortunately this is really, really slow.
11/12/01
Fixed some problems with delete calls in the model importer. Not sure why I thought a call to delete a NULL pointer would be a problem, it's not. I hope all the memory leaks in the importer are gone now, it certainly does alot less thrashing on BIG models now.
I have read the papers on building merge trees again but im not sure of the best way to proceed. I would like to implement a binary merge tree. The way it seems to work is to loop through the edges and determining which ones are suitable for collapses, then ordering them according to edge length, then performing these independent collapses at a given level. Then repeat.
10/12/01
Switched to using adjacent edge lists instead of adjacent face lists to determine edge opposites. This is quicker and doesnt use too much memory. A vertex is usually adjacent to about 6 faces and about 12 half-edges. (write a function to determine average list length etc.) This means memory usage for the algorithm rises from 6n to 12n where n is the number of verts in the model. Still, 12n is better than n^2, and the code is alot more elegant than the O(6n) face list.
Although the bunny is, in theory, a manifold surface, the mesh describing that surface is not. This means that some edges have no adjacent edges. This is recognised by the algorithm and the indices of these edges are output. When it comes to time for traversing the mesh at LOD-time, it would be a problem if the code depended on getting to the next vertex via an adjacent edge, and one didnt exist. I hope I dont need to use a bool to keep track of which edges dont have opposites, that would hit performance hard.
The next step is to read the Pajarola and Varshney papers again to start building the merge tree. Ill implement the simple binary merge first so I have some data about the average depth of merge trees and the build-times etc.
Stress tested the PLY loader on happy_buddha.ply from Stanford. It works. This model is good because it is a manifold surface. No holes in the mesh.
07/12/01
Working on the new algorithm for setting pointers from edges to opposite edges. The adjacent face lists are built for each vert and then it loops through the edges, checking which faces are adjacent to both verts in the edge. There should be 2 faces adjacent to each edge. There are always two in manifold surfaces. Some of the test data I have been using are patches which are non-manifold and so have edges which are adjacent to only one face. Problem. Do I limit the domain to manifold surfaces? or try to come up with a solution that can deal with non-manifolds?
Also, storing the edges adjacent to each vert instead of the faces would probably be better (quicker), But would use a little more memory.
06/12/01
Nick helped me get smooth shading working. The PLY loader seems good. Here is a picture of the Stanford bunny.
Spent the rest of the day working on a way to setup the pointers to opposite edges within the xev_model class. Its not a difficult algorithm but implementation is a little hairy. I didnt really know how to determine the index into an array using only pointers to the start of the array and the element who's index you're after. Turns out it is quick simple, not really sure why I thought it would be otherwise. So I have written some code to store adjacent face lists for all the verts.
Then, to determine the opposite of a given edge you check for similar entries in the adjacency list for both edges. Normally there will be two similar entries. These entries refer to the 2 faces that are adjacent to most edges ( and are, of course, the opposite of each other).
05/12/01
I have made a few changes to the PLY loader, it still reads only a small subset of the PLY format but enough for all the models I have encountered so far.
I have been searching for solutions to the opposite half-edges problem since the method I am currently using uses way too much space. I have found one example so far in the canonical PLY reading implementation from Greg Turk at Gatech. His vertex structure has an array of pointers to all the faces that contain this vertex. You can then take one vertex from the edge for which you need to find the opposite, and know all the faces that contain this vertex. Then you can search the edges of these faces to find the opposite edge. This reduces the search space a great deal.
I quickly checked the few other implementations I have seen of the half-edge and none of them had a face-adjacency array in the vertex structure. Rather than add this array to the vertex structure, I may store this information outside the model at import-time, so I can free it when the importer is done. This keeps the vertex class a little cleaner. Think more about this.
04/11/01
I have changed the way the xev_model_generator and xev_model_importer work. They now allocate memory within the function and return a xev_model* (pointer) to the model they generate/import. This solves the problem detailed in the last post. Once this problem was solved, the renderer began to work. The zipped reconstruction of the drill bit from the Stanford model archive works, its a really bad model, but it works. I then tried the vrip reconstruction of the same model, but the PLY file is slightly different, enough to break my PLY loader. More work on this is necessary.
Another problem came up when I tried to load the stanford bunny. Not only is the bunny in another different sort of PLY file, but it contains ~35K verts. This means the opposites array needs to be 35K^2 * 4 bytes. BIG, too big. This breaks the importer. I will have to come up with another way to find opposites for big files. Hopefully there is some literature somewhere.
UpdateEven the vrip reconstruction of the drill bit is too large. At 1961 verts, it requires a 14.6Mb opposites array. Even this size is too big.
29/11/01
The renderer has uncovered bugs in the xev_model structure. When the model is being built inside xev_model_generator, the pointers are setup to point correctly. However, when this model returns to the mainline of the program via an operator= call, it changes location in memory. This makes all the pointers in the model incorrect.
Does this mean i have to use integer indices instead of pointers or can I write operator= in such a way that avoids moving the model in memory?
28/11/01
I have written the part of the PLY loader that establishes the links between polygons edges and their opposites. It worked out quite well except that it uses a large amount of memory. num_vertices^2 * 32bits. Less than 50% of this two dimensional array is actually used so the memory requirement could be halved but it is still alot of memory. Still using this much memory means time spent setting up the opposites varies linearly with num_vertices. Any searching would be O(n log n) or worse.
The other problem is that some opposites are never found because the edge is a boundary edge on a non-manifold surface. I think I will stick with manifold surfaces to begin with but eventually I will need to determine which edges have no opposite and then generate opposites for those edges. Now that I think about it, it isnt very hard.
I have tracked down the problem with pointers, I was using them incorrectly, everything is good now. I think I will begin with the renderer shortly.
27/11/01
I have implemented the winged-edge data structure and written a simple model generator. The generator produces a tetrahedron which is contained is returned as a winged-edge based model. There are some problems with this code that I have not yet found. The code segfaults alot, I think this is due to the incorrect use of pointers somewhere. At this stage I am considering going back to using integer indices into arrays instead of pointers.
I have read part of a paper by Lutz Kettner, Designing a Data Structure for Polyhedral Surfaces (1997). It has some detailed discussion of OOP in C++ and some stuff on the STL, but more importantly it discusses several edge-based data structures for polyhedrons. It points out the benefits of using the half-edge data structure over the winged-edge and quad-edge data structure. Kettner's description of the half-edge is quite easy to follow. The half-edge supports all the operations as quickly as the winged-edge. I will change the winged-edge code I have written so far into half-edge code.
All the easy bits of the PLY loader are done. I can get all the data from the file. What remains is the translation from the polygon-based data structure to the edge-based data structure, which is a little difficult. Each edge in a model requires information from two polygons. These two polygons can occur at different places in the model file so associating the information from two separate polygons with one edge is difficult using only one pass over the file.
Using a half-edge data structure makes this alot easier. Each polygon in the file contains all necessary information for three half-edges. So one pass loading is easy.
UpdateEach polygon contains ALMOST all necessary information for three half-edges. It does not have information on the opposite edges. I need a structure to store which poly contains an edge so when I check the next poly I can see if any other polys have used it yet. If they have, the opposite is found, else it may exist later in the file (or not at all, in the case of a boundary edge). ALL edges have opposites, even if boundary edges.
The rendering code in persistence looks like it can be modified easily to render xev_models. Ill do this tommorow.
22/11/01
So, the start of the diary.
I am beginning to think of the sort of data structures I need for Adaptive simplification. It seems that the mesh data structure that I have always used, the list of vertices and triangles is no longer appropriate. Adaptive simplification requires a data structure that can return adjacent edges, polygons and vertices very quickly. The traditional model data structure performs these operations in O(n) time, where n is the size of the model. Unfortunately, the models I hope to use later on are very large, at least 70000 triangles. So even linear time searches for adjacency are too slow. Constant time operations are necessary.
There are several data structures that allow for constant time operations. The first of these I found in my reading is the Winged Edge data structure. This data structure is used by Varshney et al in their paper on adaptive view-dependent simplification. I have also found two others which look interesting, the half-edge (Pajarola) and the Quad-edge (Heckbert). All of these data structures are similar in that they store the model using the edges to define topology rather than polygons. The prevalence of edge collapse simplification makes this the obvious choice.
Unfortunately, the code I have written for persistence, uses polygons to describe model topology rather than edges. This means I will have to write new code for the edge based data structures. I started writing these this week.
Also, many of the data files used by other researchers in the field are from stanford graphics labs. They are destributed in PLY format. So, I intend to write a PLY file reader method in the persistence p_model_importer class. That way the p_model_importer class will read 3D Studio Max, Milkshape 3D and PLY files. Then, I will write an object translator to change these p_models into xev_models, the name of my new edge-based model data structures.
Hopefully, at some stage I can integrate the xev_model code into persistence so that either model format may be used by the persistence renderer.
This is the plan.