ReactOS  r75919
monoChain.cc File Reference
#include "gluos.h"
#include "zlassert.h"
#include "monoChain.h"
#include "quicksort.h"
#include "searchTree.h"
#include "polyUtil.h"
Include dependency graph for monoChain.cc:

Go to the source code of this file.

Macros

#define max(a, b)   ((a>b)? a:b)
 
#define min(a, b)   ((a>b)? b:a)
 

Functions

Int isCusp (directedLine *v)
 
Int deleteRepeatDiagonals (Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
 
Real intersectHoriz (Real x1, Real y1, Real x2, Real y2, Real y)
 
static int compChainHeadInY (monoChain *mc1, monoChain *mc2)
 
monoChaindirectedLineLoopToMonoChainLoop (directedLine *loop)
 
monoChaindirectedLineLoopListToMonoChainLoopList (directedLine *list)
 
static Int compEdges (directedLine *e1, directedLine *e2)
 
Int compChains (monoChain *mc1, monoChain *mc2)
 
Int MC_sweepY (Int nVertices, monoChain **sortedVertices, sweepRange **ret_ranges)
 
void MC_findDiagonals (Int total_num_edges, monoChain **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
 
directedLineMC_partitionY (directedLine *polygons, sampledLine **retSampledLines)
 

Macro Definition Documentation

#define max (   a,
  b 
)    ((a>b)? a:b)

Definition at line 52 of file monoChain.cc.

Referenced by compEdges().

#define min (   a,
  b 
)    ((a>b)? b:a)

Definition at line 55 of file monoChain.cc.

Referenced by __copy_integer_and_fill(), __merge_sort_loop(), __read_buffered(), __tcp_enter_cwr(), __wine_dbg_set_functions(), __write_floatT(), _Dispatch_type_(), _M_append_fast_pos(), _M_append_sum_pos(), basic_string< char, char_traits< char >, allocator< char > >::_M_compare(), bitset< _Nb >::_M_copy_from_string(), basic_stringbuf< _CharT, _Traits, _Alloc >::_M_xsputnc(), basic_streambuf< _CharT, _Traits >::_M_xsputnc(), _makepath_s(), _mesa_pack_rgba_span_float(), _S_apply_to_pieces(), _S_string_copy(), _SetOperationTexts(), _Stl_tenscale(), _Success_(), _test_items_ok(), _tzset(), _wmakepath_s(), CAutoComplete::ACEditSubclassProc(), acmDriverDetailsA(), acmDriverDetailsW(), ACMStream_fnInfo(), ACMStream_fnReadFormat(), add_checksum_entry(), add_chunk(), add_option(), af_glyph_hints_align_strong_points(), af_latin_hints_link_segments(), alloc_chunk(), alloc_user_entry(), Amd64SetupIdt(), basic_string< char, char_traits< char >, allocator< char > >::append(), arbfp_get_caps(), arc2polybezier(), Array_splice(), basic_string< char, char_traits< char >, allocator< char > >::assign(), ata_check_unit(), AtapiChipInit(), AtapiDmaInit(), AtapiDmaPioSync(), AtapiDmaReinit(), AtapiDmaSetup(), AtapiHwInitialize__(), AtapiResetController__(), AtapiStartIo__(), AtaSetTransferMode(), auxGetDevCapsA(), AVIFILE_LoadIndex(), balance_data_chunk(), basic_string(), bdf_cmap_char_index(), bdf_cmap_char_next(), bezier_deviation_squared(), BiosMiscService(), bitmap_info_size(), bitmap_intersect(), BLOBComp(), BlockChainStream_ReadAt(), BlockChainStream_WriteAt(), BmpFrameDecode_CopyPalette(), brush_fill_pixels(), buffer_conversion_upload(), build_exe(), CUSBRequest::BuildBulkInterruptEndpoint(), CUSBRequest::BuildBulkInterruptTransferDescriptor(), CUSBRequest::BuildBulkInterruptTransferQueueHead(), CUSBRequest::BuildIsochronousEndpoint(), CUSBRequest::BuildTransferDescriptorChain(), CalculateColorTableSize(), CBDropDown(), cbEnhPaletteCopy(), CC_RGBtoHSL(), CcCopyData(), CcFlushCache(), CcpMapData(), CcPurgeCacheSection(), CcRosCreateVacb(), CcRosTrimCache(), CdfsFindFile(), CdfsGetNameInformation(), cert_name_to_str_with_indent(), CertGetNameStringW(), CertRDNValueToStrA(), NumPutGetTest::check_get_float(), check_index_bounds(), check_keywords(), check_updates(), ChildWndProc(), chunked_read(), ClassInterpretSenseInfo(), client_start(), CLIPOBJ_bEnum(), ClipOrCenterRectToMonitor(), CmdStartExternalCommand(), cmp_keyword(), CmpCompareInIndex(), CmpCopyCompressedName(), CmpQueryKeyData(), co_UserCreateWindowEx(), ColorRGBToHLS(), ColorsProc(), CombineRgn(), ComDBGetCurrentPortUsage(), basic_string< char, char_traits< char >, allocator< char > >::compare(), compare_addrinfo(), compare_addrinfow(), compareAltNameInfo(), CompareFunc(), CRegistryFolder::CompareIDs(), CNtObjectFolder::CompareIDs(), CCommonFolder< CRegistryFolder, RegPidlEntry, CRegistryFolderExtractIcon >::CompareName(), compareNameValues(), CompareProductName(), CompareUnicodeStrings(), CompBattGetBatteryGranularity(), compEdges(), compKeyword(), CompressGetFormat(), ComputeCompatibleFormat(), CUiWindow< CStatusBar >::ComputeContentBounds(), CUiSplitPanel::ComputeContentBounds(), CUiBox::ComputeMinimalSize(), ConCfgReadUserSettings(), ConDrvGetConsoleScreenBufferInfo(), ConDrvGetConsoleTitle(), ConDrvReadConsoleOutput(), ConDrvReadConsoleOutputString(), ConDrvSetConsoleCursorInfo(), ConDrvSetConsoleWindowInfo(), ConDrvWriteConsoleOutput(), ConfigDlgProc(), ConfirmMsgBox_Init(), ConioGetIntersection(), ConioGetUnion(), ConioWriteConsole(), ConSrvApplyUserSettings(), ConSrvInitConsole(), ConSrvReadUserSettings(), ConSrvTermReadStream(), context_bind_shader_resources(), context_create(), context_map_vsamplers(), convert_argb_pixels(), ConvertINetMultiByteToUnicode(), ConvertINetUnicodeToMultiByte(), ConWrite(), basic_string< char, char_traits< char >, allocator< char > >::copy(), CopyCompAttrIMEtoClient(), CopyCompClauseIMEtoClient(), CopyCompStringIMEtoClient(), CopyStreamData(), CountThread(), cp2range(), cpu_blitter_clear(), create_taskdialog_template(), CreateDIBPalette(), CreatePropertySheetPageA(), CreatePropertySheetPageW(), CredDialogCommandOk(), CRYPT_AddPrefixA(), CRYPT_AddPrefixAToW(), CRYPT_AddPrefixW(), CRYPT_ANSIToUnicode(), CRYPT_AsnDecodeGeneralizedTime(), CSR_API(), ctrl_resize(), customWordBreakProc(), cvtMM16imaK(), cvtMMimaK(), cvtMMms16K(), cvtSS16imaK(), cvtSSima16K(), cvtSSms16K(), cvtXX16alawK(), cvtXX16ulawK(), cvtXXalaw16K(), cvtXXalawulawK(), cvtXXulaw16K(), cvtXXulawalawK(), d3d9_query_GetData(), d3dcaps_from_wined3dcaps(), d3drm_animation_get_range(), d3dx9_base_effect_get_bool_array(), d3dx9_base_effect_get_float_array(), d3dx9_base_effect_get_int(), d3dx9_base_effect_get_int_array(), d3dx9_base_effect_set_bool_array(), d3dx9_base_effect_set_float_array(), d3dx9_base_effect_set_int_array(), d3dx9_base_effect_set_vector(), D3DXCreateCubeTextureFromFileInMemoryEx(), D3DXCreateTextureFromFileInMemoryEx(), D3DXSHRotateZ(), date_parse(), Date_setHours(), Date_setMinutes(), Date_setUTCHours(), Date_setUTCMinutes(), DATETIME_IncreaseField(), DdeQueryConvInfo(), ddraw7_GetAvailableVidMem(), ddraw_surface_create(), debugtext_tn(), DeckClickProc(), DECLARE_INTERFACE_(), default_dbgstr_an(), default_dbgstr_wn(), DefWndDoSizeMove(), DefWndHandleWindowPosChanging(), DefWndStartSizeMove(), device_clear_render_targets(), DIALOG_NEW_DlgProc(), DIB_MapPaletteColors(), DiskIoctlGetDriveGeometryEx(), DiskIoctlVerify(), DispatchEx_GetDispID(), DispatchEx_InvokeEx(), Display_OnVScroll(), DmaRequest(), do_calc(), codecvt< wchar_t, char, mbstate_t >::do_in(), codecvt< _InternT, _ExternT, _StateT >::do_length(), generator_codecvt::do_length(), codecvt< char, char, mbstate_t >::do_length(), codecvt< wchar_t, char, mbstate_t >::do_length(), do_lzo_decompress(), codecvt< wchar_t, char, mbstate_t >::do_out(), do_read(), do_regexp_match_next(), do_synchronous_recv(), do_synchronous_recvfrom(), do_synchronous_send(), do_test(), do_write_file(), DosCreateProcess(), DosInitPsp(), DosInt21h(), DosLoadExecutableInternal(), DPA_InsertPtr(), drain_content(), draw_chunk_bar_H(), DrawClock(), DrawListEntries(), Subdivider::drawSurfaces(), CImgAreaWindow::drawZoomFrame(), DriverEntry(), DriverIoControl(), DrvEnablePDEV(), DrvLineTo(), DSoundRender_SendSampleData(), dump(), dump_memory_info(), duplicate_extents(), DuplicateStringAEx(), DuplicateStringWEx(), EDIT_AdjustFormatRect(), EDIT_ConfinePoint(), EDIT_EM_LineFromChar(), EDIT_EM_PosFromChar(), EDIT_EM_ReplaceSel(), EDIT_EM_SetLimitText(), EDIT_EM_SetSel(), EDIT_GetLineRect(), EDIT_PaintLine(), EDIT_WM_Copy(), EDIT_WM_Paint(), EMFDRV_ArcChordPie(), EMFDRV_LineTo(), EMFDRV_UpdateBBox(), EmulatorWriteMemory(), EngLineTo(), EnumBackgroundCopyFiles_Next(), EnumBackgroundCopyJobs_Next(), EnumFormatImpl_Next(), EnumFormatImpl_Skip(), EnumMRUListA(), EnumMRUListW(), epm_register(), basic_string< char, char_traits< char >, allocator< char > >::erase(), EtfspCompareNames(), event_client(), ExAllocatePool(), exclude_msg(), execute_view(), ExpandEnvironmentStringsW(), ExpInitializeWorkerThreads(), expr_common_type(), Ext2ExpandBlock(), Ext2FreeBlock(), FAST486_OPCODE_HANDLER(), FD31_Validate(), fdi_Zipinflate_codes(), fetch_module_versioninfo(), field_format_extension_hex_with_ascii(), FileMonikerImpl_CommonPrefixWith(), fileref_get_filename(), fill_DataFormat(), find_builtin_prop(), find_disk_holes(), find_entry_by_id(), find_entry_by_name(), find_html_symbol(), basic_string< _CharT, _Traits, _Alloc >::find_last_not_of(), basic_string< _CharT, _Traits, _Alloc >::find_last_of(), find_mime_from_buffer(), find_new_dup_stripes(), Quilt::findSampleRates(), flush_events(), flush_extents(), flush_fcb(), flush_partial_stripe(), fnIMLangFontLink2_GetStrCodePages(), FONT_TextMetricWToA(), format_to_vec4(), FrLdrHeapCreate(), fs_read(), ftGdiGetGlyphOutline(), FTP_ParseNextFile(), GdipCreateLineBrushFromRect(), GdipGetPathWorldBounds(), generic_cable80(), get_available_data(), get_builtin_func(), get_builtin_id(), get_env(), get_first_last_from_cmap4(), get_geoinfo_dataptr(), get_olemisc_value(), get_points_bounds(), get_pointsize_minmax(), get_reparse_block(), get_reparse_point(), get_selection_rect(), get_subvol_path(), get_tag_desc(), get_target_info(), get_texture_matrix(), get_valid_rects(), GetAcceptLanguagesW(), CUSBDevice::GetConfigurationDescriptors(), GetCPFileNameFromRegistry(), GetDisplayIdentifier(), GetDllList(), GetEnhMetaFileBits(), GetEnhMetaFileDescriptionA(), GetEnhMetaFileDescriptionW(), GetEnhMetaFileHeader(), GetFileVersionInfoExW(), GetFontFamilyInfoForList(), GetFontFamilyInfoForSubstitutes(), GetGeoInfoW(), getit(), GetModuleFileNameA(), GetModuleFileNameW(), GetNamedPipeHandleStateW(), CBDADeviceControl::GetNodeDescriptors(), CBDADeviceControl::GetNodeInterfaces(), GetOutlineTextMetricsA(), GetOutlineTextMetricsW(), GetStartSpoolDate(), GetSystemPaletteEntries(), GetTempPathW(), GetThemeDocumentationProperty(), GetVolumeNameForVolumeMountPointA(), GlobalMemoryStatus(), GlobalMemoryStatusEx(), glsl_fragment_pipe_get_caps(), gray_convert_glyph(), GreGetDIBitsInternal(), GreGetSetColorTable(), GreGradientFill(), GROUP_GroupWndProc(), GuiConsoleHandleScroll(), GuiConsoleReadUserSettings(), GuiConsoleShowConsoleProperties(), GuiConsoleUpdateSelection(), GuiInitFrontEnd(), gxv_kern_subtable_fmt3_validate(), HalInitializeBios(), HalpExecuteIrqs(), handle_batch_collision(), handle_read(), HandleHorizontalScrollEvents(), HandleMouseScrollEvents(), HandleVerticalScrollEvents(), hash_table_destroy(), HEADER_ChangeItemOrder(), HEXEDIT_HEM_COPYBUFFER(), HEXEDIT_IndexFromPoint(), HEXEDIT_PaintLines(), HGLOBALLockBytesImpl_ReadAt(), HidD_Hello(), HidInternalDeviceControl(), HidParser_GetScaledUsageValueWithReport(), HidParser_GetUsageValueWithReport(), HidUsb_GetReportDescriptor(), HistoryRecallHistory(), HLPFILE_BrowsePage(), HLPFILE_DoReadHlpFile(), HLPFILE_ReadFont(), HLPFILE_RtfAddHexBytes(), HLPFILE_Uncompress_Topic(), hsl_to_x(), HTTPREQ_Read(), HTTPREQ_ReadFile(), IAVIFile_fnInfo(), IAVIStream_fnInfo(), IAVIStream_fnRead(), IAVIStream_fnReadData(), IAVIStream_fnReadFormat(), ICMStream_fnInfo(), ICMStream_fnReadFormat(), IdeReadWrite(), IDirectMusicCollectionImpl_EnumInstrument(), IEditAVIStream_fnInfo(), IEditAVIStream_fnReadFormat(), IEnumFiltersImpl_Next(), IEnumMediaTypesImpl_Next(), IEnumRegFiltersImpl_Next(), if(), IFileDialog2_fnSetFileTypeIndex(), ImageList_Add(), ImageList_DragMove(), ImageList_Read(), ImageList_SetImageCount(), import_private_key_impl(), InbvDriverInitialize(), InbvIndicateProgress(), inflate_table(), CUSBRequest::InitDescriptor(), InitExeName(), InitializePool(), InitializePrintProvidor(), InitMatrixMessage(), basic_string< char, char_traits< char >, allocator< char > >::insert(), insert_chunk_fragmented(), insert_extent(), insert_prealloc_extent(), IntCreateNewRegistryPath(), IntDefWindowProc(), IntEngBitBlt(), IntEngGradientFillRect(), IntEngGradientFillTriangle(), IntEngLineTo(), IntEngPolyline(), InternetCrackUrlW(), IntersectRect(), IntFindWindow(), IntGdiLineTo(), IntGdiPolygon(), IntGetConsoleAliasesExes(), IntGetMenuItemInfo(), IntGetMonitorsFromRect(), IntHideMousePointer(), IntMapWindowPoints(), IntPaintDesktop(), IntReadConsoleOutput(), IntRectangle(), IntShowMousePointer(), IntWriteConsoleOutput(), IopLogWorker(), is_comctl32_class(), is_cp_event(), is_float(), is_integer(), is_name(), is_string(), iterator_frameditems_absolute(), ITmpFile_fnInfo(), jsstr_cmp(), jsstr_cmp_str(), K32LoadStringW(), KdbpCliInit(), KdbpCmdDisassembleX(), KdbpReadCommand(), KdbpSymUnicodeToAnsi(), KdpPrint(), KdpPrompt(), KdpPromptString(), KdpReportCommandStringStateChange(), KdpSysReadControlSpace(), KdpSysWriteControlSpace(), KeBugCheckUnicodeToAnsi(), KiDeferredReadyThread(), layout_merge_segments(), layout_recall_merge(), LayoutProc(), LineInputKeyDown(), LineInputRecallHistory(), LISTBOX_FindFileStrPos(), LISTBOX_FindStringPos(), LISTBOX_HandleMouseWheel(), LISTBOX_MoveCaret(), ListBoxWndProc_common(), LISTVIEW_AddGroupSelection(), LISTVIEW_FindItemW(), LISTVIEW_GetItemMetrics(), LISTVIEW_InsertColumnT(), LISTVIEW_InsertItemT(), LISTVIEW_MouseMove(), LISTVIEW_MouseWheel(), LISTVIEW_RedrawItems(), LISTVIEW_ScrollColumns(), LISTVIEW_ScrollTimer(), LISTVIEW_SetGroupSelection(), LISTVIEW_SetItemCount(), load_chunk_root(), load_csum(), load_cube_texture_from_dds(), load_texture_from_dds(), load_volume_texture_from_dds(), LoadShellLinkConsoleInfo(), LoadStringW(), log_file(), lookup_style_tbl(), loose_hex_to_rgb(), LPropCompareProp(), LsapLoadString(), LsapLoadStringEx(), lstrncmpiW(), lznt1_decompress(), lzo_decompress(), lzo_write_compressed_bit(), MapWindowPoints(), Math_min(), max_lookup_components(), max_putfh_components(), max_read_size(), _String_base< _Tp, _Alloc >::max_size(), max_write_size(), mbtowc(), MCICDA_Play(), MCICDA_playLoop(), ME_ApplyStyle(), ME_DrawParagraph(), ME_GetRunSizeCommon(), ME_GetTextEx(), ME_GetTextW(), ME_HandleMessage(), ME_InternalDeleteText(), ME_MoveCaret(), ME_ProtectPartialTableDeletion(), ME_ReadFromRTFString(), ME_RTFSpecialCharHook(), ME_RunOfsFromCharOfs(), ME_ScrollAbs(), ME_StreamOutHexData(), ME_StreamOutMove(), ME_StreamOutRTFText(), ME_StreamOutText(), measure_ranges_callback(), MetadataHandlerEnum_Next(), METAFILE_GraphicsDeleted(), MiBuildPagedPool(), midiInGetDevCapsA(), midiOutGetDevCapsA(), MiInitializeMemoryEvents(), MiInitializeNonPagedPoolThresholds(), MiInsertVadEx(), MiLoadImageSection(), MinTest::min1(), MinTest::min2(), AlgTest::min_max(), MiReloadBootLoadedDrivers(), mixerGetDevCapsA(), MmArmInitSystem(), MmInitializeProcessAddressSpace(), MMIO_ParseExtA(), MMixerAddMixerControl(), MMixerAddMixerControlsToMixerLineByNodeIndexArray(), MMixerBuildMixerSourceLine(), MMixerCreateDestinationLine(), MMixerGetDeviceName(), MMixerGetDeviceNameWithComponentId(), MmSplitRegion(), MMSYSTEM_MidiStream_MessageHandler(), SelectionModel::ModifyDestRect(), modtime(), module_fill_module(), mount_vol(), MsfsRead(), MSI_RecordGetStringW(), msi_strcpy_to_awstring(), MSRLE32_CompressRLE4(), MSRLE32_CompressRLE4Line(), MSRLE32_CompressRLE8(), MSRLE32_CompressRLE8Line(), MSSTYLES_GetNextToken(), MSSTYLES_GetPropertyString(), MSSTYLES_OpenThemeClass(), MSSTYLES_ParseIniSectionName(), MSSTYLES_ParseThemeIni(), msvcrt_init_io(), MyAllocatePool(), NdisOpenConfigurationKeyByIndex(), near_match(), nearest_texel_location(), NetBTAstat(), NetBTEnum(), NetBTFindName(), NetBTNodeStatusAnswerCallback(), NetBTWaitForNameResponse(), NETCON_recv(), NETCON_send(), netconn_drain_content(), netconn_read(), netconn_recv(), netconn_send(), nfs41_create_session(), nfs41_GetReparsePoint(), NoStatStreamImpl_Read(), NtfsDiskRead(), NtfsGetNameInformation(), NtfsGetVolumeData(), NtfsReadAttribute(), NtGdiDoPalette(), NtGdiExtGetObjectW(), NtGdiGetBitmapBits(), NtGdiGetBoundsRect(), NtGdiGetFontResourceInfoInternalW(), NtGdiGetTextFaceW(), NtGdiSetDIBitsToDeviceInternal(), NtUserChangeDisplaySettings(), NtUserCreateWindowEx(), NtUserEnumDisplayDevices(), NtUserEnumDisplayMonitors(), NtUserEnumDisplaySettings(), NtUserFindWindowEx(), NtUserInternalGetWindowText(), NumPutGetTest::num_put_float(), nvrc_fragment_get_caps(), ok_path(), CMainWindow::OnLink(), CUiSplitPanel::OnParentSize(), CMenuBand::OnPosRectChangeDB(), OnScroll(), CGridView::OnVScroll(), OnVScroll(), open_fcb(), OpenType_GetFontScriptTags(), OptionsProc(), OutputResult(), StartMenuRoot::Paint(), PaintStaticControls(), PALOBJ_cGetColors(), parse_ctab_constant_type(), parse_encoding_name(), parse_vertex_colors(), ParseMinMaxQuantifier(), partial_stripe_read(), patch_offset_get_filepatches(), patch_offset_get_files(), patch_offset_modify_db(), PATH_RoundRect(), pattern_bytes_transferred(), pattern_join(), pcf_cmap_char_index(), pcf_cmap_char_next(), PciDebugDumpQueryCapabilities(), PcMemGetMemoryMap(), pfr_cmap_char_index(), pfr_cmap_char_next(), pfr_lookup_bitmap_data(), PinCaptureProcess(), PinWaveCyclicDataFormat(), PinWavePciDataFormat(), POLYGONFILL_FillScanLineWinding(), POLYGONFILL_UpdateScanline(), PopFlushVolumes(), PopupError(), pqExtractMin(), prepare_dc(), prepare_raid0_write(), prepare_raid10_write(), prepare_raid5_write(), prepare_raid6_write(), PrintDiskData(), PRINTDLG_PagePaintProc(), PrintPartitionData(), proc_PlaySound(), PROGRESS_Draw(), PropertyBag_GetPropertyInfo(), PropertyHandler_Level(), PROPSHEET_CollectSheetInfoA(), PROPSHEET_CollectSheetInfoW(), PROPSHEET_Paint(), PropStgNameToFmtId(), ProtocolHandler_Read(), ProtocolSinkHandler_ReportData(), PxeOpen(), qsort(), query_dir_item(), query_internal_format(), query_ranges(), QueryCygwinSymlink(), QueryDosDeviceA(), QueryRoutine(), random_sample_n(), ranges_add(), ranges_shift(), rationalize_extents(), RawChannelIRead(), RawCodecUncompress(), read_blob_wrapper(), read_data(), read_data_raid5(), read_data_raid6(), read_file(), read_from_mds(), read_group_mappings(), read_line(), read_mappings(), read_registry(), read_send_buffer(), read_ssl_chunk(), read_text_callback(), ReadAttribute(), ReadExtraChunk(), ReadLogBuffer(), basic_istream< _CharT, _Traits >::readsome(), RealDefWindowProcA(), RealDefWindowProcW(), ReAllocate(), ReallocSplMem(), REBAR_NCCalcSize(), RECTL_bIntersectRect(), RECTL_bUnionRect(), refill_buffer(), RegEnumKey(), RegEnumKeyExW(), RegEnumValueW(), RegGetSZ(), REGION_CropRegion(), REGION_IntersectO(), REGION_RegionOp(), REGION_SetPolyPolygonRgn(), REGION_UnionRegion(), registry_load_volume_options(), RegQueryInfoKeyW(), RegQueryValueExW(), RegTGetStringValue(), RepGetValueData(), basic_string< char, char_traits< char >, allocator< char > >::replace(), reset_subkeys(), ResizeTextConsole(), ResizeWnd(), CQueryAssociations::ReturnString(), basic_string< _CharT, _Traits, _Alloc >::rfind(), RfsdReadInode(), ropes_cmp(), round_child_height(), RpnpParseExpression(), RQueryServiceConfig2A(), RQueryServiceConfig2W(), RTFPutUnicodeString(), RtlAddAce(), RtlCompareString(), RtlCompareUnicodeString(), RtlCopyMemoryStreamTo(), RtlCopyString(), RtlCopyUnicodeString(), RtlFindClearBits(), RtlFindLastBackwardRunClear(), RtlFindSetBits(), RtlGetVersion(), RtlIsTextUnicode(), RtlpCompressBufferLZNT1(), RtlpGetLengthOfRunClear(), RtlpGetLengthOfRunSet(), RtlQueryEnvironmentVariable_U(), RtlReadMemoryStream(), RtlReadOutOfProcessMemoryStream(), RtlUpperString(), s_echo_ranged_int(), s_get_name(), s_mp_add(), s_mp_sub(), SampLoadString(), ScmAssignNewTag(), ScmSetFailureActions(), scrollbar_test_default(), scrub_chunk(), scrub_chunk_raid56_stripe_run(), scrub_extent_raid0(), scrub_extent_raid10(), SecondaryDirectSoundBuffer8Impl_fnLock(), select_server(), CBrandBand::SelectImage(), send_disks_pnp_message(), set(), stdio_streambuf_base::setbuf(), basic_stringbuf< _CharT, _Traits, _Alloc >::setbuf(), SetDeviceDetails(), SelectionModel::SetSrcAndDestRectFromPoints(), SetUpAppName(), SetUpConsoleInfo(), shader_arb_get_caps(), shader_arb_load_constants_f(), shader_generate_arb_declarations(), shader_generate_glsl_declarations(), shader_get_registers_used(), shader_glsl_generate_pshader(), shader_glsl_generate_sm4_output_setup(), shader_glsl_generate_vs3_rasterizer_input_setup(), shader_glsl_get_caps(), shader_glsl_pointsize_uniform(), shader_record_register_usage(), shift_item(), show_export_ui(), ShowFailureActions(), simple_server(), SmallBlockChainStream_ReadAt(), SmallBlockChainStream_Shrink(), SmallBlockChainStream_WriteAt(), SmLookupSubsystem(), SnmpUtilOidNCmp(), SOFTPUB_HashPEFile(), SOFTWARE_GdipDrawDriverString(), SOFTWARE_GdipDrawThinPath(), SpiGetSet(), SpiGetSetProbeBuffer(), start_balance(), START_TEST(), StartClients(), state_psizemin_arb(), state_psizemin_ext(), state_psizemin_w(), StdMediaSample2_GetProperties(), StdMediaSample2_SetProperties(), sti_compar(), Storage32Impl_BigBlocksToSmallBlocks(), Storage32Impl_SmallBlocksToBigBlocks(), StorageBaseImpl_CopyStream(), StoreNameInSft(), stream_Read(), StreamOnMemory_Read(), strstreambuf::strstreambuf(), stub_manager_ext_addref(), stub_manager_ext_release(), SubstituteVars(), SymEnumTypes(), SymGetSymFromAddr(), SymGetSymFromAddr64(), SymGetSymFromName(), SymGetSymFromName64(), symt_fill_sym_info(), symt_new_array(), SynthPortImpl_IDirectMusicPort_GetFormat(), SYSLINK_AppendDocItem(), SYSLINK_ParseText(), SYSLINK_SetItem(), T1_Get_Kerning(), tcp_initialize_rcv_mss(), tcp_moderate_sndbuf(), tcp_recv(), tcp_select_initial_window(), tcp_send(), test_aligned_offset_realloc(), test_aligned_realloc(), test_Alloc(), test_async_read(), test_boundsrect(), Test_CommandLine(), test_decodeExtensions(), test_decodeNameValue(), test_decodeSequenceOfAny(), test_EM_GETLINE(), test_encoder_properties(), test_float_limits(), test_format_rect(), test_fullscreen(), test_GetLargestConsoleWindowSize(), test_GetPwrDiskSpindownRange(), test_GetSystemMetrics(), test_hv_scroll_2(), test_integral_limits(), test_integral_limits_base(), test_marshal_CLIPFORMAT(), test_media_streams(), test_moniker(), test_not_full(), test_pen_thickness(), test_persist_save_data(), test_QueryPathOfRegTypeLib(), test_reader_info(), test_scroll(), test_scroll_messages(), test_sscanf(), test_text_metrics(), TestCommonRead(), TestEventConcurrent(), TestLockBytes_ReadAt(), testScroll(), tex_coordindex(), TEXTMODE_BUFFER_Initialize(), textstream_Read(), texture_apply_base_level(), TH32CreateSnapshotSectionInitialize(), TIME_MMSysTimeCallback(), TOOLBAR_GetStringW(), TOOLBAR_SetPadding(), TOOLTIPS_OnWMGetText(), TransactedSnapshotImpl_Commit(), TransactedSnapshotImpl_DestroyDirEntry(), transform_color(), TREEVIEW_Command(), TREEVIEW_DrawItemLines(), TREEVIEW_EditLabel(), TREEVIEW_SetScrollTime(), try_clone_edr(), try_extend_data(), tt_face_get_kerning(), UDFAddXSpaceBitmap(), UDFCommonWrite(), UDFGetDiskInfo(), UDFIsExtentCached(), UDFMarkNotAllocatedAsAllocated(), UDFPrepareXSpaceBitmap(), UDFReadDiscTrackInfo(), UDFReadExtent(), UDFReadExtentLocation(), UDFRecordVAT(), UDFResizeExtent(), UDFSetAllocDescLen(), UDFSetEOF(), UDFUpdateNonAllocated(), UDFUpdateXSpaceBitmaps(), UDFVerifyPartDesc(), UDFVVerify(), UDFWriteExtent(), UDFZeroExtent(), UniataAhciDetect(), UniataChipDetect(), UniataChipDetectChannels(), UniataQueueRequest(), UnionRect(), UnLslRLine(), update_arrays(), UpdateColumnDataHints(), CPortPinWaveCyclic::UpdateCommonBuffer(), CPortPinWaveCyclic::UpdateCommonBufferOverlap(), CardRegion::UpdateFaceDir(), UpdateSelection(), UpdateWindowScrollState(), UpDownWindowProc(), UrlCompareA(), UrlCompareW(), UrlGetLocationA(), UrlGetLocationW(), UsbAudioGetDataRanges(), USBCCGP_BuildConfigurationDescriptor(), UserClipCursor(), UserDrawCaption(), UXTHEME_LoadImage(), UXTHEME_SelectImage(), UXTHEME_SizedBlt(), Validate_ShimData_Win10(), Validate_ShimData_Win10_v2(), Validate_ShimData_Win7(), VarBstrCmp(), VARIANT_FormatNumber(), verify_window_info(), VfatGetNameInformation(), VfatReadFileData(), VfatWriteFileData(), VGADDI_ComputePointerRect(), VGADDI_IntersectRect(), VGADDI_ShowCursor(), VGADDIIntersectRect(), VgaMarkForUpdate(), VidBiosScrollWindow(), VideoPortDDCMonitorHelper(), VideoPortGetRomImage(), VTUTF8ChannelIRead(), warp_check(), WAVE_mciPlay(), waveInGetDevCapsA(), waveOutGetDevCapsA(), WCacheWriteBlocks__(), wcsncat_s(), wcsncpy_s(), whilePaintingL(), WICMapGuidToShortName(), WICMapSchemaToName(), widGetDevCaps(), wine_dbgstr_an(), wine_dbgstr_wn(), wine_debugstr_an(), wined3d_adapter_init_limits(), wined3d_device_get_available_texture_mem(), wined3d_device_update_texture(), wined3d_get_adapter_identifier(), wined3d_query_get_data(), wined3d_sampler_desc_from_sampler_states(), wined3d_swapchain_apply_sample_count_override(), WINHELP_GetPopupWindowInfo(), winsizes_wnd_proc(), wmain(), WndProc(), wodGetDevCaps(), wpp_read_mem(), write_compressed(), write_file2(), write_output_buffer(), write_stream(), write_to_mds(), WriteLogBuffer(), x86_64_find_runtime_function(), XLATEOBJ_cGetPalette(), xmlreader_ReadValueChunk(), basic_streambuf< _CharT, _Traits >::xsgetn(), basic_streambuf< _CharT, _Traits >::xsputn(), zero_data(), and zoomTo().

Function Documentation

static int compChainHeadInY ( monoChain mc1,
monoChain mc2 
)
static

Definition at line 85 of file monoChain.cc.

Referenced by MC_partitionY().

86 {
87  return compV2InY(mc1->getHead()->head(), mc2->getHead()->head());
88 }
Real * head()
Int compV2InY(Real A[2], Real B[2])
directedLine * getHead()
Definition: monoChain.h:66
Int compChains ( monoChain mc1,
monoChain mc2 
)

Definition at line 376 of file monoChain.cc.

Referenced by MC_sweepY().

377 {
378  Real y;
379  assert(mc1->isKey || mc2->isKey);
380  if(mc1->isKey)
381  y = mc1->keyY;
382  else
383  y = mc2->keyY;
384  directedLine *d1 = mc1->find(y);
385  directedLine *d2 = mc2->find(y);
386  mc2->find(y);
387 // Real x1 = mc1->chainIntersectHoriz(y);
388 // Real x2 = mc2->chainIntersectHoriz(y);
389  return compEdges(d1, d2);
390 }
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: monoChain.cc:296
#define assert(x)
Definition: debug.h:53
Real keyY
Definition: monoChain.h:83
Int isKey
Definition: monoChain.h:82
directedLine * find(Real y)
Definition: monoChain.cc:393
float Real
Definition: definitions.h:36
INT INT y
Definition: msvc.h:62
static Int compEdges ( directedLine e1,
directedLine e2 
)
static

Definition at line 296 of file monoChain.cc.

Referenced by compChains(), and MC_findDiagonals().

297 {
298  Real* head1 = e1->head();
299  Real* tail1 = e1->tail();
300  Real* head2 = e2->head();
301  Real* tail2 = e2->tail();
302 /*
303  Real h10 = head1[0];
304  Real h11 = head1[1];
305  Real t10 = tail1[0];
306  Real t11 = tail1[1];
307  Real h20 = head2[0];
308  Real h21 = head2[1];
309  Real t20 = tail2[0];
310  Real t21 = tail2[1];
311 */
312  Real e1_Ymax, e1_Ymin, e2_Ymax, e2_Ymin;
313 /*
314  if(h11>t11) {
315  e1_Ymax= h11;
316  e1_Ymin= t11;
317  }
318  else{
319  e1_Ymax = t11;
320  e1_Ymin = h11;
321  }
322 
323  if(h21>t21) {
324  e2_Ymax= h21;
325  e2_Ymin= t21;
326  }
327  else{
328  e2_Ymax = t21;
329  e2_Ymin = h21;
330  }
331 */
332 
333  if(head1[1]>tail1[1]) {
334  e1_Ymax= head1[1];
335  e1_Ymin= tail1[1];
336  }
337  else{
338  e1_Ymax = tail1[1];
339  e1_Ymin = head1[1];
340  }
341 
342  if(head2[1]>tail2[1]) {
343  e2_Ymax= head2[1];
344  e2_Ymin= tail2[1];
345  }
346  else{
347  e2_Ymax = tail2[1];
348  e2_Ymin = head2[1];
349  }
350 
351 
352  /*Real e1_Ymax = max(head1[1], tail1[1]);*/ /*max(e1->head()[1], e1->tail()[1]);*/
353  /*Real e1_Ymin = min(head1[1], tail1[1]);*/ /*min(e1->head()[1], e1->tail()[1]);*/
354  /*Real e2_Ymax = max(head2[1], tail2[1]);*/ /*max(e2->head()[1], e2->tail()[1]);*/
355  /*Real e2_Ymin = min(head2[1], tail2[1]);*/ /*min(e2->head()[1], e2->tail()[1]);*/
356 
357  Real Ymax = min(e1_Ymax, e2_Ymax);
358  Real Ymin = max(e1_Ymin, e2_Ymin);
359 
360  Real y = 0.5*(Ymax + Ymin);
361 
362 /* Real x1 = intersectHoriz(e1->head()[0], e1->head()[1], e1->tail()[0], e1->tail()[1], y);
363  Real x2 = intersectHoriz(e2->head()[0], e2->head()[1], e2->tail()[0], e2->tail()[1], y);
364 */
365 /*
366  Real x1 = intersectHoriz(h10, h11, t10, t11, y);
367  Real x2 = intersectHoriz(h20, h21, t20, t21, y);
368 */
369  Real x1 = intersectHoriz(head1[0], head1[1], tail1[0], tail1[1], y);
370  Real x2 = intersectHoriz(head2[0], head2[1], tail2[0], tail2[1], y);
371 
372  if(x1<= x2) return -1;
373  else return 1;
374 }
Real * head()
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
Definition: monoChain.cc:79
#define max(a, b)
Definition: monoChain.cc:52
Real * tail()
#define min(a, b)
Definition: monoChain.cc:55
float Real
Definition: definitions.h:36
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG x2
Definition: winddi.h:3706
INT INT y
Definition: msvc.h:62
Int deleteRepeatDiagonals ( Int  num_diagonals,
directedLine **  diagonal_vertices,
directedLine **  new_vertices 
)

Definition at line 386 of file partitionY.cc.

Referenced by DBGfindDiagonals(), MC_partitionY(), and partitionY().

387 {
388  Int i,k;
389  Int j,l;
390  Int index;
391  index=0;
392  for(i=0,k=0; i<num_diagonals; i++, k+=2)
393  {
394  Int isRepeated=0;
395  /*check the diagonla (diagonal_vertice[k], diagonal_vertices[k+1])
396  *is repeated or not
397  */
398  for(j=0,l=0; j<index; j++, l+=2)
399  {
400  if(
401  (diagonal_vertices[k] == new_vertices[l] &&
402  diagonal_vertices[k+1] == new_vertices[l+1]
403  )
404  ||
405  (
406  diagonal_vertices[k] == new_vertices[l+1] &&
407  diagonal_vertices[k+1] == new_vertices[l]
408  )
409  )
410  {
411  isRepeated=1;
412  break;
413  }
414  }
415  if(! isRepeated)
416  {
417  new_vertices[index+index] = diagonal_vertices[k];
418  new_vertices[index+index+1] = diagonal_vertices[k+1];
419  index++;
420  }
421  }
422  return index;
423 }
GLenum GLclampf GLint GLenum GLuint GLenum GLenum GLsizei GLenum const GLvoid GLfloat GLfloat GLfloat GLfloat GLclampd GLint GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean GLboolean GLboolean GLboolean GLint GLenum GLsizei const GLvoid GLenum GLint GLenum GLint GLint GLsizei GLint GLenum GLint GLint GLint GLint GLsizei GLenum GLsizei const GLuint GLboolean GLenum GLenum GLint GLsizei GLenum GLsizei GLenum const GLvoid GLboolean const GLboolean GLenum const GLdouble const GLfloat const GLdouble const GLfloat GLenum GLint GLint GLint GLint GLint GLint j
Definition: glfuncs.h:98
GLenum GLclampf GLint i
Definition: glfuncs.h:14
r l[0]
Definition: byte_order.h:167
#define index(s, c)
Definition: various.h:29
int k
Definition: mpi.c:3369
int Int
Definition: definitions.h:37
monoChain* directedLineLoopListToMonoChainLoopList ( directedLine list)

Definition at line 273 of file monoChain.cc.

Referenced by MC_partitionY().

274 {
276  monoChain* mc;
277  monoChain* mcEnd;
279  mcEnd = mc;
280  for(temp = list->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
281  {
283  mcEnd->setNextPolygon(newLoop);
284  mcEnd = newLoop;
285  }
286  return mc;
287 }
monoChain * directedLineLoopToMonoChainLoop(directedLine *loop)
Definition: monoChain.cc:232
smooth NULL
Definition: ftsmooth.c:513
static stack_node_t temp
Definition: rpn.c:18
void setNextPolygon(monoChain *np)
Definition: monoChain.h:63
directedLine * getNextPolygon()
Definition: directedLine.h:75
monoChain* directedLineLoopToMonoChainLoop ( directedLine loop)

Definition at line 232 of file monoChain.cc.

Referenced by directedLineLoopListToMonoChainLoopList().

233 {
235  monoChain *ret=NULL;
236 
237  //find the first cusp
238  directedLine *prevCusp=NULL;
239  directedLine *firstCusp;
240 
241  if(isCusp(loop))
242  prevCusp = loop;
243  else
244  {
245  for(temp = loop->getNext(); temp != loop; temp = temp->getNext())
246  if(isCusp(temp))
247  break;
248  prevCusp = temp;
249  }
250  firstCusp = prevCusp;
251 //printf("first cusp is (%f,%f), (%f,%f), (%f,%f)\n", prevCusp->getPrev()->head()[0], prevCusp->getPrev()->head()[1], prevCusp->head()[0], prevCusp->head()[1], prevCusp->tail()[0], prevCusp->tail()[1]);
252 
253  for(temp = prevCusp->getNext(); temp != loop; temp = temp->getNext())
254  {
255  if(isCusp(temp))
256  {
257 //printf("the cusp is (%f,%f), (%f,%f), (%f,%f)\n", temp->getPrev()->head()[0], temp->getPrev()->head()[1], temp->head()[0], temp->head()[1], temp->tail()[0], temp->tail()[1]);
258  if(ret == NULL)
259  {
260  ret = new monoChain(prevCusp, temp);
261  }
262  else
263  ret->insert(new monoChain(prevCusp, temp));
264  prevCusp = temp;
265  }
266  }
267  assert(ret);
268  ret->insert(new monoChain(prevCusp, firstCusp));
269 
270  return ret;
271 }
VARIANT loop
#define assert(x)
Definition: debug.h:53
directedLine * getNext()
Definition: directedLine.h:74
smooth NULL
Definition: ftsmooth.c:513
int ret
static stack_node_t temp
Definition: rpn.c:18
Int isCusp(directedLine *v)
Definition: partitionY.cc:100
void insert(monoChain *nc)
Definition: monoChain.cc:134
Real intersectHoriz ( Real  x1,
Real  y1,
Real  x2,
Real  y2,
Real  y 
)
inline

Definition at line 79 of file monoChain.cc.

Referenced by monoChain::chainIntersectHoriz(), and compEdges().

80 {
81  return ((y2==y1)? (x1+x2)*0.5 : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
82 }
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG y1
Definition: winddi.h:3706
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG _In_ LONG y2
Definition: winddi.h:3706
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG x2
Definition: winddi.h:3706
INT INT y
Definition: msvc.h:62
Int isCusp ( directedLine v)

Definition at line 100 of file partitionY.cc.

Referenced by cuspType(), and directedLineLoopToMonoChainLoop().

101 {
102  Real *A=v->getPrev()->head();
103  Real *B=v->head();
104  Real *C=v->tail();
105  if(A[1] < B[1] && B[1] < C[1])
106  return 0;
107  else if(A[1] > B[1] && B[1] > C[1])
108  return 0;
109  else if(A[1] < B[1] && C[1] < B[1])
110  return 1;
111  else if(A[1] > B[1] && C[1] > B[1])
112  return 1;
113 
114  if((isAbove(v, v) && isAbove(v, v->getPrev())) ||
115  (isBelow(v, v) && isBelow(v, v->getPrev())))
116  return 1;
117  else
118  return 0;
119 }
Real * head()
Int isBelow(directedLine *v, directedLine *e)
Definition: partitionY.cc:73
directedLine * getPrev()
Definition: directedLine.h:73
Definition: ttei1.cpp:12
Int isAbove(directedLine *v, directedLine *e)
Definition: partitionY.cc:89
Real * tail()
Definition: bidi.c:91
Definition: ttei6.cpp:27
float Real
Definition: definitions.h:36
void MC_findDiagonals ( Int  total_num_edges,
monoChain **  sortedVertices,
sweepRange **  ranges,
Int num_diagonals,
directedLine **  diagonal_vertices 
)

Definition at line 567 of file monoChain.cc.

Referenced by MC_partitionY().

570 {
571  Int i,j,k;
572  k=0;
573  //reset 'current' of all the monoChains
574  for(i=0; i<total_num_edges; i++)
575  sortedVertices[i]->resetCurrent();
576 
577  for(i=0; i<total_num_edges; i++)
578  {
579  directedLine* vert = sortedVertices[i]->getHead();
580  directedLine* thisEdge = vert;
581  directedLine* prevEdge = vert->getPrev();
582  if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
583  {
584  //this is an upward interior cusp
585  diagonal_vertices[k++] = vert;
586 
587  directedLine* leftEdge = ranges[i]->left;
588  directedLine* rightEdge = ranges[i]->right;
589 
590  directedLine* leftVert = leftEdge;
591  directedLine* rightVert = rightEdge->getNext();
592  assert(leftVert->head()[1] >= vert->head()[1]);
593  assert(rightVert->head()[1] >= vert->head()[1]);
594  directedLine* minVert = (leftVert->head()[1] <= rightVert->head()[1])?leftVert:rightVert;
595  Int found = 0;
596  for(j=i+1; j<total_num_edges; j++)
597  {
598  if(sortedVertices[j]->getHead()->head()[1] > minVert->head()[1])
599  break;
600 
601  if(sweepRangeEqual(ranges[i], ranges[j]))
602  {
603  found = 1;
604  break;
605  }
606  }
607 
608  if(found)
609  diagonal_vertices[k++] = sortedVertices[j]->getHead();
610  else
611  diagonal_vertices[k++] = minVert;
612  }
613  else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
614  {
615  //downward interior cusp
616  diagonal_vertices[k++] = vert;
617  directedLine* leftEdge = ranges[i]->left;
618  directedLine* rightEdge = ranges[i]->right;
619  directedLine* leftVert = leftEdge->getNext();
620  directedLine* rightVert = rightEdge;
621  assert(leftVert->head()[1] <= vert->head()[1]);
622  assert(rightVert->head()[1] <= vert->head()[1]);
623  directedLine* maxVert = (leftVert->head()[1] > rightVert->head()[1])? leftVert:rightVert;
624  Int found=0;
625  for(j=i-1; j>=0; j--)
626  {
627  if(sortedVertices[j]->getHead()->head()[1] < maxVert->head()[1])
628  break;
629  if(sweepRangeEqual(ranges[i], ranges[j]))
630  {
631  found = 1;
632  break;
633  }
634  }
635  if(found)
636  diagonal_vertices[k++] = sortedVertices[j]->getHead();
637  else
638  diagonal_vertices[k++] = maxVert;
639  }
640  }
641  num_diagonals = k/2;
642 }
directedLine * right
Definition: partitionY.h:73
GLenum GLclampf GLint GLenum GLuint GLenum GLenum GLsizei GLenum const GLvoid GLfloat GLfloat GLfloat GLfloat GLclampd GLint GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean GLboolean GLboolean GLboolean GLint GLenum GLsizei const GLvoid GLenum GLint GLenum GLint GLint GLsizei GLint GLenum GLint GLint GLint GLint GLsizei GLenum GLsizei const GLuint GLboolean GLenum GLenum GLint GLsizei GLenum GLsizei GLenum const GLvoid GLboolean const GLboolean GLenum const GLdouble const GLfloat const GLdouble const GLfloat GLenum GLint GLint GLint GLint GLint GLint j
Definition: glfuncs.h:98
Real * head()
Int isBelow(directedLine *v, directedLine *e)
Definition: partitionY.cc:73
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: monoChain.cc:296
#define assert(x)
Definition: debug.h:53
directedLine * getPrev()
Definition: directedLine.h:73
GLenum GLclampf GLint i
Definition: glfuncs.h:14
directedLine * getNext()
Definition: directedLine.h:74
Int isAbove(directedLine *v, directedLine *e)
Definition: partitionY.cc:89
directedLine * left
Definition: partitionY.h:71
directedLine * getHead()
Definition: monoChain.h:66
Int sweepRangeEqual(sweepRange *src1, sweepRange *src2)
Definition: partitionY.cc:167
int k
Definition: mpi.c:3369
int Int
Definition: definitions.h:37
directedLine* MC_partitionY ( directedLine polygons,
sampledLine **  retSampledLines 
)

Definition at line 647 of file monoChain.cc.

Referenced by Subdivider::drawSurfaces().

648 {
649 //printf("enter mc_partitionY\n");
650  Int total_num_chains = 0;
652  monoChain** array = loopList->toArrayAllLoops(total_num_chains);
653 
654  if(total_num_chains<=2) //there is just one single monotone polygon
655  {
656  loopList->deleteLoopList();
657  free(array);
658  *retSampledLines = NULL;
659  return polygons;
660  }
661 
662 //loopList->printAllLoops();
663 //printf("total_num_chains=%i\n", total_num_chains);
664  quicksort( (void**)array, 0, total_num_chains-1, (Int (*)(void*, void*))compChainHeadInY);
665 //printf("after quicksort\n");
666 
667  sweepRange** ranges = (sweepRange**)malloc(sizeof(sweepRange*) * (total_num_chains));
668  assert(ranges);
669 
670  if(MC_sweepY(total_num_chains, array, ranges))
671  {
672  loopList->deleteLoopList();
673  free(array);
674  *retSampledLines = NULL;
675  return NULL;
676  }
677 //printf("after MC_sweepY\n");
678 
679 
680  Int num_diagonals;
681  /*number diagonals is < total_num_edges*total_num_edges*/
682  directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_chains*2/*total_num_edges*/);
683  assert(diagonal_vertices);
684 
685 //printf("before call MC_findDiagonales\n");
686 
687  MC_findDiagonals(total_num_chains, array, ranges, num_diagonals, diagonal_vertices);
688 //printf("after call MC_findDia, num_diagnla=%i\n", num_diagonals);
689 
690  directedLine* ret_polygons = polygons;
691  sampledLine* newSampledLines = NULL;
692  Int i,k;
693 
694  num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
695 
696 
697 
698 //drawDiagonals(num_diagonals, diagonal_vertices);
699 //printf("diagoanls are \n");
700 //for(i=0; i<num_diagonals; i++)
701 // {
702 // printf("(%f,%f)\n", diagonal_vertices[2*i]->head()[0], diagonal_vertices[2*i]->head()[1]);
703 // printf("**(%f,%f)\n", diagonal_vertices[2*i+1]->head()[0], diagonal_vertices[2*i+1]->head()[1]);
704 // }
705 
706  Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals);
707  for(i=0; i<num_diagonals; i++)
708  removedDiagonals[i] = 0;
709 // printf("first pass\n");
710 
711 
712  for(i=0,k=0; i<num_diagonals; i++,k+=2)
713  {
714 
715 
716  directedLine* v1=diagonal_vertices[k];
717  directedLine* v2=diagonal_vertices[k+1];
718  directedLine* ret_p1;
719  directedLine* ret_p2;
720 
721  /*we ahve to determine whether v1 and v2 belong to the same polygon before
722  *their structure are modified by connectDiagonal().
723  */
724 /*
725  directedLine *root1 = v1->findRoot();
726  directedLine *root2 = v2->findRoot();
727  assert(root1);
728  assert(root2);
729 */
730 
731 directedLine* root1 = v1->rootLinkFindRoot();
732 directedLine* root2 = v2->rootLinkFindRoot();
733 
734  if(root1 != root2)
735  {
736 
737  removedDiagonals[i] = 1;
738  sampledLine* generatedLine;
739 
740 
741 
742  v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
743 
744 
745 
746  newSampledLines = generatedLine->insert(newSampledLines);
747 /*
748  ret_polygons = ret_polygons->cutoffPolygon(root1);
749 
750  ret_polygons = ret_polygons->cutoffPolygon(root2);
751  ret_polygons = ret_p1->insertPolygon(ret_polygons);
752 root1->rootLinkSet(ret_p1);
753 root2->rootLinkSet(ret_p1);
754 ret_p1->rootLinkSet(NULL);
755 ret_p2->rootLinkSet(ret_p1);
756 */
757  ret_polygons = ret_polygons->cutoffPolygon(root2);
758 
759 
760 
761 root2->rootLinkSet(root1);
762 ret_p1->rootLinkSet(root1);
763 ret_p2->rootLinkSet(root1);
764 
765  /*now that we have connected the diagonal v1 and v2,
766  *we have to check those unprocessed diagonals which
767  *have v1 or v2 as an end point. Notice that the head of v1
768  *has the same coodinates as the head of v2->prev, and the head of
769  *v2 has the same coordinate as the head of v1->prev.
770  *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid
771  *diagonal, then x should be on the left hand side of the directed line: *v1->prev->head -- v1->head -- v1->tail. Otherwise, (v1,x) should be
772  *replaced by (v2->prev, x), that is, x is on the left of
773  * v2->prev->prev->head, v2->prev->head, v2->prev->tail.
774  */
775  Int ii, kk;
776  for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2)
777  if( removedDiagonals[ii]==0)
778  {
779  directedLine* d1=diagonal_vertices[kk];
780  directedLine* d2=diagonal_vertices[kk+1];
781  /*check d1, and replace diagonal_vertices[kk] if necessary*/
782  if(d1 == v1) {
783  /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/
784  if(! pointLeft2Lines(v1->getPrev()->head(),
785  v1->head(), v1->tail(), d2->head()))
786  {
787 /*
788  assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
789  v2->getPrev()->head(),
790  v2->getPrev()->tail(), d2->head()));
791 */
792  diagonal_vertices[kk] = v2->getPrev();
793  }
794  }
795  if(d1 == v2) {
796  /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/
797  if(! pointLeft2Lines(v2->getPrev()->head(),
798  v2->head(), v2->tail(), d2->head()))
799  {
800 /*
801  assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
802  v1->getPrev()->head(),
803  v1->getPrev()->tail(), d2->head()));
804 */
805  diagonal_vertices[kk] = v1->getPrev();
806  }
807  }
808  /*check d2 and replace diagonal_vertices[k+1] if necessary*/
809  if(d2 == v1) {
810  /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/
811  if(! pointLeft2Lines(v1->getPrev()->head(),
812  v1->head(), v1->tail(), d1->head()))
813  {
814 /* assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
815  v2->getPrev()->head(),
816  v2->getPrev()->tail(), d1->head()));
817 */
818  diagonal_vertices[kk+1] = v2->getPrev();
819  }
820  }
821  if(d2 == v2) {
822  /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/
823  if(! pointLeft2Lines(v2->getPrev()->head(),
824  v2->head(), v2->tail(), d1->head()))
825  {
826 /* assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
827  v1->getPrev()->head(),
828  v1->getPrev()->tail(), d1->head()));
829 */
830  diagonal_vertices[kk+1] = v1->getPrev();
831  }
832  }
833  }
834 }/*end if (root1 not equal to root 2)*/
835 }
836 
837  /*second pass, now all diagoals should belong to the same polygon*/
838 //printf("second pass: \n");
839 
840 // for(i=0; i<num_diagonals; i++)
841 // printf("%i ", removedDiagonals[i]);
842 
843 
844  for(i=0,k=0; i<num_diagonals; i++, k += 2)
845  if(removedDiagonals[i] == 0)
846  {
847 
848 
849  directedLine* v1=diagonal_vertices[k];
850  directedLine* v2=diagonal_vertices[k+1];
851 
852 
853 
854  directedLine* ret_p1;
855  directedLine* ret_p2;
856 
857  /*we ahve to determine whether v1 and v2 belong to the same polygon before
858  *their structure are modified by connectDiagonal().
859  */
860  directedLine *root1 = v1->findRoot();
861 /*
862  directedLine *root2 = v2->findRoot();
863 
864 
865 
866  assert(root1);
867  assert(root2);
868  assert(root1 == root2);
869  */
870  sampledLine* generatedLine;
871 
872 
873 
874  v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
875  newSampledLines = generatedLine->insert(newSampledLines);
876 
877  ret_polygons = ret_polygons->cutoffPolygon(root1);
878 
879  ret_polygons = ret_p1->insertPolygon(ret_polygons);
880 
881  ret_polygons = ret_p2->insertPolygon(ret_polygons);
882 
883 
884 
885  for(Int j=i+1; j<num_diagonals; j++)
886  {
887  if(removedDiagonals[j] ==0)
888  {
889 
890  directedLine* temp1=diagonal_vertices[2*j];
891  directedLine* temp2=diagonal_vertices[2*j+1];
892  if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2)
893  if(! temp1->samePolygon(temp1, temp2))
894  {
895  /*if temp1 and temp2 are in different polygons,
896  *then one of them must be v1 or v2.
897  */
898 
899 
900 
901  assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2);
902  if(temp1==v1)
903  {
904  diagonal_vertices[2*j] = v2->getPrev();
905  }
906  if(temp2==v1)
907  {
908  diagonal_vertices[2*j+1] = v2->getPrev();
909  }
910  if(temp1==v2)
911  {
912  diagonal_vertices[2*j] = v1->getPrev();
913  }
914  if(temp2==v2)
915  {
916  diagonal_vertices[2*j+1] = v1->getPrev();
917  }
918  }
919  }
920  }
921 
922  }
923 
924 
925  //clean up
926  loopList->deleteLoopList();
927  free(array);
928  free(ranges);
929  free(diagonal_vertices);
930  free(removedDiagonals);
931 
932  *retSampledLines = newSampledLines;
933  return ret_polygons;
934 }
void connectDiagonal(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, sampledLine **generatedLine, directedLine *list)
GLenum GLclampf GLint GLenum GLuint GLenum GLenum GLsizei GLenum const GLvoid GLfloat GLfloat GLfloat GLfloat GLclampd GLint GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean GLboolean GLboolean GLboolean GLint GLenum GLsizei const GLvoid GLenum GLint GLenum GLint GLint GLsizei GLint GLenum GLint GLint GLint GLint GLsizei GLenum GLsizei const GLuint GLboolean GLenum GLenum GLint GLsizei GLenum GLsizei GLenum const GLvoid GLboolean const GLboolean GLenum const GLdouble const GLfloat const GLdouble const GLfloat GLenum GLint GLint GLint GLint GLint GLint j
Definition: glfuncs.h:98
void rootLinkSet(directedLine *r)
Definition: directedLine.h:155
Real * head()
static int compChainHeadInY(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:85
#define free
Definition: debug_ros.c:5
void quicksort(void *v[], int left, int right, int(*comp)(void *, void *))
Definition: quicksort.cc:62
#define assert(x)
Definition: debug.h:53
sampledLine * insert(sampledLine *nline)
Definition: sampledLine.cc:53
Int samePolygon(directedLine *v1, directedLine *v2)
directedLine * getPrev()
Definition: directedLine.h:73
GLenum GLclampf GLint i
Definition: glfuncs.h:14
directedLine * insertPolygon(directedLine *newpolygon)
monoChain * directedLineLoopListToMonoChainLoopList(directedLine *list)
Definition: monoChain.cc:273
smooth NULL
Definition: ftsmooth.c:513
void MC_findDiagonals(Int total_num_edges, monoChain **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
Definition: monoChain.cc:567
directedLine * rootLinkFindRoot()
void deleteLoopList()
Definition: monoChain.cc:153
Int MC_sweepY(Int nVertices, monoChain **sortedVertices, sweepRange **ret_ranges)
Definition: monoChain.cc:451
Int deleteRepeatDiagonals(Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
Definition: partitionY.cc:386
Real * tail()
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
Int pointLeft2Lines(Real A[2], Real B[2], Real C[2], Real P[2])
Definition: polyUtil.cc:78
directedLine * cutoffPolygon(directedLine *p)
#define malloc
Definition: debug_ros.c:4
directedLine * findRoot()
GLfloat GLfloat v1
Definition: glext.h:6062
int k
Definition: mpi.c:3369
monoChain ** toArrayAllLoops(Int &num_chains)
Definition: monoChain.cc:174
int Int
Definition: definitions.h:37
Int MC_sweepY ( Int  nVertices,
monoChain **  sortedVertices,
sweepRange **  ret_ranges 
)

Definition at line 451 of file monoChain.cc.

Referenced by MC_partitionY().

452 {
453  Int i;
454  Real keyY;
455  Int errOccur=0;
456 //printf("enter MC_sweepY\n");
457 //printf("nVertices=%i\n", nVertices);
458  /*for each vertex in the sorted list, update the binary search tree.
459  *and store the range information for each vertex.
460  */
461  treeNode* searchTree = NULL;
462 //printf("nVertices=%i\n", nVertices);
463  for(i=0; i<nVertices; i++)
464  {
465  monoChain* vert = sortedVertices[i];
466  keyY = vert->getHead()->head()[1]; //the sweep line
467  directedLine *dline = vert->getHead();
468  directedLine *dlinePrev = dline->getPrev();
469  if(isBelow(dline, dline) && isBelow(dline, dlinePrev))
470  {
471 //printf("case 1\n");
472  //this<v and prev < v
473  //delete both edges
474  vert->isKey = 1;
475  vert->keyY = keyY;
476  treeNode* thisNode = TreeNodeFind(searchTree, vert, (Int (*) (void *, void *))compChains);
477  vert->isKey = 0;
478 
479  vert->getPrev()->isKey = 1;
480  vert->getPrev()->keyY = keyY;
481  treeNode* prevNode = TreeNodeFind(searchTree, vert->getPrev(), (Int (*) (void *, void *))compChains);
482  vert->getPrev()->isKey = 0;
483 
484  if(cuspType(dline) == 1)//interior cusp
485  {
486 
487  treeNode* leftEdge = TreeNodePredecessor(prevNode);
488  treeNode* rightEdge = TreeNodeSuccessor(thisNode);
489  if(leftEdge == NULL || rightEdge == NULL)
490  {
491  errOccur = 1;
492  goto JUMP_HERE;
493  }
494 
495  directedLine* leftEdgeDline = ((monoChain* ) leftEdge->key)->find(keyY);
496 
497 
498 
499  directedLine* rightEdgeDline = ((monoChain* ) rightEdge->key)->find(keyY);
500 
501  ret_ranges[i] = sweepRangeMake(leftEdgeDline, 1, rightEdgeDline, 1);
502  }
503  else /*exterior cusp*/
504  {
505  ret_ranges[i] = sweepRangeMake( dline, 1, dlinePrev, 1);
506  }
507 
508  searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
509  searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
510 
511  }
512  else if(isAbove(dline, dline) && isAbove(dline, dlinePrev))
513  {
514 //printf("case 2\n");
515  //insert both edges
516  treeNode* thisNode = TreeNodeMake(vert);
517  treeNode* prevNode = TreeNodeMake(vert->getPrev());
518 
519  vert->isKey = 1;
520  vert->keyY = keyY;
521  searchTree = TreeNodeInsert(searchTree, thisNode, (Int (*) (void *, void *))compChains);
522  vert->isKey = 0;
523 
524  vert->getPrev()->isKey = 1;
525  vert->getPrev()->keyY = keyY;
526  searchTree = TreeNodeInsert(searchTree, prevNode, (Int (*) (void *, void *))compChains);
527  vert->getPrev()->isKey = 0;
528 
529  if(cuspType(dline) == 1) //interior cusp
530  {
531 //printf("cuspType is 1\n");
532  treeNode* leftEdge = TreeNodePredecessor(thisNode);
533  treeNode* rightEdge = TreeNodeSuccessor(prevNode);
534  if(leftEdge == NULL || rightEdge == NULL)
535  {
536  errOccur = 1;
537  goto JUMP_HERE;
538  }
539 //printf("leftEdge is %i, rightEdge is %i\n", leftEdge, rightEdge);
540  directedLine* leftEdgeDline = ((monoChain*) leftEdge->key)->find(keyY);
541  directedLine* rightEdgeDline = ((monoChain*) rightEdge->key)->find(keyY);
542  ret_ranges[i] = sweepRangeMake( leftEdgeDline, 1, rightEdgeDline, 1);
543  }
544  else //exterior cusp
545  {
546 //printf("cuspType is not 1\n");
547  ret_ranges[i] = sweepRangeMake(dlinePrev, 1, dline, 1);
548  }
549  }
550  else
551  {
552 //printf("%i,%i\n", isAbove(dline, dline), isAbove(dline, dlinePrev));
553  errOccur = 1;
554  goto JUMP_HERE;
555 
556  fprintf(stderr, "error in MC_sweepY\n");
557  exit(1);
558  }
559  }
560 
561  JUMP_HERE:
562  //finally clean up space: delete the search tree
563  TreeNodeDeleteWholeTree(searchTree);
564  return errOccur;
565 }
treeNode * TreeNodeMake(void *key)
Definition: searchTree.cc:46
monoChain * getPrev()
Definition: monoChain.h:65
Real * head()
Int isBelow(directedLine *v, directedLine *e)
Definition: partitionY.cc:73
Real keyY
Definition: monoChain.h:83
directedLine * getPrev()
Definition: directedLine.h:73
Int isKey
Definition: monoChain.h:82
GLenum GLclampf GLint i
Definition: glfuncs.h:14
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
sweepRange * sweepRangeMake(directedLine *left, Int leftType, directedLine *right, Int rightType)
Definition: partitionY.cc:150
smooth NULL
Definition: ftsmooth.c:513
void * key
Definition: searchTree.h:37
treeNode * TreeNodePredecessor(treeNode *node)
Definition: searchTree.cc:266
Int compChains(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:376
#define exit(n)
Definition: config.h:202
Int cuspType(directedLine *v)
Definition: partitionY.cc:142
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
Int isAbove(directedLine *v, directedLine *e)
Definition: partitionY.cc:89
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
directedLine * getHead()
Definition: monoChain.h:66
float Real
Definition: definitions.h:36
FILE * stderr
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62
treeNode * TreeNodeInsert(treeNode *root, treeNode *newnode, int(*compkey)(void *, void *))
Definition: searchTree.cc:106
int Int
Definition: definitions.h:37