Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space

I am looking for a numerically efficient algorithm to get a triangular surface mesh of the convex hull given by 8 points in three-dimensional space.

For context, the use case is the following:

I have a numerical Simulation calculating the time evolution of a field with three components on a lattice. Say we have lattice coordinates $ (i,j,k)$ , then every lattice point $ (i,j,k)$ has a field vector $ (\phi_1, \phi_2 , \phi_3)$ attached.

For relevant physics, I need to now take unit cells on my lattice, so the 8 corners of a little cube of my lattice. I take the field vectors $ (\phi_1, \phi_2 , \phi_3)$ of every corner of my unit cell and then interpret their convex hull as a closed volume in $ \phi$ -space, with $ \phi$ -space being the 3D space given by the $ (\phi_1,\phi_2,\phi_3)$ coordinates.

I am now interested if the volume spanned by these 8 points in $ \phi$ -space does the following things:

  1. If it contains the origin, $ (0 ,0 ,0 )$

  2. If a Ray traveling from the origin in $ (-1,0,0)$ -direction pierces my given volume

The idea to evaluate both 1.) and 2.) at the same time is to decompose the surface of the convex hull into triangles. For a triangle in 3-Dimensional space, it is easy to evaluate whether it is pierced by my given Ray in $ (-1,0,0)$ direction. I can then count how many triangles are pierced. If exactly two triangles are pierced (because of convexity), I know the cell satisfies condition 2.). If exactly one triangle is pierced, I know the origin has to lie inside my volume, that is condition 1.) is satisfied. Lastly, when no triangles are pierced, none of the above apply.

I think this approach is probably relatively fast. Speed is critical, because I have approximately $ 10^6 … 10^9$ cells to evaluate per sweep across my lattice.

I’d be interested in any other approaches as well, though.

Update: So, I think possibly a 3D-Gift-Wrapping algorithm would atleast produce the required result, because it creates the convex hull by consecutively finding triangles on the surface? I will have to try that out tomorrow.

Can I do better than that in terms of efficiency?

How to compute the convex hull in linear time of the number of points on it?

I must construct 2 functions. The first function is used to add a point passed to it to an arraylist. The second function must take this arraylist, find out the set of points that lie on the convex hull formed from them, and return a linked list of those points.

How can I achieve this in a O(h) time (worst case), given that h is the number of points on the convex hull, NOT n which is the number of points originally present in the arraylist.

The two functions can have different worst case running time but most importantly, non should have a worst case that takes more than O(h).

I made it to O(n), not further though!

Describing hull of vertex intersections of two convex bounded polytopes?

We have two convex bounded polytopes $ P_1$ and $ P_2$ where

a. $ P_2\subseteq P_1$

b. $ \mathcal{V}(P_2)\cap\mathcal{V}(P_1)\neq\emptyset$ .

  1. Is there a name for the polytope $ P=\mbox{Conv}(\mathcal{V}(P_2)\cap\mathcal{V}(P_1))$ ?

  2. Is there a polynomial time algorithm to describe $ P$ by half-spaces

Note $ \mathcal{V}(P_2)\cap\mathcal{V}(P_1)=\emptyset\iff P=\emptyset$ .

Convex hull partition of a set of points

Given a set $ S$ of $ n$ points in $ \mathbb R^2$ , denote by $ \mathrm{conv}(S)$ the convex hull of $ S$ . Let \begin{align*} S_1 &= \mathrm{conv}(S)\ S_{i+1} &= \mathrm{conv}\left(S \setminus \bigcup_{j=1}^i S_j\right). \end{align*}

Now $ S_1,\ldots$ forms a partition of $ S$ . Is there an $ O(n\log n)$ time algorithm for computing this partition?

algorithm to compute the convex hull of a set of m possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of m possibly intersecting convex polygons in the plane, with a total of n vertices. Let h denote the number of vertices on the boundary of the desired convex hull. The algorithm should run in O(mh+n) time

Classifying Radon partitions in $\mathbb{R}^n$ whose affine hull is $\mathbb{R}^n$

Specifically, I want to determine all distinct “types” of Radon partitions of $ n+2$ points in $ \mathbb{R}^n$ for which the affine hull is all of $ \mathbb{R}^n$ . This is a homework question, so I’m primarily looking for advice on getting started.

Radon’s theorem states that any set of $ n+2$ points in $ \mathbb{R}^n$ can be partitioned into two disjoint sets with intersecting convex hulls.

The affine hull of a set $ S$ is given by $ $ \mbox{aff}(S)=\left\{\sum_{i=1}^k\alpha_ix_i:k>0,x_i\in S,\alpha_i\in\mathbb{R},\sum_{i=1}^k\alpha_i=1\right\}.$ $

So, the simplest case is when $ n=1$ , and clearly the affine hull of any Radon partition of $ n+2=3$ points in $ \mathbb{R}$ is all of $ \mathbb{R}$ . When $ n=2$ , the $ n+2=4$ points can be partitioned as a triple and a singleton or two pairs of points. In the case of the former, the convex hull of the triple must contain the singleton. In the case of the latter, the pairs of points must form intersecting line segments. But the former is the only “type” of partition I want to consider, as it’s affine hull is in fact $ \mathbb{R}^2$ , but the affine hull of the partitions in the latter is not all of $ \mathbb{R}^2$ . So I might conjecture that the full classification requires that the convex hull of one of the partitions must be fully contained in the convex hull of the other partition, but I’m not sure if I even believe this intuitively.

Thanks in advance for any advice.

Количество контрольных точек в HULL шейдере

На данный момент я изучаю шейдеры и сейчас остановился на hull/domain shaders. Я не смог найти нужную информацию, из-за чего у меня появилась небольшая путаница: почему hull шейдер может принимать и отдавать больше контрольных точек, чем в примитиве, с которым он работает?

Пример c MSDN:

#define MAX_POINTS 32  [domain("quad")] [partitioning("integer")] [outputtopology("triangle_cw")] [outputcontrolpoints(16)] [patchconstantfunc("SubDToBezierConstantsHS")] BEZIER_CONTROL_POINT SubDToBezierHS(      InputPatch<VS_CONTROL_POINT_OUTPUT, MAX_POINTS> ip,      uint i : SV_OutputControlPointID,     uint PatchID : SV_PrimitiveID ) {     VS_CONTROL_POINT_OUTPUT Output;      // Insert code to compute Output here.      return Output; } 

Почему здесь используется 32 контрольные точки в качестве входных данных и 16 в качестве выходных, а не 4 точки для обоих случаев?

Algorithm to simplify 2D convex hull at the cost of extra area

Are there any algorithms related to the following problem that could be usefull for solving it?

I have a convex hull built on some point set. I would like to simplify it (reduce number of points) by still keeping its perimiter (or area) as small as possible. New simplified polygon should not intersect the original hull.

The basic idea I am trying to implement is to calculate for each point of a polygon perimeter added by removal of this point. And then remove the cheapest point (which removal adds minimum value to the perimiter).

So we keep iterating and removing points while added perimiter or area value is suitable and passes some creteria.

Here comes the problem:

When removing point p1 we introduce a new edge formed by previous point p0 and the next point p2. This new edge can be non-optimal or invalid (intersecting the original hull). So I would like to adjust points p0 and p2 along their edges to keep perimeter valid and small as possible.

How can I find these adjusted positions of p0 and p2 ?

3D gift wrapping algorithm: how to find the first face in the convex hull?

I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space.

However, all the articles I have read seem to omit the description of the first step of the algorithm; namely, finding a face (that is, a triangle) in the set that will definitely be in the convex hull (and doing so in $ O(n^2)$ ).

Example of such an article:

I do understand how to find a vertex that definitely be in the convex hull: just take one with extreme coordinates. However, I don’t know how to approach the problem for edges or faces.