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.

Isolines

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 j014.java MarchSqr02.java GridCube.java SquareGridIter.java MarchSquareDisplay01.java

jimg012.png

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 j015.java GraphicsBase.java PointDisp.java LineDisp.java MarchTri01.java . jimg011.png

3D Contour Intersection mathematics.

The Elevation Grid

As part of the requirements I implemented the elevation grid with rotation. See j020.java and SurfaceRect.java . An interesting mathematical function was used, see C02.java . There was a problem with normal generation : the algorithm may not know how to handle two-sided triangles. See TriangleDisp4.java 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 j016.java MarchTet00.java ScalarFieldOffset.java TriangleDisp.java TriangleDisp3.java LineDisp2.java GridDisp.java GridDiagDisp.java

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 j018.java MarchTet01.java

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.