Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

My problem is about simplifying a given topology that can be opened ( an usual 3D reconstruction of a given square on a map ), totally closed (like a perfect sphere) or a topology with holes ( a sphere with a hole ).

Now, after reading a lot about this I probably should note that I already have a solution for simplifying the 3D mesh, my real problem is to keep the deviation and the difference at a really bare minimum level, in other words I have to preserve the topology in this process and at the same time lower the polycount.

The best that I found is the Douglas-Peucker algorithm, but it's for 2D shapes, I would like to hear a suggestion about an equivalent algorithm for 3D surfaces and topology.

Thanks.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

The first part of your question doesn't really make sense. Topology is the study of adjacency, connectivity, and containment. With topology you examine the structure and (non-geometric) shape of things. You wouldn't, for example, use topology to "simplify" a torus into a sphere by filling in the hole.

A better question would be:

What algorithms exist for simplifying a triangulated 3D surface while preserving its topological structure?

You already found a cornucopia of references in a link from user @dtlarek in response to your question on http://math.stackexchange.com.

Additionally, you could look at the excellent GTS library. It provides two surface simplification algorithms:

It's not clear to me that these methods will preserve topological structure in all cases. You can see an example of what one method does in this video of the reverse of the surface simplification of a horse.

If Python is your style, then you can access GTS's functions through the PyGTS Python bindings.

EDIT:

Your picture (in the comments) does help to describe the problem, but that problem is not one of topology. It's true that the mesh structures in each of the heads in your image are not homeomorphic - the meshes are topologically different. However, you are asking about something different: how to simplify the mesh while preserving the appearance. You want the thing to "look" nearly the same, but have fewer edges and vertices. The image below gives another example.

CGAL hand simplificaiton

The hands image is from the CGAL Triangulated Surface Mesh Simplification page. That page describes a well-developed and widely used approach to mesh simplification that is a "process of reducing the number of faces used in the surface while keeping the overall shape, volume and boundaries preserved as much as possible" (from the CGAL site).

Just remember, unless you are concerned with the topology of the mesh itself, this is not a question of topology.

share|improve this answer
    
hopefully this image will clear to you my idea of topology darcypatko.com/wp-content/uploads/2010/08/retopology.jpg and what i mean with preserving the topology while reducing the polycount. –  user2128456 Mar 6 '13 at 7:19
    
Please vote if my edit is helpfu! –  katahdin Mar 6 '13 at 13:03
    
thanks, this is what I was looking, hope that that page will contain some useful algorithms. –  user2128456 Mar 6 '13 at 13:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.