Jump to content
  • Advertisement
Sign in to follow this  
Marty666

tesselating a tetrahedron

This topic is 5393 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Tesselating a tetraheron and pushing the vertices out to unit length won't give me regular triangles. I tesselate by dividing all edges and creating 4 faces. Since the distances from the origin to the original vertices and the distances to the centers of the edges are all the same i think my sphere should end up with uniform sized faces. I use the tetrahedron because i want all triangles set up like this:
v0 .. v2 = verts
e0 .. e2 = edges

    v2      .
    /\      .
  e2  e1    .
  /    \    .
v0--e0--v1  .
and i want edge i on a face neighbouring edge i on it's neighbours face... this is an unfolded tetrahedron. You can see this works on a tetrahedron keeping all faces counterclockwise:
__0_____0___   .
\    /\    /   .
 1  2  1  2    .
  \/_0__\/     .
   \    /      .
    1  2       .
     \/        .
The problem is that a tetrahedron doesn't return a regular sphere (OR DOES IT?) I haven't found another regular shape to tesselate that obeys the above rules. Please comment, thanx! Marty

Share this post


Link to post
Share on other sites
Advertisement
I think that should work, assuming the initial vertices are already at unit distance from the origin.

Another shape that will work is an icosahedron (better known as "twenty-sided die").

Share this post


Link to post
Share on other sites
Quote:

Tesselating a tetraheron and pushing the vertices out to unit length won't give me regular triangles. I tesselate by dividing all edges and creating 4 faces.

i don't quite get what you want to do. What you mean by "regular triangles"? Equilateral triangles?

Quote:

Since the distances from the origin to the original vertices and the distances to the centers of the edges are all the same i think my sphere should end up with uniform sized faces.

Where origin is? in center of tetrahedron?
What mean "sized"? Have equal area? "the distances to the centers of the edges" from what?
Do you set your vetrices after tesselation to be unit-length?

If you'll tesselate tetrahedron and then set all vertice vectors to be unit length, i'm almost sure you'll get a polyhedra that will have 4 bigger equilateral triangles and 12 smaller non-equilateral triangles, 16 triangles total.


What rules you want it to obey?


anyway, if you want to make polyhedron with vertices placed at equal distances from center, and composed of equal triangles, you can try
1:icosahedron, it have 20 equal faces(more than your 16-face polyhedra), and all edges is equal too, it'e regular polyhedron.

2:dodecahedron with additional vertice at center of each face, so each face is splitten into 5 triangles. Center vertices must be renormalized. So you'll have 60 equal triangles.(it will be slightly non-equilateral triangles)
edit: if by above rules you mean that thing about face edges, that 60-face thing made from dodecahedron probably will not work.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you start with a regular tetrahedron, each of the four faces is an equilateral triangle like this:

____________ .
\ / .
\ / .
\ / .
\ / .
\ / .
\/ .
[/code

If I understand correctly, you want to subdivide the four faces each into four smaller equilateral triangles, like this:

____________ .
\ /\ / .
\ / \ / .
\/____\/ .
\ / .
\ / .
\/ .
[/code

And the problem is that when you blow out the new vertices that bisect each of the edges of the original triangle, your new sub-triangles aren't all the same size.

This is inevitable. The middle face will always be bigger because you're moving apart all three of its vertices, but the corner triangles only are only having two of their vertices moved apart. (By moving apart, I mean moving out to lie on the surface of the sphere on which the original four vertices lie, which also lengthens the distance between them in the direction of the line connecting them).

If you want completely regular, equal angle and equal length sided faces, you need to use a Platonic solid (such as the regular tetrahedron or icosahedron). But you can't keep adding more faces by subdividing the existing ones if you want to keep all faces equal shape and size.

Share this post


Link to post
Share on other sites
... previous was me.


If you start with a regular tetrahedron, each of the four faces is an equilateral triangle like this:

____________ .
\ / .
\ / .
\ / .
\ / .
\ / .
\/ .


If I understand correctly, you want to subdivide the four faces each into four smaller equilateral triangles, like this:

____________ .
\ /\ / .
\ / \ / .
\/____\/ .
\ / .
\ / .
\/ .


And the problem is that when you blow out the new vertices that bisect each of the edges of the original triangle, your new sub-triangles aren't all the same size.

This is inevitable. The middle face will always be bigger because you're moving apart all three of its vertices, but the corner triangles only are only having two of their vertices moved apart. (By moving apart, I mean moving out to lie on the surface of the sphere on which the original four vertices lie, which also lengthens the distance between them in the direction of the line connecting them).

If you want completely regular, equal angle and equal length sided faces, you need to use a Platonic solid (such as the regular tetrahedron or icosahedron). But you can't keep adding more faces by subdividing the existing ones if you want to keep all faces equal shape and size.

Share this post


Link to post
Share on other sites
Hi.

* Equal sized triangles = equal area on triangles.
* Normalisation is not a problem.
* The origin is set up that all the vertices are at unit vectors from the origin. The origin is in the center of the tetrahedron and the tetrahedron has equal edges.

When tesselating an octahedron this way the faces look to be having the same size (same area). The sphere is nicely round (all vertices are normalized).
I did this, but an octahedron is impossible to build obeying the following rules:


NEIGHBOUR RULE:

This->Neighbour[At_edge_0]->Neighbour[At_Edge_0] = This

This->Neighbour[At_edge_1]->Neighbour[At_Edge_1] = This

This->Neighbour[At_edge_2]->Neighbour[At_Edge_2] = This


Read the above again, the pointer to heighbour of the neighbour returns the face we started in. (see drawing in first post)


EDGE RULE:
The edges are defined as:
edge0 = vert 0..1
edge1 = vert 1..2
edge2 = vert 2..0

so vertices 0, 1, 2 are a counterclockwise triangle which is the same as edges 0, 1, 2 (the order 0, 1, 2 is important!)

2 .
/ \ .
/ \ .
2 1 .
/ \ .
0____0____1 .



PRESERVATION OF NEIGHBOUR AND EDGE RULE AFTER TESSELATION:

.
/\ .
2 1 .
/_0__\ .
/\ /\ .
2 1 2 1 .
/_0__\/_0__\ .



THE PROBLEM:
This is impossible with any platonic solid i tried so far (i have these dice, so i could try out with them) exept for the tetrahedron (see unfolded tetrahedron in first post). Only the tetrahedron gives (as the anonymous poster explained) irregular triangles (not all edges are the same size and the area is not equal for al the newly created faces after normalisation).
My octahedron gives nice results tesselating this way, but has counterclockwise and clockwise triangles to obey the NEIGHBOUR RULE, which violates the EDGE RULE.

THE QUESTION:
Is there a way to start with a solid that will obey both rules and creates triangles which have equal edges and equal areas?

Thanx,
Marty

PS: A twenty sided die cannot obey the NEIGHBOUR RULE...

Share this post


Link to post
Share on other sites
i think your neighbor rule is only conserved on primitives with an integer multiple of 3 triangles around each vertex: this only goes with the 4-sided primitive.

no subdivision method will create equal triangles, however, you can correct a lot of the distortion either by making the edges springs, and the verts masses and simulate this mass spring system, or some algebraic correction. as a rule of thumb though: the more tris you start with, the more uniform the result will be.

also, am i wrong in assuming your edge rule isnt really needed, but merely a convenience? not saying conveniences are a bad thing, certainly since your code can be quite a bit shorter and more elegant with this contraint, but a 4-sided primitive really leaves to be desired...

Share this post


Link to post
Share on other sites
Hi Eelco (and rest),

It's not only a convenience (although it really is convenient), it's also to speed up the code.

I have a recursive algorithm to find a face that is hit by a beam with a given direction from the origin.
It starts with a check which of the first generation faces the line crosses. Then it checks which child is hit, then for the grandchildren, etc.
This is a lot faster when my sphere is set up nicely.

I created the neighbour pointers to be able to tesselate quickly and still not do any vertexes double. If the neighbour(s) are allready tesselated i can use their vert(s) for the new faces. The code gets really ugly if the neighbours are not set up this way and gets a lot more complicated (unless i store all neighbours edges in every face)

Marty

Share this post


Link to post
Share on other sites
well,and how i woulda do it:
Use a icosohedron as base shape.Make a sphere out of it by non-recursively tesselating faces(well,you can recursively tesselate but it's needed to be possible to do that w/o recursion), and THEN renormalizing vertices of faces. Let each face have associated surface coordinate system with axises along edges of triangle.Let's call it, say, u,v coordinates . So coordinates of vertices is u=0,v=0;u=1,v=0;v=1,u=0 .

So,for example, finding vertices of subdivised face it's simply
for(i=0;i<N;i++)
for(j=0;j<=i;j++){u=i;v=j; WorldCoordFrom_uvCoords=Corner+u*Edge1+v*Edge2;}
(draw it on paper)

Algo:
Find face of icosohedron that is hit by beam(say,you can do it by finding largest positive dot product of icosohedron face normal and beam. It's enough to do 10 normals(symmetry) and find smallest negative dot product as well and then select one that have larger absolute value.
You can avoid checking unnecessary normals using sign of x, y , and z components of the vectors, or using values of dot products with some normal to find if it needed to check other normals.
)

Then note that intersection of beam with sphere surface corresponds to intersection of beam with face prior to renormalizing. So find "u,v" coordinates of intersection of beam with icosohedron face. Then find subdivised face it have intersected from "u,v" coordinates, analitically, no recursion needed, no rules needed, no strange simplifications needed....

Share this post


Link to post
Share on other sites
Ok, this is where my other thread starts... That's where I was still working on an octahedron:

http://www.gamedev.net/community/forums/topic.asp?topic_id=272894

I get the idear, but I can't figure out a way to tesselate not using a recursive function. With a recursive function the u/v coordinates are messed up.

Thanx,
Marty

PS: Check Dmytry's site, very nice rendered landscape images

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!