Tim Nikias wrote:
> 
> I was wondering how one could actually tesselate an
> object (creating some sort of mesh from the given object)
> using only POV-Ray.

The algorithm that comes to mind as I sit here is to slice up 3-d
space into cubes, and identify which cubes have edges which intersect
the surface of the object in question.  The patch of surface that is
contained by each cube could then be replaced with a handful of
triangles (probably no more than 12, likely averaging about four per
cube).

The smaller the cubes, the better the approximation.  The
time taken varies inversely with the volume of the cubes.

-- 
ICQ: 46085459

Post a reply to this message

John VanSickle <evi### [at] hotmailcom> wrote:
: The algorithm that comes to mind as I sit here is to slice up 3-d
: space into cubes, and identify which cubes have edges which intersect
: the surface of the object in question.  The patch of surface that is
: contained by each cube could then be replaced with a handful of
: triangles (probably no more than 12, likely averaging about four per
: cube).

: The smaller the cubes, the better the approximation.  The
: time taken varies inversely with the volume of the cubes.

  That's the so-called "marching cubes algorithm".
  I think it's patented in some countries where patenting these kind of
things is possible.

  AFAIK the marching triangles algorithm gives a better result and is free
everywhere.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote:
>   That's the so-called "marching cubes algorithm".
>   I think it's patented in some countries where patenting these kind of
> things is possible.
>
>   AFAIK the marching triangles algorithm gives a better result and is free
> everywhere.


probably not very long anymore ... if the "right" people read this, they will
in the
former countries, where it is possible to patent these kind of things, patent
it ...

how can we prevent this ?

--
#macro J(N A)#local a=mod(N 3);#local W=<int(mod(A,4)*2)int(-A/4)9>*2;#if
(!mod(a 2))sphere{W,2,2pigment{color rgb<a*5A/2W.x/A*5>}}#if(a<1)sphere{W
+<2,0>2 2pigment{color rgb<a*10A 10>}}#end#end#if(N>3)J(int(N/3)A+1)#end#
end blob{J(29229171 0)threshold 1translate<-6 3>}/******Jan Walzer******/

Post a reply to this message

Now that I got to know the "marching cubes" algorithm,
could you please be so kind and describe the
"marching triangles" as well?

As mentioned in some other posts of this thread, I don't
have the knowledge and am actually asking for that. Though
its nice to follow discussions on this algorithm vs that algorithm,
and patent pending stuff (that "stuff" is really important, if we
want to publish our work), its no use if you don't know
"this" algorithm and "that" algorithm and understand about
every fourth word (which include "and", "or"... ;) )

Don't take this rudely (lately, people tend to get a little jumpy at
the newsgroups), I am just asking!

Tim

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html

Post a reply to this message

In article <3c5859f0@news.povray.org>, "Jan Walzer" <jan### [at] lzernet> 
wrote:

> probably not very long anymore ... if the "right" people read this, 
> they will in the former countries, where it is possible to patent 
> these kind of things, patent it ...

I think if there is evidence an algorithm has already existed, it can no 
longer be patented. The requirements are that it is not a trivial or 
obvious solution and that it is original...but I'm not an expert.
I don't know how they got the marching cubes patent, it seems like a 
very trivial and obvious solution to me. Probably got people who didn't 
know any better to approve it. But we don't have to worry about the 
marching triangles algorithm getting patented, it is too widely known 
and used.

-- 
Christopher James Huff <chr### [at] maccom>
POV-Ray TAG e-mail: chr### [at] tagpovrayorg
TAG web site: http://tag.povray.org/

Post a reply to this message

Jan Walzer <jan### [at] lzernet> wrote:
: probably not very long anymore ... if the "right" people read this, they will
: in the
: former countries, where it is possible to patent these kind of things, patent
: it ...

: how can we prevent this ?

  You can't patent things which have been public and known for years.

  If you want a patent, you have to get the patent first, and then publish
the idea.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

Tim Nikias <tim### [at] gmxde> wrote:
: Now that I got to know the "marching cubes" algorithm,
: could you please be so kind and describe the
: "marching triangles" as well?

  I don't remember any webpage right now, but there are excellent ones
out there examplining the algorithm. I think it's a bit more complicated
than the marching cubes (which is to expect, as it should give a much better
result).
  Probably google will help in this.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

In article <3C586235.8A2E4A51@gmx.de>, Tim Nikias <tim### [at] gmxde> 
wrote:

> Now that I got to know the "marching cubes" algorithm,
> could you please be so kind and describe the
> "marching triangles" as well?

http://www.google.com/search?hl=en&q=marching+triangles

http://www.antinews.com/florin/mt2.txt

-- 
Christopher James Huff <chr### [at] maccom>
POV-Ray TAG e-mail: chr### [at] tagpovrayorg
TAG web site: http://tag.povray.org/

Post a reply to this message

Tim Nikias wrote:
> 
> >
> > Can you provide your book's reference ?
> 
> I guess something got wrong with the way I formulated my
> intents. I do not have any book, nor any useful reference found
> yet, and I'm asking for just that.

But you write earlier:
>>> I was strolling through a book-store these last days and found
>>> a book on 3D-Raytracing, the techniques and math behind
>>> it, as well as programming etc.

So, sorry to bother you, but I was really interested about this kind
of books... Just to get ideas of what can be done with a mesh,
because I'm just one step ahead with the mesh generation, but unless
there is some deformations, using a mesh is not really exciting.

> 
> As to the formulars and algorithms, I thought about
> tesselation first, 

If you went to my page, you can have seen four approaches:
 - two based on Warp patch, using insideness test and tracing ray on original
   (tesselate and tessel, which differs mainly by how the cube holding the
    tetrahedrons is replicated to fill the bounding box.)
 - two based only on insideness test (cristal and cubicle, which
   differs by the number of possible normals).

Of course, if you have any other ideas, you're welcome to share...

-- 
Non Sine Numine
http://grimbert.cjb.net/
Puis, s'il advient d'un peu triompher, par hasard,

Post a reply to this message

>
> So, sorry to bother you, but I was really interested about this kind
> of books... Just to get ideas of what can be done with a mesh,
> because I'm just one step ahead with the mesh generation, but unless
> there is some deformations, using a mesh is not really exciting.
>

Oh, you guys meant THAT book. Its was written by X Watt (forgot
the first name) and is entitled "Raytracing and Programming" (or
something very similiar). It mainly covers what a mesh is, how you
generate it using modellers (no tesselation algorithms, or
algorithms for bending, twisting etc), and then moves on to what
raytracing is and how it can be implemented.

>
> If you went to my page, you can have seen four approaches:
>  - two based on Warp patch, using insideness test and tracing ray on original
>    (tesselate and tessel, which differs mainly by how the cube holding the
>     tetrahedrons is replicated to fill the bounding box.)
>  - two based only on insideness test (cristal and cubicle, which
>    differs by the number of possible normals).
>
>

I'll have a look!

> Of course, if you have any other ideas, you're welcome to share...
>

I'll come up with some and share!

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html

Post a reply to this message