# find a point respecting some constraint

This topic is 4854 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 ;)

##### Share on other sites
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?

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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 ;)

##### Share on other sites
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)

##### Share on other sites
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

##### Share on other sites
Azreal42,

Please tell us what your application is. Why do you need the solution to this problem, and please also show us what you have done to try and solve it for yourself, :).

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
Quote:
 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.

Now it is clear what you are trying to do. The formulation you seek is as a "nonlinear programming" problem with linear inequality constraints. The function to minimize is to volume of the collapsed mesh subject to the constraints that all the vertices lie within the old mesh. As you mention, the constraints are linear inequalities, although the standard formulation of the problem does not use strict inequality.

The other half of the problem is setting up the function to minimize. Assuming your collapsed mesh is a simple polyhedron, a formula for computing the volume involves summing the signed volumes of tetrahedra. Each tetrahedra has a vertex at the origin. The remaining three vertices are those of a face of the polyhedron. In your problem, you have a vertex that may be selected along an edge, the edge to be removed for the collapse. If you write the vertex as V = E0+t*(E1-E0), where E0 and E1 are the end points of the edge and 0 <= t <= 1, then the polyhedron volume formula has the t-parameter introduced into those signed volumes corresponding to tetrahedra that share V. The signed volume is a determinant that, when containing a vertex varying over an edge, becomes a cubic polynomial in t. The total volume will itself then be a cubic polynomial in t. This rules out trying to reformulate the problem as a linear complementarity problem (LCP), so you have to resort to the more general nonlinear programming (NP), sometimes called mathematical programming (MP) techniques. In particular, search for Karush-Kuhn-Tucker conditions.

Actually... Assuming this formulation is what you really want, the linear inequalities are in terms of t also. The feasible set of t values is obtained as intersections of semiinfinite intervals. Because of this one-dimensional setting, you should be able to compute the feasible set as a union of bounded intervals, then minimize the cubic polynomial on each interval, selecting the t that leads to the minimum over all the interval minima.

Your post indicates you might allow V to vary over more than an edge (not clear to me from your writing), in which case you have a much harder problem that requires the general MP approach.

##### Share on other sites
Quote:
 Original post by Azreal42to 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.

Thank you!

##### Share on other sites
to Dave Eberly:
Ok i'll search this way.

to all:
Thanks a lot for all this answers :)

##### Share on other sites
Quote:
 Original post by Anonymous Posterto Dave Eberly:Ok i'll search this way.

I should have been more careful in my post. The linear inequality constraints in nonlinear programming problems must all be satisfied, so you get a convex domain over which the function must be minimized. However, your original mesh is not necessarily convex. That makes the problem more difficult in that the NP techniques will not apply. Instead, you need to choose V to minimize the volume and to be a point inside the original mesh (a point-in-polyhedron test). You might very well have to resort to an iterative scheme that samples candidates for V and chooses from this set a V that is inside the original volume and leads to minimum volume compared to other points in the set :(

##### Share on other sites
no my mesh is always convex coz i m building a convex hull at the first step of the algorithme

##### Share on other sites
Quote:
 Original post by Anonymous Posterno my mesh is always convex coz i m building a convex hull at the first step of the algorithme

It appears that I have misread your posts. I thought you were collapsing edges in the object's triangle mesh, as compared to collapsing edges in a bounding polyhedron. A generalization of "convex hull" to allow concavities is the "alpha hull". Also search on "cocone" (Tamal Dey) and on "crust algorithms" (Nina Amenta).

##### Share on other sites
I think that convex hulls are sufficient for my problem, but these techniques (alpha hull crust) are very interesting.

##### Share on other sites

This topic is 4854 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628645
• Total Posts
2984028

• 9
• 9
• 9
• 10
• 21