Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
No edit summary
No edit summary
Line 1: Line 1:
{{Infobox scientist
[[Image:BoundingBox.jpg|thumb|A three-dimensional model with its bounding box drawn in dashed lines.]]
|name              = Yuan-Cheng Fung<br />馮元楨
|image            =
|birth_date        = {{Birth date and age|1919|9|15|mf=yes}}
|birth_place      = [[Changzhou]], [[Jiangsu]], China
|death_date        =
|death_place      =
|residence        = [[USA]]
|citizenship      = [[United States|American]]
|nationality      = [[USA|American]]
|ethnicity        = [[Han Chinese|Chinese]]
|field            = [[Bioengineering]]<br />[[Biomechanics]]
|work_institutions = [[Caltech]]<br />[[University of California, San Diego|UCSD]]
|alma_mater        = [[Nanjing University]]<br />[[Caltech]]
|doctoral_advisor  =  [[Ernest Edwin Sechler|Ernest Sechler]]
|doctoral_students =
|known_for        = [[bioengineering]]<br />[[biomechanics]]
|author_abbrev_bot =
|author_abbrev_zoo =
|influences        =
|influenced        =
|prizes            = {{no wrap|[[Theodore von Karman Medal|von Karman Medal]] (1976) <br /> [[Otto Laporte Award]] (1977) <br />[[Timoshenko Medal]] (1991) <br>[[National Medal of Science]] (2000)<br />[[Jordan Allen Medal]] (1991)<br />[[Russ Prize]] (2007)}}
|religion          =
|footnotes        =
|signature        =
}}


'''Yuan-Cheng "Bert" Fung''' (born 1919) is an American bio-engineer. He is regarded as a founding figure of [[bioengineering]], [[tissue engineering]], and the "Founder of Modern [[Biomechanics]]".<ref>[http://www.techscience.com/mcb_pdf/v1n1/pdf/184288277842.pdf YC “Bert” Fung: The Father of Modern Biomechanics (pdf)]</ref>
:''For [[building code]] compliance, see [[Bounding]].''


==Biography==
In [[computer graphics]] and [[computational geometry]], a '''bounding volume''' for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap.
Fung was born in [[Jiangsu]] Province, [[China]] in 1919. He earned a Bachelor's degree in 1941 and a Master's degree in 1943 from the [[National Central University]] (later renamed [[Nanjing University]] in [[mainland China]] and reinstated in [[Taiwan]]), and earned a Ph.D. from the [[California Institute of Technology]] in the [[United States]] in 1948.  


Fung currently is Professor Emeritus and Research Engineer at the [[University of California, San Diego|University of California, San Diego (UCSD)]].
A bounding volume for a set of objects is also a bounding volume for the single object consisting of their union, and the other way around. Therefore it is possible to confine the description to the case of a single object, which is assumed to be non-empty and bounded (finite).


==Research==
==Uses of bounding volumes==
He is the author of numerous books including Foundations of Solid Mechanics, Continuum Mechanics, and a series of books on Biomechanics. He is also one of the principal founders of the ''Journal of Biomechanics'' and was a past chair of the [[American Society of Mechanical Engineers|ASME]] International [[Applied Mechanics Division]]. In 1972, Fung established the Biomechanics Symposium under the American Society of Mechanical Engineers. This biannual summer meeting, first held at the Georgia Institute of Technology, became the annual Summer Bioengineering Conference. Fung and colleagues were also the first to recognize the importance of residual stress on arterial mechanical behavior.<ref name="residual">{{cite journal
Bounding volumes are most often used to accelerate certain kinds of tests.
|author=Chuong,C.J. and Y.C. Fung
|title=On Residual Stress in Arteries
|journal=Journal of Biomechanics
|year=1986
|volume=108
|pages=189–192
|doi=10.1115/1.3138600
|issue=2}}</ref>


===Fung's Law===
In [[Ray tracing (graphics)|ray tracing]], bounding volumes are used in ray-intersection tests, and in many [[rendering (computer graphics)|rendering]] [[algorithms]], they are used for [[viewing frustum]] tests.  If the ray or viewing frustum does not intersect the bounding volume, it cannot intersect the object contained in the volume. These intersection tests produce a list of objects that must be displayed. Here, displayed means rendered or rasterized.
Fung's famous exponential strain [[constitutive equation]] for preconditioned [[soft tissues]] is
:<math>w = \frac{1}{2}\left[q + c\left( e^Q -1 \right) \right]</math>
with
:<math>q=a_{ijkl}E_{ij}E_{kl} \qquad Q=b_{ijkl}E_{ij}E_{kl}</math>
quadratic forms of [[strain (mechanics)|Green-Lagrange strains]] <math>E_{ij}</math> and <math>a_{ijkl}</math>, <math>b_{ijkl}</math> and <math>c</math> material constants.<ref name="Fung">{{cite book
|author=Fung, Y.-C.
|title=Biomechanics: Mechanical Properties of Living Tissues
|publisher=Springer-Verlag
|location=New York
|year=1993
|pages= 568
|isbn=0-387-97947-6}}</ref> <math>w</math> is a [[strain energy]] function per volume unit, which is the mechanical strain energy for a given temperature. Materials that follow this law are known as '''Fung-elastic'''.<ref name="Humphrey">{{cite journal
|author=Humphrey, Jay D.  
|title=Continuum biomechanics of soft biological tissues
|journal=Proceedings of the Royal Society of London A
|editor=The Royal Society
|year=2003
|volume=459
|pages=3–43


|doi=10.1098/rspa.2002.1060
In [[collision detection]], when two bounding volumes do not intersect, then the contained objects cannot collide, either.
|url=http://rspa.royalsocietypublishing.org/content/459/2029/3.full.pdf
|bibcode=2003RSPSA.459....3H
|issue=2029}}</ref>


==Honors and awards==
Testing against a bounding volume is typically much faster than testing against the object itself, because of the bounding volume's simpler geometry. This is because an 'object' is typically composed of polygons or data structures that are reduced to polygonal approximations. In either case, it is computationally wasteful to test each polygon against the view volume if the object is not visible. (Onscreen objects must be 'clipped' to the screen, regardless of whether their surfaces are actually visible.)
* [[Theodore von Karman Medal]], 1976
* [[Otto Laporte Award]], 1977
* Worcester Reed Warner Medal, 1984 <ref>[http://www.asme.org/Governance/Honors/SocietyAwards/Worcester_Reed_Warner_Medal.cfm WORCESTER REED WARNER MEDAL RECIPIENTS]</ref>
* Jean-Leonard-Marie Poiseuille Award, 1986<ref>[http://www.coe.ou.edu/isb/awardees/1986.htm The International Society of Biorheology: Yuan-Cheng Fung, 1986 Recipient of the Jean-Leonard-Marie Poiseuille Award]</ref>
* [[Timoshenko Medal]], 1991
* Lissner Award for Bioengineering, from ASME
* Borelli Medal, from ASB
* Landis Award, from Microcirculation Society
* Alza Award, from BMES
* Melville Medal, 1994 <ref>[http://www.asme.org/Governance/Honors/SocietyAwards/Melville_Medal.cfm MELVILLE MEDAL RECIPIENTS]</ref>
* United States National Academy of Engineering Founders Award (NAE Founders Award), 1998
* [[National Medal of Science]], 2000
* [[Russ Prize|Fritz J. and Dolores H. Russ Prize]], 2007 ("for the characterization and modeling of human tissue mechanics and function leading to prevention and mitigation of trauma.")<ref>[http://www.nae.edu/nae/awardscom.nsf/weblinks/JMAN-6X5NY5?OpenDocument Recipient of the Fritz J. and Dolores H. Russ Prize]</ref>


Fung was elected to the [[United States National Academy of Science]] (1993), the [[National Academy of Engineering]] (1979), the [[Institute of Medicine]] (1991), the [[Academia Sinica]] (1968), and is a Foreign Member of the [[Chinese Academy of Sciences]] (1994 election).
To obtain bounding volumes of complex objects, a common way is to break the objects/scene down using a [[scene graph]] or more specifically [[bounding volume hierarchy|bounding volume hierarchies]] like e.g. [[OBB tree]]s. The basic idea behind this is to organize a scene in a tree-like structure where the root comprises the whole scene and each leaf contains a smaller subpart.
 
==Common types of bounding volume==
 
The choice of the type of bounding volume for a given application is determined by a variety of factors: the computational cost of computing a bounding volume for an object, the cost of updating it in applications in which the objects can move or change shape or size, the cost of determining intersections, and the desired precision of the intersection test. The precision of the intersection test is related to the amount of space within the bounding volume not associated with the bounded object, called ''void space''. Sophisticated bounding volumes generally allow for less void space but are more computationally expensive. It is common to use several types in conjunction, such as a cheap one for a quick but rough test in conjunction with a more precise but also more expensive type.
 
The types treated here all give [[convex set|convex]] bounding volumes. If the object being bounded is known to be convex, this is not a restriction. If non-convex bounding volumes are required, an approach is to represent them as a union of a number of convex bounding volumes. Unfortunately, intersection tests become quickly more expensive as the bounding boxes become more sophisticated.
 
A '''bounding box''' is a [[cuboid]], or in 2-D a [[rectangle]], containing the object. In [[dynamical simulation]], bounding boxes are preferred to other shapes of bounding volume such as [[bounding sphere]]s or [[bounding cylinder|cylinders]] for objects that are roughly cuboid in shape when the intersection test needs to be fairly accurate. The benefit is obvious, for example, for objects that rest upon other, such as a car resting on the ground: a bounding sphere would show the car as possibly intersecting with the ground, which then would need to be rejected by a more expensive test of the actual model of the car; a bounding box immediately shows the car as not intersecting with the ground, saving the more expensive test.
 
A '''bounding capsule''' is a [[swept sphere]] (i.e. the volume that a sphere takes as it moves along a straight line segment) containing the object. Capsules can be represented by the radius of the swept sphere and the segment that the sphere is swept across). It has traits similar to a cylinder, but is easier to use, because the intersection test is simpler. A capsule and another object intersect if the distance between the capsule's defining segment and some feature of the other object is smaller than the capsule's radius. For example, two capsules intersect if the distance between the capsules' segments is smaller than the sum of their radii. This holds for arbitrarily rotated capsules, which is why they're more appealing than cylinders in practice.
 
A '''bounding cylinder''' is a [[cylinder (geometry)|cylinder]] containing the object. In most applications the axis of the cylinder is aligned with the vertical direction of the scene. Cylinders are appropriate for 3-D objects that can only rotate about a vertical axis but not about other axes, and are otherwise constrained to move by translation only. Two vertical-axis-aligned cylinders intersect when, simultaneously, their projections on the vertical axis intersect – which are two line segments – as well their projections on the horizontal plane – two circular disks. Both are easy to test. In [[video game]]s, bounding cylinders are often used as bounding volumes for people standing upright.
 
A '''bounding ellipsoid''' is an [[ellipsoid]] containing the object. Ellipsoids usually provide tighter fitting than a sphere. Intersections with ellipsoids are done by scaling the other object along the [[Principal axis theorem|principal axes]] of the ellipsoid by an amount equal to the [[multiplicative inverse]] of the radii of the ellipsoid, thus reducing the problem to intersecting the scaled object with a [[unit sphere]]. Care should be taken to avoid problems if the applied scaling introduces [[skew]]. Skew can make the usage of ellipsoids impractical in certain cases, for example collision between two arbitrary ellipsoids.
 
A '''bounding slab''' is related to the AABB and used to speed up [[ray tracing (graphics)|ray tracing]]<ref>
[[POV-Ray]] Documentation[http://www.povray.org/documentation/view/3.6.1/323/]
</ref>
 
A '''[[bounding sphere]]''' is a [[sphere]] containing the object. In 2-D graphics, this is a [[circle]]. Bounding spheres are represented by centre and radius. They are very quick to test for collision with each other: two spheres intersect when the distance between their centres does not exceed the sum of their radii. This makes bounding spheres appropriate for objects that can move in any number of dimensions.
 
In many applications the bounding box is aligned with the axes of the co-ordinate system, and it is then known as an '''axis-aligned bounding box''' ('''AABB'''). To distinguish the general case from an AABB, an arbitrary bounding box is sometimes called an '''oriented bounding box''' ('''OBB'''). AABBs are much simpler to test for intersection than OBBs, but have the disadvantage that when the model is rotated they cannot be simply rotated with it, but need to be recomputed.
 
A '''bounding triangle''' in 2-D is quite useful to speedup the clipping or visibility test of a B-Spline curve. See [[Clipping (computer graphics)#Algorithms|"Circle and B-Splines clipping algorithms"]] under the subject Clipping (computer graphics) for an example of use.
 
A '''[[convex hull]]''' is the smallest convex volume containing the object. If the object is the union of a finite set of points, its convex hull is a polytope.
 
A '''discrete oriented polytope''' ('''DOP''') generalizes the AABB. A DOP is a convex [[polytope]] containing the object (in 2-D a [[polygon]]; in 3-D a [[polyhedron]]), constructed by taking a number of suitably oriented planes at infinity and moving them until they collide with the object. The DOP is then the convex polytope resulting from intersection of the half-spaces bounded by the planes. Popular choices for constructing DOPs in 3-D graphics include the '''axis-aligned bounding box''', made from 6 axis-aligned planes, and the '''beveled bounding box''', made from 10 (if beveled only on vertical edges, say), 18 (if beveled on all edges), or 26 planes (if beveled on all edges and corners). A DOP constructed from ''k'' planes is called a ''k''-DOP; the actual number of faces can be less than ''k'', since some can become degenerate, shrunk to an edge or a vertex.
 
A '''[[minimum bounding rectangle]]''' or '''MBR''' – the least AABB in 2-D – is frequently used in the description of geographic (or "geospatial") data items, serving as a simplified proxy for a dataset's spatial extent (see [[geospatial metadata]]) for the purpose of data search (including spatial queries as applicable) and display. It is also a basic component of the [[R-tree]] method of [[spatial index]]ing.
 
==Basic intersection checks==
For some types of bounding volume (OBB and convex polyhedra), an effective check is that of the [[separating axis theorem]]. The idea here is that, if there exists an axis by which the objects do not overlap, then the objects do not intersect. Usually the axes<!-- plural of axis is axes, per Webster--> checked are those of the basic axes for the volumes (the unit axes in the case of an AABB, or the 3 base axes from each OBB in the case of OBBs). Often, this is followed by also checking the cross-products of the previous axes (one axis from each object).
 
In the case of an AABB, this tests becomes a simple set of overlap tests in terms of the unit axes. For an AABB defined by M,N against one defined by O,P they do not intersect if
(M<sub>x</sub>>P<sub>x</sub>) or (O<sub>x</sub>>N<sub>x</sub>) or (M<sub>y</sub>>P<sub>y</sub>) or (O<sub>y</sub>>N<sub>y</sub>) or (M<sub>z</sub>>P<sub>z</sub>) or (O<sub>z</sub>>N<sub>z</sub>).
 
An AABB can also be projected along an axis, for example, if it has edges of length L and is centered at C, and is being projected along the axis N:<br/>
<math>r = 0.5L_x|N_x|+0.5L_y|N_y|+0.5L_z|N_z|\,</math>, and <math>b=C*N\,</math> or <math>b=C_x N_x +C_y N_y+C_z N_z\,</math>, and <math>m=b-r, n=b+r\,</math>
where m and n are the minimum and maximum extents.
 
An OBB is similar in this respect, but is slightly more complicated. For an OBB with L and C as above, and with I, J, and K as the OBB's base axes, then:<br/>
<math>r = 0.5L_x|N*I|+0.5L_y|N*J|+0.5L_z|N*K|\,</math>
 
<math>m=C*N-r \mbox{ and } n=C*N+r\,</math>
 
For the ranges m,n and o,p it can be said that they do not intersect if m>p or o>n. Thus, by projecting the ranges of 2 OBBs along the I, J, and K axes of each OBB, and checking for non-intersection, it is possible to detect non-intersection. By additionally checking along the cross products of these axes (I<sub>0</sub>×I<sub>1</sub>, I<sub>0</sub>×J<sub>1</sub>, ...) one can be more certain that intersection is impossible.
 
This concept of determining non-intersection via use of axis projection also extends to convex polyhedra, however with the normals of each polyhedral face being used instead of the base axes, and with the extents being based on the minimum and maximum dot products of each vertex against the axes. Note that this description assumes the checks are being done in world space.
 
==See also==
* [[Bounding sphere]]
* [[Convex hull algorithms]]
* [[Minimum bounding box]]
* [[Minimum bounding rectangle]]
* [[Spatial index]]


==References==
==References==
Line 91: Line 78:


==External links==
==External links==
*[http://www.jacobsschool.ucsd.edu/faculty/faculty_bios/findprofile.sfe?department=BENG&fmp_recid=21 Profile at UCSD]
*[http://udn.epicgames.com/Two/rsrc/Two/CollisionTutorial/kdop_sizes.jpg Illustration of several DOPs for the same model, from epicgames.com]
*Y.C. Fung, [http://amresearch.blogspot.com/2006/07/1991-timoshenko-medal-lecture-by-yuan.html Mechanics of Man], Acceptance Speech for the Timoshenko Medal.
*[http://www.asme.org/Governance/Honors/SocietyAwards/YC_Fung_Young_Investigator.cfm YC Fung Young Investigator Award]
*[http://www.techscience.com/mcb_pdf/v1n1/pdf/171267552381.pdf YC Fung: A Scientific Giant and a Kind Man (pdf)]
*[http://www.techscience.com/books/fung.html Molecular & Cellular Biomechanics: In Honor of The 90th Birthday of Professor Yuan Cheng Fung ]
 
{{Winners of the National Medal of Science|engineering}}


{{Authority control|VIAF=85337796}}
[[Category:Geometric algorithms]]
{{Persondata <!-- Metadata: see [[Wikipedia:Persondata]]. -->
[[Category:3D computer graphics]]
| NAME              = Fung, Yuan-Cheng
| ALTERNATIVE NAMES =
| SHORT DESCRIPTION = American bio engineer
| DATE OF BIRTH    = September 15, 1919
| PLACE OF BIRTH    = [[Changzhou]], [[Jiangsu]], China
| DATE OF DEATH    =
| PLACE OF DEATH    =
}}
{{DEFAULTSORT:Fung, Yuan-Cheng}}
[[Category:1919 births]]
[[Category:American engineers]]
[[Category:Biological engineering]]
[[Category:Bioengineers]]
[[Category:California Institute of Technology alumni]]
[[Category:California Institute of Technology faculty]]
[[Category:Chinese emigrants to the United States]]
[[Category:Guggenheim Fellows]]
[[Category:Living people]]
[[Category:Members of Academia Sinica]]
[[Category:Members of the United States National Academy of Sciences]]
[[Category:National Medal of Science laureates]]
[[Category:Nanjing University alumni]]
[[Category:National Central University alumni]]
[[Category:People from Changzhou]]
[[Category:University of California, San Diego faculty]]
[[Category:Members of the United States National Academy of Engineering]]

Revision as of 14:45, 12 August 2014

A three-dimensional model with its bounding box drawn in dashed lines.
For building code compliance, see Bounding.

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap.

A bounding volume for a set of objects is also a bounding volume for the single object consisting of their union, and the other way around. Therefore it is possible to confine the description to the case of a single object, which is assumed to be non-empty and bounded (finite).

Uses of bounding volumes

Bounding volumes are most often used to accelerate certain kinds of tests.

In ray tracing, bounding volumes are used in ray-intersection tests, and in many rendering algorithms, they are used for viewing frustum tests. If the ray or viewing frustum does not intersect the bounding volume, it cannot intersect the object contained in the volume. These intersection tests produce a list of objects that must be displayed. Here, displayed means rendered or rasterized.

In collision detection, when two bounding volumes do not intersect, then the contained objects cannot collide, either.

Testing against a bounding volume is typically much faster than testing against the object itself, because of the bounding volume's simpler geometry. This is because an 'object' is typically composed of polygons or data structures that are reduced to polygonal approximations. In either case, it is computationally wasteful to test each polygon against the view volume if the object is not visible. (Onscreen objects must be 'clipped' to the screen, regardless of whether their surfaces are actually visible.)

To obtain bounding volumes of complex objects, a common way is to break the objects/scene down using a scene graph or more specifically bounding volume hierarchies like e.g. OBB trees. The basic idea behind this is to organize a scene in a tree-like structure where the root comprises the whole scene and each leaf contains a smaller subpart.

Common types of bounding volume

The choice of the type of bounding volume for a given application is determined by a variety of factors: the computational cost of computing a bounding volume for an object, the cost of updating it in applications in which the objects can move or change shape or size, the cost of determining intersections, and the desired precision of the intersection test. The precision of the intersection test is related to the amount of space within the bounding volume not associated with the bounded object, called void space. Sophisticated bounding volumes generally allow for less void space but are more computationally expensive. It is common to use several types in conjunction, such as a cheap one for a quick but rough test in conjunction with a more precise but also more expensive type.

The types treated here all give convex bounding volumes. If the object being bounded is known to be convex, this is not a restriction. If non-convex bounding volumes are required, an approach is to represent them as a union of a number of convex bounding volumes. Unfortunately, intersection tests become quickly more expensive as the bounding boxes become more sophisticated.

A bounding box is a cuboid, or in 2-D a rectangle, containing the object. In dynamical simulation, bounding boxes are preferred to other shapes of bounding volume such as bounding spheres or cylinders for objects that are roughly cuboid in shape when the intersection test needs to be fairly accurate. The benefit is obvious, for example, for objects that rest upon other, such as a car resting on the ground: a bounding sphere would show the car as possibly intersecting with the ground, which then would need to be rejected by a more expensive test of the actual model of the car; a bounding box immediately shows the car as not intersecting with the ground, saving the more expensive test.

A bounding capsule is a swept sphere (i.e. the volume that a sphere takes as it moves along a straight line segment) containing the object. Capsules can be represented by the radius of the swept sphere and the segment that the sphere is swept across). It has traits similar to a cylinder, but is easier to use, because the intersection test is simpler. A capsule and another object intersect if the distance between the capsule's defining segment and some feature of the other object is smaller than the capsule's radius. For example, two capsules intersect if the distance between the capsules' segments is smaller than the sum of their radii. This holds for arbitrarily rotated capsules, which is why they're more appealing than cylinders in practice.

A bounding cylinder is a cylinder containing the object. In most applications the axis of the cylinder is aligned with the vertical direction of the scene. Cylinders are appropriate for 3-D objects that can only rotate about a vertical axis but not about other axes, and are otherwise constrained to move by translation only. Two vertical-axis-aligned cylinders intersect when, simultaneously, their projections on the vertical axis intersect – which are two line segments – as well their projections on the horizontal plane – two circular disks. Both are easy to test. In video games, bounding cylinders are often used as bounding volumes for people standing upright.

A bounding ellipsoid is an ellipsoid containing the object. Ellipsoids usually provide tighter fitting than a sphere. Intersections with ellipsoids are done by scaling the other object along the principal axes of the ellipsoid by an amount equal to the multiplicative inverse of the radii of the ellipsoid, thus reducing the problem to intersecting the scaled object with a unit sphere. Care should be taken to avoid problems if the applied scaling introduces skew. Skew can make the usage of ellipsoids impractical in certain cases, for example collision between two arbitrary ellipsoids.

A bounding slab is related to the AABB and used to speed up ray tracing[1]

A bounding sphere is a sphere containing the object. In 2-D graphics, this is a circle. Bounding spheres are represented by centre and radius. They are very quick to test for collision with each other: two spheres intersect when the distance between their centres does not exceed the sum of their radii. This makes bounding spheres appropriate for objects that can move in any number of dimensions.

In many applications the bounding box is aligned with the axes of the co-ordinate system, and it is then known as an axis-aligned bounding box (AABB). To distinguish the general case from an AABB, an arbitrary bounding box is sometimes called an oriented bounding box (OBB). AABBs are much simpler to test for intersection than OBBs, but have the disadvantage that when the model is rotated they cannot be simply rotated with it, but need to be recomputed.

A bounding triangle in 2-D is quite useful to speedup the clipping or visibility test of a B-Spline curve. See "Circle and B-Splines clipping algorithms" under the subject Clipping (computer graphics) for an example of use.

A convex hull is the smallest convex volume containing the object. If the object is the union of a finite set of points, its convex hull is a polytope.

A discrete oriented polytope (DOP) generalizes the AABB. A DOP is a convex polytope containing the object (in 2-D a polygon; in 3-D a polyhedron), constructed by taking a number of suitably oriented planes at infinity and moving them until they collide with the object. The DOP is then the convex polytope resulting from intersection of the half-spaces bounded by the planes. Popular choices for constructing DOPs in 3-D graphics include the axis-aligned bounding box, made from 6 axis-aligned planes, and the beveled bounding box, made from 10 (if beveled only on vertical edges, say), 18 (if beveled on all edges), or 26 planes (if beveled on all edges and corners). A DOP constructed from k planes is called a k-DOP; the actual number of faces can be less than k, since some can become degenerate, shrunk to an edge or a vertex.

A minimum bounding rectangle or MBR – the least AABB in 2-D – is frequently used in the description of geographic (or "geospatial") data items, serving as a simplified proxy for a dataset's spatial extent (see geospatial metadata) for the purpose of data search (including spatial queries as applicable) and display. It is also a basic component of the R-tree method of spatial indexing.

Basic intersection checks

For some types of bounding volume (OBB and convex polyhedra), an effective check is that of the separating axis theorem. The idea here is that, if there exists an axis by which the objects do not overlap, then the objects do not intersect. Usually the axes checked are those of the basic axes for the volumes (the unit axes in the case of an AABB, or the 3 base axes from each OBB in the case of OBBs). Often, this is followed by also checking the cross-products of the previous axes (one axis from each object).

In the case of an AABB, this tests becomes a simple set of overlap tests in terms of the unit axes. For an AABB defined by M,N against one defined by O,P they do not intersect if (Mx>Px) or (Ox>Nx) or (My>Py) or (Oy>Ny) or (Mz>Pz) or (Oz>Nz).

An AABB can also be projected along an axis, for example, if it has edges of length L and is centered at C, and is being projected along the axis N:
, and or , and where m and n are the minimum and maximum extents.

An OBB is similar in this respect, but is slightly more complicated. For an OBB with L and C as above, and with I, J, and K as the OBB's base axes, then:

For the ranges m,n and o,p it can be said that they do not intersect if m>p or o>n. Thus, by projecting the ranges of 2 OBBs along the I, J, and K axes of each OBB, and checking for non-intersection, it is possible to detect non-intersection. By additionally checking along the cross products of these axes (I0×I1, I0×J1, ...) one can be more certain that intersection is impossible.

This concept of determining non-intersection via use of axis projection also extends to convex polyhedra, however with the normals of each polyhedral face being used instead of the base axes, and with the extents being based on the minimum and maximum dot products of each vertex against the axes. Note that this description assumes the checks are being done in world space.

See also

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

External links

  1. POV-Ray Documentation[1]