A sweep and translate algorithm for computing voxelized 3D Minkowski sums on the GPU
Computer-Aided Design 46(2014)
90–100
Contents lists available at ScienceDirect
Computer-Aided Design
journal homepage:
https://www.sodocs.net/doc/cc11032586.html,/locate/cad
A sweep and translate algorithm for computing voxelized 3D Minkowski sums on the GPU
Wei Li,Sara McMains ?
University of California,Berkeley,United States
h i g h l i g h t s
?Algorithm for computing voxelized Minkowski sum of two input polyhedra.?New decomposition formula for computing Minkowski sum,with proof.?Efficient GPU implementation using stencil shadow volumes.
a r t i c l e i n f o Keywords:
Minkowski sums GPU
Voxelization
Stencil shadow volume
a b s t r a c t
Computing the Minkowski sum of two arbitrary polyhedra in R 3is difficult because of high combinatorial complexity.We present an algorithm for directly computing a voxelization of the Minkowski sum of two closed watertight input polyhedra for applications such as path planning that do not require a boundary representation as output.We introduce a new decomposition formula for computing the Minkowski sum and prove its correctness.We describe an efficient Graphics Processing Unit (GPU)implementation of the algorithm using stencil shadow volumes to create a solid voxelization of the Minkowski sum.
?2013Elsevier Ltd.All rights reserved.
1.Introduction
Minkowski sums are a fundamental operation for many applica-tions in Computer-Aided Design and Manufacturing,such as solid modeling (offsetting and sweeping),collision detection,toolpath planning,assembly/disassembly planning,and penetration depth computation.Despite the simplicity of its mathematical definition,computing the Minkowski sum of two arbitrary polyhedra in R 3is generally difficult because of its high combinatorial complexity.In this paper,we present a new algorithm for directly computing a voxelization of the Minkowski sum of two closed watertight poly-hedra.This algorithm runs on the Graphics Processing Unit (GPU)and directly creates a voxelization without having to compute a boundary representation (B-rep).1.1.Definitions and properties
The Minkowski sum of two point sets A and B in R n is defined as
A ⊕
B ={a +b |a ∈A ,b ∈B }
(1)
where a and b denote the coordinate vectors of arbitrary points in A and B ,and +denotes vector addition.In this paper we will not
?
Corresponding author.
E-mail address:mcmains@https://www.sodocs.net/doc/cc11032586.html, (S.McMains).
distinguish between points and vectors;i.e.,a point will also repre-sent the vector pointing from the origin to itself.Unless otherwise specified,we will use lower case letters for points and upper case for sets of points.
From the above Minkowski sum definition,and the commuta-tivity and associativity of vector addition,the following two prop-erties (commutativity and associativity)of Minkowski sums hold:A ⊕B =B ⊕A ,
(2)(A ⊕B )⊕C =A ⊕(B ⊕C ).
(3)
The translation of a point set A by a vector d ,denoted as A d ,can be represented as the Minkowski sum of point set A and another point set that contains only point d ;i.e.,A d =A ⊕{d }.
(4)
For simplicity,we will denote A ⊕{d }as either A +d or A d .
The shape of a Minkowski sum is translation invariant.If we translate one of the input models by a specific vector d ,the Minkowski sum will also translate by the same vector,or math-ematically,
A d ⊕
B =A ⊕B d =(A ⊕B )d .
(5)
Another equivalent definition of Minkowski sums using the concept of translation is A ⊕B =
a ∈A
B a =
b ∈B
A b .
(6)
0010-4485/$–see front matter ?2013Elsevier Ltd.All rights reserved.https://www.sodocs.net/doc/cc11032586.html,/10.1016/j.cad.2013.08.021
W.Li,S.McMains /Computer-Aided Design 46(2014)90–100
91
Fig.1.The 2D Minkowski sum of a square and a
triangle.
Fig.2.The 3D Minkowski sum of a cube and a
tetrahedron.
Fig.3.The 2D Minkowski sum of two non-convex geometries.
The equivalence of (1)and (6)can be shown as below:A ⊕B ={a +b |a ∈A ,b ∈B }
??A ⊕B ={a +B |a ∈A }
??A ⊕B =
a ∈A
B a .1.2.Boundary sweeping
Definition (6)implies a method often used to manually
construct and visualize Minkowski sums.If A and B represent poly-gons in R 2or polyhedra in R 3,A ⊕B can be generated by ‘‘sweep-ing’’A along the boundary of B and then taking the union of the sweep with B (or vice versa).Fig.1shows the 2D Minkowski sum of a square and a triangle generated by sweeping the triangle along the boundary of the square.A 3D example is shown in Fig.2,where the 3D Minkowski sum is generated by sweeping the tetrahedron over the six boundary faces of the cube.The two examples given in Figs.1and 2are simple convex models.When both input models become non-convex,their Minkowski sum can still be generated by sweeping one over the other,but the final shape will become more complex (Fig.3).In this paper,we develop the mathematics behind the ‘‘sweep-along-the-boundary’’behavior—we give both an accurate mathematical description and a strict proof.Based on this mathematical formulation,we then introduce a new formula that decomposes the Minkowski sum of two closed watertight ob-jects as the union of the Minkowski sum of their boundaries and a translation of each input object.Finally,for an efficient implemen-tation,we use a stencil shadow volume technique to voxelize the union and create a solid voxelization of the Minkowski sum.2.Background and previous work
We now discuss some commonly used approaches for Minkowski sum computation algorithms that can take non-convex polyhedra as inputs.Although the Minkowski sum of two convex polyhedra has complexity of O (mn )(here m and n denote the num-bers of triangles of each input polyhedron)and can be computed
very efficiently [1,2],the Minkowski sum of two non-convex poly-hedra can have complexity as high as O (m 3n 3)and becomes much more difficult to compute.Most algorithms for non-convex objects fall into two main categories:convex decomposition or convolu-tion.
2.1.Convex-decomposition based approaches
The basic idea of convex-decomposition based algorithms is decomposing the input non-convex polyhedra into convex pieces,computing all the pairwise Minkowski sums of these convex pieces,and then taking their union.It is based on the following property of Minkowski sums (distributivity):Proposition 1.(A ∪B )⊕C =(A ⊕C )∪(B ⊕C ).
Proof.
x ∈(A ∪B )⊕C
??x =y +c ,y ∈A ∪B ,c ∈C
??x =a +c or b +c ,a ∈A ,b ∈B ,c ∈C ??x ∈A ⊕C or x ∈B ⊕C .
Then (A ∪B )⊕C =(A ⊕C )∪(B ⊕C ).
There are three steps in convex-decomposition based ap-proaches:convex decomposition,computing the Minkowski sum of convex pieces,and union computation.While it is desirable to compute an optimal (minimum number of pieces)convex de-composition,this problem is known to be NP-hard [3].Several practical algorithms are known to compute a sub-optimal or ap-proximate convex decomposition [4–6].The second step is typ-ically performed using either the convex hull or Gaussian map approaches [1,2].The third step,computing the union of the inter-mediate Minkowski sum pieces,is usually time consuming since the number of pairwise Minkowski sum pieces has quadratic com-plexity (in the timings given in [7],the time used for computing the union dominates the whole algorithm).Given n polyhedral objects,their union can have combinatorial complexity of O (n 3)[8].
Based on the algorithms used for convex decomposition and union computation,convex-decomposition based approaches for Minkowski sum computation can be either exact or approximate.The exact algorithms allow robust implementation and are able to find low dimensional boundaries,i.e.,they are able to identify dangling faces or lines and singular points in the Minkowski sums [9–11].However,these algorithms are limited to relatively simple objects because of their performance.To compute the Minkowski sum of two polyhedra bounded by only hundreds of triangles,it usually takes tens of minutes [12].Varadhan and Manocha pro-posed another convex-decomposition based algorithm to compute an approximated boundary of Minkowski sums [7].Instead of com-puting the exact union of pairwise Minkowski sums,they compute a signed distance field and extract its zero iso-surface.Their algo-rithm provides geometrical and topological guarantees by using an adaptive subdivision algorithm.However,the performance of their algorithm is impacted by the large number of convex pieces after decomposition.The timing reported in their paper shows that com-puting the distance fields for tens of thousands of pairwise convex Minkowski sums usually takes 5–50min.2.2.Convolution-based approaches
Convolution-based approaches have also been proposed for computing the boundary of Minkowski https://www.sodocs.net/doc/cc11032586.html,ually they start with a set of surface primitives that is a superset of the Minkowski sum boundary.These surface primitives are then trimmed and filtered to form the final boundary.
92W.Li,S.McMains/Computer-Aided Design46(2014)
90–100
Fig.4.Convolution of two smooth curves.(a)Two smooth curves(in black)and their convolution(in red)as defined in Eq.(7).(b)The boundary(in red)of the Minkowski sum of the two shapes as indicated in the left side of Eq.(8).(c)The Minkowski sum(in red)of the two curves as indicated in the rightmost side of Eq.(8).(For interpretation of the references to colour in this figure legend,the reader is referred to the web version of this article.)
For objects with smooth boundary surfaces,their convolution
is well defined.If we denote the convolution of two surfaces as?,
then the convolution of two smooth boundary surfaces?A and?B
is defined as
?A??B={a+b|a∈?A,b∈?B,n a=n b},(7)
where n a denotes the unit outward normal at point a.A2D exam-
ple of the convolution of two smooth curves is shown in Fig.4.Note
that the convolution in this context is different from its usual defi-
nition of‘‘convolving two functions’’.For two objects the convo-
lution of their boundaries is a superset of the boundary of their
Minkowski sum and also a subset of the Minkowski sum of their
boundaries[13,14];i.e.,
?(A⊕B)??A??B??A⊕?B.(8)
If both objects are convex,it is easy to show that?A??B=
?(A⊕B)[1].If at least one of them is non-convex,the convolu-
tion may become self-intersecting(see Fig.4for an example),and
the Minkowski sum boundary can be extracted by trimming and
filtering the convolution surfaces.
Polyhedra do not have smooth boundary surfaces,and the out-
ward normals at their vertices and edges are not well defined.The
definition of convolution for polyhedra is much more complicated,
especially for non-convex polyhedra.In the work by Ghosh[1],the
convolution of two polyhedra is defined using the concept of Gaus-
sian maps(called‘‘slope diagrams’’),and for non-convex input,
an additional concept called‘‘negative objects’’.In that definition,
the convolution of two polyhedra can be seen as an extension of
Eq.(7),which defines the convolution of smooth boundary sur-
faces,where n a and n b are replaced with the corresponding fea-
tures(a single point,a geodesic arc,or a patch,depending on the
position of a or b on the boundary)to which points a and b are
mapped to on the Gaussian sphere,and then instead of checking
whether the two outward normals are the same,the intersection
of the two features is checked.
Computing the exact convolution of two polyhedra(which is
the superset of the boundary of their Minkowski sum)is diffi-
cult itself since it involves3D arrangements and Boolean opera-
https://www.sodocs.net/doc/cc11032586.html,ually people compute the exact convolution only if both
input models have smooth boundaries and if explicit parameteri-
zation of both boundaries exists[13,14].Many convolution-based
approaches for polyhedra just start with?A⊕?B as the convo-
lution[15,16],and then filter and trim its surface primitives to
extract the final Minkowski sum boundary.The filtering and trim-
ming operations may become very complex since the number of
generated surface primitives has quadratic complexity and they
may intersect each other arbitrarily in3D space.The algorithm pro-
posed in our previous work[17]uses this basic approach.
Below we briefly discuss some existing convolution-based al-
gorithms.Guibas and Seidel presented an output sensitive algo-
rithm for computing the convolution of2D curves[18].Kaul and
Rossignac introduced a set of criteria to cull out facets that are
not part of the Minkowski sum boundary[16].These criteria were
used later in other works[19,15,20,17].Peternell and Steiner stud-
ied how to extract the Minkowski sum boundary from the con-
volution of two objects with piecewise smooth boundaries[14].
As discussed in the previous paragraph,Lien started with a brute
force convolution,which is simply defined as?A⊕?B,and then
computed facet–facet intersections as2D arrangements on each
facet[15].Then he introduced the novel idea of using collision de-
tection tests to merge and filter cells from2D arrangements.Un-
fortunately the2D arrangements and collision detection become
both time and memory consuming when the size and complexity
of the input models increase.
2.3.Other approaches
To overcome the computational complexity introduced by3D
operations,some approaches seek to use other lower dimensional
representations.Voelcker and his group suggested using‘‘ray
representations’’(ray-reps)to reduce3D Minkowski sum compu-
tation to1D Boolean operations[21,22],but no practical imple-
mentation of this algorithm is known.Lien proposed a point-based
approach that creates a point set covering the Minkowski sum
boundary[19].This approach starts with a set of points both on
and inside the Minkowski sum boundary.Several filters,includ-
ing the ones introduced in[16],are used to cull out points that
are not on the boundary to generate the final point set.The main
drawback of this approach is that its result includes no information
of the interior of the Minkowski sum.Kavraki proposed voxeliz-
ing both input models,then converting the Minkowski sum to the
convolution(the usual mathematical convolution,not the convo-
lution of two surfaces mentioned in the previous section)of two3D
arrays representing the voxels,and finally computing the convolu-
tion using a fast Fourier transform(FFT)[23].The main drawback
of this approach is the low resolution(1283or2563)used for the
voxelization due to memory limitations[24,25],since each voxel
needs to be represented as a floating point number(it would re-
quire512×512×512×4=512MB if a floating point number
uses4bytes).
Some algorithms have also been introduced for handling spe-
cific types of objects.Seong et al.presented an algorithm for com-
puting Minkowski sums of surfaces generated by slope-monotone
closed curves[26].Mühlthaler and Pottmann introduced an ex-
plicit parameterization of the convolution of two ruled sur-
faces[13],which was defined in Eq.(7).Barki et al.proposed an
approach for computing the Minkowski sum of a convex polyhe-
dron and a non-convex polyhedron whose boundary is completely
recoverable from three orthogonal projections[27].Other authors
have introduced fast algorithms for the special case of rotating con-
vex polyhedra by tracking the changes to the topology of the ar-
rangement on the Gaussian sphere[28–30].
2.4.Voxelization approaches
Most existing algorithms,as discussed above,compute either an
exact[11,2,10,31]or an approximated[14,7]boundary representa-
tion(B-rep)of the Minkowski sum.A B-rep is convenient for ren-
dering and visualization due to its explicit representation of surface
boundaries,but it cannot be directly applied to many applications
where we are more interested in the interior of the Minkowski
sum instead of its boundary.In motion planning,even if we have
W.Li,S.McMains/Computer-Aided Design46(2014)90–10093 computed a B-rep based configuration-space,it usually needs to
be sampled in order to construct a connectivity roadmap[32,33]. In collision detection and assembly/disassembly,we need to deter-mine whether a point is inside or outside of the Minkowski sum, which usually requires a parity check for B-reps.If we consider higher dimensional Minkowski sums(e.g.,3D motion planning involving both translation and rotation requires computing and representing6D Minkowski sums),a B-rep is not an appropriate representation any more.
To overcome the shortcomings of B-rep based Minkowski sums, our algorithm described in[17]considers using a GPU-based algo-rithm to compute a voxelized representation as an alternative to the traditional B-rep.A voxelized representation provides a uni-form and simple description for objects and can be easily extended to higher dimensions.The voxelized representation of Minkowski sums is more advantageous in applications where a B-rep would need to be sampled or point membership classification(determin-ing whether a point is inside a B-rep solid or not)would need to be performed.It provides sample points used to build the connectivity roadmap in motion planning with no need of further computation, and also provides immediate collision feedback by simply check-ing if a certain voxel is set to one or zero.However,the algorithm proposed in[17]cannot compute holes in Minkowski sums.
3.Mathematical formulation
As explained in Section1.2,to manually draw the Minkowski sum of two simple shapes,one usually sweeps one shape along the boundary of the other.(In fact this method works for complex3D objects too,but it is easier to perform manually for simple shapes.) Such an example is shown in Fig.5(a).Here we sweep the yellow triangle along the boundary of the green rectangle.Some subtleties of this common approach include:
–A reference point needs to be specified for B.This reference point is placed on and swept along the boundary of A.Theo-retically this point can be chosen arbitrarily.One usually uses a point on the boundary of B for convenience.In Fig.5(a),we use point r as the reference point.
–Before B is swept,A needs to be translated by the vector defined by the reference point of https://www.sodocs.net/doc/cc11032586.html,ually one simply sweeps B along the boundary of A without translating A,just because the ori-gin is taken as the reference point.If the reference point is not the origin,a translation of A is necessary.In Fig.5(a),the green square is translated by vector r.
–Just sweeping B along the boundary of A does not necessar-ily cover the whole Minkowski sum A⊕B.In the example in Fig.5(b),an empty rectangle inside the Minkowski sum is not covered by the sweep.This empty rectangle will be covered by
A after it is translated by vector r if r is chosen to be a point of B
(either on the boundary or in the interior),as one normally does.
(An analogous case for the swept volume of a compact man-ifold sweeping along a one-parameter trajectory was proved in[34].)
Mathematically‘‘sweeping B along the boundary of A’’is repre-sented by B⊕?A.To cover the empty area that is not covered by the sweep,we need a translation of A.A key observation is that as long as A is translated by a vector defined by any point of B,it will cover the empty area(see Fig.5(c)).We summarize this observa-tion in the proposition below and also give a strict proof.A simi-lar proposition was introduced in the technical report by Menon and Voelcker[21],though the origin was assumed to be inside of B(or translated before and after).In our proposition below,we do not put any restriction on the origin and give a more concise
proof.Fig.5.Minkowski sum A⊕B by sweeping B along the boundary of A.(a)Sweep B along the boundary of A.(b)An empty area inside the Minkowski sum is not swept by B.(c)Translation of A by any vector in B covers the empty area.(For interpretation of the references to colour in this figure legend,the reader is referred to the web version of this article.)
Proposition2.Suppose A and B are two singly connected watertight objects,and p b is an arbitrary point of B(either on the boundary or in the interior).Then
A⊕B=(B⊕?A)∪(A+p b).
Proof.Let C denote(B⊕?A)∪(A+p b),?p b∈B.By definition, B⊕?A?A⊕B and A+p b?A⊕B.Therefore C?A⊕B.We only need to prove that A⊕B?C;i.e.,?c∈A⊕B,we need to show that c∈C.
For any c∈A⊕B there must exist points a and b,a∈A and b∈B,such that c=a+b.If a∈?A,then c∈B⊕?A?C.If a∈?A, then a must lie in the interior of A.Now we consider?B+(a+b)(B is reflected around the origin and then translated by vector a+b). After this transformation,point b will coincide with point a(since ?b+(a+b)=a).Note that b can be either on the boundary or in the interior of B.Now consider the intersection between the boundaries of A and?B+(a+b).Since A and?B+(a+b)share at least one common point a,and a is in the interior of A,either these two boundaries intersect each other,or one of them completely contains the other,for a total of three different cases to consider (see Fig.6).
?Case(1):?(?B+(a+b))and?A intersect.Suppose a′is the intersection,a′∈?A and a′∈?(?B+(a+b)).Since a′∈?(?B+(a+b)),?b′∈B such that a′=?b′+a+b.Then c=a+b=(a+b?b′)+b′=a′+b′∈?A⊕B?C.
?Case(2):?B+(a+b)?A.Then?p
b
∈B,?p
b
+a+b∈A?
?p
b
+c∈A?c∈A+p
b
?C.
?Case(3):A??B+(a+b).Then?p
a
∈?A?A,p
a
∈
?B+(a+b)?p
a
∈?B+c??p
a
∈B+(?c)?c?p
a
∈B?c∈B+p a?B⊕?A?C.
Thus for all the three cases,we have c∈C.This proves A⊕B?C.Thus A⊕B=C.
Proposition2mathematically expresses the‘‘sweep-along-the-boundary’’method used to generate Minkowski sums.In fact,as suggested by our proof above,we find that the proposition can be further extended.In case(1),b′must be on the boundary of B;in case(3),p a can be any point of A,not just a point on the boundary of
A.Another reason the proposition might be extended is that A and
B are symmetric in the expression A⊕B(i.e.,they can be swapped
94W.Li,S.McMains /Computer-Aided Design 46(2014)
90–100
Fig.6.Proof of Propositions 2and 3.
without causing any change),but they are not in the expression (B ⊕?A )∪(A +p b ).
The extended proposition is given below.It shows that the Minkowski sum of two singly connected watertight objects can be decomposed as the union of the Minkowski sum of their bound-aries and a copy of each object translated by a vector defined by any point of the other object.Its proof is very similar to the one for Proposition 2.To the best of our knowledge,this is the first math-ematical formulation and explanation of the relationship between the Minkowski sum of two objects and the Minkowski sum of their boundaries.
Proposition 3.Suppose A and B are two singly connected watertight objects,and p a and p b are two arbitrary points of A and B respectively (either on the boundary or in the interior).Then A ⊕B =(?A ⊕?B )∪(A +p b )∪(B +p a ).
Proof.Let C denote (?A ⊕?B )∪(A +p b )∪(B +p a ),?p a ∈A and ?p b ∈B .By definition,?A ⊕?B ?A ⊕B ,A +p b ?A ⊕B ,and B +p a ?A ⊕B .Then C ?A ⊕B .We only need to prove that A ⊕B ?C ;i.e.,?c ∈A ⊕B ,we need to show that c ∈C .
For any c ∈A ⊕B there must exist points a and b ,a ∈A and b ∈B ,such that c =a +b .If a ∈?A and b ∈?B ,we have c ∈?A ⊕?B ?C .Otherwise,either a ∈?A or b ∈?B .Without loss of generality we assume that a ∈?A .Then a must lie in the interior of A .Now we consider ?B +(a +b )(B is reflected around the origin and then translated by vector a +b ).After this transformation,point b will coincide with point a (since ?b +(a +b )=a ).Note that b can be either on the boundary or in the interior of B .Now consider the intersection between the boundaries of A and ?B +(a +b ).Since A and ?B +(a +b )share at least one common point a and a is in the interior of A ,either these two boundaries intersect each other,or one of them completely contains the other,for a total of three different cases to consider (see Fig.6
).
Fig.7.Minkowski sum of two triangles in 3D space.
?Case (1):?(?B +(a +b ))and ?A intersect.Suppose a ′is the intersection,a ′∈?A and a ′∈?(?B +(a +b )).Since a ′∈?(?B +(a +b )),?b ′∈?B such that a ′=?b ′+a +b .Then c =a +b =(a +b ?b ′)+b ′=a ′+b ′∈?A ⊕?B ?C .
?Case (2):?B +(a +b )?A .Then ?p b ∈B ,?p b +a +b ∈A ??p b +c ∈A ?c ∈A +p b ?C .
?Case (3):A ??B +(a +b ).Then ?p a ∈A ,p a ∈?B +(a +b )?p a ∈?B +c ??p a ∈B +(?c )?c ?p a ∈B ?c ∈B +p a ?
C .
Thus for all the three cases,we have c ∈C .This proves A ⊕B ?C .Thus A ⊕B =C .
Propositions 2and 3apply to any singly connected watertight object.Note that for a degenerate object that has zero volume (such as a surface,a line,or a point embedded in 3D space),its boundary is the same as the object itself.If both input models are triangulated polyhedra,their boundaries are the sets of their boundary trian-gles.Proposition 3can then be rewritten as the corollary below.Corollary 1.Suppose A and B are two triangulated polyhedra (singly connected and watertight),F A and F B are the sets of their respective boundary triangles (faces),and p a and p b are two arbitrary points of A and B respectively (either on the boundary or in the interior),then we have
A ⊕
B =(F A ⊕F B )∪(A +p b )∪(B +p a ).
To compute F A ⊕F B ,we need to compute the Minkowski sum of two triangles in 3D space.Generally the Minkowski sum of two triangles in 3D (Fig.7)is a polyhedron with 9boundary faces (4tri-angles and 5quadrilaterals).These boundary faces are determined by the relative position of the two triangles in 3D space.To further simplify the computation,we use the proposition below to reduce the Minkowski sum of two triangles to the union of Minkowski sums of triangles and edges,which are simply triangular prisms.Proposition 4.Suppose A and B are two triangles in 3D space,and E A and E B are the sets of their respective boundary edges,then A ⊕B =(A ⊕E B )∪(B ⊕E A ).
Proof.Let C denote (A ⊕E B )∪(B ⊕E A ).By definition,A ⊕E B ?A ⊕B and B ⊕E A ?A ⊕B ,so C ?A ⊕B .It remains only to prove that A ⊕B ?C .
If the two planes containing A and B respectively are not parallel,call their intersection line L (see Fig.8).If the two planes are parallel,take any line parallel to them as L .For any c ∈A ⊕B there must exist points a and b ,a ∈A and b ∈B ,such that c =a +b .If at least one of a and b is on an edge of the two triangles,we have c ∈A ⊕E B ?C or c ∈B ⊕E A ?C .Otherwise,both a and b are in the interior of the triangles;call the intersections of the line,passing through a (respectively,b )and parallel to L ,with the edges of A (respectively,B )a 1and a 2(respectively,b 1and b 2).We compare the lengths of the four line segments aa 1,aa 2,bb 1,and bb 2.Without loss of generality,suppose aa 1has the smallest length out of the four,then b +a ?a 1∈B .This gives us c =a +b
W.Li,S.McMains /Computer-Aided Design 46(2014)90–100
95
Fig.8.Reference for proof of Proposition 4.
=(b +a ?a 1)+a 1∈B ⊕E A ?C .Note that the above reasoning
still holds if all four line segments have the same length or if A and B intersect.
Therefore we have ?c ∈A ⊕B ,c ∈C ;i.e.,A ⊕B ?C .
Based on Corollary 1and Proposition 4,we can decompose the Minkowski sum of two polyhedra as the union of a series of prisms and a translation of both input polyhedra,as shown in the proposition below.
Proposition 5.Suppose A and B are two triangulated polyhedra,F A and F B are the sets of their respective boundary triangles,E A and E B are the sets of their respective edges,and p a and p b are two arbitrary points of A and B respectively (either on the boundary or in the interior),then
A ⊕
B =(F A ⊕E B )∪(F B ⊕E A )∪(A +p b )∪(B +p a ).
Proof.For any triangle f A ∈F A and f B ∈F B ,suppose the edge sets of f A and f B are E f A and E f B respectively.From Proposition 4,f A ⊕f B = f A ⊕E f B ∪ f B ⊕E f A
.Then from Proposition 1(distributivity),we have
F A ⊕F B = ∪f A ∈F A {f A } ⊕ ∪f B ∈F B {f B }
=∪f A ∈F A ,f B ∈F B (f A ⊕f B )
=∪f A ∈F A ,f B ∈F B f A ⊕E f B ∪ f B ⊕E f A
= ∪f A ∈F A ,f B ∈F B f A ⊕E f B ∪ ∪f A ∈F A ,f B ∈F B f B ⊕E f A
= ∪f A ∈F A {f A } ⊕ ∪f B ∈F B E f B
∪ ∪f B ∈F B {f B } ⊕ ∪f A ∈F A E f A =(F A ⊕E B )∪(F B ⊕E A ).
Now applying Corollary 1,
A ⊕
B =(F A ⊕F B )∪(A +p b )∪(B +p a )
=(F A ⊕E B )∪(F B ⊕E A )∪(A +p b )∪(B +p a ).
From Proposition 5,we know that the Minkowski sum of two polyhedra can be decomposed as the union of the following four components:
–F A ⊕E B ,which is a series of prisms formed by sweeping each triangle of A along each edge of B ;
–F B ⊕E A ,which is a series of prisms formed by sweeping each triangle of B along each edge of A ;
–A +p b ,which is a translation of A by a vector defined by any point of B ;
–B +p a ,which is a translation of B by a vector defined by any point of A .Each one of these four components can be computed easily.To compute Minkowski sums using Proposition 5,we need to find a way to compute their union efficiently,which will be described in the next
section.
Fig.9.Conservative (a)and non-conservative (b)voxelization.
4.Voxelization using stencil shadow volumes
Suppose object A has |F A |triangles and |E A |edges,and object B has |F B |triangles and |E B |edges,then in total we have |F A |·|E B |+|F B |·|E A |prisms for (F A ⊕E B )∪(F B ⊕E A ).Including the two translated objects A +p b and B +p a ,we need to compute the union of |F A |·|E B |+|F B |·|E A |+2polyhedral objects in order to compute A ⊕B using Proposition 5.The combinatorial complexity of the union can be as high as O (|F A |·|E B |+|F B |·|E A |+2)3[8],which is of the same magnitude as the worst-case complexity O (|F A |3|F B |3)of the Minkowski sum A ⊕B .Even if both A and B have just thousands of triangles,the union consists of millions of objects,and in the worst case its number of facets can be on the order of https://www.sodocs.net/doc/cc11032586.html,puting an exact union of such a large number of polyhedra is not practical.Exact boundary evaluation of a union of this size is slow and prone to robustness problems.
Instead of computing the union exactly,we propose approxi-mating it by using GPU-based voxelization techniques.In a vox-elized representation,each object is represented by a 3D grid M ij (1≤i ,j ≤n ,where n is the resolution)that corresponds to the 3D space occupied by a bounding box enclosing the object.Each voxel M ij is set to either 1or 0according to whether it is located inside or outside of the object.In a conservative voxelization [35],as long as the voxel intersects with the object,it is set to 1(Fig.9(a));in other voxelizations,the center of the voxel is used as a represen-tative point to determine whether the voxel is inside or outside of the object (Fig.9(b)),which is also the behavior of standard raster-ization algorithms required by 3D graphics APIs such as OpenGL and Direct3D.In our approach for voxelizing Minkowski sums,we follow the latter convention.
Voxelization algorithms can be classified into surface voxeliza-tion (only the boundary is voxelized)and solid voxelization (the whole interior is voxelized).A surface voxelization can be created from a solid voxelization by simply checking if a voxel has any outside neighbors,as in [17].A solid voxelization can also be cre-ated from a surface voxelization by using the parity check rule (ex-plained below),if a single watertight object is being voxelized [36].In the current work we directly create a solid voxelization for the Minkowski sum,since our goal is to avoid the computational complexity involved in evaluating the complete boundary of the Minkowski sum.
Most solid voxelization algorithms are based on parity checking and work for a single watertight object [36–40].The parity check is based on the principal that a ray shooting from a point inside (or outside)the object will have an odd (or even)number of intersections with the object boundary respectively,as shown in Fig.10(a).To perform the parity check using OpenGL,we can set the near clipping plane to the current slice (here we define a slice as the intersection of the object with a plane;the parity check for all the pixels on the same slice will be performed together)and the far clipping plane to be infinity,and then render the object.Only the portion of the object that is between the near and far clipping planes is rendered.The parity flag for each pixel is initialized to be zero.Then it is toggled between one and zero for each rendered fragment at its position (these fragments can be processed in
96W.Li,S.McMains /Computer-Aided Design 46(2014)
90–100
Fig.10.(a)Parity check for a point outside the object and a point inside the object.(b)The parity check does not work for the union of several watertight
objects.
Fig.11.The stencil shadow volume technique.The stencil value is increased for back faces and decreased for front faces.
arbitrary order).After the rendering is complete,any pixel inside the object will have a flag of one,and any pixel outside will have a flag of zero.Flag toggling can be implemented using either XOR operations with the color buffer or GL_INVERT operations with the stencil buffer.
The parity check,however,does not work for the union of watertight objects.As shown in Fig.10(b),to voxelize the union of a rectangle and a triangle,the parity flag of the indicated point is zero after rendering,but in fact it is inside the union.We need a slightly more complex check to correctly classify inside and outside voxels for the union of objects.
The technique used in stencil shadow volumes [41,42]has been applied to solid voxelization of individual watertight objects as well as their union [43,44].It strengthens the above parity check by taking into consideration the orientation of boundary surfaces.Instead of simply toggling the flag between one and zero for each rendered fragment,they increase it by one for back faces and de-crease it by one for front faces,as shown in Fig.11.After the rendering is complete,any pixel inside the union will have a non-zero stencil value,while any pixel outside the union will have a zero stencil value.The increments and decrements can be imple-mented using the two-sided stencil test provided by OpenGL ex-tension GL_EXT_stencil_two_side.Note that the increments and decrements are performed with wrapping enabled to avoid satura-tion (otherwise the stencil value will be clamped at the maximum value and zero);thus for an 8-bit stencil buffer,increasing 255by one will return 0and decreasing 0by one will return 255.
The final voxelization is stored in a 3D texture,where a 3D texture of size X ×Y ×Z can be seen as Z images of size X ×Y stacked together,each one of which can be independently set as the draw buffer to store the color of currently rendered pixels.Each image is a 2D array of texels (texture elements),and each texel has four color channels (RGBA),with each color channel using eight bits.Thus each image has 32slices,with each bit representing the plane of a specific slice.Each voxel is represented by a single bit,thus for a voxelization with a resolution of 512×512×512,the
3D texture should have a size of 512×512×16(16=512/32),which uses only 16MB of video memory.
We map bits of the 3D texture to the voxels of the voxelization using color encoding [37].Suppose the resolution of the voxeliza-tion is N ×N ×N ,the index of a voxel is (x v ,y v ,z v )(ranging from 0to N ?1),and it corresponds to the n bit bit of the texel with index (x t ,y t ,z t )in the 3D texture.Then the following relationships hold:x t =x v y t =y v z t =?z v /32?n bit =z v ?32z t .
(9)
Fig.12shows a 2D example of color encoding.For the purpose of illustration,we assume each texel has a bit depth of eight,though in reality it is 32.
5.Algorithm and implementation
The overall algorithm for computing a solid voxelization of A ⊕B for closed watertight objects A and B is given in Algorithm 1and explained below.Suppose the resolution of voxelization is N ×N ×N .We first need to create a 3D texture of size N ×N ×(N /32)with a bit depth of 32.We also create a framebuffer object and a stencil buffer,and attach the stencil buffer to the framebuffer object.Next we create a display list for all the triangular prisms and two translated objects according to Proposition 5.The bounding box of the Minkowski sum,which can be computed easily by adding up the minimum and maximum points of the two input models along the x ,y ,and z directions,is divided into N slices along the z direction.
Now we perform the voxelization slice by slice.For each slice,we first need to set the near clipping plane at the current slice and the far clipping plane slightly beyond the maximum z of the bounding box.We also need to set the two-sided stencil operation to be increasing for back faces and decreasing for front faces.We disable the draw buffer for now since we do not need to render the display list to a color buffer;instead we only need to fill the stencil buffer.Now we call the display list to render the prisms and the two translated objects.Note that only the portion between the near and far clipping planes is rendered.After rendering,the stencil buffer is filled with zeros and non-zeros,indicating whether the corresponding voxel is outside or inside the Minkowski sum.
Now we can use the stencil buffer to find corresponding bits in the 3D texture.To do this,we first need to attach the current image of the 3D texture (we have N /32images in total,and each image corresponds to 32slices)as the draw buffer.If it is the i th slice (0≤i ≤N ?1),we attach the ?i /32?th image,so we only need to change the attached image every 32slices.We also need to compute an RGBA color in which only the bit corresponding to the current slice is set to one and all the other bits are zeros.
W.Li,S.McMains/Computer-Aided Design46(2014)90–100
97 Fig.12.Color encoding of the voxels(2D illustration).(a)The voxels of a solid voxelization.(b)The corresponding texture(each texel has a bit depth of eight,two for each color channel).It includes two images(16slices).The colored bits are set to1and the others are0.
In fact we create a table in advance that includes all the32pos-sible RGBA color values(0x00000001,0x00000002,0x00000004, 0x00000008,0x00000010,...,0x40000000,and0x80000000), and look up the correct color value in the table instead of com-puting it on the CPU.For the i th slice,we use the(i?32?i/32?)th color value in the table.The logical pixel operation is set to OR to avoid overwriting previously computed bits.Since we only need to write to the pixels whose stencil value is non-zero,we set the stencil test to pass if the stencil value is non-zero.Now we render a quadrilateral that is slightly larger than the xy projection of the bounding box to set the bits on the current slice.
We repeat this process for all the slices.Finally the3D texture will contain all the information of the solid voxelization. Algorithm1Compute a solid voxelization of resolution N×N×N for A⊕B
1:Create a3D texture,a stencil buffer,and a framebuffer object. 2:Create a display list of all the triangular prisms and the two translated objects.
3:for each slice do
4:Set up the view frustum.
5:Set up the two-sided stencil operation.
6:Disable the draw buffer.
7:Call the display list to render to the stencil buffer.
8:Attach the corresponding image of the3D texture as the draw buffer.
9:Compute the RGBA color corresponding to the current slice. 10:Set the logical pixel operation to OR.
11:Set the stencil test such that it passes if the stencil value is not zero.
12:Render a quadrilateral with the computed color.
13:end for
14:return the3D texture.
The main drawback of the above algorithm is the large number of prisms to be rendered.If both A and B have thousands of trian-gles,there will be millions of prisms.However,we can show that we do not need to render all the prisms for each slice.If a prism does not intersect with the current slice,it is either entirely be-tween the near and far clipping planes(prism C in Fig.13),which does not change the final stencil value,or entirely in front of the near clipping plane(prism B in Fig.13),which is not rendered at all.Therefore for each slice,instead of rendering all the prisms,we only need to render those prisms with which the current slice in-tersects.Especially for complex polyhedra generated by tessellat-ing smooth models,their boundary triangles are usually very small. The prisms formed by these triangles are therefore small compared to the Minkowski sum,and they usually intersect with only a small number of slices.Then by first computing a list of prisms intersect-ing with each slice,we can reduce the number of prisms rendered for each slice and therefore the time needed for rendering.It is straightforward to check whether a prism intersects with a slice
or Fig.13.A prism only needs to be rendered for the slices that it intersects with.For the current slice,prisms B and C do not need to be
rendered.
Fig.14.Slices are grouped into layers.In this example,layer0includes slices 0–3,and layer1includes slices4–7.The intersecting prisms for layer0are {A,B,C,D,E,G},and for layer1are{E,F,G,H,I}.
not—since the slice is perpendicular with the z axis,we just need to check whether its z value is between the minimum and maximum z coordinates of the prism.
On the other hand,finding intersecting prisms for each slice also incurs some overhead.If we use just a single display list for all the slices,we only need to create and evaluate(i.e.,process the input draw commands to generate final pixel information)the display list once,and then reuse it repeatedly without re-evaluating the data over and over again.But if we render different sets of prisms for each slice,we lose the benefits from using a display list;i.e.,we have to re-evaluate the data for each slice.
Therefore as a tradeoff,we group all the slices into several layers,each layer including a fixed number of slices.For each layer we compute a list of prisms intersecting with it,as shown in Fig.14. We render the same list of prisms for all the slices in one layer,so they can reuse a single display list.
Two factors need to be considered for choosing an appropri-ate value for the number of layers—the number and the size of display lists.If the number of layers is small,the generated dis-play lists for each layer will be large;if the number of layers is large,the display lists will have smaller sizes,but at the same time we need to create more display lists.To determine an opti-mal value for the number of layers,we compute the voxelization of two Minkowski sums,representing two different types of input,
98W.Li,S.McMains/Computer-Aided Design46(2014)
90–100
Fig.15.Running time for computing the voxelization of the Minkowski sum of the dragon(2328triangles)and the ball(500triangles)using different numbers of layers. Both resolutions of256×256×256and512×512×512are used for comparison.The Minkowski sum on the top row is rendered using resolution256×256×
256. Fig.16.Running time for computing the voxelization of the Minkowski sum of the grate1(540triangles)and the grate2(942triangles)using different numbers of layers. Both resolutions of256×256×256and512×512×512are used for comparison.The Minkowski sum on the top row is rendered using resolution256×256×256.
using varying numbers of layers and compare the running timing. The first example(dragon⊕ball,Fig.15)uses two polyhedra gen-erated by tessellating smooth models,and the second(grate1⊕grate2,Fig.16)uses two rectilinear models.The timings of both examples show that for both resolutions of256×256×256and 512×512×512,using16layers has the best https://www.sodocs.net/doc/cc11032586.html,-pared to using a single display list for all the slices(i.e.,the number of layers is one),using16layers has a3×to6×speedup.
W.Li,S.McMains/Computer-Aided Design46(2014)90–10099
Table1
Timings of the voxelization algorithm(in seconds).Two resolutions(512×512×512 and256×256×256)are used for testing.The timings reported by Lien in[15]are
6.Results and discussion
In this section,we present timings on additional models.The
test models we use come from Lien’s website[45]and were also
used in[15].The timing was performed on an NVIDIA Quadro6000
GPU with6GB video memory and an Intel Core2Quad CPU at
2.66GHz with4GB RAM.The program runs on CUDA driver
3.2
and64-bit Windows7.For all the tests we divide the slices into16
layers.
The timings of the voxelization algorithm are given in Table1.
We also include the timings reported by Lien[15]for comparison
(performed on two Intel Core2CPUs at2.13GHz with4GB RAM).
Note that Lien’s approach uses a convolution-based approach and
computes an exact boundary representation,while ours computes
an approximate voxelized representation of high resolution.
From Table1,we can see that the performance of our algorithm
is mainly dominated by the sizes(numbers of triangles)of the in-
put polyhedra,while the performance of Lien’s approach is deter-
mined by both the sizes and the shape complexity of the input
models.This is especially obvious for the‘‘grate1⊕grate2’’case, which is a worst case example for concave Minkowski sum compu-
tation with O(m3n3)faces[7].Even though the two input polyhedra do not have large numbers of triangles compared to the other ex-
amples,Lien’s approach takes318s to compute their Minkowski
sum boundary,while our approach needs just10s to compute a
512×512×512voxelization.A contrasting example is the‘‘clutch ⊕ball’’case.Since one of the input models is convex,Lien’s ap-proach can take advantage of the convexity so that it takes less than 3s to compute the Minkowski sum,but our algorithm takes around 20s to compute a256×256×256voxelization.
Overall,the performance of our algorithm does not improve sig-
nificantly on prior results,which has two explanations.The first
is that a large number of prisms need to be rendered even if the
input models have a moderate size(thousands of triangles).For
most of the examples given in Table1,we need to render mil-
lions of prisms.The other is that our algorithm does not consider
the specific shapes of the input models.If one of the input mod-
els is convex,its convexity can be used to simplify the compu-
tation of Minkowski sums[27,7,15],but it is not utilized in this
voxelization algorithm.(This explains why our algorithm takes
much longer than Lien’s to compute‘‘clutch⊕ball’’in Table1.) Another limitation of this approach,similar to several convolution-based algorithms[15,19,20],is that the input models must be closed watertight meshes,which is required by Proposition3.
An advantage of the voxelization algorithm described in this
paper is ease of implementation.It does not require the complex
3D Boolean operations that are usually involved in existing B-rep
based algorithms—the only necessary3D computation is comput-
ing the triangular prism formed by a triangle and an edge,which is
straightforward.Acknowledgments
We would like to thank NVIDIA for providing us with hardware, and the anonymous referees for their feedback.Test models are from Jyh-Ming Lien’s website[45];some are reconstructed using Tao Ju’s Polymender to eliminate nonmanifold features[46].The authors were supported in part by the National Science Foundation under CAREER Grant No.0547675,Grant No.0621198,and Grant No.1331352.
References
[1]Ghosh PijushK.A unified computational framework for Minkowski operations.
Computers&Graphics1993;17(4):357–78.
[2]Fogel Efi,Halperin Dan.Exact and efficient construction of Minkowski sums
of convex polyhedra with https://www.sodocs.net/doc/cc11032586.html,puter-Aided Design2007;39(11): 929–40.
[3]Chazelle BernardM.Convex decompositions of polyhedra.In:Proceedings of
the thirteenth annual ACM symposium on theory of computing,STOC’81, 1981,p.70–9.
[4]Chazelle Bernard,Dobkin DavidP,Shouraboura Nadia,Tal Ayellet.Strategies
for polyhedral surface decomposition:an experimental study.In:Proceedings of the eleventh annual symposium on computational geometry,SCG’95,1995, p.297–305.
[5]Ehmann StephenA,Lin MingC.Accurate and fast proximity queries between
polyhedra using convex surface https://www.sodocs.net/doc/cc11032586.html,puter Graphics Forum 2001;500–10.
[6]Lien Jyh-Ming,Amato NancyM.Approximate convex decomposition of
polyhedra.In:Proceedings of the2007ACM symposium on solid and physical modeling,SPM’07,2007,p.121–31.
[7]Varadhan Gokul,Manocha Dinesh.Accurate Minkowski sum approximation of
polyhedral models.Graphical Models2006;68(4):343–55.
[8]Aronov Boris,Sharir Micha,Tagansky Boaz.The union of convex polyhedra in
three dimensions.SIAM Journal on Computing1997;26:1670–88.
[9]CGAL.Cgal,Computational Geometry Algorithms Library,2013.http://www.
https://www.sodocs.net/doc/cc11032586.html,.
[10]Halperin Dan.Robust geometric computing in motion.International Journal of
Robotics Research2002;21(3):219–32.
[11]Hachenberger Peter.Exact Minkowski sums of polyhedra and exact and
efficient decomposition of polyhedra into convex pieces.Algorithmica2009;
55(2):329–45.
[12]Hachenberger Peter.Cgal,Computational Geometry Algorithms Library,3D
Minkowski Sum of Polyhedra,2013.https://www.sodocs.net/doc/cc11032586.html,/Manual/latest/doc_ html/cgal_manual/Minkowski_sum_3/Chapter_main.html.
[13]Mühlthaler Heidrun,Pottmann https://www.sodocs.net/doc/cc11032586.html,puting the Minkowski sum of
ruled surfaces.Graphical Models2003;65(6):369–84.
[14]Peternell Martin,Steiner Tibor.Minkowski sum boundary surfaces of3D-
objects.Graphical Models2007;69(3–4):180–90.
[15]Lien Jyh-Ming.A simple method for computing Minkowski sum boundary
in3D using collision detection.In:The8th international workshop on the algorithmic foundations of robotics,2008.
[16]Kaul Anil,Rossignac Jarek.Solid-interpolating deformations:construction and
animation of https://www.sodocs.net/doc/cc11032586.html,puters&Graphics1992;16(1):107–15.
[17]Li Wei,McMains Sara.A GPU-based voxelization approach to3D Minkowski
sum computation.In:Proceedings of the14th ACM symposium on solid and physical modeling,2010,p.31–40.
[18]Guibas L,Seidel https://www.sodocs.net/doc/cc11032586.html,puting convolutions by reciprocal search.In:SCG’86:
proceedings of the second annual symposium on computational geometry, 1986,p.90–9.
[19]Lien Jyh-Ming.Covering Minkowski sum boundary using points with
https://www.sodocs.net/doc/cc11032586.html,puter Aided Geometric Design2008;25(8):652–66.
[20]Liu Min,Liu Yu-Shen,Ramani https://www.sodocs.net/doc/cc11032586.html,puting global visibility maps for
regions on the boundaries of polyhedra using Minkowski https://www.sodocs.net/doc/cc11032586.html,puter-Aided Design2009;41(9):668–80.
[21]Menon JP,Voelcker HB.Set theoretic properties of ray representations and
Minkowski operations on solids.Technical report.The Sibley School of Mechanical Engineering,Cornell University;1993.April.
[22]Hartquist EugeneE,Menon Jai,Suresh Krishnan,Voelcker HerbertB,Zagajac Jo-
van.A computing strategy for applications involving offsets,sweeps,and Minkowski https://www.sodocs.net/doc/cc11032586.html,puter-Aided Design1999;31(3):175–83.
[23]Kavraki https://www.sodocs.net/doc/cc11032586.html,putation of configuration-space obstacles using the fast
Fourier transform.IEEE Transactions on Robotics and Automation1995;11(3): 408–13.
[24]Lysenko Mikola,Nelaturi Saigopal,Shapiro Vadim.Group morphology with
convolution algebras.In:Proceedings of the14th ACM symposium on solid and physical modeling,2010,p.11–22.
[25]Lysenko Mikola,Shapiro Vadim,Nelaturi Saigopal.Non-commutative mor-
phology:shapes,filters,and https://www.sodocs.net/doc/cc11032586.html,puter Aided Geometric Design 2011;28(8):497–522.
[26]Seong Joon-Kyung,Kim Myung-Soo,Sugihara Kokichi.The Minkowski sum
of two simple surfaces generated by slope-monotone closed curves.In: Proceedings of geometric modeling and processing—theory and applications, 2002,p.33.
100W.Li,S.McMains/Computer-Aided Design46(2014)90–100
[27]Barki Hichem,Denis Florence,Dupont Florent.Contributing vertices-based
Minkowski sum of a non-convex polyhedron without fold and a convex polyhedron.In:IEEE international conference on shape modeling and applications,2009,p.73–80.
[28]Lien Jyh-Ming.Minkowski sums of rotating convex polyhedra.In:Proceedings
of the twenty-fourth annual symposium on computational geometry,2008, p.228–9.
[29]Behar Evan,Lien Jyh-Ming.Dynamic Minkowski sum of convex shapes.In:
Proc.IEEE int.conf.robot.autom.,Shanghai,China,May2011.
[30]Mayer Naama,Fogel Efi,Halperin Dan.Fast and robust retrieval of Minkowski
sums of rotating convex polyhedra in3-space.In:Proceedings of the14th ACM symposium on solid and physical modeling,2010,p.1–10.
[31]Wein Ron.Exact and efficient construction of planar Minkowski sums using
the convolution method.In:ESA’06:proceedings of European symposium on algorithms,2006,p.829–40.
[32]Varadhan Gokul,Krishnan Shankar,Sriram TVN,Manocha Dinesh.A simple
algorithm for complete motion planning of translating polyhedral robots.
International Journal of Robotics Research2006;25(11):1049–70.
[33]Lien Jyh-Ming.Hybrid motion planning using Minkowski sums.In:Proceed-
ings of robotics:science and systems IV,Zurich,Switzerland,June2008. [34]Weld JohnD,Leu MingC.Geometric representation of swept volumes with
application to polyhedral objects.International Journal of Robotics Research 1990;9(5):105–17.
[35]Zhang Long,Chen Wei,Ebert DavidS,Peng Qunsheng.Conservative voxeliza-
tion.The Visual Computer2007;23(9):783–92.
[36]Fang Shiaofen,Chen Hongsheng.Hardware accelerated https://www.sodocs.net/doc/cc11032586.html,put-
ers and Graphics2000;24:433–42.[37]Dong Zhao,Chen Wei,Bao Hujun,Zhang Hongxin,Peng Qunsheng.Real-
time voxelization for complex polygonal models.In:PG’04:proceedings of computer graphics and applications,12th Pacific conference,2004,p.43–50.
[38]Eisemann Elmar,Décoret Xavier.Single-pass GPU solid voxelization for real-
time applications.In:GI’08:proceedings of graphics interface2008,2008, p.73–80.
[39]Heidelberger Bruno,Teschner Matthias,Gross MarkusH.Real-time volumetric
intersections of deforming objects.In:Vision modeling and visualization, 2003,p.461–8.
[40]Liao Duoduo.GPU-accelerated multi-valued solid voxelization by slice
functions in real time.In:Proceedings of the7th ACM SIGGRAPH international conference on virtual-reality continuum and its applications in industry,2008, p.18:1–18:6.
[41]Everitt Cass,Kilgard MarkJ.Practical and robust stenciled shadow volumes for
hardware-accelerated rendering.2002.https://www.sodocs.net/doc/cc11032586.html,/pdf/cs/0301002. [42]McGuire Morgan,Hughes JohnF,Egan Kevin,Kilgard Mark,Everitt Cass.Fast,
practical and robust shadows.Technical report.Austin,TX:NVIDIA Cor-poration;2003.November.https://www.sodocs.net/doc/cc11032586.html,/object/fast_shadow_ volumes.html.
[43]Llamas Ignacio.Real-time voxelization of triangle meshes on the GPU.In:
SIGGRAPH’07:SIGGRAPH sketches,2007,p.18.
[44]Liao Duoduo,Fang Shiaofen.Fast volumetric CSG modeling using standard
graphics system.In:Proceedings of the seventh ACM symposium on solid modeling and applications,2002,p.204–11.
[45]Lien Jyh-Ming.2013.https://www.sodocs.net/doc/cc11032586.html,/wiki/SimpleMsum.
[46]Ju Tao.Robust repair of polygonal models.ACM Transactions on Graphics
2004;23(3):888–95.