Finding the a face in a mesh that is coplanar to a given point

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

Finding the a face in a mesh that is coplanar to a given point

aseverino
Hello,

I'm trying to find the face index that has its points coplanar to another
given point. This given point is guaranteed to be coplanar to the mesh
*somewhere*.

Is there a more optimized method to find that face without having to iterate
over all of them (in the worst case)?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
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: Finding the a face in a mesh that is coplanar to a given point

Sebastien Loriot (GeometryFactory)
You can use AABB_tree::closest_point_and_primitive()

https://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#a1b3ac9521fd7257f760deafff3743437

Sebastien.

On 10/24/19 6:05 PM, aseverino wrote:

> Hello,
>
> I'm trying to find the face index that has its points coplanar to another
> given point. This given point is guaranteed to be coplanar to the mesh
> *somewhere*.
>
> Is there a more optimized method to find that face without having to iterate
> over all of them (in the worst case)?
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.nabble.com/
>

--
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: Finding the a face in a mesh that is coplanar to a given point

andreas.fabri

I do  not see where that helps.  A point coplanar to a face  f
can be far away from f and be close to a non-coplanar face.

      ************
      *                      *
 p   f1                     ***f2**
      *                                    *
      ******************   

p is coplanar with f2 but f1 is closer

On 10/25/2019 4:27 PM, Sebastien Loriot (GeometryFactory) wrote:
You can use AABB_tree::closest_point_and_primitive()

https://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#a1b3ac9521fd7257f760deafff3743437

Sebastien.

On 10/24/19 6:05 PM, aseverino wrote:
Hello,

I'm trying to find the face index that has its points coplanar to another
given point. This given point is guaranteed to be coplanar to the mesh
*somewhere*.

Is there a more optimized method to find that face without having to iterate
over all of them (in the worst case)?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/


-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
Reply | Threaded
Open this post in threaded view
|

Re: Finding the a face in a mesh that is coplanar to a given point

meder411
While I'm not sure if this is possible as I'm far from in-depth-experienced with CGAL.... I suspect you can build a custom AABB tree around face normals (just parameterize each normal as a point on a unit sphere (S2)). Then, look for the closest point in that AABB tree, treating your query point normal also as a point on the unit sphere.

On Fri, Oct 25, 2019 at 10:36 AM Andreas Fabri <[hidden email]> wrote:

I do  not see where that helps.  A point coplanar to a face  f
can be far away from f and be close to a non-coplanar face.

      ************
      *                      *
 p   f1                     ***f2**
      *                                    *
      ******************   

p is coplanar with f2 but f1 is closer

On 10/25/2019 4:27 PM, Sebastien Loriot (GeometryFactory) wrote:
You can use AABB_tree::closest_point_and_primitive()

https://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#a1b3ac9521fd7257f760deafff3743437

Sebastien.

On 10/24/19 6:05 PM, aseverino wrote:
Hello,

I'm trying to find the face index that has its points coplanar to another
given point. This given point is guaranteed to be coplanar to the mesh
*somewhere*.

Is there a more optimized method to find that face without having to iterate
over all of them (in the worst case)?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/


-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri


--
Marc Eder
Ph.D. Candidate, Computer Science
University of North Carolina at Chapel Hill
Reply | Threaded
Open this post in threaded view
|

Re: Finding the a face in a mesh that is coplanar to a given point

meder411
I didn't finish that thought.... That would help you to narrow down the space to only parallel planes. Then, you can either iterate over all of them and compute the projected distance. Or, if there's still a ton, you can always take the overhead of AABB trees on just these faces, and then choose the closest with `closest_point_and_primitive()`.



On Fri, Oct 25, 2019 at 10:41 AM Marc Eder <[hidden email]> wrote:
While I'm not sure if this is possible as I'm far from in-depth-experienced with CGAL.... I suspect you can build a custom AABB tree around face normals (just parameterize each normal as a point on a unit sphere (S2)). Then, look for the closest point in that AABB tree, treating your query point normal also as a point on the unit sphere.

On Fri, Oct 25, 2019 at 10:36 AM Andreas Fabri <[hidden email]> wrote:

I do  not see where that helps.  A point coplanar to a face  f
can be far away from f and be close to a non-coplanar face.

      ************
      *                      *
 p   f1                     ***f2**
      *                                    *
      ******************   

p is coplanar with f2 but f1 is closer

On 10/25/2019 4:27 PM, Sebastien Loriot (GeometryFactory) wrote:
You can use AABB_tree::closest_point_and_primitive()

https://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#a1b3ac9521fd7257f760deafff3743437

Sebastien.

On 10/24/19 6:05 PM, aseverino wrote:
Hello,

I'm trying to find the face index that has its points coplanar to another
given point. This given point is guaranteed to be coplanar to the mesh
*somewhere*.

Is there a more optimized method to find that face without having to iterate
over all of them (in the worst case)?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/


-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri

Reply | Threaded
Open this post in threaded view
|

Re: Finding the a face in a mesh that is coplanar to a given point

Sebastien Loriot (GeometryFactory)
In reply to this post by andreas.fabri
Because it is stated in the problem definition that the query point is
known to be on a face so the closest face for that point is
the face containing it.

At least that's what I understood when I read "This given point is
guaranteed to be coplanar to the mesh *somewhere*"

Sebastien.

On 10/25/19 4:36 PM, Andreas Fabri wrote:

> I do  not see where that helps.  A point coplanar to a face  f
> can be far away from f and be close to a non-coplanar face.
>
>        ************
>        *                      *
>   p   f1                     ***f2**
>        *                                    *
>        ******************
>
> p is coplanar with f2 but f1 is closer
>
> On 10/25/2019 4:27 PM, Sebastien Loriot (GeometryFactory) wrote:
>> You can use AABB_tree::closest_point_and_primitive()
>>
>> https://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#a1b3ac9521fd7257f760deafff3743437 
>>
>>
>> Sebastien.
>>
>> On 10/24/19 6:05 PM, aseverino wrote:
>>> Hello,
>>>
>>> I'm trying to find the face index that has its points coplanar to
>>> another
>>> given point. This given point is guaranteed to be coplanar to the mesh
>>> *somewhere*.
>>>
>>> Is there a more optimized method to find that face without having to
>>> iterate
>>> over all of them (in the worst case)?
>>>
>>>
>>>
>>> --
>>> Sent from: http://cgal-discuss.949826.n4.nabble.com/
>>>
>>
> --
> Andreas Fabri, PhD
> Chief Officer, GeometryFactory
> Editor, The CGAL Project
>
> phone: +33.492.954.912    skype: andreas.fabri
>

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