# N-Dimensional Tessellation

4 replies to this topic

### #1flux00

Valued Member

• Members
• 108 posts

Posted 12 March 2007 - 10:00 PM

Hello, I'm trying to tessellate a cartesian (or possibly non-cartesian) function of arbitrary dimension. Obviously for this I wouldn't be using triangles, except for a three-dimensional function. I think in order to tessellate an n-dimensional function "triangles" with n-points are required. I think that's the minimum number of points to define a hyperplane. The surface normal would just be cross(p1-p0, p2-p0, ... , pN-p0). I'm having trouble with the actual tessellation. I've defined a recursive function which adds "triangles" to a LinkedList, then calls itself 2^(n-1)-1 times. I pass an initial point P, and then generate a n-1-dimensional cube using a small increment, then I split it into n-dimensional hyperplanes. In 3 dimensions, this would be generating a square, then splitting it in two to make two triangles. In 4 dimensions, I would be splitting a 3-cube into tetrahedrons. This doesn't work without leaving a gap in the middle though, so I don't know if some of my assumptions were incorrect.

### #2Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 12 March 2007 - 11:16 PM

Woah
I'd guess you've gone far beyond the knowledge of anyone on this board, certainly beyond my knowledge of n-dimensional geometry. You might want to consider contacting a math professor at a nearby college and maybe signing up for some advanced math classes...they might teach you what you want to know. It's certainly a fascinating area.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3anubis

Senior Member

• Members
• 2225 posts

Posted 13 March 2007 - 09:16 AM

Sounds interesting allthough I can't be of any help either. What is the final purpose of what you are doing ?
If Prolog is the answer, what is the question ?

### #4flux00

Valued Member

• Members
• 108 posts

Posted 13 March 2007 - 10:03 PM

I'm thinking of different ways to visualize higher-dimensional functions. You can just interpret a 3-dimensional ray as an n-dimensional ray with all components with indices > 2 = 0. That gives you a three-dimensional slice. By tessellating a function I can collapse it by a dimension, and then render.

### #5flux00

Valued Member

• Members
• 108 posts

Posted 18 March 2007 - 05:42 PM

Before attempting ND I'm trying to at least tessellate a 3D function. I have a Function class which takes a float[] as an argument and returns a Point. In this case I'm trying Z = f(X,Y) = sin(0.1*X) + sin(0.1*Y). The Interval class defines how many samples to take, and across what interval. In this case X and Y both range from -100 to 100 with 10 samples in between. The increment ("inc") is (max-min)/samples. First I generate a 2-dimensional array of points for the mesh, then break up each square into two triangles. For some reason though, the mesh is discontinuous, and the order of the points passed to the triangle changes it's position. I used a ray-triangle intersection algorithm outlined in "Mathematics for 3D Game Programming and Computer Graphics." I don't understand why the order of the points used to create the triangle matters, especially because I check the ray origin with the plane to see which side it's on. The boolean passed to the HitPoint class indicates whether or not the Normal needs to be negated.

Here's the image I get when rendering with those parameters: http://img.photobuck...or/render19.png

public TMesh(Function f, Interval v)

{

super(f.N());

if (f.N() != 3 || v.arguments() != f.arguments())

{

throw new IllegalArgumentException();

}

mat = Material.DEFAULT_MATERIAL;

Point[][] pts = new Point[v.samples(0)+1][v.samples(1)+1];

for (int x=0; x<pts.length; ++x)

{

for (int y=0; y<pts[x].length; ++y)

{

float xa = v.min(0) + x*v.inc(0);

float ya = v.min(1) + y*v.inc(1);

pts[x][y] = f.evaluate(new float[]{xa, ya});

}

}

Triangle[] t = new Triangle[v.samples(0)*v.samples(1)*2];

for (int x=0, i=0; x<pts.length-1; ++x)

{

for (int y=0; y<pts[x].length-1; ++y)

{

Point p0 = pts[x][y];

Point p1 = pts[x][y+1];

Point p2 = pts[x+1][y];

Point p3 = pts[x+1][y+1];

t[i] = new Triangle(p2, p1, p0, mat);

t[i+1] = new Triangle(p2, p1, p3, mat);

i += 2;

}

}

set(t);

}



private Vector[] pts;

private Normal n;

private float dis;

public Triangle(Point p0, Point p1, Point p2, Material m)

{

super(3);

pts = new Vector[]{new Vector(p0), new Vector(p1), new Vector(p2)};

setMaterial(m);

Vector b = Vector.subtract(pts[1], pts[0]);

Vector c = Vector.subtract(pts[2], pts[0]);

n = new Normal(Vector.cross(b, c));

n.normalize();

dis = n.dot(pts[0]);

}

protected HitPoint getClosest(Ray ray)

{

float num=dis, den=0F;

for (int i=0; i<N; ++i)

{

num -= n.X[i]*ray.origin.X[i];

den += n.X[i]*ray.direction.X[i];

}

float t = num/den;

if (ray.isValid(t))

{

Vector p = new Vector(ray.at(t));

Vector r = Vector.subtract(p, pts[0]);

Vector q1 = Vector.subtract(pts[1], pts[0]);

Vector q2 = Vector.subtract(pts[2], pts[0]);

float q1l2 = q1.length2();

float q2l2 = q2.length2();

float dot = q1.dot(q2);

float div = q1l2*q2l2 - dot*dot;

if (AMath.abs(div) < 1E-10F)

{

return null;

}

float inv = 1F/div;

float rq1 = r.dot(q1);

float rq2 = r.dot(q2);

float w1 = inv*(q2l2*rq1 - dot*rq2);

if (w1 < 0F || w1 > 1F)

{

return null;

}

float w2 = inv*(q1l2*rq2 - dot*rq1);

if (w2 < 0F || w1 + w2 > 1F)

{

return null;

}

if (n.dot(new Vector(ray.origin)) > dis)

{

return new HitPoint(t, false, this);

}

return new HitPoint(t, true, this);

}

return null;

}



#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users