**comp.graphics.algorithms**

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

news:1145575916.937224.320570@i40g2000cwc.googlegroups.com...

> This tricky problem is part of search of geodesic line. Suppose I have

> a surface and I want to find out the geodesic line between two points

> in the surface. This surface has curvature and is composed of many

> triangular elements.

>

> I choose two end points in the surface then I can generate a straight

> line between these points. I divide this straight line into 5 or 6

> segments. Now I want to project generated segment nodes onto the

> surface. Firstly, the x and y co-ordinates of each of the segment nodes

> are used to locate specific surface trangular element in which it lies.

> The z co-ordinate of the segment node is determined using the known

> nodal co-ordinates of the surface element by a standard shape function.

>>From these initial positions, the projected segment nodes are allowed

> to slide over the surface elements in search of the equilibrium

> configuration. Once the final state of equilibrium is attained, the

> path of a geodesic will be defined by these projected segment nodes.

>

> My questions are

> 1) how to locate specific surface trangular element using the x and y

> co-ordinates of each of the segment nodes? I know the node coordinates

> of each surface triangular element but I don't know which element I

> need locate.

> 2) how to work out the z co-ordinate of the segment node using the

> known nodal co-ordinates of the surface element by a standard shape

> function?

I think you are going about this in an inefficient manner

(the projection of points onto the surface).

My approach (used in medical image analysis software) has been

to construct the adjacency information for vertices, edges,

and triangles. Given two points on the triangle mesh,

connect each point to a vertex of the containing triangle.

Use Dijkstra's algorithm for finding a shortest-length path

consisting of triangle edges. This is the starting path for

a relaxation process which updates the polyline path.

The prototypical update starts with two consecutive edge

of a pair of triangles that share an edge--the end points

of the pair of edges are vertices opposite the shared edge.

The shared point of the two edges is moved along the shared

edge to minimize the path length. No part of this approach

requires projecting points onto the triangle mesh.

If you have a parameterized surface from which the triangles

were generated, I already have an implementation for geodesic

path construction at my web site. At the home page, select

the "Source Code" tab, then the "Applications" tab. In the

"Miscellaneous" section, there is "Construction of geodesic

curves on B-spline height fields". This uses general code to

handle any smooth parametric surface. The documentation

is accessed from the "Documentation" tab at the home page,

section on "Curves", document title is "Computing Geodesics

on a Riemannian Manifold".

--

Dave Eberly

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

How to project a point onto a surface? =>

Replies:

Re: How to project a point onto a surface?

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.