Jump to content
  • Advertisement
Sign in to follow this  
Azreal42

find a point respecting some constraint

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!