Punkt in einem geschlossenen 3D-Volumen

Question

Ich habe ein 3D-geschlossenes Volumen von 6 Flächen definiert, jede Fläche hat 4 Ecken.

Also, ich möchte überprüfen, ob ein bestimmter Punkt innerhalb des Volumens oder außerhalb ist. Eine Lösung, die ich gedacht war:

1. Zeichnen eines Zufalls Zeile aus dem gegebenen Punkt und überprüfen, wo sie die Oberflächen schneidet, die das Volumen umschließen. Da ich die Vektoralgebra für die Berechnung des Schnittpunkts von Linie und Fläche verwende, kann der Schnittpunkt irgendwo auf der unendlichen 3D-Fläche liegen.

2. Jetzt überprüfe ich, ob dieser Schnittpunkt zufällig auf der Fläche liegt, die auf der unendlichen Ebene liegt und das Volumen umschließt.

Dafür ich wieder einen zufälligen ray von meinem Schnittpunkt mit der jeweiligen Fläche des Volumens zeichnen will und prüfen, ob Punkt auf dem Gesicht liegt oder nicht.

But I don't know how to check this feature of locating if it is on the surface 
or not. Can someone please suggest how can I do it. 



P.S. One way of doing this was extending ray casting to 3d but that involves 
comparison of slopes to check the orientation. So how can I check orientation 
of 3 points in 3d space. I have 4 vertices which make up that face, I know the 
point under consideration. How can I check if this point lies clockwise or 
counter clockwise to the surface. 

Answer 1

Um Ihr Problem zu betrachten, müssen wir zuerst überlegen, was die Bedeutung von innen oder außen ist. Bei einem Flächenkörper mit vier Flächen teilt jede Fläche den Raum auf genau zwei Seiten, und im Allgemeinen teilen die vier Flächen den Raum in 9 Bereiche, von denen nur einer begrenzt ist und ein Tetraeder begrenzt (wenn wir jedoch die Oberflächen sorgfältig auswählen) erreichen Sie sogar keine begrenzte Region - zum Beispiel machen Sie zwei von ihnen parallel). Also, im Allgemeinen müssen Sie entscheiden, welche der Seiten der Ebenen das Innere oder das Äußere markieren (naja, es spielt auch keine Rolle, da das Äußere dasselbe ist wie das Nicht-Innen).

Mit mehr Flächen kompliziert das Problem (und verkompliziert sich viel weiter), wie Sie mehrere begrenzte Regionen haben können, die auch Festkörper definieren, so dass Sie mehr Informationen benötigen als nur die Ebenen, die es begrenzen.Das Problem verkompliziert sogar noch mehr, wenn die Region zu einer nicht konvexen Region führt, da sich Ihr Punkt in einem Teil Ihrer Region befinden kann, der für andere Flugzeuge auf der einen Seite und auf der falschen Seite für andere ist sei in deinem Körper. Nur sehen eine begrenzte Polygon wie diese

und die Möglichkeiten der Herstellung begrenzt Regionen

Das erste, was Sie brauchen, ist angemessen Ihre solide zu definieren, die Abgrenzung der Flächen mit Kanten und etwas, das die Ränder und den Scheitelpunkt festlegt, die ein Gesicht begrenzen, wie Gesichter sich verbinden, um Ihren Körper zu bilden.

Sobald Sie diese Situation haben, haben Sie eine Reihe von Gesichtern und Vektoren auf die außerhalb für jedes Gesicht (in einer kontinuierlichen Weise, so dass Sie nicht mit einem Gesicht normal nach oben zeigen, und die nächste nach unten zeigend). Das nächste, was Sie tun müssen, ist Ihren Körper in einen konvexen Körper zu teilen. Es kann gezeigt werden, dass für einen dreidimensionalen Körper, der aus glatten Flächen besteht, er in eine endliche Menge konvexer Körper unterteilt werden kann.

Ich werde versuchen, das gleiche Problem in 2D zu veranschaulichen, aber im Wesentlichen das gleiche in 3D ist:

Erstens haben wir die anfängliche poligon haben, nehmen wir an, es konvex ist (dies ist eine wichtige Eigenschaft für diesen Zweck I soll später erwähnt werden):

Stellen wir uns vor es ist ein 3D Asteroid und Sie sind jemand, der auf seiner Oberfläche geht. Wenn du anfängst zu gehen, wirst du alle gelben Linien passieren. Dies sind die Normalen und dafür müssen Sie von jeder Fläche wissen, welche Flächen erreichbar sind und eine Karte von Normalen zu diesen Flächen erstellen, wie ich sie gemacht habe. Wenn Sie auf dem Asteroiden laufen, markieren Sie die Normalen, um zu wissen, wo sich das Innere des Asteroiden befindet, und Sie begrenzen es. Jetzt haben wir eine Karte unseres Asteroiden mit allen Normalen. Lassen Sie uns den Halbraum unter uns zeichnen (eine Seite der Oberfläche, die unter uns liegt). In Geometrie kann dies durch eine Ebene dargestellt werden (eine Ebene hat die Eigenschaft, dass alle ihre Punkte orthogonal zu einem Vektor sind). X*V=0 wobei * den Punkt darstellt Wenn wir das Zentrum unseres Poligons und den normalen Vektor als den gelben Vektor in unserer Zeichnung nehmen, erhalten wir (X - P)*N = 0, wobei X die Position eines Punktes in der Ebene ist, P ist unsere Position (die Mitte des Gesichts) und N ist ein Vektor zur Ebene normal, zeigt nach oben (auf der Außenseite des Asteroiden)

Nun, diese Gleichung die Eigenschaft hat, dass wir ersetzen, wenn X von jeder Position im Raum, alle Punkte X unterhalb der Flugzeug haben ein Wert (X - P)*N < 0 und alle Himmelswerte haben es > 0.

Wenn ich das gleiche für die vier Normalen tun, bekomme ich dies: ... Umgang und der betreffenden Stelle X wird nur in den Asteroiden begraben werden, wenn die vier Ebenen Geben Sie (X - X_face)*(N_face) < 0, wo jetzt, X_face ist die Mitte des Gesichts, und N_face ist das Gesicht normal nach außen von unserem Asteroiden zeigen. Der Punkt wird innerhalb des Asteroiden nur sein, wenn die vier Bedingungen zutreffen.

Aber was passiert, wenn der Asteroid nicht konvex ist?

Wenn Sie die Normalen zeichnen, das wird ... nicht helfen, da es Punkte, die im Inneren des Asteroiden sind und einige der Tests fehlschlagen (denken Sie daran, der Punkt unter allen Oberflächen zu sein hat, aber nicht (wie unten dargestellt):

das Problem ist, dass das Polygon (oder das Polyeder) nicht konvex, und wir können den Algorithmus dort nicht anwenden so zuerst müssen wir das Problem lösen. davon, es konvex zu machen

Wenn Sie beginnen, der gesamten Oberfläche des Asteroiden zu folgen (die Normalen zu erhalten), wenn Sie eine Kante überqueren, gelangen Sie zu einer anderen Ebene, die die Steigung erhöht oder verringert. Wenn sie also die Steigung erhöht, markieren Sie diese Kante (Ecke) in unserem Polygon) als anomal (wir haben sie in rot markiert) und wenn es sinkt, werden wir sie als normal markieren (wir haben sie grün markiert):

wenn alle Kanten normal sind, kein Problem, denn unser Asteroid wird konvex sein, aber wenn einer von ihnen anomal ist, müssen wir in dieser Ebene weitermachen (in den Asteroiden auf der ganzen Ebene graben), bis wir zu einer anderen Oberfläche kommen (wir haben die Ebene verlängert, um sie zu teilen) unser Poligon) als solches:

wie wir eine endliche Anzahl von Kanten haben, und einige von ihnen haben nur als anomal markiert worden ist, wird dieser Prozess zu beenden (erinnern Sie garantiert, dass Sie ein Gesicht zu finden bekommen die andere Seite versuchen (Seite) Ihres Polyeders (Polygons) mit dem Scheitelpunkt nach oben und dem Scheitelpunkt nach unten (in dem zuvor erläuterten Sinne))

so haben Sie Ihr Polyeder in eine endliche Menge konvexer Polyeder zerlegt, auf die der erste Algorithmus angewendet werden kann.

Answer 2

Sie können für jede Oberfläche eine boolesche Bedingung erstellen, die bestimmt, ob ein bestimmter Punkt innerhalb oder außerhalb der Oberfläche liegt. Dies kann erfordern, dass Sie Informationen über die Normalen jeder Oberfläche hinzufügen (d. H. Welche Seite der Oberfläche "nach außen" ist). Wenn diese Bedingung für jede der sechs Oberflächen gilt, befindet sich der Punkt innerhalb des Volumens.

Eine andere ähnliche Methode, um dies zu denken, ist ein System linearer Ungleichungen zu erstellen, die jede Oberfläche verwenden, um eine Ungleichheit zu erzeugen, um einen geschlossenen Raum zu erstellen, der Ihr Volumen darstellt. Es kommt auch darauf an, ob der Punkt "innerhalb" oder "außerhalb" jeder Oberfläche liegt und ob der Punkt innerhalb aller Oberflächen liegt.

Answer 3

Haben Sie einen Blick auf diese Frage: signed distance between plane and point

Nun brauchen Sie nur zu prüfen, ob Ihr Punkt auf der rechten Seite (richtige Vorzeichen) ist jeder Ihrer Volumen Oberflächen. Etwas wie folgt aus:

bool isInside(const std::vector<Planes>& planes, const Point& point){ 

    for(const auto& plane : planes){ 
    const auto dist = 
     dotProduct(plane.normal, vectorSubtract(point, plane.point)); 
    if(dist>0) return false; 
    } 

    return true; 
}; 

Answer 4

also ein Weg, ich glaube, ich kann dies tun, ist:

Extend auf 3D-Oberfläche Strahlwerfprozessoren aber das beinhaltet, wie kann mal ein Strahl von dem Punkt unter Berücksichtigung des Volumens überschritten. Dazu müssen Sie den Schnittpunkt der Linien und der Flächen des Volumens finden.

So what I can do is for a single face (and I will extend it to all the faces) 
is, I check for the point of intersection of 3d line and plane by doing simple 
algebra and then check if the point lies inside the cuboid formed by 
extremities of the vertices forming the face. i.e check if P(x.y,z) which is 
the point of intersection of line and plane lies inside the region defined by 
extremities of the surface. 
i.e. 

x > xlow and x < xhigh and y > ylow and y < yhigh and z > zlow and z < zhigh. 

These two conditions i.e. ray intersects the 3d plane and the intersection 
lies in this region proves that the intersection of ray and plane lies on the 
surface which encloses the volume. 


I can count the number of such intersections if it is odd, the point 
lies inside the volume if it is even the point lies outside the volume. 


Does anyone see a problem with this algorithm?