Hey all, I posted once earlier about a research project that I was working on. I was told to make it clear that it isn't form homework. The project is to interface with a piece of machinery at my school, but I need some help. At this point my program has generated a huge list (on the order of millions) of triangles, each defined by a set of three vertices. In order for the machine to be able to process the file, none of the polygons can intersect, and there can't be any innerfaces or anything like that. Basically I need to take my set of triangles and calculate the shell for it. One case to take into account, assume we have a box comprised of 8 vertices, one for each corner, that would make 12 polys (i have to use triangles). Now suppose that there is also a cylinder drawn so that both ends are outside of the box, but the cylinder stabs through the center of the box at some arbitrary angle. I need to refacet the new merged shape as one, as if we dipped it in chocolate and only the hardened shell was visible. I can not have the faces of the cylinder inside the box, they must stop at the polygons defining the box. Likewise the ploygons defining the box can not be 'inside' of the cylinder, the face of the box must be refaceted so that only what is visible is recorded. I guess this is kind of a crude example but I'm hoping that it will help you visualize. Now, with all of that said, I was wondering, since this seems like it might be a common problem graphics programmers face, if someone could suggest an approach. Things I would like input on are data structures I might want to look into (just using vectors, or maybe a hash table for faster access), and maybe some algorithms I should read up on since I don't have ANY experience doing something like this. Lastly, this program does not need to be fast, just accurate. Its going to be used for research purposes, generating instructional files for a stereolithography (SLA) machine. So if there is a quick and dirty way to do this, it would probably be just fine. Speed would icing on the cake, but it isn't neccessary. Thanks, Mike

I suggest you to have a look to BSP trees. They can help you to spacially sort a soup of polygon - cutting the polygons that are intersecting the other ones. Once the BSP tree is built, you should be able to tell what's inside and what's outside of your model.

Regards,

Ok, we barely glazed over them in my last programming class, but i'll take a more focused look at them. Thanks,

Any other suggestions?

Try googling for Boolean CSG algorithm.
Here's a neat looking link about CSG:
http://www.geocities.com/danbalby/

Hey, thank you everyone for the replies, I'm doing a lot of research online and you've given me a good base to start from. The Boolean CSG algorithm looks like its going to be the way to go since the models that I'll be drawing are pretty complex, imagine a big scaffold with large volumes of unoccupied space inside the model.

BSP trees seem like they are just for optimizing drawing on a computer, but that's not what I'm looking for. I need to generate a precise 3d model that can be acutally built in real life, like i need to have a physical model once generated.

On that note, I'd really appreciate it if anyone has any good boolean CSG algorithm links that they could offer up. Thanks,