**comp.graphics.algorithms**

## Subject: **Re: How to project a point onto a surface?**

news:1145897658.079982.220220@t31g2000cwb.googlegroups.com...

> Thanks Dave for your reply. I really appreciate your help. The mesh

> surface in my case is composed of finite element elements which are

> triangles with three nodes coordinates known.

To walk the triangles, you will need to establish the

adjacency information. I cannot determine from your

statement if you already have this adjacency. It sounds

like you just have an unordered collection of triangles.

> I want to make an algorithm to let user interactively choose

> two end points on two surface boundary edges. Then the

> algorithm can find out the geodesic line between these two

> end points over the mesh surface. The method in my question

> is similar to first point you mentioned:determine which triangle

> a point projects using 2-dimensional methods.

Now I see what you are doing. My company built such a tool

for a medical imaging package we work on. You should not be

projecting points to obtain the endpoints. Instead, you want

to use a 3D picking operation. A pick ray is generated based

on the camera model (perspective or orthogonal) and on the

screen location at which the user clicked the mouse. The

ray is created in the coordinate system of the triangle mesh.

If you have a small number of triangles, a simple iteration can

be made over the triangles, each a ray-triangle intersection

query. If you have a large number of triangles and if you plan

on quite a few queries, you should consider building something

like a bounding-box tree to help localize the search for

triangles intersected by the ray.

And just to make it clear, what I proposed above does not

require the triangle mesh to be the graph of a function (i.e. a

height field). The linear walk method applies when the triangle

mesh is the graph of a function.

> However, I would like to try another method as well. I am

> very interested in your "linear walk" algorithm. Can you

> tell me where I can find detail information about this algorithm?

> The union of the triangles in my case is a convex polygon.

I recall Dave Watson (famous for the incremental Delaunay

algorithm in n-dimensions) used the term "linear walk". My

Delaunay2D sample application illustrates this. The linear

walk itself is in the Foundation library file Wm3Delaunay2.cpp,

function GetContainingTriangle(). The sample application

allows you to click on a point in a (Delaunay) triangle mesh.

A starting triangle is tested, and then a path of triangles

leading to the containing triangle is drawn.

--

Dave Eberly

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

How to project a point onto a surface? =>Re: How to project a point onto a surface? =>Re: How to project a point onto a surface? =>Re: How to project a point onto a surface? =>Re: How to project a point onto a surface? =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.