• Advertisement
Sign in to follow this  

Render Spheres, torus and other complex objects by algorithm?

This topic is 4246 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

Hi everybody. I´m in big trouble. I can´t imagine how I can render, or more precisely, how to create vertex and index info of more complex objects. I mean, due to the sphere example, there is a formula for every point of the sphere, but how do I index this points and how do I evaluate the distance among two points? And this is not all. What about the torus, or this knot objects often seen in demos. I realy want to get deep into this topic. I need your help to start off, because I have absolutely no idea where to start!!! And if it needs complex numbers, no matter, I´m well introduced to it! Thanks Alex

Share this post


Link to post
Share on other sites
Advertisement
I'm going to move this over to GP&T; whilst you might be using Direct3D the basic algorithms/methods for creating primitives is independent of a particular API. Maybe the GP&T regulars can recommend some resources for you [smile]

Check out the D3DX shape drawing functions - several of the ones you mentioned are included "in box" already.

hth
Jack

Share this post


Link to post
Share on other sites
Quote:
Original post by directNoob
Thanks, but I don´t need the premade objects. Instead, I need to do it my self.
There's certainly plenty of good info to be found on this subject (I can offer some tips/links), but just out of curiosity can you explain the context? Why do you need to generate these objects procedurally? And what shapes exactly are you interested in (aside from those that have already been mentioned)?

Share this post


Link to post
Share on other sites
I don't want to hijack the people already helping directNoob, but I wanted to plant this in his mind to help the concept to sink in.

directNoob:
1. For procedural objects, you have to think about how to break it down into a triangluated surface.
2. If you can break it down into rectangular gridlike patches, it's easy to convert that to triangles (cut the quadlaterals in half - viola, triangles)
3. Look for planar, rotational and spherical symmetry to procedurally generate the object.

(just do it!)

Example - sphere
An easy way to create a sphere is to think of it in terms of latitude and longitude.
this image

shows this idea perfectly.
See if you can come up with a process to recreate the points. (hint, in this case, the sphere is basically a 2d grid, wrapped to the shape of a sphere)

-Michael g.

Share this post


Link to post
Share on other sites
@Thr33d
Your sample image suffers from problem due to the singularity at the poles. For spheres, a sub-division approach seems better suitable, especially since mapping coordinates can be interpolated easily.

To subdivide a suitable geometric object (any platonic polyeder will do - start with a tetrahedron for simplicity), you apply a basic subdivision algorithm and simply normalise the vertices.

The following ASCII chart illustrates the idea:

A
/ \
/ B-----C

To subdivide the triangle ABC, you create new points A', B' and C' by
cutting the edges into half.
__
A' = AB / 2
__
B' = BC / 2
__
C' = CA / 2

A
/ A' +...+ C'
/ . . B---+---C
B'

This naturally forms four sub-triangles A'AC, BB'A', CC'B' and A'B'C' (dotted edges).

Repeat the subdivision on the newly created sub-triangles to refine the resulting mesh. A tetrahedron conviniently consists of four equilateral triangles so it's a nice start to test this subdivision out with.

Using an octahedron or even an icosahedron (20 sides) reduces the number of subdivisions (and hence resulting triangles) required to form a smooth sphere.

HTH,
Pat.

Share this post


Link to post
Share on other sites
Hi and thanks.

@jyk:

I just want to get deeper into this material. I´m tired load x files for example.
I want to make my own objects plus, I want to extent my mathematical horizon.
When you have resources, please give it to me! I would be very grateful.
I want to experiment with this object and figure out how the guys in the demo scene are doing it. But the worst thing is, I can´t get behind it myself.
And this disappoints me very much.

@Thr33d:
Ok, that´s easy.
r^2 = x^2 + y^2 + z^2 =>
z = +-sqrt(r^2 - (x^2 + y^2))


With this formula, I get every point on the sphere.
Did you ask for this?

Greetings
Alex

Share this post


Link to post
Share on other sites
A good place to start is here, with the 'Platonic solids' .pdf. Having these shapes available can be a handy point of departure for more complex shapes.

For spheres, the aforementioned lat-long approach is quite easy to code, provided you're not concerned about the irregular distribution of triangles. Otherwise you'll want to take darookie's advice and apply recursive subdivision to an octa- or icosahedron.

A torus can be generated with simple trig; you just need to think about the geometry involved (an inner ring with circumscribing rings at regular intervals) and derive the code accordingly.

From there, procedural generation of meshes can get more or less arbitrary complex. There are subdivision surfaces, generalized cylinders using curves and various types of curve frames - the list goes on. For more advanced meshes you'll need to be comfortable with vector math, and will most likely need to develop as a foundation a mesh class with support for connectivity queries.

Share this post


Link to post
Share on other sites
Or ... you can check the source to freeglut! [smile]

I did that when I wanted to procedurally generate a torus, but never actually got it done [wink].

Share this post


Link to post
Share on other sites
In general, there are some kinds of mathematical descriptions for doing such things.

1st there are parametric surfaces. They are of the general form
S(u,v)
where S is a vector valued function (3 components since we are talking about 3D spaces, I think), and u,v are the parameters (2 components since they should describe a surface in 3D). These equations are fine to generate meshes.

Typical surfaces of this kind are spline patches. But also spheres, cylinders, tori, and others could be given this way, what typically yields in meshes like the one Thr33d showen above. As jyk has written above, using some trigonometrics with u and v makes the way.

2nd there are implicit functions where the locus of 0's defines the surface
f(x,y,z) = 0
where x,y,z are arbitrary space co-ordinates. The surface are just all those co-ordinates that fulfil the equation. Often these functions are algebraic, so that in fact an implicit algebraic surface is given then. These equations are less suitable to make meshes since they are implicit, but they are/maybe fine for other things like ray-tracing, collision detection, and such.

Typical surfaces of this kind are quadrics (i.e. where the function is a 2nd order polynomial): Spheres, ellipsoids, cylinders, some paraboloids, and some hyperboloids. Less often higher order degree polynomials could be found in 3D gfx, e.g. the "hyper-quadrics". Often there must be some additional restrictions active, e.g. to restrict the infinite quadric cylinder to a specified height.

Look e.g. at www.euclideanspace.com or wikipedia for some formulas.

[Edited by - haegarr on July 6, 2006 2:06:48 AM]

Share this post


Link to post
Share on other sites
A good resource for procedural surface construction is Paul Bourke's surface pages.

Edit: Might be a good idea to check out his geometry pages aswell.

Share this post


Link to post
Share on other sites
darookie said: "Your sample image suffers from problem due to the singularity at the poles. For spheres, a sub-division approach seems better suitable, especially since mapping coordinates can be interpolated easily."

@darookie: I was trying to give a simple example because when I read,
"I realy want to get deep into this topic."

I mis-read... thought he *didn't* want to get deep into this topic, (the context supports this)
That's why my example was oversimplified.

@directNoob: you said: Ok, that´s easy.
r^2 = x^2 + y^2 + z^2 =>
z = +-sqrt(r^2 - (x^2 + y^2))
With this formula, I get every point on the sphere.
Did you ask for this?


Yeah... now just sample it in a way that you get a *finite* number of points and "stitch" (not a technical term) them together into triangles.
Others have mentioned using surface patches, splines etc. These methods will help to give a more uniform distribution than a, for instance, cylindrical approach.

A "simple" approach would be (from here)
Treat the sphere as a 2d grid (darookie mentioned why this *wasn't* a good idea already)
have a nested loop, find the x,y,z points for a regular grid wrapped over the surface of the sphere.
(Do you understand what I'm saying?)


Here, I'll get you started (that's what he asked for in his first post - I'm just trying to help him visualize a nieve approach to this)

Write some psuedo-code using u and v as x-axis and y-axis 2d space over the surface of the sphere. Find the x,y,z points for a given 2d UV coordinate
assume RADIUS is a declared variable, you have access to trig functions, and there exists some array to output x,y,z points
put it in the format of


//psuedo-code
//for simplicity's sake, assume cylindrical coordinates
for (theta = 0; theta < TWO_PI; theta+=...)
{ for (z = -1; z < 1; z+=...)
{
//find the x, y, and z, values here
}
}






---
(someone *please* clean this up and slap me around if my example is misleading)
I know it's rather stupid to use cylindrical coordinates for a sphere... but it's a good "first step" to visualizing the x,y,z positions mathematically.

-Michael g.

p.s. If you're "beyond" this already, ignore this, and check out the resources previously mentioned by others.

edit: formatting *ugh*

Share this post


Link to post
Share on other sites
Hello Thr33d.

First of all, thanks for your help by providing as much text.

Before I can proceed, can you explain this text a bit more precisely, please.
Quote:

Write some psuedo-code using u and v as x-axis and y-axis 2d space over the surface of the sphere


I don´t understand the part with the "2d space over the surface of the sphere".

Alex

Share this post


Link to post
Share on other sites
Again, we're simplifing this down to cylindrical coordinates.

Here's how to visualize it

Take a piece of 8.5" x 11" paper. Orient it this way
_____
| |
|_____|

Draw say, 6 dots along the top and bottom edge.
then draw six dots horizontally along the middle.
You can connect the dots with vertical lines if you'd like as well (and if you connect the dots horizontally, you get a kind of grid paper)

Now take this and wrap it, dots on the outside, into a cylinder
See this page for a visual of a cylinder and it unwrapped.

Say you have a ball that this wraps nicely around.

You now have a ball with a cylindrical piece of paper wrapped around it.
The dots down the middle of the paper should be along the 'equator' of the ball.
Now, crumply in the top and bottom so the paper *wraps* against the ball.
(Think about wrapping those oddly shaped gifts for Christmas)

The dots along the top and bottom edges have converged to 2 single points. The points (or, if you've connected the dots with lines, their intersections) represent vertices. If you've drawn lines, these represent triangle edges (except you'll notice they're quadlaterials, you have to divide them each in two, no problem).
Here's a picture of what that (a sphere) formed in this way would look similar to.
here



Since it's kinda silly to have the vertex placement on fixed z-axis spacing, one could modify this to break it up based off of spherical coordinates instead and step along a constant angle interval.

In the end I believe geodesic spheres give the most bang for the vertex :) (Involves starting with a "balanced" convex polyhedron and subdividing the sucker!)

Please heed what the people above have already posted, they'll help you over the hurdle of parametric surfaces, which I didn't bother trying to cover - what I've written is mainly to help you have a simple example.

-Michael g.

Share this post


Link to post
Share on other sites
Thanks again.

But do you have any suggestions where to start? I mean, and you just said it, parametric surfaces.

I feel like a little ant underneath the whole thing and don´t know what to do!?!?

I just need something, from where I can proceed myself.

Again, where do you think, I should start with??? Is it the sphere?
All I want is to render my own procedurally created objects and no bad downloaded objects from the net or any tut. It is not worth to go ahead like I do...
Just begging for little hint once more!

Greetings
Alex

P.S.

@Thr33d


//l = longitude
//c = colatitude
//r = radius
//vb = vertexbuffer
//max = max vertices stored in vb

i = 0 // for the vb count

// colatitude needs just be calculated from 0 to Pi
// longitude needs a full circle, hence 0 to 2*Pi
// this leads to the following

for(c = 0; x < PI; c += 1/6*PI){
for(l = 0; l < 2*PI; l += 1/6*PI){

x = r * cos(l) * sin(c);
y = r * sin(l) * sin(c);
z = r * cos(c);

// the top and bottom point is needed just once,
// so proceed with the next angle
if(c == 0 || c == PI)
c += 1/6*PI;

// store the calculated point in the locked vertex buffer
// for example: #define FVF D3DFVF_XYZ
vb = VERTEX( x , y , z );

i++;
}
}

max = i;





Mybe this is the requested code you asked me for?! I didn´t try it, so I don´t know if it works. This shoud be a point list of the structure of a sphere...
But now, it needs to be indexed.

[Edited by - directNoob on July 6, 2006 8:50:34 PM]

Share this post


Link to post
Share on other sites
The code looks good to me... try it out to check for sure (loop through the list, drawing a point at that 3d location in space, make sure the sphere equation is all good)

About indexing, check out the d3d chm file. Basically though, you'll either use an indexed triagle list, where you feed it an array of indexes, or you feed it the indexes in a "special" way (read up on triagle strips and triangle fans)

For your purposes, just start out with an indexed triangle list.

Then set up the 3 loops to create the sphere's index list
Recognize there are 3 sections: the top (1) and bottom (2) are special (they connect many triangles hingeing off of one point.
The middle is the general case - you have a grid of points, set it up to index these to form triangles.

(I'm pretty sure you understand what I mean, and that you can come up with the code to do this)

Some things to note, (I can't remember the default vertex order CW or CCW)
Always order the indexes for each triangle, with the same rotation order. This is because we generally use closed surfaces, so we can make the triangles single sided - using back face culling. In order to choose a "front" and "back" side, you choose a standard.

1

2 3
CCW "front"

1

3 2

CW "front"

(you probably know that 1-2-3 is the same as 2-3-1 is the same as 3-1-2, so don't worry about absolute positioning of the verticies for index choice, just relative positions)

....

Now, go ahead and write the 3 sections of code mentioned above :)

(After you make it through this exercise, you should have a much better working knowledge of direct3d's architechture. Moving to parametric surfaces with this base of how to draw stuff on the gpu will be most benefical.)

(questions?)
-Michael g.

Share this post


Link to post
Share on other sites
Hi there,

here is a tutorial describing how to procedually generate a sphere. Maybe it is helpful: http://in4k.untergrund.net/html_articles/hugi_27_-_coding_corner_polaris_sphere_tessellation_101.htm

There is also another way of doing it, the result will be a so-called geosphere. You start off by creating a simple cube (hard-coded) and then you start to subdivide each triangle of the cube into two smaller ones, and then subdivide these two smaller ones again, etc... The more often you subdivide the cube's triangles, the more "smooth" the sphere will look. If you finally got a highly subdivided cube you loop through each vertex of it, "shoot" a ray from the center of the cube through the vertex and move the vertex to the point where the ray hits an imaginary sphere around the cube.

For the procedural generation of more complex objects than a sphere (for example meta-balls), you can look at the marching-cubes algorithm which basically extracts a polygonal mesh from an iso-surface.

http://en.wikipedia.org/wiki/Marching_cubes
http://www.essi.fr/~lingrand/MarchingCubes/accueil.html


Share this post


Link to post
Share on other sites
Hi!

Sorry that it took so long, but I had to do something for the shool...

However.

I made it, but the sphere is not a sphere. Its just the half of a sphere.
It´s exactly the same when I use this equation:

r^2 = x^2 + y^2 + z^2


Here it is the problem that you gain

+-r


out of the equation after taking the square root(or how must it be written in english?)

I hoped that with the arc function i yield the absolute values without the +- thing.

Forget this! it works. it is just a matter of " how do i calculate the number of the max vertices?"

Allow me to present the code to you:

void Setup()
{
// Longi -> Longitude
// Colati -> Colatitude

float radius = 1.0f;

// Degree measure
int iLongiDeg, iColatiDeg;
iLongiDeg = iColatiDeg = 5; // Angle of 5 degrees

// Radian measure
float fLongiRad, fColatiRad;
fLongiRad = ((float)iLongiDeg * D3DX_PI)/180.0f;
fColatiRad = ((float)iColatiDeg * D3DX_PI)/180.0f;

// figure out, how many vertices are needed:
// horizontally
int iHorzVertices = 360 / iColatiDeg ;

// vertically
int iVertVertices = 180 / iLongiDeg ;

// this must be improeved, I can´t figure out how much vertices are used!!! bad!!
int iMaxVertices = iHorzVertices * (iVertVertices) * 10 ;

g_iMaxVertices = iMaxVertices;

// now, calc the indices.
int iIndices = 0;
// On the top and on the bottom are triangle strips
// top
iIndices += 1 + iHorzVertices;
// bottom
iIndices += 1 + iHorzVertices;

// the left vertices must be organized in a triangle fan
iIndices += iMaxVertices;

VERTEX *v;
WORD *w;

g_pDev->CreateVertexBuffer(iMaxVertices * sizeof(VERTEX), D3DUSAGE_WRITEONLY,
FVF, D3DPOOL_MANAGED, &g_pvb, NULL) ;

g_pDev->CreateIndexBuffer(iIndices * sizeof(WORD), D3DUSAGE_WRITEONLY,
D3DFMT_INDEX16, D3DPOOL_MANAGED, &g_pib, NULL);

g_pvb->Lock(0, 0, (void**) &v, 0);
float x, y, z;
int topbottom = 1 + iHorzVertices;

int iCounti = 0;
int iCountj = 0;
// Calc the vertices on the colatitue
for(int i= 0; i < 180 / iColatiDeg; i++)
{
// Calc the vertices on the longitude
for(int j = 0; j<360 / iLongiDeg; j++)
{
int index = (iCounti * (360 / iLongiDeg)) + iCountj;

x = radius * cosf(fLongiRad * j) * sinf(fColatiRad * i) ;
y = radius * sinf(fLongiRad * j) * sinf(fColatiRad * i) ;
z = radius * cosf(fColatiRad * i);

v[index] = VERTEX(x,y,z, 0.0f,0.0f,0.0f, 0.0f,0.0f);

if(i * fColatiRad == 0.0f || fabs((D3DX_PI - i * fColatiRad)) <= 0.00001f )
{ i++; j = 0; }

iCountj++;
}
iCounti++;
}
g_pvb->Unlock();


}







I really hope it is readable!
The vertices are badly calculated!
Do you have any suggestions?

Here is a nice picture:
Sphere
Even better image:
Sphere
When the vertices are correctly initiated, i can start indexing it.

Greetings
Alex

[Edited by - directNoob on July 10, 2006 4:35:26 PM]

Share this post


Link to post
Share on other sites
Alright, here is my approach of indexing this sphere.
sphere3

Has anyone some hint for me, how to index this sphere?
This thing is absolutly jagged. And by the way, I get a maximum of vertex count
of 88200 vertices. Is that possible with a longitude and a colatitude of 5 degrees?

Alex

Share this post


Link to post
Share on other sites
Ok, the vertices look good... now to form some usable triangles.

Take a look at this picture:


Now, diving into this section


I've labeled one vertex as "1" another as "2" and so on. We've also labelled some below those as "W+1", "W+2" etc.
W is just a variable chosen to represent the number of vertices Wide the sphere is.

To form triangles (We'll assume CW) using indexes, the first will be something like:

1 -> 2 -> W+1
The next
2 -> W+2 -> W+1
(that's the first quad)

You'll want to loop through all the vertices to create two triangles for each vertex.

Try that out and see where it gets you :)


-Michael g.

p.s. Umm, 5' increments should be (360'/5') * (180'/5') = 2592 vertices (+ 2?)

Share this post


Link to post
Share on other sites
Hi.

Now the result of all is this monster... no, not really a monster;)
Sphere

There is this point in the middle, which I can´t restrain...
But how ever, it works. Thanks a lot. The culling is also the wrong way.
I have to change that to.

So the sphere it almost finished, just a few improvements and its ready for use.
I just have to be aware of the creation process to be able to rebuild it again.

Now, I spoke about more complex objects... I have one in process. It a Sirpinski Tetrahedron. Its almost finished.
I´m not absolutely sure how I can translate these tetras exactly to their correct position, at an arbitrary iteration. well, this is the next task i have to do.
I´m looking forward to see this object, made by myself, on my computer screen!!! My calculs are looking great, ... on the paper. :D!

However.
Thanks again.

Alex

Share this post


Link to post
Share on other sites
Now it looks like this:
Sphere

Why doesn´t Direct3D cull this mesh points from angle 0.0f und angle pi?

Share this post


Link to post
Share on other sites
Culling seems to be working fine.

Try to do a solid fill rendering of the thing.

You'll remember in your code there are 3 sections for creating the triangle buffer. The 2 endpoints, and the middle. (We looked at how to do the middle already.)

My guess is, you're incorrectly ordering every other triangle in those endpoints :)

Anyway, Try to do a solid fill render and clean up that stuff :)

-Michael g.

p.s. I mainly wanted to help you out with the concepts of how to create *any* sort of 3d triangulated objects. A sphere just happened to be easy.

you should now pay attention to those people above (e.g. darookie, jyk, haegarr ,and eq) who know more than me.
What I've taught you is a basic, conceptual way of creating a sphere's verticies and triangles. Now take that sort of knowledge (and the general idea of triangulation) and work on some parametric surfaces in a more optimal fashion :)

Good luck (oh yeah, you'll probably want to try assigning UV coordinates at some point in time. Since you're using D3d, there's some sort of texture wrapping functionality (it's not texture repeating) which will allow you to loop from 0.95 -> 0.0 travelling through 1.0 tex coord. This will be invaluable to you in using textures and indexed triangles. *grin* good luck again)

Share this post


Link to post
Share on other sites
Thanks a lot for this fine "private lession". I appreciate that you took your time for my problem.

Greetings
Alex

Share this post


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

  • Advertisement