new to 3d programming, need help...
category: general [glöplog]
so.. I'm writing an application and one of it's integral parts is to create a 3d model out of a series of 2 bit images (each image represents a "slice" of the 3d model on the Z plane). I can map vertices correctly and fine, but the problem is writing a function to connect them in the correct order, making sure there's no overlapping tri's, etc.. are there any standard, well known functions which do that kind of thing?
marching cubes springs to mind.
thanks, that helped out a lot ^^
That as little do do with programming. Don't you mean 1 bit images? Or it's in or it's out :|
You can find some algorithm to find the edges and connect the dots...
You can find some algorithm to find the edges and connect the dots...
Still clueless: http://www.dbfinteractive.com/
with marching cubes you can fake strength on voxels from images.
You can also google for NeHe
NeHe won't help him think...
Oops.. sorry, I wasn't paying attention. What do you think about using Quadtrees to speed it up?
that won't make triangulation any easier.
perhaps looking into "constructing geometry from pointclouds" could be interesting to investigate ?
the topology of point clouds is a hot topic in the field of applied topology these days. I'm not sure how much of the theory has been condensed down to easy-to-implement algorithms yet. (maybe i should google before I post this, as it is not my thing really) Some people in my department are doing pioneer work on the subject.
but I am sure it would be interesting to investigate, though.
What about the first answer you got? If you manage to convert your bitmap slices into some vector representation, then a marching cubes approach will give you something 3dimensional with more or less the same slices as you started with. Choosing the dimensions of your cubes is, of course, where your magic must be applied.
If you could do marching cubes with non-fixed dimensions on your marching cubes, then you could get some really good looking 3dmeshes.
Maybe this depends on how your input bitmaps look like. You might have to do more "jumping" than "marching".
but I am sure it would be interesting to investigate, though.
What about the first answer you got? If you manage to convert your bitmap slices into some vector representation, then a marching cubes approach will give you something 3dimensional with more or less the same slices as you started with. Choosing the dimensions of your cubes is, of course, where your magic must be applied.
If you could do marching cubes with non-fixed dimensions on your marching cubes, then you could get some really good looking 3dmeshes.
Maybe this depends on how your input bitmaps look like. You might have to do more "jumping" than "marching".
you sure picked an interesting area to begin with for a guy new to 3d programming :)
Coders go away!
Wouldn't it be easier and more reliable to connect vertices within each slice into one or more edges, then connect the edges of neighbouring slices?
Doom: but _how_ ? That's the issue, right?
for each slice find any concave polygon that covers all the dots on that slice. (you may be looking for the convex hull actually, i don't know.)
for each slice you'll obtain a circular list of vertices each specifiying a mesh level. make sure they orient the same, ie. if you span from the first vertex to the last, and to again to first, you span a right handed path (or left handed). for this check the alignment of the polygon and reverse vertices if neccessary.
now we'll connect neighbor levels with triangles. to connect to consecutive parallel polygons, start with any vertex of the first one (eg. first vertex) (a) and the nearest vertex in the second polygon to our chosen vertex (b). these will be the two vertices of our first triangle. now check next vertex to both a and b. namely a' and b'. if a-a' is shorter than b-b' than choose a' as the third and last vertex, else choose b'.
form your triangle. set a to a' if you have chosen it, else set b = b'. repeat the previous paragraph until you span all the vertices in both polygons (they'll end simultaneously if everything went alright).
form other triangles in other levels with the same approach.
the image below barely shows how to choose vertices. it may not work with all the polygons you may form (intersecting faces), but it was fine with convex hulls.
for each slice you'll obtain a circular list of vertices each specifiying a mesh level. make sure they orient the same, ie. if you span from the first vertex to the last, and to again to first, you span a right handed path (or left handed). for this check the alignment of the polygon and reverse vertices if neccessary.
now we'll connect neighbor levels with triangles. to connect to consecutive parallel polygons, start with any vertex of the first one (eg. first vertex) (a) and the nearest vertex in the second polygon to our chosen vertex (b). these will be the two vertices of our first triangle. now check next vertex to both a and b. namely a' and b'. if a-a' is shorter than b-b' than choose a' as the third and last vertex, else choose b'.
form your triangle. set a to a' if you have chosen it, else set b = b'. repeat the previous paragraph until you span all the vertices in both polygons (they'll end simultaneously if everything went alright).
form other triangles in other levels with the same approach.
the image below barely shows how to choose vertices. it may not work with all the polygons you may form (intersecting faces), but it was fine with convex hulls.
Hyde: Like anesthetic said. :)
My idea: find one vertex on each edge so you get the two closest together. Start from there, then travel in the same direction along the path of both edges, and connect either one vertex in slice A to two vertices in slice B, or vice versa, then step along the edge on which you used two vertices.
There are only two possible triangles to form at any given time, and I'd select the one with the largest area to circumference ratio. Eventually you'll have stepped through all of slice A with one or more unused edges in slice B, or vice versa, and you just finish up the last edges.
It may or may not be equivalent to anesthetic's description. :)
My idea: find one vertex on each edge so you get the two closest together. Start from there, then travel in the same direction along the path of both edges, and connect either one vertex in slice A to two vertices in slice B, or vice versa, then step along the edge on which you used two vertices.
There are only two possible triangles to form at any given time, and I'd select the one with the largest area to circumference ratio. Eventually you'll have stepped through all of slice A with one or more unused edges in slice B, or vice versa, and you just finish up the last edges.
It may or may not be equivalent to anesthetic's description. :)
Also, relaxing and smoothing the mesh afterwards might be a good idea.
anesthetic, doom: according to that algorithm, all you will ever get out is a ball (up to some deformation of course). Try to take a torus and slice it up. After glueing it together again from the slices, you will have a potato!
It seems like a too naive approach, with too many instabilities. Some marching cubes will be more stable, and be able to capture inconvexities.
Doom: relaxing the surfaces is a good idea, btw.
It seems like a too naive approach, with too many instabilities. Some marching cubes will be more stable, and be able to capture inconvexities.
Doom: relaxing the surfaces is a good idea, btw.
Using marching cubes is easier and safer.
if you don't need a mesh but just showing those slices on the screen, try out a tridimensional texture...
Check here:
http://local.wasp.uwa.edu.au/~pbourke/modelling_rendering/glvol/
http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/
http://local.wasp.uwa.edu.au/~pbourke/modelling_rendering/glvol/
http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/
Hyde: Slices through a torus would have two edges, and you'd simply connect edges that are most similar from slice to slice.
xernobyl: Marching cubes are easier if you have something like a D3D_MarchingCubesPlease() function. Idunno D3D that much. To actually implement marching cubes though is a lot harder than just connecting some dots.
Anyway for marching cubes you need to know if an arbitrary point is inside or outside the shape, and unless you want a really jagged and blocky surface, it has to be in the form of a function that reflects distance to the surface (also taking the space between the slices into account). Of course without knowing what the source data is it's hard to say which is best, anyway.
Another approach could be to create a mesh out of tiny boxes, with one pixel in each layer representing a box, such that adjacent boxes are joined, then relax it a lot to make it smooth and then I think D3D has a function to reduce the number of surfaces.
xernobyl: Marching cubes are easier if you have something like a D3D_MarchingCubesPlease() function. Idunno D3D that much. To actually implement marching cubes though is a lot harder than just connecting some dots.
Anyway for marching cubes you need to know if an arbitrary point is inside or outside the shape, and unless you want a really jagged and blocky surface, it has to be in the form of a function that reflects distance to the surface (also taking the space between the slices into account). Of course without knowing what the source data is it's hard to say which is best, anyway.
Another approach could be to create a mesh out of tiny boxes, with one pixel in each layer representing a box, such that adjacent boxes are joined, then relax it a lot to make it smooth and then I think D3D has a function to reduce the number of surfaces.
xernobyl: yeah, I meant 1 bit, on/off.
vamecum : heh, thanks :) well I didn't wanna start with something too simple, like just a cube or something, I know I can do it already without writing it... but this is actually a lot harder than I imagined, lol.
Well, after looking at marching cubes and similar voxelish algorithms, I don't really think it fits with what I want... what I was hoping for was more of a vector driven 3D model of the object that the pixels imply, rather than gloopy looking voxels where you can see it's been fashioned out of cubes.
This is what I had done before I posted here.. the way I'm mapping the vertices is like this :
[img=http://www.youknowiknow.co.uk/pimg/test2.jpg]
So there are maximum possible 4 vertices for each pixel, one for each corner.
a pic of the mesh (no faces or tris) created from the image set :
[img=http://www.youknowiknow.co.uk/pimg/test1.jpg]
(you can see there are some odd vertices flying about, I could ignore them but ideally I want to connect them on their own as a separate part of the object, which means the algorithm has to account for that)
I'm not used to thinking in 3d.. it's a lot more tough once you add the Z dimension... I had a simple method for generating tris which looped through each pixel, and if the corner of the pixel was an 'on', it would crawl along the edges of the pixels next to in two directions until it came to two other vertices, then connect them.. that didn't work though, because I forgot to allow for the Z dimension.. but now, I don't really know where to go from there.
I read up on pointclouds but I couldn't find any specific methods, and it was a bit redundant for this type of thing, the vertices can be connected more accurately because I've got the source images that they're generated from.
Oh, and another thing, I'm using BlitzBasic to program this... :\ it's DX8 i think, and you can't call any D3D functions directly. I'm a noob :( I was gonna go on to C++ but I'm not that fluent so I needed something where I could keep track of what I was doing...
vamecum : heh, thanks :) well I didn't wanna start with something too simple, like just a cube or something, I know I can do it already without writing it... but this is actually a lot harder than I imagined, lol.
Well, after looking at marching cubes and similar voxelish algorithms, I don't really think it fits with what I want... what I was hoping for was more of a vector driven 3D model of the object that the pixels imply, rather than gloopy looking voxels where you can see it's been fashioned out of cubes.
This is what I had done before I posted here.. the way I'm mapping the vertices is like this :
[img=http://www.youknowiknow.co.uk/pimg/test2.jpg]
So there are maximum possible 4 vertices for each pixel, one for each corner.
a pic of the mesh (no faces or tris) created from the image set :
[img=http://www.youknowiknow.co.uk/pimg/test1.jpg]
(you can see there are some odd vertices flying about, I could ignore them but ideally I want to connect them on their own as a separate part of the object, which means the algorithm has to account for that)
I'm not used to thinking in 3d.. it's a lot more tough once you add the Z dimension... I had a simple method for generating tris which looped through each pixel, and if the corner of the pixel was an 'on', it would crawl along the edges of the pixels next to in two directions until it came to two other vertices, then connect them.. that didn't work though, because I forgot to allow for the Z dimension.. but now, I don't really know where to go from there.
I read up on pointclouds but I couldn't find any specific methods, and it was a bit redundant for this type of thing, the vertices can be connected more accurately because I've got the source images that they're generated from.
Oh, and another thing, I'm using BlitzBasic to program this... :\ it's DX8 i think, and you can't call any D3D functions directly. I'm a noob :( I was gonna go on to C++ but I'm not that fluent so I needed something where I could keep track of what I was doing...