André's Blog for GSoC-GeoGebra3D project

Thursday 12 August

I realized I've been neglecting this blog, so I decided to post a small update with what I've been doing since the last post. The surface plot algorithm I was planning on implementing turned out to be a lot more intricate than I had anticipated, which is why it's turned into such a big part of the project. Finally though, I feel that everything is working the way I want it to.

I eventually settled for a volumetric error measure, as opposed to the previous one which was based on a height difference. The current error measure works by calculating the volume between the two triangles of a diamond, and the four triangles that would replace them if the diamond was split. This volume can be seen as a pyramid where the base isn't flat, so that two of the vertices have been shifted.

One important change was replacing the priority queues originally used with bucket based 'pseudo priority queues'. These are described in detail in the documentation. Getting them to work correctly did cause a lot of headaches, and I'm still not sure that my clamping functions are the best that can be found, but I am happy with how they perform. Previously things would slow almost to a halt once the triangle count rose to high levels since priority queues have nonconstant operation times. With the bucket priority queues, however, all operations are O(1).

Since the algorithm requires many different parts that work together, getting things to work correctly and bug-free was a major hurdle. In retrospect things would probably have been a lot smoother if I had built the system incrementally, and gone with a more modular structure. As the different components are heavily integrated, and there was not enough info available to debug efficiently, finding some problems was very time-consuming.

Another thing I put some work into was optimizing the vector class used (GgbVector). I also introduced a class derived from GgbVector optimized for 3D. However the fate of this class is unclear.

The GSoC 'pencils down' date is approaching, after which I won't be able to submit any patches. Right now I'm mainly working on writing documentation and polishing the code. There is still one bug left, related to functions with unbounded intervals, which I will make sure to fix before then.

Since there are still some aspects of the project that I haven't been able to finish but would like to, and since I'm pretty eager to implement implicit plots, I hope that I will be able to stay and continue working on GeoGebra even after GSoC.

/André

Wednesday 14 July

This is just a quick update for the midterm evaluations summarizing what I've done so far. My work has been on curve and surface plots. At the start of the project, I did a lot of research (reading books and articles on OpenGL, rendering techniques, level of detail, etc.). When I felt I had reached a level of knowledge that would allow me to synthesize my own work, I wrote and gradually improved an implementation of curve plots based on a top-down binary tree approach. Lately I've been working on surface plots, and while I'm not completely finished with them yet, I believe I have come a long way. My current implementation is very inspired by terrain rendering algorithms (and especially ROAM), and I am currently working on adapting it to be better suited for plotting purposes. Both the curve and surface plot algorithms are described in more detail below and on the wiki page. Curve plots can be tested by running (in GeoGebra3D) the command Curve[f(r),g(r),h(r),r,interval start,interval end] (where r can be any variable). Function plots can be tested by running Function[f(u,v),u,u interval start,u interval end, v, v interval start, v interval end].

/André

Saturday 10 July

Lately I've been doing a lot of work on surface plots. I wrote a new, much more intricate implementation from scratch. After some major headaches I have finally reached a point where I'm pretty happy with it. The current design is heavily influenced by ROAM, and is based on a diamond data structure. As in ROAM, frame-to-frame coherence is utilized, with two priority queues driving split and merge operations. I've spent a lot of effort making sure that things run fast, something I now believe I have accomplished. Currently, you can only specify a target triangle count, and set some parameters to decide how this target will be reached. I will (once I figure out a better error measure) implement a total error target.

There are still a few challenges that need to be overcome before I'm completely happy with my implementation. A list:

• Currently frustum culling is only partially implemented. I've written some basic code, but it doesn't quite work yet so it's turned off. Fixing this won't be hard.
• The error measure currently used is not good enough. Currently, the error is defined as the distance between the midpoint of a diamond and a line between its two parents' midpoints. Sorting the priority queues by this error produces good results. However, the total error tends to increase almost monotonically as triangle count increases. Ideally, error would monotonically decrease (however this isn't really feasible for various reasons) so that the total error could be used to guide the splitting and merging operations.
• Unlike the previous implementation where I didn't really care about having a continuous mesh, making the current implementation scale infinitely is hard. In order for it to be feasible, I will first need to convert the program to use null pointers (it currently bootstraps a fairly complicated periodic arrangement lifted from the ROAM tutorial to avoid this), and then find some way to dynamically tessellate a larger mesh (containing the previous mesh) when bootstrapping it. This is not impossible, but probably quite hard to get working properly.
• Rendering is currently somewhat inefficient, with each vertex and normal being specified individually. I've already made sure that all the vertices are packed tightly in a FloatBuffer, so using vertex buffers or VBOs instead won't be hard.

/André

Sunday 27 June

Whew, time sure flies! I revamped the curve plots once more, and have now reached a point where I'm pretty much happy with them.

Recently I've been focusing on surface plots on the form f(x,y). My initial approach was to use a top-down approach with triangle quadtrees. Each node is an isosceles triangle. Refinement was done by comparing the normals of adjacent triangles, and splitting one triangle at a time into four smaller isosceles triangles. I also let the triangle quadtree expand depending on the camera zoom, to create an impression of an "infinite" surface. However, I identified two problems with this approach and am now in the process of revamping the surface plots.

The first problem was T-junctions (basically a point in a mesh where the edge of a triangle meets a vertex shared by two other triangles). T-junctions destroy the manifold topology of a mesh, and should be avoided. T-junctions are created when one triangle is split, while one of its neighbors is not. The easiest way to avoid it is to recursively split adjacent triangles until there are no more T-junctions. However, with the quadtree approach I was using, each triangle is always split along every edge, and so any recursive approach would lead to a chain reaction where a large part of the mesh would have to be refined.

The other issue I've detected is speed. The top-down approach just isn't effective enough, and update times become intolerably long when the camera is zoomed out.

I haven't yet decided exactly how I want the new implementation to look. I am however currently looking heavily at ROAM for inspiration. I will be using a bintree instead of a quadtree (probably using diamonds instead of triangles). I will abandon the top-down approach in favor of a more continuous approach, where the next iteration of the mesh is based on the previous, and merges/splits are driven by priority queues (sorted by some sort of error metric, I haven't yet decided on any particular one to use).

/André

Sunday 13 June

In the past week I've been doing a lot of work on curve plots, and am beginning to feel fairly happy with my implementation. A curve is created using Curve[f(r),g(r),h(r),r,rMin,rMax]. Curves are stored in the class geogebra3D.euclidian3D.CurveTree. Points on a curve are represented using the class geogebra3D.euclidean3D.CurveTreeNode. CurveTree contains a binary tree of points (f(r),g(r),h(r)) evaluated in the interval ]tMin,tMax[, as well as a two special points start and end evaluated at tMin and tMax, respectively. Initially, the curve tree is created with a specified depth (CurveTree.initialLevels) to get a good approximation for the bounding volumes of the points (right now these are simply stored as bounding radii in order to speed up calculations).

When the curve is to be drawn the segments [start,root] and [root,end] (where root is the root of the tree) are evaluated in PlotterBrush.refine() according to a some detail criteria (soon to be described in detail). If the segments don't fulfill the criteria, the method calls itself recursively with {[start,l],[l,root]} and {[root,r],[r,end]}, where l and r are the left and right children of root. refine() always draws the point that is in both segments when it is visible. The recursion is repeated until the detail criteria are satisfied.

As for the detail criteria, the goal is basically to have a curve that looks smooth without being unnecessarily detailed. In order to achieve a smooth curve, we assume that the curve is continuous, and then (for two segments (A,B), (B,C)) make sure that the angle between (B-A) and (C-B) is small enough. We also refine if the angle between the tangents at two consecutive points is too big. Since we don't want the level of detail to be too high, we don't refine a segment between two points if they're at a small enough distance (this distance depends on how zoomed in the camera is).

A number of intricacies are introduced when singularities are to be taken into consideration. The current implementation can handle singularities, however they are not drawn correctly Ideally singularities should extend to infinity, but now they only extend a (nonuniform) distance. See, for example, Curve[t,0,tan(t),t,-100,100].

I will hopefully be able to start working on surface plots this week, and already have a few ideas on how I'd like to implement them.

/André

Saturday 5 June

During the past week I have finally been able to sink my teeth into the project and get a better idea of what I should do and how. I have read the better part of the following books:

• Interactive Computer Graphics: A Top-Down Approach Using OpenGL by Angel
• Advanced Graphics Programming Using OpenGL by McReynolds and Blythe
• Level of Detail for 3D Graphics by Luebke et al.
• Real-Time Rendering by Akenine-Moller et al.

I have also begun playing around with the code. I implemented two different methods of dynamic refinement for parametric curve plots, and have also begun work on a more advanced approach using a binary tree over the parameter that will allow for fast rendering and dynamic level of detail. These are discussed in detail on the wiki page.

/André

Monday 24 May

Today is the first day of CSoC 2010! Naturally I'm very excited to have the opportunity to work on this project and I think it will be a great experience. Since I'm right in the middle of my exam period, I won't be able to do much work for the next few days. From Thursday and on, however, I will be working full-time on the project.

I will update this blog continuously during the summer with information on how my work is progressing. Initially I will work on plotting, so expect a few updates on that in the near future!

/André