Isolines, Isosurfaces and Elevation Grids

Assignment Report

by Chelton Evans

An algorithmic view of Marching Squares and Cubes was taken. By analysing the algorithms, I was able to construct new isoline algorithms and built a Marching Tetrahedron algorithm.


jimg005.png To be honest with you I come from a maths background and we spend so much time with functions that I didn't know exactly what a field was. So I first implemented Marching Squares with a function and verified the contour with Mathematica.

Marching Squares was implemented. See


It soon became apparent that marching isolines accross a cube was part of a general way of drawing contours, and by choosing different grids and coordinate systems, many isoline algorithms are possible.

jimg034.png jimg032.png jimg036.png

To test this, I implemented Marching Triangles. Further I separated the graphics from the algorithm. This alowed me to plug in point display, and line display. See . jimg011.png

3D Contour Intersection mathematics.

The Elevation Grid

As part of the requirements I implemented the elevation grid with rotation. See and . An interesting mathematical function was used, see . There was a problem with normal generation : the algorithm may not know how to handle two-sided triangles. See at the tail end of the file for the normal generation code. jimg022.png

Marching Tetrahedrons

Since the cube is not the most primative 3D shape but the tetrahedron I believed an algorithm for marching tetrahedrons was possible, and more general for algorithm building.

Marching Tetrahedron cases

jimg016.png Marching Tetrahedrons VRML

Critical failure

I pursued marching tetrahedrons by constructing a bipartite grid structure. This has certain properties (better approximation and I believed in nature has advantages and are basic building blocks for other ideas). However the algorithm fell through, as it did not cover the surface and covered in ways I did not understand.

vrml/marchtet03.png vrml/marchtet00.png vrml/marchtet01.png vrml/marchtet02.png
jimg015.png vrml/marchtet30.png

vrml/marchtet15.png vrml/marchtet13.png vrml/marchtet17.png vrml/marchtet19.png

vrml/marchtet26.png vrml/marchtet28.png

jimg026.png jimg024.png See

Simplest possible Marching Tetrahedron algorithm

So my major algorithm flunked and I am a week or two out from submission. But there was a lesson here, the surfaces were not joining, so the marching cubes was possibly doing more than partitioning the region, it was matching surfaces.

Therefore it was doing something in the xyz planes, and if I could get a representation that did the same thing (I still have not ruled out an error in the previous implementations code causing the failure, but I needed the algorithm not the proof). Perhaps a volume triangle might work - still using cubes and easy to implement. Observe that in implementing marching tetrahedrons the two non trivial case draw surfaces in orthogonal planes.

vrml/marchtet06.png jimg028.png jimg030.png

jimg018.png jimg020.png See

Further improvements are to draw non-faceted normals. This is straight forward but I have run out of time. However by having a state to remember the inserted point and its index, general and unique edge representation, the generate normals capablity can be used. I just realised this only when the obvious was pointed out to me.