- 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 - That makes more sense to me, 31 bit int and all...

thanks :)

--- Radu Grigore <radugrigore@...> wrote:

> --- David Thomas <David_HD@...> wrote:

____________________________________________________

> > --- Jon Harrop <jon@...> wrote:

> > > let def_hash (i,j,k) = i + (j lsl 10) + (k lsl

> 10)

> > Any particular reason behind that in particular?

>

> That is probably a typo since

>

> let def_hash (i, j, k) = i + (j lsl 10) + (k lsl

> 20)

>

> works almost twice as fast.

>

>

> __________________________________________________

> Do You Yahoo!?

> Tired of spam? Yahoo! Mail has the best spam

> protection around

> http://mail.yahoo.com

>

Start your day with Yahoo! - make it your home page

http://www.yahoo.com/r/hs - It seems to me that it would depend on how often j + k

= n, for the same n. The more often, the more

collisions.

--- Jon Harrop <jon@...> wrote:

> On Saturday 03 September 2005 09:37, Radu Grigore

http://www.ffconsultancy.com/products/ocaml_for_scientists

> wrote:

> > That is probably a typo since

> >

> > let def_hash (i, j, k) = i + (j lsl 10) + (k lsl

> 20)

> >

> > works almost twice as fast.

>

> That's weird - it is actually slightly slower here.

> That's probably because I

> altered the problem though...

>

> --

> Dr Jon D Harrop, Flying Frog Consultancy Ltd.

> Objective CAML for Scientists

>

>

__________________________________________________

Do You Yahoo!?

Tired of spam? Yahoo! Mail has the best spam protection around

http://mail.yahoo.com - I completely rewrote it using some of the tips in here and it now

performs very well... well under a second. Could probably render each

frame like the c++ program does. Now I have just one problem

remaining concerning the normals (half faceted, half smooth). I'll put

it up somewhere once I fix that.

Thanks for everyones help.