CGAL users discussion list

[Qianqian Fang <>]

 wrote:
> A point to polyhedron test is O(n) for every test. That will be quite
> cumbersome, especially for a large number of points needed for mesh
> generations. You might try to obtain some code to compute the medial surface 
> of
> the polyhedron, in order to efficiently compute the distance function, but I'm
> not sure how that works for self-intersecting meshes. Besides, the complexity
> is at least O(n^2).
>   
thank you for the reply.

I was just thinking about using an Octree to represent this surface, and 
surprisingly
I found something in demo/Surface_mesher. I am still trying to digest the
demo. The following lines may be related to what I need:

CGAL_polyhedral_surface* surface_ptr;
std::ifstream in(off_filename.toUtf8());
surface_ptr = new CGAL_polyhedral_surface(in,
                                       sharp_edges_angle_lower_bound,
                                       sharp_edges_angle_upper_bound,
                                       tree /*construct octree*/);

it creates a surface with octree, but then, I want to query the distance
from any point, I have not found function to do such yet.
> Why don't you clip the intersecting parts? See what triangle intersect badly,
> cut off the inside-intersecting parts and then glue the intersections
> boundaries together. You can do this in O(n) quite easily.
>   
clipping is easy, but how to glue the openings is not clear to me.
I am not familiar with the literature in this field, and I only hope
I can find some tools in CGAL to do this easily.
> Amir.
>
> -----Original Message-----
> From: Qianqian Fang [mailto:] 
> Sent: Sunday, February 22, 2009 10:59 PM
> To: 
>
> Subject: [cgal-discuss] use Surface mesher to re-mesh self-intersecting
> surfaces
>
> hi
>
> In the past, I asked in this list about removing self-intersecting
> elements from triangular surface. I was recommended to use
> the surface mesher avoid repairing a bad mesh as it guarantees to
> have no self-intersecting elements.
>
> Now, I need to process a surface generated from other software,
> unfortunately, this mesh contains self-intersecting elements. So, I
> still need a program to fix this surface (and resample it to my
> desired density).
>
> Reading the documents of the Surface Mesher, I have the impression
> that it can be applied for this situation. The only difference
> is that the surface is not defined by gray-scale image, or an implicit
> function, but by a triangular surface mesh.
>
> Indeed, I can even define the surface by an implicit function, which
> returns the distance from a Point_3 to a Polyhedron_3, similar to
> the sphere case in the manual. Does this sound like a viable
> approach to you?
>
> If it may work, what I need is to find a subroutine to calculate the
> distance. I only found a squared_distance() for Point_3
> to Plane_3 in include/CGAL/squared_distance_3_2.h. I am wondering
> if a similar function to calculate Point3 to a polyhedron exists?
> if it does, can anyone show me an example how to use it?
>
> thank you
>
> Qianqian
>