Hi there!

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.

Sadly, there is not much to be found about real 3D-Objects,
like POV-Ray does (a sphere is a sphere, no hunch-bunch-
big-bag full of facettes). And while thinking about that,
I was wondering how one could actually tesselate an
object (creating some sort of mesh from the given object)
using only POV-Ray.

If this could be done somehow, it would open the door for
those complex object-modifications a mesh-renderer is able
to, but POV-Ray is not (I'd do this by introducing mesh-macros
to POV-Ray). A mentioned feature in the docs is the "bend"
of objects...

So, anyone has some tutorials, links or sites concerned with
tesselation? I'm rather keen at getting to know the stuff. :-)

Tim

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

Post a reply to this message

Tim Nikias <tim### [at] gmxde> wrote:
: And while thinking about that,
: I was wondering how one could actually tesselate an
: object (creating some sort of mesh from the given object)
: using only POV-Ray.

  Old idea. In fact, even a patch has been done which tesselates any
traceable povrary object (the same patch gives means to write this mesh
to, for example, a file).
  The problem with the patch is that it doesn't work well. It should be
rewritten, using a different algorithm, probably the marching triangles.

-- 
#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

>
>   Old idea. In fact, even a patch has been done which tesselates any
> traceable povrary object (the same patch gives means to write this mesh
> to, for example, a file).
>   The problem with the patch is that it doesn't work well. It should be
> rewritten, using a different algorithm, probably the marching triangles.
>

I know its no new idea, I'm by no means and explorer of the unknown! ;)

But I asked for information regarding the algorithms and how to implement
that in SDL. You see, even "the marching triangles" is something I don't
know what to do with...

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

Post a reply to this message

Tim Nikias wrote:

> So, anyone has some tutorials, links or sites concerned with
> tesselation? I'm rather keen at getting to know the stuff. :-)

you might be interested by my experiments with an evolution of 3.1
(based on a patch made by Warp), see http://grimbert.cjb.net/pov/patch.html
for some pictures...

Beware, it's in french, so you may want to use some web translator
such as http://www.babelfish.org/

I would be interested to get more information about the proposed
deformations (formula for bend and any other kind of deformations).

Can you provide your book's reference ?
-- 
Non Sine Numine
http://grimbert.cjb.net/

Post a reply to this message

>
> 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.

As to the formulars and algorithms, I thought about
tesselation first, then move on to algorithms for usage
with those meshes. As of yet, I don't have need for
meshes, and thus don't think much about algorithms
for that...

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

Post a reply to this message

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