>   I have been thinking about using the marching triangles algorithm in the
> tesselation patch, as I think it gives much better results than marching
> cubes/tetrahedrons.

	I guess the problem with "marching" algorithms is the fixed step
used to sample the space; even if you try using an adaptive method, as
supersampling. While Delaunay triangulation - if possibly implemented in
a tesselation procedure - would give triangles of different sizes according
to the local complexity of the scanned object (so leading to the curvature
dependant tessellation discussed earlier). Triangles are not required to have
vertices of the same size; complexes shapes give small, numerous triangles,
while relative flat shapes give just a few large triangles. This could in
principle give good results even for simple flat objects, e.g. cubes,
including at the edges.
	I guess Christoph Hormann was actually thinking about this kind
of method, since AFAIR it starts from a point and expands in any direction.

	By the way, I don't think it would be a good idea to change the
tessellation accuracy according to distance from viewpoint, simply in
order to save memory. Tesselation can be made just once, for instance
in an animation. And that's much better for exporting (probably one of
the main purpose actually).

	- NC

Post a reply to this message

On Wed, 10 Oct 2001 22:46:10 +0200, Nicolas Calimet wrote:
>	I guess the problem with "marching" algorithms is the fixed step
>used to sample the space; even if you try using an adaptive method, as
>supersampling. While Delaunay triangulation - if possibly implemented in
>a tesselation procedure - would give triangles of different sizes according

I think you're thinking of something besides Delaunay triangulation.  That's
a purely 2d technique and has nothing to do with meshes.

-- 
#local R=rgb 99;#local P=R-R;#local F=pigment{gradient x}box{0,1pigment{gradient
y pigment_map{[.5F pigment_map{[.3R][.3F color_map{[.15red 99][.15P]}rotate z*45
translate x]}]#local H=pigment{gradient y color_map{[.5P][.5R]}scale 1/3}[.5F
pigment_map{[.3R][.3H][.7H][.7R]}]}}}camera{location.5-3*z}//only my opinions

Post a reply to this message

You all are talking about problems very well known to engineers. We use to
call this kind of operation as 'meshing an object'.
I'm looking for some papers I've read about the problem of meshing for
Computational Fluid Dinamics problems as soon as I can find them I will
publish them on my internet site and advise you all.

Massimiliano Cirri


_____________________________________________
Eng. Massimiliano Cirri
Ph.D. Student
Department of Energetics "Sergio Stecco"
e-mail: m.c### [at] ingunifiit
tel: +39 055 4796239
fax: +39 055 4796342
private fax: +39 02 700 544 824
_____________________________________________



"Ron Parker" <ron### [at] povrayorg> ha scritto nel messaggio
news:slr### [at] fwicom...
> On Wed, 10 Oct 2001 22:46:10 +0200, Nicolas Calimet wrote:
> > I guess the problem with "marching" algorithms is the fixed step
> >used to sample the space; even if you try using an adaptive method, as
> >supersampling. While Delaunay triangulation - if possibly implemented in
> >a tesselation procedure - would give triangles of different sizes
according
>
> I think you're thinking of something besides Delaunay triangulation.
That's
> a purely 2d technique and has nothing to do with meshes.
>
> --
> #local R=rgb 99;#local P=R-R;#local F=pigment{gradient
x}box{0,1pigment{gradient
> y pigment_map{[.5F pigment_map{[.3R][.3F color_map{[.15red
99][.15P]}rotate z*45
> translate x]}]#local H=pigment{gradient y color_map{[.5P][.5R]}scale
1/3}[.5F
> pigment_map{[.3R][.3H][.7H][.7R]}]}}}camera{location.5-3*z}//only my
opinions

Post a reply to this message

> I think you're thinking of something besides Delaunay triangulation.  That's
> a purely 2d technique and has nothing to do with meshes.

	Mhhh, guess you're wrong, sorry.
	Delaunay triangulation is commonly used in 3D (and maybe more dim.)
to create meshes from different kind of data, e.g. a cloud of points. I had
got a lot of internet references when looking at a related problem (mesh
simplification) but unfortunately lost all while moving. Probably worth to
search again since there might have new stuffs appearing  :o)

	- NC

Post a reply to this message

On Thu, 11 Oct 2001 16:40:24 +0200, Nicolas Calimet wrote:
>> I think you're thinking of something besides Delaunay triangulation.  That's
>> a purely 2d technique and has nothing to do with meshes.
>
>	Mhhh, guess you're wrong, sorry.
>	Delaunay triangulation is commonly used in 3D (and maybe more dim.)
>to create meshes from different kind of data, e.g. a cloud of points. I had
>got a lot of internet references when looking at a related problem (mesh
>simplification) but unfortunately lost all while moving. Probably worth to
>search again since there might have new stuffs appearing  :o)

But it's not triangulation in that case; it's a more generalized sort of
related thing involving solids.  The whole idea of triangulation doesn't 
make sense unless all of the points are in a plane, because the notion of
"none of the other points fall in the circumscribed circle" doesn't make
sense.  You can construct a Voronoi diagram of sorts in 3-space and then 
take something that resembles a dual of that, but it wouldn't be quite the 
same sort of dual (because it swaps volumes with vertices and faces with 
edges, rather than the 2d version that swaps faces with vertices and has a 
1:1 correspondence between the two sets of edges) and it shouldn't be 
called a Delaunay triangulation (if for no other reason than that the 
mathematically interesting part of the result isn't the triangles, but the 
solids that they bound.)

-- 
#local R=<7084844682857967,0787982,826975826580>;#macro L(P)concat(#while(P)chr(
mod(P,100)),#local P=P/100;#end"")#end background{rgb 1}text{ttf L(R.x)L(R.y)0,0
translate<-.8,0,-1>}text{ttf L(R.x)L(R.z)0,0translate<-1.6,-.75,-1>}sphere{z/9e3
4/26/2001finish{reflection 1}}//ron.parker@povray.org My opinions, nobody else's

Post a reply to this message

On 11 Oct 2001 11:37:08 -0400, Ron Parker wrote:
>>	Delaunay triangulation is commonly used in 3D (and maybe more dim.)
>>to create meshes from different kind of data, e.g. a cloud of points. I had
>>got a lot of internet references when looking at a related problem (mesh
>>simplification) but unfortunately lost all while moving. Probably worth to
>>search again since there might have new stuffs appearing  :o)

Here's a good place to start (and they call the 3d process tetrahedralization,
which is a better word.)

http://www.ics.uci.edu/~eppstein/pubs/geom-tri.html

-- 
plane{-z,-3normal{crackle scale.2#local a=5;#while(a)warp{repeat x flip x}rotate
z*60#local a=a-1;#end translate-9*x}pigment{rgb 1}}light_source{-9red 1rotate 60
*z}light_source{-9rgb y rotate-z*60}light_source{9-z*18rgb z}text{ttf"arial.ttf"
"RP".01,0translate-<.6,.4,.02>pigment{bozo}}light_source{-z*3rgb-.2}//Ron Parker

Post a reply to this message

Ron Parker wrote:
> 
> On Thu, 11 Oct 2001 16:40:24 +0200, Nicolas Calimet wrote:
> >> I think you're thinking of something besides Delaunay triangulation.  That's
> >> a purely 2d technique and has nothing to do with meshes.
> >
> But it's not triangulation in that case; it's a more generalized sort of
> related thing involving solids.

	Okay, I won't discuss about terminologies since my skills in maths
are fairly limited, not yours  ;o)  I was just recalling about those possi-
bilities of constructing meshes in a similar way the Delaunay triangulation
works (and yes I remember about the relation with Voronoi diagrams)

> [from your second answer]
> Here's a good place to start (and they call the 3d process tetrahedralization,
> which is a better word.)

	Fine for me. Now I feel a bit more mathematician  :o)

> http://www.ics.uci.edu/~eppstein/pubs/geom-tri.html

	Wow, I forgot that D. Eppstein works on so many things... I actually
did some recent (and current) work using graph theory and did not remind that
he was also publishing on this mesh problems. I'm sure this link it basically
the first one I found at that time... Thanks for pointing it out again !

	- NC

Post a reply to this message

On Thu, 11 Oct 2001 20:43:03 +0200, Nicolas Calimet wrote:
>> http://www.ics.uci.edu/~eppstein/pubs/geom-tri.html
>
>	Wow, I forgot that D. Eppstein works on so many things... I actually
>did some recent (and current) work using graph theory and did not remind that
>he was also publishing on this mesh problems. I'm sure this link it basically
>the first one I found at that time... Thanks for pointing it out again !

I have to confess that I'm an afficionado of his Geometry Junkyard; I'm
always scrounging around there looking for stuff I can turn into cool 
textures or primitives or whatever.  Lately I've been slumming in the 
"tilings" section, trying to get up the nerve to write a penrose pattern.

(For those playing along at home, the Geometry Junkyard is at
http://www.ics.uci.edu/%7Eeppstein/junkyard/topic.html )

--
#macro R(L P)sphere{L __}cylinder{L P __}#end#macro P(_1)union{R(z+_ z)R(-z _-z)
R(_-z*3_+z)torus{1__ clipped_by{plane{_ 0}}}translate z+_1}#end#macro S(_)9-(_1-
_)*(_1-_)#end#macro Z(_1 _ __)union{P(_)P(-_)R(y-z-1_)translate.1*_1-y*8pigment{
rgb<S(7)S(5)S(3)>}}#if(_1)Z(_1-__,_,__)#end#end Z(10x*-2,.2)camera{rotate x*90}

Post a reply to this message

in news:slr### [at] fwicom Ron Parker wrote:

> ately I've been slumming in the 
> "tilings" section, trying to get up the nerve to write a penrose
> pattern. 

Pure penrose or this n-dimensinal quasicrystal thing?

http://www.math.ubc.ca/~robles/tiling/quasitiler.html
http://www.math.ubc.ca/~robles/tiling/quasiinfo.html

Ingo

-- 
Photography: http://members.home.nl/ingoogni/
Pov-Ray    : http://members.home.nl/seed7/

Post a reply to this message

On 11 Oct 2001 18:00:06 -0400, ingo wrote:
>in news:slr### [at] fwicom Ron Parker wrote:
>
>> ately I've been slumming in the 
>> "tilings" section, trying to get up the nerve to write a penrose
>> pattern. 
>
>Pure penrose or this n-dimensinal quasicrystal thing?

Penrose tiles are a subset of the quasicrystals, so I'd obviously go with 
the more general case.  But of course I won't have time to even think about
that until after 3.5.

-- 
#local R=rgb 99;#local P=R-R;#local F=pigment{gradient x}box{0,1pigment{gradient
y pigment_map{[.5F pigment_map{[.3R][.3F color_map{[.15red 99][.15P]}rotate z*45
translate x]}]#local H=pigment{gradient y color_map{[.5P][.5R]}scale 1/3}[.5F
pigment_map{[.3R][.3H][.7H][.7R]}]}}}camera{location.5-3*z}//only my opinions

Post a reply to this message