对偶变换：计算几何中的光线跟踪与超采样

"对偶变换-计算流体力学与传热学 陶文全" 本文主要探讨了计算几何中的一种重要概念——对偶变换，它在处理平面几何问题时具有广泛应用。对偶变换是一种将点集映射为直线集，或者反过来的操作，保持了某些特定性质的一一对应关系。这个概念在计算流体力学、传热学以及计算机图形学等领域都有重要应用，例如在光线跟踪和超采样中。 在第8章“排列与对偶：光线跟踪超采样”中，作者陶文全介绍了如何利用对偶变换来处理和优化计算问题。首先，他阐述了如何在单位正方形内选取n个点，并在O(n^2)的时间复杂度内计算这些点的半平面差异值，这是对偶变换的一个实际应用。接着，他详细定义了对偶变换的过程，即一个点p=(px,py)的对偶是直线y=pxx-py，而一条非垂直直线y=mx+b的对偶则是一个点(m,-b)。对于垂直线，由于无法直接定义对偶，通常需要特殊处理或通过旋转场景来避免。 对偶变换使得原对象（点或直线）在原平面（primal plane）中的属性被映射到了对偶平面（dual plane）中，保持了某些特性，如共线的点对应于共点的直线。这种变换对于解决某些计算问题非常有用，比如在光线跟踪中，通过对点和直线的对偶变换，可以更有效地追踪光线与几何物体的交互。 此外，书中还提到了其他计算几何的主题，如线段求交、多边形三角剖分、线性规划、正交区域查找、点定位以及Voronoi图等，这些都是计算几何的核心内容。这些章节分别讲述了如何处理这些问题，以及相关算法的应用和优化。例如，线性规划在铸模制造中的几何应用，以及kd-树和区域树在数据库查询中的高效数据结构。 对偶变换是计算几何中的一个强大工具，它能够帮助简化复杂问题，提高算法效率，特别是在处理大量几何对象时。结合其他计算几何的理论和技术，可以解决实际工程和科学计算中的诸多挑战。通过深入理解和掌握这些概念，读者能够更好地应对计算流体力学、传热学以及其他领域的计算问题。