Jump to content
  • Advertisement
Sign in to follow this  
pim

Geometric shapes/solids generation

This topic is 4830 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! I was wondering of anybody know of a good place to look for information on generating different geometric shapes/solids - everything from the simplest to the more complex (disc, plane, torus, torus knot, sphere, icosahedron++)? I've found a couple of pages but they don't add information about normal and texture coordinate generation. Thanks edit: Mathworld has some nice models of different shapes, also unwrapped - but they don't supply the coordinates of the unwrapped shapes :( [Edited by - pim on July 24, 2005 10:42:16 AM]

Share this post


Link to post
Share on other sites
Advertisement
Can't help you with the texture coordinates, but here's some random information that may be useful.

This paper (which you may have already seen) has coordinate and connectivity info for various platonic solids.

Spheres can be constructed with trig, but the triangle distribution is not even. An alternate method is to start with a faceted solid and repeatedly subdivide the faces to the desired level of detail, then normalize and multiply by the radius. This can be extented to ellipsoids by having a different radius for each axis. Normals for a sphere are trivial, and normals for an ellipsoid can be found with a little calculus.

Cylinders, discs, tori, and cones can be constructed with trig. In some cases the normal is clear; in other cases, such as the discontinuities in the surface of a cylinder or cone, I'm not sure what the correct normal should be...

Torus knot? Haven't done it myself, but I'm thinking you could find the medial structure by parameterizing the inner and outer angles of the torus, and then tessellate using a Frenet frame, but I'm just guessing.

As with spheres, other shapes with curved components, such as capsules and lozenges, can be created through subdivision.

I have some sketch code lying around to construct meshes for Platonic solids, spheres, ellipsoids, tori, solid and hollow cylinders, capsules, and cones. I don't think I got around to adding normals, but I'd be glad to post the code if you're interested.

Share this post


Link to post
Share on other sites
Some code would be nice, yes :D
I've made torus, sphere, disc, cube and some of the different platonic solids before (though I would like to see your code :)) but now I'm planning to make a couple of different classes to create and manipulate different solids and for this I need good control over how I generate the different solids. I would like to be able to make three different types of the same solid:

1: Optimal
Only as many vertices as needed. For use with simple shading/no texturing

2: Separate polys
Separates the shape into polygons (with different amount of vertices) Good for platonic solids with flat shading.

3: Unwrappable
As few vertices as possible while still keeping unique texture coordinates

Share this post


Link to post
Share on other sites
Paul Bourke's site (http://astronomy.swin.edu.au/~pbourke/) has some great stuff on generating 3d shapes in the geometry section.

Share this post


Link to post
Share on other sites
Ok, here is my mesh class (just sketched out at the moment - a work in progress). You got me interested, so I added torus knots this afternoon. Here's an image:



Quote:
I would like to be able to make three different types of the same solid:

2: Separate polys
Separates the shape into polygons (with different amount of vertices) Good for platonic solids with flat shading.
I haven't tried it, but I think you could accomplish this by calling the 'subdivide' function the desired number of times after creating the initial mesh.

Here's the code. (I think you can only include so much text in one post, so I'll post half the code here and half in another post.)


// --------------------------------------------------------------------------------------
// FILE: jykMesh.h
// --------------------------------------------------------------------------------------

#ifndef JYKMESH_H
#define JYKMESH_H

#include "jykMatrix3.h"
#include "gl.h"
#include <vector>
#include <algorithm>
#include <assert.h>

namespace jyk {
namespace geom {

template <class T = float>
class Mesh
{
public:

Mesh();
Mesh(unsigned int numVerts, unsigned int numIndices);

void MakeTetrahedron(T s = (T)1.0);
void MakeHexahedron(T s = (T)1.0);
void MakeOctahedron(T s = (T)1.0);
void MakeDodecahedron(T s = (T)1.0);
void MakeIcosahedron(T s = (T)1.0);
void MakeCylinder(T r, T l, const Vector3<T>& axis, unsigned int lod);
void MakeCylinder(T ro, T ri, T l, const Vector3<T>& axis, unsigned int lod);
void MakeEllipsoid(const Vector3<T>& C, T rx, T ry, T rz, unsigned int lod);
void MakeSphere(const Vector3<T>& C, T r, unsigned int lod);
void MakeTorus(T r1, T r2, const Vector3<T>& axis, unsigned int lod1, unsigned int lod2);
void MakeTorusKnot(T r1, T r2, T r3, int p, int q, const Vector3<T>& axis, unsigned int lod1, unsigned int lod2);
void MakeCapsule(T r, T l, const Vector3<T>& axis, unsigned int lod);
void MakeCone(T r, T l, const Vector3<T>& axis, unsigned int lod);
void MakeBox(const Vector3<T>& e);

void Subdivide();

void Draw(T r = (T)1.0, T g = (T)1.0, T b = (T)1.0) const;

private:

std::vector<Vector3<T> > m_verts;
std::vector<int> m_indices;

struct Edge
{
Edge() {}
Edge(unsigned int v0, unsigned int v1)
{
v[0] = v0;
v[1] = v1;
}

bool operator==(const Edge& e)
{
return (v[0] == e.v[0] && v[1] == e.v[1]) || (v[0] == e.v[1] && v[1] == e.v[0]);
}

unsigned int v[2];
};

struct Face
{
Face() {}

unsigned int v[3];
unsigned int e[3];
};
};
// --------------------------------------------------------------------------------------
template <class T> Mesh<T>::Mesh() {}
// --------------------------------------------------------------------------------------
template <class T> Mesh<T>::Mesh(unsigned int numVerts, unsigned int numIndices) :
m_verts(numVerts),
m_indices(numIndices) {}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeTetrahedron(T s)
{
T sqrt2 = Math<T>::SQRT_2;
T sqrt6 = Math<T>::SQRT_6;
T sqrt2Over3 = sqrt2 / (T)3.0;
T sqrt6Over3 = sqrt6 / (T)3.0;
T oneThird = (T)1.0 / (T)3.0;

m_verts.resize(4);
m_indices.resize(12);

m_verts[0].Set((T)0.0, (T)0.0, (T)1.0);
m_verts[1].Set((T)2.0 * sqrt2Over3, (T)0.0, -oneThird);
m_verts[2].Set(-sqrt2Over3, sqrt6Over3, -oneThird);
m_verts[3].Set(-sqrt2Over3, -sqrt6Over3, -oneThird);

m_indices[0] = 0;
m_indices[1] = 1;
m_indices[2] = 2;

m_indices[3] = 0;
m_indices[4] = 2;
m_indices[5] = 3;

m_indices[6] = 0;
m_indices[7] = 3;
m_indices[8] = 1;

m_indices[9] = 1;
m_indices[10] = 3;
m_indices[11] = 2;

for (int i = 0; i < m_verts.size(); ++i)
m_verts *= s;


}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeHexahedron(T s)
{
m_verts.resize(8);
m_indices.resize(36);

T t = (T)1.0 / Math<T>::SQRT_3;

T verts[] = {
-t, -t, -t,
t, -t, -t,
t, t, -t,
-t, t, -t,
-t, -t, t,
t, -t, t,
t, t, t,
-t, t, t};

unsigned int indices[] = {
0, 3, 2,
0, 4, 7,
6, 2, 3,
0, 2, 1,
0, 7, 3,
6, 3, 7,
0, 1, 5,
6, 5, 1,
6, 7, 4,
0, 5, 4,
6, 1, 2,
6, 4, 5};

for (int i = 0; i < 8; ++i)
m_verts.Set(verts[i * 3 + 0], verts[i * 3 + 1], verts[i * 3 + 2]);
for (int i = 0; i < 36; ++i)
m_indices = indices;
for (int i = 0; i < m_verts.size(); ++i)
m_verts *= s;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeOctahedron(T s)
{
m_verts.resize(6);
m_indices.resize(24);

m_verts[0].Set((T)1.0, (T)0.0, (T)0.0);
m_verts[1].Set((T)-1.0, (T)0.0, (T)0.0);
m_verts[2].Set((T)0.0, (T)1.0, (T)0.0);
m_verts[3].Set((T)0.0, (T)-1.0, (T)0.0);
m_verts[4].Set((T)0.0, (T)0.0, (T)1.0);
m_verts[5].Set((T)0.0, (T)0.0, (T)-1.0);

m_indices[0] = 4;
m_indices[1] = 0;
m_indices[2] = 2;

m_indices[3] = 4;
m_indices[4] = 2;
m_indices[5] = 1;

m_indices[6] = 4;
m_indices[7] = 1;
m_indices[8] = 3;

m_indices[9] = 4;
m_indices[10] = 3;
m_indices[11] = 0;

m_indices[12] = 5;
m_indices[13] = 2;
m_indices[14] = 0;

m_indices[15] = 5;
m_indices[16] = 1;
m_indices[17] = 2;

m_indices[18] = 5;
m_indices[19] = 3;
m_indices[20] = 1;

m_indices[21] = 5;
m_indices[22] = 0;
m_indices[23] = 3;

for (int i = 0; i < m_verts.size(); ++i)
m_verts *= s;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeDodecahedron(T s)
{
m_verts.resize(20);
m_indices.resize(108);

T a = (T)1.0 / Math<T>::Sqrt((T)3.0);
T b = Math<T>::Sqrt(((T)3.0 - Math<T>::Sqrt((T)5.0)) / (T)6.0);
T c = Math<T>::Sqrt(((T)3.0 + Math<T>::Sqrt((T)5.0)) / (T)6.0);

T verts[] = {
a, a, a,
a, a, -a,
a, -a, a,
a, -a, -a,
-a, a, a,
-a, a, -a,
-a, -a, a,
-a, -a, -a,
b, c, (T)0.0,
-b, c, (T)0.0,
b, -c, (T)0.0,
-b, -c, (T)0.0,
c, (T)0.0, b,
c, (T)0.0, -b,
-c, (T)0.0, b,
-c, (T)0.0, -b,
(T)0.0, b, c,
(T)0.0, -b, c,
(T)0.0, b, -c,
(T)0.0, -b, -c};

unsigned int indices[] = {
0, 8, 9,
0, 16, 17,
12, 2, 10,
9, 5, 15,
3, 19, 18,
7, 11, 6,
0, 9, 4,
0, 17, 2,
12, 10, 3,
9, 15, 14,
3, 18, 1,
7, 6, 14,
0, 4, 16,
0, 2, 12,
12, 3, 13,
9, 14, 4,
3, 1, 13,
7, 14, 15,
0, 12, 13,
8, 1, 18,
16, 4, 14,
6, 11, 10,
7, 15, 5,
7, 19, 3,
0, 13, 1,
8, 18, 5,
16, 14, 6,
6, 10, 2,
7, 5, 18,
7, 3, 10,
0, 1, 8,
8, 5, 9,
16, 6, 17,
6, 2, 17,
7, 18, 19,
7, 10, 11};

for (int i = 0; i < 20; ++i)
m_verts.Set(verts[i * 3 + 0], verts[i * 3 + 1], verts[i * 3 + 2]);
for (int i = 0; i < 108; ++i)
m_indices = indices;
for (int i = 0; i < m_verts.size(); ++i)
m_verts *= s;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeIcosahedron(T s)
{
m_verts.resize(12);
m_indices.resize(60);

T t = ((T)1.0 + Math<T>::SQRT_5 * (T)0.5
T scale = (T)1.0 / Math<T>::Sqrt((T)1.0 + t * t);

T verts[] = {
t, (T)1.0, (T)0.0,
-t, (T)1.0, (T)0.0,
t, (T)-1.0, (T)0.0,
-t, (T)-1.0, (T)0.0,
(T)1.0, (T)0.0, t,
(T)1.0, (T)0.0, -t,
(T)-1.0, (T)0.0, t,
(T)-1.0, (T)0.0, -t,
(T)0.0, t, (T)1.0,
(T)0.0, -t, (T)1.0,
(T)0.0, t, (T)-1.0,
(T)0.0, -t, (T)-1.0};

unsigned int indices[] = {
0, 8, 4,
1, 10, 7,
2, 9, 11,
7, 3, 1,
0, 5, 10,
3, 9, 6,
3, 11, 9,
8, 6, 4,
2, 4, 9,
3, 7, 11,
4, 2, 0,
9, 4, 6,
2, 11, 5,
0, 10, 8,
5, 0, 2,
10, 5, 7,
1, 6, 8,
1, 8, 10,
6, 1, 3,
11, 7, 5};

for (int i = 0; i < 12; ++i)
m_verts.Set(verts[i * 3 + 0], verts[i * 3 + 1], verts[i * 3 + 2]);
for (int i = 0; i < 60; ++i)
m_indices = indices;
for (int i = 0; i < m_verts.size(); ++i)
m_verts *= scale * s;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeCylinder(T r, T l, const Vector3<T>& axis, unsigned int lod)
{
unsigned int numSteps = 4 << lod;

m_verts.resize(numSteps * 2 + 2);

T hl = l * (T)0.5;
T a = (T)0.0;
T step = Math<T>::TWO_PI / (T)numSteps;
for (int i = 0; i < numSteps; ++i)
{
T x = Math<T>::Cos(a) * r;
T y = Math<T>::Sin(a) * r;
m_verts.Set(x, y, hl);
m_verts[i + numSteps].Set(x, y, -hl);

a += step;
}

m_verts[numSteps * 2 + 0].Set((T)0.0, (T)0.0, +hl);
m_verts[numSteps * 2 + 1].Set((T)0.0, (T)0.0, -hl);

// For the triangles, we'll need the following:

// 1. Two tris for every side = 2 * numSteps
// 2. For each cap, one tri for every step = 2 * numSteps

m_indices.resize(4 * numSteps * 3);

for (int i = 0; i < numSteps; ++i)
{
unsigned int i1 = i;
unsigned int i2 = (i1 + 1) % numSteps; // Use Next()?
unsigned int i3 = i1 + numSteps;
unsigned int i4 = i2 + numSteps;

// Sides

// i1, i3, i2
// i4, i2, i3

m_indices[i * 6 + 0] = i1;
m_indices[i * 6 + 1] = i3;
m_indices[i * 6 + 2] = i2;

m_indices[i * 6 + 3] = i4;
m_indices[i * 6 + 4] = i2;
m_indices[i * 6 + 5] = i3;

// Caps

// numSteps * 2 + 0, i1, i2
// numSteps * 2 + 1, i3, i4

m_indices[numSteps * 6 + i * 6 + 0] = numSteps * 2 + 0;
m_indices[numSteps * 6 + i * 6 + 1] = i1;
m_indices[numSteps * 6 + i * 6 + 2] = i2;

m_indices[numSteps * 6 + i * 6 + 3] = numSteps * 2 + 1;
m_indices[numSteps * 6 + i * 6 + 4] = i4;
m_indices[numSteps * 6 + i * 6 + 5] = i3;
}

// Now re-orient along input axis
Matrix3<T> m;
m.MakeOrthonormalBasis(axis);
for (int i = 0; i < m_verts.size(); ++i)
m_verts = m * m_verts;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeCylinder(T ro, T ri, T l, const Vector3<T>& axis, unsigned int lod)
{
unsigned int numSteps = 4 << lod;

m_verts.resize(numSteps * 4);

T hl = l * (T)0.5;
T a = (T)0.0;
T step = Math<T>::TWO_PI / (T)numSteps;
for (int i = 0; i < numSteps; ++i)
{
T c = Math<T>::Cos(a);
T s = Math<T>::Sin(a);
T xo = c * ro;
T yo = s * ro;
T xi = c * ri;
T yi = s * ri;
m_verts[numSteps * 0 + i].Set(xo, yo, +hl);
m_verts[numSteps * 1 + i].Set(xo, yo, -hl);
m_verts[numSteps * 2 + i].Set(xi, yi, +hl);
m_verts[numSteps * 3 + i].Set(xi, yi, -hl);

a += step;
}

// For the triangles, we'll need the following:

// 1. Two tris for every outer side side = 2 * numSteps
// 2. Two tris for every inner side side = 2 * numSteps
// 2. For each cap, two tris for every step = 4 * numSteps

m_indices.resize(8 * numSteps * 3);

unsigned int index = 0;
for (int i = 0; i < numSteps; ++i)
{
// Outer indices

unsigned int io1 = i;
unsigned int io2 = (io1 + 1) % numSteps; // Use Next()?
unsigned int io3 = io1 + numSteps;
unsigned int io4 = io2 + numSteps;

// Inner indices
unsigned int ii1 = io1 + numSteps * 2;
unsigned int ii2 = io2 + numSteps * 2;
unsigned int ii3 = io3 + numSteps * 2;
unsigned int ii4 = io4 + numSteps * 2;

// Outer sides

// i1, i3, i2
// i4, i2, i3

m_indices[index++] = io1;
m_indices[index++] = io3;
m_indices[index++] = io2;

m_indices[index++] = io4;
m_indices[index++] = io2;
m_indices[index++] = io3;

// Inner sides

// i3, i1, i4
// i2, i4, i1

m_indices[index++] = ii3;
m_indices[index++] = ii1;
m_indices[index++] = ii4;

m_indices[index++] = ii2;
m_indices[index++] = ii4;
m_indices[index++] = ii1;

// Positive end caps

// ii1, io1, ii2
// io2, ii2, io1

m_indices[index++] = ii1;
m_indices[index++] = io1;
m_indices[index++] = ii2;

m_indices[index++] = io2;
m_indices[index++] = ii2;
m_indices[index++] = io1;

// Negative end caps

// io3, ii3, io4
// ii4, io4, ii3

m_indices[index++] = io3;
m_indices[index++] = ii3;
m_indices[index++] = io4;

m_indices[index++] = ii4;
m_indices[index++] = io4;
m_indices[index++] = ii3;
}

// Now re-orient along input axis
Matrix3<T> m;
m.MakeOrthonormalBasis(axis);
for (int i = 0; i < m_verts.size(); ++i)
m_verts = m * m_verts;
}




Share this post


Link to post
Share on other sites
The rest:


// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeEllipsoid(const Vector3<T>& C, T rx, T ry, T rz, unsigned int lod)
{
MakeIcosahedron();
for (int i = 0; i < lod; ++i)
Subdivide();
for (int i = 0; i < m_verts.size(); ++i)
{
m_verts.NormalizeSelf();
m_verts.Set(m_verts[0] * rx, m_verts[1] * ry, m_verts[2] * rz);
m_verts += C;
}
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeSphere(const Vector3<T>& C, T r, unsigned int lod)
{
MakeEllipsoid(C, r, r, r, lod);
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeTorus(
T r1,
T r2,
const Vector3<T>& axis,
unsigned int lod1,
unsigned int lod2)
{
unsigned int numSteps1 = 4 << lod1;
unsigned int numSteps2 = 4 << lod2;

// We'll build the torus along the z axis, and then re-orient.

// First we need the number of vertices. Basically, for every step1, we have step2
// vertices.

m_verts.resize(numSteps1 * numSteps2);

// This will be different than other meshes in that we need some intermediate
// points, the inner ring.

std::vector<Vector3<T> > p(numSteps1);

// Find the points for the inner ring

T a = (T)0.0;
T step = Math<T>::TWO_PI / (T)numSteps1;
for (int i = 0; i < numSteps1; ++i)
{
T x = Math<T>::Cos(a) * r1;
T y = Math<T>::Sin(a) * r1;
p.Set(x, y, (T)0.0);
a += step;
}

// Now for the actual verts, we create a ring around each point in the inner ring

for (int i = 0; i < numSteps1; ++i)
{
// Basis vectors for this ring are the z axis and the normalized vector
// from the point to the origin

Vector3<T> u = Vector3<T>::Normalize(-p) * r2; // Could be p also
Vector3<T> v = Vector3<T>::Z_AXIS * r2;

// Create the verts
a = (T)0.0;
T step = Math<T>::TWO_PI / (T)numSteps2;
for (int j = 0; j < numSteps2; ++j)
{
T c = Math<T>::Cos(a);
T s = Math<T>::Sin(a);
m_verts[i * numSteps2 + j] = p + c * u + s * v;
a += step;
}
}

// Now comes the hard part - triangulating. Let's start by figuring out how
// many triangles we need. We have numSteps1 'slices', each with numSteps2
// quads, each with two tris, each with 3 indices. So:

m_indices.resize(numSteps1 * numSteps2 * 6);

// Triangulate

int index = 0;
for (int i = 0; i < numSteps1; ++i)
{
int i1 = i;
int i2 = (i1 + 1) % numSteps1;

for (int j = 0; j < numSteps2; ++j)
{
int j1 = j;
int j2 = (j1 + 1) % numSteps2;

m_indices[index++] = i1 * numSteps2 + j1;
m_indices[index++] = i1 * numSteps2 + j2;
m_indices[index++] = i2 * numSteps2 + j1;

m_indices[index++] = i2 * numSteps2 + j2;
m_indices[index++] = i2 * numSteps2 + j1;
m_indices[index++] = i1 * numSteps2 + j2;
}
}

// Now re-orient along input axis
Matrix3<T> m;
m.MakeOrthonormalBasis(axis);
for (int i = 0; i < m_verts.size(); ++i)
m_verts = m * m_verts;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeTorusKnot(
T r1,
T r2,
T r3,
int p,
int q,
const Vector3<T>& axis,
unsigned int lod1,
unsigned int lod2)
{
unsigned int numSteps1 = 4 << lod1;
unsigned int numSteps2 = 4 << lod2;

// We'll build the knot along the z axis, and then re-orient.

// First we need the number of vertices. Basically, for every step1, we have step2
// vertices.

m_verts.resize(numSteps1 * numSteps2);

// For the knot, we're going to evaluate the inner ring, and the knot medial structure.

std::vector<Vector3<T> > inner(numSteps1), outer(numSteps1);

// Find the points for the inner ring and knot medial structure

T u = (T)0.0;
T v = (T)0.0;
T stepU = (Math<T>::TWO_PI * p) / (T)numSteps1;
T stepV = (Math<T>::TWO_PI * q) / (T)numSteps1;
for (int i = 0; i < numSteps1; ++i)
{
T su = Math<T>::Sin(u);
T cu = Math<T>::Cos(u);
T sv = Math<T>::Sin(v);
T cv = Math<T>::Cos(v);

T x = cu * (r1 + cv * r2);
T y = su * (r1 + cv * r2);
T z = sv * r2;

assert(i < outer.size());
outer.Set(x, y, z);

x = cu * r1;
y = su * r1;

assert(i < inner.size());
inner.Set(x, y, (T)0.0);

u += stepU;
v += stepV;
}

// Now for the actual verts, we create a ring around each point on the medial structure

for (int i = 0; i < numSteps1; ++i)
{
// Basis vectors for this ring are:

// Side: normalized vector from inner ring point to outer medial structure point

Vector3<T> u = Vector3<T>::Normalize(outer - inner) * r3;

// For up, we need a forward vector to cross with. We'll use outer[i + 1] - outer,
// although there may be a way to do it with calculus.

int j = (i + 1) % outer.size();
Vector3<T> w = outer[j] - outer;

// Now we can find v

Vector3<T> v = w.UnitCross(u) * r3;

// Create the verts
T a = (T)0.0;
T step = Math<T>::TWO_PI / (T)numSteps2;
for (int j = 0; j < numSteps2; ++j)
{
T c = Math<T>::Cos(a);
T s = Math<T>::Sin(a);
assert(i * numSteps2 + j < m_verts.size());
m_verts[i * numSteps2 + j] = outer + c * u + s * v;
a += step;
}
}

m_indices.resize(numSteps1 * numSteps2 * 6);

// Triangulate

int index = 0;
for (int i = 0; i < numSteps1; ++i)
{
int i1 = i;
int i2 = (i1 + 1) % numSteps1;

for (int j = 0; j < numSteps2; ++j)
{
int j1 = j;
int j2 = (j1 + 1) % numSteps2;

assert(index < m_indices.size());
m_indices[index++] = i1 * numSteps2 + j1;
assert(index < m_indices.size());
m_indices[index++] = i1 * numSteps2 + j2;
assert(index < m_indices.size());
m_indices[index++] = i2 * numSteps2 + j1;

assert(index < m_indices.size());
m_indices[index++] = i2 * numSteps2 + j2;
assert(index < m_indices.size());
m_indices[index++] = i2 * numSteps2 + j1;
assert(index < m_indices.size());
m_indices[index++] = i1 * numSteps2 + j2;
}
}

// Now re-orient along input axis
Matrix3<T> m;
m.MakeOrthonormalBasis(axis);
for (int i = 0; i < m_verts.size(); ++i)
{
assert(i < m_verts.size());
m_verts = m * m_verts;
}
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeCapsule(T r, T l, const Vector3<T>& axis, unsigned int lod)
{
// We're going to do this a little bit differently. Basically, we're going to
// try and use the 'sphere' method, where we create faces of equal area and
// then subdivide.

// So first we need to create the source mesh. This has one vertex at each end,
// and two sets of four vertices for a total of 10.

m_verts.resize(10);

// The order will be the five at one end, and then the five at the other

T hl = l * (T)0.5;
m_verts[0].Set((T)1.0, (T)0.0, hl);
m_verts[1].Set((T)0.0, (T)1.0, hl);
m_verts[2].Set(-(T)1.0, (T)0.0, hl);
m_verts[3].Set((T)0.0, -(T)1.0, hl);
m_verts[4].Set((T)0.0, (T)0.0, hl + (T)1.0);
m_verts[5].Set((T)1.0, (T)0.0, -hl);
m_verts[6].Set((T)0.0, (T)1.0, -hl);
m_verts[7].Set(-(T)1.0, (T)0.0, -hl);
m_verts[8].Set((T)0.0, -(T)1.0, -hl);
m_verts[9].Set((T)0.0, (T)0.0, -hl - (T)1.0);

// When I re-write this, the order should be 4+, 4-, cap+, cap-.

// Well, our subivision idea won't work like we want as is because it will subdivide the
// triangles along the sides also. Eventually we'll need a way to flag certain
// triangles as 'don't subdivide'.

// Anyway, we 4 sides * 2 tris each, plus 2 ends * 4 tris each * 3 indices each.

m_indices.resize(48);

// Here we go.

unsigned int indices[] = {
0, 5, 1,
6, 1, 5,
1, 6, 2,
7, 2, 6,
2, 7, 3,
8, 3, 7,
3, 8, 0,
5, 0, 8,
0, 1, 4,
1, 2, 4,
2, 3, 4,
3, 0, 4,
5, 9, 6,
6, 9, 7,
7, 9, 8,
8, 9, 5};

for (int i = 0; i < 48; ++i)
m_indices = indices;

// Subdivide

for (int i = 0; i < lod; ++i)
Subdivide();

// Now we want to re-normalize the verts with respect to the endpoints. For now
// I'm going to hack it and just determine the endpoint by the z value of the vert.

// (Note: use 'closest point on segment' here instead)

Vector3<T> p1((T)0.0, (T)0.0, +hl);
Vector3<T> p2((T)0.0, (T)0.0, -hl);

for (int i = 0; i < m_verts.size(); ++i)
{
if (m_verts[2] > hl - Math<T>::EPSILON)
m_verts = p1 + Vector3<T>::Normalize(m_verts - p1) * r;
else if (m_verts[2] < -hl + Math<T>::EPSILON)
m_verts = p2 + Vector3<T>::Normalize(m_verts - p2) * r;
else
{
T x = m_verts[0];
T y = m_verts[1];
T z = m_verts[2];
T invl = Math<T>::InvSqrt(x * x + y * y);
x *= invl * r;
y *= invl * r;
m_verts.Set(x, y, z);
}
}

// And that is absolutely perfect, except for the unnecessary subdivision along
// the length. But that will have to wait until later.

// TODO: Or at least try. What if I didn't create the side triangles initially,
// and went ahead and subdivided without them. Would I have enough information about
// the order of the verts to add the side triangles after subdividing? Probably not.

// Now re-orient along input axis
Matrix3<T> m;
m.MakeOrthonormalBasis(axis);
for (int i = 0; i < m_verts.size(); ++i)
m_verts = m * m_verts;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeCone(T r, T l, const Vector3<T>& axis, unsigned int lod)
{
unsigned int numSteps = 4 << lod;

// The number of vertices is numSteps + 1 for the bottom center and 1 for the tip.

m_verts.resize(numSteps + 2);

// Now we create them.

T hl = l * (T)0.5;
T a = (T)0.0;
T step = Math<T>::TWO_PI / (T)numSteps;
for (int i = 0; i < numSteps; ++i)
{
T x = Math<T>::Cos(a) * r;
T y = Math<T>::Sin(a) * r;
m_verts.Set(x, y, -hl);

a += step;
}

m_verts[numSteps + 0].Set((T)0.0, (T)0.0, -hl);
m_verts[numSteps + 1].Set((T)0.0, (T)0.0, +hl);

// For the triangles, we'll need the following:

// One tri for each step, for both the side and the bottom.

m_indices.resize(2 * numSteps * 3);

// Note that the bottom may be optional at some point

for (int i = 0; i < numSteps; ++i)
{
unsigned int i1 = i;
unsigned int i2 = (i1 + 1) % numSteps; // Use Next()?

// Side

m_indices[i * 3 + 0] = i1;
m_indices[i * 3 + 1] = i2;
m_indices[i * 3 + 2] = numSteps + 1;

// Bottom

m_indices[numSteps * 3 + i * 3 + 0] = i2;
m_indices[numSteps * 3 + i * 3 + 1] = i1;
m_indices[numSteps * 3 + i * 3 + 2] = numSteps;
}

// Now re-orient along input axis
Matrix3<T> m;
m.MakeOrthonormalBasis(axis);
for (int i = 0; i < m_verts.size(); ++i)
m_verts = m * m_verts;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::MakeBox(const Vector3<T>& e)
{
// 8 verts, 1 for each corner

m_verts.resize(8);

// Now we create them. We'll go counterclockwise, starting in the positive
// octant around the xy plane, then around the xy plane with -z.

m_verts[0].Set( e[0], e[1], e[2]);
m_verts[1].Set(-e[0], e[1], e[2]);
m_verts[2].Set(-e[0], -e[1], e[2]);
m_verts[3].Set( e[0], -e[1], e[2]);
m_verts[4].Set( e[0], e[1], -e[2]);
m_verts[5].Set(-e[0], e[1], -e[2]);
m_verts[6].Set(-e[0], -e[1], -e[2]);
m_verts[7].Set( e[0], -e[1], -e[2]);

// For the triangles, we'll need the following:

// 6 faces, two tris per face.

m_indices.resize(36);

// Now we have to figure out a reasonable way to determine the order.
// If you look at any face, you're either looking down a positive axis
// or a negative axis.

// Let's start with the +x face. The indices, starting in the + quadrant
// and going CCW, are 0, 3, 7, 4.

// For +y, we have 0, 4, 5, 1.

// For +z, we have 0, 1, 2, 3.

// For -x, 1, 5, 6, 2.

// For -y, 3, 2, 6, 7.

// For -z, 4, 7, 6, 5.

// TODO: Double-check. Also, it might make more sense for the -z verts
// to be CCW when viewed from the back, not the front. I think this would
// just mean that 5 and 7 would switch wherever they appear.

m_indices[0] = 0;
m_indices[1] = 3;
m_indices[2] = 7;
m_indices[3] = 7;
m_indices[4] = 4;
m_indices[5] = 0;

m_indices[6] = 0;
m_indices[7] = 4;
m_indices[8] = 5;
m_indices[9] = 5;
m_indices[10] = 1;
m_indices[11] = 0;

m_indices[12] = 0;
m_indices[13] = 1;
m_indices[14] = 2;
m_indices[15] = 2;
m_indices[16] = 3;
m_indices[17] = 0;

m_indices[18] = 1;
m_indices[19] = 5;
m_indices[20] = 6;
m_indices[21] = 6;
m_indices[22] = 2;
m_indices[23] = 1;

m_indices[24] = 3;
m_indices[25] = 2;
m_indices[26] = 6;
m_indices[27] = 6;
m_indices[28] = 7;
m_indices[29] = 3;

m_indices[30] = 4;
m_indices[31] = 7;
m_indices[32] = 6;
m_indices[33] = 6;
m_indices[34] = 5;
m_indices[35] = 4;
}
// --------------------------------------------------------------------------------------
template <class T> void Mesh<T>::Subdivide()
{
// First we need to find all unique edge

std::vector<Edge> edges;
for (int i = 0; i < m_indices.size(); ++i)
{
// Create a new edge
Edge e(m_indices, m_indices[(i - (i % 3)) + ((i + 1) % 3)]);

// Add if not already in array
if (std::find(edges.begin(), edges.end(), e) == edges.end())
edges.push_back(e);
}

// Create face list

std::vector<Face> faces(m_indices.size() / 3);
for (int i = 0; i < faces.size(); ++i)
{
faces.v[0] = m_indices[(i * 3) + 0];
faces.v[1] = m_indices[(i * 3) + 1];
faces.v[2] = m_indices[(i * 3) + 2];
}

// Match edges to faces

// For each face
for (int i = 0; i < faces.size(); ++i)
{
// For each edge of the face
for (int j = 0; j < 3; ++j)
{
// Edge indices
unsigned int v0 = faces.v[j];
unsigned int v1 = faces.v[(j + 1) % 3];

// Create edge
Edge e(v0, v1);

// Find and set edge index
faces.e[j] = std::find(edges.begin(), edges.end(), e) - edges.begin();

// Sanity check
assert(faces.e[j] >= 0 && faces.e[j] < edges.size());
}
}

// We need to resize the vertex array. The size is the number of verts currently
// plus one new one for each edge.

unsigned int numVerts = m_verts.size();
m_verts.resize(numVerts + edges.size());

// Add a new vert at the midpoint of each edge
for (int i = 0; i < edges.size(); ++i)
{
Vector3<T> v0 = m_verts[edges.v[0]];
Vector3<T> v1 = m_verts[edges.v[1]];
Vector3<T> v = (v0 + v1) * (T)0.5; // Math<T>::Average()?

m_verts[numVerts + i] = v;
}

// Resize index array. The new number of triangles is four times the old.

m_indices.resize(m_indices.size() * 4);

// Create new faces

int index = 0;
for (int i = 0; i < faces.size(); ++i)
{
unsigned int v0 = faces.v[0];
unsigned int v1 = faces.v[1];
unsigned int v2 = faces.v[2];
unsigned int v3 = faces.e[0] + numVerts;
unsigned int v4 = faces.e[1] + numVerts;
unsigned int v5 = faces.e[2] + numVerts;

m_indices[index++] = v0;
m_indices[index++] = v3;
m_indices[index++] = v5;

m_indices[index++] = v1;
m_indices[index++] = v4;
m_indices[index++] = v3;

m_indices[index++] = v2;
m_indices[index++] = v5;
m_indices[index++] = v4;

m_indices[index++] = v3;
m_indices[index++] = v4;
m_indices[index++] = v5;
}
}
// --------------------------------------------------------------------------------------
// For now we're only going to allow drawing of Mesh<float>s, so that we can send the
// vertex array directly to OpenGL.
void Mesh<float>::Draw(float r, float g, float b) const
{
// Set up OpenGL
glCullFace(GL_BACK);
glPolygonMode(GL_FRONT, GL_LINE);
glEnableClientState(GL_VERTEX_ARRAY);
glDisableClientState(GL_TEXTURE_COORD_ARRAY);
glDisableClientState(GL_COLOR_ARRAY);

// Draw
glColor3f(r, g, b);
glVertexPointer(3, GL_FLOAT, 0, (float*)&m_verts[0]);
glDrawElements(GL_TRIANGLES, m_indices.size(), GL_UNSIGNED_INT, &m_indices[0]);

// glColor3f(1.0f, 1.0f, 1.0f);
// glBegin(GL_POINTS);
// for (int i = 0; i < m_verts.size(); ++i)
// glVertex3f((float)m_verts[0], (float)m_verts[1], (float)m_verts[2]);
// glEnd();

// Restore
glCullFace(GL_FRONT);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);
glEnableClientState(GL_COLOR_ARRAY);
}
// --------------------------------------------------------------------------------------

} // namespace geom
} // namespace jyk

#endif

Share this post


Link to post
Share on other sites
jyk: Thanks ALOT! I'll have a look at it later on (don't have time right now).
Mercury & kwijibo: I'm visiting that page all the time, but thanks anyway ;)

Now when it comes to normals and texture coordinates I've decided that I'll add them as a "post processing" step to all the primitives that don't have a trivial solution to how they're generated.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!