Wow!!! Thanks Jon.

It appears I made an error in translating the bit twiddling functions

in the C code.

// flip the given bit of i

inline int FLIP(int i, int bit)

{

return i^1<<bit;

}

I translated that as i lxor (1 lsr b) by mistake. Small typo,

dramatic impact. I think I'll nominate myself for thedailywtf.

The algorithm now does 1150 cubes not 80k. Checking the C++ app I

found generates 1052, so it's on par with it (I expect it to be

identical given the same partitioning size).

I can only say I'm sorry about this. It's quite an embarrising error.

The error was present in both the old version and the new one because

I just copied those over. :(

On 03/09/05, Jon Harrop <jon@...> wrote:

> On Friday 02 September 2005 22:39, Chris Campbell wrote:

> > The algorithm is actually quite simple. Compute value of the surface

> > function at the four corners of each of the 6 faces of a cube. If a

> > face has atleast one corner of different sign from the others add the

> > cube beside that face (if it hasn't been done already). The different

> > sign indicates the face intersects the surface along atleast one edge

> > (the surface is defined to be all points where the surface function is

> > 0).

> >

> > The part that isn't implemented is tetrahedral decomposition which

> > computes the triangles in a cube containing atleast one such edge.

>

> Is that marching cubes/tetrahedra? It would be great to publish an open-source

> 3D tesselator!

I know it's not marching cubes (even though US patents don't apply in

UK they still leave a bad taste in the mouth so I avoided it, plus it

has ambigious cases), but I'm not 100% sure if it is called marching

tetrahedra or not. I only know it from J Bloomenthals Graphics Gem

paper (http://www.unchainedgeometry.com/jbloom/pdf/polygonizer.pdf).

> > Sure. http://www.cyberdanx.co.uk/polygonizer.tar.gz

>

> Wow! Lots more advice from you.

In the code? It's mostly there for my benefit. :) Looking at the c

version made my head hurt and it took a long time to understand what

it does because of all the data structures are managed all over the

place (it's spaghetti). That sort of code tends to obscure the

algorithm. :)

> First, two mutually-recursive bits of advice for you:

>

> 1. Don't annotate types unless you have to.

> and

> 2. Don't optimise prematurely.

>

> You have added explicit type annotations for almost everything. 99% of them

> simply clutter up the code. One of the main advantages of OCaml, and the

> source of its brevity, is type inference.

Went from one extreme to the other... I'll restrain myself in future. :)

> Note that OCaml has flattened out the LatticeHashType module name (only the

> top-most module name remains, Polygonalizer, in the profile). This "equal"

> function may appear to be fully type annotated to the untrained eye. However,

> my spidey sense tells me that "a=b" is doing a structural comparison of a

> pair of 3-tuples which ocamlopt will dispatch to polymorphic comparison

> (compare_val).

>

> If you tweak this code to:

>

> let equal ((i1,j1,k1):t) ((i2,j2,k2):t) = i1=i2 && j1=j2 && k1=k2

>

> Then OCaml is only comparing integers and the program becomes 3x faster!

:s

That's suprising. I would have expected that it was fully type

annotated, but then I thought the types in mli files would have an

impact on polymorphic code being generated...

Thanks Jon.

Chris