CGAL users discussion list

[Jeremy <>]

Thanks. I triangulated my mesh and was able to send it through the collapse process. LindstromTurk_cost gives decent starting results, however it leaves alot of useless triangles by not removing the redundant intermediate edges along a long straight edge.

Here are some before and after on a small test level.
http://tinypic.com/view.php?pic=6hdtet4
http://tinypic.com/view.php?pic=5z23ddl

Starting to wonder if I'm going about this the wrong way, and that I should probably use a simplified algorithm.

Basically, it's important that the result retain the borders and holes, that ultimately gives an accurate and optimized walkable region representation of the environment.

An idea I've had that maybe you can provide feedback on
Leave the input as a quad mesh, go through all the faces, collapse all quads that don't have a border edge into a single point(and probably if they lie on the same plane). I think this seemingly simple process would eliminate all the internal faces right? I'd still need to go through and merge all the edges along straight lines though. What's the best way to do this? Go through all the edges merging any edge that has a previous() and a next() that falls on the same line?

I'm not sure if the 2d convex partitioning would be usable somehow for me since its technically just a 2.5d flood plan. Ideally I would love to optimize it to convex partitions.

Any ideas on how I can achieve this goal would be greatly appreciated.
Effectively I'm wanting to turn a flood filled map from a game
environment into an optimized convex floor plan to use for navigation. The flood fill is created by flood filling small axis aligned bounding boxes and testing collision to find edges, walls, etc. That much works, as the screens should demonstrate. Now the harder part of optimizing it down to something manageable.

Thanks
Jeremy

On 6/22/07, Fernando Cacciola <> wrote:

Hello Jeremy,

> Anyone know of a
> simplification algorithm for what is basically a tessellated floor
> plan of an indoor environment made up of interconnected quads that
> were the result of a flood fill through the environment? It's not a
> closed mesh, and may have holes.

Surface_mesh_simplification fails becasue it is a quad mesh, not a triangle
mesh.
You need to triangulate your quads to allow Surface_mesh_simplification to
apply.

The most obvious straightforward procedure is to just split each quad into
two triangles.
Another possibility is to split each quad into 4 rather than 2 triangles,
adding a center vertex.

If your mesh is given by a Polyhedron_3, you can use
Polyhedron.split_facet() or Polyhedron.create_center_vertex():

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Polyhedron_ref/Class_Polyhedron_3.html#Cross_link_anchor_693

In any case you will end up with a triangle mesh, of course, not a quad mesh
anymore, but borders and holes will be retained, so this seems to fit your
requirements.

HTH

Fernando Cacciola
GeometryFactory


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss