Sign in to follow this  
Benjamin GD

Simple Mesh Union Algorithm

Recommended Posts

Circumstance:
I am making a 3D map editor for my game engine. I need to be able to take models and put them partly inside of each-other, with the insides being hollowed and the geometry adjusted so there are no triangle-triangle intersections.

Solution:
Make a buffer containing a copy of one of the meshes that the intersection is about. Take the other mesh and "subtract" it from the first mesh, then use the copy of the first mesh to "subtract" from the other mesh. At the end, release the buffer and simply combine the two new meshes into a single unified mesh.

Problem:
Mesh "Subtraction"

This kind of subtraction will only subtract from triangles, and not entire volumes.

Research:

Part 1 - Intersections

I have been thinking up a supposedly "fast" algorithm to do this. There are two meshes; the target; the mesh which is having parts of it's geometry removed and revised, and the subtractor; the mesh which is affecting the target. To keep it simple, a single original triangle of the target becomes considered a polygon in-itself; it will not interfere with other triangles.

We will use two for loops (one inside of the other) at the base of our work. The first one will scroll down the list of triangles as part of the target, and the second will search for the subtractor's triangles having intersections with the current target-triangle selected. This way we will find all intersections we need to know about.

Intersection breakdown:
1. plane through plane > triangle areas converts intersection vector into line segment


2. subtractor-point inside target-plane > point within target-triangle area

Discuss any apparent problems...

my Questions:
1. Is this intersection breakdown comprehensive enough?
2. How could these intersections be calculated? I have a few pieces of math I learned from my good friend Stephan; who you might know by this: http://www.gamedev.net/community/forums/topic.asp?topic_id=506794

But I only understand a few things about vectors and planes, such as the cross and dot products, I also know of the equation of the plane. I just don't understand ALL of the things you can do with them, because I don't really know how to visualize their workings. I need to also learn matrices, but I'm sure you guys can link me up with a website where you learned them for yourself.

Part 2 - Re-Triangulation
... Coming after the first discussion is cooking.
Though I'm prepared for this part, let's wait before I get over my head in the math from Part 1.

Cheers!
- Benjamin

[Edited by - Benjamin GD on October 2, 2010 12:38:53 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this