Find all neighbours of a certain primitive

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Find all neighbours of a certain primitive

Rash
Hi people,

I wrote a small raytracer (with CGAL::Surface_mesh<Point> Mesh) with tree acceleration in cgal. I would like to find all neighbours of a hit primitive.

Ray_intersection hit = tree.first_intersection(rays[y][x]);

if(hit)
{
    const Point& point =  boost::get<Point>(hit->first);
    const Primitive_id& primitive_id = boost::get<Primitive_id>(hit->second);
    //i need the neighbours of the hit primitive
}

How do I this? I found this documentation but it seems to work only for points not primitives:

https://doc.cgal.org/latest/Spatial_searching/index.html

And it searches for its euclidan distance not for being connected together.

Is there something like:

std::vector<Primitive_id&> ids = getNeighoursOfPrimive(primitive_id);


Like I said I am using CGAL::Surface_mesh<Point> Mesh for my mesh and their is only one mesh in the scene.

Kind regards
Rashid

Reply | Threaded
Open this post in threaded view
|

Re: Find all neighbours of a certain primitive

MaelRL

Hello,

Do you really care for the primitive, or just the neighboring faces? If you just want the neighboring faces, and assuming your primitive is AABB_face_graph_triangle_primitive, the primitive ID is a boost::graph_traits<Surface_mesh>::face_descriptor (i.e. Surface_mesh::Face_index) and you can use BGL-like functions provided by CGAL such as CGAL::faces_around_face:

face_descriptor fd = p_id;
for(face_descriptor neigh_fd : CGAL::faces_around_face(halfedge(fd, sm), sm) // sm is your surface mesh
{
  etc
}

See the package BGL for a lot of convenient functions (it requires a data structure to fit a certain interface, which CGAL::Surface_mesh does using the 'graph_traits' interface).

Best,
Mael

On 16/05/2019 01:57, Rash wrote:
Hi people,

I wrote a small raytracer (with CGAL::Surface_mesh<Point> Mesh) with tree acceleration in cgal. I would like to find all neighbours of a hit primitive.

Ray_intersection hit = tree.first_intersection(rays[y][x]);

if(hit)
{
    const Point& point =  boost::get<Point>(hit->first);
    const Primitive_id& primitive_id = boost::get<Primitive_id>(hit->second);
    //i need the neighbours of the hit primitive
}

How do I this? I found this documentation but it seems to work only for points not primitives:

https://doc.cgal.org/latest/Spatial_searching/index.html

And it searches for its euclidan distance not for being connected together.

Is there something like:

std::vector<Primitive_id&> ids = getNeighoursOfPrimive(primitive_id);


Like I said I am using CGAL::Surface_mesh<Point> Mesh for my mesh and their is only one mesh in the scene.

Kind regards
Rashid

Reply | Threaded
Open this post in threaded view
|

Re: Find all neighbours of a certain primitive

Rash
It works, thank you a lot.

There is a small bug. I would like to find all neighbours, not only the
ones which share a edge. If two triangles share a vertex (but not an
edge), they should be neighbours. Here is an example (same color means
it is a connected surface). There should be only a red and one green
surface. There are 4 surfaces colors.

https://owncloud.ev-bs.de/index.php/s/1qFVNbiwA2Z6o7D

I tried to use:

CGAL::Face_around_target_circulator< Graph >

but I failed. Is there a way to get all triangles which share a vertex
descriptor with surface mesh?

For finding one connected Surface I wrote this code. What could I change
to get all connected faces, even the one only connected via a single vertex?

My code:


void visitAllFaces(const face_descriptor &_fd,
std::map<face_descriptor,size_t> &_maps, std::set<face_descriptor>
&_visited, const size_t _patch_index, const Mesh& _mesh)
{
    const size_t key_was_found = _visited.count(_fd);
    if(!key_was_found)
    {
        _visited.insert(_fd);
        _maps[_fd] = _patch_index;

        for(face_descriptor neigh_fd :
CGAL::faces_around_face(halfedge(_fd, _mesh), _mesh)) // m is your
surface mesh
        {
            if(neigh_fd !=
boost::graph_traits<CGAL::Surface_mesh<K::Point_3> >::null_face())
            {
                visitAllFaces(neigh_fd,_maps,_visited, _patch_index,_mesh);
            }
        }
    }
}

Btw. having null faces which just crash (no assert warning) is realy
confusing.


Am 16.05.19 um 08:22 schrieb Mael:

> Hello,
>
> Do you really care for the primitive, or just the neighboring faces? If
> you just want the neighboring faces, and assuming your primitive is
> AABB_face_graph_triangle_primitive, the primitive ID is a
> boost::graph_traits<Surface_mesh>::face_descriptor (i.e.
> Surface_mesh::Face_index) and you can use BGL-like functions provided by
> CGAL such as CGAL::faces_around_face
> <https://doc.cgal.org/latest/BGL/group__PkgBGLIterators.html#ga5a12f39e74a0667374570d61b859bfb1>:
>
> face_descriptor fd = p_id;
> for(face_descriptor neigh_fd : CGAL::faces_around_face(halfedge(fd, sm),
> sm) // sm is your surface mesh
> {
>   etc
> }
>
> See the package BGL
> <https://doc.cgal.org/latest/BGL/group__PkgBGLRef.html> for a lot of
> convenient functions (it requires a data structure to fit a certain
> interface, which CGAL::Surface_mesh does using the 'graph_traits'
> interface).
>
> Best,
> Mael
>
> On 16/05/2019 01:57, Rash wrote:
>> Hi people,
>>
>> I wrote a small raytracer (with CGAL::Surface_mesh<Point> Mesh) with
>> tree acceleration in cgal. I would like to find all neighbours of a
>> hit primitive.
>>
>> Ray_intersection hit = tree.first_intersection(rays[y][x]);
>>
>> if(hit)
>> {
>>     const Point& point =  boost::get<Point>(hit->first);
>>     const Primitive_id& primitive_id =
>> boost::get<Primitive_id>(hit->second);
>>     //i need the neighbours of the hit primitive
>> }
>>
>> How do I this? I found this documentation but it seems to work only
>> for points not primitives:
>>
>> https://doc.cgal.org/latest/Spatial_searching/index.html
>>
>> And it searches for its euclidan distance not for being connected
>> together.
>>
>> Is there something like:
>>
>> std::vector<Primitive_id&> ids = getNeighoursOfPrimive(primitive_id);
>>
>>
>> Like I said I am using CGAL::Surface_mesh<Point> Mesh for my mesh and
>> their is only one mesh in the scene.
>>
>> Kind regards
>> Rashid
>>

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


Reply | Threaded
Open this post in threaded view
|

Re: Find all neighbours of a certain primitive

MaelRL

Hello,

When you mean "vertex", do you mean a combinatorial vertex, or do you mean its geometric position? What is supposed to be done in non-manifold situations such as two independent umbrellas around the same (combinatorial) vertex? What do you mean with Face_around_target "failed"?

Where are your colors coming from? Note that if you are interested in defining connected components on your mesh, you can also look into these functions.

The null face represents the outside of the domain, and is just usually a null pointer which is why it is so silent (but something else could be done it's true). You can check if your face is this null face via an equality check with "boost::graph_traits<Graph>::null_face()", and if you are manipulating (half)edges via the "is_border(h/e, g)".

Best,
Mael

On 13/06/2019 17:02, Rash wrote:
It works, thank you a lot.

There is a small bug. I would like to find all neighbours, not only the
ones which share a edge. If two triangles share a vertex (but not an
edge), they should be neighbours. Here is an example (same color means
it is a connected surface). There should be only a red and one green
surface. There are 4 surfaces colors.

https://owncloud.ev-bs.de/index.php/s/1qFVNbiwA2Z6o7D

I tried to use:

CGAL::Face_around_target_circulator< Graph >

but I failed. Is there a way to get all triangles which share a vertex
descriptor with surface mesh?

For finding one connected Surface I wrote this code. What could I change
to get all connected faces, even the one only connected via a single vertex?

My code:


void visitAllFaces(const face_descriptor &_fd,
std::map<face_descriptor,size_t> &_maps, std::set<face_descriptor>
&_visited, const size_t _patch_index, const Mesh& _mesh)
{
    const size_t key_was_found = _visited.count(_fd);
    if(!key_was_found)
    {
        _visited.insert(_fd);
        _maps[_fd] = _patch_index;

        for(face_descriptor neigh_fd :
CGAL::faces_around_face(halfedge(_fd, _mesh), _mesh)) // m is your
surface mesh
        {
            if(neigh_fd !=
boost::graph_traits<CGAL::Surface_mesh<K::Point_3> >::null_face())
            {
                visitAllFaces(neigh_fd,_maps,_visited, _patch_index,_mesh);
            }
        }
    }
}

Btw. having null faces which just crash (no assert warning) is realy
confusing.


Am 16.05.19 um 08:22 schrieb Mael:
Hello,

Do you really care for the primitive, or just the neighboring faces? If
you just want the neighboring faces, and assuming your primitive is
AABB_face_graph_triangle_primitive, the primitive ID is a
boost::graph_traits<Surface_mesh>::face_descriptor (i.e.
Surface_mesh::Face_index) and you can use BGL-like functions provided by
CGAL such as CGAL::faces_around_face
<https://doc.cgal.org/latest/BGL/group__PkgBGLIterators.html#ga5a12f39e74a0667374570d61b859bfb1>:

face_descriptor fd = p_id;
for(face_descriptor neigh_fd : CGAL::faces_around_face(halfedge(fd, sm),
sm) // sm is your surface mesh
{
  etc
}

See the package BGL
<https://doc.cgal.org/latest/BGL/group__PkgBGLRef.html> for a lot of
convenient functions (it requires a data structure to fit a certain
interface, which CGAL::Surface_mesh does using the 'graph_traits'
interface).

Best,
Mael

On 16/05/2019 01:57, Rash wrote:
Hi people,

I wrote a small raytracer (with CGAL::Surface_mesh<Point> Mesh) with
tree acceleration in cgal. I would like to find all neighbours of a
hit primitive.

Ray_intersection hit = tree.first_intersection(rays[y][x]);

if(hit)
{
    const Point& point =  boost::get<Point>(hit->first);
    const Primitive_id& primitive_id =
boost::get<Primitive_id>(hit->second);
    //i need the neighbours of the hit primitive
}

How do I this? I found this documentation but it seems to work only
for points not primitives:

https://doc.cgal.org/latest/Spatial_searching/index.html

And it searches for its euclidan distance not for being connected
together.

Is there something like:

std::vector<Primitive_id&> ids = getNeighoursOfPrimive(primitive_id);


Like I said I am using CGAL::Surface_mesh<Point> Mesh for my mesh and
their is only one mesh in the scene.

Kind regards
Rashid