Here is my problem: I have to find the best position of a point respecting some constraint. The point should be "above" N plane. So it should respect theses inequation: a1x + b1y +c1z + d1 > 0 a2x + b2y +c2z + d2 > 0 a3x + b3y +c3z + d3 > 0 . . . . anx + bny + cnz + dn > 0 Thats the first constraint. The plane are always defining an existing volume, but this volume is not necessary closed. The second constraint is that the solution point have to be the closest point to another out of the volume. ie: the distance between my reference point and the solution point should be the smaller possible. I have to solve this system numerically. Please heeelp ;) PS: I know... I need to improve my english level ;)

it looks to me that the point the closest to a reference point outside the volume is a point on the surface. So you need to find the closest distance to the n planes, there intersecting edges or vertices.

It sounds like the shortes distance of a point to a polyhedron.

Is this what you mean?

No... that not my problem,
in fact, i want to make a LOD that always enclose the volume of the original mesh.
So at the edge collapse, to be sure that the new faces created are enclosing the old faces, a suffisant condition is that the point lie outside the planes defined by the old faces.

So the solution point have to be above these plane.
But i also need that the new volume created by the edge collapsing be the smaller possible. So i ve decide to introduce the second constraint (the solution point need to be the closest point respecting the plane inequalities with one of the edge point).

It should work because the mesh is always closed and convex.
(the first step of the algo is to build a convex hull of the mesh)

I'll post a picture to explain this within few hour.

first:
what do you mean by 'above' N plane

saying that anx + bny + cnz + dn has to be greater than 0
it all depends on how you construct the equations of the planes

multiplying by a number (e.g. -1) gives the same plane, but your inequation is different

second:
this implies (like Airo said) that your solution lies on 1 of the planes

the normal of the plane is the normal of my triangle. So i have only one plane possible.

Yes the solution lies on a plane but not necessary on all the plane.

For exemple :
1 2
\/ <-- my solution point is a the intersection of these two
/\ planes but do not intersect the third plane.
____/__\_____3
/
Sorry for my crappy asci art ;)

I want to implement the progressive hulls describe here
http://research.microsoft.com/~hoppe/silclip.pdf
but i have replace the winding number by the distance between my point solution and one of the point of the edge (coz my mesh is convex)

just a thought but

can't you just go through each plane
find the shortest distance (= perpendicular line i believe) from the ref point to this plane
remember this distance

at the end choose the shortest distance (with corresponding plane)
and calculate the solution point through the intersection of the perp. line and plane

i'm sure there are a couple of gaps in my solution, but that's the generally idea

to ILM:
That was the first idea i ve got. But it dont work ...

Take a look at this picture:
http://etudiant.epita.fr/~godin_g/explication.jpg

In this picture u can see that the shortest distance is 0 (plane 1) but the solution doesn't lies on the plane 1.

The picture show the problem in 2D... I'll make another to show my problem in 3d.


to grhodes_at_work:
My appliction is a motor3d. I want to use this special lod to create a bounding mesh (approximatly ~30/50 triangles). These bounding mesh will be used for occlusion culling/collision purposes.
Im actually using the garland and heckbert algorithme for creating LOD.
I want to replace the cost function and the way to find the target vertex. So at each contraction the new triangles will allways enclose the old triangles.
To be sure that the new faces are enclosing the old triangles, the condition is that the target vertex be above the plane of all the old triangle.
But we also need to minimize the volume created by the contraction. So the target vertex must be above all plane AND be the closest to a reference point.
I choose the reference point to be either one point of the edge either the midpoint of the edge.

Here is the picture of the 3d problem:
http://etud.epita.fr/~godin_g/EXPLICATION3D.jpg

Unfortunatly, i can't show the plane of each faces, coz it was unreadable.

But u can imagine them ;p