Partial and Approximate Symmetry Detection for 3D Geometry
Niloy J.Mitra Stanford University
Leonidas J.Guibas Stanford Universityiwaki
Mark Pauly ETH Z¨u rich
dundas
0.02
-0.02Figure 1:Symmetry detection on a sculpted model.From left to right:Original model,detected partial and approximate symmetries,
color-coded deviations from perfect symmetry as a fraction of the bounding box diagonal.
Abstract
“Symmetry is a complexity-reducing concept [...];ek it every-where.”-Alan J.Perlis
Many natural and man-made objects exhibit signi ficant symmetries or contain repeated substructures.This paper prents a new al-gorithm that process geometric models and ef ficiently discovers and extracts a compact reprentation of their Euclidean symme-tries.The symmetries can be partial,approximate,or both.The method is bad on matching simple local shape signatures in pairs and using the matches to accumulate evidence for symmetries in an appropriate transformation space.A clustering stage extracts potential signi ficant symmetries of the object,followed by a veri-fication step.Bad on a statistical sampling analysis,we provide theoretical guarantees on the success rate of our algorithm.The extracted symmetry graph reprentation captures important high-level information about the structure of a geometric model which in turn enables a large t of further processing operations,including shape compression,gmentation,con
sistent editing,symmetriza-tion,indexing for retrieval,etc.
CR Categories:I.3.5[Computer Graphics]:Computational Geometry and Object Modeling.
Keywords:geometric modeling,shape analysis,symmetry detec-tion,shape descriptor,sampling guarantees.
1Introduction
Symmetry is an esntial and ubiquitous concept in nature,science,and art.For example,in geometry,the Erlanger program of Felix Klein [1893]has fueled for over a century mathematicians’int
er-est in invariance under certain group actions as a key principle for
understanding geometric spaces.Numerous biological,physical,or man-made structures exhibit symmetries as a fundamental design principle or as an esntial aspect of their function.Whether by evolution or design,symmetry implies certain economies and ef fi-ciencies of structure that make it universally appealing.Symmetry also plays an important role in human visual perception and aes-thetics.Arguably much of the understanding of the world around us is bad on the perception and recognition of shared or repeated structures,and so is our n of beauty [Thompson 1961].In this paper we prent a novel method for detecting meaningful symmetries in digital 3D shapes.We understand symmetry as the invariance under a t of transformations —in our ca translation,rotation,re flection,and uniform scaling,the common generators of the Euclidean group.The figure below shows a 2D illustration.As can be en in this example,symmetries or congruences that are quite apparent to us can be approximate and occur at differ-ent scales.Our goal is to de fine an algorithm that extracts (partial)symmetries at all scales,including approximate or imperfect sym-metries of varying degree.This allows the ur to lect the subt of symmetries that are most meaningful for a speci fic application.Examples include scan registration and alignment,shape matching,gmentation and skeleton extraction,compression,advanced mod-eling and editing,and shape databa retrieval.
To achieve this goal,we parate the symmetry computation into two phas:In the first step,we compute simple local shape de-scriptors at a lected t of points on the shape.The descriptors are chon so that they are invariant under the group actions of in-terest.We u the local descriptors to pair up points that could be mapped to each other under a candidate symmetry action.We think of each such pair as depositing mass,or voting,for a speci fic sym-metry in the transformation space of interest.In this space,pairs with similar transformations form clusters that provide evidence for the corresponding symmetry relation.
In the cond step we u a stochastic clustering algorithm to ex-tract the significant modes of this mass distribution.Since the map-ping to transformation space does not prerve the spatial coher-ence or structure of samples on the input shape,we verify whether a meaningful symmetry has been found by checking the spatial consistency of the extracted subparts of the surface.Our cluster-ing method provides the necessary surface correspondences,since every point mass in transformation space corresponds to a candi-date pair of points in the spatial domain.Thus only a small t of candidates samples needs to be considered when detecting and extracting symmetric surface patches,avoiding a costly quadratic spatial arch over the whole input data t.
This paration into two stages is crucial for the effectiveness of our algorithm.The underlying obr
vation is the following:given a propod symmetry relation,it is simple and efficient to verify whether this specific symmetry is prent in the model;we just need to apply the symmetry transform and check whether the model is mapped onto itlf,or a sub-part of the model is mapped to a corre-sponding sub-part.However,the number of all potential mappings is by far too large to do an exhaustive arch.Therefore,wefirst accumulate statistical evidence for which symmetries are prent via our clustering in transformation space.Only if this evidence is sufficient do we perform spatial verification to check whether a specific symmetry is actually valid.Thus the complexity of symme-try extraction depends primarily on the number and size of relevant symmetries prent in the model and not on the complexity of the model itlf or that of the underlying symmetry group.As part of our approach,we can provide a quantitative measure on the“exact-ness”,or saliency,of a symmetry relation,which allows the ur to control the degree of perfection in the extracted symmetries.In addition,by specifying the size of the t of local shape descriptors, the ur can trade accuracy for computational efficiency.While fewer samples are sufficient for detecting large global symmetries, small partial symmetries require a significantly denr sampling. Thefinal output of our algorithm is a“symmetry graph”of the ob-ject,which encodes the significant symmetries of the object,each described by a patch pair and the corresponding transformation be-tween them.For objects that contain regular repeated structures, like windows or doors in architectural models,we ca
n recover the symmetries of the repetition pattern through a basis reduction algo-rithm.This in effect leads to a sparr and more informative sym-metry graph that contains only fundamental symmetry generators and avoids encoding parately symmetries that are just products of already recorded symmetries.This kind of repeated pattern discov-ery can be uful in consistent mesh editing applications.
1.1Contributions
We propo a new algorithm for pairing sample points on3D shapes with compatible local descriptors to generate a distribution in trans-formation space who peaks capture relevant symmetries of the object.We show how a stochastic clustering algorithm over this dis-tribution detects potential symmetry candidates,and provide a sur-face patching method that extracts a reduced symmetry graph from the extracted clusters.Our algorithms can be applied to3D mod-els of different shape characteristics and reprentations.Memory requirements are minimal and the computation is output-nsitive in the n that its complexity depends mainly on the number and extent of symmetries actually prent in the object.In addition,we provide theoretical bounds on the success rate of our algorithm as a function of the number of initial samples lected.The results in-dicate that the algorithm can be effective even for very large models that cannotfit in main memory.
1.2Related worklicenmanager
The problem of symmetry detection has been extensively studied in numerousfields including visual perception,computer vision, robotics,and computational geometry.Early methods concentrated onfinding perfect symmetries in2D or3D planar point ts[Atallah 1985],[Wolter et al.1985].Since the restriction to exact symme-tries limits the u of the methods for real-world objects,Alt et al.[1988]introduced a method for computing approximate global symmetries in3D point ts,but the complexity of the algorithm makes it impractical for large data ts.Zabrodsky et al.[1995]for-malized the notion of approximate symmetry by expressing sym-metry as a continuous feature.Sun et al.[1997]propod to exam-ine the correlation of the Gaussian image to recover global reflec-tive and rotational symmetries.Kazhdan and co-workers[2002]in-troduced a shape descriptor that concily encodes global reflective symmetries.Later they extended this work to rotational symmetries and ud it for shape retrieval for databa matching in[Kazhdan et al.2004].
Our method bears some similarity to the Hough transform,a popular feature extraction method mainly ud in image process-ing[Hough1959].Starting from a t of sample points obtained using edge detection,the method repeatedly lects small subts of the samples to estimate the parameters of the feature curve. Analogous to our approach,votes cast by all of the estimates are
kristen connolly
accumulated and thefinal feature curve is extracted bad on the majority of votes.Recently ideas bad on the Hough transform have been ud by[Loy and Eklundh2006]to detect reflective and rotational symmetries in images.
The RANdom SAmple Connsus(RANSAC)method propod by Fischler and Bolles[1981]is an algorithm for robust model fitting for data containing many outliers.In the context of shape matching the basic idea is to choo a random t of corresponding samples on the query and target shapes,apply the global transfor-mation induced by the samples,and evaluate the matching error between the two shapes.If sufficiently many transformations are explored in this way,the relevant symmetries can eventually be de-termined.Since the evaluation of the matching error requires costly spatial proximity tests,geometric hashing[Lamdan and Wolfson 1988]pre-computes all possible alignments by denly sampling the space of transformations and storing the resulting shape distri-bution in a hash grid.Gal and Cohen-Or[2006]recently prented an effective method for shape matching bad on this idea.Their al-gorithm computes local shape descriptors that are grouped to form salient shape features.Using an empirical saliency measure,shape features are then ud to pre-compute a geometric hash table that allows efficient partial matching.
While sharing some similarities,our method is fundamentally dif-ferent from both RANSAC and geom
etric hashing.We avoid the costly exhaustive arch of the former by computing the match-ing error of a transformation only after we accumulate sufficient evidence for a symmetry.At the same time our method requires minimal storage,in contrast to geometric hashing,where hash ta-bles of up to3.5GBytes have been reported for complex geometric shapes[Gal and Cohen-Or2006].
1.3Overview
Wefirst give some intuition for our method by looking at the2D example shown in Figure3,where the goal is to detect reflective symmetries of the butterfly.Any pair of points(p,q)on the bound-ary of the model defines a unique reflection with respect to the bi-ctor line through(p+q)/2with normal direction p−q.Hence
VDPSOLQJ DQDO\VLV SDLULQJ FOXVWHULQJ LQSXW PRGHO VDPSOH VHW VLJQDWXUHV WUDQVIRUPDWLRQV VXUIDFH SDWFKHV
SDWFKLQJ
'
7GHQVLW\Figure 2:The symmetry extraction pipeline.Sampling yields a t P of surface points.For each p i ∈P a local signature is computed.Points p i ,p j with similar signatures are paired and a point in transformation space Γis computed mapping the local frame of p i to the one at p j .Clustering in Γyields subts of P that remain invariant under a certain transformation,which can be extracted using spatial region growing.such a pair can be understood as evidence for the existence of this speci fic re flective symmetry.By looking at all such pairs we can accumulate this evidence and extract the relevant symmetry rela-tion(s).Only if many point pairs agree on (roughly)the same re-flection line,do we have reason to believe that the corresponding symmetry is truly prent in the model.Thus we can detect po-tential symmetries by looking at clusters of points in the space of transformations Γ,where each point corresponds to a speci fic re-flection line.However,as shown in the illustration,the evidence of a single point pair is only reliable if the local geometry around the poin
ts is faithfully mirrored by the re flective transformation.This obrvation will allow us to signi ficantly prune the t of all point pairs and avoid an exhaustive computation on a quadratic number of point pairs.
Since the mapping to Γdoes not incorporate the spatial position of surface samples,pairs from unrelated parts of the object can be mapped to the same point in transformation space.Thus in a cond pha we extract spatially coherent components of the model that are invariant under the extracted symmetry transformations.Us-ing the point pair correspondences prent in the cluster,we per-form an incremental region growing algorithm to verify a speci fic symmetry.Figure 2gives a high-level overview of our symmetry extraction pipeline.The following ctions will elaborate on the individual stages and provide details of our approach.
F
G WUDQVIRUPDWLRQ VSDFH
'
Figure 3:Illustration of symmetry detection for re flections.Every
pair of points de fines a symmetry line l that can be described by a distance d and an angle φ.Multiple points clustered in a small re-gion in transformation space provide evidence of a symmetry.The pair on the top left is discarded due to normal inconsistency.
2Signatures and Transformations
We consider the Euclidean transformation group generated by translations,rotations,re flections,and uniform scalings.Our goal is to find parts of a given 3D shape that are invariant under trans-formations in this symmetry group or some lower-dimensional sub-group.
In order to apply the ideas sketched above,we need to compute the transformation T i j that maps a point p i on the surface of the model to another point p j .While point positions are suf ficient for de fin-ing a unique plane of re flection as in the example above,we cannot determine all degrees of freedom of a general Euclidean transform from the spatial positions alone.We therefore compute geometry signatures at each sample point p i bad on the concept of normal cycles [Cohen-Steiner and Morvan 2003].We apply the algorithm propod in [Alliez et al.2003]to approximate the curvature tensor at p i within a sphere of radius r and compute integrated principal curvatures κi ,1≤κi ,2and principal directions c i ,1and c i ,2.The ra-dius r should be on the order of the local sample spa
cing to achieve suf ficient averaging when computing the curvature tensor and avoid a strong dependence on the speci fic location of the sample points.
F M
F M
Q M
S M
F L
F L
Q L
S L
F M
F M
F L
a F L a F
M F M
Q L Q M
a F L
a F L a The principal directions de fine a local frame (c i ,1,c i ,2,n i ),with nor-mal vector n i =c i ,1×c i ,2.We orient this frame as a right-handed coordinate frame that aligns with the outward pointing surface nor-mal by flipping signs of the appropriate vectors if necessary.In order to obtain a canonical rotational component R i j of the transfor-mation T i j we first align the two normals along their common plane and then pick the smaller of the two rotations around the normal that aligns to one of the two possible choices of orientation in tan-gent space.The uniform scale component of T i j is estimated from the ratio of principal curvatures as s i j =(κi ,1/κj ,1+κi ,2/κj ,2)/2,the translation is computed as t i j =p j −s i j R i j p i .For a given pair (p i ,p j )we thus obtain a point in 7-dimensional transforma-tion space Γas T i j =(s i j ,R x i j ,R y i j ,R z i j ,t x i j ,t y i j ,t z i j ),where R x i j ,R y i j ,R z i j
are the Euler angles derived from R i j and t i j =[t x i j t y
i j t z i j ]T .In order to handle re flections,we also compute the transformation obtained when re flecting the model about an arbitrary but fixed plane.
2.1Point Pruning
A differential surface patch at umbilic ,tho for which κi ,1=κi ,2,is invariant under rotations around the surface normal.Pairs involving such points and their signatures do not de fine a unique transformation,but trace out curves in transformation space,which may quickly camou flage meaningful symmetry clusters.To avoid clutter in transformation space,we discard the points from the sample ,we only consider points on the surface with distinct principal curvatures (and hence stable principal directions),
which give ri to a unique transformation when paired with an-other compatible point.Apart from making the symmetry clus-tering more robust,point pruning has the additional advantage of reducing computation time.We obtain the adaptive sample t by applying a thresholdγ<1on the ratio of curvatures:p i∈P,if
|κi,1/κi,2|<γ.We uγ=0.75for all examples in this paper. 2.2Pairing
Given the reduced t of surface samples P and their signatures, we can now compute transformations for pairs of points in P.We lect a random subt P ⊂P andfind all pairs(p ,p)with p ∈P and p∈P that provide evidence for a symmetry relation.In the Appendix we give theoretical bounds on the size of P and P required to successfullyfind symmetries of a certain size.
As indicated above,the evidence of a lected point pair for a spe-cific symmetry relation is only reliable,if a local surface patch around each point is invariant under a transformation from the con-sidered symmetry group G.In the2D illustration of Figure3,for example,we can reject a pair,if the curvature estimates at both points differ too much,since curvature is invariant under reflection. To obtain an efficient pairing algorithm we map all samples to a signature spaceΩand u the metric of that space to estimate the deviation from perfect invariance.Only point pairs that are clo in Ωare considered as suitable candidates for a local symmetry rela-tion,which avoids an exhaustive computation of a quadratic number of point pairs.
For the full7-dimensional Euclidean group in3D,the mapping from P toΩ7=I R is given asσ7(p i)=κi,1/κi,2,since uniform scaling,rotation,and translation leave the ratio of principal curva-tures unchanged.The sub-index7indicates the dimension of the symmetry group.For purely rigid transforms,we defineσ6(p i)= (κi,1,κi,2)withΩ6=I R2.We can now for a given sample p i∈P determine
all suitable partners in P by performing a range query inΩ.Using standard spatial proximity data ,a kd-tree,we can perform pairing in O(n log n)time,where n=|P|and n =|P |.If only reflections and/or translations are considered,we can additionally reject pairs bad on the orientation of the local frames,as illustrated in Figure3.
Figure4shows that pruning not only reduces the complexity of the clustering algorithm,but,even more importantly,avoids clutter in transformation space.By focusing only on locally consistent symmetry pairs,meaningful clusters are stably detected inΓ.
3Clustering多彩多姿
The pairing computed in the previous stage provides us with a t of transformations that map local surface patches onto each other. Each pair thus provides evidence for a symmetry relation at the level of the local sample spacing.To extract meaningful symme-tries at larger scales we need to accumulate this local ,find groups of pairs with a similar transformation that correspond to symmetric subts of the model surface.This requires the defi-nition of a distance metric inΓ,which is non-trivial,since scaling, rotation,and translation need to be combined in a single metric.We follow the approach of[Amato et al.2000]and define the norm of a transformation T=(s,R x,R y,R z,t x,t y,t z)
∈Γas the weighted sum T 2=β1s2+β2(R2x+R2y+R2z)+β3(t2x+t2y+t2z).The weightsβi allow to adjust the relative influence of the individual components of the transformation.In all our examples we t the weights so that a rotation by180degrees corresponds to a displacement of
half
F
G
F F
G
G
Figure4:Pair pruning.40samples on the butterfly lead to
40
2
= 780points in transformation space.Pruning bad on curvature re-duces the t to503points,while additionally normal-bad prun-ing yields138points.The density plots show how the meaningful symmetry clusters become significantly more pronounced.
the bounding box diagonal and a scaling factor of10.A metric for Γcan then be derived as d(T,T )= T−T ,where the subtrac-tion is component-wi,e also[Hofer et al.2004]for a detailed discussion.
3.1Mean-Shift
If the symmetries in the model are perfect(and the sampling in-cludes point pairs that are perfectly symmetric),then all pairs of the same(discrete)symmetry relation map to a single point inΓ.Many real-world objects exhibit approximate symmetries,however,and the sampling will not be precily symme
tric in general.We thus need a method tofind clusters in transformation space.When look-ing at the distribution of points inΓ,we immediately e that stan-dard parametric clustering methods,such as k-means clustering,are not suitable for our purpos.In general we have no a priori knowl-edge on the number of(partial)symmetries of the input , lecting k would be difficult.Furthermore,clusters are not nec-essarily isotropic,especially for approximate symmetries like the ones shown in Figure1.A more suitable clustering method is mean shift clustering,a non-parametric method bad on gradient ascent on a density functionρ[Comaniciu and Meer2002]1.This density function is defined as a sum of kernel functions K centered at each point T i inΓas
ρ(T)=∑
i
K( T−T i /h).
We u the radially symmetric Epanechnikov kernel with band-width h as suggested in[Comaniciu and Meer2002].The signif-icant modes ofρare determined using gradient ascent.All points thatflow into a local maximum of sufficient height are considered samples of a significant cluster C k.The corr
esponding symmetry transformation T k is then defined by the cluster’s maximum.Esn-tially,the algorithm can be understood as a voting scheme:Every point pair votes for the symmetry relation that has been extracted 1Mean shift clustering has also been ud in[James and Twigg2005]for skinning mesh animations and in[Tuzel et al.2005]for3D motion estima-tion.
from its local frames.If many votes are cast for the same symme-try,a local peak is created in the accumulated density function.For more details on mean-shift clustering we refer to[Comaniciu and Meer2002].
4Verification
A significant mode detected by the mean-shift clustering algorithm does not necessarily correspond to a meaningful symmetry.Since the spatial relation of sample points is lost during the mapping to transformation space,sample pairs from uncorrelated parts of the object can accumulate to form discernible clusters.The effective-ness of our method is bad on the obrvation that statistically such spurious modes are rare(e also the analysis in the Appendix):It is highly unlikely that many uncorrelated point pairs agree on the same ,are mapped to the same point in7D trans-formation space.We can thus afford to perform a spatial verifica-tion for each cluster C k by ext
racting the connected components of the model that are invariant under the corresponding transformation T k.We compute the surface patches using an incremental patch growing process,starting with a random point of C k,which corre-sponds to a pair(p i,p j)of points on the model surface.Now we look at the one-ring neighbors of p i,apply T k,and check whether the distance of the transformed points to the surface around p j is below a given error threshold.If so,we add them to the current patch.We keep extending this patch along its boundary until no more points can be added.During the growth process,we mark all visited samples on the surface and remove points in C k that corre-spond to the samples.This process is then repeated using the next point in C k until all points have been considered.
Since the transformation T k at the cluster’s maximum does not nec-essarily provide the best possible transformation for matching the surface patches,we incrementally refine T k during the patch grow-ing using the iterated clost points(ICP)algorithm[Rusinkiewicz and Levoy2001].The normalized residual of the ICP matching then provides a quantitative measure for the exactness of the sym-metry[Mitra et al.2004].Other measures,such as the Hausdorff distance can also be ud.We end up with a collection of pairs of patches on the model surface that are mapped onto each other by the cluster’s transformation T k.This information can be encoded in a weighted graph,
where each node corresponds to a patch and each edge denotes the transformation that maps two patches onto each other,weighted by the matching error.
4.1Compound Transforms
Many geometric objects exhibit symmetries in a structured or repet-itive fashion resulting in a large number of clusters in transforma-tion space[Liu et al.2004].Encoding all pair-wi symmetry re-lations for such models leads to a complex and highly redundant symmetry graph and thus a costly verification stage.In this c-tion we describe a simple basis reduction algorithm that computes a compact t of generators for all detected symmetries in transfor-mation space[Magnus et al.2004].This significantly reduces the number of spatial consistency checks required for verification and yields a more informative symmetry graph that supports advanced editing operations and high level shape comparisons.
The algorithm shown below takes as input all extracted symmetry transformations T sorted in descending order of cluster height and iteratively process each transformation T i∈T.During execution we maintain an alphabet A of generators and the language L that encodes T in terms of the alphabet A.A ur parameterηcontrols
WUDQV
R
URW
Figure5:Symmetry graph reduction for a model with structured symmetries at two different scales.60significant modes have been extracted in the clustering stage.The reduced basis contains6trans-formations,as indicated by the arrows.The graph on the left shows the number of detected symmetries as a function of random samples in the subt P ⊂P.
the complexity of the algorithm by limiting the arch to loops of lengthη+1.The thresholdδmeasures the allowed deviation from the exact transformation.
Figure5shows an example of a reduced symmetry basis.Verifi-cation can now be applied more efficiently on the t L of com-pound transformations.For more details on basis reduction we refer to[Magnus et al.2004].
Algorithm1Symmetry basis reduction.
Input:T={T1,T2,...,T n}
A←{I}
otherwi虚拟语气
L←/0
for i=1to n do
if∃(A1,...,Aη)with A j∈T i−∏ηj=1A j|≤δthen
L←L∪{(A1,...,Aη)}
el
A←A∪{T i,T−1i}
L←L∪{(T i)}
end if
end for
5Results and Applications
We have implemented the pipeline sketched in Figure2.An initial sample t is created by uniformly sampling the input model.Af-ter computing signatures using the method of[Alliez et al.2003], point pruning yields the reduced sample t P.We then lect a random subt P ⊂P,find all suitable pairs(p ∈P ,p∈P)bad on the proximity in signature space,and compute the correspond-ing transformations.We perform mean-shift clustering using the method propod in[Arya et al.1998]to efficiently compute neigh-borhoods in7D transformation space.Basis reduction and verifica-tionfinally yield the symmetric patches.We show in the Appendix that our method is guaranteed tofind existing symmetry relations provided the sampling is den enough with respect to the size of the symmetric patches.The following examples verify this claim and demonstrate that practical results can be obtained even if the theoretical sampling requirements are not met.
UDQGRP VDPSOHV
RXW RI WRWDO
漂亮的英文单词V
F O X V W H U K H L J K W
Figure 6:The six most signi ficant modes of the Sydney Opera with the full 7-dimensional symmetries (1,2,3)and pure re flections (4,5,6).The graph shows the distribution of scaling factors.
Figure 1shows partial and approximate symmetry detection on a
lar scan of a hand-sculpted model.The dragon has been sampled with 2470points out of which 800have been randomly lected to extract the five most signi ficant modes.The deviations from perfect symmetry are visualized as the signed distances to the clost point on the perfectly symmetric patch.Since the displacements can be compactly encoded,a compresd reprentation of the surface can be computed bad on the extracted symmetry graph.
Figure 6shows an example using the full 7-dimensional symmetry group compod of uniform scaling,rotation,re flection,and trans-lation.All major symmetries are faithfully recovered from only 500random samples,drawn from an initial sample t of 2000points.Figure 7shows a complex architectural model with symmetries at many different scales.The model has been sampled with 2254points out of which 100points (black spheres)and 500points (yellow spheres)where randomly chon leading to 280and 1262points in Γ,respectively.For visualization purpos we project the sam
ples in transformation space to 2D using metric multi-dimensional scaling [Cox and Cox 1994]as shown in (b).Note that the elliptical structures are due to errors caud by this projection.The two biggest modes map to the symmetries shown on the right,where the perfect global symmetry is faithfully recovered from only 100random samples.Automatic model reduction and instantiation is shown in (c).Using the first eight signi ficant modes,a reduction to only 14%of the original model size is achieved by taking out the corresponding symmetric patches.The resulting bounding box hierarchy shown in the lower right corner supports ef ficient spatial queries for applications such as ray-tracing or collision detection directly from the reduced geometry and the corresponding symme-try relations.In (d)we utilized the extracted symmetries to perform advanced editing operations.The ur can lect a speci fic symme-try relation and modify certain parts of the model.The system will then automatically apply the modi fications to all corresponding patches to maintain the original symmetry.
Figure 8illustrates an application of our method for gmentation.Two pos of the hor have been sampled with 1000points.We then lected 500random points on po A and paired the with samples from po B,as shown in (d).The mapping to transforma-tion space is thus restricted to only include pairs that contain one sample from either po.We can then extract the rigid gments of the
model as tho parts that are invariant under a rigid transforma-tion between the two pos (e).The projected density function is shown in (b).The biggest modes on the left correspond to the torso and head of the hor.The plot on the right is obtained after
remov-ing
the parts from the model
and adding 192additional samples
to初二化学上册知识点
the t of
random points.
Note
that in the 6D transformation space
等待的英文
D
E
F
雅思在线学习G
UDQGRP VDPSOHV UDQGRP VDPSOHV
SDLUV SDLUV
' '
' 'Figure 7:Chambord castle.(a)input model with random surface samples drawn from a total of 2254samples,(b)points in trans-formation space projected to 2D and associated density plots;the symmetries corresponding to the biggest two modes are shown on the right,(c)successive reduction by taking out symmetric patches and resulting bounding box hierarchy,(d)advanced editing using the extracted symmetry relations.
