if (x + y + z < 1) // Interpolate points (0, 0, 0), (1, 0, 0), (0, 1, 0) and (0, 0, 1) else if (other equations)But I doubt that would compare performance wise with trilinear. Any ideas? Oh, one last thing, I did have the idea of replacing my cubic grid with a tetrahedral one, but I don't know if it's practical or worth it.

**0**

# Tetrahedral interpolation

Started by RAZORUNREAL, Nov 26 2007 08:07 PM

6 replies to this topic

###
#1
Members - Reputation: **567**

Posted 26 November 2007 - 08:07 PM

I'm working on a voxel renderer (have a look if you want) and an important part of the algorithm is 3d interpolation. As in, without the interpolation it doesn't work properly. I'm not too worried about the quality, it just has to be there. At the moment I'm using trusty old trilinear interpolation, but I've been looking at alternatives. The most interesting alternative I've found so far is tetrahedral interpolation, which would let me halve the number of lookups, thereby greatly improving performance (I hope). Unfortunately, the only descriptions I've found of it are either in legalese or cost money.
I've found out enough that I think I could work out how to interpolate between the 4 points of the tetrahedron. I have no idea if it can be done fast, but that's a question for another day. What I want to ask about is how you divide a cube into tetrahedrons and, having done that, how you quickly determine which tetrahedron a point is in. I came up with a way of dividing a cube into 5 tetrahedrons (at least, I think I did), but in my search I came across a way of dividing one into 6, which all share a common edge (a diagonal through the centre). I'm still trying to get my head around how both are possible, and which would be simpler.
To determine which tetrahedron a point is in, all I've come up with is checking against the plane equations. For example:

___________________________________________________David OlsenIf I've helped you, please vote for PigeonGrape!

Sponsor:

###
#3
Members - Reputation: **567**

Posted 27 November 2007 - 10:06 AM

Yes, that link was quite useful but it just breezes over how you determine which tetrahedron a point is in. Unless I missed something?

Thanks.

Thanks.

___________________________________________________David OlsenIf I've helped you, please vote for PigeonGrape!

###
#4
Senior Moderators - Reputation: **1781**

Posted 27 November 2007 - 10:13 AM

Localizing in a tetrahedral zoo is annoying, to say the least. If the tetrahedralization is a Delaunay tetrahedralization, there's a simple way to do it: Simply choose an arbitrary starting tetrahedron, and walk from one tetrahedron to the next along whichever face has a normal taking you in the best direction. For the special case of the Delaunay tetrahedralization, this is guaranteed to work. For more complex cases, there's plenty of other solutions, but possibly the simplest efficient one would be a bounding volume hierarchy of the tetrahedra. For your case, though, it sounds like all the tetrahedra are just pieces of a cube in a cubic grid. In that case, yeah, just check against the plane equations. BTW, any slicing of a cube into tetrahedra must slice into 6 tetrahedra. If you think you found one with only 5 tetrahedra, you're missing one.

###
#5
Members - Reputation: **567**

Posted 27 November 2007 - 11:47 AM

Quote:

Original post by Sneftel

BTW, any slicing of a cube into tetrahedra must slice into 6 tetrahedra. If you think you found one with only 5 tetrahedra, you're missing one.

Are you sure? My brother just tried it out in unrealed. There's 1 tetrahedron in the middle, and 4 more surrounding it, each sharing a face with the middle one. It gives the right number of faces in theory, and looked ok in 3d. The middle tetrahedron has different proportions to the others of course.

And thanks, I hadn't heard of Delaunay tetrahedralization before.

___________________________________________________David OlsenIf I've helped you, please vote for PigeonGrape!

###
#6
Senior Moderators - Reputation: **1781**

Posted 27 November 2007 - 12:02 PM

Huh! I'll be damned, you seem to be right. If one allows the tetrahedra to have different volumes, you can do it with five tetrahedra. I wouldn't suggest this, because the middle tetrahedron will have different properties than the others, ones which would be more difficult to calculate.

BTW, the standard tool for cubic voxel rendering is marching cubes. Have you looked into that algorithm?

BTW, the standard tool for cubic voxel rendering is marching cubes. Have you looked into that algorithm?

###
#7
Members - Reputation: **567**

Posted 27 November 2007 - 02:19 PM

Quote:

Original post by SneftelI wouldn't suggest this, because the middle tetrahedron will have different properties than the others, ones which would be more difficult to calculate.

That's true, and I doubt there's much advantage to having less tetrahedra anyway.

Quote:

Original post by SneftelBTW, the standard tool for cubic voxel rendering is marching cubes. Have you looked into that algorithm?

Can't say I've looked at it in detail, but the whole point was to come up with a new way of doing it. My algorithm looks quite promising so far, it runs at about 5 fps on my 2.8ghz pentium D, and about 25 fps on my friends new quad core, entirely software rendered at 512 by 512 resolution. Which isn't great, except that the size of the dataset barely makes any difference. Assuming you have the memory (my algorithm is especially bad in that respect), you can render massive amounts of data at interactive framerates, where marching cubes quickly produces unreasonable amounts of triangles. And I'm cheating, I'm actually storing more about the surface than just a boolean solid/not solid, which makes it smoother and more accurate. Seems to me it's worth more investigation at least, especially since it should be possible to implement on sm3 hardware.

EDIT: Just in case someone should stumble over this, I did figure it out. I used the 6 tetrahedron way, and boiled the checks against plane equations down to this:

pos = fractional position;

// Find which tetrahedron we're in (numbered 1 to 6).

int tetrahedron = (pos.x < pos.z) * 4 + (pos.z < pos.y) * 2 + (pos.y < pos.x);

switch (tetrahedron)

{

case 0: // x, y and z are equal, so the point is on the diagonal shared by all 6 tetrahedra.

case 1-6: // Position is in tetrahedron 1 through 6, lerp appropriate verts.

case 7: // Hopefully not possible.

}

Then to do the linear interpolation, you multiply the value at vertex a by the volume of a tetrahedron whose vertices are the position of interest and vertices b, c and d. Similarly for the other vertices, then add them up and divide by the total volume of the tetrahedron (a, b, c, d). It's all special cases so it simplifies very nicely. For example (tetrahedron 1 according to my method):

float result = a * (1 - pos.x) + b * (pos.x - pos.z) + c * (pos.z - pos.y) + d * pos.y;

Where a, b, c and d are the values at the vertices [0, 0, 0], [1, 0, 0], [1, 0, 1] and [1, 1, 1] respectively.

[Edited by - RAZORUNREAL on December 1, 2007 3:19:55 AM]