1e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen/* 2e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * Copyright (C) 2011 The Android Open Source Project 3e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * 4e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * Licensed under the Apache License, Version 2.0 (the "License"); 5e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * you may not use this file except in compliance with the License. 6e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * You may obtain a copy of the License at 7e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * 8e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * http://www.apache.org/licenses/LICENSE-2.0 9e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * 10e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * Unless required by applicable law or agreed to in writing, software 11e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * distributed under the License is distributed on an "AS IS" BASIS, 12e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * See the License for the specific language governing permissions and 14e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen * limitations under the License. 15e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen */ 16e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 17e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen///////////////////////////// 18e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Geometry.h 19e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// $Id: Geometry.h,v 1.2 2011/06/17 13:35:48 mbansal Exp $ 20e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 21e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#pragma once 22e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#include "MosaicTypes.h" 23e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 24e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen/////////////////////////////////////////////////////////////// 25e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen///////////////// BEG GLOBAL ROUTINES ///////////////////////// 26e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen/////////////////////////////////////////////////////////////// 27e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 28e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 29e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline double hypotSq(double a, double b) 30e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 31e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return ((a)*(a)+(b)*(b)); 32e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 33e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 34e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline void ClipRect(double x, double y, BlendRect &brect) 35e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 36e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (y < brect.bot) brect.bot = y; 37e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (y > brect.top) brect.top = y; 38e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (x < brect.lft) brect.lft = x; 39e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (x > brect.rgt) brect.rgt = x; 40e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 41e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 42e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline void ClipRect(BlendRect rrect, BlendRect &brect) 43e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 44e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (rrect.bot < brect.bot) brect.bot = rrect.bot; 45e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (rrect.top > brect.top) brect.top = rrect.top; 46e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (rrect.lft < brect.lft) brect.lft = rrect.lft; 47e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (rrect.rgt > brect.rgt) brect.rgt = rrect.rgt; 48e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 49e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 50e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Clip x to be within [-border,width+border-1] 51e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline void clipToSegment(int &x, int width, int border) 52e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 53e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if(x < -border) 54e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen x = -border; 55e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else if(x >= width+border) 56e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen x = width + border - 1; 57e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 58e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 59e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Return true if x within [-border,width+border-1] 60e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline bool inSegment(int x, int width, int border) 61e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 62e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return (x >= -border && x < width + border - 1); 63e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 64e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 65e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline void FindTriangleCentroid(double x0, double y0, double x1, double y1, 66e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double x2, double y2, 67e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double &mass, double ¢X, double ¢Y) 68e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 69e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate the centroid of the triangle 70e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen centX = (x0 + x1 + x2) / 3.0; 71e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen centY = (y0 + y1 + y2) / 3.0; 72e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 73e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate 2*Area for the triangle 74e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (y0 == y2) 75e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 76e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (x0 == x1) 77e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 78e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = fabs((y1 - y0) * (x2 - x0)); // Special case 1a 79e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 80e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else 81e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 82e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = fabs((y1 - y0) * (x1 - x0)); // Special case 1b 83e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 84e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 85e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else if (x0 == x2) 86e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 87e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (x0 == x1) 88e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 89e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = fabs((x2 - x0) * (y2 - y0)); // Special case 2a 90e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 91e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else 92e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 93e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = fabs((x1 - x0) * (y2 - y0)); // Special case 2a 94e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 95e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 96e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else if (x1 == x2) 97e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 98e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = fabs((x1 - x0) * (y2 - y0)); // Special case 3 99e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 100e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else 101e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 102e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate line equation from x0,y0 to x2,y2 103e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double dx = x2 - x0; 104e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double dy = y2 - y0; 105e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate the length of the side 106e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double len1 = sqrt(dx * dx + dy * dy); 107e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double m1 = dy / dx; 108e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double b1 = y0 - m1 * x0; 109e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate the line that goes through x1,y1 and is perpendicular to 110e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // the other line 111e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double m2 = 1.0 / m1; 112e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double b2 = y1 - m2 * x1; 113e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate the intersection of the two lines 114e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (fabs( m1 - m2 ) > 1.e-6) 115e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 116e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double x = (b2 - b1) / (m1 - m2); 117e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // the mass is the base * height 118e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen dx = x1 - x; 119e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen dy = y1 - m1 * x + b1; 120e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = len1 * sqrt(dx * dx + dy * dy); 121e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 122e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else 123e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen { 124e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen mass = fabs( (y1 - y0) * (x2 - x0) ); 125e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 126e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 127e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 128e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 129e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Cheninline void FindQuadCentroid(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, 130e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double ¢X, double ¢Y) 131e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 132e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 133e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // To find the centroid: 134e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // 1) Divide the quadrilateral into two triangles by scribing a diagonal 135e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // 2) Calculate the centroid of each triangle (the intersection of the angle bisections). 136e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // 3) Find the centroid of the quad by weighting each triangle centroids by their area. 137e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 138e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Calculate the corner points 139e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double z; 140e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 141e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // The quad is split from x0,y0 to x2,y2 142e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double mass1, mass2, cent1x, cent2x, cent1y, cent2y; 143e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen FindTriangleCentroid(x0, y0, x1, y1, x2, y2, mass1, cent1x, cent1y); 144e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen FindTriangleCentroid(x0, y0, x3, y3, x2, y2, mass2, cent2x, cent2y); 145e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 146e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // determine position of quad centroid 147e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen z = mass2 / (mass1 + mass2); 148e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen centX = cent1x + (cent2x - cent1x) * z; 149e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen centY = cent1y + (cent2y - cent1y) * z; 150e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 151e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 152e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen/////////////////////////////////////////////////////////////// 153e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen////////////////// END GLOBAL ROUTINES //////////////////////// 154e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen/////////////////////////////////////////////////////////////// 155e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 156e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 157